Métodos Estacionarios y de Relajación

Los métodos iterativos estacionarios resuelven un sistema lineal dividiendo la matriz y aplicando repetidamente una regla de actualización fija; los esquemas clásicos de Jacobi, Gauss-Seidel y de sobrerrelajación sucesiva son los ejemplos fundamentales.

Definition

Un método iterativo estacionario es aquel cuya actualización aplica la misma matriz de iteración en cada paso, derivada de una división de la matriz de coeficientes en una parte fácilmente invertible y un resto; la convergencia se rige por el radio espectral de la matriz de iteración resultante.

Scope

Este tema cubre el marco de división de matrices, las iteraciones de Jacobi y Gauss-Seidel, la sobrerrelajación sucesiva y la elección del parámetro de relajación óptimo, el criterio del radio espectral para la convergencia, y el papel que estas iteraciones simples desempeñan hoy en día como suavizadores dentro de la multigrid y como precondicionadores.

Core questions

• ¿Cómo la división de la matriz produce una iteración de punto fijo para el sistema lineal?
• ¿En qué se diferencian los métodos de Jacobi y Gauss-Seidel, y por qué Gauss-Seidel suele ser más rápido?
• ¿Cómo acelera la sobrerrelajación la convergencia y cómo se elige el parámetro óptimo?
• ¿Bajo qué condiciones de la matriz convergen estas iteraciones?

Key theories

División de matrices y el criterio del radio espectral

Escribir la matriz como una parte fácilmente invertible menos un resto define una iteración estacionaria cuyo error se multiplica por una matriz de iteración en cada paso; la iteración converge para cada estimación inicial si y solo si el radio espectral de esa matriz de iteración es menor que uno.

Sobrerralajación sucesiva

Al exceder la corrección de Gauss-Seidel con un factor de relajación, la sobrerrelajación sucesiva puede reducir en gran medida el radio espectral; para ciertas matrices estructuradas, se conoce analíticamente un parámetro de relajación óptimo que produce una aceleración drástica.

Mechanisms

El método de Jacobi actualiza cada incógnita simultáneamente utilizando solo valores del barrido anterior, lo que equivale a separar la diagonal. Gauss-Seidel utiliza los valores actualizados más recientemente dentro del mismo barrido, separando la parte triangular inferior, lo que generalmente converge más rápido. La sobrerrelajación sucesiva forma un promedio ponderado del valor antiguo y la actualización de Gauss-Seidel gobernado por un parámetro de relajación; elegir este parámetro mayor que uno acelera la convergencia para matrices adecuadas. La convergencia para los tres métodos está garantizada para clases como matrices estrictamente diagonalmente dominantes o simétricas definidas positivas, y se cuantifica por el radio espectral de la matriz de iteración.

Clinical relevance

Aunque suelen ser demasiado lentos para ser solucionadores competitivos por sí solos para sistemas grandes, los métodos estacionarios siguen siendo importantes como suavizadores en el corazón de la multigrid, como precondicionadores simples para los métodos de Krylov, y como bloques de construcción fácilmente paralelizable; Gauss-Seidel y Jacobi ponderado en particular son omnipresentes dentro de los solucionadores multinivel modernos.

History

Las iteraciones de Jacobi y Gauss-Seidel datan del siglo XIX, mientras que la sobrerrelajación sucesiva y su rigurosa teoría de convergencia fueron desarrolladas por David Young y Richard Varga en la década de 1950; aunque más tarde eclipsadas por los métodos de Krylov y multigrid como solucionadores primarios, estas iteraciones fueron revividas como componentes esenciales de esquemas multinivel y precondicionados.

Key figures

• Carl Friedrich Gauss
• Philipp Ludwig von Seidel
• David M. Young
• Richard S. Varga

Seminal works

• saad2003
• varga2000

Frequently asked questions

¿Por qué Gauss-Seidel suele ser más rápido que Jacobi?

Gauss-Seidel utiliza inmediatamente los valores actualizados dentro del mismo barrido, por lo que la información se propaga más rápido a través de las incógnitas, lo que generalmente reduce a la mitad el número de iteraciones en comparación con Jacobi, que utiliza solo valores del barrido anterior.

Si estos métodos son lentos, ¿por qué se siguen estudiando?

Son excelentes suavizadores y precondicionadores simples. Dentro de la multigrid, unas pocas pasadas de Gauss-Seidel o Jacobi ponderado eliminan eficientemente el error oscilatorio, que es exactamente el papel que necesita la multigrid, por lo que estas iteraciones clásicas perduran como componentes de los solucionadores modernos rápidos.