Tasa de convergencia

La progresión geométrica${\textstyle (a_{k})=1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},{\frac {1}{32}},\ldots ,{\bigl (}{\tfrac {1}{2}}{\bigr )}^{k},\dots }$ converge a${\displaystyle L=0}$. Sustituyendo la secuencia en la definición de convergencia Q-lineal (es decir, orden de convergencia 1) se muestra que

$${\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}}.}$$

De este modo${\displaystyle (a_{k})}$converge Q-linealmente con una tasa de convergencia de${\displaystyle \mu =1/2}$Véase el primer gráfico de la figura siguiente.

En términos más generales, para cualquier valor inicial${\displaystyle a}$en los números reales y una razón común de números reales${\displaystyle r}$entre -1 y 1, una progresión geométrica${\displaystyle (ar^{k})}$converge linealmente con la tasa${\displaystyle |r|}$y la sucesión de sumas parciales de una serie geométrica${\textstyle {\bigl (}\sum _{n=0}^{k}ar^{n}{\bigr )}}$también converge linealmente con la tasa${\displaystyle |r|}$Lo mismo se aplica a las progresiones geométricas y a las series geométricas parametrizadas por cualquier número complejo .${\displaystyle a\in \mathbb {C} ,r\in \mathbb {C} ,|r|<1.}$

La progresión geométrica escalonada${\textstyle (b_{k})=1,1,{\frac {1}{4}},{\frac {1}{4}},{\frac {1}{16}},{\frac {1}{16}},\ldots ,{\bigl (}{\tfrac {1}{4}}{\bigr )}^{\left\lfloor k/2\right\rfloor },\ldots ,}$utilizando la función de piso${\textstyle \lfloor x\rfloor }$que da el mayor número entero que es menor o igual a${\displaystyle x,}$Converge linealmente a R con una tasa de 1/2, pero no converge linealmente a Q; véase el segundo gráfico de la figura siguiente. Los límites de convergencia lineal a Q que definen esta secuencia no existen porque una subsecuencia de cocientes de error que comienza en pasos impares converge a 1 y otra subsecuencia de cocientes que comienza en pasos pares converge a 1/4. Cuando dos subsecuencias de una secuencia convergen a límites diferentes, la secuencia en sí misma no converge a un límite. En general, para cualquier progresión geométrica escalonada${\displaystyle (ar^{\lfloor k/m\rfloor })}$, la secuencia no convergerá Q-linealmente pero convergerá R-linealmente con una tasa${\textstyle {\sqrt[{m}]{|r|}};}$Estos ejemplos demuestran por qué la "R" en convergencia lineal R es la abreviatura de "raíz".

La secuencia $${\displaystyle (c_{k})={\frac {1}{2}},{\frac {1}{4}},{\frac {1}{16}},{\frac {1}{256}},{\frac {1}{65,\!536}},\ldots ,{\frac {1}{2^{2^{k}}}},\ldots }$$ Converge a cero de forma superlineal Q. De hecho, converge cuadráticamente con una tasa de convergencia cuadrática de 1. Esto se muestra en el tercer gráfico de la figura siguiente.

Finalmente, la secuencia $${\displaystyle (d_{k})=1,{\frac {1}{2}},{\frac {1}{3}},{\frac {1}{4}},{\frac {1}{5}},{\frac {1}{6}},\ldots ,{\frac {1}{k+1}},\ldots }$$ Converge a cero de forma sublineal y logarítmica en Q, y su convergencia se muestra en el cuarto gráfico de la figura siguiente.

