5.11 Méthode du gradient conjugué
171
Table 5.4. Erreurs obtenues pour la résolution du système de Hilbert avec
les méthodes du gradient préconditionné (PG), du gradient conjugué préconditionné (PCG) et la méthode directe utilisée par la commande \ de Matlab.
Pour les méthodes itératives, on indique aussi le nombre d’itérations
\
PG
PCG
n
K(An)
Erreur
Erreur
Iter
Erreur
Iter
4
1.55e+04
7.72e-13
8.72e-03
995
1.12e-02
3
6
1.50e+07
7.61e-10
3.60e-03
1813
3.88e-03
4
8
1.53e+10
6.38e-07
6.30e-03
1089
7.53e-03
4
10
1.60e+13
5.24e-04
7.98e-03
875
2.21e-03
5
12
1.70e+16
6.27e-01
5.09e-03
1355
3.26e-03
5
14
6.06e+17
4.12e+01
3.91e-03
1379
4.32e-03
5
Exemple 5.16 Revenons à l’Exemple 5.9 sur les matrices de Hilbert et résolvons le système correspondant, pour différentes valeurs de n, par les méthodes du gradient préconditionné (PG) et du gradient conjugué préconditionné (PCG), en utilisant comme préconditionneur la matrice diagonale D
constituée des coefficients diagonaux de la matrice de Hilbert. On prend x
(0)
égal au vecteur nul et on itère jusqu’à ce que le résidu relatif (5.60) soit inférieur à 10
−6 . On indique dans la Table 5.4 les erreurs absolues (par rapport à la
solution exacte) obtenues avec PG et PCG et avec la commande \ de MATLAB. On voit dans ce dernier cas que l’erreur augmente considérablement
quand n devient grand. On appréciera en revanche la convergence très rapide
qu’on peut obtenir avec une méthode itérative bien choisie comme PCG.
Remarque 5.4 (Systèmes non-symétriques) La méthode CG est un cas
particulier des méthodes de Krylov (ou Lanczos) qui peuvent s’appliquer à
des systèmes non nécessairement symétriques. On trouvera une présentation
de ces méthodes dans [Axe94], [Saa03] et [vdV03] par exemple.
Certaines d’entre elles possèdent, comme CG, la propriété de converger
en un nombre fini d’étapes (en arithmétique exacte). Pour des systèmes non
symétriques, c’est aussi le cas de GMRES (Generalized Minimum RESidual )
qui est l’une des méthodes de Krylov les plus remarquables, disponible dans
la toolbox sparfun de MATLAB sous le nom gmres.
gmres
Une autre méthode, Bi-CGStab ([vdV03]), est également très efficace. La
commande MATLAB correspondante est bicgstab.
bicgstab
Octave 5.1 Octave implémente la méthode du gradient conjugué préconditionné (PCG) dans la fonction pcg et la méthode des résidus conjugués préconditionnés (PCR/Richardson) dans la fonction pcr. La fonction bicgstab existe dans Octave depuis la version 3.2.0.
Voir Exercices 5.15–5.18.
171
Table 5.4. Erreurs obtenues pour la résolution du système de Hilbert avec
les méthodes du gradient préconditionné (PG), du gradient conjugué préconditionné (PCG) et la méthode directe utilisée par la commande \ de Matlab.
Pour les méthodes itératives, on indique aussi le nombre d’itérations
\
PG
PCG
n
K(An)
Erreur
Erreur
Iter
Erreur
Iter
4
1.55e+04
7.72e-13
8.72e-03
995
1.12e-02
3
6
1.50e+07
7.61e-10
3.60e-03
1813
3.88e-03
4
8
1.53e+10
6.38e-07
6.30e-03
1089
7.53e-03
4
10
1.60e+13
5.24e-04
7.98e-03
875
2.21e-03
5
12
1.70e+16
6.27e-01
5.09e-03
1355
3.26e-03
5
14
6.06e+17
4.12e+01
3.91e-03
1379
4.32e-03
5
Exemple 5.16 Revenons à l’Exemple 5.9 sur les matrices de Hilbert et résolvons le système correspondant, pour différentes valeurs de n, par les méthodes du gradient préconditionné (PG) et du gradient conjugué préconditionné (PCG), en utilisant comme préconditionneur la matrice diagonale D
constituée des coefficients diagonaux de la matrice de Hilbert. On prend x
(0)
égal au vecteur nul et on itère jusqu’à ce que le résidu relatif (5.60) soit inférieur à 10
−6 . On indique dans la Table 5.4 les erreurs absolues (par rapport à la
solution exacte) obtenues avec PG et PCG et avec la commande \ de MATLAB. On voit dans ce dernier cas que l’erreur augmente considérablement
quand n devient grand. On appréciera en revanche la convergence très rapide
qu’on peut obtenir avec une méthode itérative bien choisie comme PCG.
Remarque 5.4 (Systèmes non-symétriques) La méthode CG est un cas
particulier des méthodes de Krylov (ou Lanczos) qui peuvent s’appliquer à
des systèmes non nécessairement symétriques. On trouvera une présentation
de ces méthodes dans [Axe94], [Saa03] et [vdV03] par exemple.
Certaines d’entre elles possèdent, comme CG, la propriété de converger
en un nombre fini d’étapes (en arithmétique exacte). Pour des systèmes non
symétriques, c’est aussi le cas de GMRES (Generalized Minimum RESidual )
qui est l’une des méthodes de Krylov les plus remarquables, disponible dans
la toolbox sparfun de MATLAB sous le nom gmres.
gmres
Une autre méthode, Bi-CGStab ([vdV03]), est également très efficace. La
commande MATLAB correspondante est bicgstab.
bicgstab
Octave 5.1 Octave implémente la méthode du gradient conjugué préconditionné (PCG) dans la fonction pcg et la méthode des résidus conjugués préconditionnés (PCR/Richardson) dans la fonction pcr. La fonction bicgstab existe dans Octave depuis la version 3.2.0.
Voir Exercices 5.15–5.18.