Satz von Kantorowitsch

Der Satz von Kantorowitsch garantiert die Konvergenz des Newton-Verfahrens unter minimalen Voraussetzungen.

Voraussetzungen

Es seien X⊂RnX\subset\R^n eine offene Teilmenge und F:Rn⊃X→RnF:\R^n\supset X\to\R^n eine differenzierbare Funktion, deren Ableitung lokal Lipschitz-stetig ist.
D.h. für jedes x∈X\mathbf x\in X existiere die Jacobi-Matrix F´(x)F´ (\bm{x}) der partiellen Ableitungen und es gebe für jede beschränkte Teilmenge U⊂XU\subset X eine Konstante L>0L > 0 mit
∥F ′(x)−F ′(y)∥≤L  ∥x−y∥\|F\, '(\mathbf x)-F\, '(\mathbf y)\|\le L\;\|\mathbf x-\mathbf y\| für beliebige x,y∈U\mathbf{x,y}\in U.
Die Norm der Differenz der Jacobi-Matrizen ist die induzierte Matrixnorm. Diese in die Vektornorm aufgelöst ergibt die Bedingung
∥F′(x)(v)−F′(y)(v)∥≤L  ∥x−y∥ ∥v∥\|F'(\mathbf x)(v)-F'(\mathbf y)(v)\|\le L\;\|\mathbf x-\mathbf y\|\,\|v\|
für beliebige Punkte x,y∈Ux,y\in U und Tangentialvektoren v∈Rnv\in\R^n.
In XX sei ein Punkt x0∈U\mathbf x_0\in U bekannt, so dass die Jacobi-Matrix F ′(x0)F\, '(\mathbf x_0) invertierbar ist. Sei h0=F′(x0)−1F(x0)h_0=F'(\mathbf x_0)^{-1}F(\mathbf x_0) der Newtonschritt und x1=x0−h0\mathbf x_1=\mathbf x_0-h_0 das nächste Glied der Newton-Iteration.
Es bezeichne ∥h0∥=∥x1−x0∥\|h_0\|=\|\mathbf x_1-\mathbf x_0\| die Länge des Newtonschritts.
 
 

Aussage

Liegt die Kugel B=Kˉ(x1,∥h0∥)B=\bar K(\mathbf x_1,\|h_0\|) um den Punkt x1\mathbf x_1 mit der Länge des ersten Newtonschritts als Radius noch vollständig in UU und ist die Ungleichung
α0=M ∥F′(x0)−1∥ ∥h0∥≤12\alpha_0=M\,\|F'(\mathbf x_0)^{-1}\|\,\|h_0\|\le \dfrac12
erfüllt, wobei MM die Lipschitz-Konstante auf BB ist, dann
  1. gibt es eine eindeutige Lösung der Vektorgleichung F(x)=0F(\mathbf x)=0 innerhalb der abgeschlossenen Kugel B=Kˉ(x1,∥h0∥)B=\bar K(\mathbf x_1,\|h_0\|) und
  2. konvergiert die Newton-Iteration xk+1=xk−F′(xk)−1F(xk)\mathbf x_{k+1}=\mathbf x_k-F'(\mathbf x_k)^{-1}F(\mathbf x_k) mit Startpunkt x0\mathbf x_0 mit wenigstens linearer Konvergenzgeschwindigkeit zu dieser Lösung.

Verallgemeinerung

Der normierte Raum (Rn,∥⋅∥)(\R^n,\|\cdot\|) kann durch einen beliebigen Banach-Raum in Definitions- und Wertebereich ersetzt werden, die Differenzierbarkeit ist dann durch die Fréchet-Ableitung definiert.
Auch im endlichdimensionalen Fall kann man die Normen in Definitions- und Wertebereich unterschiedlich wählen. Mit
∥x∥Def=∥F ′(x0)( x )∥Wert\|x\|_{\text{Def}}=\|F\, '(x_0)(\,x\,)\|_{\text{Wert}}
ergibt sich z.B., dass
∥F ′(x0)−1∥=1\|F\, '(x_0)^{-1}\|=1
gilt. Die einfachere Form der Konvergenzbedingung ist jedoch aufzuwiegen gegen die komplexere Form der Absätzung zur Lipschitz-Konstanten.

