Алгоритм Борвейна

Метод расчета значения числа Пи

Алгоритм Борвейна был разработан Джонатаном и Питером Борвейном для вычисления значения . Этот и другие алгоритмы можно найти в книге Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity . ^[1] $1/\пи$

Ряд Рамануджана–Сато

Эти два примера являются рядом Рамануджана–Сато . Соответствующий алгоритм Чудновского использует дискриминант с классом номер 1.

Класс № 2 (1989)

Начните с настройки ^[2]

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

Затем

{\frac {1}{\pi }}=12\sum _{n=0}^{\infty }{\frac {(-1)^{n}(6n)!\,(A+nB)}{(n!)^{3}(3n)!\,C^{n+{\frac {1}{2}}}}}

Каждый дополнительный член частичной суммы дает приблизительно 25 цифр.

Класс № 4 (1993)

Начните с настройки ^[3]

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

Затем

{\frac {\sqrt {-C^{3}}}{\pi }}=\sum _{n=0}^{\infty }{{\frac {(6n)!}{(3n)!(n!)^{3}}}{\frac {A+nB}{C^{3n}}}}

Каждый дополнительный член ряда дает приблизительно 50 цифр.

Итеративные алгоритмы

Квадратичная сходимость (1984)

Начните с настройки ^[4]

{\begin{aligned}a_{0}&={\sqrt {2}}\\b_{0}&=0\\p_{0}&=2+{\sqrt {2}}\end{aligned}}

Затем повторите

{\begin{aligned}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{aligned}}

Тогда p _k квадратично сходится к $π$ ; то есть каждая итерация приблизительно удваивает количество правильных цифр. Алгоритм не является самокорректирующимся; каждая итерация должна выполняться с желаемым количеством правильных цифр для конечного результата $π .$

Кубическая сходимость (1991)

Начните с настройки

{\begin{aligned}a_{0}&={\frac {1}{3}}\\s_{0}&={\frac {{\sqrt {3}}-1}{2}}\end{aligned}}

Затем повторите

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

Тогда k сходится кубически _к ⁠1/ $π$ ⁠ ; то есть каждая итерация примерно утраивает количество правильных цифр.

Квартальная сходимость (1985)

Начните с установки ^[5]

{\begin{aligned}a_{0}&=2\left({\sqrt {2}}-1\right)^{2}\\y_{0}&={\sqrt {2}}-1\end{aligned}}

Затем повторите

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

Тогда k _{сходится} квартично к ⁠1/ $π$ ⁠ ; то есть каждая итерация приблизительно учетверяет количество правильных цифр. Алгоритм не является самокорректирующимся; каждая итерация должна выполняться с желаемым количеством правильных цифр для конечного результата $π .$

Одна итерация этого алгоритма эквивалентна двум итерациям алгоритма Гаусса–Лежандра . Доказательство этих алгоритмов можно найти здесь: ^[6]

Квинтовая сходимость

Начните с настройки

{\begin{aligned}a_{0}&={\frac {1}{2}}\\s_{0}&=5\left({\sqrt {5}}-2\right)={\frac {5}{\phi ^{3}}}\end{aligned}}

где золотое сечение . Затем итерация $\phi ={\tfrac {1+{\sqrt {5}}}{2}}$

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

Тогда _k сходится квинтично к ⁠1/ $π$ ⁠ (то есть каждая итерация приблизительно в пять раз увеличивает количество правильных цифр), и выполняется следующее условие:

0<a_{n}-{\frac {1}{\pi }}<16\cdot 5^{n}\cdot e^{-5^{n}}\pi \,\!

Необычная сходимость

Начните с настройки

{\begin{aligned}a_{0}&={\frac {1}{3}}\\r_{0}&={\frac {{\sqrt {3}}-1}{2}}\\s_{0}&=\left(1-r_{0}^{3}\right)^{\frac {1}{3}}\end{aligned}}

Затем повторите

