Tasa de convergencia

Velocidad de convergencia de una secuencia matemática

En el análisis matemático , en particular en el análisis numérico , la tasa de convergencia y el orden de convergencia de una secuencia que converge a un límite son cualquiera de varias caracterizaciones de la rapidez con la que esa secuencia se acerca a su límite. Estas se dividen en general en tasas y órdenes de convergencia que describen la rapidez con la que una secuencia se acerca aún más a su límite una vez que ya está cerca de él, llamadas tasas asintóticas y órdenes de convergencia, y las que describen la rapidez con la que las secuencias se acercan a sus límites desde puntos de partida que no están necesariamente cerca de sus límites, llamadas tasas no asintóticas y órdenes de convergencia.

El comportamiento asintótico es particularmente útil para decidir cuándo detener una secuencia de cálculos numéricos, por ejemplo, una vez que se ha alcanzado una precisión objetivo con un algoritmo iterativo de búsqueda de raíces , pero el comportamiento preasintótico suele ser crucial para determinar si se debe comenzar una secuencia de cálculos, ya que puede ser imposible o poco práctico alcanzar una precisión objetivo con un enfoque mal elegido. Las tasas asintóticas y los órdenes de convergencia son el foco de este artículo.

En los cálculos numéricos prácticos, las tasas asintóticas y los órdenes de convergencia siguen dos convenciones comunes para dos tipos de secuencias: la primera para secuencias de iteraciones de un método numérico iterativo y la segunda para secuencias de discretizaciones numéricas sucesivamente más precisas de un objetivo. En matemáticas formales, las tasas de convergencia y los órdenes de convergencia se describen a menudo de forma comparativa utilizando la notación asintótica comúnmente llamada " notación O grande ", que puede utilizarse para abarcar ambas convenciones anteriores; esta es una aplicación del análisis asintótico .

Para los métodos iterativos, se dice que una secuencia que converge a tiene orden de convergencia asintótico y tasa de convergencia asintótica si ${\displaystyle (x_{k})}$ ${\displaystyle L}$ ${\displaystyle q\geq 1}$ ${\displaystyle \mu }$

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

Cuando se requiere precisión metodológica, estas tasas y órdenes de convergencia se conocen específicamente como tasas y órdenes de convergencia Q, abreviatura de convergencia-cociente, ya que el límite en cuestión es un cociente de términos de error. ^[1] La tasa de convergencia también puede denominarse constante de error asintótico , y algunos autores utilizarán tasa donde este artículo utiliza orden. ^{[2] Los métodos} de aceleración de series son técnicas para mejorar la tasa de convergencia de la secuencia de sumas parciales de una serie y posiblemente también su orden de convergencia. ${\displaystyle \mu }$

Se utilizan conceptos similares para las secuencias de discretizaciones. Por ejemplo, idealmente, la solución de una ecuación diferencial discretizada mediante una cuadrícula regular convergerá a la solución de la ecuación continua a medida que el espaciado de la cuadrícula tiende a cero y, de ser así, la tasa asintótica y el orden de esa convergencia son propiedades importantes del método de cuadrícula. Se dice que una secuencia de soluciones de cuadrícula aproximadas de algún problema que converge a una solución verdadera con una secuencia correspondiente de espaciamientos de cuadrícula regulares que convergen a 0 tiene un orden asintótico de convergencia y una tasa asintótica de convergencia si ${\displaystyle (y_{k})}$ ${\displaystyle S}$ ${\displaystyle (h_{k})}$ ${\displaystyle q}$ ${\displaystyle \mu }$

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

donde los símbolos de valor absoluto representan una métrica para el espacio de soluciones, como la norma uniforme . También se aplican definiciones similares para esquemas de discretización sin cuadrícula, como las mallas poligonales de un método de elementos finitos o los conjuntos de base en química computacional : en general, la definición apropiada de la tasa asintótica implicará el límite asintótico de la relación entre un término de error de aproximación anterior y una potencia de orden asintótico de un parámetro de escala de discretización inferior. ${\displaystyle \mu }$ ${\displaystyle q}$

