Tasa de convergencia

Velocidad de convergencia de una secuencia matemática.

En análisis numérico , el orden de convergencia y la tasa de convergencia de una secuencia convergente son cantidades que representan qué tan rápido la secuencia se acerca a su límite. Se dice que una secuencia que converge tiene orden de convergencia y tasa de convergencia si ${\displaystyle (x_{n})}$ ${\displaystyle L}$ ${\displaystyle q\geq 1}$ ${\displaystyle \mu }$

${\displaystyle \lim _{n\rightarrow \infty }{\frac {\left|x_{n+1}-L\right|}{\left|x_{n}-L\right|^{q}}}=\mu .}$^[1]

La tasa de convergencia también se llama constante de error asintótica . Tenga en cuenta que esta terminología no está estandarizada y algunos autores usarán tasa donde este artículo usa orden (por ejemplo, ^[2] ). ${\displaystyle \mu }$

En la práctica, la tasa y el orden de convergencia proporcionan información útil cuando se utilizan métodos iterativos para calcular aproximaciones numéricas. Si el orden de convergencia es mayor, normalmente se necesitan menos iteraciones para producir una aproximación útil. Sin embargo, estrictamente hablando, el comportamiento asintótico de una secuencia no proporciona información concluyente sobre ninguna parte finita de la secuencia.

Se utilizan conceptos similares para los métodos de discretización . La solución del problema discretizado converge a la solución del problema continuo cuando el tamaño de la cuadrícula llega a cero, y la velocidad de convergencia es uno de los factores de la eficiencia del método. Sin embargo, la terminología, en este caso, es diferente de la terminología de los métodos iterativos.

La aceleración en serie es una colección de técnicas para mejorar la tasa de convergencia de una discretización en serie. Esta aceleración se logra comúnmente con transformaciones de secuencia .

Velocidad de convergencia para métodos iterativos.

Definiciones de convergencia

Supongamos que la secuencia converge al número . Se dice que la secuencia converge con orden de y con una tasa de convergencia ^[3] de , si ${\displaystyle (x_{k})}$ ${\displaystyle L}$ ${\displaystyle q}$ ${\displaystyle L}$ ${\displaystyle \mu }$

para alguna constante positiva si y si . ^{[4] [5]} No es necesario, sin embargo, que sea un número entero. Por ejemplo, el método de la secante , al converger a una raíz simple y regular , tiene un orden de φ ≈ 1,618. ^{[ cita necesaria ]} ${\displaystyle \mu \in (0,\infty )}$ ${\displaystyle q>1}$ ${\displaystyle \mu \in (0,1)}$ ${\displaystyle q=1}$ ${\displaystyle q}$

Convergencia con orden

• ${\displaystyle q=1}$se llama convergencia lineal si , y se dice que la secuencia converge Q-linealmente a . ${\displaystyle \mu \in (0,1)}$ ${\displaystyle L}$
• ${\displaystyle q=2}$se llama convergencia cuadrática.
• ${\displaystyle q=3}$se llama convergencia cúbica.
• etc.

Estimación del pedido

Un método práctico para calcular el orden de convergencia de una secuencia generada por una iteración de punto fijo es calcular la siguiente secuencia, que converge a : ^[6] ${\displaystyle q}$

$${\displaystyle q\approx {\frac {\log \left|\displaystyle {\frac {x_{k+1}-x_{k}}{x_{k}-x_{k-1}}}\right|}{\log \left|\displaystyle {\frac {x_{k}-x_{k-1}}{x_{k-1}-x_{k-2}}}\right|}}.}$$

Para la aproximación numérica de un valor exacto mediante un método numérico de orden q ver ^[7]

Definiciones de convergencia Q

Además de la convergencia Q-lineal definida previamente, existen algunas otras definiciones de convergencia Q. Dada la Definición 1 definida anteriormente, se dice que la secuencia converge Q-superlinealmente ${\displaystyle L}$ (es decir, más rápido que linealmente) en todos los casos donde y también en el caso . ^[8] Dada la Definición 1, se dice que la secuencia converge Q-sublinealmente (es decir, más lentamente que linealmente) si . La secuencia converge logarítmicamente si la secuencia converge sublinealmente y además si ^[9] ${\displaystyle q>1}$ ${\displaystyle q=1,\mu =0}$ ${\displaystyle L}$ ${\displaystyle q=1,\mu =1}$ ${\displaystyle (x_{k})}$ ${\displaystyle L}$

