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\R^n$ eine offene konvexe Teilmenge und $F:\R^n\supset X\to\R^n$ eine differenzierbare Funktion, deren Ableitung lokal Lipschitz-stetig ist.

D.h. für jedes $\mathbf x\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

$\|F'(\mathbf x)-F'(\mathbf y)\|\le L\;\|\mathbf x-\mathbf y\|$ für beliebige $\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'(\mathbf x)(v)-F'(\mathbf y)(v)\|\le L\;\|\mathbf x-\mathbf y\|\,\|v\|$

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

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

Es bezeichne $\|h_0\|=\|\mathbf x_1-\mathbf x_0\|$ die Länge des Newtonschritts.

Aussage

Liegt die Kugel $B=\bar K(\mathbf x_1,\|h_0\|)$ um den Punkt $\mathbf x_1$ mit der Länge des ersten Newtonschritts als Radius noch vollständig in U und ist die Ungleichung

$\alpha_0=M\,\|F'(\mathbf x_0)^{-1}\|\,\|h_0\|\le \tfrac12$

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

1. gibt es eine eindeutige Lösung der Vektorgleichung $F(\mathbf x)=0$ innerhalb der abgeschlossenen Kugel $B=\bar K(\mathbf x_1,\|h_0\|)$ und
2. konvergiert die Newton-Iteration $\mathbf x_{k+1}=\mathbf x_k-F'(\mathbf x_k)^{-1}F(\mathbf x_k)$ mit Startpunkt $\mathbf x_0$ mit wenigstens linearer Konvergenzgeschwindigkeit zu dieser Lösung.

Verallgemeinerung

Der normierte Raum $(\R^n,\|\cdot\|)$ kann durch einen beliebigen Banach-Raum 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

$\|x\|_D=\|F'(x_0)(\,x\,)\|_W$

ergibt sich z.B., dass

$\|F'(x_0)^{-1}\|=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

$\|F(x+h)-F(x)-F'(x)(h)\| \le \tfrac12 M\,\|h\|^2$

gilt, falls x und x+h in U enthalten sind. Für x₀ und x₁ = x₀ + h₀ mit dem Newtonschritt h₀ folgt insbesondere

$\|F(x_1)\|\le\tfrac12 M\,\|h_0\|^2\le \tfrac12 M\,\|F'(x_0)^{-1}\|\,\|F(x)\|\,\|h_0\|=\tfrac12 \alpha_0 \,\|F(x)\|$.

Wegen

$\|F'(x_1)-F'(x_0)\|\le M\|h_0\|\le\alpha_0\,\|F'(x_0)^{-1}\|^{-1}$

ist F'(x₁) nach dem Satz zur Neumann-Reihe ebenfalls invertierbar und es gilt

$\|F'(x_1)^{-1}\| \le\tfrac1{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 h₁ = − F'(x₁) ^{− 1}F(x₁):

$\|h_1\|\le\alpha_0\,\|h_0\|\le\tfrac12\,\|h_0\|$

und der die Konvergenz kontrollierenden Kenngröße

$\alpha_1=M\|F'(x_1)^{-1}\|\,\|h_1\|\le2\alpha_0^2\le\tfrac12$.

Die Kugel um x₂ = x₁ + h₁ mit Radius $\|h_1\|$ 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, 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)