En general, comparativamente, se dice que una secuencia que converge a un límite converge asintóticamente más rápidamente que otra secuencia que converge a un límite si ${\displaystyle (a_{k})}$ ${\displaystyle L_{a}}$ ${\displaystyle (b_{k})}$ ${\displaystyle L_{b}}$

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

y se dice que los dos convergen asintóticamente con el mismo orden de convergencia si el límite es cualquier valor finito positivo. Se dice que los dos son asintóticamente equivalentes si el límite es igual a uno. Estas definiciones comparativas de tasa y orden de convergencia asintótica son fundamentales en el análisis asintótico y encuentran una amplia aplicación en el análisis matemático en su conjunto, incluido el análisis numérico, el análisis real , el análisis complejo y el análisis funcional .

Tasas asintóticas de convergencia para métodos iterativos

Definiciones

Supóngase que la secuencia de iteraciones de un método iterativo converge al número límite cuando . Se dice que la secuencia converge con orden a y con una tasa de convergencia si el límite de cocientes de diferencias absolutas de iteraciones secuenciales a partir de su límite satisface ${\displaystyle (x_{k})}$ ${\displaystyle L}$ ${\displaystyle k\rightarrow \infty }$ ${\displaystyle q}$ ${\displaystyle L}$ ${\displaystyle \mu }$ ${\displaystyle k\rightarrow \infty }$ ${\displaystyle x_{k},x_{k+1}}$ ${\displaystyle L}$

$${\displaystyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|^{q}}}=\mu }$$

para alguna constante positiva si y si . ^{[1] [3] [4]} Se necesitan otras definiciones de velocidad más técnicas si la secuencia converge pero ^[5] o el límite no existe. ^[1] Esta definición se llama técnicamente Q-convergencia, abreviatura de convergencia de cociente, y las velocidades y órdenes se denominan velocidades y órdenes de Q-convergencia cuando se necesita esa especificidad técnica. § La R-convergencia, a continuación, es una alternativa apropiada cuando este límite no existe. ${\displaystyle \mu \in (0,1)}$ ${\displaystyle q=1}$ ${\displaystyle \mu \in (0,\infty )}$ ${\displaystyle q>1}$ ${\textstyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|}}=1}$

Las secuencias con órdenes mayores convergen más rápidamente que aquellas con órdenes menores, y aquellas con tasas menores convergen más rápidamente que aquellas con tasas mayores para un orden determinado. Este comportamiento de "tasas menores convergen más rápidamente" entre secuencias del mismo orden es estándar, pero puede ser contraintuitivo. Por lo tanto, también es común definir como tasa; esta es la "cantidad de decimales adicionales de precisión por iteración" para secuencias que convergen con orden 1. ^[1] ${\displaystyle q}$ ${\displaystyle \mu }$ ${\displaystyle -\log _{10}\mu }$

Las potencias enteras de son comunes y reciben nombres comunes. La convergencia con orden y se llama convergencia lineal y se dice que la secuencia converge linealmente a . La convergencia con y cualquiera se llama convergencia cuadrática y se dice que la secuencia converge cuadráticamente . La convergencia con y cualquiera se llama convergencia cúbica . Sin embargo, no es necesario que sea un entero. Por ejemplo, el método de la secante , al converger a una raíz regular simple , tiene un orden de la proporción áurea φ ≈ 1,618. ^[6] ${\displaystyle q}$ ${\displaystyle q=1}$ ${\displaystyle \mu \in (0,1)}$ ${\displaystyle L}$ ${\displaystyle q=2}$ ${\displaystyle \mu }$ ${\displaystyle q=3}$ ${\displaystyle \mu }$ ${\displaystyle q}$

Los nombres comunes para los órdenes enteros de convergencia se relacionan con la notación O grande asintótica , donde la convergencia del cociente implica Estas son expresiones polinómicas lineales, cuadráticas y cúbicas cuando es 1, 2 y 3, respectivamente. Más precisamente, los límites implican que el error de orden principal es exactamente lo que se puede expresar utilizando la notación O pequeña asintótica como ${\textstyle |x_{k+1}-L|=O(|x_{k}-L|^{q}).}$ ${\displaystyle q}$ ${\textstyle \mu |x_{k}-L|^{q},}$ ${\textstyle |x_{k+1}-L|=\mu |x_{k}-L|^{q}+o(|x_{k}-L|^{q}).}$

