Comprender la "tasa de convergencia" para los métodos iterativos

Según Wikipedia, la tasa de convergencia se expresa como una relación específica de las normas vectoriales. Estoy tratando de entender la diferencia entre las tasas "lineales" y "cuadráticas", en diferentes puntos de tiempo (básicamente, "al comienzo" de la iteración y "al final"). ¿Podría decirse que:

• con convergencia lineal, la norma del error de la iteración está limitada por x k + 1 ‖ e k$e_{k+1}$$x_{k+1}$$\|e_k\|$

• con convergencia cuadrática, la norma del error $e_{k+1}$ de la iteración $x_{k+1}$ está limitada por $\|e_k\|^2$

Dicha interpretación significaría que, con unos pocos (pequeño número de) iteraciones del algoritmo A1 linealmente convergente (se supone una inicialización aleatoria), se lograría un error menor que con unas pocas iteraciones del algoritmo A2 cuadráticamente convergente. Sin embargo, dado que el error disminuye y debido a la cuadratura, las iteraciones posteriores significarían un error menor con A2.

¿Es válida la interpretación anterior? Tenga en cuenta que no tiene en cuenta el coeficiente de velocidad $\lambda$ .

En la práctica, sí. Si bien todavía es grande, el coeficiente de tasa λ dominará el error en lugar de la tasa q. (Tenga en cuenta que estas son tasas asintóticas , por lo que las declaraciones a las que se vinculó solo se mantienen para el límite como k → ∞ ).$e_k$$\lambda$$k\to\infty$

Por ejemplo, para los métodos de primer orden en la optimización, a menudo observa una disminución inicial rápida del error, que luego se nivela. Por otro lado, para el método de Newton, puede pasar un tiempo antes de que la convergencia superlineal (o cuadrática) entre en acción (después de todo, solo es localmente superlinealmente convergente). Por esa razón, es común comenzar con unos pocos pasos de gradiente para comenzar antes de cambiar a un método de Newton, o usar métodos de homotopía o cuasi-Newton que se comportan como métodos de primer orden inicialmente y se convierten en un método de Newton al acercarse a objetivo.

$e_{k+1} \le \lambda_1 e_k$$\lambda_1<1$$e_{k+1} \le \lambda_2 e_k^2$$\lambda_2$$\lambda_2 e_1<1$- es decir, que su suposición inicial está lo suficientemente cerca. Este es un comportamiento comúnmente observado: que los algoritmos convergentes cuadráticamente deben iniciarse "lo suficientemente cerca" de la solución para converger, mientras que los algoritmos linealmente convergentes suelen ser más robustos. Esta es otra razón por la que a menudo se comienzan con unos pocos pasos de un algoritmo de convergencia lineal (por ejemplo, el método de descenso más pronunciado) antes de cambiar a otros más eficientes (por ejemplo, el método de Newton).

La interpretación es cualitativamente correcta.

Tenga en cuenta que la convergencia lineal y cuadrática es con respecto al peor de los casos, la situación en un algoritmo particular puede ser mejor que la que obtiene del análisis de peor caso dado por Wolfgang Bangerth, aunque la situación cualitativa generalmente corresponde a este análisis.

En algoritmos concretos (p. Ej., En la optimización), a menudo tiene sentido iterar primero con un método económico pero solo linealmente convergente hasta que el progreso sea lento, y luego terminar con un método convergente cuadráticamente (o al menos superlinealmente). En la práctica, la convergencia superlineal tiende a ser tan buena como la convergencia cuadrática solo porque la parte inicial, que converge lentamente, tiende a dominar el trabajo general.