Enoncés et corrections : Ana Matos.

Exo7

Méthodes itératives

Exercice 1
 
1 a a
Soit a ∈ R et A =  a 1 a 
a a 1
1. Pour qu’elles valeurs de a A est–elle définie positive?

2. Pour qu’elles valeurs de a la méthode de Gauss–Seidel est–elle convergente?

3. Ecrire la matrice J de l’itération de Jacobi.

4. Pour qu’elles valeurs de a la méthode de Jacobi converge–t–elle?

5. Ecrire la matrice L1 de l’itération de Gauss–Seidel. Calculer ρ(L1 ).

6. Pour quelles valeurs de a la méthode de Gauss–Seidel converge–t–elle plus vite que celle de Jacobi?

[002235]

Exercice 2
Soit A une matrice hermitienne inversible décomposée en A = M − N où M est inversible. Soit B = I − M −1 A
la matrice de l’itération:
xn+1 = Bxn + c.
Supposons que M + M ∗ − A soit définie positive.

1. Soit x un vecteur quelconque et on pose y = Bx. Montrer l’identité:

(x, Ax) − (y, Ay) = ((x − y), (M + M ∗ − A)(x − y)).

2. Supposons que A est définie positive. Soit x ̸= 0 un vecteur propre de B associé à la valeur propre λ ,
y = Bx = λ x. Utiliser l’identité précédente pour montrer que |λ | < 1. Que peut–on conclure sur la
convergence de la méthode?

3. Supposons maintenant que ρ(B) < 1. montrer que A est définie positive.

4. Supposons A décomposée par points ou par blocs sous la forme

A = D − E − F avec D définie positive.

Montrer que la méthode de relaxation par points ou par blocs pour 0 < w < 2 converge si et seulement si
A est définie positive.

Correction ▼ [002236]

Exercice 3
Soit A = I −E −E ∗ une matrice carrée d’ordre N où E est une matrice strictement triangulaire inférieure (ei j = 0
pour i ⩽ j). Pour résoudre le système Ax = b, on propose la méthode itérative définie par

(I − E)x2k+1 = E ∗ x2k + b


(I − E ∗ )x2k+2 = Ex2k+1 + b

1
 1. Déterminer B et c pour que l’on ait:
x2k+2 = Bx2k + c.
Vérifier que B = M −1 N et A = M − N avec M = (I − E)(I − E ∗ ) , N = EE ∗ .
2. Montrer que M ∗ + N est une matrice définie positive. En déduire une condition nécessaire et suffisante
pour la convergence de la méthode.
Correction ▼ [002237]

Exercice 4
Soient A et B deux matrices réelles d’ordre N et a, b deux vecteurs de Rn . On considère les deux itérations
suivantes: 
xk+1 = Byk + a
k = 0, 1, · · · (1)
yk+1 = Axk + b
avec x0 , y0 ∈ Rn donnés.
1. Déterminer une condition nécessaire et suffisante de convergence des deux suites de vecteurs.
2. Soit zk = (xk , yk )T ∈ R2n . Montrer que (1) peut s’écrire
zk+1 = Czk + c
où C est une matrice d’ordre 2n. Expliciter C et c.
3. Montrer que ρ 2 (C) = ρ(AB).
4. On considère maintenant les deux itérations suivantes:

xk+1 = Byk + a
k = 0, 1, · · · (2)
yk+1 = Axk+1 + b
Donner une condition nécessaire et suffisante de convergence.
Montrer que (2) est équivalent à
zk+1 = Dzk + d
où D est une matrice d’ordre 2N.
Montrer que ρ(D) = ρ(AB).
5. Taux de convergence
On appelle taux de convergence asymptotique de la matrice itérative M le nombre
R(M) = − ln(ρ(M))).
On pose ek = xk − x∗ l’erreur de l’itéré d’ordre k.
∥ek ∥
(a) Montrer que le nombre d’itérations k pour réduire l’erreur d’un facteur ε , i.e., ∥e0 ∥
⩽ ε vérifie
− ln ε
k⩾ .
R(M)
(b) Comparer le taux de convergence des algorithmes (1) et (2).
Correction ▼ [002238]

Exercice 5
On considère le système Ax = b avec
 
3 1 0 0 0

 1 2 1 0 0 

A=
 0 2 3 1 0 
 (3)
 0 0 1 4 3 
0 0 0 1 1

2
 1. Décomposer A sous la forme LU et en déduire que (3) admet une solution unique x∗ .

2. Ecrire l’itération de Gauss–Seidel pour ce système, c’est–à–dire, le système linéaire donnant Xn+1 =
(xn+1 , yn+1 , zn+1 ,tn+1 , un+1 ) en fonction de Xn = (xn , yn , zn ,tn , un ).