En general, cuando una secuencia o cualquier secuencia que satisface esas secuencias se dice que convergen superlinealmente (es decir, más rápido que linealmente). ^[1] Se dice que una secuencia converge sublinealmente (es decir, más lento que linealmente) si converge y Es importante destacar que es incorrecto decir que estas secuencias de orden sublineal convergen linealmente con una tasa asintótica de convergencia de 1. Una secuencia converge logarítmicamente a si la secuencia converge sublinealmente y también ^[5] ${\displaystyle q>1}$ ${\textstyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|}}=0,}$ ${\textstyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|}}=1.}$ ${\displaystyle (x_{k})}$ ${\displaystyle L}$ ${\textstyle \lim _{k\to \infty }{\frac {|x_{k+1}-x_{k}|}{|x_{k}-x_{k-1}|}}=1.}$

R-convergencia

Las definiciones de tasas de convergencia Q tienen el inconveniente de que no capturan naturalmente el comportamiento de convergencia de secuencias que convergen, pero no convergen con una tasa asintóticamente constante con cada paso, de modo que el límite de convergencia Q no existe. Una clase de ejemplos son las progresiones geométricas escalonadas que se acercan a sus límites solo cada dos pasos o cada varios pasos, por ejemplo el ejemplo detallado a continuación (donde se aplica la función de piso a ). Los límites de convergencia Q-lineales definitorios no existen para esta secuencia porque una subsecuencia de cocientes de error que comienza a partir de pasos impares converge a 1 y otra subsecuencia de cocientes que comienza a partir de pasos pares converge a 1/4. Cuando dos subsecuencias de una secuencia convergen a límites diferentes, la secuencia en sí no converge a un límite. ${\textstyle (b_{k})=1,1,1/4,1/4,1/16,1/16,\ldots ,1/4^{\left\lfloor {\frac {k}{2}}\right\rfloor },\ldots }$ ${\textstyle \lfloor x\rfloor }$ ${\displaystyle x}$

En casos como estos, es más apropiada una definición estrechamente relacionada pero más técnica de la tasa de convergencia llamada R-convergencia. El prefijo "R-" significa "raíz". ^{[1] [7] : 620} Se dice que una secuencia que converge a converge al menos R-linealmente si existe una secuencia que limita el error tal que y converge Q-linealmente a cero; se aplican definiciones análogas para la convergencia R-superlineal, la convergencia R-sublineal, la convergencia R-cuadrática, etc. ^[1] ${\displaystyle (x_{k})}$ ${\displaystyle L}$ ${\displaystyle (\varepsilon _{k})}$ ${\textstyle |x_{k}-L|\leq \varepsilon _{k}\quad {\text{for all }}k}$ ${\displaystyle (\varepsilon _{k})}$

Cualquier secuencia de acotación de error proporciona un límite inferior en la tasa y el orden de convergencia R y el límite inferior más grande proporciona la tasa y el orden exactos de convergencia R. En cuanto a la convergencia Q, las secuencias con órdenes mayores convergen más rápidamente y aquellas con tasas menores convergen más rápidamente para un orden dado, por lo que estas secuencias de límite inferior de error de tasa más grande son aquellas que tienen el mayor posible y el menor posible dado que . ${\displaystyle (\varepsilon _{k})}$ ${\displaystyle q}$ ${\displaystyle \mu }$ ${\displaystyle q}$ ${\displaystyle \mu }$ ${\displaystyle q}$

En el ejemplo dado anteriormente, la secuencia de límites estrictos converge Q-linealmente con una tasa de 1/2, por lo que converge R-linealmente con una tasa de 1/2. En general, para cualquier progresión geométrica escalonada , la secuencia no convergerá Q-linealmente, pero convergerá R-linealmente con una tasa. Estos ejemplos demuestran por qué la "R" en convergencia R-lineal es la abreviatura de "raíz". ${\textstyle (b_{k})}$ ${\textstyle (\varepsilon _{k})=2,1,1/2,1/4,1/8,1/16,\ldots ,1/2^{k-1},\ldots }$ ${\textstyle (b_{k})}$ ${\displaystyle (ar^{\lfloor k/m\rfloor })}$ ${\textstyle {\sqrt[{m}]{|r|}}.}$

