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.

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^[1]

Formulation

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

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

où :

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 :

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 :

(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 $x_{0}$ arbitraire, et où chaque itération consiste à déterminer $x_{k+1}$ à l'aide de $x_{k}$ selon la formule suivante :

(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 $x_{k+1}$ par :

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 $\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

Algorithme

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

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

Boucler i de 1 à n

\sigma \leftarrow 0

Boucler j de 1 à i − 1

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

Fin (boucle j)

Boucler j de i + 1 à n

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

Fin (boucle j)

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

Autre applications de la méthode

Article principal : extrapolation de Richardson.

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 :

x_{n+1}=f(x_{n})

alors la méthode modifiée devient :

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

ou de manière équivalente :

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

En pratique, le choix $\omega >1$ est utilisé pour accélérer la convergence tandis que le choix $\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 $\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.

Voir aussi

Notes

↑ David M. Young, Iterative methods for solving partial difference equations of elliptical type, vol. PhD thesis, Harvard University, 1^er mai 1950 (lire en ligne)

Références

(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

Liens externes

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

[1] David M. Young, Iterative methods for solving partial difference equations of elliptical type, vol. PhD thesis, Harvard University, 1^er mai 1950 (lire en ligne)

[1]