Livre_silo 30 août 2013 16:32 Page 197
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
197
7 – Pivot de Gauss et résolution de systèmes
de v va alors envoyer Ae 1 sur la droite engendrée par e 1 . Cette réflexion a pour matrice dans la base
canonique S 1 = In −
2
∥v∥
2
v.
t v. Ainsi, S 1 A possède sa première colonne colinéaire à e 1 et on est
ramené au cas précédent.
1 Formaliser l’algorithme précédent en pseudo-code.
2 Écrire un programme Python implémentant cet algorithme.
3 Quelle est la complexité de cette méthode, en termes d’opérations arithmétiques ?
Exercice 7.22 ** On s’intéresse ici à la méthode de Jacobi, une méthode itérative de résolution approchée
de Ax = y, sous des conditions assez fortes ¹⁷ sur A.
Soit A ∈ Mn(R) une matrice dont la diagonale est dominante, c’est-à-dire : pour tout i ∈ 1, n,
|a i,i | >
∑
j̸ =i
|a i,j |. Cette condition assure de façon classique le caractère inversible de A, donc le système
Ax = y est de Cramer.
On décompose A sous la forme A = D + H, avec D diagonale et H comportant des 0 sur la diagonale.
On a alors Ax = y si et seulement si Dx = −Hx + y, soit encore (les conditions sur A assurent que les
éléments diagonaux de D sont différents de 0) : x = −D −1 Hx + D −1 y. La méthode de Jacobi consiste
alors à choisir un premier vecteur x 0 quelconque (par exemple x 0 = 0), puis définir une suite (xp) p∈N
par la relation de récurrence x p+1 = −D −1 Hxp + D −1 y. On démontre que sous les hypothèses faites
plus haut, la suite converge vers x, l’unique solution de Ax = y. En pratique, un point délicat consiste à
déterminer une condition raisonnable d’arrêt (calculer une infinité de termes est assez lassant).
1 On admet la formule suivante, qui permet de contrôler l’erreur ∥xp − x∥ à l’aide de la quantité
R = max i
1
a i,i
∑
j̸ =i
|a i,j | < 1 :
∥x − xp∥ ⩽
R p
1 − R
∥x 1 − x 0 ∥
(la norme considérée ici étant ∥z∥ = max(|z i |)).
Déduire de cette majoration un test d’arrêt dans la méthode de Jacobi, si on se donne pour objectif
une majoration ∥x − xp∥ ⩽ ε 0 .
2 Écrire en pseudo-code cet algorithme de Jacobi.
3 Quelle est la complexité de cet algorithme (en termes d’opérations arithmétiques élémentaires et fonction de n et ε 0 ) ?
4 Programmer une fonction Python jacobi implémentant effectivement cet algorithme. Tester. Comparer
avec la fonction linalg.jacobi de numpy.
5 La matrice de Virginie n’a pas sa diagonale dominante (les inégalités requises sont strictes ¹⁸), mais on
peut montrer que le rayon spectral ¹⁹ de D −1 (Vn − D) est de la forme 1 − αn, avec αn ∼
K
n 2 , ce qui
assure une convergence avec p bits significatifs en un nombre d’itérations de l’ordre de pn 2 .
Quel est le coût d’une résolution de VnX = Y à pn 2 itérations ? On distinguera selon le mode de
représentation choisi : avec une matrice « pleine » (classique), ou en exploitant le caractère creux de Vn.
Programmer et expérimenter la méthode de Jacobi sur ce type d’exemple peut faire l’objet de TP très
riches.
17. Il existe une condition nécessaire et suffisante relativement précise qui assure la convergence, mais on a
choisi de présenter ici une condition suffisante simple.
18. Elle est tout de même faiblement dominante, avec des inégalités larges, au moins une stricte et le caractère
irréductible.
19. Ici : la plus grande valeur propre.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
197
7 – Pivot de Gauss et résolution de systèmes
de v va alors envoyer Ae 1 sur la droite engendrée par e 1 . Cette réflexion a pour matrice dans la base
canonique S 1 = In −
2
∥v∥
2
v.
t v. Ainsi, S 1 A possède sa première colonne colinéaire à e 1 et on est
ramené au cas précédent.
1 Formaliser l’algorithme précédent en pseudo-code.
2 Écrire un programme Python implémentant cet algorithme.
3 Quelle est la complexité de cette méthode, en termes d’opérations arithmétiques ?
Exercice 7.22 ** On s’intéresse ici à la méthode de Jacobi, une méthode itérative de résolution approchée
de Ax = y, sous des conditions assez fortes ¹⁷ sur A.
Soit A ∈ Mn(R) une matrice dont la diagonale est dominante, c’est-à-dire : pour tout i ∈ 1, n,
|a i,i | >
∑
j̸ =i
|a i,j |. Cette condition assure de façon classique le caractère inversible de A, donc le système
Ax = y est de Cramer.
On décompose A sous la forme A = D + H, avec D diagonale et H comportant des 0 sur la diagonale.
On a alors Ax = y si et seulement si Dx = −Hx + y, soit encore (les conditions sur A assurent que les
éléments diagonaux de D sont différents de 0) : x = −D −1 Hx + D −1 y. La méthode de Jacobi consiste
alors à choisir un premier vecteur x 0 quelconque (par exemple x 0 = 0), puis définir une suite (xp) p∈N
par la relation de récurrence x p+1 = −D −1 Hxp + D −1 y. On démontre que sous les hypothèses faites
plus haut, la suite converge vers x, l’unique solution de Ax = y. En pratique, un point délicat consiste à
déterminer une condition raisonnable d’arrêt (calculer une infinité de termes est assez lassant).
1 On admet la formule suivante, qui permet de contrôler l’erreur ∥xp − x∥ à l’aide de la quantité
R = max i
1
a i,i
∑
j̸ =i
|a i,j | < 1 :
∥x − xp∥ ⩽
R p
1 − R
∥x 1 − x 0 ∥
(la norme considérée ici étant ∥z∥ = max(|z i |)).
Déduire de cette majoration un test d’arrêt dans la méthode de Jacobi, si on se donne pour objectif
une majoration ∥x − xp∥ ⩽ ε 0 .
2 Écrire en pseudo-code cet algorithme de Jacobi.
3 Quelle est la complexité de cet algorithme (en termes d’opérations arithmétiques élémentaires et fonction de n et ε 0 ) ?
4 Programmer une fonction Python jacobi implémentant effectivement cet algorithme. Tester. Comparer
avec la fonction linalg.jacobi de numpy.
5 La matrice de Virginie n’a pas sa diagonale dominante (les inégalités requises sont strictes ¹⁸), mais on
peut montrer que le rayon spectral ¹⁹ de D −1 (Vn − D) est de la forme 1 − αn, avec αn ∼
K
n 2 , ce qui
assure une convergence avec p bits significatifs en un nombre d’itérations de l’ordre de pn 2 .
Quel est le coût d’une résolution de VnX = Y à pn 2 itérations ? On distinguera selon le mode de
représentation choisi : avec une matrice « pleine » (classique), ou en exploitant le caractère creux de Vn.
Programmer et expérimenter la méthode de Jacobi sur ce type d’exemple peut faire l’objet de TP très
riches.
17. Il existe une condition nécessaire et suffisante relativement précise qui assure la convergence, mais on a
choisi de présenter ici une condition suffisante simple.
18. Elle est tout de même faiblement dominante, avec des inégalités larges, au moins une stricte et le caractère
irréductible.
19. Ici : la plus grande valeur propre.