Ejemplos

La progresión geométrica converge a . Introduciendo la secuencia en la definición de convergencia Q-lineal (es decir, orden de convergencia 1) se muestra que ${\textstyle (a_{k})=1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},{\frac {1}{32}},\ldots ,1/{2^{k}},\dots }$ ${\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}}.}$$

Por lo tanto, converge Q-linealmente con una tasa de convergencia de ; vea el primer gráfico de la figura a continuación. ${\displaystyle (a_{k})}$ ${\displaystyle \mu =1/2}$

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

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

La secuencia converge a cero de manera Q-superlineal. De hecho, es cuadráticamente convergente con una tasa de convergencia cuadrática de 1. Esto se muestra en el tercer gráfico de la figura siguiente. $${\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 }$$

Finalmente, la secuencia converge a cero de forma Q-sublineal y logarítmica y su convergencia se muestra como el cuarto gráfico de la figura siguiente. $${\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 }$$

Gráficos log-lineales de las secuencias de ejemplo a _k , b _k , c _k y d _k que ejemplifican tasas de convergencia lineal, lineal, superlineal (cuadrática) y sublineal, respectivamente.

Tasas de convergencia a puntos fijos de secuencias recurrentes

Las secuencias recurrentes , llamadas iteraciones de punto fijo , definen sistemas dinámicos autónomos en el 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 , tal que , el punto fijo es un punto fijo atractivo y la secuencia recurrente convergerá al menos linealmente a p para cualquier valor inicial suficientemente cercano a p . Si y , entonces la secuencia recurrente convergerá al menos cuadráticamente, y así sucesivamente. Si , 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. ${\textstyle x_{k+1}:=f(x_{k})}$ ${\textstyle f(p)=p,}$ ${\textstyle |f'(p)|<1}$ ${\displaystyle x_{0}}$ ${\displaystyle |f'(p)|=0}$ ${\textstyle |f''(p)|<1}$ ${\displaystyle |f'(p)|>1}$

Estimación de pedidos

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 : ^[8] ${\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 una aproximación numérica de un valor exacto a través de un método numérico de orden, véase ^{[9] .} ${\displaystyle q}$

Aceleración de las tasas de convergencia

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. Tales técnicas se conocen en general 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 por 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 converge linealmente, el método de Aitken la transforma en una secuencia que aún converge linealmente (excepto en casos especiales diseñados patológicamente), pero más rápida 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_{k})}$ ${\displaystyle (a_{k})}$ ${\textstyle \lim _{k\rightarrow \infty }(a_{k}-L)/(x_{k}-L)=0}$

Tasas asintóticas de convergencia para métodos de discretización

Definiciones

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

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

para algunas constantes positivas y y utilizando para representar una métrica de distancia apropiada en el espacio de soluciones , con mayor frecuencia 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, la inversa 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 de base mecánico cuántico . ${\displaystyle \mu }$ ${\displaystyle q}$ ${\displaystyle |x|}$

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 cualquier secuencia discreta particular de soluciones discretizadas. En estos casos, se considera una única solución discretizada abstracta generada utilizando el método con un parámetro de escala y, entonces, se dice que el método tiene un orden asintótico de convergencia y una tasa asintótica de convergencia si ${\displaystyle y_{h}}$ ${\displaystyle h}$ ${\displaystyle q}$ ${\displaystyle \mu }$

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

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

En algunos casos, puede ser importante utilizar múltiples tasas y órdenes para el mismo método pero con diferentes opciones de parámetros de escala, por ejemplo, para métodos de diferencias finitas basados ​​en cuadrículas multidimensionales donde las diferentes dimensiones tienen diferentes espaciamientos de cuadrícula o para métodos de elementos finitos basados ​​en mallas poligonales donde elegir la distancia promedio entre los puntos de la malla o la distancia máxima entre los puntos de la malla como parámetros de escala puede implicar diferentes órdenes de convergencia. En algunos contextos especialmente técnicos, las tasas asintóticas y los órdenes de convergencia 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 posiblemente afecte la tasa asintótica y el orden de convergencia del método con respecto a los otros parámetros de escala.

Ejemplo

Consideremos la ecuación diferencial ordinaria

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

