Numerische Bestimmung von Funktionen oder deren Elemente

Bei der computerisierten Lösung mathematischer Aufgabenstellungen steht die Effizienz, d.h. Rechengeschwindigkeit und Speicherplatzbedarf, im Vordergrund. Daher werden Algorithmen gesucht, die diesen Anforderungen gerecht werden.

Beispiel 1

Die Berechnung von n! ist auf die Multiplikation aller ganzen Zahlen (n Î N) in aufsteigender Folge bis zum Wert n mit sich selbst zurückzuführen.

\( n! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5...n \) Gl. 101

Als Sonderfall ist 0! = 1 definiert.

Als Rekursionsformel lautet Gl. 101:

\( n! = n \cdot (n - 1)! \) Gl. 102

(n-1)! wird nun wiederum durch (n-1)(n-2)! usw. berechnet. Wenn endlich 0! = 1 erreicht worden ist (Abbruchbedingung) ist die Rekursion beendet.

Als C-Programm würde die Berechnung der Fakultät wie folgt aussehen:

int fact(int n) { if(n==0) return 1; else return n*fact(n-1); };

Beispiel 2

Die Berechnung der Koeffizienten des PASCAL’schen Dreiecks beruht auf der wiederholten (also rekursiven) Anwendung der folgenden Beziehung:

\( {a_{i,k} } = {a_{i - 1,k} } + {a_{i - 1,k + 1} } \) Gl. 103

Wobei i der Zeilenindex und k der Spaltenindex innerhalb des Dreiecks ist.

Die Startbedingung für i = k = 0 lautet:

\( {a_{0,0} } = 1 \) Gl. 104

Wie aus den Beispielen zu erkennen ist, eignen sich Rekursionen besonders für die prinzipielle Lösung von komplexen mathematischen Problemen.

Inwieweit eine Rekursionsformel Anweisungen für die numerische Lösung solcher Probleme liefern kann, ist fallweise zu untersuchen, da hier u.a. Instabilitäten gegenüber Rundungsfehlern Grenzen setzen können.