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 ${\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 der Differenz der Jacobi-Matrizen ist die induzierte Matrixnorm. Diese in die Vektornorm aufgelöst ergibt die 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, wobei M die Lipschitz-Konstante auf 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 sich z. B., dass

${\displaystyle \|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

${\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 der 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)