Satz von Kantorowitsch

aus Wikipedia, der freien Enzyklopädie

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.

Inhaltsverzeichnis 1 Voraussetzungen 2 Aussage 3 Verallgemeinerung 4 Beweisskizze 5 Quellen 6 Literatur

[Bearbeiten] Voraussetzungen

Es seien eine offene Teilmenge und eine differenzierbare Funktion, deren Ableitung lokal Lipschitz-stetig ist.

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

für beliebige .

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

für beliebige Punkte und Tangentialvektoren .

In X sei ein Punkt bekannt, so dass die Jacobi-Matrix invertierbar ist. Sei der Newtonschritt und das nächste Glied der Newton-Iteration.

Es bezeichne die Länge des Newtonschritts.

[Bearbeiten] Aussage

Liegt die Kugel um den Punkt mit der Länge des ersten Newtonschritts als Radius noch vollständig in U und ist die Ungleichung

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

1. gibt es eine eindeutige Lösung der Vektorgleichung innerhalb der abgeschlossenen Kugel und
2. konvergiert die Newton-Iteration mit Startpunkt mit wenigstens linearer Konvergenzgeschwindigkeit zu dieser Lösung.

[Bearbeiten] Verallgemeinerung

Der normierte Raum 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 Definitions- und Wertebereich unterschiedlich wählen. Mit

ergibt sich z.B., dass

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

[Bearbeiten] Beweisskizze

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

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

.

Wegen

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

Diese beiden Abschätzungen kann man zusammenfassen zu einer Abschätzung des nächsten Newtonschrittes h₁ = − F'(x₁) ^{− 1}F(x₁):

und der die Konvergenz kontrollierenden Kenngröße

.

Die Kugel um x₂ = x₁ + h₁ mit Radius 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.

[Bearbeiten] Quellen

• John H. Hubbard und Barbara Burke Hubbard: Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach,

Matrix Editions, Lesebeispiel der dritten Auflage (vorauss. März 2007)

[Bearbeiten] 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 .