Kantorovichova věta - Kantorovich theorem - Wikipedia

The Kantorovichova věta, nebo Newton – Kantorovichova věta, je matematický výrok o semi-lokálním konvergence z Newtonova metoda. Poprvé to uvedl Leonid Kantorovič v roce 1948.^[1][2] Je to podobné jako forma Banachova věta o pevném bodě, i když uvádí existenci a jedinečnost a nula spíše než a pevný bod.^[3]

Newtonova metoda konstruuje posloupnost bodů, které za určitých podmínek konvergují k řešení ${ displaystyle x}$ rovnice ${ displaystyle f (x) = 0}$ nebo vektorové řešení soustavy rovnic ${ displaystyle F (x) = 0}$. Kantorovichova věta udává podmínky pro počáteční bod této posloupnosti. Pokud jsou tyto podmínky splněny, existuje řešení blízko počátečního bodu a posloupnost konverguje k tomuto bodu.^[1][2]

Předpoklady

Nechat ${ displaystyle X podmnožina mathbb {R} ^ {n}}$ být otevřenou podmnožinou a ${ displaystyle F: X podmnožina mathbb {R} ^ {n} do mathbb {R} ^ {n}}$ A diferencovatelná funkce s Jacobian ${ displaystyle F ^ { prime} ( mathbf {x})}$ to je lokálně Lipschitz kontinuální (například pokud ${ displaystyle F}$ je dvakrát diferencovatelné). To znamená, že se předpokládá, že pro každou otevřenou podmnožinu ${ displaystyle U podmnožina X}$ existuje konstanta ${ displaystyle L> 0}$ takový, že pro každého ${ displaystyle mathbf {x}, mathbf {y} v U}$

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

drží. Norma vlevo je nějaká norma operátora, která je kompatibilní s vektorovou normou vpravo. Tuto nerovnost lze přepsat tak, aby používala pouze vektorovou normu. Pak pro jakýkoli vektor ${ displaystyle mathbf {v} in mathbb {R} ^ {n}}$ nerovnost

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

musí držet.

Nyní vyberte libovolný počáteční bod ${ displaystyle mathbf {x} _ {0} v X}$. Předpokládat, že ${ displaystyle F '( mathbf {x} _ {0})}$ je invertibilní a vytvoří Newtonův krok ${ displaystyle mathbf {h} _ {0} = - F '( mathbf {x} _ {0}) ^ {- 1} F ( mathbf {x} _ {0}).}$

Další předpoklad je, že nejen další bod ${ displaystyle mathbf {x} _ {1} = mathbf {x} _ {0} + mathbf {h} _ {0}}$ ale celý míč ${ displaystyle B ( mathbf {x} _ {1}, | mathbf {h} _ {0} |)}$ je obsažen uvnitř sady ${ displaystyle X}$. Nechat ${ displaystyle M leq L}$ být Lipschitzovou konstantou pro Jacobiana nad tímto míčem.

Jako poslední přípravu vytvořte rekurzivně sekvence, pokud je to možné ${ displaystyle ( mathbf {x} _ {k}) _ {k}}$, ${ displaystyle ( mathbf {h} _ {k}) _ {k}}$, ${ displaystyle ( alpha _ {k}) _ {k}}$ podle

${ displaystyle { 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 { alignedat}}}$

Prohlášení

Teď když ${ displaystyle alpha _ {0} leq { tfrac {1} {2}}}$ pak

1. řešení ${ displaystyle mathbf {x} ^ {*}}$ z ${ displaystyle F ( mathbf {x} ^ {*}) = 0}$ uvnitř uzavřené koule ${ displaystyle { bar {B}} ( mathbf {x} _ {1}, | mathbf {h} _ {0} |)}$ a
2. Newtonova iterace začínající v ${ displaystyle mathbf {x} _ {0}}$ konverguje k ${ displaystyle mathbf {x} ^ {*}}$ s alespoň lineárním řádem konvergence.

Výrok, který je přesnější, ale o něco těžší prokázat, využívá kořeny ${ displaystyle t ^ { ast} leq t ^ {**}}$ kvadratického polynomu

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

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

a jejich poměr

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

Pak

1. řešení ${ displaystyle mathbf {x} ^ {*}}$ uvnitř uzavřené koule ${ displaystyle { bar {B}} ( mathbf {x} _ {1}, theta | mathbf {h} _ {0} |) podmnožina { bar {B}} ( mathbf { x} _ {0}, t ^ {*})}$
2. je jedinečný uvnitř větší koule ${ displaystyle B ( mathbf {x} _ {0}, t ^ {* ast})}$
3. a konvergence k řešení ${ displaystyle F}$ dominuje konvergence Newtonovy iterace kvadratického polynomu ${ displaystyle p (t)}$ směrem k jeho nejmenšímu kořenu ${ displaystyle t ^ { ast}}$,^[4] -li ${ displaystyle t_ {0} = 0, , t_ {k + 1} = t_ {k} - { tfrac {p (t_ {k})} {p '(t_ {k})}}}$, pak

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

4. Kvadratická konvergence se získá z odhadu chyby^[5]

   ${ displaystyle | 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 } |.}$

Důsledek

V roce 1986 Yamamoto dokázal, že hodnocení chyb Newtonovy metody, jako je Doring (1969), Ostrowski (1971, 1973),^[6][7] Gragg-Tapia (1974), Potra-Ptak (1980),^[8] Miel (1981),^[9] Potra (1984),^[10] lze odvodit z Kantorovichovy věty.^[11]

Zobecnění

Tady je q-analogový pro Kantorovičovu větu.^[12][13] Další zevšeobecnění / variace viz Ortega & Rheinboldt (1970).^[14]

Aplikace

Oishi a Tanabe tvrdili, že Kantorovichovu větu lze použít k získání spolehlivých řešení lineární programování.^[15]

Reference

Další čtení

• John H. Hubbard a Barbara Burke Hubbard: Vektorový počet, lineární algebra a diferenciální formy: jednotný přístupMatrix Edition, ISBN  978-0-9715766-3-6 (náhled 3. vydání a ukázkový materiál včetně Kant.-thm. )
• Yamamoto, Tetsuro (2001). "Historický vývoj v konvergenční analýze pro Newtonovy a Newtonovy metody". In Brezinski, C .; Wuytack, L. (eds.). Numerická analýza: Historický vývoj ve 20. století. Severní Holandsko. 241–263. ISBN  0-444-50617-9.