Tasa de convergencia - Rate of convergence

Ecuaciones diferenciales
Ecuaciones diferenciales de Navier-Stokes utilizadas para simular el flujo de aire alrededor de una obstrucción
Alcance Ciencias Naturales Ingenieria Astronomía Física Química Biología Geología Matemáticas Aplicadas Mecánica de Medios Continuos Teoría del caos Sistemas dinámicos Ciencias Sociales Ciencias económicas Dinámica poblacional
Clasificación
Tipos Ordinario Parcial Diferencial-algebraico Integro-diferencial Fraccionario Lineal No lineal Por tipo de variable Variables dependientes e independientes Autónomo Complejo Acoplado / desacoplado Exacto Homogéneo  / No homogéneo Características Pedido Operador Notación
Relación con los procesos Diferencia (análogo discreto) Estocástico Estocástico parcial Demora
Solución
Existencia y singularidad Teorema de Picard-Lindelöf Teorema de existencia de Peano Teorema de existencia de Carathéodory Teorema de Cauchy-Kowalevski
Temas generales Wronskian Retrato de fase Espacio de fase Estabilidad de Lyapunov  / Asintótica  / Exponencial Tasa de convergencia Serie  / Soluciones integrales Integracion numerica Función delta de Dirac
Métodos de solución Inspección Método de características Euler Fórmula de respuesta exponencial Diferencia finita   ( Crank – Nicolson ) Elemento finito Elemento infinito Volumen finito Galerkin Petrov – Galerkin Factor integrador Transformaciones integrales Teoría de la perturbación Runge – Kutta Separación de variables Coeficientes indeterminados Variación de parámetros
Personas Isaac Newton Gottfried Leibniz Leonhard Euler Émile Picard Józef Maria Hoene-Wroński Ernst Lindelöf Rudolf Lipschitz Augustin-Louis Cauchy John Crank Phyllis Nicolson Carl David Tolmé Runge Martin Kutta
v t mi

En el análisis numérico , el orden de convergencia y la tasa de convergencia de una secuencia convergente son cantidades que representan la rapidez con la que 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 x ^ {*}}$ ${\ Displaystyle q \ geq 1}$ ${\ Displaystyle \ mu}$

${\ Displaystyle \ lim _ {n \ rightarrow \ infty} {\ frac {\ left | x_ {n + 1} -x ^ {*} \ right |} {\ left | x_ {n} -x ^ {*} \ right | ^ {q}}} = \ mu.}$

La tasa de convergencia también se denomina constante de error asintótica . Tenga en cuenta que esta terminología no está estandarizada y algunos autores usarán la tasa donde este artículo usa el orden (por ejemplo,). ${\ 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. Dicha aceleración se logra comúnmente con transformaciones de secuencia .

Velocidad de convergencia para métodos iterativos

Definiciones de Q-convergencia

Suponga que la secuencia converge al número . Se dice que la secuencia converge Q-linealmente si existe un número tal que ${\ Displaystyle (x_ {k})}$${\ Displaystyle L}$${\ Displaystyle L}$${\ Displaystyle \ mu \ in (0,1)}$

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

El número se llama tasa de convergencia.${\ Displaystyle \ mu}$

Se dice que la secuencia converge Q-superlinealmente a ${\ Displaystyle L}$ (es decir, más rápido que linealmente) si

${\ Displaystyle \ lim _ {k \ to \ infty} {\ frac {| x_ {k + 1} -L |} {| x_ {k} -L |}} = 0}$

y se dice que converge Q-sublinealmente a ${\ Displaystyle L}$ (es decir, más lento que linealmente) si

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

Si la secuencia converge sublinealmente y adicionalmente

${\ Displaystyle \ lim _ {k \ to \ infty} {\ frac {| x_ {k + 2} -x_ {k + 1} |} {| x_ {k + 1} -x_ {k} |}} = 1,}$

entonces se dice que la secuencia converge logarítmicamente a . Tenga en cuenta que, a diferencia de las definiciones anteriores, la convergencia logarítmica no se denomina "Q-logarítmica". ${\ Displaystyle (x_ {k})}$ ${\ Displaystyle L}$

Para clasificar aún más la convergencia, el orden de convergencia se define de la siguiente manera. La secuencia se dice que converge con el fin de ${\ Displaystyle q}$${\ Displaystyle L}$ para si ${\ Displaystyle q \ geq 1}$

${\ Displaystyle \ lim _ {k \ to \ infty} {\ frac {| x_ {k + 1} -L |} {| x_ {k} -L | ^ {q}}} <M}$

para alguna constante positiva (no necesariamente menor que 1 si ). En particular, la convergencia con el orden ${\ Displaystyle M> 0}$${\ Displaystyle q> 1}$

• ${\ Displaystyle q = 1}$ se llama convergencia lineal (si ), ${\ Displaystyle M <1}$
• ${\ Displaystyle q = 2}$ se llama convergencia cuadrática ,
• ${\ Displaystyle q = 3}$ se llama convergencia cúbica ,
• etc.

Algunas fuentes exigen que sea ​​estrictamente mayor que ya que el caso así lo requiere es mejor tratarlo por separado. Sin embargo, no es necesario que sea ​​un número entero. Por ejemplo, el método de la secante , cuando converge a una raíz simple regular , tiene un orden de φ ≈ 1.618. ${\ Displaystyle q}$${\ Displaystyle 1}$${\ Displaystyle q = 1}$${\ Displaystyle M <1}$${\ Displaystyle q}$

En las definiciones anteriores, "Q-" significa "cociente" porque los términos se definen utilizando el cociente entre dos términos sucesivos. A menudo, sin embargo, la "Q-" se elimina y simplemente se dice que una secuencia tiene convergencia lineal , convergencia cuadrática , etc.

Estimación de pedidos

Un método práctico para calcular el orden de convergencia de una secuencia es calcular la siguiente secuencia, que converge a ${\ Displaystyle q}$

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

Definición de R-convergencia

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

Suponga 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 {para todos}} k \ ,,}$

