Tasa de convergencia

La tasa de convergencia es la principal característica de los métodos numéricos para la resolución de ecuaciones y la optimización .

El concepto de tasa de convergencia

Sea una secuencia convergente de aproximaciones de algún algoritmo para encontrar la raíz de la ecuación o el extremo de la función , entonces: ${\ estilo de visualización \ izquierda \ {x_ {n} \ derecha \}}$ $x^{*}$

Se dice que un método tiene convergencia lineal si . $\existe \alpha \in (0,\;1):\quad \exists N\in \mathbb {N} ,\;\forall n\geq N\quad ||x_{n}-x^{ *}||<\alfa ||x_{n-1}-x^{*}||$

Se dice que un método tiene grado de convergencia $\beta$ si . ${\displaystyle \existe \alpha \in (0,\;1]:\quad \exists N\in \mathbb {N} ,\;\forall n\geq N\quad ||x_{n}-x^{ *}||<\alfa ||x_{n-1}-x^{*}||^{\beta ))$

Tenga en cuenta que la tasa de convergencia de los métodos generalmente no excede la cuadrática. En casos raros, el método puede tener una tasa de convergencia cúbica ( método de Chebyshev ).

Definición práctica

Sea una secuencia de aproximaciones del algoritmo considerado para encontrar la raíz de alguna ecuación, luego la tasa de convergencia se determina a partir de la ecuación: ${\ estilo de visualización \ izquierda \ {x_ {n} \ derecha \}}$ $x^{*}$ $\beta$

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

Para simplificar, se reescribe como:

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

La tasa de convergencia se estima directamente a partir de la tangente de la pendiente de la gráfica logarítmica de dependencia de . ${\ estilo de visualización ||x_{n}-x^{*}||}$ ${\ estilo de visualización ||x_{n-1}-x^{*}||}$

Literatura sobre el tema

Amosov A. A., Dubinsky Yu. A., Kopchenova N. V. Métodos computacionales para ingenieros. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Métodos numéricos. - 8ª ed. - M. : Laboratorio de Conocimientos Básicos, 2000.
Volkov E. A. Métodos numéricos. — M. : Fizmatlit, 2003.