5.13 Pour finir : méthode directe ou itérative ?
177
0
50
100
150
200
250
0
50
100
150
200
250
0
2000
4000
6000
8000
10000
12000
0
5
10
15
20
25
30
35
40
45
Figure 5.13. Structure de la matrice utilisée pour le second cas test (à
gauche), et temps CPU (en sec.) nécessaire à la résolution du système linéaire
associé (à droite) : le trait plein correspond à la commande \, le trait mixte à
la factorisation de Cholesky, le trait discontinu à la méthode itérative PCG.
Les valeurs en abscisses correspondent à la dimension n de la matrice
Enfin, il faut se souvenir que les méthodes directes nécessitent davantage de mémoire que les méthodes itératives, ce qui peut être rédhibitoire
pour les très grands problèmes.
Systèmes avec matrices pleines
La commande gallery de MATLAB donne accès à une collection de gallery
matrices ayant diverses structures et propriétés. En particulier pour
notre troisième cas test, nous utilisons A=gallery(’riemann’,n) pour
construire la matrice de Riemann de dimension n, c’est-à-dire une matrice pleine n × n, non symétrique, dont le déterminant se comporte en
O(n!n
−1/2+ ) pour tout > 0. Le système linéaire associé est résolu avec
la méthode itérative GMRES (voir Remarque 5.4) et les itérations sont
stoppées dès que la norme du résidu relatif (5.60) est inférieure à 10
−13 .
Nous utiliserons aussi la commande \ qui, dans le cas considéré, effectue
une factorisation LU.
On résout le système linéaire pour diverses valeurs de n. Le second
membre est tel que la solution exacte est le vecteur 1
T . On effectue les
tests avec GMRES sans préconditionneur Sur la Figure 5.14, à droite,
on indique le temps CPU pour n allant de 100 à 1000. A gauche, on
représente le conditionnement de A, cond(A). Comme on peut le voir,
la méthode de factorisation directe est beaucoup moins chère que la
méthode GMRES non préconditionnée. Cependant pour des grandes valeurs de n, la méthode directe devient plus chère que la méthode itérative
utilisée avec un bon préconditionneur.
Octave 5.2 La commande gallery n’existe pas en Octave. Cependant
quelques matrices particulières sont disponibles via les commandes hilb,
hankel, vander, invhilb sylvester_matrix, toeplitz (matrices de Hilbert,
177
0
50
100
150
200
250
0
50
100
150
200
250
0
2000
4000
6000
8000
10000
12000
0
5
10
15
20
25
30
35
40
45
Figure 5.13. Structure de la matrice utilisée pour le second cas test (à
gauche), et temps CPU (en sec.) nécessaire à la résolution du système linéaire
associé (à droite) : le trait plein correspond à la commande \, le trait mixte à
la factorisation de Cholesky, le trait discontinu à la méthode itérative PCG.
Les valeurs en abscisses correspondent à la dimension n de la matrice
Enfin, il faut se souvenir que les méthodes directes nécessitent davantage de mémoire que les méthodes itératives, ce qui peut être rédhibitoire
pour les très grands problèmes.
Systèmes avec matrices pleines
La commande gallery de MATLAB donne accès à une collection de gallery
matrices ayant diverses structures et propriétés. En particulier pour
notre troisième cas test, nous utilisons A=gallery(’riemann’,n) pour
construire la matrice de Riemann de dimension n, c’est-à-dire une matrice pleine n × n, non symétrique, dont le déterminant se comporte en
O(n!n
−1/2+ ) pour tout > 0. Le système linéaire associé est résolu avec
la méthode itérative GMRES (voir Remarque 5.4) et les itérations sont
stoppées dès que la norme du résidu relatif (5.60) est inférieure à 10
−13 .
Nous utiliserons aussi la commande \ qui, dans le cas considéré, effectue
une factorisation LU.
On résout le système linéaire pour diverses valeurs de n. Le second
membre est tel que la solution exacte est le vecteur 1
T . On effectue les
tests avec GMRES sans préconditionneur Sur la Figure 5.14, à droite,
on indique le temps CPU pour n allant de 100 à 1000. A gauche, on
représente le conditionnement de A, cond(A). Comme on peut le voir,
la méthode de factorisation directe est beaucoup moins chère que la
méthode GMRES non préconditionnée. Cependant pour des grandes valeurs de n, la méthode directe devient plus chère que la méthode itérative
utilisée avec un bon préconditionneur.
Octave 5.2 La commande gallery n’existe pas en Octave. Cependant
quelques matrices particulières sont disponibles via les commandes hilb,
hankel, vander, invhilb sylvester_matrix, toeplitz (matrices de Hilbert,