Secuencias recurrentes${\textstyle x_{k+1}:=f(x_{k})}$, llamadas iteraciones de punto fijo , definen sistemas dinámicos autónomos de tiempo discreto y tienen importantes aplicaciones generales en matemáticas a través de varios teoremas de punto fijo sobre su comportamiento de convergencia. Cuando f es continuamente diferenciable , dado un punto fijo p ,${\textstyle f(p)=p,}$de tal manera que${\textstyle |f'(p)|<1}$, el punto fijo es un punto fijo atractivo y la secuencia recurrente convergerá al menos linealmente a p para cualquier valor inicial.${\displaystyle x_{0}}$suficientemente cerca de p . Si${\displaystyle |f'(p)|=0}$y${\textstyle |f''(p)|<1}$, entonces la secuencia recurrente convergerá al menos cuadráticamente, y así sucesivamente. Si${\displaystyle |f'(p)|>1}$, entonces el punto fijo es un punto fijo repulsivo y las secuencias no pueden converger a p desde sus vecindarios inmediatos , aunque aún pueden saltar a p directamente desde fuera de sus vecindarios locales.

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 al orden${\displaystyle q}$: ^{[ 8 ]}$${\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${\displaystyle q}$ver. ^{[ 9 ]}

Existen muchos métodos para acelerar la convergencia de una secuencia dada, es decir, para transformar una secuencia en una segunda secuencia que converge más rápidamente al mismo límite. Estas técnicas se conocen generalmente como métodos de " aceleración de series ". Estos pueden reducir los costos computacionales de aproximar los límites de las secuencias originales. Un ejemplo de aceleración de series mediante transformación de secuencias es el proceso delta-cuadrado de Aitken . Estos métodos en general, y en particular el método de Aitken, no suelen aumentar el orden de convergencia y, por lo tanto, solo son útiles si inicialmente la convergencia no es más rápida que lineal: si${\displaystyle (x_{k})}$converge linealmente, el método de Aitken lo transforma en una secuencia${\displaystyle (a_{k})}$que aún converge linealmente (excepto en casos especiales diseñados patológicamente), pero más rápido en el sentido de que${\textstyle \lim _{k\rightarrow \infty }(a_{k}-L)/(x_{k}-L)=0}$. Por otro lado, si la convergencia ya es de orden ≥ 2, el método de Aitken no aportará ninguna mejora.

Una secuencia de aproximaciones discretizadas${\displaystyle (y_{k})}$de alguna función de dominio continuo${\displaystyle S}$que converge a este objetivo, junto con una secuencia correspondiente de parámetros de escala de discretización.${\displaystyle (h_{k})}$Se dice que una función que converge a 0 tiene un orden de convergencia asintótico.${\displaystyle q}$y tasa asintótica de convergencia${\displaystyle \mu }$si

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|y_{k}-S\right|}{h_{k}^{q}}}=\mu ,}$$

para algunas constantes positivas${\displaystyle \mu }$y${\displaystyle q}$y utilizando${\displaystyle |x|}$para representar una métrica de distancia apropiada en el espacio de soluciones , generalmente la norma uniforme , la diferencia absoluta o la distancia euclidiana . Los parámetros de escala de discretización pueden ser espaciamientos de una cuadrícula regular en el espacio o en el tiempo, el inverso del número de puntos de una cuadrícula en una dimensión, una distancia promedio o máxima entre puntos en una malla poligonal , los espaciamientos unidimensionales de una cuadrícula dispersa irregular o un cuanto característico de energía o momento en un conjunto base de mecánica cuántica .

Cuando todas las discretizaciones se generan utilizando un único método común, es habitual analizar la tasa asintótica y el orden de convergencia del método en sí, en lugar de secuencias discretas particulares de soluciones discretizadas. En estos casos, se considera una única solución discretizada abstracta.${\displaystyle y_{h}}$generado utilizando el método con un parámetro de escala${\displaystyle h}$y entonces se dice que el método tiene un orden de convergencia asintótico.${\displaystyle q}$y tasa asintótica de convergencia${\displaystyle \mu }$si

$${\displaystyle \lim _{h\rightarrow 0}{\frac {\left|y_{h}-S\right|}{h^{q}}}=\mu ,}$$

Nuevamente para algunas constantes positivas${\displaystyle \mu }$y${\displaystyle q}$y una métrica apropiada${\displaystyle |x|.}$Esto implica que el error de una discretización escala asintóticamente como el parámetro de escala de la discretización a la${\displaystyle q}$poder, o${\textstyle \left|y_{h}-S\right|=O(h^{q})}$utilizando la notación asintótica de la gran O. Más precisamente, implica que el error de orden principal es${\displaystyle \mu h^{q},}$que puede expresarse utilizando la notación asintótica de o pequeña como${\textstyle \left|y_{h}-S\right|=\mu h^{q}+o(h^{q}).}$

