MACS1 2010-2011 Analyse numérique
feuille d’exercices n˚6
Méthodes itératives I
Exercice 1 : Non convergence de la méthode de Jacobi.
Soit a ∈ R et A ∈ M3 (R) donnée par
1 a a
A = a 1 a .
a a 1
Montrer que A est symétrique définie positive si et seulement si − 21 < a < 1 et que la méthode
de Jacobi converge si et seulement si − 21 < a < 12 .
Exercice 2 : Méthode du gradient à pas fixe.
Soit A une matrice dans Mn (R) avec n ≥ 2 telle qu’il existe un réel α strictement positif avec
hAx, xi ≥ α||x||2 ∀x ∈ Rn .
Q.1) Montrer que pour tout vecteur b ∈ Rn , le système linéaire Ax = b admet une unique solution.
Q.2) Soient θ un réel et (xk )k∈N la suite de vecteurs définis par
x0 ∈ R n
.
xk+1 = xk − θ(Axk − b), ∀k ∈ N
2α
Montrer que pour θ ∈ 0, , la suite (xk )k∈N converge vers la solution du système linéaire Ax = b.
||A||22
Exercice 3 : Autre exemple de la Méthode du gradient.
Soit A une matrice carrée d’ordre n > 0, et b un vecteur de Rn . On veut résoudre le système
linéaire
Ax = b. (1)
1
On note D la matrice diagonale constituée des éléments diagonaux de la matrice A. Soit α 6= 0,
on étudie la méthode itérative
xk+1 = In − αD−1 A xk + αD−1 b.
Q.1) Montrer que la méthode est consistante, i.e si xk k∈N converge vers x alors x est solution de (1).
Q.2) Exprimer les coefficients de la matrice D−1 A en fonction de ceux de A.
Q.3) On suppose que 0 < α ≤ 1 et que A est à diagonale strictement dominante, i.e
n
X
|ai,i | > |ai,j |, ∀i = 1, . . . , n.
j=1j6=i
Montrer que la méthode est bien définie et
In − αD−1 A < 1.
∞
En déduire que la méthode est convergente.
Exercice 4 : Méthode de relaxation.
Soit A ∈ M3 (R) définie par A = Id − E − F avec
0 −2 0 0 0 0
E = −1 0 0 et F = 0 0 0 .
0 0 0 −1 −1 0
Q.1) Montrer que A est inversible.
√
1 2
Q.2) Soit 0 < ω < 2. Montrer que la matrice Id − E est inversible si et seulement si ω 6= .
ω 2
√
2
Pour 0 < ω < 2 avec ω 6= , on considère la méthode itérative, pour la résolution du système
2
linéaire Ax = b, définie par :
1 k+1 1−ω
Id − E x = F+ Id xk + b,
ω ω
−1
et note Lω = ω1 Id − E F + 1−ω
ω Id .
Q.3) Calculer en fonction de ω, les valeurs propres de Lω et son rayon spectral.
Q.4) Pour quelles
n valeurs de ω la méthode
√ o
est-elle convergente ? Déterminer ω0 ∈]0, 2[ tel que
2
ρ(Lω0 ) = min ρ(Lω ), ω0 ∈]0, 2[, ω 6= 2 .
2
Exercice 5 : Méthode de Jacobi et Gauss-Siedel pour une matrice tridiagonale.
On considère la matrice tridiagonale A d’ordre n ≥ 3 à coefficients réels ou complexes donnée par
a1 c1 0 ... 0
.. ..
b2
a2 c2 . .
A=0
.. .. ..
,
. . . 0
..
..
. bn−1 an−1 cn−1
.
0 ... 0 bn an
où les coefficients ai étant non nuls.
Q.1) Montrer que pour toute matrice B = (bi,j )1≤i,j≤n dans Mn (K) et pour tout scalaire t, la
matrice B(t) = (bi,j (t))1≤i,j≤n définie par
bi,j (t) = ti−j bi,j , 1 ≤ i, j ≤ n,
est semblable à B.
Q.2) Montrer que le polynôme caractéristique de la matrice J intervenant dans la méthode de Jacobi
(pour la résolution de Ax = b) s’écrit sous la forme PJ (λ) = P (λ2 )λq , où P est polynôme tel que
P (0) 6= 0.
Q.3) Montrer que le polynôme caractéristique de la matrice G intervenant dans la méthode de
Gauss-Siedel s’écrit PG (λ2 ) = PJ (λ)λn .
Q.4) Montrer que ρ(G) = (ρ(J))2 et R∞ (G) = 2R∞ (J), et conclure.
