Sobre-relajación sucesiva
En álgebra lineal numérica , el método de relajación excesiva sucesiva ( SOR ) es una variante del método de Gauss-Seidel para resolver un sistema lineal de ecuaciones , lo que resulta en una convergencia más rápida. Se puede utilizar un método similar para cualquier proceso iterativo de convergencia lenta .
Fue ideado simultáneamente por David M. Young Jr. y por Stanley P. Frankel en 1950 con el propósito de resolver automáticamente sistemas lineales en computadoras digitales. Los métodos de relajación excesiva se habían utilizado antes del trabajo de Young y Frankel. Un ejemplo es el método de Lewis Fry Richardson y los métodos desarrollados por RV Southwell . Sin embargo, estos métodos fueron diseñados para el cálculo por calculadoras humanas , lo que requiere cierta experiencia para garantizar la convergencia a la solución que los hizo inaplicables para la programación en computadoras digitales. Estos aspectos son discutidos en la tesis de David M. Young Jr. [1]
Entonces A se puede descomponer en un componente diagonal D , y componentes triangulares estrictamente inferior y superior L y U :
El método de relajación excesiva sucesiva es una técnica iterativa que resuelve el lado izquierdo de esta expresión para x , usando el valor anterior para x en el lado derecho. Analíticamente, esto se puede escribir como:
donde es la k -ésima aproximación o iteración de y es la siguiente o k + 1 iteración de . Sin embargo, al aprovechar la forma triangular de ( D + ωL ), los elementos de x ( k +1) se pueden calcular secuencialmente mediante la sustitución directa :
La elección del factor de relajación ω no es necesariamente fácil y depende de las propiedades de la matriz de coeficientes. En 1947, Ostrowski demostró que si es simétrico y definido positivo entonces para . Por lo tanto, sigue la convergencia del proceso de iteración, pero generalmente estamos interesados en una convergencia más rápida en lugar de solo convergencia.
