Un critère d'arrêt justifié par le reste

Ce qu'on montre. Qu'un calcul numérique de somme n'a de valeur que s'il majore son reste — et qu'ici le reste se calcule exactement, ce qui rend le critère d'arrêt certain.

Le reste, exactement. Posons $R_n=\sum _{k=n+1}^{+\infty }\frac{k}{2^k}$ et faisons le changement d'indice $k=n+1+j$ : $$R_n=\sum _{j=0}^{+\infty }\frac{n+1+j}{2^{n+1+j}}=\frac{1}{2^{n+1}}\left[(n+1)\sum _{j=0}^{+\infty }{\left(\frac{1}{2}\right)}^j+\sum _{j=0}^{+\infty }j{\left(\frac{1}{2}\right)}^j\right].$$ Les deux séries de référence donnent $\sum _{j\ge 0}{\left(\frac{1}{2}\right)}^j=2$ et $$\sum _{j\ge 0}j{\left(\frac{1}{2}\right)}^j=\frac{1}{2}\sum _{j\ge 1}j{\left(\frac{1}{2}\right)}^{j-1}=\frac{1}{2}\cdot \frac{1}{{\left(1-\frac{1}{2}\right)}^2}=\frac{1}{2}\times 4=2.$$ Donc $$R_n=\frac{2(n+1)+2}{2^{n+1}}=\frac{n+2}{2^n}.$$ Contrôle : pour $n=0$, $R_0=2$ — c'est bien la somme totale, que le même calcul donne pour $S$.

Le critère d'arrêt. On somme tant que $R_n>\epsilon$, c'est-à-dire tant que $\frac{n+2}{2^n}>\epsilon$ ; à l'arrêt, l'erreur commise est garantie inférieure à $\epsilon$.

Le programme.

def somme_approchee(eps):
    """Somme de k/2**k, arretee quand le reste exact passe sous eps."""
    S = 0.0
    n = 0
    while (n + 2) / 2.0 ** n > eps:     # reste d'ordre n
        n = n + 1
        S = S + n / 2.0 ** n
    return S, n

print(somme_approchee(1e-10))    # (1.9999999999254..., 39)

Le résultat. Le programme s'arrête à $n=39$ et renvoie une valeur $S\approx 1,9999999999254$. Vérification du rang : pour $n=38$, $\frac{40}{2^{38}}\approx 1,46\cdot 10^{-10}>10^{-10}$, tandis que pour $n=39$, $\frac{41}{2^{39}}\approx 7,5\cdot 10^{-11}\le 10^{-10}$. Trente-neuf termes suffisent donc, et trente-huit ne suffiraient pas.

La valeur exacte. La même série de référence donne $$\sum _{k=1}^{+\infty }\frac{k}{2^k}=\frac{1}{2}\sum _{k\ge 1}k{\left(\frac{1}{2}\right)}^{k-1}=\frac{1}{2}\times 4=2,$$ et l'écart observé, $2-S\approx 7,46\cdot 10^{-11}$, est bien inférieur au $10^{-10}$ annoncé — il vaut d'ailleurs exactement le reste $R_{39}=\frac{41}{2^{39}}$, ce qui valide la formule.

Point délicat. Un critère d'arrêt fondé sur le terme (« s'arrêter quand $\frac{n}{2^n}<\epsilon$ ») ne garantit rien en général : pour la série harmonique, le terme tend vers $0$ alors que le reste n'existe même pas. C'est toujours le reste, jamais le terme, qui doit être contrôlé.