Les scripts complets du tournoi des méthodes

Le DM Le sinus du degré organise en partie V un tournoi entre trois façons d’attraper la même racine. Voici les scripts complets, exécutés, avec leurs sorties réelles et la mesure exacte de ce que chacune gagne par tour.

Rappel du cadre. On cherche $x^{*}$, l’unique zéro dans $[0\,;0{,}06]$ de

$f(x) = 4x^3 - 3x + q, \qquad q = \sin 3^\circ \approx 0{,}0523359562.$

Ce $x^{*}$ est $\sin 1^\circ$, à ceci près que $q$ est donné tronqué : la question Q17 du DM mesure précisément l’écart que cette troncature provoque, et nous y reviendrons au dernier paragraphe.

Le piège à ne pas manquer. La valeur de $q$ est écrite en dur dans tous les scripts, c’est voulu. Toute la trigonométrie du devoir tient dans cette constante. Si vous êtes tenté d’écrire math.sin(3), sachez que Python calcule le sinus de $3$ radians, soit $0{,}1411\ldots$ : l’itération convergerait alors sans le moindre message d’erreur, vers une valeur plausible et fausse. La bonne écriture est math.sin(math.radians(3)).

1. La machine d’al-Kashi (partie II)

Le coup de génie tient dans un changement d’écriture : au lieu de $3x - 4x^3 = q$, écrire $x = \frac{q + 4x^3}{3}$ et lire cette égalité comme une machine.

q = 0.0523359562        # sin(3 degres), donnee de Samarcande (R2)

def g(x):
    return (q + 4 * x**3) / 3

u = q / 3               # le point de depart de la question Q6
for n in range(8):
    print(n, u)
    u = g(u)

Sortie :

0 0.017445318733333333
1 0.017452397791199867
2 0.017452406412434986
3 0.01745240642293863
4 0.017452406422951424
5 0.017452406422951438
6 0.017452406422951438
7 0.017452406422951438

L’affichage se fige à partir de $n = 5$, et le DM prévenait que ce gel resterait mystérieux jusqu’à la question Q17. La raison est double, et il faut les distinguer : à partir de $n = 5$ la suite a atteint la précision des flottants de la machine, et de toute façon elle converge vers le point fixe de l’équation avec $q$ tronqué, pas vers $\sin 1^\circ$.

Le compte des décimales stabilisées demandé en Q6, mesuré exactement :

$n$	$u_n$	erreur	décimales exactes	gain
0	$0{,}017445318733$	$7{,}1 \times 10^{-6}$	$5{,}15$
1	$0{,}017452397791$	$8{,}6 \times 10^{-9}$	$8{,}06$	$+2{,}91$
2	$0{,}017452406412$	$1{,}1 \times 10^{-11}$	$10{,}98$	$+2{,}91$
3	$0{,}017452406423$	$1{,}3 \times 10^{-14}$	$13{,}89$	$+2{,}91$
4	$0{,}017452406423$	$1{,}6 \times 10^{-17}$	$16{,}81$	$+2{,}91$

Exactement $2{,}91$ décimales par tour, avec une régularité de métronome. Le DM en donne la raison en partie III : la machine est une contraction, et son facteur local au point fixe vaut

$g'(x^{*}) = 4 (x^{*})^{2} = 4\sin^2 1^\circ \approx 1{,}2183 \times 10^{-3}.$

Chaque tour multiplie l’erreur par ce nombre, donc lui gagne $-\log_{10}\left(1{,}2183 \times 10^{-3}\right) = 2{,}914$ décimales. La théorie et la mesure coïncident à la deuxième décimale près.

2. La dichotomie, valeur sûre (question Q18)

q = 0.0523359562

def f(x):
    return 4 * x**3 - 3 * x + q

a, b = 0.0, 0.06
n = 0
while b - a > 1e-10:
    m = (a + b) / 2
    if f(a) * f(m) <= 0:
        b = m
    else:
        a = m
    n += 1
