20.5 Das mehrdimensionale Newton-Verfahren
Das mehrdimensionale Newton-Verfahren
Um Gleichungen der Form \( F(x)=0 \) mit einer differenzierbaren Funktion \( F:\mathbb {R}\to \mathbb {R} \) näherungsweise zu lösen, ist oft das Newton-Verfahren sehr gut geeignet. Es basiert darauf, dass man die "komplizierte" Funktion \( F \) durch eine lineare Näherung \( F(x_0)+(x-x_0)F’(x_0) \) ersetzt und statt \(F(x)=0 \) die Gleichung
\( F(x_0)+F’(x_0)\cdot(x-x_0)=0 \)
löst. Etwas genauer formuliert: Man konstruiert sich eine Folge von Punkten \( x_0,x_1,x_2,\ldots \), so dass \( x_{n+1} \) für jede Zahl \( n\in \mathbb{N} \) gerade die Lösung von
\( F(x_n)+F’(x_n)\cdot(x-x_n)=0 \)
ist. Auf diese Weise kann man sich ausgehend von einer ersten Näherung \( x_0 \) immer weitere Näherungswerte verschaffen, so lange, bis man meint, nahe genug an der exakten Lösung zu sein. Die Iterationsvorschrift des eindimensionalen Newton-Verfahrens lautet daher
\( x_{n+1}=x_n-\displaystyle\frac{F(x_n)}{F’(x_n)}. \)
Im Mehrdimensionalen geht man jetzt so analog wie möglich vor. Man betrachtet die vektorwertige differenzierbare Funktion \( \vec{F}:\mathbb {R}^ n\to \mathbb {R}^n \), also "‘\( n \) Gleichungen in \( n \) Variablen"’. Unsere Erfahrung mit \( n \) linearen Gleichungen für \( n \) Variablen sagt uns, dass wir eine eindeutige Lösung erwarten können, wenn die Koeffizientenmatrix invertierbar ist. Diese Aussage ist zwar für nichtlineare Funktionen so nicht richtig, man kann aber erwarten, dass die Lösungen des nichtlinearen Gleichungssystems \( \vec{F}(\vec{x})=\vec{0} \) nur aus einzelnen Punkten besteht, wenn die Jacobi-Matrix von \( \vec{F} \), die im nichtlinearen Fall die Rolle der Koeffizientenmatrix des linearen Gleichungssystems übernimmt, invertierbar ist. Wenn wir \(\vec{F}(\vec{x}) \) durch die lineare Funktion \( \vec{F}(\vec{x}_0)+D\vec{F}(\vec{x}_0)(\vec{x}-\vec{x}_0) \) ersetzen, müssen wir statt \(\vec{F}(\vec{x})=\vec{0} \) die Gleichung
\( \vec{F}(\vec{x}_0)+D\vec{F}(\vec{x}_0)(\vec{x}-\vec{x}_0)=\vec{0} \)
lösen. Diese (lineare!) Gleichung lässt sich nach \( \vec{x} \) auflösen, wenn die Jacobi-Matrix $D\vec{F}(\vec{x}_0)$ invertierbar ist. Das führt zu folgendem Verfahren:
Sei \( \vec{F}:\mathbb{R}^ n\to \mathbb{R}^n \) eine differenzierbare Funktion, von der man eine Nullstelle bestimmen möchte, und \(\vec{x}_0 \) ein beliebiger Startwert (idealerweise nicht weit entfernt von der gesuchten Nullstelle). Dann nennt man die Iterationsvorschrift
\( \vec{x}_{n+1}=\vec{x}_n-(D\vec{F}(\vec{x}_n))^{-1}\vec{F}(\vec{x}_n), \)
mit der eine Folge \( \vec{x}_1, \vec{x}_2,\ldots \) von Punkten im \( \mathbb {R}^n \) erzeugt wird, das mehrdimensionale Newtonverfahren.
Die Hoffnung ist nun, dass die Folge \( \vec{x}_1, \vec{x}_2,\ldots \) gegen eine Nullstelle von \(\vec{F}\) konvergiert und dass \(\vec{x}_2\) oder \(\vec{x}_3\) schon eine gute Näherung für diese Nullstelle bieten.