L’algorithme de Brouncker est une méthode numérique qui permet d’approcher la valeur de logarithmes népériens, notamment \(\ln(2)\), par le biais des fractions continues, notion peu abordée au programme d’ECG. Bien que le programme officiel de mathématiques en ECG se concentre davantage sur la méthode de dichotomie pour l’approximation de réels, l’algorithme de Brouncker offre une perspective algorithmique élégante et efficace pour comprendre comment Python peut manipuler le concept de « boucle ». Nous allons d’abord explorer le fondement mathématique de l’algorithme de Brouncker, avant de détailler sa traduction en langage Python. Nous verrons ensuite comment optimiser la précision de cet algorithme.
Fondements mathématiques et preuve de la relation
Cette première partie s’attache à donner quelques éléments de contextualisation afin de comprendre la formule de Brouncker que nous allons utiliser dans cet algorithme. Tu peux passer cette partie si tu n’as pas encore vu en prépa le développement en série des fonctions usuelles (généralement au programme de deuxième année) et aller droit au but pour la réalisation du script d’approximation.
L’algorithme de Brouncker repose sur la théorie des fractions continues généralisées, concept élégant mais assez peu étudié en prépa ECG. Contrairement à une fraction continue simple où tous les numérateurs sont égaux à \(1\), la forme de Brouncker utilise des suites de numérateurs et de dénominateurs spécifiques. Pour le calcul du logarithme népérien de \(2\), on utilise le développement de la fonction \(x \mapsto \ln(1+x)\).
La formule générale s’énonce ainsi :
\[\ln(1+x) = \frac{x}{1 + \frac{1^2x}{2-x + \frac{2^2x}{3-2x + \frac{3^2x}{4-3x + \dots}}}}\]
Tu remarques directement que pour \(x=1\), les fractions se simplifient, puisque \(2-x= 1\), \(3-2x = 1\), etc.
Pour approfondir cette base, il est essentiel de comprendre comment on passe d’une série entière classique à une fraction continue. La preuve repose sur la transformation d’Euler (hors programme que l’on admettra ici, car la formule ne constitue pas le cœur de notre propos). Le point de départ est le développement en série du logarithme, au programme et souvent étudié en deuxième année de prépa :
\[\ln(1+x) = \sum_{n=1}^{\infty} (-1)^{n-1} \frac{x^n}{n} = x – \frac{x^2}{2} + \frac{x^3}{3} – \dots\]
Or, cette série converge très lentement pour \(x=1\), donc l’algorithme utilisant cette formule mettrait un peu de temps à trouver une approximation satisfaisante de \(ln(2)\). La transformation d’Euler (hors programme comme mentionnée plus haut) stipule qu’une série de type \(S = c_0 + c_0c_1 + c_0c_1c_2 + \dots\) peut se réécrire sous forme de fraction continue, et c’est tout pile ce que l’on cherche à obtenir afin d’exprimer \(ln(2)\) sous forme de fraction continue.
On définit alors la profondeur \(n\) par une relation de récurrence arrière :
\[\begin{cases} R_n = 0 \\ R_{k-1} = \frac{k^2}{1 + R_k} \end{cases}\]
L’approximation finale est alors donnée par :
\[\ln(2) \approx \frac{1}{1 + R_0}\]
Cette structure montre que là où la série de Mercator oscille, la fraction continue de Brouncker encadre la valeur de \(\ln(2)\) de manière beaucoup plus serrée, chaque nouvel étage réduisant l’incertitude de manière géométrique (en effet, chaque étage de la fraction est un réel au carré, donc réduisant fortement l’approximation).
Implémentation de l’algorithme en Python
Contrairement à une suite récurrente classique \(u_{n+1} = f(u_n)\) que l’on calcule de \(0\) vers \(n\), une fraction continue se calcule plus naturellement de la fin vers le début (en partant de la « profondeur » de la fraction).
Je te laisse alors chercher une manière de coder ceci en Python afin d’obtenir une approximation de \(ln(2)\).
Voici une proposition très simple pour coder l’algorithme de Brouncker :
Dans cet algorithme, on reprend notre relation de récurrence qui nous permet de « remonter vers le haut dans la fraction » et on l’implémente au sein d’une boucle avec « for i in range ».
Pour rappel, la fonction range (start, stop, step) génère une suite de nombre compris entre la valeur « start » et la valeur « stop » (ATTENTION, la valeur de stop est toujours exclue), avec un pas « step ».
Ainsi, dans notre exemple, la boucle parcourt les valeurs suivantes « n, n-1, n-2, …, 2, 1 ». En effet, il est important de s’arrêter à \(1\), car la formule de Brouncker nous permet de calcul \(R_{k-1}\) donc on s’arrête effectivement à \(R_0\).
Précision et convergence
L’un des enjeux majeurs en informatique est la vitesse de convergence et, comme nous l’avons mentionné précédemment, c’est pour cela que cet algorithme est plébiscité. Rappelons-le, même si cela semble logique, plus l’entier \(n\) passé en argument est grand, plus la précision sera importante.
Vérifions cela en comparant grâce à un script Python la vitesse de convergence de l’approximation par Brouncker par rapport à la méthode de dichotomie. Naturellement, la dichotomie trouve les zéros d’une fonction, on peut poser \(f(x) = e^x -2\), puisque l’on sait que seul \(ln(2)\) annule cette fonction.
Voici une proposition de code, assez long, mais qui se comprend bien car il se segmente :
Si on regarde chaque partie de ce script, ce dernier se comprend assez aisément. On commence par définir la méthode de Brouncker, comme vu précédemment. Ensuite, on crée la série de Mercator, c’est-à-dire le développement en série de \(ln(1+x)\).
Il s’agit alors de créer deux vecteurs qui calculent à chaque fois la nouvelle approximation de la valeur de \(ln(2)\) pour chaque nouvelle valeur de \(n\) jusqu’à \(n=15\). On obtient alors un graph de ce type en sortie de ce script :
On remarque qu’avec \(n = 15\), l’approximation souhaitée est déjà extrêmement robuste.
Conclusion
L’algorithme de Brouncker est un excellent exercice de style. Il permet de transformer une formule mathématique impressionnante en un script Python de seulement quelques lignes. Si cet algorithme est intéressant, il convient de ne toutefois pas oublier les méthodes plus classiques de calculs de valeur approchée avec Python (comme la dichotomie ou le théorème central limite).
Tu peux retrouver ici le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder ici à toutes nos autres ressources mathématiques !