print(n, (a + b) / 2)

Sortie :

30 0.017452406426891685

Trente étapes. Le calcul exact de la question Q18b le prévoyait : après $n$ étapes, le milieu approche $x^{*}$ à $\frac{0{,}06}{2^{\,n+1}}$ près, et l’on veut $\frac{0{,}06}{2^{\,n+1}} \leqslant 0{,}5 \times 10^{-10}$, soit $2^{\,n+1} \geqslant 1{,}2 \times 10^{9}$. Comme $2^{30} \approx 1{,}07 \times 10^{9}$ ne suffit pas et $2^{31} \approx 2{,}15 \times 10^{9}$ suffit, il faut $n = 30$.

Le rythme est celui du cours, et il ne dépend d’aucune propriété de $f$ : chaque étape divise l’erreur par $2$, donc gagne $\log_{10}(2) = 0{,}301$ décimale. Autrement dit $3{,}32$ étapes par décimale, et jamais mieux.

3. La fausse position (question Q19)

Au lieu de couper au milieu, on coupe là où la corde traverse l’axe. Sur $[a\,;b]$ avec $f(a)$ et $f(b)$ de signes contraires, la corde joint $(a\,;f(a))$ à $(b\,;f(b))$ et rencontre l’axe des abscisses en

$c = a - f(a)\,\frac{b - a}{f(b) - f(a)}.$

q = 0.0523359562

def f(x):
    return 4 * x**3 - 3 * x + q

a, b = 0.0, 0.06
for n in range(1, 6):
    c = a - f(a) * (b - a) / (f(b) - f(a))
    print(n, c)
    if f(a) * f(c) <= 0:
        b = c
    else:
        a = c

Sortie :

1 0.017529460142015008
2 0.017452469172211597
3 0.01745240647393911
4 0.017452406422992874
5 0.017452406422951473

La première corde donne déjà $c_1 \approx 0{,}0175294601$, soit trois décimales exactes en une seule opération, comme l’annonçait la question Q19b. Le rythme mesuré :

$n$	$c_n$	erreur	décimales exactes	gain
1	$0{,}017529460142$	$7{,}7 \times 10^{-5}$	$4{,}11$
2	$0{,}017452469172$	$6{,}3 \times 10^{-8}$	$7{,}20$	$+3{,}09$
3	$0{,}017452406474$	$5{,}1 \times 10^{-11}$	$10{,}29$	$+3{,}09$
4	$0{,}017452406423$	$4{,}1 \times 10^{-14}$	$13{,}38$	$+3{,}09$
5	$0{,}017452406423$	$3{,}4 \times 10^{-17}$	$16{,}47$	$+3{,}09$

Exactement $3{,}09$ décimales par tour, et là encore la théorie l’explique. Dans cette configuration, la borne $a = 0$ ne bouge jamais : seule $b$ descend vers $x^{*}$. L’erreur est donc multipliée à chaque tour par le facteur

$\left| 1 - f'(x^{*})\,\frac{a - x^{*}}{f(a) - f(x^{*})} \right| \approx 8{,}2 \times 10^{-4},$

ce qui donne $-\log_{10}\left(8{,}2 \times 10^{-4}\right) = 3{,}09$ décimales par tour. La figure du DM disait déjà pourquoi : sur $[0\,;0{,}06]$, la cubique est si peu courbée que la corde s’en distingue à peine.

4. Le podium, et le récit honnête

print("methode                decimales gagnees par tour")
print("dichotomie             0.301")
print("machine d'al-Kashi     2.91")
print("fausse position        3.09")

Le tournoi n’oppose pas une lente à une rapide : il oppose une méthode lente à deux méthodes rapides, qui gagnent toutes les deux environ trois décimales par tour. C’est le récit exact, et il faut y insister car la tentation est grande de raconter un duel.

