Pratique des calculs
On calcule les matrices L
(k) et U
(k) de proche en proche, jusqu’à L=L
(n) et U =U
(n) :
® L
(1) = [ 1 ] et U
(1) = A
(1) ;
® Si l’on a calculé L
(k) et U
(k) , on pose comme dans la démonstration précédente :
L
(k+1) =
L
(k) 0
X 1
, U
(k+1) =
U
(k) Y
0 u
et A
(k+1) =
A
(k) P
Q a
,
avec a et u des scalaires ; on calcule alors la matrice-colonne X et la matrice-ligne
Y en résolvant les équations L
(k) Y = P , XU
(k) = Q, puis on obtient le scalaire u
au moyen de l’égalité XY + u = a.
Pour calculer L et U lorsque A est de grande taille n, le nombre d’opérations à
effectuer (additions, multiplications et divisions) est de l’ordre de n
3 .
2.2 Méthode de relaxation
Au lieu de résoudre algébriquement l’équation linéaire AX = B, on peut chercher
à approcher la solution par des vecteurs X
(0) , X
(1) , . . . , X
(k) , . . . qui tendent vers la
solution. Voici une méthode couramment pratiquée pour construire une telle suite.
Hypothèse générale : la matrice A = [a ij ] est inversible et ses coefficients diagonaux
a ii sont tous non nuls.
On note b 1 , b 2 , . . . , b n les coordonnées du vecteur B.
Construction des vecteurs X (k)
Pour définir une méthode de relaxation, on se donne un nombre ω tel que 0 < ω < 2.
® On choisit un vecteur initial X
(0) .
® On passe de X
(k) = (x
(k)
1 , x
(k)
2 , . . . , x
(k)
n ) à X
(k+1) = (x
(k+1)
1
, x
(k+1)
2
, . . . , x
(k+1)
n
) en
appliquant la formule suivante pour i = 1, 2, . . . , n :
(1)
x
(k+1)
i
= x
(k)
i + ω
a ii
b i −
i−1
j=1
a ij x
(k+1)
j
−
n
j=i
a ij x
(k)
j
où l’on convient que si i = 1, le signe
i−1
j=1 donne comme résultat 0.
Par cette formule, on calcule successivement x
(k+1)
1
,x
(k+1)
2
,. . .,x
(k+1)
n
, connaissant X
(k) .
Supposons que les vecteurs X
(k) tendent vers une limite X quand k tend vers l’infini.
Pour chaque valeur fixée de i, on peut passer à la limite dans l’égalité (1) : en notant
x 1 ,x 2 ,. . .,x n les coordonnées de la limite X , on obtient x i =x i + ω
a ii
b i −
n
j=1 a ij x j
,
donc 0 = b i −
n
j=1 a ij x j ; puisque la somme est la i-ième coordonnée de AX , on
a B = AX . Cela montre que
si les vecteurs X
(k) ont une limite, cette limite est la solution de l’équation AX = B.
248 – R ´
ESOLUTION D’ ´
EQUATIONS LIN ´
EAIRES
On calcule les matrices L
(k) et U
(k) de proche en proche, jusqu’à L=L
(n) et U =U
(n) :
® L
(1) = [ 1 ] et U
(1) = A
(1) ;
® Si l’on a calculé L
(k) et U
(k) , on pose comme dans la démonstration précédente :
L
(k+1) =
L
(k) 0
X 1
, U
(k+1) =
U
(k) Y
0 u
et A
(k+1) =
A
(k) P
Q a
,
avec a et u des scalaires ; on calcule alors la matrice-colonne X et la matrice-ligne
Y en résolvant les équations L
(k) Y = P , XU
(k) = Q, puis on obtient le scalaire u
au moyen de l’égalité XY + u = a.
Pour calculer L et U lorsque A est de grande taille n, le nombre d’opérations à
effectuer (additions, multiplications et divisions) est de l’ordre de n
3 .
2.2 Méthode de relaxation
Au lieu de résoudre algébriquement l’équation linéaire AX = B, on peut chercher
à approcher la solution par des vecteurs X
(0) , X
(1) , . . . , X
(k) , . . . qui tendent vers la
solution. Voici une méthode couramment pratiquée pour construire une telle suite.
Hypothèse générale : la matrice A = [a ij ] est inversible et ses coefficients diagonaux
a ii sont tous non nuls.
On note b 1 , b 2 , . . . , b n les coordonnées du vecteur B.
Construction des vecteurs X (k)
Pour définir une méthode de relaxation, on se donne un nombre ω tel que 0 < ω < 2.
® On choisit un vecteur initial X
(0) .
® On passe de X
(k) = (x
(k)
1 , x
(k)
2 , . . . , x
(k)
n ) à X
(k+1) = (x
(k+1)
1
, x
(k+1)
2
, . . . , x
(k+1)
n
) en
appliquant la formule suivante pour i = 1, 2, . . . , n :
(1)
x
(k+1)
i
= x
(k)
i + ω
a ii
b i −
i−1
j=1
a ij x
(k+1)
j
−
n
j=i
a ij x
(k)
j
où l’on convient que si i = 1, le signe
i−1
j=1 donne comme résultat 0.
Par cette formule, on calcule successivement x
(k+1)
1
,x
(k+1)
2
,. . .,x
(k+1)
n
, connaissant X
(k) .
Supposons que les vecteurs X
(k) tendent vers une limite X quand k tend vers l’infini.
Pour chaque valeur fixée de i, on peut passer à la limite dans l’égalité (1) : en notant
x 1 ,x 2 ,. . .,x n les coordonnées de la limite X , on obtient x i =x i + ω
a ii
b i −
n
j=1 a ij x j
,
donc 0 = b i −
n
j=1 a ij x j ; puisque la somme est la i-ième coordonnée de AX , on
a B = AX . Cela montre que
si les vecteurs X
(k) ont une limite, cette limite est la solution de l’équation AX = B.
248 – R ´
ESOLUTION D’ ´
EQUATIONS LIN ´
EAIRES