En algunos casos, pueden ser importantes múltiples tasas y órdenes para un mismo método, pero con diferentes opciones de parámetro de escala. Por ejemplo, para métodos de diferencias finitas basados ​​en mallas multidimensionales, donde las distintas dimensiones tienen diferentes espaciamientos, o para métodos de elementos finitos basados ​​en mallas poligonales, donde elegir la distancia media entre puntos de la malla o la distancia máxima entre puntos de la malla como parámetros de escala puede implicar diferentes órdenes de convergencia. En algunos contextos especialmente técnicos, las tasas y órdenes de convergencia asintóticas de los métodos de discretización se caracterizarán por varios parámetros de escala a la vez, y el valor de cada parámetro de escala puede afectar la tasa y el orden de convergencia asintótica del método con respecto a los demás parámetros de escala.

Consideremos la ecuación diferencial ordinaria.

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

con condición inicial${\displaystyle y(0)=y_{0}}$Podemos aproximar una solución a esta ecuación unidimensional utilizando una secuencia${\displaystyle (y_{n})}$Aplicación del método de Euler hacia adelante para la discretización numérica utilizando cualquier espaciado de malla regular.${\displaystyle h}$y puntos de la cuadrícula indexados por${\displaystyle n}$como sigue:

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

lo que implica la recurrencia lineal de primer orden con coeficientes constantes

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

Dado${\displaystyle y(0)=y_{0}}$La secuencia que satisface esa recurrencia es la progresión geométrica.

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

La solución analítica exacta de la ecuación diferencial es${\displaystyle y=f(x)=y_{0}\exp(-\kappa x)}$, correspondiente a la siguiente expansión de Taylor en${\displaystyle nh\kappa }$: $${\displaystyle f(x_{n})=f(nh)=y_{0}\exp(-\kappa nh)=y_{0}\left(1-nh\kappa +{\frac {n^{2}h^{2}\kappa ^{2}}{2}}+...\right).}$$

Por lo tanto, el error de la aproximación discreta en cada punto discreto es

$${\displaystyle |y_{n}-f(x_{n})|={\frac {nh^{2}\kappa ^{2}}{2}}+\ldots }$$

Para cualquier específico${\displaystyle x=p}$, dada una secuencia de aproximaciones de Euler hacia adelante${\displaystyle ((y_{n})_{k})}$, cada uno utilizando espaciados de cuadrícula${\displaystyle h_{k}}$que dividen${\displaystyle p}$de modo que${\displaystyle n_{p,k}=p/h_{k}}$, uno tiene

$${\displaystyle \lim _{h_{k}\rightarrow 0}{\frac {|y_{k}(p)-f(p)|}{h_{k}}}=\lim _{h_{k}\rightarrow 0}{\frac {|y_{k,n_{p,k}}-f(h_{k}n_{p,k})|}{h_{k}}}={\frac {h_{k}n_{p,k}\kappa ^{2}}{2}}={\frac {p\kappa ^{2}}{2}}}$$

para cualquier secuencia de cuadrículas con espaciamientos de cuadrícula sucesivamente más pequeños${\displaystyle h_{k}}$. De este modo${\displaystyle ((y_{n})_{k})}$converge a${\displaystyle f(x)}$punto por punto con un orden de convergencia${\displaystyle q=1}$y constante de error asintótica${\displaystyle p\kappa ^{2}/2}$en cada punto${\displaystyle p>0.}$De manera similar, la secuencia converge uniformemente con el mismo orden y con una tasa${\displaystyle L\kappa ^{2}/2}$en cualquier intervalo acotado de${\displaystyle p\leq L}$, pero no converge uniformemente en el conjunto no acotado de todos los valores reales positivos,${\displaystyle [0,\infty ).}$

En el análisis asintótico en general, una secuencia${\displaystyle (a_{k})_{k\in \mathbb {N} }}$que converge a un límite${\displaystyle L}$Se dice que converge asintóticamente a${\displaystyle L}$con un orden de convergencia más rápido que otra secuencia${\displaystyle (b_{k})_{k\in \mathbb {N} }}$que converge a${\displaystyle L}$en un espacio métrico compartido con métrica de distancia${\displaystyle |\cdot |,}$tales como los números reales o los números complejos con las métricas de diferencia absoluta ordinarias , si

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L\right|}{|b_{k}-L|}}=0,}$$

