3.13 Exercices
113
(1) Est-il possible d’utiliser la m´ ethode de Gauss sans pivot ? (2) Trouver une
permutation de A, sous la forme PAQ, pour laquelle on peut appliquer la m´ ethode de Gauss. Comment transforme-t-elle le syst` eme lin´ eaire ?
[Solution : la Propri´ et´ e 3.4 n’est pas satisfaite car d´ et(A22) = 0. La matrice de
permutation est celle qui ´ echange d’une part la premi` ere et la seconde lignes,
d’autre part la seconde et la troisi` eme colonnes.]
10. Montrer que, si A est une matrice sym´ etrique d´ efinie positive, r´ esoudre le syst` eme lin´ eaire Ax = b revient ` a calculer x=
n
i=1 (ci/λi)vi, o` u les λi sont les
valeurs propres de A et o` u les vi sont les vecteurs propres correspondants.
11. (D’apr` es [JM92]). On se donne le syst` eme lin´ eaire suivant
1001 1000
1000 1001
x1
x2
=
b1
b2
.
En utilisant l’Exercice 10, expliquer pourquoi, quand b = [2001, 2001]
T , un
petite perturbation δb = [1, 0]
T produit de grandes variations dans la solution,
et r´ eciproquement quand b = [1, −1]
T , une petite variation δx = [0.001, 0]
T
dans la solution induit de grandes variations dans b.
[Indication : d´ ecomposer le second membre sur la base des vecteurs propres
de la matrice.]
12. D´ eterminer le remplissage pour une matrice A ∈ R
n×n n’ayant des termes non
nuls que sur la diagonale principale, sur la premi` ere colonne et sur la derni` ere
ligne. Proposer une permutation qui minimise le remplissage.
[Indication : il suffit d’´ echanger la premi` ere ligne et la premi` ere colonne avec
la derni` ere ligne et la derni` ere colonne respectivement.]
13. Soit Hnx = b un syst` eme lin´ eaire o` u Hn est la matrice de Hilbert d’ordre n.
Estimer, en fonction de n, le nombre maximum de chiffres significatifs qu’on
peut attendre en r´ esolvant ce syst` eme avec la m´ ethode de Gauss.
14. Montrer que si A=QR alors
1
n
K1(A) ≤ K1(R) ≤ nK1(A),
et K2(A) = K2(R).
113
(1) Est-il possible d’utiliser la m´ ethode de Gauss sans pivot ? (2) Trouver une
permutation de A, sous la forme PAQ, pour laquelle on peut appliquer la m´ ethode de Gauss. Comment transforme-t-elle le syst` eme lin´ eaire ?
[Solution : la Propri´ et´ e 3.4 n’est pas satisfaite car d´ et(A22) = 0. La matrice de
permutation est celle qui ´ echange d’une part la premi` ere et la seconde lignes,
d’autre part la seconde et la troisi` eme colonnes.]
10. Montrer que, si A est une matrice sym´ etrique d´ efinie positive, r´ esoudre le syst` eme lin´ eaire Ax = b revient ` a calculer x=
n
i=1 (ci/λi)vi, o` u les λi sont les
valeurs propres de A et o` u les vi sont les vecteurs propres correspondants.
11. (D’apr` es [JM92]). On se donne le syst` eme lin´ eaire suivant
1001 1000
1000 1001
x1
x2
=
b1
b2
.
En utilisant l’Exercice 10, expliquer pourquoi, quand b = [2001, 2001]
T , un
petite perturbation δb = [1, 0]
T produit de grandes variations dans la solution,
et r´ eciproquement quand b = [1, −1]
T , une petite variation δx = [0.001, 0]
T
dans la solution induit de grandes variations dans b.
[Indication : d´ ecomposer le second membre sur la base des vecteurs propres
de la matrice.]
12. D´ eterminer le remplissage pour une matrice A ∈ R
n×n n’ayant des termes non
nuls que sur la diagonale principale, sur la premi` ere colonne et sur la derni` ere
ligne. Proposer une permutation qui minimise le remplissage.
[Indication : il suffit d’´ echanger la premi` ere ligne et la premi` ere colonne avec
la derni` ere ligne et la derni` ere colonne respectivement.]
13. Soit Hnx = b un syst` eme lin´ eaire o` u Hn est la matrice de Hilbert d’ordre n.
Estimer, en fonction de n, le nombre maximum de chiffres significatifs qu’on
peut attendre en r´ esolvant ce syst` eme avec la m´ ethode de Gauss.
14. Montrer que si A=QR alors
1
n
K1(A) ≤ K1(R) ≤ nK1(A),
et K2(A) = K2(R).