Алгоритм Гаусса-Лежандра является алгоритм для вычисления цифр П . Он примечателен тем, что быстро сходится: всего 25 итераций дают 45 миллионов правильных цифр π . Однако недостатком является то, что он интенсивно использует память компьютера, и поэтому иногда вместо него используются формулы, подобные Мачину .
Метод основан на индивидуальной работе Карла Фридриха Гаусса (1777–1855) и Адриена-Мари Лежандра (1752–1833) в сочетании с современными алгоритмами умножения и вычисления квадратных корней . Он неоднократно заменяет два числа их средним арифметическим и геометрическим , чтобы аппроксимировать их среднее арифметико-геометрическое .
Представленная ниже версия также известна как алгоритм Гаусса – Эйлера , Брента – Саламина (или Саламина – Брента ) ; [1] он был независимо открыт в 1975 году Ричардом Брентом и Юджином Саламином . Он использовался для вычисления первых 206 158 430000 цифр числа π с 18 по 20 сентября 1999 г., а результаты были проверены с помощью алгоритма Борвейна .
Алгоритм
1. Установка начального значения:
2. Повторяйте следующие инструкции до тех пор, пока не изменится а также находится в пределах желаемой точности:
3. Тогда π аппроксимируется как:
Первые три итерации дают (приближения до первой неправильной цифры включительно):
Алгоритм имеет квадратичную сходимость , что по сути означает, что количество правильных цифр удваивается с каждой итерацией алгоритма.
Математический фон
Пределы среднего арифметико-геометрического
Арифметико-геометрическое среднее из двух чисел, A 0 и Ь 0 , определяется путем вычисления предела последовательностей
которые оба сходятся к одному пределу.
Если а также тогда предел где - полный эллиптический интеграл первого рода
Если , , тогда
где - полный эллиптический интеграл второго рода :
- а также
Гаусс знал об обоих этих результатах. [2] [3] [4]
Личность Лежандра
Для а также такой, что Лежандр доказал идентичность:
- [2]
- Эквивалентно,
Элементарное доказательство с интегральным исчислением
Алгоритм Гаусса-Лежандра может быть доказан без эллиптических модульных функций. Это делается здесь [5] и здесь [6] с использованием только интегрального исчисления.
Смотрите также
Рекомендации
- ^ Брент, Ричард , Старые и новые алгоритмы для числа Пи , Письма в редакцию, Уведомления о AMS 60 (1), стр. 7
- ^ a b Брент, Ричард (1975), Трауб, Дж. Ф. (ред.), «Методы определения нуля с высокой точностью и сложность вычисления элементарных функций» , Analytic Computational Complexity , New York: Academic Press, стр. 151–176 , получено 8 сентября 2007 г.
- ^ Саламин, Евгений , Вычисление числа Пи , Чарльз Старк Дрейпер Laboratory памятка МКС 74-19, 30 января 1974, Кембридж, Массачусетс
- ^ Саламин, Евгений (1976), "Вычисление пи Использование арифметико-геометрического среднего", Математика вычислений , 30 (135), стр 565-570,. DOI : 10,2307 / 2005327 , ISSN 0025-5718
- ^ Лорд, Ник (1992), "Последние расчеты я: Гаусс-Саламин Алгоритм", Математическая газета , 76 (476): 231-242, DOI : 10,2307 / 3619132 , JSTOR 3619132
- ^ Милла, Лоренц (2019), Простое доказательство трех рекурсивных π-алгоритмов , arXiv : 1907.04110