Ver el código de «Sobre-relajación sucesiva simétrica (SSOR)»


En [[análisis numérico]], el método de [[Sobrerrelajación sucesiva|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:

<math display="block">x^{(k+1)}=Qx^{(k)}+c.</math>

Su velocidad de convergencia, dada por el [[radio espectral]] de <math>Q</math>, suele ser inferior a la de SOR.<ref>{{Cita publicación|url=http://dx.doi.org/10.1016/c2013-0-11733-3|título=Iterative Solution of Large Linear Systems|apellidos=Young|nombre=David M.|fecha=1971|publicación=|fechaacceso=2020-11-21|doi=10.1016/c2013-0-11733-3|pmid=}}</ref> 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: <math>Ax=b</math>. La matriz <math>A</math> se descompone en la suma de su forma diagonal <math>D</math>, triangular inferior <math>L</math> y triangular superior <math>U</math>:

<math display="block">A = L+D+U</math>

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

<math display="block">\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},</math>

seguida de una iteración de SOR hacia atrás (se intercambia <math>L</math> por <math>U</math>):

<math display="block">\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}.</math>
Juntando ambas iteraciones en un solo paso vectorial, se obtiene la matriz de iteración de SSOR:<ref name=":0">{{Cita libro|título=Iterative Methods for Sparse Linear Systems|url=https://epubs.siam.org/doi/book/10.1137/1.9780898718003|editorial=Society for Industrial and Applied Mathematics|fecha=2003-01-01|fechaacceso=2020-11-20|isbn=978-0-89871-534-7|serie=Other Titles in Applied Mathematics|doi=10.1137/1.9780898718003|nombre=Yousef|apellidos=Saad}}</ref>
<math display="block">Q = (D+\omega U)^{-1} \big( \omega L + (\omega-1) D \big) (D+\omega L)^{-1} \big( \omega U + (\omega-1) D \big) </math>

El vector del método se puede escribir como:
<math display="block">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. </math>

== Uso como precondicionador ==
La iteración de SSOR se puede escribir de forma alternativa como:<ref name=":0" />

<math display="block">x^{(k+1)} = M^{-1} \big( M-A \big) x^{(k)} + M^{-1} b  = x^{(k)} - M^{-1}A x^{(k)} + M^{-1} b,</math>

para cierta matriz <math>M</math> invertible. En el caso de SSOR la matriz es:<ref name=":0" /><math display="block">M = \frac{1}{w(2-w)} (D+wL) D^{-1} (D+wU)</math>La iteración anterior se puede ver como un método de punto fijo, utilizado para resolver el sistema lineal: 

<math display="block">M^{-1}A x = M^{-1} b.</math>

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

<math display="block">M = \frac{1}{w(2-w)} (D+wL) D^{-1} (D+wL)^{T}</math>El hecho de que <math>M</math> sea simétrica, permite utilizarla como precondicionador en métodos iterativos como [[Método del gradiente conjugado|gradiente conjugado]].

== Véase también ==

* [[Sobrerrelajación sucesiva|Sobre-relajación sucesiva]]

== Referencias ==
{{listaref}}

{{Control de autoridades}}
[[Categoría:Álgebra lineal numérica]]