3.2 R´ esolution d’un syst` eme triangulaire
71
par les erreurs d’arrondi dans la r´ esolution d’un syst` eme triangulaire peuvent
donc ˆ etre n´ eglig´ ees. Par cons´ equent, la pr´ ecision des solutions calcul´ ees par les
algorithmes de substitution directe et r´ etrograde est g´ en´ eralement tr` es ´ elev´ ee.
Ces r´ esultats peuvent ˆ etre encore am´ elior´ es en faisant des hypoth` eses suppl´ ementaires sur les coefficients de L ou U. En particulier, si les coefficients
de U sont tels que |u ii | ≥ |u ij | pour tout j > i, alors
|x i −
x i | ≤ 2
n−i+1 nu
1 − nu
max
j≥i
| x j |,
1 ≤ i ≤ n.
On a le mˆ eme r´ esultat si T=L quand |l ii | ≥ |l ij | pour tout j < i, ou si L et U
sont `
a diagonale dominante. Les estimations pr´ ec´ edentes seront utilis´ ees dans
les Sections 3.3.1 et 3.4.2.
Pour les d´ emonstrations des r´ esultats que nous venons d’´ enoncer, voir
[FM67], [Hig89] et [Hig88].
3.2.3 Inverse d’une matrice triangulaire
On peut employer l’algorithme (3.20) (resp. (3.19)) pour calculer explicitement
l’inverse d’une matrice triangulaire sup´ erieure (resp. inf´ erieure). En effet, ´ etant
donn´ e une matrice triangulaire sup´ erieure inversible U, les vecteurs colonnes
v i de l’inverse V=(v 1 , . . . , v n ) de U satisfont les syst` emes lin´ eaires suivants
Uv i = e i , i = 1, . . . , n,
(3.23)
o` u {e i } est la base canonique de R
n (d´ efinie dans l’Exemple 1.2). Le calcul
des v i n´ ecessite donc d’appliquer n fois l’algorithme (3.20) `
a (3.23).
Cette proc´ edure est assez inefficace puisqu’au moins la moiti´ e des ´ el´ ements
de l’inverse de U sont nuls. Nous allons tirer avantage de ceci. Notons v
k =
(v
1k , . . . , v
kk )
T le vecteur de taille k tel que
U
(k) v
k = l k k = 1, . . . , n,
(3.24)
o` u les U
(k) sont les sous-matrices principales de U d’ordre k et l k est le vecteur
de R
k dont le premier ´ el´ ement vaut 1 et les autres 0. Les syst` emes (3.24) sont
triangulaires sup´ erieurs d’ordre k et ils peuvent ˆ etre ` a nouveau r´ esolus en
utilisant la m´ ethode (3.20). L’algorithme d’inversion des matrices triangulaires
sup´ erieures s’´ ecrit : pour k = n, n − 1, . . . , 1, calculer
v
kk = u
−1
kk ,
v
ik = −u
−1
ii
k
j=i+1
u ij v
jk , pour i = k − 1, k − 2, . . . , 1.
(3.25)
A la fin de cette proc´ edure, les vecteurs v
k fournissent les termes non nuls
des colonnes de U
−1 . L’algorithme n´ ecessite environ n
3 /3 + (3/4)n
2 flops. A
nouveau `
a cause des erreurs d’arrondi, l’algorithme (3.25) ne donne pas la
solution exacte, mais une approximation de celle-ci. On peut ´ evaluer l’erreur
introduite en utilisant l’analyse a priori r´ etrograde effectu´ ee ` a la Section 3.1.3.
71
par les erreurs d’arrondi dans la r´ esolution d’un syst` eme triangulaire peuvent
donc ˆ etre n´ eglig´ ees. Par cons´ equent, la pr´ ecision des solutions calcul´ ees par les
algorithmes de substitution directe et r´ etrograde est g´ en´ eralement tr` es ´ elev´ ee.
Ces r´ esultats peuvent ˆ etre encore am´ elior´ es en faisant des hypoth` eses suppl´ ementaires sur les coefficients de L ou U. En particulier, si les coefficients
de U sont tels que |u ii | ≥ |u ij | pour tout j > i, alors
|x i −
x i | ≤ 2
n−i+1 nu
1 − nu
max
j≥i
| x j |,
1 ≤ i ≤ n.
On a le mˆ eme r´ esultat si T=L quand |l ii | ≥ |l ij | pour tout j < i, ou si L et U
sont `
a diagonale dominante. Les estimations pr´ ec´ edentes seront utilis´ ees dans
les Sections 3.3.1 et 3.4.2.
Pour les d´ emonstrations des r´ esultats que nous venons d’´ enoncer, voir
[FM67], [Hig89] et [Hig88].
3.2.3 Inverse d’une matrice triangulaire
On peut employer l’algorithme (3.20) (resp. (3.19)) pour calculer explicitement
l’inverse d’une matrice triangulaire sup´ erieure (resp. inf´ erieure). En effet, ´ etant
donn´ e une matrice triangulaire sup´ erieure inversible U, les vecteurs colonnes
v i de l’inverse V=(v 1 , . . . , v n ) de U satisfont les syst` emes lin´ eaires suivants
Uv i = e i , i = 1, . . . , n,
(3.23)
o` u {e i } est la base canonique de R
n (d´ efinie dans l’Exemple 1.2). Le calcul
des v i n´ ecessite donc d’appliquer n fois l’algorithme (3.20) `
a (3.23).
Cette proc´ edure est assez inefficace puisqu’au moins la moiti´ e des ´ el´ ements
de l’inverse de U sont nuls. Nous allons tirer avantage de ceci. Notons v
k =
(v
1k , . . . , v
kk )
T le vecteur de taille k tel que
U
(k) v
k = l k k = 1, . . . , n,
(3.24)
o` u les U
(k) sont les sous-matrices principales de U d’ordre k et l k est le vecteur
de R
k dont le premier ´ el´ ement vaut 1 et les autres 0. Les syst` emes (3.24) sont
triangulaires sup´ erieurs d’ordre k et ils peuvent ˆ etre ` a nouveau r´ esolus en
utilisant la m´ ethode (3.20). L’algorithme d’inversion des matrices triangulaires
sup´ erieures s’´ ecrit : pour k = n, n − 1, . . . , 1, calculer
v
kk = u
−1
kk ,
v
ik = −u
−1
ii
k
j=i+1
u ij v
jk , pour i = k − 1, k − 2, . . . , 1.
(3.25)
A la fin de cette proc´ edure, les vecteurs v
k fournissent les termes non nuls
des colonnes de U
−1 . L’algorithme n´ ecessite environ n
3 /3 + (3/4)n
2 flops. A
nouveau `
a cause des erreurs d’arrondi, l’algorithme (3.25) ne donne pas la
solution exacte, mais une approximation de celle-ci. On peut ´ evaluer l’erreur
introduite en utilisant l’analyse a priori r´ etrograde effectu´ ee ` a la Section 3.1.3.