Twierdzenie Kantorowicza

Twierdzenie Kantorowicza lub twierdzenie Newtona-Kantorowicza jest matematycznym stwierdzeniem dotyczącym półlokalnej zbieżności metody Newtona . Po raz pierwszy został stwierdzony przez Leonida Kantorowicza w 1948 roku. Jest podobny do postaci twierdzenia Banacha o punkcie stałym , chociaż stwierdza istnienie i jednoznaczność zera, a nie punktu stałego .

Metoda Newtona konstruuje sekwencję punktów, które w pewnych warunkach zbiegają się do rozwiązania równania lub $= 0$$x$ { \ ${\ Displaystyle F (x) = 0}$ . Twierdzenie Kantorowicza podaje warunki w punkcie początkowym tego ciągu. Jeśli te warunki są spełnione, to rozwiązanie istnieje blisko punktu początkowego i ciąg jest zbieżny do tego punktu.

Założenia

Niech ${\ Displaystyle X \ podzbiór \ mathbb {R} ^ {n}}$ będzie podzbiorem otwartym i $}}$${\ Displaystyle F: X \ podzbiór \ mathbb {R} ^ {$$Lipschitza$ { funkcja różniczkowalna z Jakobianem , który lokalnie (na przykład jeśli ${\ Displaystyle F}$ jest dwukrotnie różniczkowalna). Oznacza to, że dla każdego ${\$ otwarty podzbiór , że $}$$in$ displaystyle istnieje stała $U$ , że ​​dla dowolnego ${\ Displaystyle \ mathbf {x}, \ mathbf {y} \ w$

${\ Displaystyle \| F '(\ mathbf {x}) -F '(\ mathbf {y}) \|\ równoważnik L \ ;\|\mathbf {x} -\mathbf {y} \|}$

posiada. Norma po lewej stronie to pewna norma operatora, która jest zgodna z normą wektora po prawej stronie. Tę nierówność można przepisać tak, aby używała tylko normy wektorowej. Następnie dla dowolnego wektora nierówność ${\ Displaystyle \ mathbf {v} \ in \ mathbb {R} ^ {n}}$

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

trzeba trzymać.

Teraz wybierz dowolny punkt początkowy ${\ Displaystyle \ mathbf {x} _ {0} \ in X}$ . Załóżmy, $że$${\ Displaystyle \ mathbf {h} _ {0} = - F '(\ mathbf {x} _ {0}) ^ {- 1} F (\ mathbf {x} _ {0}).}$ krok

Kolejnym założeniem jest $ale$ punkt cała piłka ${\ Displaystyle B (\ mathbf {x} _ {1}, \|\ mathbf {h} _ {0} \|)}$ jest zawarta w zbiorze ${\ styl wyświetlania X}$ . Niech $stałą$ Lipschitza dla Jakobianu nad tą piłką (zakładając, że istnieje)

Jako ostatnie przygotowanie, konstruuj rekurencyjnie, tak długo, jak to możliwe, sekwencje ${\ Displaystyle (\ mathbf {x} _ {k}) _ {k}}$ , ${\ Displaystyle (\ mathbf {h} _ {k}) _ {k}}$ , ${\ Displaystyle (\ alfa _ {k}) _ {k}}$ według

${\ Displaystyle {\ rozpocząć {wyrównane w} {2} \ mathbf {h} _ {k} & = - F '(\ mathbf {x} _ {k}) ^ {- 1} F (\ mathbf {x} _ {k})\\[0.4em]\alpha _{k}&=M\,\|F'(\mathbf {x} _{k})^{-1}\|\,\|\mathbf { h} _{k}\|\\[0.4em]\mathbf {x} _{k+1}&=\mathbf {x} _{k}+\mathbf {h} _{k}.\end{ wyrównane}}}$

Oświadczenie

Teraz , jeśli to ${\ Displaystyle \ alpha _ {0} \ równoważnik {\ tfrac {1} {2}}}$

1. rozwiązanie istnieje $wewnątrz$$_$ _ $_$ _
2. iteracja Newtona rozpoczynająca się $zbiega$ do $co$ najmniej liniowego rzędu zbieżności

Stwierdzenie, które jest dokładniejsze, ale nieco trudniejsze do udowodnienia, wykorzystuje pierwiastki wielomianu kwadratowego ${\ Displaystyle t ^ {\ ast} \ równoważnik t ^ {**}}$

${\ Displaystyle p (t) = \ lewo ({\ tfrac {1} {2}} L\|F'(\mathbf {x} _{0})^{-1}\|^{-1}\right)t^{2}-t+\|\mathbf {h} _{0}\ |}$ ,

${\ Displaystyle t ^ {\ ast / **} = {\ Frac {2 \|\ mathbf {h} _ {0} \|} 1 \ pm {\ sqrt {1-2 \ alfa _ { 0}}}}}}$

i ich stosunek

${\ Displaystyle \ theta = {\ Frac {t ^ {*}} {t ^ {**}}} = {\ Frac {1- {\ sqrt {1-2 \ alfa _ {0}}}} {1 +{\sqrt {1-2\alfa _{0}}}}}.}$

Następnie

1. rozwiązanie istnieje wewnątrz zamkniętej kuli $Displaystyle {\ bar {$$x$
2. jest wyjątkowy wewnątrz większej kuli ${\ Displaystyle B (\ mathbf {x} _ {0}, t ^ {* \ as})}$
3. a zbieżność do rozwiązania jest zdominowana ${$ zbieżność iteracji Newtona wielomianu kwadratowego $jego$ najmniejszego pierwiastka ${ \ast }}$ , jeśli ${\ Displaystyle t_ {0} = 0, \, t_ {k + 1} = t_ {k} - {\ tfrac {p (t_ {k})} {p' (t_ {k})}}}, a$ następnie

   ${\ Displaystyle \|\ mathbf {x} _ {k + p} - \ mathbf {x} _ {k} \|\ równoważnik t_ {k + p} -t_ {k}.}$

4. Kwadratową zbieżność uzyskuje się z oszacowania błędu

   ${\ Displaystyle \|\ mathbf {x} _ {n + 1} - \ mathbf {x} ^ {*} \|\ równoważnik \ theta ^ {2 ^ {n}} \|\ mathbf {x} _ {n +1}-\mathbf {x} _{n}\|\leq {\frac {\theta ^{2^{n}}}{2^{n}}}\|\mathbf {h} _{0 }\|.}$

Następstwo

W 1986 roku Yamamoto udowodnił, że oceny błędów metody Newtona takie jak Doring (1969), Ostrowski (1971, 1973), Gragg-Tapia (1974), Potra-Ptak (1980), Miel (1981), Potra (1984) , można wyprowadzić z twierdzenia Kantorowicza.

Uogólnienia

Istnieje analog q dla twierdzenia Kantorowicza. Inne uogólnienia/odmiany można znaleźć w Ortega i Rheinboldt (1970).

Aplikacje

Oishi i Tanabe twierdzili, że twierdzenie Kantorowicza można zastosować do uzyskania niezawodnych rozwiązań programowania liniowego .

Dalsza lektura

•   John H. Hubbard i Barbara Burke Hubbard : Rachunek wektorowy, algebra liniowa i formy różniczkowe: ujednolicone podejście , Matrix Editions, ISBN 978-0-9715766-3-6 ( podgląd 3. wydania i przykładowy materiał, w tym Kant.-thm . )
•   Yamamoto, Tetsuro (2001). „Historyczny rozwój analizy konwergencji dla metod Newtona i metod podobnych do Newtona”. W Brzezińskim C.; Wuytack, L. (red.). Analiza numeryczna: rozwój historyczny w XX wieku . Holandia Północna. s. 241–263. ISBN 0-444-50617-9 .