Beweisskizze

Man kann zeigen, dass für ein konvexes Gebiet UU mit Lipschitz-Konstante MM der ersten Ableitung immer die Ungleichung
∥F(x+h)∥≤∥F(x+h)−F(x)−F′(x)(h)∥+12M ∥h∥2 \|F(x+h)\|\le \|F(x+h)-F(x)-F'(x)(h)\|+\dfrac12 M\,\|h\|^2
gilt, falls xx und x+hx+h in UU enthalten sind. Für x0x_0 und x1=x0+h0x_1=x_0+h_0 mit dem Newtonschritt h0h_0 folgt insbesondere
∥F(x1)∥≤12M ∥h0∥2 \|F(x_1)\|\le\dfrac12 M\,\|h_0\|^2≤12M ∥F′(x0)−1∥ ∥F(x)∥ ∥h0∥ \le \dfrac12 M\,\|F'(x_0)^{-1}\|\,\|F(x)\|\,\|h_0\|=12α0 ∥F(x)∥ =\dfrac12 \alpha_0 \,\|F(x)\| .
Wegen
∥F ′(x1)−F ′(x0)∥\|F\, '(x_1)-F\, '(x_0)\|≤M∥h0∥ \le M\|h_0\|≤α0 ∥F ′(x0)−1∥−1 \le\alpha_0\,\|F\, '(x_0)^{-1}\|^{-1}
ist F ′(x1)F\, '(x_1) nach dem Satz zur Neumann-Reihe ebenfalls invertierbar und es gilt
∥F ′(x1)−1∥≤11−α0 ∥F ′(x0)−1∥≤2 ∥F ′(x0)−1∥\|F\, '(x_1)^{-1}\| \le\dfrac1{1-\alpha_0}\,\|F\, '(x_0)^{-1}\|\le 2\,\|F\, '(x_0)^{-1}\|
Diese beiden Abschätzungen kann man zusammenfassen zu einer Abschätzung des nächsten Newtonschrittes h1=−F ′(x1)−1F(x1)h_1=-F\, '(x_1)^{-1}F(x_1):
∥h1∥≤α0 ∥h0∥≤12 ∥h0∥\|h_1\|\le\alpha_0\,\|h_0\|\le\dfrac12\,\|h_0\|
und der die Konvergenz kontrollierenden Kenngröße
α1=M∥F ′(x1)−1∥ ∥h1∥≤2α02≤12\alpha_1=M\|F\, '(x_1)^{-1}\|\,\|h_1\|\le2\alpha_0^2\le\dfrac12.
Die Kugel um x2=x1+h1x_2=x_1+h_1 mit Radius ∥h1∥\|h_1\| ist [!vollständig] in BB und damit in XX enthalten, die Lipschitz-Konstante der kleineren Kugel kann nur kleiner sein als MM. Es sind also alle Voraussetzungen für den nächsten Schritt hergestellt. Per Induktion wird dies auf die gesamte Newton-Iteration fortgesetzt. Es ergibt sich eine Folge von ineinander enthaltenen Kugeln, deren Radius sich in jedem Schritt mindestens halbiert. Der gemeinsame Durchschnitt aller Kugeln ist also genau ein Punkt, der auch Grenzwert der Newton-Iteration ist. Die Funktionswerte der Newton-Iteration reduzieren sich in jedem Schritt auf ein Viertel des vorhergehenden Funktionswertes, bilden also eine Nullfolge. Der Grenzwert der Newton-Iteration löst also die Vektorgleichung F(x)=0F(x)=0.

Die Mathematik als Fachgebiet ist so ernst, daß man keine Gelegenheit versäumen sollte, dieses Fachgebiet unterhaltsamer zu gestalten.

Blaise Pascal

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Satz von Kantorowitsch aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Nichtlineare Gleichungssysteme