136
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
Dans les strat´ egies consid´ er´ ees jusqu’` a pr´ esent, les coefficients qui ont ´ et´ e
n´ eglig´ es ne peuvent plus ˆ etre pris en compte durant la factorisation incompl` ete. Une alternative possible consiste par exemple ` a ajouter, ligne
par ligne, les coefficients n´ eglig´ es au coefficient diagonal de U in , `
a la fin
de chaque ´ etape de factorisation. La factorisation incompl` ete ainsi obtenue est connue sous le nom de MILU (pour ILU modifi´ ee). Elle poss` ede
la propri´ et´ e d’ˆ etre exacte par rapport aux vecteurs constants, c’est-` a-dire
R1 = 0 (voir [Axe94] pour d’autres formulations). En pratique, cette
simple astuce fournit, pour une large classe de matrices, un meilleur pr´ econditionnement que ILU.
L’existence de la factorisation ILU n’est pas garantie pour toutes les matrices inversibles (voir [Elm86] pour un exemple) et le proc´ ed´ e s’interrompt si un pivot nul apparaˆ ıt. Des th´ eor` emes d’existence peuvent ˆ etre
´ etablis pour les M-matrices [MdV77] et les matrices ` a diagonale dominante [Man80].
Terminons en mentionnant la factorisation ILUT, qui poss` ede les propri´ et´ es de ILU(p) et MILU. Cette factorisation peut aussi inclure, au prix
d’une l´ eg` ere augmentation du coˆ ut de calcul, un changement de pivot
partiel par colonnes.
Pour une impl´ ementation efficace des factorisations incompl` etes, nous renvoyons ` a la fonction luinc de la toolbox sparfun de MATLAB.
3. Pr´ econditionneurs polynomiaux : la matrice de pr´ econditionnement est
d´ efinie par
P
−1 = p(A),
o` u p est un polynˆ ome en A, g´ en´ eralement de bas degr´ e.
Consid´ erons l’exemple important des pr´ econditionneurs polynomiaux de
Neumann. En posant A = D − C, on a A = (I − CD
−1 )D, d’o` u
A
−1 = D
−1 (I − CD
−1 )
−1 = D
−1 (I + CD
−1 + (CD
−1 )
2 + . . .).
On peut obtenir un pr´ econditionneur en tronquant la s´ erie ` a une certaine
puissance p. La m´ ethode n’est vraiment efficace que si ρ(CD
−1 ) < 1, i.e.
si la s´ erie de Neumann est convergente.
Des pr´ econditionneurs polynomiaux plus sophistiqu´ es utilisent le polynˆ ome g´ en´ er´ e par la m´ ethode it´ erative de Chebyshev apr` es un (petit)
nombre d’´ etapes fix´ e (voir aussi la Section 4.3.1).
4. Pr´ econditionneurs par moindres carr´ es : A
−1 est approch´ ee au sens des
moindres carr´ es par un polynˆ ome p s (A) (voir Section 3.12). Puisque le
but est de rendre la matrice I − P
−1 A aussi proche que possible de z´ ero,
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
Dans les strat´ egies consid´ er´ ees jusqu’` a pr´ esent, les coefficients qui ont ´ et´ e
n´ eglig´ es ne peuvent plus ˆ etre pris en compte durant la factorisation incompl` ete. Une alternative possible consiste par exemple ` a ajouter, ligne
par ligne, les coefficients n´ eglig´ es au coefficient diagonal de U in , `
a la fin
de chaque ´ etape de factorisation. La factorisation incompl` ete ainsi obtenue est connue sous le nom de MILU (pour ILU modifi´ ee). Elle poss` ede
la propri´ et´ e d’ˆ etre exacte par rapport aux vecteurs constants, c’est-` a-dire
R1 = 0 (voir [Axe94] pour d’autres formulations). En pratique, cette
simple astuce fournit, pour une large classe de matrices, un meilleur pr´ econditionnement que ILU.
L’existence de la factorisation ILU n’est pas garantie pour toutes les matrices inversibles (voir [Elm86] pour un exemple) et le proc´ ed´ e s’interrompt si un pivot nul apparaˆ ıt. Des th´ eor` emes d’existence peuvent ˆ etre
´ etablis pour les M-matrices [MdV77] et les matrices ` a diagonale dominante [Man80].
Terminons en mentionnant la factorisation ILUT, qui poss` ede les propri´ et´ es de ILU(p) et MILU. Cette factorisation peut aussi inclure, au prix
d’une l´ eg` ere augmentation du coˆ ut de calcul, un changement de pivot
partiel par colonnes.
Pour une impl´ ementation efficace des factorisations incompl` etes, nous renvoyons ` a la fonction luinc de la toolbox sparfun de MATLAB.
3. Pr´ econditionneurs polynomiaux : la matrice de pr´ econditionnement est
d´ efinie par
P
−1 = p(A),
o` u p est un polynˆ ome en A, g´ en´ eralement de bas degr´ e.
Consid´ erons l’exemple important des pr´ econditionneurs polynomiaux de
Neumann. En posant A = D − C, on a A = (I − CD
−1 )D, d’o` u
A
−1 = D
−1 (I − CD
−1 )
−1 = D
−1 (I + CD
−1 + (CD
−1 )
2 + . . .).
On peut obtenir un pr´ econditionneur en tronquant la s´ erie ` a une certaine
puissance p. La m´ ethode n’est vraiment efficace que si ρ(CD
−1 ) < 1, i.e.
si la s´ erie de Neumann est convergente.
Des pr´ econditionneurs polynomiaux plus sophistiqu´ es utilisent le polynˆ ome g´ en´ er´ e par la m´ ethode it´ erative de Chebyshev apr` es un (petit)
nombre d’´ etapes fix´ e (voir aussi la Section 4.3.1).
4. Pr´ econditionneurs par moindres carr´ es : A
−1 est approch´ ee au sens des
moindres carr´ es par un polynˆ ome p s (A) (voir Section 3.12). Puisque le
but est de rendre la matrice I − P
−1 A aussi proche que possible de z´ ero,