5.3 Factorisation LU
137
Table 5.1. Temps nécessaire à la résolution d’un système linéaire de dimension n avec la formule de Cramer, “h.l.” désigne des durées hors de limites
raisonnables
No. de flops de l’ordinateur
n
10
9 (Giga)
10
10
10
11
10
12 (Tera)
10
15 (Peta)
10
10
−1 sec
10
−2 sec
10
−3 sec
10
−4 sec
négligeable
15
17 heures
1.74 heures
10.46 min
1 min
0.6 10
−1 sec
20
4860 ans
486 ans
48.6 ans
4.86 ans
1.7 jour
25
h.l.
h.l.
h.l.
h.l.
38365 ans
dans l’Exemple 1.3. Néanmoins, ce coût est encore trop élevé pour les
grandes valeurs de n qu’on rencontre souvent en pratique.
Deux classes de méthodes sont utilisées : les méthodes directes, qui
donnent la solution en un nombre fini d’étapes, et les méthodes itératives,
qui nécessitent (théoriquement) un nombre infini d’étapes. Les méthodes
itératives seront traitées à la Section 5.9. Le lecteur doit être conscient
que le choix entre méthodes directes et itératives dépend de nombreux
critères : l’efficacité théorique de l’algorithme, le type de matrice, la capacité de stockage en mémoire, l’architecture de l’ordinateur (voir Section
5.13 pour plus de détails).
Notons enfin qu’un système associé à une matrice pleine ne peut
pas être résolu par moins de n
2 opérations. En effet, si les équations sont
toutes couplées, on peut s’attendre à ce que chacun des n
2 coefficients de
la matrice soit impliqué au moins une fois dans une opération algébrique.
Bien que la plupart des méthodes de cette section soient applicables
aux matrices complexes, nous restreindrons notre analyse aux matrices
réelles. Noter que MATLAB et Octave traitent indifféremment les systèmes réels et complexes, sans qu’on ait à modifier les instructions utilisées.
Parfois, les hypothèses faites pour les matrices réelles doivent être
adaptées dans le cas complexe. Nous indiquerons ces situations. Ce sera
le cas par exemple pour définir la notion de matrice définie positive, ou
pour définir le cadre de la factorisation de Cholesky d’une matrice.
5.3 Factorisation LU
Soit A∈ R
n×n . Supposons qu’il existe deux matrices, L et U, respectivement triangulaire inférieure et supérieure, telles que
A = LU
(5.7)
On appelle (5.7) factorisation (ou décomposition) LU de A. Si A est
régulière, alors L et U le sont aussi, et leurs termes diagonaux sont donc
non nuls (comme vu à la Section 1.4).
137
Table 5.1. Temps nécessaire à la résolution d’un système linéaire de dimension n avec la formule de Cramer, “h.l.” désigne des durées hors de limites
raisonnables
No. de flops de l’ordinateur
n
10
9 (Giga)
10
10
10
11
10
12 (Tera)
10
15 (Peta)
10
10
−1 sec
10
−2 sec
10
−3 sec
10
−4 sec
négligeable
15
17 heures
1.74 heures
10.46 min
1 min
0.6 10
−1 sec
20
4860 ans
486 ans
48.6 ans
4.86 ans
1.7 jour
25
h.l.
h.l.
h.l.
h.l.
38365 ans
dans l’Exemple 1.3. Néanmoins, ce coût est encore trop élevé pour les
grandes valeurs de n qu’on rencontre souvent en pratique.
Deux classes de méthodes sont utilisées : les méthodes directes, qui
donnent la solution en un nombre fini d’étapes, et les méthodes itératives,
qui nécessitent (théoriquement) un nombre infini d’étapes. Les méthodes
itératives seront traitées à la Section 5.9. Le lecteur doit être conscient
que le choix entre méthodes directes et itératives dépend de nombreux
critères : l’efficacité théorique de l’algorithme, le type de matrice, la capacité de stockage en mémoire, l’architecture de l’ordinateur (voir Section
5.13 pour plus de détails).
Notons enfin qu’un système associé à une matrice pleine ne peut
pas être résolu par moins de n
2 opérations. En effet, si les équations sont
toutes couplées, on peut s’attendre à ce que chacun des n
2 coefficients de
la matrice soit impliqué au moins une fois dans une opération algébrique.
Bien que la plupart des méthodes de cette section soient applicables
aux matrices complexes, nous restreindrons notre analyse aux matrices
réelles. Noter que MATLAB et Octave traitent indifféremment les systèmes réels et complexes, sans qu’on ait à modifier les instructions utilisées.
Parfois, les hypothèses faites pour les matrices réelles doivent être
adaptées dans le cas complexe. Nous indiquerons ces situations. Ce sera
le cas par exemple pour définir la notion de matrice définie positive, ou
pour définir le cadre de la factorisation de Cholesky d’une matrice.
5.3 Factorisation LU
Soit A∈ R
n×n . Supposons qu’il existe deux matrices, L et U, respectivement triangulaire inférieure et supérieure, telles que
A = LU
(5.7)
On appelle (5.7) factorisation (ou décomposition) LU de A. Si A est
régulière, alors L et U le sont aussi, et leurs termes diagonaux sont donc
non nuls (comme vu à la Section 1.4).