Les scripts du laboratoire

Les scripts du cours (paragraphe 6.1) et de la partie VIII de l’Atelier, rassemblés, exécutés et vérifiés. Chaque bloc se copie tel quel dans votre éditeur ; les lignes print ajoutées pour rendre la sortie visible sont signalées par un commentaire. Les sorties reproduites ci-dessous sont celles obtenues à l’exécution réelle, pas des valeurs recopiées de l’énoncé.

1. La dichotomie du cours (§ 6.1)

La brique de base : couper l’intervalle en deux, garder la moitié où $f$ change de signe. La boucle s’arrête quand la longueur passe sous eps.

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

f = lambda x: x**5 - x - 1          # l'equation de l'ouverture du cours

print(dichotomie(f, 1, 2, 1e-6))    # ajoute pour l'affichage

Sortie :

1.1673035621643066

À comparer à la valeur exacte $c = 1{,}1673039782614\ldots$ : l’écart vaut $4{,}2 \times 10^{-7}$, conformément à la garantie (le milieu d’un intervalle de longueur au plus $10^{-6}$ est à $5 \times 10^{-7}$ près de tout point de cet intervalle). Le TVI (§ 6) garantissait que cette racine existe, puisque $f(1) = -1 < 0 < 29 = f(2)$ et que $f$ est continue sur $[1\,;2]$. Le script se contente de l’attraper.

Le piège de la condition d’arrêt. Ici l’arrêt porte sur la longueur de l’intervalle, $b - a \leqslant \varepsilon$. Le milieu rendu est alors à $\frac{\varepsilon}{2}$ près de la racine, donc deux fois meilleur que ce que la condition promet. Les Coulisses, elles, comptent les étapes nécessaires pour que l’erreur du milieu passe sous $\varepsilon$, et trouvent une étape de moins. Les deux comptes sont justes ; dites toujours laquelle des deux quantités vous majorez.

2. Le compteur d’étapes (exercice 29, questions 1 et 2)

On munit la dichotomie d’un compteur pour vérifier expérimentalement la loi des $3{,}32$ étapes par décimale. L’équation est celle du défi de Fibonacci (exercice 24) : $x^3 + 2x^2 + 10x = 20$.

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

f = lambda x: x**3 + 2*x**2 + 10*x - 20   # l'equation de Fibonacci

print("eps        racine approchee    etapes")           # ajoute pour l'affichage
for k in (1, 3, 6, 9, 12):
    racine, n = dichotomie_compteur(f, 1.0, 2.0, 10.0**(-k))
    print("1e-%-2d      %.12f      %2d" % (k, racine, n))

Sortie :

eps        racine approchee    etapes
1e-1       1.343750000000       4
1e-3       1.368652343750      10
1e-6       1.368808269501      20
1e-9       1.368808107916      30
1e-12      1.368808107821      40

Les comptes annoncés par l’énoncé sont confirmés : $4$, $10$, $20$, $30$, $40$. La justification est exacte, pas expérimentale : l’intervalle de départ a pour longueur $1$, sa longueur après $n$ étapes vaut $2^{-n}$, et la boucle s’arrête au premier $n$ tel que $2^{-n} \leqslant 10^{-k}$, c’est-à-dire $2^{n} \geqslant 10^{k}$. Le vérifier en trois lignes :

for k in (1, 3, 6, 9, 12):
    n = 0
    while 2**n < 10**k:
        n = n + 1
    print("plus petit n tel que 2^n >= 10^%-2d : %d" % (k, n))

Sortie :

plus petit n tel que 2^n >= 10^1  : 4
plus petit n tel que 2^n >= 10^3  : 10
plus petit n tel que 2^n >= 10^6  : 20
plus petit n tel que 2^n >= 10^9  : 30
plus petit n tel que 2^n >= 10^12 : 40

Le rythme (question 3). Chaque tranche de trois décimales coûte exactement dix étapes : $\frac{10}{3} \approx 3{,}33$ étapes par décimale, en accord avec la valeur du cours $\log_2(10) = \frac{\ln 10}{\ln 2} \approx 3{,}3219$. Le calcul exact : gagner une décimale, c’est diviser l’erreur par $10$, et chaque étape ne la divise que par $2$ ; il faut donc $n$ étapes avec $2^n \geqslant 10$, soit $n \geqslant \log_2(10)$.

