«Способы вычисления числа ПИ.»

Сообщение №2084 от - 20 декабря 2001 г. 13:31
Тема: «Способы вычисления числа ПИ.»

Члены математических последовательностей можно складывать и перемножать, иногда получая при этом ряды или бесконечные произведения, сходящиеся к p (деленному на константу) или к 1/p. Первые две последовательности, открытые математиками Джоном Валлисом и Джеймсом Грегори, широко известны, однако для вычислительных целей практически бесполезны. Для нахождения ста знаков p не хватило бы и ста лет работы суперкомпьютера, запрограммированного на сложение или умножение членов любой из этих последовательностей. Формула, открытая Джоном Мэчином, сделала вычисление p выполнимым, так как из анализа известен способ представлять арктангенс числа х в виде ряда, который сходится к значению арктангенса тем быстрее, чем меньше x. Все известные вычисления p с начала XVIII в. и до начала 70-х годов нашего века опирались на варианты формулы Мэчина. Сумма последовательности Рамануджана сходится к истинному значению 1/p гораздо быстрее: каждый очередной член последовательности добавляет, грубо говоря, восемь новых правильных цифр. Самая нижняя последовательность добавляет около 25 цифр с каждым новым членом. Первый член (соответствующий n = 0) дает число, совпадающее с p в 24 десятичных знаках.

Величайший математик древности Архимед из Сиракуз вычислил и приближенное значение p, причем на основе математических принципов, а не прямых измерений длины окружности, площади круга и диаметра. Архимед вписывал в окружность и описывал около нее правильные многоугольники (т. е. многоугольники со сторонами одинаковой длины). Диаметр окружности принимался за единицу, а периметры описанного и вписанного многоугольников рассматривались как приближения соответственно сверху и снизу к длине окружности, которая в данном случае численно совпадала с p.

Этот метод приближения p не был новшеством: еще раньше вписывать многоугольники с возрастающим числом сторон предложил Антифон, а его современник Брисон из Гераклеи дополнительно ввел описанные многоугольники. Новшеством был выполненный Архимедом правильный расчет результата удвоения числа сторон как вписанного, так и описанного многоугольников. Тем самым он разработал процедуру, повторение которой достаточное число раз в принципе позволяет вычислить p с любым количеством знаков. (Следует заметить, что периметр правильного многоугольника легко вычисляется с помощью простых  тригонометрических функций: синуса, косинуса и тангенса, однако во времена Архимеда, т. е. в III в. до н. э., эти функции еще не были полностью изучены и вычисление периметров было далеко не таким легким делом, как может сейчас показаться.)

Архимед начал с вписанного и описанного шестиугольников и получил неравенство 3 < p < 2·31/2. Четырежды удвоив число сторон (т. е. доведя его до 96), он сузил интервал для p: 3+10/71 < p < 3+1/7 и получил приближенное значение p= 3,14. Есть некоторые основания предполагать, что дошедший до нас текст трактата "Измерение круга" представляет собой часть более обширного труда, в котором Архимед объясняет, как, начав с десятиугольников и применив шесть раз операцию удвоения, он получил приближение с пятью знаками: p = 3,1416. Сам по себе метод Архимеда прост, но при отсутствии готовых таблиц тригонометрических функций требует извлечения корней; выполнение этой операции вручную занимает довольно много времени. Кроме того, приближения сходятся к p очень медленно: с каждой итерацией погрешность уменьшается лишь вчетверо. Тем не менее до середины XVII в. все попытки европейских ученых вычислить p так или иначе опирались на этот метод. Голландский математик XVI в. Лудольф ван Цейлен посвятил вычислению p большую часть своей научной деятельности. К концу жизни он нашел приближение с 32 десятичными знаками, вычислив периметры вписанного и описанного многоугольников с 262 (т. е. порядка 1018) сторонами. Говорят, полученное им значение p, которое в некоторых европейских странах называют в его честь числом Лудольфа, высечено на его надгробном камне.

Развитие анализа в основном трудами Исаака Ньютона и Готфрида Вильгельма Лейбница позволило намного ускорить вычисление приближенных значений p. В анализе существуют эффективные методы нахождения для функции ее производной (скорости изменения значения функции при изменении переменных) и интеграла (суммы значений функции на некоторой области изменения переменных). С помощью этих методов можно показать, что обратные тригонометрические функции представляются в виде интегралов от квадратичных функций, связанных с окружностью. (Обратная тригонометрическая функция задает угол, которому отвечает данное значение самой тригонометрической функции. Так, значение функции, обратной тангенсу, т. е. арктангенса, от 1 равно 45 градусам, или p/4 радианам.) Связь между тригонометрическими функциями и алгебраическими выражениями станет понятней, если рассмотреть окружность единичного радиуса с центром в начале координат на декартовой плоскости х-у. Уравнение этой окружности (ее площадь численно совпадает с p) имеет вид х2 + у2 = 1; оно получается по теореме Пифагора для прямоугольного треугольника с гипотенузой 1. Синус и косинус угла между положительной полуосью х и радиусом, проведенным в любую точку окружности, равны соответственно координатам у и х этой точки, а его тангенс равен у /х.

Однако для вычисления p гораздо важнее тот факт, что обратную тригонометрическую функцию можно разложить в ряд, члены которого выражаются через ее производные. Сам Ньютон нашел 15 знаков p, суммируя несколько первых членов ряда для арксинуса. Позднее он писал одному из коллег: "Мне стыдно сказать вам, до скольких знаков я выполнил эти вычисления, не занимаясь больше ничем".

