5.3 Factorisation LU
139
Exemple 5.1 Ecrivons la relation (5.7) pour une matrice quelconque A ∈
R
2×2
l11 0
l21 l22
u11 u12
0 u22
=
a11 a12
a21 a22
.
Les 6 éléments inconnus de L et U doivent vérifier les équations (nonlinéaires) suivantes
(e1) l11u11 = a11, (e2) l11u12 = a12,
(e3) l21u11 = a21, (e4) l21u12 + l22u22 = a22.
(5.11)
Le système (5.11) est sous-déterminé puisqu’il comporte moins d’équations
que d’inconnues. On peut le compléter en fixant arbitrairement les valeurs des
coefficients diagonaux de L, par exemple en posant l11 = 1 et l22 = 1. Le
système (5.11) peut alors être résolu de la manière suivante : on détermine
les éléments u11 et u12 de la première ligne de U en utilisant (e1) et (e2). Si
u11 est non nul, on déduit l21 de (e3) (c’est-à-dire la première colonne de L,
puisque l11 est déjà connu). On obtient alors, avec (e4), le seul élément non
nul u22 de la deuxième ligne de U.
Exemple 5.2 Reprenons les calculs dans le cas d’une matrice 3 × 3. Pour
déterminer les 12 coefficients inconnus de L et U, on dispose des 9 équations
suivantes
(e1) l11u11 = a11, (e2) l11u12 = a12,
(e3) l11u13 = a13,
(e4) l21u11 = a21, (e5) l21u12 +l22u22 = a22, (e6) l21u13 +l22u23 = a23,
(e7) l31u11 = a31, (e8) l31u12 +l32u22 = a32, (e9) l31u13 +l32u23 +l33u33 = a33.
Complétons ce système en posant lii = 1 pour i = 1, 2, 3. Les coefficients
de la première ligne de U sont alors obtenus avec (e1), (e2) et (e3). Ensuite,
en utilisant (e4) et (e7), on détermine les coefficients l21 et l31 de la première
colonne de L. Avec (e5) et (e6), on peut alors calculer les coefficients u22 et
u23 de la deuxième ligne de U. Puis, avec (e8), on détermine le coefficient l32
de la seconde colonne de L. Enfin, la dernière ligne de U (qui se résume au
seul élément u33) est obtenue en résolvant (e9).
Pour une matrice quelconque A∈ R
n×n de dimension n, on procède
ainsi :
1. les éléments de L et U satisfont le système d’équations non linéaires
min(i,j)
r=1
l ir u rj = a ij , i, j = 1, . . ., n;
(5.12)
2. le système (5.12) est sous-déterminé ; il y a en effet n
2 équations et
n
2 + n inconnues, la factorisation LU ne peut donc être unique ; il
existe même une infinité de matrices L et U satisfaisant (5.12) ;
139
Exemple 5.1 Ecrivons la relation (5.7) pour une matrice quelconque A ∈
R
2×2
l11 0
l21 l22
u11 u12
0 u22
=
a11 a12
a21 a22
.
Les 6 éléments inconnus de L et U doivent vérifier les équations (nonlinéaires) suivantes
(e1) l11u11 = a11, (e2) l11u12 = a12,
(e3) l21u11 = a21, (e4) l21u12 + l22u22 = a22.
(5.11)
Le système (5.11) est sous-déterminé puisqu’il comporte moins d’équations
que d’inconnues. On peut le compléter en fixant arbitrairement les valeurs des
coefficients diagonaux de L, par exemple en posant l11 = 1 et l22 = 1. Le
système (5.11) peut alors être résolu de la manière suivante : on détermine
les éléments u11 et u12 de la première ligne de U en utilisant (e1) et (e2). Si
u11 est non nul, on déduit l21 de (e3) (c’est-à-dire la première colonne de L,
puisque l11 est déjà connu). On obtient alors, avec (e4), le seul élément non
nul u22 de la deuxième ligne de U.
Exemple 5.2 Reprenons les calculs dans le cas d’une matrice 3 × 3. Pour
déterminer les 12 coefficients inconnus de L et U, on dispose des 9 équations
suivantes
(e1) l11u11 = a11, (e2) l11u12 = a12,
(e3) l11u13 = a13,
(e4) l21u11 = a21, (e5) l21u12 +l22u22 = a22, (e6) l21u13 +l22u23 = a23,
(e7) l31u11 = a31, (e8) l31u12 +l32u22 = a32, (e9) l31u13 +l32u23 +l33u33 = a33.
Complétons ce système en posant lii = 1 pour i = 1, 2, 3. Les coefficients
de la première ligne de U sont alors obtenus avec (e1), (e2) et (e3). Ensuite,
en utilisant (e4) et (e7), on détermine les coefficients l21 et l31 de la première
colonne de L. Avec (e5) et (e6), on peut alors calculer les coefficients u22 et
u23 de la deuxième ligne de U. Puis, avec (e8), on détermine le coefficient l32
de la seconde colonne de L. Enfin, la dernière ligne de U (qui se résume au
seul élément u33) est obtenue en résolvant (e9).
Pour une matrice quelconque A∈ R
n×n de dimension n, on procède
ainsi :
1. les éléments de L et U satisfont le système d’équations non linéaires
min(i,j)
r=1
l ir u rj = a ij , i, j = 1, . . ., n;
(5.12)
2. le système (5.12) est sous-déterminé ; il y a en effet n
2 équations et
n
2 + n inconnues, la factorisation LU ne peut donc être unique ; il
existe même une infinité de matrices L et U satisfaisant (5.12) ;