Iterace s pevným bodem - Fixed-point iteration - Wikipedia

v numerická analýza, iterace s pevným bodem je metoda výpočtu pevné body funkce.

Přesněji řečeno, vzhledem k funkci ${ displaystyle f}$ definované na reálná čísla se skutečnými hodnotami a bodem ${ displaystyle x_ {0}}$ v doména z ${ displaystyle f}$ , iterace pevného bodu je

{ displaystyle x_ {n + 1} = f (x_ {n}), , n = 0,1,2, tečky}

což vede k sekvence ${ displaystyle x_ {0}, x_ {1}, x_ {2}, dots}$ v které se doufá konvergovat do bodu ${ displaystyle x}$ . Li ${ displaystyle f}$ je spojitý, pak lze prokázat, že získaný ${ displaystyle x}$ je pevný bod ${ displaystyle f}$ , tj.,

{ displaystyle f (x) = x. ,}

Obecněji řečeno, funkce ${ displaystyle f}$ lze definovat na jakémkoli metrický prostor s hodnotami ve stejném prostoru.

Příklady

Prvním jednoduchým a užitečným příkladem je Babylonská metoda pro výpočet odmocnina z A> 0, která spočívá v braní ${ displaystyle f (x) = { frac {1} {2}} vlevo ({ frac {a} {x}} + x vpravo)}$ , tj. střední hodnota X a sekera, přiblížit se k limitu ${ displaystyle x = { sqrt {a}}}$ (z jakéhokoli výchozího bodu ${ displaystyle x_ {0} gg 0}$ ). Toto je zvláštní případ Newtonova metoda citováno níže.

Iterace s pevným bodem X_n+1 = hřích X_n s počáteční hodnotou X₀ = 2 konverguje k 0. Tento příklad nesplňuje předpoklady Banachova věta o pevném bodě a tak jeho rychlost konvergence je velmi pomalá.

Iterace s pevným bodem ${ displaystyle x_ {n + 1} = cos x_ {n} ,}$ konverguje k jedinečnému pevnému bodu funkce ${ displaystyle f (x) = cos x ,}$ pro jakýkoli výchozí bod ${ displaystyle x_ {0}.}$ Tento příklad splňuje předpoklady Banachova věta o pevném bodě. Proto chyba po n krocích vyhovuje ${ displaystyle | x_ {n} -x | leq {q ^ {n} nad 1-q} | x_ {1} -x_ {0} | = Cq ^ {n}}$ (kde můžeme vzít ${ displaystyle q = 0,85}$ , pokud začneme od ${ displaystyle x_ {0} = 1}$ .) Pokud je chyba menší než násobek ${ displaystyle q ^ {n}}$ pro nějakou konstantu q, říkáme, že máme lineární konvergence. Banachova věta o pevném bodě umožňuje jednomu získat iterace s pevným bodem s lineární konvergencí.
Iterace s pevným bodem ${ displaystyle x_ {n + 1} = 2x_ {n} ,}$ se rozcházejí, pokud ${ displaystyle x_ {0} = 0}$ . Říkáme, že pevný bod ${ displaystyle f (x) = 2x ,}$ odpuzuje.
Požadavek, že F je spojitý je důležité, jak ukazuje následující příklad. Iterace

{ displaystyle x_ {n + 1} = { begin {cases} { frac {x_ {n}} {2}}, & x_ {n} neq 0 1, & x_ {n} = 0 end { případy}}}

konverguje na 0 pro všechny hodnoty ${ displaystyle x_ {0}}$ . 0 je ne pevný bod funkce

{ displaystyle f (x) = { begin {cases} { frac {x} {2}}, & x neq 0 1, & x = 0 end {cases}}}

protože tato funkce je ne nepřetržitě v ${ displaystyle x = 0}$ a ve skutečnosti nemá žádné pevné body.

Aplikace

Newtonova metoda pro nalezení kořenů dané diferencovatelné funkce ${ displaystyle f (x)}$ je

