108
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
notons x
(0) la solution calcul´ ee. Ayant pr´ ealablement fix´ e une tol´ erance tol
pour l’erreur, le raffinement it´ eratif consiste ` a effectuer les ´ etapes suivantes
jusqu’` a convergence : pour i = 0, 1, . . .,
1. calculer le r´ esidu r
(i) = b − Ax
(i) ;
2. r´ esoudre le syst` eme lin´ eaire Az = r
(i) en utilisant la factorisation LU de
A ;
3. mettre ` a jour la solution en posant x
(i+1) = x
(i) + z ;
4. si z/x
(i+1)
< tol, sortir de la boucle et renvoyer la solution x
(i+1) .
Sinon, retourner `
a l’´ etape 1.
En l’absence d’erreur d’arrondi, l’algorithme s’arrˆ ete ` a la premi` ere ´ etape et
donne la solution exacte. Les propri´ et´ es de convergence de la m´ ethode peuvent
ˆ etre am´ elior´ ees en calculant le r´ esidu r
(i) en double pr´ ecision, et les autres
quantit´ es en simple pr´ ecision. Nous appelons cette proc´ edure raffinement it´ eratif en pr´ ecision mixte (RPM en abr´ eg´ e), par opposition au raffinement it´ eratif en pr´ ecision fixe (RPF).
On peut montrer que, si |A
−1
| |
L| |
U| | ∞ est assez petit, alors, ` a chaque
´ etape i de l’algorithme, l’erreur relative x − x
(i)
∞ /x ∞ est diminu´ ee d’un
facteur ρ donn´ e par
ρ 2 n cond(A, x)u (RPF),
ou
ρ u
(RPM).
Remarquer que ρ est ind´ ependant du conditionnement de A dans le cas RPM.
Une convergence lente de RPF est une indication claire du grand conditionnement de la matrice : si p est le nombre d’it´ erations n´ ecessaires ` a la convergence
de la m´ ethode, on peut montrer que K ∞ (A) β
t(1−1/p) .
Mˆ eme quand il est effectu´ e en pr´ ecision fixe, le raffinement it´ eratif est utile
dans la mesure o` u il am´ eliore la stabilit´ e globale des m´ ethodes directes pour la
r´ esolution d’un syst` eme. Nous renvoyons le lecteur ` a [Ric81], [Ske80], [JW77]
[Ste73], [Wil63] et [CMSW79] pour davantage de renseignements sur ce sujet.
3.12 Syst` emes ind´ etermin´ es
Nous avons vu que si n = m et si A est inversible alors la solution du syst` eme
lin´ eaire Ax=b existe et est unique. Dans cette section, nous donnons un sens
` a la solution d’un syst` eme surd´ etermin´ e, i.e. quand m > n, et sousd´ etermin´ e,
i.e. quand m < n. Notons qu’un syst` eme ind´ etermin´ e n’a g´ en´ eralement pas
de solution `
a moins que le second membre b n’appartienne `
a Im(A).
Nous renvoyons `
a [LH74], [GL89] et [Bj¨ o88] pour une pr´ esentation plus d´ etaill´ ee.
Etant donn´ e A∈ R
m×n avec m ≥ n, et b∈ R
m , on dit que x
∗
∈ R
n est
une solution du syst` eme lin´ eaire Ax=b au sens des moindres carr´ es si
Φ(x
∗ ) ≤ min
x∈R n
Φ(x),
o` u Φ(x) = Ax − b
2
2 .
(3.62)
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
notons x
(0) la solution calcul´ ee. Ayant pr´ ealablement fix´ e une tol´ erance tol
pour l’erreur, le raffinement it´ eratif consiste ` a effectuer les ´ etapes suivantes
jusqu’` a convergence : pour i = 0, 1, . . .,
1. calculer le r´ esidu r
(i) = b − Ax
(i) ;
2. r´ esoudre le syst` eme lin´ eaire Az = r
(i) en utilisant la factorisation LU de
A ;
3. mettre ` a jour la solution en posant x
(i+1) = x
(i) + z ;
4. si z/x
(i+1)
< tol, sortir de la boucle et renvoyer la solution x
(i+1) .
Sinon, retourner `
a l’´ etape 1.
En l’absence d’erreur d’arrondi, l’algorithme s’arrˆ ete ` a la premi` ere ´ etape et
donne la solution exacte. Les propri´ et´ es de convergence de la m´ ethode peuvent
ˆ etre am´ elior´ ees en calculant le r´ esidu r
(i) en double pr´ ecision, et les autres
quantit´ es en simple pr´ ecision. Nous appelons cette proc´ edure raffinement it´ eratif en pr´ ecision mixte (RPM en abr´ eg´ e), par opposition au raffinement it´ eratif en pr´ ecision fixe (RPF).
On peut montrer que, si |A
−1
| |
L| |
U| | ∞ est assez petit, alors, ` a chaque
´ etape i de l’algorithme, l’erreur relative x − x
(i)
∞ /x ∞ est diminu´ ee d’un
facteur ρ donn´ e par
ρ 2 n cond(A, x)u (RPF),
ou
ρ u
(RPM).
Remarquer que ρ est ind´ ependant du conditionnement de A dans le cas RPM.
Une convergence lente de RPF est une indication claire du grand conditionnement de la matrice : si p est le nombre d’it´ erations n´ ecessaires ` a la convergence
de la m´ ethode, on peut montrer que K ∞ (A) β
t(1−1/p) .
Mˆ eme quand il est effectu´ e en pr´ ecision fixe, le raffinement it´ eratif est utile
dans la mesure o` u il am´ eliore la stabilit´ e globale des m´ ethodes directes pour la
r´ esolution d’un syst` eme. Nous renvoyons le lecteur ` a [Ric81], [Ske80], [JW77]
[Ste73], [Wil63] et [CMSW79] pour davantage de renseignements sur ce sujet.
3.12 Syst` emes ind´ etermin´ es
Nous avons vu que si n = m et si A est inversible alors la solution du syst` eme
lin´ eaire Ax=b existe et est unique. Dans cette section, nous donnons un sens
` a la solution d’un syst` eme surd´ etermin´ e, i.e. quand m > n, et sousd´ etermin´ e,
i.e. quand m < n. Notons qu’un syst` eme ind´ etermin´ e n’a g´ en´ eralement pas
de solution `
a moins que le second membre b n’appartienne `
a Im(A).
Nous renvoyons `
a [LH74], [GL89] et [Bj¨ o88] pour une pr´ esentation plus d´ etaill´ ee.
Etant donn´ e A∈ R
m×n avec m ≥ n, et b∈ R
m , on dit que x
∗
∈ R
n est
une solution du syst` eme lin´ eaire Ax=b au sens des moindres carr´ es si
Φ(x
∗ ) ≤ min
x∈R n
Φ(x),
o` u Φ(x) = Ax − b
2
2 .
(3.62)