y converge Q-linealmente a cero. El prefijo "R-" significa "raíz". ${\ Displaystyle (\ varepsilon _ {k})}$

Ejemplos de

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

Se puede demostrar que esta secuencia converge a . Para determinar el tipo de convergencia, introducimos la secuencia en la definición de convergencia Q-lineal, ${\ 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, encontramos que Q converge linealmente y tiene una tasa de convergencia de . De manera más general, para cualquiera , la secuencia converge linealmente con la tasa . ${\ 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 \}}$

también converge linealmente a 0 con tasa 1/2 bajo la definición de R-convergencia, pero no bajo la definición de Q-convergencia. (Tenga en cuenta que es la función de piso , que da el entero más grande que es menor o igual a ). ${\ 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 \ }}$

converge superlinealmente. De hecho, es cuadráticamente convergente.

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

converge sublineal y logarítmicamente.

Velocidad de convergencia para métodos de discretización

Existe una situación similar para los métodos de discretización. El parámetro importante aquí para la velocidad de convergencia no es el número de iteración k , sino el número de puntos de la cuadrícula y el espaciado de la cuadrícula. En este caso, el número de puntos de la cuadrícula n en un proceso de discretización es inversamente proporcional al espaciado de la cuadrícula.

En este caso, se dice que una secuencia converge a L con orden q si existe una constante C tal que ${\ Displaystyle (x_ {n})}$

${\ Displaystyle | x_ {n} -L | <Cn ^ {- q} {\ text {para todos}} n.}$

Esto está escrito usando notación O grande . ${\ Displaystyle | x_ {n} -L | = {\ mathcal {O}} (n ^ {- q})}$

Ésta es la definición relevante cuando se discuten los métodos para la cuadratura numérica o la solución de ecuaciones diferenciales ordinarias .

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 y calcular los errores resultantes y . Luego, el orden de convergencia se aproxima mediante la siguiente fórmula: ${\ Displaystyle h _ {\ text {nuevo}}}$${\ displaystyle h _ {\ text {antiguo}}}$${\ displaystyle e _ {\ text {nuevo}}}$${\ displaystyle e _ {\ text {antiguo}}}$

${\ Displaystyle q \ approx {\ frac {\ log (e _ {\ text {nuevo}} / e _ {\ text {antiguo}})} {\ log (h _ {\ text {nuevo}} / h _ {\ text { viejo}})}}.}$

Ejemplos (continuación)

La secuencia con se introdujo anteriormente. Esta secuencia converge con el orden 1 según la convención para métodos de discretización. ${\ Displaystyle (d_ {k})}$${\ Displaystyle d_ {k} = 1 / (k + 1)}$

La secuencia con , que también se introdujo anteriormente, converge con el orden q para cada número q . Se dice que converge exponencialmente usando la convención para métodos de discretización. Sin embargo, solo converge linealmente (es decir, con el orden 1) usando la convención para métodos iterativos. ${\ Displaystyle (a_ {k})}$${\ Displaystyle a_ {k} = 2 ^ {- k}}$

El orden de convergencia de un método de discretización está relacionado con su error de truncamiento global (GTE) .

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 converge más rápidamente al mismo límite. Estas técnicas se conocen en general como " aceleración en serie ". El objetivo de la secuencia transformada es reducir el costo computacional del cálculo. Un ejemplo de aceleración en serie es el proceso delta cuadrado de Aitken .

Referencias

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; La definición de Big O cuando se utiliza la serie de Taylor se utiliza 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 . .