Algorithme de Borwein

En analyse appliquée, l'algorithme de Borwein est un algorithme conçu par Jonathan et Peter Borwein pour calculer la valeur de $1 / π$ . Cet algorithme est l'un de ceux publiés dans leur livre Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity^[1].

Série de Ramanujan-Sato

Ces deux exemples utilisent une série de Ramanujan-Sato. L'algorithme de Chudnovsky associé utilise un discriminant de nombre de classe égal à 1.

Nombre de classe à 2 (1989)

On commence par fixer les paramètres^[2]

\begin{matrix} A & = 212175710912 \sqrt{61} + 1657145277365 \\ B & = 13773980892672 \sqrt{61} + 107578229802750 \\ C & = {(5280 (236674 + 30303 \sqrt{61}))}^{3} \end{matrix}

Alors

\frac{1}{π} = 12 \sum_{n = 0}^{\infty} \frac{(- 1)^{n} (6 n)! (A + n B)}{(n!)^{3} (3 n)! C^{n + \frac{1}{2}}}

Chaque terme supplémentaire de la somme partielle ajoute environ 25 chiffres à la précision.

Nombre de classe à 4 (1993)

On commence par fixer les paramètres^[3]

\begin{matrix} A = & 63365028312971999585426220 \\ + 28337702140800842046825600 \sqrt{5} \\ + 384 \sqrt{5} (10891728551171178200467436212395209160385656017 \\ + {4870929086578810225077338534541688721351255040 \sqrt{5})}^{\frac{1}{2}} \\ B = & 7849910453496627210289749000 \\ + 3510586678260932028965606400 \sqrt{5} \\ + 2515968 \sqrt{3110} (6260208323789001636993322654444020882161 \\ + {2799650273060444296577206890718825190235 \sqrt{5})}^{\frac{1}{2}} \\ C = & - 214772995063512240 \\ - 96049403338648032 \sqrt{5} \\ - 1296 \sqrt{5} (10985234579463550323713318473 \\ + {4912746253692362754607395912 \sqrt{5})}^{\frac{1}{2}} \end{matrix}

Alors

\frac{\sqrt{- C^{3}}}{π} = \sum_{n = 0}^{\infty} \frac{(6 n)!}{(3 n)! (n!)^{3}} \frac{A + n B}{C^{3 n}}

Chaque terme supplémentaire de la série ajoute environ 50 chiffres au résultat.

Algorithmes itératifs

Convergence quadratique (1984)

On commence par fixer les paramètres^[4]

a_{0} = \sqrt{2}, b_{0} = 0, p_{0} = 2 + \sqrt{2}

Ensuite, on utilise le processus itératif

\begin{matrix} a_{n + 1} & = \frac{\sqrt{a_{n}} + \frac{1}{\sqrt{a_{n}}}}{2} \\ b_{n + 1} & = \frac{(1 + b_{n}) \sqrt{a_{n}}}{a_{n} + b_{n}} \\ p_{n + 1} & = \frac{(1 + a_{n + 1}) p_{n} b_{n + 1}}{1 + b_{n + 1}} \end{matrix}

Alors $p k$ converge quadratiquement vers $π$ ; c'est-à-dire que chaque itération double approximativement le nombre de chiffres corrects. L'algorithme n'est pas auto-correcteur : chaque itération doit être effectuée avec le nombre souhaité de chiffres corrects pour le calcule de $π$ .

Convergence cubique (1991)

On commence par fixer les paramètres

a_{0} = \frac{1}{3}, s_{0} = \frac{\sqrt{3} - 1}{2}

Ensuite, on itère selon le processus

\begin{matrix} r_{k + 1} & = \frac{3}{1 + 2 {(1 - s_{k}^{3})}^{\frac{1}{3}}} \\ s_{k + 1} & = \frac{r_{k + 1} - 1}{2} \\ a_{k + 1} & = r_{k + 1}^{2} a_{k} - 3^{k} (r_{k + 1}^{2} - 1) \end{matrix}

Alors $a k$ converge cubiquement vers $1 / π$ ; c’est-à-dire que chaque itération triple approximativement le nombre de chiffres corrects.

Convergence quartique (1985)

On commence par fixer les paramètres ^[5]

a_{0} = 2 {(\sqrt{2} - 1)}^{2}, y_{0} = \sqrt{2} - 1

Ensuite, on itère selon

\begin{matrix} y_{k + 1} & = \frac{1 - {(1 - y_{k}^{4})}^{\frac{1}{4}}}{1 + {(1 - y_{k}^{4})}^{\frac{1}{4}}} \\ a_{k + 1} & = a_{k} {(1 + y_{k + 1})}^{4} - 2^{2 k + 3} y_{k + 1} (1 + y_{k + 1} + y_{k + 1}^{2}) \end{matrix}

Alors $a k$ converge quartiquement vers $1 / π$ ; c’est-à-dire que chaque itération quadruple approximativement le nombre de chiffres corrects. L'algorithme n'est pas auto-correcteur : chaque itération doit être effectuée avec le nombre souhaité de chiffres corrects pour le calcul de π.

Une itération de cet algorithme est équivalente à deux itérations de l'algorithme de Brent-Salamin.

Convergence quintique

On commence par fixer les paramètres

