1. Problèmes numériques
21
1.3 Accélération de la convergence
Le procédé d’extrapolation de Richardson illustre l’accélération de la
convergence d’une méthode numérique. Proposée en 1927 par Lewis Fry
Richardson (1881-1953), l’extrapolation à la limite consiste à calculer plusieurs fois la même quantité avec un maillage diérent. Soit uA1 un réel
fixé et x k une approximation de x.S ix est du premier ordre et si le calcul
est fait deux fois, on a
x k = x + k + R(k
2 )
x k@u = x +
k
u + R(k
2 )
Ainsi, en combinant le résultat x k avec un résultat issu d’un maillage plus
fin, on obtient
ux k@u x k =(u 1)x + R(k
2 )
Plus généralement, si x est approché à l’ordre q
x(k)=d + ek
q + fk
q+1 + ···+ hk
q+o + r(k
q+o )
En prenant deux pas quelconques k 1 et k 2 ,silepask 2 est plus petit que le
pas k 1 , x(k 2 ) est une meilleure approximation que x(k 1 ). On obtient une
approximation encore meilleure en supprimant le terme en k
q
,e np r e n a n t
x(k 1 >k 2 )=
k
q
1 x(k 2 ) k
q
2 x(k 1 )
k q
1 k q
2
En particulier, pour k 1 = k et k 2 = k@u avec uA1,o no b t i e n t
x k = x + dk
q + R(k
q+1 )
x k@u = x + d
k
q
u q + R(k
q+1 )
d’où la relation usuelle
u
q x k@u x k
u q 1
= x + R(k
q+1 ) ;q 1
1.4 Complexité
Les problèmes traités sur un calculateur se répartissent en deux grandes
catégories selon qu’une valeur numérique est attendue (problèmes de calcul) ou qu’une réponse par oui ou non est souhaitée (problème de décision).
Les propriétés des algorithmes ont été étudiées dans les années 1930 par le
mathématicien Alan Turing (1912-1954) qui inventa la machine qui porte
son nom. Turing, en démontrant que les problèmes qui ne pouvaient pas
être résolus par sa machine symbolique n’avaient pas d’algorithme, fixa les
limites de la calculabilité. Depuis, on classe les problèmes en deux grandes
21
1.3 Accélération de la convergence
Le procédé d’extrapolation de Richardson illustre l’accélération de la
convergence d’une méthode numérique. Proposée en 1927 par Lewis Fry
Richardson (1881-1953), l’extrapolation à la limite consiste à calculer plusieurs fois la même quantité avec un maillage diérent. Soit uA1 un réel
fixé et x k une approximation de x.S ix est du premier ordre et si le calcul
est fait deux fois, on a
x k = x + k + R(k
2 )
x k@u = x +
k
u + R(k
2 )
Ainsi, en combinant le résultat x k avec un résultat issu d’un maillage plus
fin, on obtient
ux k@u x k =(u 1)x + R(k
2 )
Plus généralement, si x est approché à l’ordre q
x(k)=d + ek
q + fk
q+1 + ···+ hk
q+o + r(k
q+o )
En prenant deux pas quelconques k 1 et k 2 ,silepask 2 est plus petit que le
pas k 1 , x(k 2 ) est une meilleure approximation que x(k 1 ). On obtient une
approximation encore meilleure en supprimant le terme en k
q
,e np r e n a n t
x(k 1 >k 2 )=
k
q
1 x(k 2 ) k
q
2 x(k 1 )
k q
1 k q
2
En particulier, pour k 1 = k et k 2 = k@u avec uA1,o no b t i e n t
x k = x + dk
q + R(k
q+1 )
x k@u = x + d
k
q
u q + R(k
q+1 )
d’où la relation usuelle
u
q x k@u x k
u q 1
= x + R(k
q+1 ) ;q 1
1.4 Complexité
Les problèmes traités sur un calculateur se répartissent en deux grandes
catégories selon qu’une valeur numérique est attendue (problèmes de calcul) ou qu’une réponse par oui ou non est souhaitée (problème de décision).
Les propriétés des algorithmes ont été étudiées dans les années 1930 par le
mathématicien Alan Turing (1912-1954) qui inventa la machine qui porte
son nom. Turing, en démontrant que les problèmes qui ne pouvaient pas
être résolus par sa machine symbolique n’avaient pas d’algorithme, fixa les
limites de la calculabilité. Depuis, on classe les problèmes en deux grandes