Exercice 30 L'algorithme de Briggs

Partie A

1. Démontrons par récurrence la propriété $P_n : \text{« } u_{n}>0 \text{ »}$.

Initialisation : $u_{0}=x>0$ par hypothèse, donc $P_0$ est vraie.

Hérédité : Soit $k\in\mathbb{N}$. Supposons $u_{k}>0$. Alors $\sqrt{u_{k}}$ existe et est strictement positif, donc $u_{k+1}>0$ : la propriété $P_{k+1}$ est vraie.

Conclusion : Par principe de récurrence, $\boxed{u_{n}>0 \text{ pour tout } n\in\mathbb{N}.}$

Cette étape n'est pas une formalité : elle garantit que la racine carrée et le logarithme utilisés ensuite ont bien un sens.

2. Démontrons par récurrence la propriété $P_n : \text{« } \ln\left(u_{n}\right)=\dfrac{\ln(x)}{2^{\,n}} \text{ »}$.

Initialisation : Pour $n=0$ : $\ln\left(u_{0}\right)=\ln(x)$ et $\dfrac{\ln(x)}{2^{0}}=\ln(x)$. Vrai.

Hérédité : Soit $k\in\mathbb{N}$. Supposons $\ln\left(u_{k}\right)=\dfrac{\ln(x)}{2^{\,k}}$. Alors, en utilisant $\ln\left(\sqrt{a}\right)=\dfrac{1}{2}\ln(a)$ : $$\ln\left(u_{k+1}\right)=\ln\left(\sqrt{u_{k}}\right)=\frac{1}{2}\ln\left(u_{k}\right) =\frac{1}{2}\times\frac{\ln(x)}{2^{\,k}}=\frac{\ln(x)}{2^{\,k+1}}$$

Conclusion : $\boxed{\text{Pour tout } n\in\mathbb{N},\ \ln\left(u_{n}\right)=\dfrac{\ln(x)}{2^{\,n}}.}$

3. Le numérateur $\ln(x)$ est un nombre fixé, tandis que $2^{\,n}\to+\infty$ : $$\boxed{\lim_{n\to+\infty}\ln\left(u_{n}\right)=0}$$ Comme $u_{n}=\mathrm{e}^{\ln\left(u_{n}\right)}$ et que la fonction exponentielle est continue en $0$ : $$\boxed{\lim_{n\to+\infty}u_{n}=\mathrm{e}^{0}=1}$$

4. De la question 2 on tire $2^{\,n}=\dfrac{\ln(x)}{\ln\left(u_{n}\right)}$, valable tant que $\ln\left(u_{n}\right)\neq 0$, c'est-à-dire tant que $u_{n}\neq 1$. En reportant : $$v_{n}=2^{\,n}\left(u_{n}-1\right) =\boxed{\ln(x)\times\frac{u_{n}-1}{\ln\left(u_{n}\right)}}$$

5. D'après la question 3, $u_{n}\to 1$, donc $\boxed{t_{n}=u_{n}-1\longrightarrow 0}$. De plus $u_{n}=1+t_{n}$, d'où $$\frac{u_{n}-1}{\ln\left(u_{n}\right)}=\boxed{\frac{t_{n}}{\ln\left(1+t_{n}\right)}}$$

6. La limite du cours $\displaystyle\lim_{t\to 0}\frac{\ln(1+t)}{t}=1$ donne, par passage à l'inverse, $\dfrac{t_{n}}{\ln\left(1+t_{n}\right)}\longrightarrow 1$. Par produit : $$v_{n}=\ln(x)\times\frac{t_{n}}{\ln\left(1+t_{n}\right)}\longrightarrow \ln(x)\times 1$$

$$\boxed{\lim_{n\to+\infty}v_{n}=\ln(x)}$$ L'algorithme calcule donc bien un logarithme, à partir de la seule extraction de racines carrées — ce que Briggs savait faire à la main.

Partie B

7.

from math import sqrt

def briggs(x, n):
    u = x
    for i in range(n):
        u = sqrt(u)
    return 2**n * (u - 1)

8. Pour $x=2$ :

9. Jusqu'à $n=30$, l'approximation s'améliore régulièrement : l'erreur passe de $8\times 10^{-3}$ à $2\times 10^{-9}$. Puis tout se dégrade brutalement. $$\boxed{\text{Pour } n=40 \text{ on perd cinq décimales, et pour } n=50 \text{ le résultat } 0{,}5 \text{ est absurde.}}$$ En poursuivant, on obtiendrait même $0$ pour $n=60$.

10. Le nombre $u_{n}$ devient extrêmement proche de $1$. Or une machine ne conserve qu'une quinzaine de chiffres significatifs : lorsque $u_{n}$ vaut par exemple $1{,}000\,000\,000\,000\,6$, la soustraction $u_{n}-1$ ne conserve qu'un seul chiffre exact, tous les autres ayant été perdus au moment de l'arrondi de $u_{n}$. $$\boxed{\begin{array}{l} \text{C'est le phénomène de \textbf{cancellation} : soustraire deux nombres très proches}\\[1mm] \text{détruit la précision. Le facteur } 2^{\,n} \text{ amplifie ensuite l'erreur commise.} \end{array}}$$

11. Le meilleur compromis se situe autour de $\boxed{n=25 \text{ à } 30}$ : assez grand pour que $t_{n}$ soit petit, assez petit pour que la soustraction reste fiable.

Il est remarquable qu'augmenter le nombre d'itérations puisse dégrader le résultat : en analyse numérique, plus de calculs ne signifie pas toujours plus de précision.