Míra konvergence

Rychlost konvergence je hlavní charakteristikou numerických metod pro řešení rovnic a optimalizaci .

Koncept míry konvergence

Nechť je konvergentní posloupnost aproximací nějakého algoritmu pro nalezení kořene rovnice nebo extrému funkce , pak: $\left\{x_{n}\right\}$ $x^{*}$

O metodě se říká, že má lineární konvergenci , jestliže . $\exists \alpha \in (0,\;1):\quad \exists N\in \mathbb {N} ,\;\forall n\geq N\quad ||x_{n}-x^{ *}||<\alpha ||x_{n-1}-x^{*}||$

O metodě se říká, že má stupeň konvergence $\beta$ , jestliže . ${\displaystyle \exists \alpha \in (0,\;1]:\quad \exists N\in \mathbb {N} ,\;\forall n\geq N\quad ||x_{n}-x^{ *}||<\alpha ||x_{n-1}-x^{*}||^{\beta ))$

Všimněte si, že rychlost konvergence metod obvykle nepřesahuje kvadratickou hodnotu. Ve vzácných případech může mít metoda kubickou míru konvergence ( Čebyševova metoda ).

Praktická definice

Nechť je posloupnost aproximací uvažovaného algoritmu pro nalezení kořene nějaké rovnice, pak se rychlost konvergence určí z rovnice: $\left\{x_{n}\right\}$ $x^{*}$ $\beta$

${\displaystyle ||x_{n}-x^{*}||<\alpha ||x_{n-1}-x^{*}||^{\beta ))$

Pro jednoduchost je to přepsáno takto:

$\log ||x_{n}-x^{*}||<\log \alpha +\beta \log ||x_{n-1}-x^{*}||$

Rychlost konvergence se přímo odhaduje z tečny sklonu logaritmického grafu závislosti na . $||x_{n}-x^{*}||$ $||x_{n-1}-x^{*}||$

Literatura k tématu

Amosov A. A., Dubinsky Yu. A., Kopchenova N. V. Výpočetní metody pro inženýry. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numerické metody. - 8. vyd. - M . : Laboratoř základních znalostí, 2000.
Volkov E. A. Numerické metody. — M .: Fizmatlit, 2003.