Kantorovichs sats

Kantorovich-satsen , eller Newton-Kantorovitj-satsen, är ett matematiskt påstående om den semi-lokala konvergensen av Newtons metod . Det angavs först av Leonid Kantorovich 1948. Det liknar formen av Banachs fasta punktsats , även om det anger existensen och unikheten hos en nolla snarare än en fast punkt .

Newtons metod konstruerar en sekvens av punkter som under vissa förhållanden kommer att konvergera till en lösning $x$ av en ekvation $f(x)=0$ eller en vektorlösning av ett ekvationssystem $F(x)=0$ . Kantorovich-satsen ger villkor på startpunkten i denna sekvens. Om dessa villkor är uppfyllda finns en lösning nära den initiala punkten och sekvensen konvergerar till den punkten.

Antaganden

Låt $X\subset \mathbb {R} ^{n}$ vara en öppen delmängd och $F:X\subset \mathbb {R} ^{ n}\to \mathbb {R} ^{n}$ en differentierbar funktion med en Jacobian $F^{\prime }(\mathbf {x} )$ som lokalt är Lipschitz kontinuerlig (till exempel om $F$ är två gånger differentierbar). Det vill säga, det antas att för alla $x\in X$ finns en öppen delmängd $U\subset X$ så att $x\in U$ och det finns en konstant $L>0$ så att för alla $\mathbf {x} ,\mathbf {y} \in U$

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

håller. Normen till vänster är någon operatornorm som är kompatibel med vektornormen till höger. Denna olikhet kan skrivas om till att endast använda vektornormen. Sedan för valfri vektor ${\displaystyle \mathbf {v} \in \mathbb {R} ^{n}} är$ olikheten

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

måste hålla.

Välj nu valfri startpunkt $\mathbf {x} _{0}\in X$ . Antag att $F'(\mathbf {x} _{0})$ är inverterbar och konstruera Newtonsteget $\mathbf {h} _{0}=-F'(\mathbf {x} _{0})^{-1}F(\mathbf {x} _{0}).$

Nästa antagande är att inte bara nästa punkt $\mathbf {x} _{1}=\mathbf {x} _{0}+\mathbf {h} _{0}$ utan hela bollen $B(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)$ finns i mängden ${\ displaystil X}$ . Låt $M$ vara Lipschitz-konstanten för Jacobianen över denna boll (förutsatt att den existerar).

Som en sista förberedelse, konstruera rekursivt, så länge det är möjligt, sekvenserna ${\displaystyle (\mathbf {x} _{k})_{k}} ,$ ( $\displaystyle (\mathbf {h} _{k})_{k}}$ , $(\alpha _{k})_{k}$ enl .

${\begin{alignedat}{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{ aligned}}$

Påstående

Om nu $\alpha _{0}\leq {\tfrac {1}{2}}$ så

1. en lösning $\mathbf {x} ^{*}$ av $F(\mathbf {x} ^{*})=0$ finns inuti den slutna bollen ${\bar {B}}(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)$ och
2. Newton-iterationen som börjar på $\mathbf {x} _{0}$ konvergerar till $\mathbf {x} ^{*}$ med åtminstone linjär konvergensordning.

Ett påstående som är mer exakt men något svårare att bevisa använder rötterna $t^{\ast }\leq t^{**}$ i kvadratpolynomet

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

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

och deras förhållande

$\theta ={\frac {t^{*}}{t^{**}}}={\frac {1-{\sqrt {1-2\alpha _{0}}}}{1 +{\sqrt {1-2\alpha _{0}}}}}.$

Sedan

1. en lösning $\mathbf {x} ^{*}$ finns inuti den slutna bollen ${\bar {B }}(\mathbf {x} _{1},\theta \|\mathbf {h} _{0}\|)\subset {\bar {B}}(\mathbf {x} _{0},t ^{*})$
2. den är unik inuti den större bollen $B(\mathbf {x} _{0},t^{*\ast })$
3. och konvergensen till lösningen av $F$ domineras av konvergensen av Newton-iterationen av det kvadratiska polynomet $p(t)$ mot dess minsta rot $t^{ \ast }$ , om $t_{0}=0,\,t_{k+1}=t_{k }-{\tfrac {p(t_{k})}{p'(t_{k})}}$ , sedan

   $\|\mathbf {x} _{k+p}-\mathbf {x} _{k}\|\leq t_{k+p}-t_{k}.$

4. Den kvadratiska konvergensen erhålls från feluppskattningen

   $\|\mathbf {x} _{n+1}-\mathbf {x} ^{*}\|\leq \theta ^{2^{n}}\|\mathbf {x} _{n +1}-\mathbf {x} _{n}\|\leq {\frac {\theta ^{2^{n}}}{2^{n}}}\|\mathbf {h} _{0 }\|.$

Naturlig följd

1986 bevisade Yamamoto att felutvärderingarna av Newtonmetoden som Doring (1969), Ostrowski (1971, 1973), Gragg-Tapia (1974), Potra-Ptak (1980), Miel (1981), Potra (1984) , kan härledas från Kantorovich-satsen.

Generaliseringar

Det finns en q -analog för Kantorovich-satsen. För andra generaliseringar/variationer, se Ortega & Rheinboldt (1970).

Ansökningar

Oishi och Tanabe hävdade att Kantorovich-satsen kan tillämpas för att få tillförlitliga lösningar för linjär programmering .

Vidare läsning

•   John H. Hubbard och Barbara Burke Hubbard : Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach , Matrix Editions, ISBN 978-0-9715766-3-6 ( förhandsvisning av 3. upplagan och exempelmaterial inklusive Kant.-thm . )
•   Yamamoto, Tetsuro (2001). "Historisk utveckling i konvergensanalys för Newtons och Newtonliknande metoder". I Brezinski, C.; Wuytack, L. (red.). Numerisk analys: Historisk utveckling under 1900-talet . Nord-Holland. s. 241–263. ISBN 0-444-50617-9 .