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