Méthode de surrelaxation successive

En analyse numérique, la méthode de surrelaxation successive (en anglais : Successive Overrelaxation Method, abrégée en SOR) est une variante de la méthode de Gauss-Seidel pour résoudre un système d'équations linéaires. La convergence de cet algorithme est généralement plus rapide. Une approche similaire peut être appliquée à bon nombre de méthodes itératives.

Selon David Kincaid^[1], cette méthode aurait été découverte simultanément par David M. Young, Jr. (en) et Stan Frankel en 1950 dans le but de résoudre automatiquement des systèmes linéaires avec des ordinateurs ; mais les méthodes de surrelaxations étaient déjà utilisées auparavant : qu'il suffise de citer la méthode de Lewis Fry Richardson ou la méthode de R. V. Southwell (1946). Ces méthodes étaient conçues pour le calcul à la main et requéraient une expertise certaine afin d'assurer la convergence. Ces méthodes ne pouvaient être retranscrites sur ordinateur. Ces limitations ont été discutées dans la thèse de David Young^[2]

On considère un système linéaire de n équations avec n inconnues notées x (qui est un vecteur) :

${\displaystyle A\mathbf {x} =\mathbf {b} }$

où :

${\displaystyle A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}},\qquad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\qquad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{bmatrix}}.}$

A étant la somme d'une matrice diagonale notée D et de deux matrices triangulaires (respectivement inférieure et supérieure) notées L et U :

${\displaystyle A=D+L+U\qquad {\text{avec}}\quad D={\begin{bmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{bmatrix}},\quad L={\begin{bmatrix}0&0&\cdots &0\\a_{21}&0&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &0\end{bmatrix}},\quad U={\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\0&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &0\end{bmatrix}},}$

le système d'équations linéaires peut être reformulé par :

${\displaystyle (D+\omega L)\mathbf {x} =\omega \mathbf {b} -[\omega U+(\omega -1)D]\mathbf {x} }$

pour tout ω > 0.

La méthode de surrelaxation successive est une méthode itérative initialisée par le choix d'un ${\displaystyle x_{0}}$ arbitraire, et où chaque itération consiste à déterminer ${\displaystyle x_{k+1}}$ à l'aide de ${\displaystyle x_{k}}$ selon la formule suivante :

${\displaystyle (D+\omega L)\mathbf {x_{k+1}} =\omega \mathbf {b} -[\omega U+(\omega -1)D]\mathbf {x_{k}} }$

La matrice de gauche (D+ωL) étant triangulaire, il est aisé de calculer ${\displaystyle x_{k+1}}$ par :

${\displaystyle x_{i}^{(k+1)}=(1-\omega )x_{i}^{(k)}+{\frac {\omega }{a_{ii}}}\left(b_{i}-\sum _{j>i}a_{ij}x_{j}^{(k)}-\sum _{j<i}a_{ij}x_{j}^{(k+1)}\right),\quad i=1,2,\ldots ,n.}$

Le choix du facteur de relaxation n'est pas trivial et dépend des coefficients de la matrice. Pour une matrice définie positive, on peut démontrer que l'algorithme est convergent pour tout ${\displaystyle \omega \in ]0,2[}$. Toutefois, on veut une convergence aussi rapide que possible. Notons que pour un facteur de relaxation de 1, on tombe sur la méthode de Gauss-Seidel

Entrée: A, b, ω
Sortie: ${\displaystyle \phi }$

On choisit une solution initiale arbitraire ${\displaystyle \phi ^{(0)}}$. Répéter jusqu'à convergence

Boucler i de 1 à n

${\displaystyle \sigma \leftarrow 0}$

Boucler j de 1 à i − 1

${\displaystyle \sigma \leftarrow \sigma +a_{ij}\phi _{j}^{(k+1)}}$

Fin (boucle j)

Boucler j de i + 1 à n

${\displaystyle \sigma \leftarrow \sigma +a_{ij}\phi _{j}^{(k)}}$

Fin (boucle j)

${\displaystyle \phi _{i}^{(k+1)}\leftarrow (1-\omega )\phi _{i}^{(k)}+{\frac {\omega }{a_{ii}}}(b_{i}-\sigma )}$

Fin (boucle i)

Vérifier la convergence.

Fin (boucle répétition)

Note:
${\displaystyle (1-\omega )\phi _{i}^{(k)}+{\frac {\omega }{a_{ii}}}(b_{i}-\sigma )}$ peut aussi être écrit ${\displaystyle \phi _{i}^{(k)}+\omega \left({\frac {b_{i}-\sigma }{a_{ii}}}-\phi _{i}^{(k)}\right)}$. Ceci économise une multiplication à chaque itération.

Une technique similaire peut être utilisée pour toute méthode itérative. On suppose que l'itération peut être écrite sous la forme :

${\displaystyle x_{n+1}=f(x_{n})}$

alors la méthode modifiée devient :

${\displaystyle x_{n+1}^{\mathrm {SOR} }=(1-\omega )x_{n}^{\mathrm {SOR} }+\omega f(x_{n}^{\mathrm {SOR} })}$

ou de manière équivalente :

${\displaystyle x_{n}=\omega x_{n-1}+(1-\omega )x_{n-2},\quad \omega <1}$

En pratique, le choix ${\displaystyle \omega >1}$ est utilisé pour accélérer la convergence tandis que le choix ${\displaystyle \omega <1}$ est souvent utilisé pour faire converger un processus divergent.

Il existe de nombreuses méthodes pour décider de la valeur à donner au paramètre ${\displaystyle \omega }$, basées sur le comportement de l'algorithme. En principe ces méthodes permettent d'avoir une convergence superlinéaire dans beaucoup de cas, mais elles peuvent échouer dans certains cas.

• Méthode de Jacobi
• Méthode de Gauss-Seidel

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Successive over-relaxation » (voir la liste des auteurs).
• Superrelaxation successive - SOR sur cfd-online
• (en) Black, Noel and Moore, Shirley, « Successive Overrelaxation Method », sur MathWorld
• (en) Yousef Saad, Iterative Methods for Sparse Linear Systems, 1st edition, PWS, 1996
• (en) Templates for the Solution of Linear Systems par Jack Dongarra sur netlib

• (en) Eric W. Weisstein, « Successive Overrelaxation Method », sur MathWorld
• (en) Module for the SOR Method

• Portail de l’algèbre
• Portail de l'informatique théorique