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. Una secuencia que converge a se dice que tiene orden de convergencia y tasa de convergencia Si
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, [2] ).
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 para 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 a si existe un numero tal que
El número se llama tasa de convergencia. [3]
Se dice que la secuencia converge Q-superlinealmente a (es decir, más rápido que linealmente) si
y se dice que converge Q-sublinealmente a (es decir, más lento que linealmente) si
Si la secuencia converge sublinealmente y adicionalmente
entonces se dice que la secuencia converge logarítmicamente a . [4] Tenga en cuenta que, a diferencia de las definiciones anteriores, la convergencia logarítmica no se denomina "Q-logarítmica".
Para clasificar aún más la convergencia, el orden de convergencia se define de la siguiente manera. Se dice que la secuencia converge con el orden a por Si
por alguna constante positiva (no necesariamente menos de 1 si ). En particular, la convergencia con el orden
- se llama convergencia lineal (si),
- se llama convergencia cuadrática ,
- se llama convergencia cúbica ,
- etc.
Algunas fuentes requieren que es estrictamente mayor que desde el caso requiere por lo que es mejor tratarlo por separado. [5] Sin embargo, no es necesario queser 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. [ cita requerida ]
En las definiciones anteriores, "Q-" significa "cociente" porque los términos se definen utilizando el cociente entre dos términos sucesivos. [6] : 619 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
Definición de R-convergencia
Las definiciones de Q-convergencia tienen el inconveniente de que no incluyen algunas secuencias, como la secuencia a continuación, que convergen razonablemente rápido, pero cuya tasa es variable. Por tanto, la definición de tasa de convergencia se amplía de la siguiente manera.
Suponer que converge a . Se dice que la secuencia converge R-linealmente a si existe una secuencia tal que
y converge Q-linealmente a cero. [3] El prefijo "R-" significa "raíz". [6] : 620
Ejemplos de
Considere la secuencia
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,
Por lo tanto, encontramos que converge Q-linealmente y tiene una tasa de convergencia de . De manera más general, para cualquier, la secuencia converge linealmente con la tasa .
La secuencia
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 quees la función de piso , que da el entero más grande que es menor o igual que.)
La secuencia
converge superlinealmente. De hecho, es cuadráticamente convergente.
Finalmente, la secuencia
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, una secuencia se dice que converge a L con orden q si existe una constante C tal que
Esto está escrito como usando la notación O grande .
É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 . [ 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 y calcular los errores resultantes y . Luego, el orden de convergencia se aproxima mediante la siguiente fórmula:
- [ cita requerida ]
Ejemplos (continuación)
La secuencia con fue presentado arriba. Esta secuencia converge con el orden 1 según la convención para métodos de discretización. [ ¿por qué? ]
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. [ ¿por qué? ]
El orden de convergencia de un método de discretización está relacionado con su error de truncamiento global (GTE) . [ ¿cómo? ]
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
- ↑ Ruye, Wang (12 de febrero de 2015). "Orden y tasa de convergencia" . hmc.edu . Consultado el 31 de julio de 2020 .
- ^ Senning, Jonathan R. "Computación y estimación de la tasa de convergencia" (PDF) . gordon.edu . Consultado el 7 de agosto de 2020 .
- ^ a b Bockelman, Brian (2005). "Tasas de convergencia" . math.unl.edu . Consultado el 31 de julio de 2020 .
- ^ 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 .
- ^ Porta, FA (1989). "Sobre el orden Q y el orden R de convergencia" (PDF) . Revista de teoría y aplicaciones de la optimización . 63 (3): 415–431. doi : 10.1007 / BF00939805 . S2CID 116192710 . Consultado el 31 de julio de 2020 .
- ^ a b Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica (2ª ed.). Berlín, Nueva York: Springer-Verlag . ISBN 978-0-387-30303-1.
- ^ Senning, Jonathan R. "Computación y estimación de la tasa de convergencia" (PDF) . gordon.edu . Consultado el 7 de agosto de 2020 .
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..