Se dice que ambos convergen asintóticamente a${\displaystyle L}$con el mismo orden de convergencia si

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L\right|}{|b_{k}-L|}}=\mu }$$

para alguna constante finita positiva${\displaystyle \mu ,}$y se dice que ambos convergen asintóticamente a${\displaystyle L}$con la misma tasa y orden de convergencia si

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L\right|}{|b_{k}-L|}}=1.}$$

Estas definiciones comparativas de tasa y orden de convergencia asintótica son fundamentales en el análisis asintótico . ^{[ 10 ] [ 11 ]} Para las dos primeras de ellas existen expresiones asociadas en notación asintótica O : la primera es que${\displaystyle a_{k}-L=o(b_{k}-L)}$en notación de o minúscula ^{[ 12 ]} y la segunda es que${\displaystyle a_{k}-L=\Theta (b_{k}-L)}$en notación de Knuth. ^{[ 13 ]} La tercera también se denomina equivalencia asintótica, expresada${\displaystyle a_{k}-L\sim b_{k}-L.}$^{[ 14 ] [ 15 ]}

Para cualesquiera dos progresiones geométricas${\displaystyle (ar^{k})_{k\in \mathbb {N} }}$y${\displaystyle (bs^{k})_{k\in \mathbb {N} },}$con límite compartido cero, las dos secuencias son asintóticamente equivalentes si y solo si ambas${\displaystyle a=b}$y${\displaystyle r=s.}$Convergen con el mismo orden si y solo si${\displaystyle r=s.}$${\displaystyle (ar^{k})}$converge con un orden más rápido que${\displaystyle (bs^{k})}$si y solo si${\displaystyle r<s.}$La convergencia de cualquier serie geométrica a su límite tiene términos de error que son iguales a una progresión geométrica, por lo que relaciones similares se dan también entre series geométricas. Cualquier sucesión asintóticamente equivalente a una sucesión geométrica convergente puede decirse que "converge geométricamente" o "converge exponencialmente" con respecto a la diferencia absoluta de su límite, o bien que "converge linealmente" con respecto a un logaritmo de la diferencia absoluta, como el "número de decimales de precisión". Esto último es habitual en el análisis numérico.

Para cualesquiera dos secuencias de elementos proporcionales a una potencia inversa de${\displaystyle k,}$${\displaystyle (ak^{-n})_{k\in \mathbb {N} }}$y${\displaystyle (bk^{-m})_{k\in \mathbb {N} },}$con límite compartido cero, las dos secuencias son asintóticamente equivalentes si y solo si ambas${\displaystyle a=b}$y${\displaystyle n=m.}$Convergen con el mismo orden si y solo si${\displaystyle n=m.}$${\displaystyle (ak^{-n})}$converge con un orden más rápido que${\displaystyle (bk^{-m})}$si y solo si${\displaystyle n>m.}$

Para cualquier secuencia${\displaystyle (a_{k})_{k\in \mathbb {N} }}$con un límite de cero, su convergencia puede compararse con la convergencia de la secuencia desplazada.${\displaystyle (a_{k-1})_{k\in \mathbb {N} },}$reescalamientos de la secuencia desplazada por una constante${\displaystyle \mu ,}$${\displaystyle (\mu a_{k-1})_{k\in \mathbb {N} },}$y escalado${\displaystyle q}$-potencias de la secuencia desplazada,${\displaystyle (\mu a_{k-1}^{q})_{k\in \mathbb {N} }.}$Estas comparaciones son la base de las clasificaciones de Q-convergencia para métodos numéricos iterativos como se describió anteriormente: cuando una secuencia de errores de iteración de un método numérico${\displaystyle (|x_{k}-L|)_{k\in \mathbb {N} }}$es asintóticamente equivalente a la secuencia desplazada, exponenciada y reescalada de errores de iteración.${\displaystyle (\mu |x_{k-1}-L|^{q})_{k\in \mathbb {N} },}$Se dice que converge con el orden.${\displaystyle q}$y tasa${\displaystyle \mu .}$