La corde, la tangente et le ciseau

Le chapitre F1 s’est clos sur une équation sans formule et sur la dichotomie. Ses Coulisses ont chronométré les tangentes. Le laboratoire du chapitre F2 a introduit la troisième et dernière méthode du programme, la sécante, et sa marge a promis un joyau : son ordre de convergence est le nombre d’or.

La famille est maintenant complète. Voici la course, sur la même équation et depuis les mêmes bornes.

$x^{5} - x - 1 = 0, \qquad \text{de racine} \quad c = 1{,}167\,303\,978\,261\,418\,7\ldots$

Toutes les valeurs de cette page ont été recalculées ; les scripts sont donnés en entier, prêts à exécuter.

Le tableau de famille

Méthode	Ordre	Ce qu’elle exige	Itérations pour douze décimales
Dichotomie sur $[1\,;2]$	$1$	la continuité, et un changement de signe	39
Sécante depuis $x_0 = 1$, $x_1 = 2$	$\varphi \approx 1{,}618$	rien de plus que $f$	10
Tangentes depuis $x_0 = 1$	$2$	$f'$, et un bon point de départ	5

L’ordre se lit dans la façon dont l’erreur se contracte. Ordre $1$ : chaque étape multiplie l’erreur par une constante, ici $\frac12$, ce qui fait gagner environ $0{,}301$ décimale par tour, autrement dit un peu plus de trois étapes par décimale. (Ce nombre $0{,}301$ est le logarithme décimal de $2$, l’outil qui compte les chiffres ; il arrivera au chapitre F3, et l’on peut ici se contenter de le constater.) Ordre $p > 1$ : chaque étape élève l’erreur à la puissance $p$, ce qui multiplie par $p$ le nombre de décimales exactes. La différence n’est pas de vitesse, elle est de nature.

Les trois erreurs, tour par tour

Le tableau ci-dessous donne $|x_n - c|$ à chaque itération. Il vaut tous les discours.

$n$	Dichotomie	Sécante	Tangentes
2	$4{,}2 \times 10^{-2}$	$1{,}3 \times 10^{-1}$	$1{,}1 \times 10^{-2}$
3	$2{,}0 \times 10^{-2}$	$1{,}1 \times 10^{-1}$	$2{,}3 \times 10^{-4}$
4	$1{,}1 \times 10^{-2}$	$3{,}7 \times 10^{-2}$	$1{,}0 \times 10^{-7}$
5	$4{,}6 \times 10^{-3}$	$8{,}0 \times 10^{-3}$	$2{,}1 \times 10^{-14}$
6	—	$5{,}4 \times 10^{-4}$	—
7	—	$8{,}4 \times 10^{-6}$	—
8	—	$8{,}8 \times 10^{-9}$	—
9	—	$1{,}4 \times 10^{-13}$	—
10	$1{,}8 \times 10^{-4}$	—	—
20	$4{,}2 \times 10^{-7}$	—	—
30	$2{,}6 \times 10^{-10}$	—	—
39	$5{,}6 \times 10^{-13}$	—	—

Lisez la colonne des tangentes : le nombre de zéros après la virgule double à chaque ligne. Lisez celle de la sécante : il est à peu près la somme des deux précédents, $0{,}9$ ; $1{,}0$ ; $1{,}4$ ; $2{,}1$ ; $3{,}3$ ; $5{,}1$ ; $8{,}1$. C’est la récurrence de Fibonacci, et c’est de là que sort le nombre d’or : l’ordre exact de la sécante est le nombre $p$ vérifiant $p^{2} = p + 1$.

Lisez enfin celle de la dichotomie : trente-neuf étapes pour arriver où la tangente arrive en cinq. Elle est lente. Elle est aussi la seule des trois qui garantisse son erreur avant même de commencer : après $n$ étapes sur $[a\,;b]$, elle est inférieure à $\frac{b-a}{2^{\,n+1}}$, quoi qu’il arrive.

Les trois scripts

def dichotomie(f, a, b, eps):
    n = 0
    while (b - a) / 2 > eps:
        m = (a + b) / 2
        if f(a) * f(m) <= 0:
            b = m
        else:
            a = m
        n += 1
    return (a + b) / 2, n


def secante(f, x0, x1, eps):
    n = 1
    while abs(x1 - x0) > eps:
        pas = f(x1) * (x1 - x0) / (f(x1) - f(x0))
        x0, x1 = x1, x1 - pas
        n += 1
    return x1, n


def tangentes(f, fp, x0, eps):
    n = 0
    while abs(f(x0)) > eps:
        x0 = x0 - f(x0) / fp(x0)
        n += 1
    return x0, n


f  = lambda x: x**5 - x - 1
fp = lambda x: 5 * x**4 - 1

print(dichotomie(f, 1, 2, 1e-12))   # (1.1673039782608612, 39)
print(secante(f, 1, 2, 1e-12))      # (1.1673039782614187, 10)
print(tangentes(f, fp, 1, 1e-12))   # (1.1673039782614396, 5)