{ displaystyle x_ {n + 1} = x_ {n} - { frac {f (x_ {n})} {f '(x_ {n})}}.}

Pokud píšeme

{ displaystyle g (x) = x - { frac {f (x)} {f '(x)}}}

můžeme Newtonovu iteraci přepsat jako iteraci s pevným bodem

{ displaystyle x_ {n + 1} = g (x_ {n})}

.

Pokud tato iterace konverguje k pevnému bodu

X

z

G

, pak

{ displaystyle x = g (x) = x - { frac {f (x)} {f '(x)}}}

, tak

{ displaystyle f (x) / f '(x) = 0.}

Převrácená hodnota čehokoli je tedy nenulová

F (X) = 0

:

X

je vykořenit z

F

. Podle předpokladů Banachova věta o pevném bodě, ukazuje Newtonova iterace, orámovaná jako metoda s pevným bodem lineární konvergence. Ukazuje se však podrobnější analýza kvadratická konvergence, tj.,

{ displaystyle | x_ {n} -x |

, za určitých okolností.

Halleyova metoda je podobný Newtonova metoda ale když to funguje správně, jeho chyba je ${ displaystyle | x_ {n} -x |$ (kubická konvergence ). Obecně je možné navrhnout metody, které se sbíhají s rychlostí ${ displaystyle Cq ^ {k ^ {n}}}$ pro všechny ${ displaystyle k in mathbb {N}}$ . Obecně platí, že čím vyšší $k$ , čím méně stabilní je a tím je výpočetně dražší. Z těchto důvodů se metody vyššího řádu obvykle nepoužívají.
Metody Runge – Kutta a číselné obyčejná diferenciální rovnice řešitele obecně lze považovat za iterace s pevným bodem. Základní myšlenka při analýze A-stabilita řešitelů ODE je začít zvláštním případem ${ displaystyle y '= ay}$ , kde a je a komplexní číslo, a zkontrolovat, zda řešič ODE konverguje do pevného bodu ${ displaystyle y = 0}$ kdykoli je skutečná část a záporná.^[A]
The Picard – Lindelöfova věta, což ukazuje, že běžné diferenciální rovnice mají řešení, je v podstatě aplikací Banachova věta o pevném bodě na speciální posloupnost funkcí, která tvoří iteraci pevného bodu, konstrukci řešení rovnice. Řešení ODR tímto způsobem se nazývá Picardova iterace, Picardova metoda, nebo Picardův iterační proces.
Schopnost iterace v aplikaci Excel lze použít k nalezení řešení Colebrookova rovnice na přesnost 15 platných čísel.^[1]^[2]

Některá schémata "postupné aproximace" používaná v dynamické programování vyřešit Bellmanova funkční rovnice jsou založeny na iteracích s pevným bodem v prostoru návratové funkce.^[3]^[4]

Kontrakce

Pokud je funkce ${ displaystyle f}$ definovaný na reálné linii se skutečnými hodnotami je Lipschitz kontinuální s Lipschitzovou konstantou ${ displaystyle L <1}$ , pak má tato funkce přesně jeden pevný bod a iterace pevného bodu konverguje k tomuto pevnému bodu pro jakýkoli počáteční odhad ${ displaystyle x_ {0}.}$ Tuto větu lze zobecnit na jakýkoli úplný metrický prostor.

Důkaz této věty:

Od té doby ${ displaystyle f}$ je Lipschitzův spojitý s Lipschitzovou konstantou ${ displaystyle L <1}$ , pak pro sekvenci ${ displaystyle {x_ {n}, n = 0,1,2, ldots }}$ , my máme:

{ displaystyle { begin {aligned} | x_ {2} -x_ {1} | = | f (x_ {1}) - f (x_ {0}) | & leq L | x_ {1} -x_ { 0} |, | x_ {3} -x_ {2} | = | f (x_ {2}) - f (x_ {1}) | & leq L | x_ {2} -x_ {1} | , & , , , vdots end {zarovnáno}}}

a

{ displaystyle | x_ {n} -x_ {n-1} | = | f (x_ {n-1}) - f (x_ {n-2}) | leq L | x_ {n-1} -x_ {n-2} |.}

Kombinace výše uvedených nerovností přináší:

{ displaystyle | x_ {n} -x_ {n-1} | leq L ^ {n-1} | x_ {1} -x_ {0} |.}

Od té doby ${ displaystyle L <1}$ , ${ displaystyle L ^ {n-1} rightarrow 0}$ tak jako ${ displaystyle n rightarrow infty.}$

Proto můžeme ukázat ${ displaystyle {x_ {n} }}$ je Cauchyova posloupnost a tím konverguje k bodu ${ displaystyle x ^ {*}}$ .

Pro iteraci ${ displaystyle x_ {n} = f (x_ {n-1})}$ , nechť ${ displaystyle n}$ jdi do nekonečna na obou stranách rovnice, dostaneme ${ displaystyle x ^ {*} = f (x ^ {*})}$ . To ukazuje ${ displaystyle x ^ {*}}$ je pevný bod pro ${ displaystyle f}$ . Dokázali jsme tedy, že iterace nakonec konverguje k pevnému bodu.

Tato vlastnost je velmi užitečná, protože ne všechny iterace mohou dospět ke konvergentnímu pevnému bodu. Při konstrukci iterace s pevným bodem je velmi důležité zajistit, aby konvergovala. Je jich několik věty o pevném bodě abychom zaručili existenci pevného bodu, ale protože iterační funkce je spojitá, můžeme obvykle použít výše uvedenou větu k otestování, zda iterace konverguje nebo ne. Důkaz zobecněné věty o dokončení metrických prostorů je podobný.

Zrychlení konvergence

Rychlost konvergence iterační sekvence lze zvýšit pomocí a zrychlení konvergence metoda jako Aitkenův delta-kvadratický proces. Aplikace Aitkenovy metody na iteraci s pevným bodem je známá jako Steffensenova metoda a je možné ukázat, že Steffensenova metoda přináší míru konvergence, která je přinejmenším kvadratická.

Viz také

Reference

^ Jeden může také zvážit určité iterace A-stabilní, pokud iterace zůstanou omezené po dlouhou dobu, což je nad rámec tohoto článku.

^ M A Kumar (2010), Řešení implicitních rovnic (Colebrook) v rámci pracovního listu, Createspace, ISBN 1-4528-1619-0
^ Brkic, Dejan (2017) Řešení implicitní Colebrookovy rovnice pro tření toku pomocí aplikace Excel, tabulky ve vzdělávání (eJSiE): sv. 10: Vydání 2, článek 2. Dostupné na: https://sie.scholasticahq.com/article/4663-solution-of-the-implicit-colebrook-equation-for-flow-friction-using-excel
^ Bellman, R. (1957). Dynamické programování, Princeton University Press.
^ Sniedovich, M. (2010). Dynamické programování: základy a principy, Taylor & Francis.

Další čtení

Burden, Richard L .; Faires, J. Douglas (1985). "Iterace s pevným bodem". Numerická analýza (Třetí vydání.). Vydavatelé PWS. ISBN 0-87150-857-5.
Hoffman, Joe D .; Frankel, Steven (2001). „Iterace s pevným bodem“. Numerické metody pro inženýry a vědce (Druhé vydání.). New York: CRC Press. str. 141–145. ISBN 0-8247-0443-6.
Judd, Kenneth L. (1998). „Iterace s pevným bodem“. Numerické metody v ekonomii. Cambridge: MIT Press. str. 165–167. ISBN 0-262-10071-1.

externí odkazy

[1] Jeden může také zvážit určité iterace A-stabilní, pokud iterace zůstanou omezené po dlouhou dobu, což je nad rámec tohoto článku.

[2] M A Kumar (2010), Řešení implicitních rovnic (Colebrook) v rámci pracovního listu, Createspace, ISBN 1-4528-1619-0

[3] Brkic, Dejan (2017) Řešení implicitní Colebrookovy rovnice pro tření toku pomocí aplikace Excel, tabulky ve vzdělávání (eJSiE): sv. 10: Vydání 2, článek 2. Dostupné na: https://sie.scholasticahq.com/article/4663-solution-of-the-implicit-colebrook-equation-for-flow-friction-using-excel

[4] Bellman, R. (1957). Dynamické programování, Princeton University Press.

[5] Sniedovich, M. (2010). Dynamické programování: základy a principy, Taylor & Francis.

[A]

[1]

[2]

[3]

[4]