Sobrerrelajación successiva

Erro al crear miniatura:

Ràdio espectral $\rho (C_{\omega })$ de la matriu de iteración $C_{\omega }$ del método SOR, per a distints valors de $\omega$. Els distints traços corresponen a distints valors del radi espectral de la corresponent matriu de Jacobi: $\mu :=\rho (C_{\text{Jac}})$

En àlgebra llineal numèrica, el método de sobre-relaixació successiva (SOR), és una variant del método de Gauss-Seidel per a estimar la solució d'un sistema llineal d'equacions, permetent una convergència més ràpida.

Va ser propost simultàneament per David M. Young Jr. i Stanley P. Frankel en 1950, en el propòsit de resoldre sistemes llineals en ordenadors digitals. Anteriorment ya existien métodos de tipo sobre-relaixació, com el método de Lewis Fry Richardson, i els métodos desenrollats per R. V. Southwell. No obstant, estos últims estaven dissenyats per a ser utilisats per calculadores humanes, requerint alguna perícia per a assegurar convergència a la solució, lo que els feya inaplicables per a ordenadors digitals. Es poden trobar detalls d'estos aspectes en la tesis de David M. Young Jr.

Formulació matricial

Es considera un sistema llineal quadrat, de $n$ equacions, en variable desconeguda $𝐱$:

$$A𝐱=𝐛,A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right],𝐱=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right],𝐛=\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_n\end{array}\right].$$

La matriu As pot escriure com la suma de: el seu component diagonal $D$, i els seus components estrictament triangular inferior i superior, $L$ i $U$ respectivament: $A=D+L+U;$ on:

$$D=\left[\begin{array}{cccc}{a}_{11}& 0& \cdots & 0\\ 0& a_{22}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & a_{nn}\end{array}\right],L=\left[\begin{array}{cccc}0& 0& \cdots & 0\\ a_{21}& 0& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & 0\end{array}\right],U=\left[\begin{array}{cccc}0& a_{12}& \cdots & a_{1n}\\ 0& 0& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 0\end{array}\right].$$

D'esta forma, el sistema d'equacions llineals pot ser escrit com:$$(D+\omega L)𝐱=\omega 𝐛-[\omega U+(\omega -1)D]𝐱;$$per a qualsevol constant $\omega >1$, denominada factor de relaixació. El método SOR és una tècnica iterativa que en cada iteración "rebuja" $x$ del costat esquerre d'esta igualtat, utilisant el valor de $x$ del pas anterior en el costat dret. Analíticament, açò pot ser escrit com:$${𝐱}^{(k+1)}=(D+\omega L{)}^{-1}(-[\omega U+(\omega -1)D]{𝐱}^{(k)}+\omega 𝐛)=C_{\omega }{𝐱}^{(k)}+𝐜;$$on ${𝐱}^{(k)}$ és la k-ésima aproximació de $𝐱$, i ${𝐱}^{(k+1)}$ és la nova estimació que es vol determinar. Com es pot vore, la matriu de iteración del método és:$$C_{\omega }=-(D+\omega L{)}^{-1}(\omega U+(\omega -1)D).$$

Formulació per coordenades

En la pràctica s'evita trobar l'inversa de forma explícita en aplicar SOR. En el seu lloc es pot resoldre el sistema d'equacions llineals que s'obté en multiplicar cada costat de la iteración per $(D+\omega L)$ a l'esquerra:

$$(D+\omega L){𝐱}^{(k+1)}=-[\omega U+(\omega -1)D]{𝐱}^{(k)}+\omega 𝐛;$$

Ya que la matriu $(D+\omega L)$ és triangular inferior, es pot trobar $x^{(k+1)}$ per mig de substitució cap a avant. D'esta forma s'obté una expressió per a cada coordenada de l'estimació $x^{(k+1)}$:

$$x_i^{(k+1)}=(1-\omega )x_i^{(k)}+\frac{\omega }{a_{ii}}(b_i-\sum _{j<i}{a}_{ij}{x}_j^{(k+1)}-\sum _{j>i}{a}_{ij}{x}_j^{(k)}),i=1,2,\dots ,n.$$

Vore també

• Método de Jacobi
• Método de Gauss-Seidel
• Sobre-relaixació successiva simètrica (SSOR)