Sobre-relajación sucesiva simétrica (SSOR)

Se quiere resolver un sistema lineal de la forma: ${\displaystyle Ax=b}$. La matriz ${\displaystyle A}$ se descompone en la suma de su forma diagonal ${\displaystyle D}$, triangular inferior ${\displaystyle L}$ y triangular superior ${\displaystyle U}$:

$${\displaystyle A=L+D+U}$$

El método SSOR se obtiene aplicando una iteración de sobre-relajación sucesiva (SOR):

$${\displaystyle \mathbf {x} ^{(k+{\frac {1}{2}})}=-(D+\omega L)^{-1}{\big (}\omega U+(\omega -1)D{\big )}\mathbf {x} ^{(k)}+\omega (D+\omega L)^{-1}\mathbf {b} ,}$$

seguida de una iteración de SOR hacia atrás (se intercambia ${\displaystyle L}$ por ${\displaystyle U}$):

$${\displaystyle \mathbf {x} ^{(k+1)}=-(D+\omega U)^{-1}{\big (}\omega L+(\omega -1)D{\big )}\mathbf {x} ^{(k+{\frac {1}{2}})}+\omega (D+\omega U)^{-1}\mathbf {b} .}$$

Juntando ambas iteraciones en un solo paso vectorial, se obtiene la matriz de iteración de SSOR:[2]

$${\displaystyle Q=(D+\omega U)^{-1}{\big (}\omega L+(\omega -1)D{\big )}(D+\omega L)^{-1}{\big (}\omega U+(\omega -1)D{\big )}}$$

El vector del método se puede escribir como:

$${\displaystyle c=\omega (2-\omega )(D+\omega U)^{-1}D(D+\omega L)^{-1}b=\left({\frac {1}{\omega (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U)\right)^{-1}b.}$$

La iteración de SSOR se puede escribir de forma alternativa como:[2]

$${\displaystyle x^{(k+1)}=M^{-1}{\big (}M-A{\big )}x^{(k)}+M^{-1}b=x^{(k)}-M^{-1}Ax^{(k)}+M^{-1}b,}$$

para cierta matriz ${\displaystyle M}$ invertible. En el caso de SSOR la matriz es:[2]

$${\displaystyle M={\frac {1}{w(2-w)}}(D+wL)D^{-1}(D+wU)}$$

La iteración anterior se puede ver como un método de punto fijo, utilizado para resolver el sistema lineal:

$${\displaystyle M^{-1}Ax=M^{-1}b.}$$

Este último sistema se denomina sistema preocondicionado, donde la matriz ${\displaystyle M}$ es el precondicionador. El sistema precondicionado es equivalente al original, en cuanto a que tiene las mismas soluciones. Se busca seleccionar ${\displaystyle M}$ de forma que el sistema precondicionado sea más sencillo de resolver que el original.

Utilizar SSOR como precondicionador consiste en tomar como matriz de precondición la matriz ${\displaystyle M}$ de SSOR. Luego se aplica otro método iterativo para resolver el sistema precondicionado por la matriz de SSOR.

En el caso particular en que ${\displaystyle A}$ es simétrica, se tiene: ${\displaystyle U=L^{T}}$. Por lo tanto la matriz de precondición de SSOR también resulta simétrica:

$${\displaystyle M={\frac {1}{w(2-w)}}(D+wL)D^{-1}(D+wL)^{T}}$$

El hecho de que ${\displaystyle M}$ sea simétrica, permite utilizarla como precondicionador en métodos iterativos como gradiente conjugado.

• Sobre-relajación sucesiva