Sup’Galilée Année 2020/2021
MACS1
Analyse numérique - TD8
Méthodes itératives pour la résolution des systèmes linéaires
TM : Travail à la Maison
Rappel (c.f. Cours)
Soient A P Mn pCq une matrice inversible, et deux matrices M P Mn pCq inversible et N P Mn pCq telles que A “ M ´ N.
Soient u p0q P Cn et b P Cn . On considère l’algorithme
M u pk`1q “ N u pkq ` b , @ k P N. (1)
On pose B “ M´1 N. Si la suite pu upkq qkPN converge, alors elle converge vers la solution u du système Au
u “ b . De plus, la
upkq qkPN converge vers u pour toute donnée initiale u p0q si et seulement si ρpBq ă 1.
suite pu
Exercice 1 (cas particulier des matrices hermitiennes)
Soit A P Mn pCq une matrice hermitienne inversible décomposée en A “ M ´ N où M est inversible. On note B “ I ´ M´1 A.
1. Montrer que la matrice M˚ ` N est hermitienne.
On suppose maintenant que M˚ ` N est définie positive.
2. Soit x un vecteur quelconque de Cn et y “ Bx
x.
1. Montrer que
x ´ y “ M´1 Ax
x
et que
x, Ax
xx x, AM´1 Ax
xy ´ xyy , Ayy y “ xx xy ` xM´1 Ax xy ´ xM´1 Ax
x, Ax x, AM´1 Ax
xy
2. En déduire que
x, Ax
xx x ´ y , pM˚ ` Nqpx
xy ´ xyy , Ayy y “ xx x ´ y qy.
3. Montrer que si A est définie positive alors ρpBq ă 1.
4. Démontrer par l’absurde que si ρpBq ă 1 alors A est définie positive.
Exercice 2 (méthodes de Jacobi et Gauss-Seidel)
Soit b P Rn et A la matrice définie par
¨ ˛
1 ´ 21 1
2
A“˝ 1 1 1 ‚.
´ 12 ´ 21 1
1. La matrice A est-elle inversible ?
2. Etudier la convergence de la méthode itérative de Jacobi pour résoudre le système Axx “ b.
3. Etudier la convergence de la méthode itérative de Gauss-Seidel pour résoudre le système Axx “ b.
Exercice 3 (méthodes de relaxation) (TM)
On considère la résolution du système linéaire Axx “ b par la méthode de relaxation, avec A P Mn pRq inversible et b P Rn
p0q n xpkq qkPN de vecteurs Rn , pour k P N par
donnés. Soit x P R fixé. On définit la suite px
pk`1q pk`1q
x pk`1q “ px1 , x2 , ¨ ¨ ¨ , xpk`1q
n qt
˜ ¸
i´1 n
pk`1q ω ÿ pk`1q
ÿ pkq pkq
avec xi “ bi ´ aij xj ´ aij xj ` p1 ´ ωqxi , @i P v1, nw. (2)
aii j“1 j“i`1
1
1. En écrivant A sous la forme A “ D ´ E ´ F, avec, pour pi, jq P v1, nw2
dii “ aii , dij “ 0, si i ‰ j,
eij “ ´aij , si i ą j, eij “ 0, si i ď j,
fij “ ´aij , si i ă j, fij “ 0, si i ě j,
montrer que (2) s’écrit sous la forme Mx xpk`1q “ Nx xpkq ` b , où l’on précisera les matrices M et N associées. Réécrire
cette relation sous la forme x pk`1q “ Bx
xpkq ` c , où l’on précisera la matrice B et le vecteur c associés.
On note dans la suite Lω “ B la matrice d’itération de la méthode de relaxation.
2. Dans cette question on va montrer que ρpLω q ě |ω ´ 1| pour ω ‰ 0. On note pLω le polynôme caractéristique de Lω .
Il s’écrit sous la forme
pLω pλq “ λn ` αn´1 λn´1 ` ¨ ¨ ¨ ` α1 λ ` α0 .
On note tλi uiPv1,nw les valeurs propres de Lω , c’est-à-dire les racines de pLω .
śn
(a) En utilisant la relation i“1 λi “ p´1qn α0 “ p´1qn pLω p0q, montrer que
n
ź ` ˘
λi “ det p1 ´ ωqIn ` ωD´1 F .
i“1
(b) En déduire que
n
ź
|λi | “ |1 ´ ω|n ,
i“1
et conclure que ρpLω q ě |1 ´ ω|.
Déduire de la question précédente que si la méthode de relaxation converge, alors nécessairement ω Ps0, 2r.
3. En utilisant le résultat de l’exercice 5,montrer que si A est symétrique définie positive, et si ω Ps0, 2r, alors la méthode
de relaxation converge. En déduire, en particulier, que la méthode de Gauss-Seidel converge.
Exercice 4
Soit A P Mn pRq une matrice inversible telle que ses éléments diagonaux soient tous non nuls et soit b un vecteur de Rn . On
souhaite résoudre le système linéaire Ax
x “ b `en utilisant
˘ la méthode itérative suivante : α étant un réel non nul et le vecteur
x p0q P Rn étant donné, on construit la suite x pkq kPN par la formule de récurrence
x pk`1q “ pI ´ αD´1 Aqx
xpkq ` αD´1b , (3)
où I est la matrice identité et D la matrice diagonale constituée de la diagonale de A (Dii “ Aii , @i P v1, nw).
` ˘
x P Rn , alors x̄
1. Montrer que si la suite x pkq kPN converge vers x̄ x est la solution du système linéaire Ax̄
x “ b.
2. Exprimer les coefficients de la matrice pI ´ αD´1 Aq en fonction des coefficients de A.
3. On suppose que A est à diagonale strictement dominante 1 et que 0 ă α ď 1.
}Axx}8
(a) On rappelle que pour A P Mn pRq, on a }A}8 “ sup .
x‰0 }xx }8
Montrer que
}I ´ αD´1 A}8 ă 1.
(b) Soit } ¨ }s une norme matricielle subordonnée. Montrer que
ρpAq ď }A}s ,
et en déduire que ρpAq ď }A}8 .
(c) Donner la matrice d’itération de la méthode itérative (3). En déduire que cette méthode converge.
4. Quelle méthode itérative étudiée en cours retrouve-t-on lorsque α “ 1 ? Justifier.
n
ÿ
1. Une matrice A P Mn pRq est dite à diagonale strictement dominante si, |Ai,i | ą |Ai,j |, @i P v1, nw.
j“1
j‰i
