Relajación excesiva 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 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 ser computados por calculadoras humanas , requiriendo cierta experiencia para asegurar la convergencia a la solución, lo que los hizo inaplicables para la programación en computadoras digitales. Estos aspectos se discuten en la tesis de David M. Young Jr. [1]
Entonces A puede descomponerse en un componente diagonal D , y componentes triangulares estrictamente inferior y superior L y U :
El método de sobre-relajación sucesiva es una técnica iterativa que resuelve el lado izquierdo de esta expresión para x , utilizando 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 usando sustitución hacia adelante :
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 positivo-definido, 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 una convergencia.