con condición inicial . Podemos aproximar una solución a esta ecuación unidimensional utilizando una secuencia que aplica el método de Euler directo para discretización numérica utilizando cualquier espaciado de cuadrícula regular y puntos de cuadrícula indexados por de la siguiente manera: ${\displaystyle y(0)=y_{0}}$ ${\displaystyle (y_{n})}$ ${\displaystyle h}$ ${\displaystyle n}$

${\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 , la secuencia que satisface esa recurrencia es la progresión geométrica ${\displaystyle y(0)=y_{0}}$

$${\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 , correspondiente a la siguiente expansión de Taylor en : ${\displaystyle y=f(x)=y_{0}\exp(-\kappa x)}$ ${\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 , dada una secuencia de aproximaciones de Euler hacia adelante , cada una utilizando espaciamientos de cuadrícula que se dividen de modo que , se tiene ${\displaystyle x=p}$ ${\displaystyle ((y_{n})_{k})}$ ${\displaystyle h_{k}}$ ${\displaystyle p}$ ${\displaystyle n_{p,k}=p/h_{k}}$

$${\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 . Por lo tanto , converge a puntualmente con un orden de convergencia y un error asintótico constante en cada punto. De manera similar, la secuencia converge uniformemente con el mismo orden y con una tasa en cualquier intervalo acotado de , pero no converge uniformemente en el conjunto ilimitado de todos los valores reales positivos, ${\displaystyle h_{k}}$ ${\displaystyle ((y_{n})_{k})}$ ${\displaystyle f(x)}$ ${\displaystyle q=1}$ ${\displaystyle p\kappa ^{2}/2}$ ${\displaystyle p>0.}$ ${\displaystyle L\kappa ^{2}/2}$ ${\displaystyle p\leq L}$ ${\displaystyle [0,\infty ).}$

Comparación de tasas asintóticas de convergencia

Definiciones

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

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

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

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

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

$${\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 estas hay expresiones asociadas en notación O asintótica : la primera es la de notación o minúscula ^[12] y la segunda es la de notación Knuth. ^[13] La tercera también se llama equivalencia asintótica, expresada ^{[14] [15]} ${\displaystyle a_{k}-L=o(b_{k}-L)}$ ${\displaystyle a_{k}-L=\Theta (b_{k}-L)}$ ${\displaystyle a_{k}-L\sim b_{k}-L.}$

Ejemplos

Para dos progresiones geométricas cualesquiera y con límite compartido cero, las dos secuencias son asintóticamente equivalentes si y solo si ambas y convergen con el mismo orden si y solo si converge con un orden más rápido que si y solo si 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 también se mantienen relaciones similares entre series geométricas. Se puede decir que cualquier secuencia que sea asintóticamente equivalente a una secuencia geométrica convergente "converge geométricamente" o "converge exponencialmente" con respecto a la diferencia absoluta con respecto a su límite, o se puede decir que "converge linealmente" con respecto a un logaritmo de la diferencia absoluta como el "número de decimales de precisión". Esto último es estándar en el análisis numérico. ${\displaystyle (ar^{k})_{k\in \mathbb {N} }}$ ${\displaystyle (bs^{k})_{k\in \mathbb {N} },}$ ${\displaystyle a=b}$ ${\displaystyle r=s.}$ ${\displaystyle r=s.}$ ${\displaystyle (ar^{k})}$ ${\displaystyle (bs^{k})}$ ${\displaystyle r<s.}$

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

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

Tasas de convergencia no asintóticas

Las tasas de convergencia no asintóticas no tienen las definiciones estándar y comunes que tienen las tasas de convergencia asintóticas. Entre las técnicas formales, la teoría de Lyapunov es uno de los marcos más poderosos y ampliamente aplicados para caracterizar y analizar el comportamiento de la convergencia no asintótica.

En el caso de los métodos iterativos , un enfoque práctico común consiste en analizar estas tasas en términos de la cantidad de iteraciones o el tiempo de computación necesario para alcanzar proximidades cercanas a un límite desde puntos de partida alejados del límite. La tasa no asintótica es entonces una inversa de esa cantidad de iteraciones o tiempo de computación. En aplicaciones prácticas, se dirá que un método iterativo que requiere menos pasos o menos tiempo de computación que otro para alcanzar la precisión objetivo ha convergido más rápido que el otro, incluso si su convergencia asintótica es más lenta. Estas tasas generalmente serán diferentes para diferentes puntos de partida y diferentes umbrales de error para definir las proximidades. Es más común analizar resúmenes de distribuciones estadísticas de estas tasas de un solo punto correspondientes a distribuciones de posibles puntos de partida, como la "tasa no asintótica promedio", la "tasa no asintótica mediana" o la "tasa no asintótica del peor caso" para algún método aplicado a algún problema con algún umbral de error fijo. Estos conjuntos de puntos de partida se pueden elegir según parámetros como la distancia inicial desde el límite final para definir cantidades como "tasa promedio no asintótica de convergencia desde una distancia dada".

En el caso de los métodos de aproximación discretizada , se pueden utilizar enfoques similares con un parámetro de escala de discretización, como la inversa de un número de puntos de la cuadrícula o de la malla , o una frecuencia de corte de la serie de Fourier que desempeñe el papel de número de iteración inverso, aunque no es especialmente común. Para cualquier problema, existe un parámetro de escala de discretización máximo compatible con una precisión de aproximación deseada, y puede que no sea tan pequeño como se requiere para que la tasa asintótica y el orden de convergencia proporcionen estimaciones precisas del error. En aplicaciones prácticas, cuando un método de discretización proporciona una precisión deseada con un parámetro de escala de discretización mayor que otro, a menudo se dirá que converge más rápido que el otro, incluso si su convergencia asintótica final es más lenta.

Referencias

1. Nocedal, Jorge; Wright, Stephen J. (1999). Optimización numérica (1.ª ed.). Nueva York, NY: Springer. pp. 28–29. ISBN 978-0-387-98793-4.
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. Hundley, Douglas. "Tasa de convergencia" (PDF) . Whitman College . Consultado el 13 de diciembre de 2020 .
4. Porta, FA (1989). "Sobre el orden Q y el orden R de convergencia" (PDF) . Journal of Optimization Theory and Applications . 63 (3): 415–431. doi :10.1007/BF00939805. S2CID  116192710 . Consultado el 31 de julio de 2020 .
5. 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 .
6. Chanson, Jeffrey R. (3 de octubre de 2024). «Orden de convergencia». LibreTexts Mathematics . Consultado el 3 de octubre de 2024 .
7. Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica (2.ª ed.). Berlín, Nueva York: Springer-Verlag . ISBN 978-0-387-30303-1.
8. Senning, Jonathan R. "Cálculo y estimación de la tasa de convergencia" (PDF) . gordon.edu . Consultado el 7 de agosto de 2020 .
9. Senning, Jonathan R. "Verificación de tasas de convergencia numérica" ​​(PDF) . Consultado el 9 de febrero de 2024 .
10. Balcázar, José L.; Gabarró, Joaquim. "Clases de complejidad no uniformes especificadas por límites superiores e inferiores" (PDF) . RAIRO – Informática Teórica y Aplicaciones – Informatique Théorique et Applications . 23 (2): 180. ISSN  0988-3754. Archivado (PDF) desde el original el 14 de marzo de 2017 . Consultado el 14 de marzo de 2017 a través de Numdam.
11. Cucker, Felipe; Bürgisser, Peter (2013). "A.1 Big Oh, Little Oh, and Other Comparisons". Estado: La geometría de los algoritmos numéricos . Berlín, Heidelberg: Springer. págs. 467–468. doi :10.1007/978-3-642-38896-5. ISBN 978-3-642-38896-5.
12. Apostol, Tom M. (1967). Cálculo . Vol. 1 (2.ª ed.). Estados Unidos: John Wiley & Sons. pág. 286. ISBN. 0-471-00005-1.
13. Knuth, Donald (abril-junio de 1976). "Gran ómicron, gran omega y gran theta". SIGACT News . 8 (2): 18–24. doi : 10.1145/1008328.1008329 . S2CID 5230246 . 
14. Apostol, Tom M. (1967). Cálculo . Vol. 1 (2.ª ed.). Estados Unidos: John Wiley & Sons. pág. 396. ISBN 0-471-00005-1.
15. "Igualdad asintótica", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]