3. Fibonacci expulsé de l’intervalle (exercice 29, question 4)

La plus belle question de la partie : faire mesurer par la dichotomie l’épaisseur du trait de plume de 1225. On affiche l’intervalle courant et l’on surveille la valeur historique $1{,}3688081075$.

f = lambda x: x**3 + 2*x**2 + 10*x - 20
fibonacci = 1.3688081075                  # la valeur du Flos, 1225

a, b = 1.0, 2.0
for n in range(1, 41):
    m = (a + b) / 2
    if f(a) * f(m) <= 0:
        b = m
    else:
        a = m
    if 28 <= n <= 32:                     # on n'affiche que la zone critique
        print("etape %2d : [%.12f ; %.12f]  largeur %.2e  Fibonacci dedans : %s"
              % (n, a, b, b - a, a <= fibonacci <= b))

Sortie :

etape 28 : [1.368808105588 ; 1.368808109313]  largeur 3.73e-09  Fibonacci dedans : True
etape 29 : [1.368808107451 ; 1.368808109313]  largeur 1.86e-09  Fibonacci dedans : True
etape 30 : [1.368808107451 ; 1.368808108382]  largeur 9.31e-10  Fibonacci dedans : True
etape 31 : [1.368808107451 ; 1.368808107916]  largeur 4.66e-10  Fibonacci dedans : True
etape 32 : [1.368808107683 ; 1.368808107916]  largeur 2.33e-10  Fibonacci dedans : False

Expulsion à l’étape 32. La racine exacte vaut $\alpha = 1{,}36880810782137\ldots$, la valeur de Fibonacci $1{,}3688081075$ : l’écart est de $3{,}2 \times 10^{-10}$, il se joue sur la dixième décimale. Tant que l’intervalle est plus large que cet écart, il contient les deux nombres ; dès que sa largeur passe sous $3{,}2 \times 10^{-10}$, il doit choisir, et il choisit la vraie racine.

Rien de contradictoire avec les neuf décimales exactes annoncées : neuf décimales exactes signifient une erreur inférieure à $10^{-9}$, pas inférieure à $10^{-10}$. Huit siècles plus tard, une boucle de cinq lignes vient de mesurer précisément où s’arrêtait la précision de 1225.

4. Le microscope à monstres (exercice 30, questions 1 et 2)

Les sommes partielles de la fonction de Weierstrass : pour $N \in \mathbb{N}$ et tout $x \in \mathbb{R}$,

$W_N(x) = \sum_{n=0}^{N} \left(\frac{1}{2}\right)^{n} \cos\left(3^{n} \pi x\right).$

import numpy as np
import matplotlib.pyplot as plt

def W(x, N):
    return sum(0.5**n * np.cos(3**n * np.pi * x) for n in range(N + 1))

x = np.linspace(-1, 1, 20000)
fig, axes = plt.subplots(1, 4, figsize=(16, 4))
for N, ax in zip((0, 2, 5, 8), axes):
    ax.plot(x, W(x, N), linewidth=0.7)
    ax.set_title("N = %d" % N)
    ax.set_ylim(-2.1, 2.1)
plt.tight_layout()
plt.show()

Question 1. $W_0$ est un simple cosinus. Chaque terme supplémentaire ajoute des oscillations trois fois plus serrées et deux fois plus basses : des rides sur les rides, sans que la silhouette générale change. C’est l’effet du couple $(a, b) = \left(\frac12, 3\right)$.

Question 2, le zoom. On remplace l’intervalle par $[0{,}30\,;0{,}32]$, puis on zoome encore. Pour que la comparaison soit parlante, on mesure au passage l’amplitude d’une parabole ordinaire sur la même fenêtre :

centre = 0.31
demi = 1.0
print("largeur     amplitude de W_12   amplitude de la parabole")
for k in range(5):
    x = np.linspace(centre - demi, centre + demi, 20000)
    w = W(x, 12)
    p = (x - centre)**2 + (x - centre)          # une parabole quelconque
    print("%.0e      %.6f            %.3e" % (2*demi, w.max() - w.min(), p.max() - p.min()))
    demi = demi / 10

