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

Алгоритм Гаусса -Лежандра — это алгоритм вычисления цифр числа π . Он примечателен своей быстрой сходимостью: всего за 25 итераций получается 45 миллионов правильных цифр числа π . Однако он имеет некоторые недостатки (например, требует большого объема памяти компьютера ) и поэтому во всех рекордных расчетах на протяжении многих лет использовались другие методы, почти всегда алгоритм Чудновского . Подробности см. в «Хронологии расчета π» .

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

Представленная ниже версия также известна как Гаусса–Эйлера , Брента–Саламина (или Саламина–Брента ) алгоритм ; он был независимо открыт в 1975 году Ричардом Брентом и Юджином Саламином . Он использовался для вычисления первых 206 158 430 000 десятичных цифр числа π с 18 по 20 сентября 1999 года, а результаты были проверены с помощью алгоритма Борвейна .

Алгоритм

1. Начальная установка значения: $$a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad t_{0}={\frac {1}{4}}\qquad p_{0}=1.$$
2. Повторяйте следующие инструкции до тех пор, пока разница $a_{n}$ и $b_{n}$ находится в пределах желаемой точности: $${\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. Тогда π аппроксимируется как: $$\pi \approx {\frac {(a_{n+1}+b_{n+1})^{2}}{4t_{n+1}}}.$$

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

$3.140\dots$

$3.14159264\dots$

$3.1415926535897932382\dots$

$3.141592653589793238462643\dots$

$3.14159265358979323846264338327\dots$

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

Математическая основа

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

Среднее арифметико -геометрическое двух чисел a ₀ и b ₀ находится путем вычисления предела последовательностей

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

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

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

Если $c_{0}=\sin \varphi$, $c_{i+1}=a_{i}-a_{i+1}$, затем

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

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

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

Гаусс знал об этих двух результатах.

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

Лежандр доказал следующее тождество:

$$K(\cos \theta )E(\sin \theta )+K(\sin \theta )E(\cos \theta )-K(\cos \theta )K(\sin \theta )={\pi \over 2},$$

для всех $\theta$.

Элементарное доказательство с помощью интегрального исчисления

Можно доказать, что алгоритм Гаусса-Лежандра дает результаты, сходящиеся к π, используя только интегральное исчисление. Это сделано здесь и здесь.

См. также

• Численные аппроксимации π