5. Systèmes linéaires
111
d’où, en posant f 0 =0et x 0 =1
G q =
q
Y
l=1
x l =
q
Y
l=1
(e l d l
f l1
x l1
)
5.2.6 Méthode de Cholesky
La méthode d’André-Louis Cholesky (1875-1918) s’applique aux matrices
hermitiennes ou symétriques. Elle est fondée sur le théorème suivant qui
a!rme que pour une matrice hermitienne (resp. symétrique) définie positive
D, il existe (au moins) une matrice triangulaire supérieure inversible X
telle que D = X
X (resp. D = X
w X ). Si les éléments diagonaux de X sont
strictement positifs, la matrice X est unique. Ce théorème est valable pour
une matrice triangulaire inférieure. Soit D une matrice symétrique définie
positive à coe!cients réels, mettons D sous la forme D = O
w O en appliquant
l’algorithme à la l-ième étape, on calcule la matrice O par
o lm =(d lm
m1 P
n=1
o ln o nm )@o mm
m =1> ===> l 1
o ll =(d lm
l1 P
n=1
o
2
ln )
1@2
On résout ensuite le système O| = e puis O
w { = | par un double balayage
| l =(e l
l1 P
n=1
o ln | n )@o ll
l =1>===>q
{ l =(| m
q
P
n=l+1
o nl { n )@o ll
5.2.7 Méthode de Householder. Factorisation QR
La méthode de triangularisation de Householder pour la résolution du
système D{ = e consiste à trouver (q1) matrices de Householder K 1 >===>K q
telles que la matrice produit K q1 === K 2 K 1 D soit triangulaire supérieure.
On résout alors le système par la méthode de remontée. La méthode repose
sur la factorisation QR qui a!rme que pour une matrice carrée d’ordre q
àcoe!cients complexes, il existe une matrice unitaire unique T et une matrice triangulaire supérieure, à éléments diagonaux positifs ou nuls, telles
que D = TU.S iD est inversible, la décomposition est unique. Si D est une
matrice de Hessenberg supérieure, T est aussi une matrice de Hessenberg
supérieure. Soit { un vecteur colonne non nul, { 5 C
q \{0},u n em a t r i c e
de Householder est une matrice de la forme
K({)=L
2
{ ={
{={