Un seuil sur une suite récurrente

Le code.

def seuil(eps):
    u = 3.0
    n = 0
    v = 0.5 * (u + 6 / u)
    while abs(v - u) >= eps:
        u = v
        v = 0.5 * (u + 6 / u)
        n = n + 1
    return n, v

print(seuil(1e-10))        # (4, 2.449489742783178)
print(6 ** 0.5)            #      2.449489742783178

Pourquoi la suite converge vers $\sqrt{6}$. Si $u_n\to \ell$ avec $\ell >0$, le passage à la limite dans la relation de récurrence donne $\ell =\frac{1}{2}\left(\ell +\frac{6}{\ell }\right)$, soit $2{\ell }^2={\ell }^2+6$, donc ${\ell }^2=6$ et $\ell =\sqrt{6}$ (la suite reste positive, $u_0>0$ et la relation conservant la positivité).

Les premiers termes, à la main.

$$u_0=3,u_1=\frac{1}{2}\left(3+2\right)=2,5,u_2=\frac{1}{2}\left(2,5+2,4\right)=2,45,$$

puis $u_3\approx 2,4494898$ et $u_4\approx 2,4494897$. La valeur exacte est $\sqrt{6}\approx 2,449489743$.

Pourquoi si peu de tours. Le nombre de décimales exactes double à chaque étape : $1$, puis $2$, puis $5$, puis $10$. Trois ou quatre tours suffisent donc à atteindre la précision maximale d'un flottant, là où une dichotomie sur $[2,3]$ en demanderait une trentaine — chaque tour n'y gagnant qu'un facteur $2$, c'est-à-dire environ un tiers de décimale.

Le test d'arrêt porte sur l'écart entre deux termes, pas sur l'écart à $\sqrt{6}$ : la limite est justement ce qu'on ignore. C'est le test disponible en pratique, et il n'est légitime que parce que la convergence est rapide — sur une suite qui avance très lentement, deux termes consécutifs peuvent être proches alors que la limite est encore loin.

Un garde-fou à ne pas oublier. Si l'on choisit eps plus petit que la précision des flottants (environ $10^{-16}$ en valeur relative), l'écart $|v-u|$ peut ne jamais descendre sous le seuil et la boucle tourner sans fin. En pratique on borne aussi le nombre de tours.