Table des mati` eres
XI
3.8.2 Inverse d’une matrice par blocs . . . . . . . . . . . . . . . . . . . . 100
3.8.3 Syst` emes tridiagonaux par blocs . . . . . . . . . . . . . . . . . . . 101
3.9
Pr´ ecision de la m´ ethode de Gauss . . . . . . . . . . . . . . . . . . . . . . . . 102
3.10 Un calcul approch´ e de K(A) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.11 Am´ eliorer la pr´ ecision de la m´ ethode de Gauss . . . . . . . . . . . . . 106
3.11.1 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.11.2 Raffinement it´ eratif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
3.12 Syst` emes ind´ etermin´ es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.13 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4 M´ ethodes it´ eratives pour la r´ esolution
des syst` emes lin´ eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.1
Convergence des m´ ethodes it´ eratives . . . . . . . . . . . . . . . . . . . . . . 115
4.2
M´ ethodes it´ eratives lin´ eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.2.1 Les m´ ethodes de Jacobi, de Gauss-Seidel
et de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.2.2 R´ esultats de convergence pour les m´ ethodes
de Jacobi et de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . 120
4.2.3 R´ esultats de convergence pour la m´ ethode
de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.2.4 Matrices par blocs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.2.5 Forme sym´ etrique des m´ ethodes SOR
et de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.2.6 Impl´ ementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
4.3
M´ ethodes it´ eratives stationnaires et instationnaires . . . . . . . . . 127
4.3.1 Analyse de la convergence des m´ ethodes
de Richardson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
4.3.2 Matrices de pr´ econditionnement . . . . . . . . . . . . . . . . . . . 130
4.3.3 La m´ ethode du gradient . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.3.4 La m´ ethode du gradient conjugu´ e . . . . . . . . . . . . . . . . . . 142
4.3.5 La m´ ethode du gradient conjugu´ e pr´ econditionn´ e . . . . 146
4.4
M´ ethodes de Krylov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
4.4.1 La m´ ethode d’Arnoldi pour les syst` emes lin´ eaires . . . . 152
4.4.2 La m´ ethode GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
4.5
Tests d’arrˆ et . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.5.1 Un test d’arrˆ et bas´ e sur l’incr´ ement . . . . . . . . . . . . . . . . 158
4.5.2 Un test d’arrˆ et bas´ e sur le r´ esidu . . . . . . . . . . . . . . . . . . 159
4.6
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5 Approximation des valeurs propres
et des vecteurs propres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
5.1
Localisation g´ eom´ etrique des valeurs propres . . . . . . . . . . . . . . . 163
5.2
Analyse de stabilit´ e et conditionnement . . . . . . . . . . . . . . . . . . . 166
5.2.1 Estimations a priori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
XI
3.8.2 Inverse d’une matrice par blocs . . . . . . . . . . . . . . . . . . . . 100
3.8.3 Syst` emes tridiagonaux par blocs . . . . . . . . . . . . . . . . . . . 101
3.9
Pr´ ecision de la m´ ethode de Gauss . . . . . . . . . . . . . . . . . . . . . . . . 102
3.10 Un calcul approch´ e de K(A) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.11 Am´ eliorer la pr´ ecision de la m´ ethode de Gauss . . . . . . . . . . . . . 106
3.11.1 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.11.2 Raffinement it´ eratif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
3.12 Syst` emes ind´ etermin´ es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.13 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4 M´ ethodes it´ eratives pour la r´ esolution
des syst` emes lin´ eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.1
Convergence des m´ ethodes it´ eratives . . . . . . . . . . . . . . . . . . . . . . 115
4.2
M´ ethodes it´ eratives lin´ eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.2.1 Les m´ ethodes de Jacobi, de Gauss-Seidel
et de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.2.2 R´ esultats de convergence pour les m´ ethodes
de Jacobi et de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . 120
4.2.3 R´ esultats de convergence pour la m´ ethode
de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.2.4 Matrices par blocs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.2.5 Forme sym´ etrique des m´ ethodes SOR
et de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.2.6 Impl´ ementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
4.3
M´ ethodes it´ eratives stationnaires et instationnaires . . . . . . . . . 127
4.3.1 Analyse de la convergence des m´ ethodes
de Richardson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
4.3.2 Matrices de pr´ econditionnement . . . . . . . . . . . . . . . . . . . 130
4.3.3 La m´ ethode du gradient . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.3.4 La m´ ethode du gradient conjugu´ e . . . . . . . . . . . . . . . . . . 142
4.3.5 La m´ ethode du gradient conjugu´ e pr´ econditionn´ e . . . . 146
4.4
M´ ethodes de Krylov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
4.4.1 La m´ ethode d’Arnoldi pour les syst` emes lin´ eaires . . . . 152
4.4.2 La m´ ethode GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
4.5
Tests d’arrˆ et . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.5.1 Un test d’arrˆ et bas´ e sur l’incr´ ement . . . . . . . . . . . . . . . . 158
4.5.2 Un test d’arrˆ et bas´ e sur le r´ esidu . . . . . . . . . . . . . . . . . . 159
4.6
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5 Approximation des valeurs propres
et des vecteurs propres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
5.1
Localisation g´ eom´ etrique des valeurs propres . . . . . . . . . . . . . . . 163
5.2
Analyse de stabilit´ e et conditionnement . . . . . . . . . . . . . . . . . . . 166
5.2.1 Estimations a priori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166