Newton-Verfahren

Beschreibung

Das Newton-Verfahren ist ein Iteratives Verfahren, das genutzt wird, um Nullstellen zu bestimmen

Definition

Eindimensional

Sei $I\in \mathbb{R}$ Intervall, $f^{\prime }:I\to \mathbb{R}$ differenzierbar mit $f^{\prime }(x)\ne 0$ auf $I$ und mit einziger Nullstelle $\hat{x}\in I$.

$f$ erfülle außerdem eine der viel Eigenschaften:

• $f$ streng monoton steigend und konvex
• $f$ streng monoton steigend und konkav
• $f$ streng monoton fallend und konvex
• $f$ streng monoton fallend und konkav

Dann ist das Newtonverfahren durch folgende Iteration definiert: $x_0\in A,x_{n+1}:=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$

Q: Bedingungen für das eindimensionale Newtonverfahren A: - $I\in \mathbb{R}$ Intervall

• $f^{\prime }:I\to \mathbb{R}$ differenzierbar
• einzige Nullstelle $\hat{x}\in I$.
• $x_0,x_1\in I$ auf verschiedener Seite von $\hat{x}$ oder $x_0,x_1\in I$ auf gleicher Seite von $\hat{x}$

Q: Monotonie und Krümmungsbedingungen für das Newtonverfahren A: - $f$ streng monoton steigend und konvex

• $f$ streng monoton steigend und konkav
• $f$ streng monoton fallend und konvex
• $f$ streng monoton fallend und konkav

Q: Formel des Eindimensionalen Newton-Verfahrens A: $x_0\in A,x_{n+1}:=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$

Mehrdimensional

Sei $A\subseteq {\mathbb{R}}^m$, $f:A\to {\mathbb{R}}^m$ differenzierbar

Das Newton-Verfahren errechnet sich durch die Iteration $x_0\in A,x_{n+1}:=x_n-(Df(x_n){)}^{-1}f(x_n)$ oder äquivalent durch $Df(x_n)x_{n+1}=Df(x_n)x_n-f(x_n)$

Q: Formel des Mehrdimensionalen Newton-Verfahrens A: $x_{n+1}:=x_n-(Df(x_n){)}^{-1}f(x_n)$

Eigenschaften

Schneller als der Banachsche Fixpunktsatz

Die iterative Anwendung des Newton-Verfahrens benötigt mehr Voraussetzungen als der Banachsche Fixpunktsatz, konvergiert jedoch auch schneller.

Lokal konvergent

Wählt man einen Startpunkt nah genug an einer Nullstelle, so konvergiert auch das mehrdimensionale Newton-Verfahren.

Formell: Sei $\Vert \cdot \Vert$ eine Norm, $x_{\ast }\in A$ die Nullstelle, $r>0$ genügend klein, sodass der Ball in $A$ liegt: $B_r(x_{\ast })\subseteq A$. Sei $Df(x_{\ast })$ invertierbar und $\beta >0$ so, dass bei der induzierten Matrixnorm $\Vert (Df(x_{\ast }){)}^{-1}\Vert \le \beta$ und $Df:B_r(x_{\ast })\to \mathcal{L}({\mathbb{R}}^n,{\mathbb{R}}^m)$ $L$-lipschitzstetig.

Wähle $\delta :=\min \text{ges}r,\frac{1}{2\beta L}$. Dann ist für jedes $x_0\in B_{\delta }(x_{\ast })$ das Newtonverfahren wohldefiniert und ${\lim }_{n\to \infty }{x}_n=x_{\ast }$.

Q: Welchen Radius $\delta$ muss ein Ball um eine Nullstelle $x_{\ast }$ haben, damit das Newton-Verfahren konvergiert? A: $\delta :=\min \left\{r,\frac{1}{2\beta L}\right\}$ wobei

• $r$ der Radius eines größeren, umgebenden Balls ist.
• $\beta =\Vert (Df(x_{\ast }){)}^{-1}\Vert$
• $L$ die Lipschitzkonstante von $Df$ auf $B_r(x_{\ast })$ ist

Fehlerabschätzung

Mit oberem Konvergenzbedingungen gilt die Fehlerabschätzung: $\Vert x_{n+1}-x_{\ast }\Vert \le \beta L\Vert x_n-x_{\ast }{\Vert }^2\le \frac{1}{2}\Vert x_n-x_{\ast }\Vert$ $\Vert x_n-x_{\ast }\Vert \le \text{klam}{\frac{1}{2}}^{2^n-1}\Vert x_0-x_{\ast }\Vert$