Sobrerrelajación sucesiva
En álgebra lineal numérica, el método de sobre-relajación sucesiva (SOR), es una variante del método de Gauss-Seidel para estimar la solución de un sistema lineal de ecuaciones, permitiendo una convergencia más rápida.
Fue propuesto simultáneamente por David M. Young Jr.
y Stanley P. Frankel en 1950, con el propósito de resolver sistemas lineales en ordenadores digitales.
Anteriormente ya existían métodos de tipo sobre-relajación, como el método de Lewis Fry Richardson, y los métodos desarrollados por R. V. Southwell.
Sin embargo, estos últimos estaban diseñados para ser utilizados por calculadoras humanas, requiriendo alguna pericia para asegurar convergencia a la solución, lo que los hacía inaplicables para ordenadores digitales.
Se pueden encontrar detalles de estos aspectos en la tesis de David M. Young Jr.
[1] Se considera un sistema lineal cuadrado, de
: La matriz A se puede escribir como la suma de: su componente diagonal
, denominada factor de relajación.
del paso anterior en el lado derecho.
es la nueva estimación que se quiere determinar.
Como se puede ver, la matriz de iteración del método es:
En la práctica se evita hallar la inversa de forma explícita al aplicar SOR.
En su lugar se puede resolver el sistema de ecuaciones lineales que se obtiene al multiplicar cada lado de la iteración por
es triangular inferior, se puede hallar
, la estimación de SOR es una combinación convexa de la estimación SOR del paso anterior, y la estimación que se obtendría aplicando un paso de Gauss-Seidel a la estimación SOR del paso anterior:
[2] En general esta condición no es suficiente para asegurar la convergencia, aunque sí lo es para cierto tipo de matrices.
es simétrica y definida positiva, el método SOR converge si y solo si
de forma que el método no solo sea convergente, sino que logre la convergencia lo más rápido posible.
con el que se logra la mejor tasa de convergencia se denomina factor de relajación óptimo, y se denota
Esta tasa o velocidad de convergencia viene dada por el recíproco del radio espectral
Bajo ciertas hipótesis, es posible obtener una expresión analítica para el radio espectral
donde éste se minimiza (mayor tasa de convergencia).
Supongamos en particular que se cumplen las siguientes hipótesis:[3][4] Entonces el radio espectral de la matriz de iteración de SOR puede ser expresado como: donde el parámetro de relajación óptimo que minimiza el radio espectral es En particular, para
La última hipótesis se satisface para matrices tridiagonales, pues
Dado que las estimaciones del algoritmo pueden ser sobre-escritas cuando están siendo computadas, la implementación del algoritmo requiere un único vector de almacenamiento en cada iteración.
Por lo tanto, en el siguiente pseudo-código se omite la indexación de cada vector.
: Para estimar su solución se aplica SOR con un factor de relajación
El método converge a la solución exacta (3, −2, 2, 1).
Una implementación en Python del pseudo-código proporcionado más arriba es:
