Идеи реализации

Программы для вычисления числа π, основанные на постепенном суммировании рядов Лейбница и Эйлера, будут совершенно однотипными. К переменной, изначально равной нулю, в цикле будут прибавляться слагаемые, составляющие бесконечную сумму.

Совершенно аналогично вычисляется произведение Валлиса. Переменная, вначале равная единице, в цикле домножается на очередной множитель.

С произведением Виета дело обстоит несколько сложнее. В случае рядов Лейбница и Эйлера и произведения Валлиса каждое слагаемое или каждый множитель явно выражался через его номер. Очень маловероятно, что получится явно выразить величину v i = 2 2 + 2 + 2 + 2 + 2 через i, количество квадратных корней в знаменателе дроби, используя лишь элементарные (изучаемые в школе) функции.

Ясно, что вся трудность вычисления очередного множителя в произведении Виета приходится на знаменатель, который мы обозначим как d i , так что v i = 2 d i . Отсутствие явной формулы для d i не помешает нам вычислить эту величину алгоритмически: d 0 цикл для k из 1 i d 2 + d конец цикла После выполнения программы переменная d получит значение d i .

Было бы неразумно запускать такой цикл для вычисления каждого из знаменателей. Заметим, что если переменная d равна d i , то после присваивания d 2 + d она будет равняться d i + 1 . Так что можно поместить в цикл команды для вычисления очередного множителя произведения Виета, да и частного произведения: p 2 d 0 цикл до бесконечности вывод p d 2 + d p p 2 d конец цикла Обратите внимание, что начальное значение переменной p в этом алгоритме берётся равным 2 (вместо 1), поскольку мы сразу вычисляем приближённые значения π, а не π 2 .

В отличие от прочих формул, используемых для вычисления π, для бесконечного произведения Виета имеется элементарное доказательство, вполне доступное для понимания читателям, знакомым с основами тригонометрии и планиметрии. Мы не смогли отказать себе в удовольствии привести его здесь. Впрочем, читатель может пропустить доказательство без ущерба для понимания дальнейшего материала.

Для начала умножим обе части произведения на 2: 2 2 2 2 2 + 2 2 2 + 2 + 2 = π . Заметим, что π — площадь круга единичного радиуса, а вписанный в такой круг квадрат имеет площадь 2. Это как раз первый множитель в бесконечном произведении. Мы утверждаем, что площадь правильного восьмиугольника, вписанного в круг, равна 2 2 2 , шестнадцатиугольника — 2 2 2 2 2 + 2 , и вообще, площадь правильного 2 k + 1 -угольника равняется произведению первых k множителей из бесконечного произведения Виета (то есть k-му частному произведению). Если это правда, формула Виета становится очевидной: начиная с квадрата, будем удваивать количество углов во вписанном правильном многоугольнике, постепенно «исчерпывая» площадь круга (рисунок 6.1. ««Исчерпывание» площади круга»).

Рисунок 6.1. «Исчерпывание» площади круга

Площадь правильного 2 k + 1 -угольника можно вычислить. Он состоит из 2 k + 1 одинаковых равнобедренных треугольников с боковой стороной 1 (радиус круга) и углом при вершине 2 π 2 k + 1 = π 2 k . Поэтому площадь равна P k = 2 k sin π 2 k , и, следовательно, P k 1 = 2 k 1 sin π 2 k 1 . Тогда P k P k 1 = 2 k sin π 2 k 2 k 1 sin π 2 k 1 = 2 sin π 2 k sin 2 π 2 k = 1 cos π 2 k (последнее равенство получено по формуле синуса двойного угла). С другой стороны, π = P = P 1 P 2 P 1 P 3 P 2 P 4 P 3 = 2 1 cos π 4 1 cos π 8 1 cos π 16 .

Осталось доказать, что каждый множитель в последнем произведении равен множителю с тем же порядковым номером в произведении Виета, то есть 1 cos π 4 = 2 2 , 1 cos π 8 = 2 2 + 2 , 1 cos π 16 = 2 2 + 2 + 2 , ну и так далее. Иными словами, нужно доказать при любом k равенство d k = 2 cos π 2 k + 1 , где, как и раньше, d k = 2 + 2 + 2 + 2 + 2 содержит k знаков квадратного корня.

Что ж, докажем утверждение по индукции. Оно очевидно при k = 1 , так что теперь следует доказать индуктивный переход. Как уже было установлено выше, d k = 2 + d k 1 . Следовательно, должно выполняться 2 cos π 2 k + 1 = 2 + 2 cos π 2 k . Но это прямо вытекает из формулы косинуса половинного угла cos α 2 = 1 + cos α 2 , или 2 cos α 2 = 2 + 2 cos α .

Мы обсудим другой приближённый метод; он также связан с постепенным вычислением, при котором точность растёт. Правда, этот способ не даёт гарантированной точности вычисления, он сравнительно медленный, однако имеет множество достоинств, которые особенно проявляются при решении других задач. Этот способ предполагает приближённое вычисление площади некоторой фигуры или объёма некоторого тела. В прикладной математике часто бывает нужно вычислять объёмы тел, в том числе многомерных. Данный способ хорош тем, что в отличие от других работает одинаково быстро независимо от размерности многомерного тела. Способ годится и для вычисления многократных интегралов.