Un mot sur la dernière décimale, parce qu’elle raconte quelque chose. Les trois sorties ne coïncident pas au dernier chiffre, et c’est normal : chaque méthode s’arrête sur son propre critère naturel. La dichotomie surveille la largeur de son encadrement, la sécante l’écart entre deux itérés successifs, les tangentes la petitesse de $f(x)$. Ce sont trois façons différentes de dire « c’est assez près », et elles ne s’arrêtent pas au même tour.

Vous lirez par ailleurs, dans l’extra du chapitre F1, quatre itérations pour les tangentes là où cette page en annonce cinq. Ce n’est pas une contradiction, et le critère d’arrêt n’y est pour rien : les deux pages emploient le même. La différence est ailleurs, et la section suivante lui est consacrée.

Le point de départ décide de tout

Un détail que le tableau cache, et qui compte plus que l’ordre de convergence : partez des tangentes depuis $x_0 = 2$ au lieu de $x_0 = 1$, et il faut sept itérations au lieu de cinq. Deux tours perdus à redescendre, parce que la courbe est très raide en $2$ et que la tangente y renvoie loin. Partez au contraire de $x_0 = 1{,}2$, et quatre suffisent : c’est le départ qu’avait choisi l’extra du chapitre F1, et c’est toute l’explication de l’écart entre ses quatre itérations et nos cinq.

C’est le défaut structurel de la méthode la plus rapide : sa vitesse est locale. Loin de la racine, elle n’a aucune garantie, et si $f'$ passe près de zéro, la tangente est presque horizontale et projette le point à l’autre bout du monde. La dichotomie, elle, ne peut pas échouer : elle enferme la racine et resserre. C’est toute l’opposition du chapitre, et elle est ancienne : la sûreté contre la vitesse.

La corde qui ne perd jamais la racine, et qui rampe

Le cours a présenté la fausse position : on garde un encadrement $[a\,;b]$ avec $f(a) < 0 < f(b)$, comme en dichotomie, mais on coupe à la corde plutôt qu’au milieu. Sur notre fonction, convexe sur $[1\,;2]$ puisque $\forall x \in [1\,;2],\ f''(x) = 20x^{3} > 0$, et qui y traverse l’axe en croissant, le cours annonce que la borne $b = 2$ ne bougera jamais. Vérifions, et regardons le prix.

a, b = 1.0, 2.0
for k in range(12):
    c = a - f(a) * (b - a) / (f(b) - f(a))
    if f(a) * f(c) <= 0:
        b = c
    else:
        a = c
    print(k + 1, round(c, 9))

Les douze premières coupes :

Coupe	Valeur	Coupe	Valeur
1	$1{,}033$	7	$1{,}137$
2	$1{,}061$	8	$1{,}144$
3	$1{,}084$	9	$1{,}149$
4	$1{,}102$	10	$1{,}154$
5	$1{,}116$	11	$1{,}157$
6	$1{,}128$	12	$1{,}159$

La prédiction du cours est exacte : la borne droite reste bloquée à $2$, et les coupes montent vers la racine en croissant, toutes du même côté. Mais regardez la douzième : $1{,}159$, alors que la racine vaut $1{,}167$. Douze tours pour deux décimales. La sécante, aux mêmes douze tours, aurait dépassé la précision de la machine.

Voilà le paradoxe, et il est instructif. La fausse position et la sécante emploient exactement la même corde. La sécante garde les deux derniers points ; la fausse position garde les deux points qui encadrent. La seconde y gagne une garantie que la première n’a pas, et elle y perd son ordre : sur une fonction convexe, l’extrémité immobile la condamne à ramper. La convexité, ici, ne fait pas que décorer l’algorithme : c’est elle qui prédit quelle borne se figera, et donc qui explique la lenteur avant même de lancer le calcul.

Ce que choisissent les bibliothèques

Aucune bibliothèque de calcul sérieuse n’implémente une seule de ces trois méthodes. Elles les combinent : on tente une étape rapide, corde ou tangente, on vérifie qu’elle est retombée dans l’encadrement courant, et sinon on la jette pour une bissection. On obtient la vitesse en régime normal et la garantie en cas de mauvaise surprise. C’est l’idée des méthodes hybrides, et c’est la même que celle de l’extra du chapitre F1 sur la course entre dichotomie et tangentes.

Quand la dérivée est chère à calculer, ou simplement indisponible parce que $f$ est le résultat d’une simulation, c’est la corde qui l’emporte : ordre $1{,}618$ sans jamais dériver quoi que ce soit. Entre la tortue et le lièvre, le compromis est doré.

Sources

• Cours F2, paragraphe 6 ; Coulisses n°5, pièce 45 La corde au rythme doré.
• Cours F1, paragraphe 6, et l’extra « La course dichotomie contre Newton » du chapitre F1, dont cette page est la suite directe.
• Tous les nombres de cette page ont été recalculés en Python, la racine de référence étant obtenue par itération de Newton en arithmétique décimale à soixante chiffres.