Méthode de Richardson
Soit A ∈ Mn inversible et b ∈ Rn . Soit x ∈ Rn solution de
Ax = b.
Méthode de Richardson: soit α ∈ R, on construit une suite de solution x k de la
forme
x k+1 = x k + α(b − Ax k ).
On a donc
(x k+1 − x) = (I − αA)(x k − x),
(x k+1 − x) = (I − αA)k (x 1 − x),
B = (I − αA)
Convergence: ssi ρ(B) < 1
Taux de convergence: kB k k1/k → ρ(I − αA)
Méthode de Richardon pour les matrices SDP
Soit A ∈ Mn SDP (Symétrique Définie Positive) et λi > 0, i = 1, · · · , n ses
valeurs propres par ordre croissant
ρ(I − αA) = max |1 − αλ1 |, |1 − αλn |
αopt = argminα∈R max |1 − αλ1 |, |1 − αλn |
2 λn − λ1 κ−1
αopt = , ρ(I − αopt A) = = <1
λ 1 + λn λ1 + λn κ+1
Problème: on ne connait pas les valeurs propres de A
Voir Exercice: Méthode de Richardson à pas variable
Méthode de Richardon pour les matrices SDP
Nombre d’itérations pour une précision fixée:
k
kx k+1 − xk2 ≤ ρ(I − αopt A) kx 1 − xk2 ,
κ − 1 k
kx k+1 − xk2 ≤ kx 1 − xk2 ,
κ+1
On cherche le nb d’itération k pour atteindre une précision ǫ, ie
κ − 1 k
≤ ǫ,
κ+1
ln( 1ǫ )
k≥ 1+ κ1
ln( 1− 1 )
κ
Pour κ grand:
κ 1
>
k ∼ ln( )
2 ǫ
Méthode de Richardon à pas variable pour les matrices
SDP
Soit A ∈ Mn SDP (Symétrique Définie Positive).
On pose e k = x − x k , r k = Ae k = b − Ax k ,
et on considère l’algorithme itératif: x 1 donné et pour k = 1, · · ·
k k
k (r ,r )
α = k k
,
(Ar , r )
k+1
x = x k + αk r k .
On montre que
αk = Argminα∈R (Ae k+1 , e k+1 ) = α2 (Ar k , r k ) − 2α(r k , r k ) + (Ae k , e k ),
et
(r k , r k )2
k+1 k+1 k k
(Ae ,e )= 1− (Ae , e ),
(Ar k , r k )(A−1 r k , r k )
d’où
1
(Ae k+1 , e k+1 ) ≤ 1 − (Ae k , e k )
Cond2 (A)
Méthode de Richardon à pas variable pour les matrices
SDP: algorithme
Ax = b avec A matrice SDP
Choix de la précision ǫ sur le résidu relatif
Initialisation: x 1 , r 1 = b − Ax 1 , nr = nr 0 = kr 1 k
Itérer tant que nrnr0 ≥ ǫ
p k = Ar k
k (r k ,r k )
α = (pk ,r k )
x k+1 = x k + αk r k
r k+1 = r k − αk p k
nr = kr k+1 k
Méthode de Richardon préconditionnée
Préconditionnement: matrice C ∈ Mn inversible
x k+1 = x k + αC −1 (b − Ax k )
(x k+1 − x) = (I − αC −1 A)(x k − x)
B = (I − αC −1 A)
On cherche un préconditionnement C tel que
C ∼ α A ie ρ(I − αC −1 A) << 1
le système Cy = r est peu coûteux à résoudre
Exemple des matrices et préconditionnements SDP
A, C ∈ Mn symétriques définies positives.
Soient y = C 1/2 x, y k = C 1/2 x k , c = C −1/2 b on a
C −1/2 AC −1/2 y = c,
La matrice C −1/2 AC −1/2 est SDP, et
y k+1 = y k + α c − C −1/2 AC −1/2 y k
Convergence ssi ρ(I − αC −1/2 AC −1/2 ) < 1
2
αopt =
λmin (C −1/2 AC −1/2 ) + λmax (C −1/2 AC −1/2 )
−1/2 −1/2 −1/2 −1/2
−1/2 −1/2 λ max (C AC ) − λ min (C AC )
ρ(I − αopt C AC )=
λmin (C −1/2 AC −1/2 ) + λmax (C −1/2 AC −1/2 )
Exemple des matrices et préconditionnements SDP
A, C ∈ Mn symétriques définies positives.
Soient y = C 1/2 x, y k = C 1/2 x k , c = C −1/2 b on a
C −1/2 AC −1/2 y = c,
La matrice C −1/2 AC −1/2 est SDP, et
y k+1 = y k + α c − C −1/2 AC −1/2 y k
Convergence ssi ρ(I − αC −1/2 AC −1/2 ) < 1
2
αopt =
λmin (C −1/2 AC −1/2 ) + λmax (C −1/2 AC −1/2 )
−1/2 −1/2 −1/2 −1/2
−1/2 −1/2 λ max (C AC ) − λ min (C AC )
ρ(I − αopt C AC )=
λmin (C −1/2 AC −1/2 ) + λmax (C −1/2 AC −1/2 )
Méthode de Richardon préconditionnée à pas variable pour
les matrices et préconditionnements SDP: algorithme
Soient A et C SDP et le système Ax = b.
On applique l’algorithme de Richardon à pas variable au système
C −1/2 AC −1/2 y = C −1/2 b.
Il se formule comme précédemment avec la matrice A e = C −1/2 AC −1/2 , le
second membre c = C −1/2 b, les itérés y k = C 1/2 x k et les résidus r̃ k = C −1/2 r k .
En repassant à A, x, r on obtient:
Choix de la précision ǫ sur le résidu relatif
Initialisation: x 1 , r 1 = b − Ax 1 , nr = nr 0 = kr 1 k
Itérer tant que nrnr0 ≥ ǫ
q k = C −1 r k
p k = Aq k
k (q k ,r k )
α = (pk ,qk )
x k+1 = x k + αk q k
r k+1 = r k − αk p k
nr = kr k+1 k
Exemples de préconditionnements
A=D −E −F
avec D diagonale de A (supposée inversible), D − E = tril(A), D − F = triu(A)
Jacobi:
C =D
Gauss Seidel
C = D − E ou C = D − F
SOR (Successive over relaxation) ω ∈ (0, 2)
D
C= −E
ω
SSOR (Symmetric Successive over relaxation) ω ∈ (0, 2)
D D
C= −E −F
ω ω
