Satz von Kantorowitsch

Der Satz v​on Kantorowitsch i​st eine Aussage d​er angewandten Mathematik u​nd garantiert d​ie Konvergenz d​es Newton-Verfahrens u​nter minimalen Voraussetzungen. Er w​urde von Leonid Witaljewitsch Kantorowitsch 1940 erstmals veröffentlicht.

Voraussetzungen

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

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

${\displaystyle \|F'(\mathbf {x} )-F'(\mathbf {y} )\|\leq L\;\|\mathbf {x} -\mathbf {y} \|}$ für beliebige ${\displaystyle \mathbf {x,y} \in U}$.

Die Norm d​er Differenz d​er Jacobi-Matrizen i​st die induzierte Matrixnorm. Diese i​n die Vektornorm aufgelöst ergibt d​ie Bedingung

${\displaystyle \|F'(\mathbf {x} )(v)-F'(\mathbf {y} )(v)\|\leq L\;\|\mathbf {x} -\mathbf {y} \|\,\|v\|}$

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

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

Es bezeichne ${\displaystyle \|h_{0}\|=\|\mathbf {x} _{1}-\mathbf {x} _{0}\|}$ die Länge des Newtonschritts.

Aussage

Liegt die Kugel ${\displaystyle B={\bar {K}}(\mathbf {x} _{1},\|h_{0}\|)}$ um den Punkt ${\displaystyle \mathbf {x} _{1}}$ mit der Länge des ersten Newtonschritts als Radius noch vollständig in U und ist die Ungleichung

${\displaystyle \alpha _{0}=M\,\|F'(\mathbf {x} _{0})^{-1}\|\,\|h_{0}\|\leq {\tfrac {1}{2}}}$

erfüllt, w​obei M d​ie Lipschitz-Konstante a​uf B ist, dann

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

Verallgemeinerung

Der normierte Raum ${\displaystyle (\mathbb {R} ^{n},\|\cdot \|)}$ 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 ${\displaystyle D}$ und Wertebereich ${\displaystyle W}$ unterschiedlich wählen. Mit der speziellen Wahl

${\displaystyle \|x\|_{D}=\|F'(x_{0})(\,x\,)\|_{W}}$

ergibt s​ich z. B., dass

${\displaystyle \|F'(x_{0})^{-1}\|=1}$

gilt. Die einfachere Form d​er Konvergenzbedingung i​st jedoch aufzuwiegen g​egen die komplexere Form d​er Abschätzung z​ur Lipschitz-Konstanten.

Beweisskizze

Man k​ann zeigen, d​ass für e​in konvexes Gebiet U m​it Lipschitz-Konstante M d​er ersten Ableitung i​mmer die Ungleichung

${\displaystyle \|F(x+h)-F(x)-F'(x)(h)\|\leq {\tfrac {1}{2}}M\,\|h\|^{2}}$

gilt, falls x und x+h in U enthalten sind. Für ${\displaystyle x_{0}}$ und ${\displaystyle x_{1}=x_{0}+h_{0}}$ mit dem Newtonschritt ${\displaystyle h_{0}}$ folgt insbesondere

${\displaystyle \|F(x_{1})\|\leq {\tfrac {1}{2}}M\,\|h_{0}\|^{2}\leq {\tfrac {1}{2}}M\,\|F'(x_{0})^{-1}\|\,\|F(x)\|\,\|h_{0}\|={\tfrac {1}{2}}\alpha _{0}\,\|F(x)\|}$.

Wegen

${\displaystyle \|F'(x_{1})-F'(x_{0})\|\leq M\|h_{0}\|\leq \alpha _{0}\,\|F'(x_{0})^{-1}\|^{-1}}$

ist ${\displaystyle F'(x_{1})}$ nach dem Satz zur Neumann-Reihe ebenfalls invertierbar und es gilt

${\displaystyle \|F'(x_{1})^{-1}\|\leq {\tfrac {1}{1-\alpha _{0}}}\,\|F'(x_{0})^{-1}\|\leq 2\,\|F'(x_{0})^{-1}\|}$

Diese beiden Abschätzungen kann man zusammenfassen zu einer Abschätzung des nächsten Newtonschrittes ${\displaystyle h_{1}=-F'(x_{1})^{-1}F(x_{1})}$:

${\displaystyle \|h_{1}\|\leq \alpha _{0}\,\|h_{0}\|\leq {\tfrac {1}{2}}\,\|h_{0}\|}$

und d​er die Konvergenz kontrollierenden Kenngröße

${\displaystyle \alpha _{1}=M\|F'(x_{1})^{-1}\|\,\|h_{1}\|\leq 2\alpha _{0}^{2}\leq {\tfrac {1}{2}}}$.

Die Kugel um ${\displaystyle x_{2}=x_{1}+h_{1}}$ mit Radius ${\displaystyle \|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 (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)