a_{0} = \frac{1}{2}, s_{0} = 5 (\sqrt{5} - 2) = \frac{5}{ϕ^{3}}

où $ϕ = \frac{1 + \sqrt{5}}{2}$ est le nombre d'or. Ensuite, on itère selon

\begin{matrix} x_{n + 1} & = \frac{5}{s_{n}} - 1 \\ y_{n + 1} & = {(x_{n + 1} - 1)}^{2} + 7 \\ z_{n + 1} & = {(\frac{1}{2} x_{n + 1} (y_{n + 1} + \sqrt{y_{n + 1}^{2} - 4 x_{n + 1}^{3}}))}^{\frac{1}{5}} \\ a_{n + 1} & = s_{n}^{2} a_{n} - 5^{n} (\frac{s_{n}^{2} - 5}{2} + \sqrt{s_{n} (s_{n}^{2} - 2 s_{n} + 5)}) \\ s_{n + 1} & = \frac{25}{{(z_{n + 1} + \frac{x_{n + 1}}{z_{n + 1}} + 1)}^{2} s_{n}} \end{matrix}

Alors $a k$ converge quintiquement vers $1 / π$ (c’est-à-dire que chaque itération quintuple approximativement le nombre de chiffres corrects), et on a même l'encadrement suivant :

0 < a_{n} - \frac{1}{π} < 16 \cdot 5^{n} \cdot e^{- 5^{n}} π

Convergence nonique

On commence par fixer les paramètres

a_{0} = \frac{1}{3}, r_{0} = \frac{\sqrt{3} - 1}{2}, s_{0} = {(1 - r_{0}^{3})}^{\frac{1}{3}}

Ensuite, on itère selon

\begin{matrix} t_{n + 1} & = 1 + 2 r_{n} \\ u_{n + 1} & = {(9 r_{n} (1 + r_{n} + r_{n}^{2}))}^{\frac{1}{3}} \\ v_{n + 1} & = t_{n + 1}^{2} + t_{n + 1} u_{n + 1} + u_{n + 1}^{2} \\ w_{n + 1} & = \frac{27 (1 + s_{n} + s_{n}^{2})}{v_{n + 1}} \\ a_{n + 1} & = w_{n + 1} a_{n} + 3^{2 n - 1} (1 - w_{n + 1}) \\ s_{n + 1} & = \frac{{(1 - r_{n})}^{3}}{(t_{n + 1} + 2 u_{n + 1}) v_{n + 1}} \\ r_{n + 1} & = {(1 - s_{n + 1}^{3})}^{\frac{1}{3}} \end{matrix}

Alors $a k$ converge noniquement vers $1 / π$ ; c’est-à-dire que chaque itération multiplie approximativement le nombre de chiffres corrects par neuf^[6].

Voir aussi

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Borwein's algorithm » (voir la liste des auteurs).

↑ (en) Jonathan M. Borwein et Peter B. Borwein, Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity, New York, Wiley, 1987 (lire en ligne).
↑ (en) Bailey, « Peter Borwein: A Visionary Mathematician », Notices of the American Mathematical Society, vol. 70, n^o 4,‎ 1^er avril 2023, p. 610–613 (ISSN 0002-9920, DOI 10.1090/noti2675)
↑ (en) Borwein et Borwein, « Class number three Ramanujan type series for 1/π », Journal of Computational and Applied Mathematics, vol. 46, n^os 1–2,‎ 1993, p. 281–290 (DOI 10.1016/0377-0427(93)90302-R)
↑ (en) Jörg Arndt et Christoph Haenel, $π$ Unleashed, Springer-Verlag, 1998 (ISBN 3-540-66572-2), p. 236
↑ Ronald Mak, The Java Programmers Guide to Numerical Computation, Pearson Educational, 2003 (ISBN 0-13-046041-9), p. 353
↑ Henrik Vestermark, « Practical implementation of π Algorithms »,‎ 4 novembre 2016 (consulté le 29 novembre 2020)

Liens externes

(en) Eric W. Weisstein, « Pi Formulas », sur MathWorld

Portail de l'analyse

[1] (en) Jonathan M. Borwein et Peter B. Borwein, Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity, New York, Wiley, 1987 (lire en ligne).

[Bailey_Borwein_2023-2] (en) Bailey, « Peter Borwein: A Visionary Mathematician », Notices of the American Mathematical Society, vol. 70, n^o 4,‎ 1^er avril 2023, p. 610–613 (ISSN 0002-9920, DOI 10.1090/noti2675)

[Borwein_Borwein_1993_pp._281–290-3] (en) Borwein et Borwein, « Class number three Ramanujan type series for 1/π », Journal of Computational and Applied Mathematics, vol. 46, n^os 1–2,‎ 1993, p. 281–290 (DOI 10.1016/0377-0427(93)90302-R)

[4] (en) Jörg Arndt et Christoph Haenel, $π$ Unleashed, Springer-Verlag, 1998 (ISBN 3-540-66572-2), p. 236

[5] Ronald Mak, The Java Programmers Guide to Numerical Computation, Pearson Educational, 2003 (ISBN 0-13-046041-9), p. 353

[6] Henrik Vestermark, « Practical implementation of π Algorithms »,‎ 4 novembre 2016 (consulté le 29 novembre 2020)

[1]

[2]

[3]

[4]

[5]

[6]