Sortie :

largeur     amplitude de W_12   amplitude de la parabole
2e+00      3.991231            2.250e+00
2e-01      1.513969            2.000e-01
2e-02      0.315873            2.000e-02
2e-03      0.040901            2.000e-03
2e-04      0.012650            2.000e-04

Lisez les deux colonnes. La parabole, elle, est dérivable : son amplitude est divisée par exactement $10$ à chaque zoom, parce que sur une petite fenêtre elle se confond avec sa tangente, dont l’amplitude est proportionnelle à la largeur. Pour $W_{12}$, l’amplitude n’est divisée que par $4$ environ, et jamais par $10$. Non, la courbe ne se lisse pas.

Le chiffre $4$ n’est pas un hasard : la théorie prévoit une division par $10^{\alpha}$ avec $\alpha = \frac{\ln 2}{\ln 3} \approx 0{,}631$, soit $10^{0{,}631} \approx 4{,}3$. Les fluctuations de la colonne (entre $2{,}6$ et $7{,}7$) viennent de ce que les fenêtres choisies ne sont pas alignées sur les puissances de $3$ ; sur des fenêtres alignées, le rapport devient exactement $2$ pour un zoom de facteur $3$. Ce n’est donc pas un artefact d’affichage : c’est l’auto-similarité de la construction, démontrée sur la page « Le zoom sans fond dans la fonction de Weierstrass ».

5. La majoration de $W_8$ (exercice 30, question 3)

Le seul résultat de l’exercice qui se démontre entièrement, et il ne coûte que la somme géométrique du chapitre A1. Pour tout $x \in \mathbb{R}$ :

$\left|W_8(x)\right| \leqslant \sum_{n=0}^{8} \left(\frac{1}{2}\right)^{n} \left|\cos\left(3^{n}\pi x\right)\right| \leqslant \sum_{n=0}^{8} \left(\frac{1}{2}\right)^{n} = \frac{1 - \left(\frac12\right)^{9}}{1 - \frac12} = 2 - \frac{1}{2^{8}} < 2.$

La vérification numérique, sur vingt mille points :

import numpy as np

def W(x, N):
    return sum(0.5**n * np.cos(3**n * np.pi * x) for n in range(N + 1))

x = np.linspace(-1, 1, 20000)
print("max de |W_8| observe :", abs(W(x, 8)).max())
print("borne demontree      :", 2 - 1/2**8)

Sortie :

max de |W_8| observe : 1.99609375
borne demontree      : 1.99609375

La borne est atteinte, au dernier chiffre près : en $x = 0$, tous les cosinus valent $1$ à la fois et la somme vaut exactement $2 - \frac{1}{2^8} = 1{,}99609375$. La majoration n’a rien perdu en route, et c’est rare : chaque inégalité de la chaîne devient une égalité en ce point.

6. Et la question 4, celle qui n’a pas de script

La dernière question de l’Atelier est marquée d’une étoile, et elle ne se code pas. Pourquoi ce procédé de tracé ne pourra-t-il jamais montrer la vraie $W$ ?

Parce que le tracé ne montre jamais que $W_N$, une somme finie de fonctions dérivables, donc une fonction parfaitement lisse dont les rides s’arrêtent à l’échelle $3^{-N}$. Zoomez au-delà, et $W_N$ finit par se confondre avec sa tangente, comme n’importe quelle parabole. La vraie $W$ est la limite de ces sommes : sa rugosité à toutes les échelles n’existe qu’après le passage à la limite, celui-là même qu’aucun écran, aucune imprimante et aucun crayon ne peut effectuer.

Le monstre commence exactement là où le dessin s’arrête. C’est la phrase du chapitre entier.

Sources

• Cours F1, § 6.1 (la dichotomie instrumentée) ; Atelier, partie VIII, exercices 29 et 30, et leur corrigé.
• Tous les scripts de cette page ont été exécutés ; les sorties sont recopiées telles quelles.