XII
Table des mati` eres
5.2.2 Estimations a posteriori . . . . . . . . . . . . . . . . . . . . . . . . . . 170
5.3
La m´ ethode de la puissance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
5.3.1 Approximation de la valeur propre de plus grand
module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
5.3.2 M´ ethode de la puissance inverse . . . . . . . . . . . . . . . . . . . 174
5.3.3 Impl´ ementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
5.4
La m´ ethode QR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.5
La m´ ethode QR “de base” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.6
La m´ ethode QR pour les matrices de Hessenberg . . . . . . . . . . . 183
5.6.1 Matrices de transformation de Householder
et Givens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
5.6.2 R´ eduction d’une matrice sous la forme
de Hessenberg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
5.6.3 Factorisation QR d’une matrice de Hessenberg . . . . . . 189
5.6.4 M´ ethode QR de base en partant d’une matrice
de Hessenberg sup´ erieure . . . . . . . . . . . . . . . . . . . . . . . . . 190
5.6.5 Impl´ ementation des matrices de transformation . . . . . . 192
5.7
La m´ ethode QR avec translations . . . . . . . . . . . . . . . . . . . . . . . . 195
5.7.1 La m´ ethode QR avec translations . . . . . . . . . . . . . . . . . . 195
5.8
Calcul des valeurs propres des matrices sym´ etriques . . . . . . . . 198
5.8.1 La m´ ethode de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
5.8.2 La m´ ethode des suites de Sturm . . . . . . . . . . . . . . . . . . . 202
5.9
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
III Sur les fonctions et les fonctionnelles
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires . . . . . 211
6.1
Conditionnement d’une ´ equation . . . . . . . . . . . . . . . . . . . . . . . . . 212
6.2
Une approche g´ eom´ etrique de la d´ etermination des racines . . 214
6.2.1 M´ ethode de dichotomie . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
6.2.2 Les m´ ethodes de la corde, de la s´ ecante, de la fausse
position et de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
6.3
It´ erations de point fixe pour les ´ equations non lin´ eaires . . . . . 223
6.3.1 R´ esultats de convergence pour des m´ ethodes de
point fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
6.4
Racines des ´ equations alg´ ebriques . . . . . . . . . . . . . . . . . . . . . . . . 227
6.4.1 M´ ethode de Horner et d´ eflation . . . . . . . . . . . . . . . . . . . . 228
6.4.2 La m´ ethode de Newton-Horner . . . . . . . . . . . . . . . . . . . . 229
6.4.3 La m´ ethode de Muller . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
6.5
Crit` eres d’arrˆ et . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
6.6
Techniques de post-traitement pour les m´ ethodes it´ eratives . . 238
6.6.1 Acc´ el´ eration d’Aitken . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
6.6.2 Techniques pour les racines multiples . . . . . . . . . . . . . . . 241
Table des mati` eres
5.2.2 Estimations a posteriori . . . . . . . . . . . . . . . . . . . . . . . . . . 170
5.3
La m´ ethode de la puissance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
5.3.1 Approximation de la valeur propre de plus grand
module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
5.3.2 M´ ethode de la puissance inverse . . . . . . . . . . . . . . . . . . . 174
5.3.3 Impl´ ementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
5.4
La m´ ethode QR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.5
La m´ ethode QR “de base” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.6
La m´ ethode QR pour les matrices de Hessenberg . . . . . . . . . . . 183
5.6.1 Matrices de transformation de Householder
et Givens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
5.6.2 R´ eduction d’une matrice sous la forme
de Hessenberg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
5.6.3 Factorisation QR d’une matrice de Hessenberg . . . . . . 189
5.6.4 M´ ethode QR de base en partant d’une matrice
de Hessenberg sup´ erieure . . . . . . . . . . . . . . . . . . . . . . . . . 190
5.6.5 Impl´ ementation des matrices de transformation . . . . . . 192
5.7
La m´ ethode QR avec translations . . . . . . . . . . . . . . . . . . . . . . . . 195
5.7.1 La m´ ethode QR avec translations . . . . . . . . . . . . . . . . . . 195
5.8
Calcul des valeurs propres des matrices sym´ etriques . . . . . . . . 198
5.8.1 La m´ ethode de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
5.8.2 La m´ ethode des suites de Sturm . . . . . . . . . . . . . . . . . . . 202
5.9
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
III Sur les fonctions et les fonctionnelles
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires . . . . . 211
6.1
Conditionnement d’une ´ equation . . . . . . . . . . . . . . . . . . . . . . . . . 212
6.2
Une approche g´ eom´ etrique de la d´ etermination des racines . . 214
6.2.1 M´ ethode de dichotomie . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
6.2.2 Les m´ ethodes de la corde, de la s´ ecante, de la fausse
position et de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
6.3
It´ erations de point fixe pour les ´ equations non lin´ eaires . . . . . 223
6.3.1 R´ esultats de convergence pour des m´ ethodes de
point fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
6.4
Racines des ´ equations alg´ ebriques . . . . . . . . . . . . . . . . . . . . . . . . 227
6.4.1 M´ ethode de Horner et d´ eflation . . . . . . . . . . . . . . . . . . . . 228
6.4.2 La m´ ethode de Newton-Horner . . . . . . . . . . . . . . . . . . . . 229
6.4.3 La m´ ethode de Muller . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
6.5
Crit` eres d’arrˆ et . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
6.6
Techniques de post-traitement pour les m´ ethodes it´ eratives . . 238
6.6.1 Acc´ el´ eration d’Aitken . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
6.6.2 Techniques pour les racines multiples . . . . . . . . . . . . . . . 241