9.5 Chapitre 5
327
d’où xn 3n!. Il est intéressant de rappeler que la formule de Cramer (voir
Section 5.2) requiert environ 3(n + 1)! opérations pour résoudre un système
linéaire d’ordre n avec une matrice pleine.
Solution 5.2 On utilise les commandes MATLAB suivantes pour calculer
les déterminants et les temps de calcul :
t = []; NN =3:500;
for n = NN
A = magic (n ); tt= cputime ; d= det( A ); t =[t , cputime - tt ];
end
Les coefficients du polynôme aux moindres carrés de degré 3 qui approche les
données NN=[3:500] et t sont :
c = polyfit (NN ,t ,3)
c =
1.4055e-10
7.1570e-08 -3.6686e-06
3.1897e-04
Si on calcule le polynôme aux moindres carrés de degré 4,
c = polyfit (NN ,t ,4)
on obtient les coefficients suivants :
c =
7.6406e-15
1.3286e-10
7.4064e-08 -3.9505e-06
3.2637e-04
Le coefficient de n
4 est donc proche de la précision machine, et les autres sont à
peu près inchangés par rapport à la projection sur P3. On déduit de ce résultat
que dans MATLAB le temps CPU nécessaire au calcul du déterminant d’une
matrice d’ordre n croît en n
3 .
Solution 5.3 En notant Ai la sous-matrice principale de A d’ordre i, on a :
detA1 = 1, detA2 = ε, detA3 = detA = 2ε + 12. Par conséquent, si ε = 0 la
seconde sous-matrice principale est singulière et la factorisation de Gauss de
A n’existe pas (voir Proposition 5.1). La matrice A est singulière si ε = −6.
Dans ce cas, la factorisation de Gauss existe et donne
L =
⎡
⎣
1 0
0
2 1
0
3 1.25 1
⎤
⎦ , U =
⎡
⎣
1 7
3
0 −12 −4
0 0
0
⎤
⎦ .
Remarquer que U est singulière (comme on pouvait s’y attendre puisque A est
singulière) et le système triangulaire supérieur Ux = y admet une infinité de
solutions. On ne peut pas appliquer l’algorithme de remontée (5.10) pour les
mêmes raisons.
Solution 5.4 Considérons l’algorithme 5.13. A l’étape k =1, on effectue n − 1
divisions pour calculer les termes l i1 , i = 2, . . . , n. Puis, (n−1)
2 multiplications
et (n − 1)
2 additions pour les nouveaux termes a
(2)
ij , i,j = 2, . . . , n. A l’étape
k =2, le nombre de divisions est (n − 2), celui de multiplications et d’additions
est (n − 2)
2 . A la dernière étape k =n − 1, on n’effectue plus qu’une seule
addition, une multiplication et une division. Ainsi, en utilisant les relations
327
d’où xn 3n!. Il est intéressant de rappeler que la formule de Cramer (voir
Section 5.2) requiert environ 3(n + 1)! opérations pour résoudre un système
linéaire d’ordre n avec une matrice pleine.
Solution 5.2 On utilise les commandes MATLAB suivantes pour calculer
les déterminants et les temps de calcul :
t = []; NN =3:500;
for n = NN
A = magic (n ); tt= cputime ; d= det( A ); t =[t , cputime - tt ];
end
Les coefficients du polynôme aux moindres carrés de degré 3 qui approche les
données NN=[3:500] et t sont :
c = polyfit (NN ,t ,3)
c =
1.4055e-10
7.1570e-08 -3.6686e-06
3.1897e-04
Si on calcule le polynôme aux moindres carrés de degré 4,
c = polyfit (NN ,t ,4)
on obtient les coefficients suivants :
c =
7.6406e-15
1.3286e-10
7.4064e-08 -3.9505e-06
3.2637e-04
Le coefficient de n
4 est donc proche de la précision machine, et les autres sont à
peu près inchangés par rapport à la projection sur P3. On déduit de ce résultat
que dans MATLAB le temps CPU nécessaire au calcul du déterminant d’une
matrice d’ordre n croît en n
3 .
Solution 5.3 En notant Ai la sous-matrice principale de A d’ordre i, on a :
detA1 = 1, detA2 = ε, detA3 = detA = 2ε + 12. Par conséquent, si ε = 0 la
seconde sous-matrice principale est singulière et la factorisation de Gauss de
A n’existe pas (voir Proposition 5.1). La matrice A est singulière si ε = −6.
Dans ce cas, la factorisation de Gauss existe et donne
L =
⎡
⎣
1 0
0
2 1
0
3 1.25 1
⎤
⎦ , U =
⎡
⎣
1 7
3
0 −12 −4
0 0
0
⎤
⎦ .
Remarquer que U est singulière (comme on pouvait s’y attendre puisque A est
singulière) et le système triangulaire supérieur Ux = y admet une infinité de
solutions. On ne peut pas appliquer l’algorithme de remontée (5.10) pour les
mêmes raisons.
Solution 5.4 Considérons l’algorithme 5.13. A l’étape k =1, on effectue n − 1
divisions pour calculer les termes l i1 , i = 2, . . . , n. Puis, (n−1)
2 multiplications
et (n − 1)
2 additions pour les nouveaux termes a
(2)
ij , i,j = 2, . . . , n. A l’étape
k =2, le nombre de divisions est (n − 2), celui de multiplications et d’additions
est (n − 2)
2 . A la dernière étape k =n − 1, on n’effectue plus qu’une seule
addition, une multiplication et une division. Ainsi, en utilisant les relations