3. Pour tout n ∈ N on pose en = Xn − x∗ . Montrer qu’il existe a ∈ [0, 1[ tel que:

∀n ∈ N ∥en+1 ∥∞ ⩽ a∥en ∥∞ .
En déduire la convergence de la suite.

4. Déterminer la matrice de Gauss–Seidel L1 associée à A. Calculer ∥L1 ∥∞ . En déduire la convergence de

(Xn ) vers x∗ .

5. Soit A ∈ Rn×n vérifiant la propriété suivante:

|ai j | ⩾ ∑ j̸=i |ai j | i = 2, · · · , n

|a11 | > ∑ j̸=1 |a1 j |

et sur chaque ligne de A il existe il existe un terme non nul ai j pour i ⩾ 2 et j < i.
Montrer qu’alors la méthode de Gauss–Seidel converge.

Correction ▼ [002239]

3
Correction de l’exercice 2 ▲

1. Pour le membre de gauche on obtient

(x, Ax) − (y, Ay) = (x, AM −1 Mx) + (M −1 Ax, Ax) − (M −1 Ax, AM −1 Ax)

Pour le membre de droite on obtient y = Bx = x − M −1 Ax ⇒ x − y = M −1 Ax et donc

(x − y, (M + M ∗ − A)(x − y)) = (M −1 Ax, (M + M ∗ − A)M −1 Ax) =

(M −1 Ax, Ax) + (M −1 Ax, M ∗ M −1 Ax) − (M −1 Ax, AM −1 Ax)

Mais
(M −1 Ax, M ∗ M −1 Ax) = (x, (M −1 A)∗ M ∗ M −1 Ax) = (x, AM −1 Ax)
ce qui fini la démonstration.

2. y = Bx = λ x ⇒ x − y = (1 − λ )x. En utilisant l’égalité précédente

(x, Ax) − (y, Ay) = (x, Ax) − (λ x, A(λ x)) = (1 − |λ |2 )(x, Ax)
(x − y, (M + M ∗ − A)(x − y)) = ((1 − λ )x, (M + M ∗ − A)((1 − λ )x)) = |1 − λ |2 (x, (M + M ∗ − A)x)
et donc
(1 − |λ |2 )(x, Ax) = |1 − λ |2 (x, (M + M ∗ − A)x)
λ ne peut pas être = 1 car sinon y = Bx = x ⇔ x − M −1 Ax = x ⇔ M −1 Ax = 0 ⇔ x = 0. Donc λ ̸= 1,
M + M ∗ − A définie positive, |1 − λ |2 > 0, A définie positive impliquent que 1 − |λ |2 > 0 ⇔ |λ | < 1.
Donc ρ(B) < 1 et la méthode itérative converge.

3. Démonstration par absurde. Supposons que ce n’est pas vrai: ∃x0 ̸= 0 α0 = (x0 , Ax0 ) ⩽ 0. Alors la
suite xn = Bxn−1 = Bn x0 tend vers 0 et lim αn = lim(xn , Axn ) = 0
On utilise maintenant la relation de la question 1 avec x = xn−1 et y = Bxn−1 = xn et on obtient

αn−1 − αn = (xn−1 − xn , (M + M ∗ − A)(xn−1 − xn ) > 0

si xn−1 − xn ̸= 0 (ce qui est vrai car sinon xn−1 = xn = Bxn−1 et B a une valeur propre = 1)
Donc (αn−1 − αn ) est une suite strictement décroissante convergeant vers 0 avec α0 < 0. Ceci est
impossible et donc A est définie positive

4. Soit A = D − E − F la décomposition usuelle de A. Comme A est hermitienne, D = D∗ et F = E ∗ . Pour

la méthode de relaxation on a M = D/w − E et donc
2−w
M ∗ + M − A = D/w − F + D/w − E − D + E + F = D
w
qui est hermitienne. Pour 0 < w < 2, M ∗ +M −A est définie positive, alors des deux questions précédentes
on conclut que la méthode converge ssi A est définie positive.

Correction de l’exercice 3 ▲

1. On a x2k+1 = (I − E)−1 E ∗ x2k + (I − E)−1 b et donc

x2k+2 = (I − E ∗ )−1 E(I − E)−1 E ∗ x2k + (I − E ∗ )−1 E(I − E)−1 b + (I − E ∗ )−1 b

Mais E(I − E)−1 = (I − E)−1 E et alors

x2k+2 = (I − E ∗ )−1 (I − E)−1 EE ∗ x2k + (I − E ∗ )−1 (I − E)−1 (E + I − E)b = M −1 Nx2k + M −1 b

avec
M = (I − E)(I − E ∗ ), N = EE ∗ , M − N = I − E − E∗ = A

4
 2. M ∗ + N = I − E − E ∗ + 2EE ∗ et donc
v∗ (M ∗ +N)v = ∥v∥22 −v∗ Ev−v∗ E ∗ v+2v∗ EE ∗ v = ∥E ∗ v∥22 +(∥v∥22 +∥E ∗ v∥22 −2Re(v, E ∗ v)) On a l’inégalité

−2∥v∥∥E ∗ v∥ ⩽ −2|(v, E ∗ v)| ⩽ −2|Re(v, E ∗ v)|

et donc
(∥v∥2 − ∥E ∗ v∥2 )2 ⩽ ∥v∥22 + ∥E ∗ v∥22 − 2Re(v, E ∗ v) ⇒
v∗ (M ∗ + N)v ⩾ ∥E ∗ v∥22 + (∥v∥ − ∥E ∗ v∥2 )2 implique que

v∗ (M ∗ + N)b = 0 ⇔ ∥E ∗ v∥2 = 0 et ∥v∥2 = ∥E ∗ v∥2 ⇔ ∥v∥2 = 0

Donc M ∗ + N est définie positive et en appliquant un résultat d’un exercice précédent on conclut que la
méthode converge ssi A est définie positive.

Correction de l’exercice 4 ▲

1. C’est facile à voir que si (xk ) converge vers x∗ et (yk ) converge vers y∗ , alors x∗ et y∗ sont solution des
systèmes (I − BA)x∗ = Bb + a et (I − AB)y∗ = Aa + b. On a:

xk+1 = B(Axk−1 + b) + a = BAxk−1 + Bb + a
yk+1 = A(Byk−1 + a) + b = AByk−1 + Aa + b

et donc (xk ) converge ssi ρ(BA) < 1 et (yk ) converge ssi ρ(AB) < 1.
   
0 B a
2. zk+1 = Czk + c avec C = ,c =
A 0 b

3. Soit λ valeur propre non nulle de C et z = (x, y)T vecteur propre associé

By = λ x
Cz = λ z ⇔ ⇒ ABy = λ Ax = λ 2 y ⇒
Ax = λ y

λ 2 est valeur propre de AB.

Soit maintenant α valeur propre de AB ⇔ ∃u ̸= 0 : ABu = αu. On pose β 2 = α et x = Bu, y = β u
       
x β Bu β Bu x
C = = =β
y ABu β 2u y

et donc ρ 2 (C) = ρ(AB)

   
0 B a
4. D = , d= . La démonstration de ρ(D) = ρ(AB) se fait comme dans la
0 AB Aa + b
question précédente.
∥ek ∥
5. (a) ek = M k e0 ⇒ ∥e0 ∥
⩽ ∥M k ∥ ⩽ ε. Il suffit donc d’avoir ∥M k ∥1/k ⩽ ε 1/k ⇒ log(∥M k ∥1/k ) ⩽ 1k log ε
log ε
c’est- à dire k ⩾ log(∥M k ∥1/k )
Mais comme ρ(M) ⩽ ∥M k ∥1/k on obtient finalement

k ⩾ − log ε/R(M)
p
(b) nous avons ρ 2 (C) = ρ(AB) ⇒ ρ(C) = ρ(AB) et ρ(D) = ρ(AB) . Donc ρ(D) < ρ(C) ⇒ R(D) >
R(C). Donc on atteint la même réduction d’erreur avec un plus petit nombre d’itérations de la
méthode 2)

Correction de l’exercice 5 ▲

5
1.

2. Itération de Gauss-Seidel : (D − E)Xn+1 = FXn + b avec

   
3 0 1
 1 2   0 1 
   
D−E =  0 2 3

 , −F = 
  0 1 

 0 0 1 4   0 3 
0 0 0 1 1 0

3. en = Xn − X ∗ , , Xn+1 = (D − E)−1 FXn + (D − E)−1 b, X ∗ = (D − E)−1 FX ∗ + (D − E)−1 b ⇒ en+1 =

(D − E)−1 Fen
On obtient alors (D − E)en+1 = (D − E)−1 Fen et si on écrit composante à composante on obtient
3e1n+1 = −e2n ⇒ |e1n+1 | ⩽ 13 ∥en ∥∞
e1n+1 + 2e2n+1 = −e3n ⇒ |e2n+1 | ⩽ 61 ∥en ∥∞ + 21 ∥en ∥∞ = 23 ∥en ∥∞
22 1 7
2e2n+1 + 3e3n+1 = −e4n ⇒ |e3n+1 | ⩽ 3 3 ∥en ∥∞ + 3 ∥en ∥∞ = 9 ∥en ∥∞
en+1 32 + 4e4n+1 = −3e5n ⇒ |e4n+1 | ⩽ 41 79 ∥en ∥∞ + 43 ∥en ∥∞ = 34
16 ∥en ∥∞
17
e4n+1 + e5n+1 = 0 ⇒ |e5n+1 | ⩽ 18 ∥en ∥∞
et donc
17
∥en ∥∞ ⩽ ∥en ∥∞
18
4.  1 
3 0 0 0 0
 −1 1
0 0 0 
 16 2
(D − E)−1 = 

 9 − 13 1
3 0 0 ,

 −1 1 1
− 12 1
0 
36 12 4
1 1 1
36 − 12 12 − 14 1
 1 
0 3 0 0 0
 0 − 61 1
2 0 0 
−1
 1

L1 = (D − E) F = 
 0 9 − 21 1
3 0 

1 1 1 3
 0 − 36 12 − 12 4

1 1 1
0 36 − 12 12 − 34
et donc ∥L1 ∥∞ = max( 13 , 64 , 17 32 32
18 , 36 , 36 ) =
17
18 .
On en déduit donc la convergence de (Xn ) vers X ∗ .