Satz von Kantorowitsch

Der Satz von Kantorowitsch ist eine Aussage der angewandten Mathematik und garantiert die Konvergenz des Newton-Verfahrens unter minimalen Voraussetzungen. Er wurde von Leonid Witaljewitsch Kantorowitsch 1940 erstmals veröffentlicht.

Voraussetzungen

Es seien $X\subset {ℝ}^n$ eine offene konvexe Teilmenge und $F:{ℝ}^n\supset X\to {ℝ}^n$ eine differenzierbare Funktion, deren Ableitung lokal Lipschitz-stetig ist.

D.h. für jedes $𝐱\in X$ existiere die Jacobi-Matrix F'(x) der partiellen Ableitungen und es gebe für jede beschränkte Teilmenge $U\subset X$ eine Konstante L > 0 mit

$\Vert F^{\prime }(𝐱)-F^{\prime }(𝐲)\Vert \le L\Vert 𝐱-𝐲\Vert$ für beliebige $𝐱,𝐲\in U$.

Die Norm der Differenz der Jacobi-Matrizen ist die induzierte Matrixnorm. Diese in die Vektornorm aufgelöst ergibt die Bedingung

$\Vert F^{\prime }(𝐱)(v)-F^{\prime }(𝐲)(v)\Vert \le L\Vert 𝐱-𝐲\Vert \Vert v\Vert$

für beliebige Punkte $x,y\in U$ und Tangentialvektoren $v\in {ℝ}^n$.

In X sei ein Punkt ${𝐱}_0\in U$ bekannt, so dass die Jacobi-Matrix $F^{\prime }({𝐱}_0)$ invertierbar ist. Sei $h_0=F^{\prime }({𝐱}_0{)}^{-1}F({𝐱}_0)$ der Newtonschritt und ${𝐱}_1={𝐱}_0-h_0$ das nächste Glied der Newton-Iteration.

Es bezeichne $\Vert h_0\Vert =\Vert {𝐱}_1-{𝐱}_0\Vert$ die Länge des Newtonschritts.

Aussage

Liegt die Kugel $B=\overline{K}({𝐱}_1,\Vert h_0\Vert )$ um den Punkt ${𝐱}_1$ mit der Länge des ersten Newtonschritts als Radius noch vollständig in U und ist die Ungleichung

${\alpha }_0=M\Vert F^{\prime }({𝐱}_0{)}^{-1}\Vert \Vert h_0\Vert \le \frac{1}{2}$

erfüllt, wobei M die Lipschitz-Konstante auf B ist, dann

1. gibt es eine eindeutige Lösung der Vektorgleichung $F(𝐱)=0$ innerhalb der abgeschlossenen Kugel $B=\overline{K}({𝐱}_1,\Vert h_0\Vert )$ und
2. konvergiert die Newton-Iteration ${𝐱}_{k+1}={𝐱}_k-F^{\prime }({𝐱}_k{)}^{-1}F({𝐱}_k)$ mit Startpunkt ${𝐱}_0$ mit wenigstens linearer Konvergenzgeschwindigkeit zu dieser Lösung.

Verallgemeinerung

Der normierte Raum $({ℝ}^n,\Vert \cdot \Vert )$ kann durch einen beliebigen Banachraum in Definitions- und Wertebereich ersetzt werden, die Differenzierbarkeit ist dann durch die Frechet-Ableitung definiert.

Auch im endlichdimensionalen Fall kann man die Normen in Definitionsbereich $D$ und Wertebereich $W$ unterschiedlich wählen. Mit der speziellen Wahl

$\Vert x{\Vert }_D=\Vert F^{\prime }(x_0)(x){\Vert }_W$

ergibt sich z. B., dass

$\Vert F^{\prime }(x_0{)}^{-1}\Vert =1$

gilt. Die einfachere Form der Konvergenzbedingung ist jedoch aufzuwiegen gegen die komplexere Form der Abschätzung zur Lipschitz-Konstanten.

Beweisskizze

Man kann zeigen, dass für ein konvexes Gebiet U mit Lipschitz-Konstante M der ersten Ableitung immer die Ungleichung

$\Vert F(x+h)-F(x)-F^{\prime }(x)(h)\Vert \le \frac{1}{2}M\Vert h{\Vert }^2$

gilt, falls x und x+h in U enthalten sind. Für $x_0$ und $x_1=x_0+h_0$ mit dem Newtonschritt $h_0$ folgt insbesondere

$\Vert F(x_1)\Vert \le \frac{1}{2}M\Vert h_0{\Vert }^2\le \frac{1}{2}M\Vert F^{\prime }(x_0{)}^{-1}\Vert \Vert F(x)\Vert \Vert h_0\Vert =\frac{1}{2}{\alpha }_0\Vert F(x)\Vert$.

Wegen

$\Vert F^{\prime }(x_1)-F^{\prime }(x_0)\Vert \le M\Vert h_0\Vert \le {\alpha }_0\Vert F^{\prime }(x_0{)}^{-1}{\Vert }^{-1}$

ist $F^{\prime }(x_1)$ nach dem Satz zur Neumann-Reihe ebenfalls invertierbar und es gilt

$\Vert F^{\prime }(x_1{)}^{-1}\Vert \le \frac{1}{1-{\alpha }_0}\Vert F^{\prime }(x_0{)}^{-1}\Vert \le 2\Vert F^{\prime }(x_0{)}^{-1}\Vert$

Diese beiden Abschätzungen kann man zusammenfassen zu einer Abschätzung des nächsten Newtonschrittes $h_1=-F^{\prime }(x_1{)}^{-1}F(x_1)$:

$\Vert h_1\Vert \le {\alpha }_0\Vert h_0\Vert \le \frac{1}{2}\Vert h_0\Vert$

und der die Konvergenz kontrollierenden Kenngröße

${\alpha }_1=M\Vert F^{\prime }(x_1{)}^{-1}\Vert \Vert h_1\Vert \le 2{\alpha }_0^2\le \frac{1}{2}$.

Die Kugel um $x_2=x_1+h_1$ mit Radius $\Vert h_1\Vert$ ist vollständig in B und damit in X enthalten, die Lipschitz-Konstante der kleineren Kugel kann nur kleiner sein als M. 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)=0.

Quellen

• John H. Hubbard und Barbara Burke Hubbard (2007): Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach, Matrix Editions, Lesebeispiel der dritten Auflage (PDF; 422 kB), ISBN 9780971576636

Literatur

• Kantorowitsch, L. (1948): Funktionalanalysis und angewandte Mathematik (russ.). UMN3, 6 (28), 89–185.
• Kantorowitsch, L. W.; Akilow, G. P. (1964): Funktionalanalysis in normierten Räumen. Berlin.
• P. Deuflhard: Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms. Springer, Berlin 2004, ISBN 3-540-21099-7 (Reihe: Springer Series in Computational Mathematics, Vol. 35)