5. Systèmes linéaires
117
5.3.3 Méthodes de relaxation
La convergence d’une méthode itérative ne dépend pas du choix du vecteur initial { 0 , mais la rapidité de convergence en dépend. D’où l’idée d’introduire un facteur de relaxation $ non nul. Les matrices P et Q sont
choisies comme dans la méthode de Gauss mais pondérées par le facteur
de relaxation P =(
1
$ G H) et Q =
1$
$ G + I= La matrice
O = P
1 Q =(
1
$
G H)
1 (
1 $
$
G + I )
est appelée matrice de relaxation. L’algorithme est fondé sur le calcul des
itérées
{
(n+1)
l
= {
(n)
l +
$
d ll
(e l
l1
X
m=1
d lm {
(n+1)
m
q
X
m=l
d lm {
(n)
m )
On démontre que si le facteur de relaxation dépasse 2, la méthode diverge.
Pour $ =1 , on retrouve la méthode de Gauss-Seidel. Lorsque 0 ?$?1,
on parle de sous-relaxation et lorsque 1 ?$?2, on parle de surrelaxation
(SOR, Successive Over Relaxation). Le théorème d’Ostrowski-Reich a!rme
que si D est une matrice définie positive et si le facteur de relaxation 0
?$?2> alors la méthode converge. Lorsque D est une matrice tridiagonale
par blocs dont les blocs diagonaux sont inversibles, si on note M la matrice
M = G
1 P = G
1 (H + I ),e t(M) son rayon spectral (c’est-à-dire le plus
grand module des valeurs propres de M), alors la valeur optimale du facteur
de relaxation est donnée par
$ 0 =
2
1+
p
1 (M) 2
Dans certains cas, on utilise diérents facteurs $ pour diérents blocs de
D : c’est la méthode de relaxation par blocs.
Exemple. Pour un système de trois équations à trois inconnues, l’itération
conduit à calculer
;
?
=
{
(n+1) = {
(n) + $ (e 1 d 11 { n d 12 |
(n) d 13 }
(n) )@d 11
|
(n+1) = |
(n) + $ (e 2 d 21 {
(n+1) d 22 |
(n) d 23 }
(n) )@d 22
}
(n+1) = }
(n) + $ (e 3 d 31 {
(n+1) d 32 |
(n+1) d 33 }
(n) )@d 33
La surrelaxation successive symétrique (SSOR, Symetric Successive Over
Relaxation) consiste à faire jouer le même rôle aux matrices H et I ,e n
introduisant un vecteur intermédiaire | d’itérée |
(n)
:
½
(
1
$ G H)|
(n) =(
1$
$ G + I ){
(n)
(
1
$ G I ){
(n+1) =(
1$
$ G + H)|
(n)