• La dichotomie perd de dix ordres de grandeur en rythme. Sa vertu est ailleurs, et elle est immense : elle garantit son erreur à chaque étape, sans aucune hypothèse sur $f$ au-delà de la continuité et du changement de signe.
• La fausse position est la plus rapide en rythme de croisière, d’un cheveu : $3{,}09$ contre $2{,}91$.
• La machine d’al-Kashi atteint pourtant les dix décimales la première. Regardez les deux tableaux : $u_2$ est à $10{,}98$ décimales après deux tours, alors que $c_3$ n’atteint $10{,}29$ qu’au troisième. L’avance ne vient donc pas de la vitesse de croisière, elle vient du point de départ. La question Q7 du DM l’avait démontré avant même de tourner : $\left|u_0 - x^{*}\right| \leqslant 10^{-5}$, la machine connaît déjà cinq décimales avant son premier tour, quand la fausse position part de rien.

Et la question Q20b, qui est la vraie question du DM. Pourquoi al-Kashi, à Samarcande, en base soixante, à la main, a-t-il choisi la machine plutôt que la corde, alors que la corde va très légèrement plus vite ?

Parce que la machine n’a rien à surveiller. La dichotomie et la fausse position exigent de maintenir un encadrement, d’évaluer $f$ en deux points, de comparer des signes et de choisir un côté à chaque tour : autant d’occasions de se tromper quand on calcule à la plume sur des tables sexagésimales. La machine, elle, itère une formule unique, sans aucun test. Mieux encore, et c’est décisif : ses chiffres, une fois posés, ne bougent plus. Al-Kashi ne recalculait pas tout à chaque tour, il déterminait la place suivante et l’écrivait. Une méthode qui écrit ses chiffres définitivement bat, pour un calculateur humain, une méthode marginalement plus rapide qui les réécrit tous.

C’est un critère qui a disparu de nos préoccupations, et qui gouvernait les leurs.

5. La cellule de vérification (question Q17d)

Seule apparition de la trigonométrie machine dans tout le devoir, et elle est en radians.

import math
print(math.sin(math.radians(1)))

Sortie :

0.01745240643728351

Comparez avec la limite de la machine, $0{,}017452406422951\ldots$ : les deux valeurs divergent à la onzième décimale. Ce n’est ni une erreur de la machine, ni une erreur de Python. C’est la question Q17 : la donnée $q$ a été tronquée à dix décimales, et cette troncature se propage jusqu’au résultat.

Le DM en donne le coefficient exact. En dérivant l’équation $h(x^{*}) = q$ par rapport à $q$, on obtient

$\frac{\mathrm{d}x^{*}}{\mathrm{d}q} = \frac{1}{3 - 12\sin^2 1^\circ} \approx 0{,}3337,$

c’est-à-dire qu’une erreur sur $q$ se transmet à $x^{*}$ en étant divisée par trois environ. Vérification : l’écart mesuré entre la limite de la machine et $\sin 1^\circ$ vaut $1{,}43 \times 10^{-11}$, et l’erreur de troncature sur $q$ est de l’ordre de $4{,}3 \times 10^{-11}$. Le rapport est bien voisin de $\frac13$.

La conclusion vaut pour tout le chapitre. Aucun algorithme, si rapide soit-il, ne peut être plus précis que sa donnée d’entrée. La machine d’al-Kashi n’a pas fait d’erreur : elle a résolu exactement le problème qu’on lui a posé, avec le $q$ qu’on lui a donné. Si l’on veut plus de décimales de $\sin 1^\circ$, il faut d’abord plus de décimales de $\sin 3^\circ$, et c’est précisément l’objet de la partie VI du devoir, qui va les chercher sous forme exacte, par radicaux.

Sources

• DM1 F1, Le sinus du degré, parties II, III et V, et annexe B.
• Cours F1, § 6.1 pour la dichotomie et sa loi des $3{,}32$ étapes par décimale.
• Tous les scripts de cette page ont été exécutés ; les sorties sont recopiées telles quelles. Les erreurs, décimales exactes et taux de convergence ont été recalculés en précision arbitraire (50 chiffres de travail).