“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 114 — #124
i
i
i
i
i
i
i
i
114
3
• Techniques de programmation déclarative
Il est clair que la pile sémantique n’a qu’un élément juste avant chaque appel récursif, l’instruction R={Iterate S i+1 }. C’est le même raisonnement que nous avons
utilisé pour expliquer la récursion terminale dans la section 2.5.1.
3.2.2 L’itération avec des nombres
Un bon exemple du calcul itératif est la méthode de Newton pour calculer la racine
carrée d’un nombre réel positif x. L’idée est de commencer avec une estimation g de
la racine carrée et d’améliorer cette estimation itérativement jusqu’à ce qu’elle soit
suffisamment précise. Dans chaque itération, on calcule une estimation améliorée g
en prenant la moyenne de g et x/g :
g
= (g + x/g)/2.
Pour voir que l’estimation g
est meilleure, nous utilisons la différence ´ entre l’estimation et
√
x :
´ = g −
√
x
Nous pouvons calculer la différence entre g
et
√
x comme
´
= g
−
√
x = (g + x/g)/2 −
√
x = ´
2
/2g
Pour la convergence, ´
doit être plus petit que ´. Quelle condition cela impose-t-il sur
x et g ? La condition ´
< ´ est la même que ´
2
/2g < ´, qui est la même que ´ < 2g.
(En supposant que ´ > 0 ; sinon nous commençons avec ´
, qui est toujours plus grand
que 0.) En substituant la définition de ´, nous obtenons la condition
√
x + g > 0. Si
x > 0 et l’estimation initiale g > 0, cette condition sera toujours vraie. L’algorithme
converge donc toujours.
La figure 3.4 montre un programme itératif pour la méthode de Newton. La fonction
{SqrtIter Guess X} appelle {SqrtIter {Improve Guess X} X} jusqu’à ce que Guess satisfasse la condition {GoodEnough Guess X}. Il est clair
que ce calcul est une instance du schéma général, c’est donc un calcul itératif. L’estimation améliorée est calculée selon la formule ci-dessus. Le test de « suffisamment
précis » est |x − g
2
|/x < 0.00001 : la racine carrée a une précision de cinq décimales.
On dit que ce test est relatif, parce que l’erreur est divisée par x. Nous pourrions aussi
utiliser un test absolu, par exemple |x − g
2
| < 0.00001, où la grandeur de l’erreur est
plus petite qu’une constante. Pourquoi le test relatif est-il meilleur pour le calcul des
racines carrées ?
i
i
i
i
i
i
i
i
114
3
• Techniques de programmation déclarative
Il est clair que la pile sémantique n’a qu’un élément juste avant chaque appel récursif, l’instruction R={Iterate S i+1 }. C’est le même raisonnement que nous avons
utilisé pour expliquer la récursion terminale dans la section 2.5.1.
3.2.2 L’itération avec des nombres
Un bon exemple du calcul itératif est la méthode de Newton pour calculer la racine
carrée d’un nombre réel positif x. L’idée est de commencer avec une estimation g de
la racine carrée et d’améliorer cette estimation itérativement jusqu’à ce qu’elle soit
suffisamment précise. Dans chaque itération, on calcule une estimation améliorée g
en prenant la moyenne de g et x/g :
g
= (g + x/g)/2.
Pour voir que l’estimation g
est meilleure, nous utilisons la différence ´ entre l’estimation et
√
x :
´ = g −
√
x
Nous pouvons calculer la différence entre g
et
√
x comme
´
= g
−
√
x = (g + x/g)/2 −
√
x = ´
2
/2g
Pour la convergence, ´
doit être plus petit que ´. Quelle condition cela impose-t-il sur
x et g ? La condition ´
< ´ est la même que ´
2
/2g < ´, qui est la même que ´ < 2g.
(En supposant que ´ > 0 ; sinon nous commençons avec ´
, qui est toujours plus grand
que 0.) En substituant la définition de ´, nous obtenons la condition
√
x + g > 0. Si
x > 0 et l’estimation initiale g > 0, cette condition sera toujours vraie. L’algorithme
converge donc toujours.
La figure 3.4 montre un programme itératif pour la méthode de Newton. La fonction
{SqrtIter Guess X} appelle {SqrtIter {Improve Guess X} X} jusqu’à ce que Guess satisfasse la condition {GoodEnough Guess X}. Il est clair
que ce calcul est une instance du schéma général, c’est donc un calcul itératif. L’estimation améliorée est calculée selon la formule ci-dessus. Le test de « suffisamment
précis » est |x − g
2
|/x < 0.00001 : la racine carrée a une précision de cinq décimales.
On dit que ce test est relatif, parce que l’erreur est divisée par x. Nous pourrions aussi
utiliser un test absolu, par exemple |x − g
2
| < 0.00001, où la grandeur de l’erreur est
plus petite qu’une constante. Pourquoi le test relatif est-il meilleur pour le calcul des
racines carrées ?