5. Systèmes linéaires
105
L’algorithme consiste alors à remplacer à chaque étape la matrice D par
une matrice D
(n)
dont les n-ièmes premiers vecteurs colonnes correspondent
au début d’une matrice triangulaire. À la (n +1)-ième étape, on conserve
les n premières lignes et les (n 1) premières colonnes de D
(n)
d
(n+1)
lm
= d
(n)
lm
d
(n)
ln
d
(n)
nn
d
(n)
nm
l = n +1> ===> q et m = n +1> ===> q
d
(n+1)
ln
=0
l = n +1> ===> q
e
(n+1)
l
= e
(n)
l
d
(n)
ln
d
(n)
nn
e
(n)
n
En pratique, si le pivot, c’est-à-dire l’élément d
(n)
nn situé à la n-ième ligne
et à la n-ième colonne, est petit ou nul, l’algorithme n’est plus valable.
On emploie dans ce cas des permutations de lignes et de colonnes appelées
stratégies de pivot (voir le paragraphe Problème des pivots).
Exemple. Considérons le système linéaire
3
C
284
21 06
182
4
D
3
C
{
|
}
4
D =
3
C
1
1
1
4
D
À la première étape, on fait apparaître le vecteur (1> 0>===>0) à la première
colonne. Pour cela, on divise la première ligne par 2 (le terme d 11 =2est
pris comme pivot) et on retranche la première ligne aux autres lignes de la
matrice, soit
3
C
142
022
040
4
D
3
C
{
|
}
4
D =
3
C
1@2
0
1@2
4
D
À la deuxième étape, on poursuit la triangulation en annulant les termes
situés sous la diagonale. On divise la deuxième ligne par 2 (d 22 est pris
comme pivot) et on retranche la deuxième ligne multipliée par 4 à la troisième, de façon à faire apparaître un zéro en troisième ligne et deuxième
colonne
3
C
14 2
01 1
004
4
D
3
C
{
|
}
4
D =
3
C
1@2
0
1@2
4
D
À la troisième étape, on divise la troisième ligne par -4 (d 33 )a fi nd ’ a v o i r
une matrice triangulaire n’ayant que des 1 sur la diagonale
3
C
142
011
001
4
D
3
C
{
|
}
4
D =
3
C
1@2
0
1@8
4
D