Soit f le polynôme caractéristique de (
t
A)A. L’équation f (1/x) = 0 a pour solutions
les inverses des racines de f et 1/λ min est la plus grande de ces solutions. Posons
g(x)=x
n f (1/x), où n=degf est la taille de la matrice (
t A)A ; alors g est un polynôme
de degré n et l’on peut calculer 1/λ min en appliquant la méthode de Newton à g.
Estimation pratique. La formule de la proposition est valable pour toutes les perturbations dB du second membre, notamment celles qui provoquent la plus grande
variation sur la solution X ; mais dans la pratique, un vecteur dB au hasard ne
provoquera que des variations dX nettement inférieures au maximum prévu par le
conditionnement. On se contente donc souvent d’estimer numériquement un coefficient C(A) tel que l’inégalité
dX
X
C(A)
dB
B
soit valable pour suffisamment de
second membres B et suffisamment de perturbations dB prises au hasard :
® on génère un assez grand nombre de vecteurs B et dB au hasard,
® on résout les équations AX = B et A(X + dX) = B + dB ,
® on prend comme valeur de C(A) le plus grand des nombres
dX
X
dB
B
−1
.
Le nombre C(A) est en général bien inférieur au conditionnement, mais, en pratique,
il n’est pas déraisonnable de l’utiliser pour des calculs d’erreurs.
2. Résolution d'équations linéaires
Dans ce paragraphe, on considère des équations linéaires AX = B , où A est une
matrice inversible de taille n à coefficients réels ou complexes.
2.1 Factorisation LU
Lorsque la matrice A est triangulaire, l’équation linéaire AX = B se résout facilement : si par exemple A est triangulaire inférieure, la première équation fournit x 1 ,
première coordonnée de la solution X = (x 1 , x 2 , . . . , x n ), puis en reportant dans la
deuxième équation, on obtient x 2 et ainsi de suite ; si A est triangulaire supérieure,
il faut commencer par la dernière équation et remonter jusqu’à la première.
Prenons une matrice A produit de matrices triangulaires, par exemple A = LU , où
L est triangulaire inférieure et U triangulaire supérieure. Puisque A est inversible,
L et U le sont aussi : en effet, det A = (det L)(det U ) est non nul, donc L et U ont
des déterminants non nuls. Si C est le vecteur tel que LC = B, alors on a
AX = B ⇐⇒ LU X = LC ⇐⇒ UX = C , car L est inversible.
La résolution de l’équation AX = B peut donc s’opérer en deux étapes plus simples :
® résolution de l’équation triangulaire LC = B,
® puis résolution de l’équation triangulaire UX = C .
246 – R ´
ESOLUTION D’ ´
EQUATIONS LIN ´
EAIRES
t
A)A. L’équation f (1/x) = 0 a pour solutions
les inverses des racines de f et 1/λ min est la plus grande de ces solutions. Posons
g(x)=x
n f (1/x), où n=degf est la taille de la matrice (
t A)A ; alors g est un polynôme
de degré n et l’on peut calculer 1/λ min en appliquant la méthode de Newton à g.
Estimation pratique. La formule de la proposition est valable pour toutes les perturbations dB du second membre, notamment celles qui provoquent la plus grande
variation sur la solution X ; mais dans la pratique, un vecteur dB au hasard ne
provoquera que des variations dX nettement inférieures au maximum prévu par le
conditionnement. On se contente donc souvent d’estimer numériquement un coefficient C(A) tel que l’inégalité
dX
X
C(A)
dB
B
soit valable pour suffisamment de
second membres B et suffisamment de perturbations dB prises au hasard :
® on génère un assez grand nombre de vecteurs B et dB au hasard,
® on résout les équations AX = B et A(X + dX) = B + dB ,
® on prend comme valeur de C(A) le plus grand des nombres
dX
X
dB
B
−1
.
Le nombre C(A) est en général bien inférieur au conditionnement, mais, en pratique,
il n’est pas déraisonnable de l’utiliser pour des calculs d’erreurs.
2. Résolution d'équations linéaires
Dans ce paragraphe, on considère des équations linéaires AX = B , où A est une
matrice inversible de taille n à coefficients réels ou complexes.
2.1 Factorisation LU
Lorsque la matrice A est triangulaire, l’équation linéaire AX = B se résout facilement : si par exemple A est triangulaire inférieure, la première équation fournit x 1 ,
première coordonnée de la solution X = (x 1 , x 2 , . . . , x n ), puis en reportant dans la
deuxième équation, on obtient x 2 et ainsi de suite ; si A est triangulaire supérieure,
il faut commencer par la dernière équation et remonter jusqu’à la première.
Prenons une matrice A produit de matrices triangulaires, par exemple A = LU , où
L est triangulaire inférieure et U triangulaire supérieure. Puisque A est inversible,
L et U le sont aussi : en effet, det A = (det L)(det U ) est non nul, donc L et U ont
des déterminants non nuls. Si C est le vecteur tel que LC = B, alors on a
AX = B ⇐⇒ LU X = LC ⇐⇒ UX = C , car L est inversible.
La résolution de l’équation AX = B peut donc s’opérer en deux étapes plus simples :
® résolution de l’équation triangulaire LC = B,
® puis résolution de l’équation triangulaire UX = C .
246 – R ´
ESOLUTION D’ ´
EQUATIONS LIN ´
EAIRES