68
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
La matrice ´ etant inversible, ses termes diagonaux l ii , i = 1, 2, 3 sont non
nuls. On peut donc d´ eterminer successivement les valeurs inconnues x i pour
i = 1, 2, 3 :
x 1 = b 1 /l 11 ,
x 2 = (b 2 − l 21 x 1 )/l 22 ,
x 3 = (b 3 − l 31 x 1 − l 32 x 2 )/l 33 .
Cet algorithme peut ˆ etre ´ etendu aux syst` emes n × n. On l’appelle substitution directe. Dans le cas d’un syst` eme Lx=b, o` u L est une matrice inversible
triangulaire inf´ erieure d’ordre n (n ≥ 2), la m´ ethode s’´ ecrit
x 1 =
b 1
l 11
,
x i =
1
l ii
⎛
⎝ b i −
i−1
j=1
l ij x j
⎞
⎠ , i = 2, . . . , n.
(3.19)
On appelle ces relations formules de “descente”. L’algorithme effectue n(n +
1)/2 multiplications et divisions et n(n − 1)/2 additions et soustractions. Le
nombre global d’op´ erations pour (3.19) est donc n
2 flops.
On traite de mani` ere analogue un syst` eme lin´ eaire Ux=b, o` u U est une
matrice inversible triangulaire sup´ erieure d’ordre n (n ≥ 2). Dans ce cas l’algorithme s’appelle substitution r´ etrograde et s’´ ecrit dans le cas g´ en´ eral
x n =
b n
u nn
,
x i =
1
u ii
⎛
⎝ b i −
n
j=i+1
u ij x j
⎞
⎠ , i = n − 1, . . . , 1
(3.20)
(formules de “remont´ ee”). Son coˆ ut est encore de n
2 flops.
3.2.1 Impl´ ementation des m´ ethodes de substitution
A l’´ etape i de l’algorithme (3.19), on effectue un produit scalaire entre le
vecteur ligne L(i, 1 : i − 1) (cette notation d´ esignant le vecteur obtenu en
extrayant de la matrice L les ´ el´ ements de la i-i` eme ligne depuis la premi` ere
jusqu’` a la (i-1)-i` eme colonne) et le vecteur colonne x(1 : i − 1). L’acc` es aux
´ el´ ements de la matrice L se fait donc par ligne ; pour cette raison, on dit que
l’algorithme de substitution directe impl´ ement´ e comme ci-dessus est orient´ e
ligne.
Son impl´ ementation est propos´ ee dans le Programme 1.
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
La matrice ´ etant inversible, ses termes diagonaux l ii , i = 1, 2, 3 sont non
nuls. On peut donc d´ eterminer successivement les valeurs inconnues x i pour
i = 1, 2, 3 :
x 1 = b 1 /l 11 ,
x 2 = (b 2 − l 21 x 1 )/l 22 ,
x 3 = (b 3 − l 31 x 1 − l 32 x 2 )/l 33 .
Cet algorithme peut ˆ etre ´ etendu aux syst` emes n × n. On l’appelle substitution directe. Dans le cas d’un syst` eme Lx=b, o` u L est une matrice inversible
triangulaire inf´ erieure d’ordre n (n ≥ 2), la m´ ethode s’´ ecrit
x 1 =
b 1
l 11
,
x i =
1
l ii
⎛
⎝ b i −
i−1
j=1
l ij x j
⎞
⎠ , i = 2, . . . , n.
(3.19)
On appelle ces relations formules de “descente”. L’algorithme effectue n(n +
1)/2 multiplications et divisions et n(n − 1)/2 additions et soustractions. Le
nombre global d’op´ erations pour (3.19) est donc n
2 flops.
On traite de mani` ere analogue un syst` eme lin´ eaire Ux=b, o` u U est une
matrice inversible triangulaire sup´ erieure d’ordre n (n ≥ 2). Dans ce cas l’algorithme s’appelle substitution r´ etrograde et s’´ ecrit dans le cas g´ en´ eral
x n =
b n
u nn
,
x i =
1
u ii
⎛
⎝ b i −
n
j=i+1
u ij x j
⎞
⎠ , i = n − 1, . . . , 1
(3.20)
(formules de “remont´ ee”). Son coˆ ut est encore de n
2 flops.
3.2.1 Impl´ ementation des m´ ethodes de substitution
A l’´ etape i de l’algorithme (3.19), on effectue un produit scalaire entre le
vecteur ligne L(i, 1 : i − 1) (cette notation d´ esignant le vecteur obtenu en
extrayant de la matrice L les ´ el´ ements de la i-i` eme ligne depuis la premi` ere
jusqu’` a la (i-1)-i` eme colonne) et le vecteur colonne x(1 : i − 1). L’acc` es aux
´ el´ ements de la matrice L se fait donc par ligne ; pour cette raison, on dit que
l’algorithme de substitution directe impl´ ement´ e comme ci-dessus est orient´ e
ligne.
Son impl´ ementation est propos´ ee dans le Programme 1.