Konvergenshastighed

Konvergenshastigheden er hovedkarakteristikken ved numeriske metoder til løsning af ligninger og optimering .

Begrebet konvergenshastighed

Lad være en konvergent sekvens af tilnærmelser af en eller anden algoritme til at finde roden af ligningen eller ekstremumet af funktionen , så: $\left\{x_{n}\right\}$ $x^{*}$

En metode siges at have lineær konvergens , hvis . $\exists \alpha \in (0,\;1):\quad \exists N\in \mathbb {N} ,\;\forall n\geq N\quad ||x_{n}-x^{ *}||<\alpha ||x_{n-1}-x^{*}||$

En metode siges at have gradkonvergens, $\beta$ hvis . ${\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 ))$

Bemærk, at hastigheden for konvergens af metoder normalt ikke overstiger kvadratisk. I sjældne tilfælde kan metoden have en kubisk konvergenshastighed ( Chebyshev-metoden ).

Praktisk definition

Lad være en sekvens af tilnærmelser af den betragtede algoritme til at finde roden til en ligning, så bestemmes konvergenshastigheden ud fra ligningen: $\left\{x_{n}\right\}$ $x^{*}$ $\beta$

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

For nemheds skyld er det omskrevet som:

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

Konvergenshastigheden estimeres direkte ud fra tangens af hældningen af det logaritmiske plot af afhængighed af . $||x_{n}-x^{*}||$ $||x_{n-1}-x^{*}||$

Litteratur om emnet

Amosov A. A., Dubinsky Yu. A., Kopchenova N. V. Beregningsmetoder for ingeniører. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numeriske metoder. - 8. udgave - M . : Laboratory of Basic Knowledge, 2000.
Volkov E. A. Numeriske metoder. — M .: Fizmatlit, 2003.