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

En análisis numérico, el método de sobre-relajación sucesiva simétrica (SSOR), es un método iterativo que permite estimar soluciones de un sistema de ecuaciones lineales. También puede ser utilizado como precondicionador para otros métodos iterativos.

SSOR es un método iterativo de tipo estacionario, por lo que cada iteración es de la forma:

$x^{(k+1)}=Qx^{(k)}+c.$

Su velocidad de convergencia, dada por el radio espectral de $Q$ , suele ser inferior a la de SOR.^[1] Esto hace que la mayor utilidad de SSOR sea como precondicionador de otros métodos iterativos.

Deducción del método

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

$A=L+D+U$

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

$\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 $L$ por $U$ ):

$\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] $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: $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.$

Uso como precondicionador

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

$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 $M$ invertible. En el caso de SSOR la matriz es:^[2] $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:

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

Este último sistema se denomina sistema preocondicionado, donde la matriz $M$ es el precondicionador. El sistema precondicionado es equivalente al original, en cuanto a que tiene las mismas soluciones. Se busca seleccionar $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 $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 $A$ es simétrica, se tiene: $U=L^{T}$ . Por lo tanto la matriz de precondición de SSOR también resulta simétrica:

$M={\frac {1}{w(2-w)}}(D+wL)D^{-1}(D+wL)^{T}$ El hecho de que $M$ sea simétrica, permite utilizarla como precondicionador en métodos iterativos como gradiente conjugado.