{\begin{aligned}t_{n+1}&=1+2r_{n}\\u_{n+1}&=\left(9r_{n}\left(1+r_{n}+r_{n}^{2}\right)\right)^{\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\left(1+s_{n}+s_{n}^{2}\right)}{v_{n+1}}}\\a_{n+1}&=w_{n+1}a_{n}+3^{2n-1}\left(1-w_{n+1}\right)\\s_{n+1}&={\frac {\left(1-r_{n}\right)^{3}}{\left(t_{n+1}+2u_{n+1}\right)v_{n+1}}}\\r_{n+1}&=\left(1-s_{n+1}^{3}\right)^{\frac {1}{3}}\end{aligned}}

Тогда k сходится нелинейно _к ⁠1/ $π$ ⁠ ; то есть каждая итерация приблизительно умножает количество правильных цифр на девять. ^[7]

Смотрите также

Ссылки

^ Джонатан М. Борвейн, Питер Б. Борвейн, Pi и AGM – Исследование аналитической теории чисел и вычислительной сложности , Wiley, Нью-Йорк, 1987. Многие из их результатов доступны в: Jorg Arndt, Christoph Haenel, Pi Unleashed, Springer, Берлин, 2001, ISBN 3-540-66572-2
^ Бейли, Дэвид Х. (01.04.2023). «Питер Борвейн: математик-визионер». Notices of the American Mathematical Society . 70 (04): 610– 613. doi :10.1090/noti2675. ISSN 0002-9920.
^ Борвейн, Дж. М.; Борвейн, П. Б. (1993). «Ряд типа Рамануджана класса номер три для 1/π». Журнал вычислительной и прикладной математики . 46 ( 1– 2): 281– 290. doi : 10.1016/0377-0427(93)90302-R .
^ Арндт, Йорг; Хенель, Кристоф (1998). $π$ Развязан . Спрингер-Верлаг. п. 236. ИСБН 3-540-66572-2.
^ Мак, Рональд (2003). Руководство для программистов Java по численным вычислениям . Pearson Educational. стр. 353. ISBN 0-13-046041-9.
^ Милла, Лоренц (2019), Простое доказательство трех рекурсивных $π$ -алгоритмов , arXiv : 1907.04110
↑ Хенрик Вестермарк (4 ноября 2016 г.). «Практическая реализация π-алгоритмов» (PDF) . Проверено 29 ноября 2020 г.

Внешние ссылки

Формулы числа Пи от Wolfram MathWorld

[1] Джонатан М. Борвейн, Питер Б. Борвейн, Pi и AGM – Исследование аналитической теории чисел и вычислительной сложности , Wiley, Нью-Йорк, 1987. Многие из их результатов доступны в: Jorg Arndt, Christoph Haenel, Pi Unleashed, Springer, Берлин, 2001, ISBN 3-540-66572-2

[Bailey_Borwein_2023-2] Бейли, Дэвид Х. (01.04.2023). «Питер Борвейн: математик-визионер». Notices of the American Mathematical Society . 70 (04): 610– 613. doi :10.1090/noti2675. ISSN 0002-9920.

[Borwein_Borwein_1993_pp._281–290-3] Борвейн, Дж. М.; Борвейн, П. Б. (1993). «Ряд типа Рамануджана класса номер три для 1/π». Журнал вычислительной и прикладной математики . 46 ( 1– 2): 281– 290. doi : 10.1016/0377-0427(93)90302-R .

[4] Арндт, Йорг; Хенель, Кристоф (1998). $π$ Развязан . Спрингер-Верлаг. п. 236. ИСБН 3-540-66572-2.

[5] Мак, Рональд (2003). Руководство для программистов Java по численным вычислениям . Pearson Educational. стр. 353. ISBN 0-13-046041-9.

[6] Милла, Лоренц (2019), Простое доказательство трех рекурсивных $π$ -алгоритмов , arXiv : 1907.04110

[7] Хенрик Вестермарк (4 ноября 2016 г.). «Практическая реализация π-алгоритмов» (PDF) . Проверено 29 ноября 2020 г.