Upload
djimramadji-josue
View
5
Download
2
Embed Size (px)
DESCRIPTION
Methode de Jacobi Et Gauss-Seidel
Citation preview
1
Méthodes itératives de Gauss-Seidel et Jacobi
Théorème 1. On note A = (ai,j)1≤i,j≤n ∈ GLn(K) et b = (bi)1≤i≤n et on s’interesse à larésolution par des méthodes numériques itératives du système Ax = b. Alors,• si A est à diagonale strictement dominante, les méthodes de Jacobi et de Gauss-Seidelconvergent.• si A ∈ S++
n (R), la méthode de Gauss-Seidel converge.
Démonstration. :Etape 1 : montrons que la méthode de Jacobi converge si A est à diagonale strictement domi-nante. Remarquons tout d’abord que la décomposition de la méthode de Jacobi est bien définie.En effet, A étant à diagonale strictement dominante, on a bien pour tout i ∈ [[1, n]], |ai,i| > 0 etD est bien inversible.
Méthode 1. Il suffit de montrer l’existence d’une norme matricielle ‖.‖ telle que B = M−1Nvérifie : ‖B‖ = ‖D−1(E + F )‖ < 1.
En considérant la norme ‖.‖∞ sur Kn, la norme de B subordonnée à la norme ‖.‖∞ est donnée
par : ‖B‖∞ = max1≤i≤n
n∑j=1
|bi,j |. On a alors :
B = D−1(E + F ) =
a−111 0 . . . 0
0 a−122
......
. . ....
0 . . . . . . a−1n,n
0 −a1,2 . . . −a1,n
−a2,1 0...
.... . . −an−1,n
−an,1 . . . −an,n−1 0
ce qui nous donne pour tout i ∈ [[1, n]], bi,i = 0 et ∀i 6= j, bi,j = −ai,j
ai,i(∇1). Alors, pour tout
i ∈ [[1, n]], on a :n∑
j=1
|bi,j | =∑j 6=i
|bi,j | =∑j 6=i
|ai,jai,i| = 1
|ai,i|∑j 6=i
|ai,j | < 1
D’où ‖B‖∞ < 1 et la méthode de Jacobi converge.
Etape 2 : montrons que la méthode de Gauss-Seidel converge si A est à diagonale strictementdominante. Remarquons comme dans l’étape 1, que la décomposition de Gauss-Seidel est biendéfinie. En effet, M = D − E est triangulaire inférieure et ses termes diagonaux sont non nulscomme vu précédemment.
Méthode 2. Montrons par un raisonnement par l’absurde que ρ(B) < 1, ce qui assurera laconvergence de la méthode.
Soit λ ∈ C une valeur propre de B =M−1N = (D −E)−1F et x 6= 0 un vecteur propre associé.On suppose par l’absurde que |λ| ≥ 1. Alors, (D − E)−1Fx = λx ⇐⇒ Fx = λ(D − E)x ce quinous donne :
0 −a1,2 . . . −a1,n0 . . . −a2,n
.... . . −an−1,n
0 . . . . . . 0
x1x2...xn
= λ
a1,1 0 . . . 0
a2,1 a2,2...
.... . . 0
an,1 . . . . . . an,n
x1x2...xn
soit ∀i ∈ [[1, n]],−
n∑j=i+1
ai,jxj = λi∑
j=1
ai,jxj puis :
λai,ixi = −
(n∑
j=i+1
ai,jxj + λi−1∑j=1
ai,jxj
)Soit i ∈ [[1, n]] tel que |xi| = max
1≤k≤n|xk| (x 6= 0 =⇒ xi 6= 0). Pour un tel i, on a :
|λai,i| =1
|xi||
n∑j=i+1
ai,jxj + λi−1∑j=1
ai,jxj | ≤1
|xi|
(n∑
j=i+1
|ai,j |.|xj |+ |λ|i−1∑j=1
|ai,j |.|xj |
)
2
et donc comme |λ| ≥ 1 :
|λ||ai,i|= |λai,i| ≤ |λ|n∑
j=i+1
|ai,j |+ |λ|i−1∑j=1
|ai,j | ≤ |λ|∑j 6=i
|ai,j |
D’où |λ| ≥ 1 =⇒ |ai,i| ≤∑j 6=i
|ai,j |, absurde. Ainsi, ρ(B) < 1 et la méthode de Gauss-Seidel
converge.
Etape 3 : Soit A ∈ S++n (R), vérifions pour commencer que M = D − E est bien inversible.
Comme D−E est triangulaire inférieure, il suffit de montrer que ces coefficients diagonaux sontnon nuls. Or, A étant définie positive, pour le vecteur colonne Xi où seul le i-ème coefficient estnon nul et vaut 1, on a :
tXiAXi = ai,i > 0 et donc M = D − E est bien inversible.
Méthode 3. montrons que ρ(B) < 1, ce qui assurera la convergence de la méthode.
Soit donc λ ∈ C une valeur propre de B =M−1N = (D−E)−1F et x 6= 0 un vecteur propre deB pour la valeur propre λ. A priori x ∈ Cn, considérons alors le produit scalaire hermitien :
< x,Ax >= < x, (D − E)x− Fx >= < x, (D − E)x > − < x,Fx > (1)
Alors, comme M−1Nx = λx⇐⇒ Nx = λMx⇐⇒ Fx = λ(D − E)x, on a aussi :
< x,Ax >= < x, (D − E)x > − < x, λ(D − E)x >
= (1− λ) < x, (D − E)x > (2)
Soit x = x1 + iy1 où x1, y1 ∈ R. Alors :
< x,Ax >= < (x1 + iy1), A(x1 + iy1) >
= < x1, Ax1 > +i < x1, Ay1 > −i < y1, Ax1 > −i× i < y1, Ay1 >
= < x1, Ax1 > +i < x1, Ay1 > −i < x1, Ay1 > + < y1, Ay1 >
= < x1, Ax1 >︸ ︷︷ ︸≥0
+< y1, Ay1 >︸ ︷︷ ︸≥0
> 0 car A définie positive, avec x 6= 0
On déduit de la relation (2) que λ 6= 1 car < x,Ax >∈ R∗+. Comme les coefficients diagonaux deD sont strictement positifs, D est symétrique définie positive et en particulier < x,Dx >∈ R∗+,en explicitant le calcul comme pour < x,Ax >. On en déduit que < x,Ax > =< x,Ax > et< x,Dx > =< x,Dx >. Vérifions que < x,Ex > =< x,Fx >. Comme A est symétrique réelle,on a :
tE = F , E = E et F = F
et ainsi < x,Ex > = txEx = txEx = t(Ex)x = tx tEx = txFx =< x,Fx >. En prenant leconjugué de la relation (2), on a :
< x,Ax >= (1− λ)(< x,Dx > − < x,Fx >) (3)
Puis, en faisant1
1− λ(2)+
1
1− λ(3)−(1) on a (
1
1− λ+
1
1− λ−1) < x,Ax >=< x,Dx >. D’où :
(1− λ) + (1− λ)− |1− λ|2
|1− λ|2< x,Ax >=
1− |λ|2
|1− λ|2< x,Ax >=< x,Dx >
Comme < x,Dx >∈ R∗+ et < x,Ax >∈ R∗+, on a |λ| < 1 et donc ρ(B) < 1, soit la convergencede la méthode de Gauss-Seidel
Rappels
Rappel 1. A est dit à diagonale strictement dominante si |ai,i| >n∑
j 6=i
|ai,j | pour tout i ∈ [[1, n]].
3
1 Méthodologie généraleOn considère K = R ou C. Soit A ∈ GLn(K) et b ∈ Kn. On cherche une approximation dex ∈ Kn solution de Ax = b. Pour cela on pose A =M−N oùM est facile à inverse (orthogonale,triangulaire) et on considère la suite itérative :
xk+1 =M−1Nxk +M−1b (∗) et on note B =M−1N .
Si la suite (xk)k∈N converge, alors sa limite x doit vérifier :
x =M−1Nx+M−1b⇐⇒Mx = Nx+ b⇐⇒ Ax = (M −N)x = b.
Définition 1. On dit que l’algorithme itératif (∗) converge si pour tout b ∈ Kn et tout x0 ∈ Kn,la suite itérative converge vers la solution x = A−1b ie lim
k 7−→+∞‖xk − x‖ = 0. Notant ek = xk − x
l’erreur à la k-ème iteration, on a alors
ek+1 = Bek =⇒ ek = Bke0
et l’algorithme converge donc si pour tout e0, limk 7−→+∞
Bke0 = 0.
Proposition 1. (Critères de convergence) Les propositions suivantes sont équivalentes :1. La méthode est convergente.2. ρ(B) = ρ(M−1N) < 1 où ρ désigne toujours le rayon spectral.3. ‖B‖ < 1 pour au moins une norme matricielle ‖.‖4. Pour tout v ∈ Kn, lim
k 7−→∞Bkv = 0.
Remarque 1. Pour une démonstration des équivalences de la proposition 1 voir Rouvière ex 12sur le rayon spectral.
1.1 Méthode de Jacobi et Gauss-Seidel.Pour A ∈ GLn(K) on désigne par :• −E, la matrice triangulaire strictement inférieure issue de A.• D, la matrice diagonale issue de A• −F , la matrice triangulaire strictement supérieure issue de A.
méthode décomposition B =M−1NJacobi A =M −N = D − (E + F ) D−1(E + F )
Gauss-Seidel A =M −N = (D − E)− F (D − E)−1F