В 1674 г. Лейбниц вывел формулу 1 - 1/3 + 1/5 - 1/7 + ... = p/4 (арктангенс единицы). (Общий ряд для арктангенса был открыт в 1671 г. шотландским математиком Джеймсом Грегори, хотя аналогичные выражения, по-видимому, были получены в Индии на несколько столетий раньше.) Погрешность этого приближения, определяемая как разность между суммой n членов ряда и точным значением p/4, приблизительно равна (n + 1)-му члену. Так как знаменатель каждого следующего слагаемого возрастает лишь на два, то, чтобы получить приближение с точностью до двух знаков, приходится суммировать около 50 членов, с точностью до трех знаков - около 500 и т. д. Таким образом, этот ряд практически непригоден для нахождения более чем нескольких первых знаков p.

Спасла положение формула Джона Мэчина: p/4=4arctg(l/5) - arctg(l/239). Поскольку ряд для арктангенса при заданном значении переменной сходится тем быстрее, чем меньше это значение, благодаря этой формуле вычисления сильно упростились. Пользуясь своей формулой и рядом для арктангенса, Мэчин в 1706 г. вычислил 100 знаков p. Его метод оказался столь мощным, что с начала XVIII в. и до самого недавнего времени все вычисления p с большим числом знаков были выполнены с помощью тех или иных вариантов этого метода.

Из вычислений, проведенных в XIX в., два следует упомянуть особо. В 1844 г. Иоганн Дазе нашел 205 знаков p в течение нескольких месяцев, вычисляя значения трех арктангенсов и пользуясь формулой, аналогичной формуле Мэчина. Дазе был чудо-вычислителем: он мог примерно за 8 часов перемножать в уме стозначные числа. (Его, наверное, можно считать предтечей современного суперкомпьютера, по крайней мере по объему памяти.) В 1853 г. Уильям Шенкс обошел Дазе, опубликовав полученное им значение p с 607 знаками, хотя начиная с 528-го все остальные оказались неверными. Шенкс потратил на свой труд многие годы - это было рутинное, хотя и трудоемкое применение формулы Мэчина. Своеобразным рекордом стало и то, что ошибка Шенкса была обнаружена только через 92 года при сравнении его значений с приближением p до 530 знаков, вычисленным Д.Ф. Фергюсоном с помощью механического калькулятора.

С появлением цифровых вычислительных машин попытки найти еще больше десятичных знаков p возобновились, так как машина идеально приспособлена к долгому и упорному "перемалыванию" чисел. В июне 1949 г. Джон фон Нейман и его сотрудники применили один из первых цифровых компьютеров ENIAC. Машина выдала 2037 знаков за 70 часов. В 1957 г. Г.Э. Фелтон пытался вычислить 10 000 знаков p, но из-за ошибки компьютера только первые 7480 знаков оказались правильными. Рубеж в 10 000 знаков был достигнут годом позже Ф. Женюи с помощью компьютера IBM 704. В 1961 г. Дэниел Шенкс [по утверждению М. Гарднера, не имеющий отношения к Уильяму Шенксу. - Перев.] и Джон У. Ренч-младший вычислили 100 000 знаков p с помощью компьютера IBM 7090 менее чем за 9 часов. Отметка в миллион знаков была пройдена в 1973 г. Жаном Гийу и М. Буйе. Это заняло чуть меньше одного дня работы компьютера CDC 7600. (Вычисления Шенкса - Ренча и Гийу - Буйе были проделаны дважды при помощи двух разных выражений для p через арктангенсы. С учетом всех ошибок, допущенных в подобных вычислениях как человеком, так и машиной, только после такой проверки современные "охотники за знаками" считают рекорд официально установленным.)

Главная причина, по которой стало возможным все более точное вычисление p, состояла в увеличении быстродействия компьютеров. Однако вскоре выявились серьезные препятствия к дальнейшему росту точности. При традиционных способах выполнения на компьютере арифметических действий, если бы мы захотели удвоить число знаков, нам пришлось бы увеличить время вычисления по крайней мере вчетверо. Таким образом, даже при стократном увеличении быстродействия программе Гийу и Буйе для получения миллиардного знака p понадобилось бы четверть века машинного времени. В 70-е годы казалось, что такое вычисление практически невыполнимо. Однако теперь эта задача осуществима, причем не только благодаря появлению "скоростных" компьютеров, но и благодаря применению новых методов умножения чисел. Решающим было и третье нововведение - итерационные алгоритмы, быстро сходящиеся к p. (Итерационный алгоритм можно реализовать в виде программы, которая повторно выполняет одни и те же арифметические действия, используя выход одного цикла в качестве входа для следующего.) Эти алгоритмы (некоторые из них построены нами) во многих отношениях предвосхищены Рамануджаном, хотя он и не знал ничего о программировании. Компьютеры не только позволили применить результаты Рамануджана, но и помогли разгадать их. Совершенное программное обеспечение, предусматривающее сложные алгебраические манипуляции, позволило уверенно двигаться по дороге, по которой в одиночку, лишенный помощи пробирался Рамануджан 75 лет назад.

[ В Мире Науки, Апрель 1988]

--------------------------------
Re: Способы вычисления числа ПИ

№2082 от Б.Б. , 19 декабря 2001 г. 23:57:
В ответ на №2079: Re: Способы вычисления числа ПИ от Alexander , 19 декабря 2001 г.:

http://www.nas.nasa.gov/Pubs/NASnews/97/05/math.html


Отклики на это сообщение:

Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100