138
5 Systèmes linéaires
Dans ce cas, résoudre Ax = b revient à résoudre deux systèmes
triangulaires
Ly = b, Ux = y
(5.8)
Les deux systèmes sont faciles à résoudre. En effet, L étant triangulaire
inférieure, la première ligne du système Ly = b est de la forme
l 11 y 1 = b 1 ,
ce qui donne la valeur de y 1 puisque l 11 = 0. En substituant cette valeur
de y 1 dans les n − 1 équations suivantes, on obtient un nouveau système
dont les inconnues sont y 2 , . . ., y n , pour lesquelles on peut faire de même.
En procédant équation par équation, on calcule ainsi toutes les inconnues
par l’algorithme dit de descente
y 1 =
1
l 11
b 1 ,
y i =
1
l ii
⎛
⎝ b i −
i−1
j=1
l ij y j
⎞
⎠ , i = 2, . . . , n
(5.9)
Evaluons le nombre d’opérations requis par (5.9). On effectue i − 1
sommes, i−1 produits et 1 division pour calculer l’inconnue y i . Le nombre
total d’opérations est donc
n
i=1
1 + 2
n
i=1
(i − 1) = 2
n
i=1
i − n = n
2 .
On peut résoudre le système Ux = y de manière similaire. Cette
fois, on commence par déterminer x n puis, puis de proche en proche, les
autres inconnues x i , de i = n − 1 à i = 1
x n =
1
u nn
y n ,
x i =
1
u ii
⎛
⎝ y i −
n
j=i+1
u ij x j
⎞
⎠ , i = n − 1, . . ., 1
(5.10)
C’est l’algorithme de remontée. Il nécessite également n
2 opérations.
Il reste à présent à trouver un algorithme qui permette le calcul
effectif des facteurs L et U. Illustrons le procédé général en commençant
par deux exemples.