$${\displaystyle \lim _{k\to \infty }{\frac {|x_{k+1}-x_{k}|}{|x_{k}-x_{k-1}|}}=1.}$$

En las definiciones anteriores, "Q-" significa "cociente" porque los términos se definen utilizando el cociente entre dos términos sucesivos. ^{[10] : 619} Sin embargo, a menudo se elimina la "Q-" y simplemente se dice que una secuencia tiene convergencia lineal , convergencia cuadrática , etc.

Definición de convergencia R

Las definiciones de Q-convergencia tienen el inconveniente de que no incluyen algunas secuencias, como la siguiente, que convergen razonablemente rápido, pero cuya velocidad es variable. Por lo tanto, la definición de tasa de convergencia se amplía de la siguiente manera. ${\displaystyle (b_{k})}$

Supongamos que converge a . Se dice que la secuencia converge R-linealmente si existe una secuencia tal que ${\displaystyle (x_{k})}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle (\varepsilon _{k})}$

$${\displaystyle |x_{k}-L|\leq \varepsilon _{k}\quad {\text{for all }}k\,,}$$

^{[3][10] : 620} ${\displaystyle (\varepsilon _{k})}$

Ejemplos

Considere la secuencia

$${\displaystyle (a_{k})=\left\{1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},{\frac {1}{32}},\ldots ,{\frac {1}{2^{k}}},\dots \right\}.}$$

${\displaystyle L=0}$

$${\displaystyle \lim _{k\to \infty }{\frac {\left|1/2^{k+1}-0\right|}{\left|1/2^{k}-0\right|}}=\lim _{k\to \infty }{\frac {2^{k}}{2^{k+1}}}={\frac {1}{2}}.}$$

${\displaystyle (a_{k})}$ ${\displaystyle \mu =1/2}$ ${\displaystyle c\in \mathbb {R} ,\mu \in (-1,1)}$ ${\displaystyle (c\mu ^{k})}$ ${\displaystyle |\mu |}$

La secuencia

$${\displaystyle (b_{k})=\left\{1,1,{\frac {1}{4}},{\frac {1}{4}},{\frac {1}{16}},{\frac {1}{16}},\ldots ,{\frac {1}{4^{\left\lfloor {\frac {k}{2}}\right\rfloor }}},\,\ldots \right\}}$$

función suelo ${\displaystyle \lfloor x\rfloor }$ ${\displaystyle x}$

La secuencia

$${\displaystyle (c_{k})=\left\{{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{16}},{\frac {1}{256}},{\frac {1}{65,\!536}},\ldots ,{\frac {1}{2^{2^{k}}}},\ldots \right\}}$$

Finalmente, la secuencia

$${\displaystyle (d_{k})=\left\{1,{\frac {1}{2}},{\frac {1}{3}},{\frac {1}{4}},{\frac {1}{5}},{\frac {1}{6}},\ldots ,{\frac {1}{k+1}},\ldots \right\}}$$

Tasas de convergencia lineal, lineal, superlineal (cuadrática) y sublineal

Velocidad de convergencia para métodos de discretización.

Existe una situación similar para los métodos de discretización diseñados para aproximar una función , que podría ser una integral aproximada mediante cuadratura numérica , o la solución de una ecuación diferencial ordinaria (ver ejemplo a continuación). El método de discretización genera una secuencia , donde cada sucesivo es función de junto con el espaciado de la cuadrícula entre valores sucesivos de la variable independiente . El parámetro importante aquí para la velocidad de convergencia es el espaciado de la cuadrícula , inversamente proporcional al número de puntos de la cuadrícula, es decir, el número de puntos en la secuencia necesarios para alcanzar un valor dado de . ${\displaystyle y=f(x)}$ ${\displaystyle {y_{0},y_{1},y_{2},y_{3},...}}$ ${\displaystyle y_{j}}$ ${\displaystyle y_{j-1},y_{j-2},...}$ ${\displaystyle h}$ ${\displaystyle x}$ ${\displaystyle y=f(x)}$ ${\displaystyle h}$ ${\displaystyle x}$

En este caso, se dice que la secuencia converge a la secuencia de orden q si existe una constante C tal que ${\displaystyle (y_{n})}$ ${\displaystyle f(x_{n})}$

${\displaystyle |y_{n}-f(x_{n})|<Ch^{q}{\text{ for all }}n.}$

