Konvergenshastighet

Konvergenshastigheten är det huvudsakliga kännetecknet för numeriska metoder för att lösa ekvationer och optimering .

Begreppet konvergenshastighet

Låt oss vara en konvergent sekvens av approximationer av någon algoritm för att hitta roten till ekvationen eller funktionens extremum , då: $\left\{x_{n}\right\}$ $x^{*}$

En metod sägs ha linjär konvergens om . $\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 metod sägs ha gradkonvergens $\beta$ om . ${\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 ))$

Observera att konvergenshastigheten för metoder vanligtvis inte överstiger kvadratisk. I sällsynta fall kan metoden ha en kubisk konvergenshastighet ( Chebyshev-metoden ).

Praktisk definition

Låt vara en sekvens av approximationer av den övervägda algoritmen för att hitta roten till någon ekvation, då bestäms konvergenshastigheten från ekvationen: $\left\{x_{n}\right\}$ $x^{*}$ $\beta$

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

För enkelhetens skull skrivs det om till:

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

Hastigheten för konvergens beräknas direkt från tangenten av lutningen av den logaritmiska plotten av beroende av . $||x_{n}-x^{*}||$ $||x_{n-1}-x^{*}||$

Litteratur om ämnet

Amosov A. A., Dubinsky Yu. A., Kopchenova N. V. Beräkningsmetoder för ingenjörer. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numeriska metoder. - 8:e upplagan - M . : Laboratory of Basic Knowledge, 2000.
Volkov E. A. Numeriska metoder. — M .: Fizmatlit, 2003.