Для вычисления π будем искать площадь единичного круга, или, что удобнее, его четвертинки. Площадь такой четвертинки равна π 4 . Возьмём на координатной плоскости x y четверть круга единичного радиуса, заключённую в единичный квадрат. Разбросаем равномерно по квадрату много точек. Интуитивно ясно, что доля точек, попавших в четверть круга, приблизительно такая же, что и доля площади четверти круга в площади квадрата, то есть π 4 . И чем больше точек мы разбросаем, тем точнее будет результат. Приложение на рисунке 6.2. «Вычисление числа π методом Монте-Карло» наглядно показывает этот процесс.

Рисунок 6.2. Вычисление числа π методом Монте-Карло

Осталось придать строгий смысл понятию «последовательность точек, равномерно распределённая в квадрате».

Пусть M — некоторое измеримое (то есть имеющее площадь) множество на плоскости. Некоторые множества площади не имеют, но, чтобы проиллюстрировать эту мысль, придётся обратиться к высшей математике, к теории меры, а это не входит в наши планы. Рассмотрим бесконечную последовательность точек p 1 , p 2 , p 3 , M и некоторое измеримое подмножество I M . Обозначим n I количество элементов множества p i i = 1 , , n ; p i I . Последовательность называется равномерно распределённой на множестве M, если для любого измеримого подмножества I величина n I n неограниченно приближается к I M , где I и M  — площади множеств I и M.

Данное определение можно распространить на случай, когда M — множество на прямой. Только надо всюду в определении заменить слово «площадь» на слово «длина». Точно так же для множеств в пространстве вместо площади можно рассматривать объём. Для длин, площадей и объёмов в математике имеется обобщающий термин «мера».

Можно доказать, что в качестве последовательности точек, равномерно распределённой в единичном квадрате, годится такая: i α , i β , i = 1 , 2 , . Здесь z  — дробная часть числа z, а α и β — иррациональные, кроме того, несоизмеримые числа (то есть такие, отношение которых иррационально). Эти условия, наложенные на числа α и β, равносильны следующему: равенство α k + β l = 0 не достигается ни при каких k , l . В качестве таких чисел α и β можно взять, к примеру, 2 и 3 .

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

Ещё один экспериментальный метод приближённого вычисления числа π называется методом иглы Бюффона. В сущности, это тот же самый метод Монте-Карло. Потребуется иголка и достаточно большой лист бумаги.

Бумага расчерчивается параллельными прямыми, отстоящими друг от друга на расстояние в одну иголку. Бумажный лист кладётся на пол, а экспериментатор бросает на него иглу, никуда специально не целясь (лучше это делать с достаточно большой высоты, чтобы никто не мог упрекнуть в подтасовке). После падения иглы экспериментатор смотрит, пересекла ли игла какую-нибудь прямую, и, если пересекла, этот факт учитывается. Также подсчитывается общее количество бросаний.

Оказывается, что при большом числе испытаний доля попаданий (то есть ситуаций, когда игла пересекает прямую) среди всех бросаний иглы неограниченно приближается к числу 2 π .

Мы предлагаем доказательство этого утверждения. Правда, оно использует тригонометрические функции и интеграл. Пусть наши юные читатели, ещё не знакомые с этими сложными вещами, не унывают. Другое, удивительно красивое, и при этом элементарное объяснение феномена иглы Бюффона, содержится в замечательной книге [20], которую (вместе с первой и второй частями) мы очень рекомендуем всем, кто интересуется физикой и математикой. Похожее рассуждение приведено в книге [22].

Проведём через центр брошенной иглы числовую ось x перпендикулярно начерченным прямым таким образом, чтобы две прямые, окружающие центр иголки, пересекли её в точках 0 и 1 (длины измеряются в иголках). Пусть центр иглы имеет координату x, а сама игла образует с координатной прямой угол θ (рисунок 6.3. «Игла Бюффона»).

Найдём значения x, при которых для заданного угла поворота θ иголка пересекает прямую. При 0 x 1 2 игла может пересечь лишь прямую, соответствующую значению x = 0 , и то не обязательно. Из прямоугольного треугольника с катетом x и гипотенузой 1 2 получаем условие пересечения x 1 2 cos θ . Если центр иглы лежит ближе к прямой x = 1 , совершенно аналогично получим условие x 1 1 2 cos θ .

Рисунок 6.3. Игла Бюффона

Мы изобразили на рисунке 6.4. «Игла Бюффона — области пересечения» зелёным цветом область, заданную обоими неравенствами. Она ограничена прямыми x = 0 и x = 1 и двумя дугами синусоид x = 1 2 cos θ и x = 1 1 2 cos θ . Видно, что при малых углах θ (то есть когда игла падает почти перпендикулярно прямым) пересечение происходит почти наверняка. Наоборот, когда θ близко к ± π 2 , пересечение возможно лишь при значениях x, близких к 0 или 1.

Рисунок 6.4. Игла Бюффона — области пересечения

Область возможных значений величин x и θ представляет собой прямоугольник размером 1 × π и площадью π. Если доказать, что площадь зелёной фигуры равна 2, то наше утверждение будет доказано. Действительно, бросание иголки равносильно бросанию точки в прямоугольник таким образом, что координата x равномерно распределена на отрезке 0 1 , а угол θ равномерно распределён на отрезке π 2 π 2 . Всё это означает, что воображаемая точка при многократных бросаниях иглы равномерно распределена в прямоугольнике. Теперь найдём площадь зелёной фигуры. Площадь одной половинки даётся интегралом 1 2 π 2 π 2 cos θ θ = 1 2 sin π 2 sin π 2 = 1 . Площадь всей зелёной фигуры, таким образом, равна 2, а отношение её площади к площади прямоугольника составляет, как и было обещано, 2 π .

Информатика-54© А. Н. Швец