Esto se escribe usando notación O grande . ${\displaystyle |y_{n}-f(x_{n})|={\mathcal {O}}(h^{q})}$

Esta es la definición relevante cuando se analizan métodos de cuadratura numérica o la solución de ecuaciones diferenciales ordinarias (EDO). ^{[ ejemplo necesario ]}

Un método práctico para estimar el orden de convergencia de un método de discretización es elegir tamaños de paso y calcular los errores resultantes . Luego, el orden de convergencia se aproxima mediante la siguiente fórmula: ${\displaystyle h_{\text{new}}}$ ${\displaystyle h_{\text{old}}}$ ${\displaystyle e_{\text{new}}}$ ${\displaystyle e_{\text{old}}}$

${\displaystyle q\approx {\frac {\log(e_{\text{new}}/e_{\text{old}})}{\log(h_{\text{new}}/h_{\text{old}})}},}$^{[ cita necesaria ]}

que proviene de escribir el error de truncamiento, en los espacios de cuadrícula antiguos y nuevos, como

${\displaystyle e=|y_{n}-f(x_{n})|={\mathcal {O}}(h^{q}).}$

El error es, más específicamente, un error de truncamiento global (GTE), ya que representa una suma de errores acumulados en todas las iteraciones, a diferencia de un error de truncamiento local (LTE) en una sola iteración. ${\displaystyle e}$ ${\displaystyle n}$

Ejemplo de métodos de discretización.

Considere la ecuación diferencial ordinaria.

${\displaystyle {\frac {dy}{dx}}=-\kappa y}$

con condición inicial . Podemos resolver esta ecuación usando el esquema de Euler directo para discretización numérica : ${\displaystyle y(0)=y_{0}}$

${\displaystyle {\frac {y_{n+1}-y_{n}}{h}}=-\kappa y_{n},}$

que genera la secuencia

${\displaystyle y_{n+1}=y_{n}(1-h\kappa ).}$

En términos de , esta secuencia es la siguiente, del teorema del binomio : ${\displaystyle y(0)=y_{0}}$

$${\displaystyle y_{n}=y_{0}(1-h\kappa )^{n}=y_{0}\left(1-nh\kappa +n(n-1){\frac {h^{2}\kappa ^{2}}{2}}+....\right).}$$

La solución exacta a esta EDO es , correspondiente a la siguiente expansión de Taylor para : ${\displaystyle y=f(x)=y_{0}\exp(-\kappa x)}$ ${\displaystyle h\kappa }$ ${\displaystyle h\kappa \ll 1}$

$${\displaystyle f(x_{n})=f(nh)=y_{0}\exp(-\kappa nh)=y_{0}\left[\exp(-\kappa h)\right]^{n}=y_{0}\left(1-h\kappa +{\frac {h^{2}\kappa ^{2}}{2}}+....\right)^{n}=y_{0}\left(1-nh\kappa +{\frac {n^{2}h^{2}\kappa ^{2}}{2}}+...\right).}$$

En este caso, el error de truncamiento es

${\displaystyle e=|y_{n}-f(x_{n})|={\frac {nh^{2}\kappa ^{2}}{2}}={\mathcal {O}}(h^{2}),}$

entonces converge con una tasa de convergencia . ${\displaystyle (y_{n})}$ ${\displaystyle f(x_{n})}$ ${\displaystyle q=2}$

Ejemplos (continuación)

La secuencia con se introdujo anteriormente. Esta secuencia converge con el orden 1 según la convención para los métodos de discretización. ^{[ ¿por qué? ]} ${\displaystyle (d_{k})}$ ${\displaystyle d_{k}=1/(k+1)}$

La secuencia con , que también se presentó anteriormente, converge con orden q para cada número q . Se dice que converge exponencialmente usando la convención para métodos de discretización. Sin embargo, sólo converge linealmente (es decir, con orden 1) utilizando la convención para métodos iterativos. ^{[ ¿por qué? ]} ${\displaystyle (a_{k})}$ ${\displaystyle a_{k}=2^{-k}}$

Secuencias recurrentes y puntos fijos.

