Jednoduchá iterační metoda

Jednoduchá iterační metoda je jednou z nejjednodušších numerických metod řešení rovnic . Metoda je založena na principu kompresního mapování , které lze ve vztahu k numerickým metodám obecně nazvat také metodou prosté iterace nebo metodou postupných aproximací [1] . Zejména existuje podobná iterační metoda pro systémy lineárních algebraických rovnic .

Metoda nápad

Myšlenkou jednoduché iterační metody je zredukovat rovnici na ekvivalentní rovnici $f(x)=0$

x=\varphi(x)

aby byl displej kompresní. Pokud se to podaří, posloupnost iterací se sblíží. Tato transformace může být provedena různými způsoby. Zejména rovnice tvaru $\varphi(x)$ $x_{i+1}=\varphi(x_i)$

\varphi (x)=x-{\lambda }(x)f(x)\!,

pokud na studovaném segmentu. Optimální volba je , což vede k Newtonově metodě , která je rychlá, ale vyžaduje výpočet derivace. Pokud v okolí odmocniny zvolíme konstantu stejného znaménka jako derivace, dostaneme nejjednodušší iterační metodu. ${\lambda}(x) \neq 0$ $\lambda(x) = \frac{1}{f'(x)}$ $\lambda(x)$

Popis

Nějaká konstanta se bere jako funkce , jejíž znaménko se shoduje se znaménkem derivace v nějakém sousedství odmocniny (a zejména na úsečce spojující a ). Konstanta obvykle nezávisí ani na čísle kroku. Někdy vezmou a nazývají tuto metodu metoda jedné tečny . Iterační vzorec se ukazuje jako velmi jednoduchý: ${\lambda }(x)$ ${\displaystyle {\lambda }_{0))$ $f'(x)$ ${\displaystyle x_{0))$ $x^{*}$ ${\displaystyle {\lambda }_{0))$ ${\lambda}_0=\frac{1}{f'(x_0)}$

\displaystyle x_{i+1}=x_i-{\lambda}_0f(x_i)\!,

a při každé iteraci musíte jednou vypočítat hodnotu funkce . $f(x)$

Tento vzorec, stejně jako požadavek, aby se označení shodovala , lze snadno odvodit z geometrických úvah. Uvažujme přímku procházející bodem na grafu se sklonem . Pak bude rovnice této přímky $f'$ ${\displaystyle {\lambda }_{0))$ $(x_{i};f(x_{i}))$ $y=f(x)$ $\tan \nolimits \alpha ={\frac {1}{\lambda }}_{0}$

\displaystyle y=f(x_{i})+{\frac {1}{{\lambda }_{0}}}(x-x_{i}).

Najděte průsečík této přímky s osou z rovnice $OX$

\displaystyle f(x_{i})+{\dfrac {1}({\lambda }_{0))}(x-x_{i})=0,

odkud _ Proto tato přímka protíná osu právě v bodě další aproximace. Získáme tak následující geometrickou interpretaci postupných aproximací. Počínaje bodem se přes odpovídající body grafu kreslí přímky se sklonem stejného znaménka jako derivace . (Všimněte si, že za prvé není nutné vypočítat hodnotu derivace, stačí vědět, zda funkce klesá nebo roste; za druhé, že čáry nakreslené v různých mají stejný sklon , a proto jsou rovnoběžné k sobě. ) Jako další přiblížení ke kořeni se bere průsečík sestrojené přímky s osou . ${\displaystyle x=x_{i}-{\lambda }_{0}f(x_{i})=x_{i+1))$ $OX$ ${\displaystyle x_{0))$ $y=f(x)$ ${\displaystyle k={\dfrac {1}{{\lambda }_{0))))$ $f'(x_{0})$ $f(x)$ $x_i$ $k$ $OX$

Výkres vpravo ukazuje iterace pro případ a případ . Vidíme, že v prvním případě bod změny již v prvním kroku "přeskočí" na druhou stranu kořene a iterace se začnou přibližovat ke kořenu z druhé strany. Ve druhém případě se po sobě jdoucí body přibližují ke kořenu a zůstávají po celou dobu na jeho jedné straně. $f'(x)>0$ $k={\dfrac {1}{{\lambda }_{0}}}<f'(x_{0})$ $k={\dfrac {1}{{\lambda }_{0}}}>f'(x_{0})$ $x_i$ $x^{*}$ $x_i$

Podmínka konvergence

Postačující podmínkou pro konvergenci je:

\displaystyle \vert {\varphi }'(x)\vert =\vert 1-{\lambda }_{0}f'(x)\vert \leqslant {\gamma }<1.

Tuto nerovnost lze přepsat jako

\displaystyle -{\gamma }+1\leqslant {\lambda }_{0}f'(x)\leqslant {\gamma }+1,

odkud získáme, že konvergence je zaručena, když za prvé,

\displaystyle {\lambda }_{0}f'(x)>0,

protože (tím je objasněn význam výběru znaménka čísla ) a za druhé, když pro všechny na celý uvažovaný segment obklopující kořen. Tato druhá nerovnost je jistě splněna, pokud $-{\gamma }+1>0$ ${\displaystyle {\lambda }_{0))$ ${\lambda }_{0}f'(x)<2$ $X$

\displaystyle \vert k\vert ={\dfrac {1}{\vert {\lambda }_{0}\vert }}>{\dfrac {M_{1}}{2)),

kde . Sklon by tedy neměl být v absolutní hodnotě příliš malý: při malém sklonu již v prvním kroku může bod vyskočit z uvažovaného okolí kořene a nemusí dojít ke konvergenci ke kořenu. $M_{1}=\max \limits _{x}\vert f'(x)\vert$ $k$ $x_1$ $x^{*}$

Poznámky

↑ Matematický encyklopedický slovník . - M .: "Sovy. encyklopedie“ , 1988. - S. 847 .

Jednoduchá iterační metoda

Metoda nápad

Popis

Podmínka konvergence

Poznámky

Viz také