Algorithme de Briggs - Python

Principe de l’algorithme de Briggs

Une première approximation

Donnons pour commencer l’approximation sur laquelle repose l’algorithme.

À retenir

Si $x$ est suffisamment proche de $1$, alors nous avons :

$$\ln{(x)}\approx x-1$$

Nous pouvons comprendre intuitivement cette approximation de manière graphique, en regardant la courbe représentative $\mathscr C$ de la fonction logarithme népérien et sa tangente $\mathcal T$ au point d’abscisse $1$ :

Nous voyons que, au voisinage de $1$, $\mathscr C$ et $\mathcal T$ se « confondent ».

Nous avons appris en cours que la fonction logarithme népérien est dérivable sur $]0\ ;\, +\infty[$ et que, pour tout $x > 0$ :

$$\ln^{\prime}(x)=\dfrac 1x$$

Et nous savons donc déterminer l’équation de $\mathcal T$ :

$$\begin{aligned} y&=\ln^{\prime}(1)(x-1)+\ln{(1)} \\ \textcolor{#A9A9A9}{\text{Soit\ :\ }} y&=\dfrac 11(x-1)+\ln{(1)} \end{aligned}$$

Comme $\ln{(1)}=0$, nous obtenons finalement :

$$\mathcal T:y=x-1$$

• Ainsi, quand $x$ est assez proche de $1$ et comme $\mathscr C$ et $\mathcal T$ se « confondent » au voisinage de $1$, nous avons : $\ln{(x)}\approx x-1$.

Approximation de $\ln{(2)}$

Nous allons ici montrer le principe de l’algorithme de Briggs à travers un exemple : nous cherchons à donner une valeur approchée de $\ln{(2)}$.

Pour utiliser l’approximation donnée plus haut, il nous faut, en partant de $2$, nous rapprocher de $1$ autant que possible.

• Pour cela, nous nous servons de la racine carrée.

En effet, prenons un nombre strictement positif $a$.
En calculant successivement la racine carrée de $a$, puis la racine carrée du résultat, et ainsi de suite tant que c’est nécessaire, nous pouvons nous approcher autant que nous le souhaitons de $1$.

Pour $2$, nous souhaitons, grâce aux racines carrées successives, nous ramener à une valeur $V$ dont la distance à $1$ est inférieure ou égale à $10^{-2}$, c’est-à-dire que nous voulons :

$$\vert V - 1 \vert \leq 10^{-2}$$

Le tableau suivant donne les résultats successifs obtenus avec une calculatrice :

Nous voyons que, en $7$ étapes (soit en prenant $7$ fois la racine carrée du résultat précédent), nous arrivons à la précision demandée, avec une distance à $1$ inférieure ou égale à $10^{-2}$.

• Nous trouvons ainsi $V$ :

$$\begin{aligned} V&= \sqrt{\sqrt{\sqrt {\sqrt{\sqrt{\sqrt{\sqrt 2}}}}}} \\ &= 1,00542… \end{aligned}$$

Nous pouvons maintenant considérer que $V$ est suffisamment proche de $1$ pour appliquer l’approximation :

$$\ln{(V)}\approx V-1$$

Or, nous avons vu dans le cours la propriété suivante :

Propriété

Pour tout $a > 0$, nous avons :

$$\ln{(\sqrt{a})}=\dfrac 12 \ln{(a)}$$

Ainsi, nous avons :

$$\begin{aligned} \ln{(\sqrt 2)}&=\dfrac 12 \ln{(2)} \\ \ln\left(\sqrt{\sqrt 2}\right) &= \dfrac 12 \ln{(\sqrt 2)} = \left(\dfrac 12\right)^2\ln{(2)} = \dfrac 1{2^2}\ln{(2)} \\ \ln\left(\sqrt{\sqrt{\sqrt 2}}\right) &= \dfrac 12 \ln\left(\sqrt{\sqrt 2}\right)=\dfrac 1{2^3}\ln{(2)} \\ &\footnotesize{\textcolor{#A9A9A9}{\text{et ainsi de suite}}} \end{aligned}$$

Il a fallu $7$ étapes pour obtenir $V$, nous avons donc :

$$\ln{(V)}=\dfrac1{2^7}\ln 2 \approx V - 1$$

Nous en déduisons donc une approximation de $\ln{(2)}$ :

$$\begin{aligned} \ln{(2)}&\approx 2^7(V-1) \\ &\approx 0,69502… \footnotesize{\textcolor{#A9A9A9}{\text{ [avec la calculatrice]}}} \end{aligned}$$

Utilisons encore notre calculatrice, cette fois en faisant appel directement à la fonction $\ln$ :

$$\ln{(2)} = 0,69314…$$

L’approximation est relativement correcte, mais nous pouvons encore l’améliorer, cette fois en déterminant $V$ avec une précision inférieure ou égale à $10^{-3}$ : il faut alors $10$ étapes pour obtenir $V=1,00067…$

• Nous obtenons alors :

$$\begin{aligned} \ln{(2)}&\approx 2^{10}(V-1) \\ &\approx 0,69338… \end{aligned}$$

Bien sûr, en réduisant à chaque fois la distance de $V$ à $1$, nous pouvons approcher de manière de plus en plus précise la valeur de $\ln{(2)}$.

Généralisation

Ce que nous avons fait pour $\ln{(2)}$, nous pouvons le faire pour $\ln{(a)}$, pour tout $a$ strictement positif.

À retenir

• On calcule la racine carrée de $a$, puis la racine carrée du résultat, et ainsi de suite jusqu’à obtenir la valeur $V$ proche de $1$ avec la précision voulue.
• Soit $r$ le nombre de racines carrées successives qu’il a fallu pour obtenir $V$.
• L’approximation de $\ln{(a)}$ par l’algorithme de Briggs est alors donnée par :

$$\ln{(a)}\approx 2^r(V-1)$$

Algorithme Python

Nous avons maintenant compris le principe de l’algorithme. Eh bien, le gros du travail est fait ! Car le traduire en un programme Python est alors assez simple.

• Tout d’abord, la racine carrée va être importante, nous l’avons vu ?
• Nous importons donc la fonction $\purple{\text{sqrt}}$ du module $\purple{\text{math}}$.

• Puis nous définissons la fonction $\purple{\text{briggs}}$, qui prend en paramètres :
• $\purple{\text{a}}$, le nombre dont nous voulons donner une valeur approchée du logarithme népérien ;
• $\purple{\text{p}}$, la précision souhaitée.

• Pour éviter que la programme renvoie une erreur si le $\purple{\text{a}}$ entré est négatif, nous commençons par vérifier que nous cherchons bien le logarithme népérien d’un nombre strictement positif.

• Nous souhaitons garder en mémoire la valeur initiale de $\purple{\text{a}}$ (pour l’affichage final). Nous créons ainsi une variable $\purple{\text{V}}$, que nous initialisons avec la valeur de $\purple{\text{a}}$.
• C’est sur cette variable $\purple{\text{V}}$ que nous travaillerons avec les racines carrées.

• Nous l’avons expliqué dans la première partie, nous allons avoir besoin de compter le nombre de racines carrées successives auxquelles nous ferons appel.
• Nous initialisons donc le compteur $\purple{\text{r}}$ à $\purple{\text{0}}$.

• Nous allons calculer la racine carrée de $\purple{\text{V}}$ tant que la distance de sa valeur à $1$ est strictement supérieure à $\purple{\text{p}}$.
• Nous utilisons pour cela une boucle $\purple{\text{while}}$.

• Nous calculons donc la racine carrée de $\purple{\text{V}}$ et assignons à $\purple{\text{V}}$ sa nouvelle valeur.
• Et nous indiquons que nous avons calculé une racine carrée, en incrémentant $\purple{\text{r}}$.

• Au sortir de la boucle, $\purple{\text{V}}$ contiendra la valeur aussi proche de $1$ que l’indiquait $\purple{\text{p}}$.
  Et $\purple{\text{r}}$ contiendra le nombre de fois que la boucle a été parcourue, c’est-à-dire le nombre de racines carrées successives.
• Nous utilisons donc la formule de la première partie et assignons le résultat à une varialbe $\purple{\text{l}}$ : il s’agit de l’approximation recherchée.

• Nous demandons enfin au programme d’afficher le résultat $\purple{\text{l}}$, en rappelant le nombre $\purple{\text{a}}$ entré en paramètre.

• Nous n’oublions pas de prévoir le cas où $\purple{\text{a}} \leq 0$.
• Nous demandons alors au programme de répondre simplement que $\ln$ n’est pas définie en $\purple{\text{a}}$.

À retenir

Le programme est terminé :

$\begin{aligned} \textcolor{#A9A9A9}{\text{1}}&\quad\text{from math import sqrt} \\ \textcolor{#A9A9A9}{\text{2}}& \\ \textcolor{#A9A9A9}{\text{3}}&\quad\text{def briggs(a, p):} \\ \textcolor{#A9A9A9}{\text{4}}&\quad\qquad\text{if a > 0:} \\ \textcolor{#A9A9A9}{\text{5}}&\quad\qquad\qquad\text{V = a} \\ \textcolor{#A9A9A9}{\text{6}}&\quad\qquad\qquad\text{r = 0} \\ \textcolor{#A9A9A9}{\text{7}}&\quad\qquad\qquad\text{while abs(V - 1) > p:} \\ \textcolor{#A9A9A9}{\text{8}}&\quad\qquad\qquad\qquad\text{V = sqrt(V)} \\ \textcolor{#A9A9A9}{\text{9}}&\quad\qquad\qquad\qquad\text{r = r + 1} \\ \textcolor{#A9A9A9}{\text{10}}&\quad\qquad\qquad\text{l = 2$\ast\ast\,$r $\ast$ (V - 1)} \\ \textcolor{#A9A9A9}{\text{11}}&\quad\qquad\qquad\text{print($^{\backprime\backprime}$ln($\lbrace\rbrace$)$\approx\lbrace\rbrace^{\prime\prime}$.format(a, l))} \\ \textcolor{#A9A9A9}{\text{12}}&\quad\qquad \text{else:} \\ \textcolor{#A9A9A9}{\text{13}}&\quad\qquad\qquad\text{ print($^{\backprime\backprime}$La fonction logarithme népérien} \\ &\quad\qquad\qquad\quad\text{n'est pas définie en$^{\prime\prime}$, a)} \end{aligned}$

Exemple

Vous pouvez maintenant approcher, par exemple, la valeur de $\ln{(2)}$ avec une précision de $10^{-5}$, en saisissant la commande :

$$\purple{\text{briggs(2, 0.00001)}} \textcolor{#A9A9A9}{\text{ ou }}\purple{\text{briggs(2, 10$\ast\ast\,$(-5))}}$$

• Normalement, vous aurez en retour :

$$\purple{\text{ln(2)$\approx$0.6931490133574698}}$$

Résultat à comparer avec celui que donne la fonction $\ln$ de votre calculatrice.