Алгоритм Гаусса – Лежандра - Gauss–Legendre algorithm

В Алгоритм Гаусса – Лежандра является алгоритм вычислить цифры π. Он примечателен тем, что быстро сходится: всего 25 итераций дают 45 миллионов правильных цифрπ. Однако недостатком является то, что это память компьютера -интенсивный и поэтому иногда Машинные формулы вместо этого используются.

Метод основан на индивидуальной работе Карл Фридрих Гаусс (1777–1855) и Адриан-Мари Лежандр (1752–1833) в сочетании с современными алгоритмами умножения и квадратные корни. Он неоднократно заменяет два числа их арифметика и среднее геометрическое, чтобы приблизить их среднее арифметико-геометрическое.

Представленная ниже версия также известна как Гаусс – Эйлер, Брент – Саламин (или же Саламин – Брент) алгоритм;^[1] он был независимо открыт в 1975 г. Ричард Брент и Евгений Саламин. Он использовался для вычисления первых 206 158 430000 десятичных цифр π 18-20 сентября 1999 г., и результаты были проверены Алгоритм Борвейна.

Алгоритм

1. Установка начального значения:

${\displaystyle a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad t_{0}={\frac {1}{4}}\qquad p_{0}=1.}$

2. Повторяйте следующие инструкции, пока не изменится ${\displaystyle a_{n}}$ и ${\displaystyle b_{n}}$ находится в пределах желаемой точности:

${\displaystyle {\begin{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}},\\\\b_{n+1}&={\sqrt {a_{n}b_{n}}},\\\\t_{n+1}&=t_{n}-p_{n}(a_{n}-a_{n+1})^{2},\\\\p_{n+1}&=2p_{n}.\\\end{aligned}}}$

3. π затем аппроксимируется как:

${\displaystyle \pi \approx {\frac {(a_{n+1}+b_{n+1})^{2}}{4t_{n+1}}}.}$

Первые три итерации дают (приближения до первой неправильной цифры включительно):

${\displaystyle 3.140\dots }$

${\displaystyle 3.14159264\dots }$

${\displaystyle 3.1415926535897932382\dots }$

Алгоритм имеет квадратичная сходимость, что по сути означает, что количество правильных цифр удваивается с каждым итерация алгоритма.

Математический фон

Пределы среднего арифметико-геометрического

В среднее арифметико-геометрическое из двух чисел,₀ и б₀, находится путем вычисления предела последовательностей

${\displaystyle {\begin{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}},\\[6pt]b_{n+1}&={\sqrt {a_{n}b_{n}}},\end{aligned}}}$

которые оба сходятся к одному пределу.
Если ${\displaystyle a_{0}=1}$ и ${\displaystyle b_{0}=\cos \varphi }$ тогда предел ${\textstyle {\pi \over 2K(\sin \varphi )}}$ куда ${\displaystyle K(k)}$ это полный эллиптический интеграл первого рода

${\displaystyle K(k)=\int _{0}^{\pi /2}{\frac {d\theta }{\sqrt {1-k^{2}\sin ^{2}\theta }}}.}$

Если ${\displaystyle c_{0}=\sin \varphi }$, ${\displaystyle c_{i+1}=a_{i}-a_{i+1}}$, тогда

${\displaystyle \sum _{i=0}^{\infty }2^{i-1}c_{i}^{2}=1-{E(\sin \varphi ) \over K(\sin \varphi )}}$

куда ${\displaystyle E(k)}$ это полный эллиптический интеграл второго рода:

${\displaystyle E(k)=\int _{0}^{\pi /2}{\sqrt {1-k^{2}\sin ^{2}\theta }}\;d\theta }$ и ${\displaystyle K(k)=\int _{0}^{\pi /2}{\frac {d\theta }{\sqrt {1-k^{2}\sin ^{2}\theta }}}.}$

Гаусс знал об обоих этих результатах.^[2][3][4]

Личность Лежандра

За ${\displaystyle \varphi }$ и ${\displaystyle \theta }$ такой, что ${\textstyle \varphi +\theta ={1 \over 2}\pi }$ Лежандр доказал идентичность:

${\displaystyle K(\sin \varphi )E(\sin \theta )+K(\sin \theta )E(\sin \varphi )-K(\sin \varphi )K(\sin \theta )={1 \over 2}\pi .}$^[2]

Эквивалентно,

${\displaystyle \forall \varphi :K(\sin \varphi )[E(\cos \varphi )-K(\cos \varphi )]+K(\cos \varphi )E(\sin \varphi )={\frac {\pi }{2}}}$

Элементарное доказательство с интегральным исчислением

Алгоритм Гаусса-Лежандра может быть доказан без эллиптических модульных функций. Это сделано здесь^[5] и тут^[6] используя только интегральное исчисление.

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

• Численные приближения π

Рекомендации

1. Брент, Ричард, Старый и новый алгоритмы для пи, Письма в редакцию, Извещения AMS 60 (1), стр. 7
2. Брент, Ричард (1975), Трауб, Дж. Ф. (ред.), «Методы определения нуля с высокой точностью и сложность вычисления элементарных функций», Аналитическая вычислительная сложность, Нью-Йорк: Academic Press, стр. 151–176., получено 8 сентября 2007
3. Саламин, Евгений, Вычисление числа пи, Меморандум 74–19 лаборатории Чарльза Старка Дрейпера на МКС, 30 января 1974 г., Кембридж, Массачусетс.
4. Саламин, Евгений (1976), «Вычисление числа пи с использованием среднего арифметико-геометрического», Математика вычислений, 30 (135), стр. 565–570, Дои:10.2307/2005327, ISSN  0025-5718
5. Лорд, Ник (1992), «Недавние вычисления π: алгоритм Гаусса-Саламина», Математический вестник, 76 (476): 231–242, Дои:10.2307/3619132, JSTOR  3619132
6. Милла, Лоренц (2019), Простое доказательство трех рекурсивных π-алгоритмов, arXiv:1907.04110