De particular interés es el caso de las secuencias recurrentes que ocurren en sistemas dinámicos y en el contexto de varios teoremas del punto fijo . Suponiendo que las derivadas relevantes de f son continuas, se puede (fácilmente) demostrar que para un punto fijo tal que , se tiene al menos convergencia lineal para cualquier valor inicial suficientemente cercano a p . Si y , entonces se tiene al menos convergencia cuadrática, y así sucesivamente. Si , entonces tenemos un punto fijo repulsivo y ningún valor inicial producirá una secuencia que converja a p (a menos que saltemos directamente al punto p mismo). ${\displaystyle x_{n+1}:=f(x_{n})}$ ${\displaystyle f(p)=p}$ ${\displaystyle |f'(p)|<1}$ ${\displaystyle x_{0}}$ ${\displaystyle |f'(p)|=0}$ ${\displaystyle |f''(p)|<1}$ ${\displaystyle |f'(p)|>1}$

Aceleración de la convergencia

Existen muchos métodos para aumentar la tasa de convergencia de una secuencia dada, es decir, para transformar una secuencia dada en una que converja más rápido al mismo límite. Estas técnicas se conocen generalmente como " aceleración en serie ". El objetivo de la secuencia transformada es reducir el coste computacional del cálculo. Un ejemplo de aceleración en serie es el proceso delta cuadrado de Aitken . Estos métodos en general (y en particular el método de Aitken) no aumentan el orden de convergencia, y son útiles sólo si inicialmente la convergencia no es más rápida que lineal: si las convergencias son lineales, se obtiene una secuencia que aún converge linealmente (excepto en casos patológicamente diseñados). casos especiales), pero más rápido en el sentido de que . Por otro lado, si la convergencia ya es de orden ≥ 2, el método de Aitken no aportará ninguna mejora. ${\displaystyle (x_{n})}$ ${\displaystyle (a_{n})}$ ${\displaystyle \lim(a_{n}-L)/(x_{n}-L)=0}$

Referencias

1. Ruye, Wang (12 de febrero de 2015). "Orden y ritmo de convergencia". hmc.edu . Consultado el 31 de julio de 2020 .
2. Senning, Jonathan R. "Cálculo y estimación de la tasa de convergencia" (PDF) . gordon.edu . Consultado el 7 de agosto de 2020 .
3. Bockelman, Brian (2005). "Tasas de convergencia". math.unl.edu . Consultado el 31 de julio de 2020 .
4. Hundley, Douglas. "Tasa de convergencia" (PDF) . Universidad Whitman . Consultado el 13 de diciembre de 2020 .
5. Porta, FA (1989). "Sobre el orden Q y el orden R de convergencia" (PDF) . Revista de teoría y aplicaciones de optimización . 63 (3): 415–431. doi :10.1007/BF00939805. S2CID  116192710 . Consultado el 31 de julio de 2020 .
6. Senning, Jonathan R. "Cálculo y estimación de la tasa de convergencia" (PDF) . gordon.edu . Consultado el 7 de agosto de 2020 .
7. Senning, Jonathan R. "Verificación de tasas de convergencia numérica" ​​(PDF) . Consultado el 9 de febrero de 2024 .
8. Arnold, Marcos. "Orden de Convergencia" (PDF) . Universidad de Arkansas . Consultado el 13 de diciembre de 2022 .
9. Van Tuyl, Andrew H. (1994). "Aceleración de la convergencia de una familia de secuencias logarítmicamente convergentes" (PDF) . Matemáticas de la Computación . 63 (207): 229–246. doi :10.2307/2153571. JSTOR  2153571 . Consultado el 2 de agosto de 2020 .
10. Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica (2ª ed.). Berlín, Nueva York: Springer-Verlag . ISBN 978-0-387-30303-1.

Literatura

La definición simple se utiliza en

• Michelle Schatzman (2002), Análisis numérico: una introducción matemática , Clarendon Press, Oxford. ISBN 0-19-850279-6 . 

La definición ampliada se utiliza en

• Walter Gautschi (1997), Análisis numérico: una introducción, Birkhäuser, Boston. ISBN 0-8176-3895-4 . 
• Endre Süli y David Mayers (2003), Introducción al análisis numérico, Cambridge University Press. ISBN 0-521-00794-1 . 

La definición de Big O se utiliza en

• Richard L. Burden y J. Douglas Faires (2001), Análisis numérico (7ª ed.), Brooks/Cole. ISBN 0-534-38216-9 

Los términos Q-lineal y R-lineal se utilizan en

• Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica (2ª ed.). Berlín, Nueva York: Springer-Verlag . págs.619+620. ISBN 978-0-387-30303-1..