Voir la source de Méthode de surrelaxation successive

En [[analyse numérique]], la méthode de '''surrelaxation successive''' (en anglais : ''{{lang|en|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éthode itérative|méthodes itératives]].

Cette méthode aurait été découverte simultanément par {{Lien|fr=David M. Young, Jr.|lang=en}} et [[Stan Frankel]] en 1950 dans le but de résoudre automatiquement des systèmes linéaires avec des [[ordinateur]]s ; 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 [[Richard V. Southwell|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 numérique|convergence]]. Ces méthodes ne pouvaient être retranscrites sur ordinateur. Ces limitations ont été discutées dans la thèse de David Young<ref>{{ouvrage
 |nom1=Young 
 |prénom1=David M. 
 |titre=Iterative methods for solving partial difference equations of elliptical type
 |url=http://www.ma.utexas.edu/CNA/DMY/david_young_thesis.pdf
 |jour = 1
 |mois=May
 |année=1950
 |volume=PhD thesis, Harvard University
}}</ref>

== Formulation ==
On considère un système linéaire de ''n'' équations avec ''n'' inconnues notées '''x''' (qui est un [[vecteur]]) :
:<math>A\mathbf x = \mathbf b</math>

où :
:<math>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}.</math>

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

:<math>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} ,</math>

le système d'équations linéaires peut être reformulé par :
:<math>(D+\omega L) \mathbf{x} = \omega \mathbf{b} - [\omega U + (\omega-1) D ] \mathbf{x} </math>
pour tout ''ω'' > 0.

La méthode de surrelaxation successive est une méthode itérative initialisée par le choix d'un <math>x_0</math> arbitraire, et où chaque [[itération]] consiste à déterminer <math>x_{k+1}</math> à l'aide de <math>x_k</math> selon la formule suivante :
:<math>(D+\omega L) \mathbf{x_{k+1}} = \omega \mathbf{b} - [\omega U + (\omega-1) D ] \mathbf{x_k} </math>

La matrice de gauche (''D''+''ωL'') étant triangulaire, il est aisé de calculer <math>x_{k+1}</math> par :
:<math> x^{(k+1)}_i  = (1-\omega)x^{(k)}_i + \frac{\omega}{a_{ii}} \left(b_i - \sum_{j>i} a_{ij}x^{(k)}_j - \sum_{j<i} a_{ij}x^{(k+1)}_j \right),\quad i=1,2,\ldots,n. </math>

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 <math> \omega \in ]0,2[ </math>. 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'', ω <br />
Sortie: <math>\phi</math>

On choisit une solution initiale arbitraire <math>\phi^{(0)}</math>.
'''Répéter''' jusqu'à convergence
:'''Boucler''' ''i'' '''de''' 1 '''à''' ''n''
::<math>\sigma \leftarrow 0</math>
::'''Boucler''' ''j'' '''de''' 1 '''à''' ''i'' − 1
:::<math> \sigma \leftarrow \sigma + a_{ij} \phi_j^{(k+1)} </math>
::'''Fin''' (boucle ''j'')
::'''Boucler''' ''j'' '''de''' ''i'' + 1 '''à''' ''n''
:::<math> \sigma \leftarrow \sigma + a_{ij} \phi_j^{(k)} </math>
::'''Fin''' (boucle ''j'')
::<math> \phi_i^{(k+1)} \leftarrow (1-\omega)\phi_i^{(k)} + \frac{\omega}{a_{ii}} (b_i - \sigma)</math>
:'''Fin''' (boucle ''i'')
:Vérifier la convergence.
'''Fin''' (boucle répétition)

'''Note:'''<br /> <math>(1-\omega)\phi_i^{(k)} + \frac{\omega}{a_{ii}} (b_i - \sigma)</math> peut aussi être écrit <math>\phi_i^{(k)} + \omega \left( \frac{b_i - \sigma}{a_{ii}} - \phi_i^{(k)}\right)</math>. 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 :
:<math>x_{n+1}=f(x_n)</math>

alors la méthode modifiée devient :
:<math>x^\mathrm{SOR}_{n+1}=(1-\omega)x^{\mathrm{SOR}}_n+\omega f(x^\mathrm{SOR}_n)</math>

ou de manière équivalente :
:<math>x_{n}=\omega x_{n-1} + (1-\omega)x_{n-2},\quad \omega<1</math>
En pratique, le choix <math>\omega>1</math> est utilisé pour accélérer la convergence tandis que le choix <math>\omega<1</math> 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 <math>\omega</math>, 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 ==

* [[Méthode de Jacobi]]
* [[Méthode de Gauss-Seidel]]

== Notes ==
{{références}}

== Références ==
{{Traduction/Référence|en|Successive over-relaxation|312835957}}
* [http://www.cfd-online.com/Wiki/Successive_over-relaxation_method_-_SOR Superrelaxation successive - SOR] sur cfd-online
* {{MathWorld|nom_url=SuccessiveOverrelaxationMethod|titre=Successive Overrelaxation Method|auteur=Black, Noel and Moore, Shirley}}
* {{en}} [[Yousef Saad]], ''[http://www-users.cs.umn.edu/%7Esaad/books.html Iterative Methods for Sparse Linear Systems]'', {{1st}} edition, PWS, 1996
* {{en}} ''[http://www.netlib.org/utk/papers/templates/node11.html Templates for the Solution of Linear Systems]'' par [[Jack Dongarra]] sur [[netlib]]

== Liens externes ==
* {{mathworld |titre=Successive Overrelaxation Method |nom_url=SuccessiveOverrelaxationMethod}}
* {{en}} ''[http://math.fullerton.edu/mathews/n2003/SORmethodMod.html Module for the SOR Method]''

{{Palette|Analyse Numérique}}
{{portail|Algèbre|informatique théorique}}

{{DEFAULTSORT:Methode de surrelaxation successive}}
[[Catégorie:Analyse numérique matricielle]]
[[Catégorie:Algorithme numérique]]