Способ экспериментального вычисления числа
Программы для вычисления числа π , основанные на постепенном суммировании рядов Лейбница и Эйлера, будут совершенно однотипными. К переменной, изначально равной нулю, в цикле будут прибавляться слагаемые, составляющие бесконечную сумму.
Совершенно аналогично вычисляется произведение Валлиса. Переменная, вначале равная единице, в цикле домножается на очередной множитель.
С произведением Виета дело обстоит несколько сложнее. В случае рядов Лейбница и Эйлера и произведения Валлиса каждое слагаемое или каждый множитель явно выражался через его номер. Очень маловероятно, что получится явно выразить величину 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. ««Исчерпывание» площади круга»).
Площадь правильного 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. «Вычисление числа π методом Монте-Карло» наглядно показывает этот процесс.
Осталось придать строгий смысл понятию «последовательность точек, равномерно распределённая в квадрате».
Данное определение можно распространить на случай, когда 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.4. «Игла Бюффона — области пересечения» зелёным цветом область, заданную обоими неравенствами. Она ограничена прямыми x = 0 и x = 1 и двумя дугами синусоид x = 1 2 cos θ и x = 1 − 1 2 cos θ . Видно, что при малых углах θ (то есть когда игла падает почти перпендикулярно прямым) пересечение происходит почти наверняка. Наоборот, когда θ близко к ± π 2 , пересечение возможно лишь при значениях x , близких к 0 или 1 .
Область возможных значений величин x и θ представляет собой прямоугольник размером 1 × π и площадью π . Если доказать, что площадь зелёной фигуры равна 2 , то наше утверждение будет доказано. Действительно, бросание иголки равносильно бросанию точки в прямоугольник таким образом, что координата x равномерно распределена на отрезке 0 1 , а угол θ равномерно распределён на отрезке − π 2 π 2 . Всё это означает, что воображаемая точка при многократных бросаниях иглы равномерно распределена в прямоугольнике. Теперь найдём площадь зелёной фигуры. Площадь одной половинки даётся интегралом 1 2 ∫ − π 2 π 2 cos θ ⅆ θ = 1 2 sin π 2 − sin − π 2 = 1 . Площадь всей зелёной фигуры, таким образом, равна 2 , а отношение её площади к площади прямоугольника составляет, как и было обещано, 2 π .
Вычисление по формуле Броункера
Алгоритм, вычисляющий π по формуле Броункера, требует отдельного основательного разговора. Мы посвятили непрерывным дробям отдельную главу 22. «Непрерывные дроби».
Источник
Реализация вычисления числа Пи с использованием датчика случайных чисел
Используя генератор случайных чисел, придумайте и реализуйте способ экспериментального вычисления числа pi.
Тут только методом Монте Карло можно?
С использованием датчика случайных чисел сформировать два массива X и Y
С помощью датчика случайных чисел сформировать два массива X и Y размерностью 100 и 200 чисел в.
Сформировать одномерный массив с использованием датчика случайных чисел
Сформировать одномерный массив, содержащий 15 элементов, с помощью датчика случайных чисел.
Сформировать одномерный массив из n элементов с использованием датчика случайных чисел
Удаление Все элементы больше среднего арифметическ ого элементов массива Добавление К элементов в.
Нахождение номеров максимального элемента двумерного массива, вводимого с использованием датчика случайных чисел
Нахождения номеров максимального элемента двумерного массива, вводимого с использованием датчика.
Записать в файл N натуральных чисел: a1, a2. an (числа получить с помощью датчика случайных чисел)
Помогите с лабами) 1) Записать в файл N натуральных чисел: a1, a2. an (числа получить с помощью.
С помощью датчика случайных чисел получить натуральные числа m и n, не превосходящие 20
С помощью датчика случайных чисел получить натуральные числа m и n, не превосходящие 20, n целых.
В одномерный массив A размерности N при датчика случайных чисел вводятся действительные числа
В одномерный массив A размерности N при помощи датчика случайных чисел вводятся действительные.
С помощью датчика случайных чисел получить 30 целых чисел, лежащих в диапазоне от 0 до 5
Здраствуйте! С помощью датчика случайных чисел получить 30 целых чисел, лежащих в диапазоне от 0 до.
Задать массив вещественных чисел с помощью датчика случайных чисел.
Задать массив вещественных чисел с помощью датчика случайных чисел. Упорядочить массив по.
записать в файл с помощью датчика случайных чисел N натуральных чисел
записать в файл с помощью датчика случайных чисел N натуральных чисел а1.а2. аn.Сформировать новый.
Источник
Вычисление числа Пи методом Монте-Карло
Существует много способов вычисления числа Пи. Самым простым и понятным является численный метод Монте-Карло, суть которого сводится к простейшему перебору точек на площади. Суть расчета заключается в том, что мы берем квадрат со стороной a = 2 R, вписываем в него круг радиусом R. И начинаем наугад ставить точки внутри квадрата. Геометрически, вероятность P1 того, чтот точка попадет в круг, равна отношению площадей круга и квадрата:
P1=Sкруг / Sквадрата = πR 2 / a 2 = πR 2 / (2 R ) 2 = πR 2 / (2 R) 2 = π / 4 (1)
Выглядит это так:
Вероятность попадания точки в круг можно также посчитать после численного эксперимента ещё проще: посчитать количество точек, попавших в круг, и поделить их на общее количество поставленных точек:
P2=Nпопавших в круг / Nточек; (2)
Так, при большом количестве точек в численном эксперименте вероятности должны вести себя cледующим образом:
lim(Nточек→∞)(P2-P1)=0; (3)
Следовательно:
π / 4 = Nпопавших в круг / Nточек; (4)
π =4 Nпопавших в круг / Nточек; (5)
НО! При моделировании мы применяем псевдослучайные числа, которые не являются случайным процессом.
Поэтому, выражение (5), к сожалению, строго не выполняется. Логичны вопросы, каковы оптимальные размеры квадрата и как много нужно применить точек?
Чтобы это выяснить, я написал такую программу:
Программа выводит значения числа Пи в зависимости от радиуса и количества точек. Единственное, что остается читателю, это скомпилировать её самостоятельно и запустить с параметрами, которые желает он.
Приведу лишь одну таблицу с полученными значениями:
| Радиус | Nточек | Pi |
| 102400 | 204800 | 3,145664 |
| 102400 | 409600 | 3,137188 |
| 102400 | 819200 | 3,139326 |
| 102400 | 1638400 | 3,144478 |
| 102400 | 3276800 | 3,139875 |
| 102400 | 6553600 | 3,142611 |
| 102400 | 13107200 | 3,140872 |
| 102400 | 26214400 | 3,141644 |
| 102400 | 52428800 | 3,141217 |
| 102400 | 1,05E+08 | 3,141324 |
| 102400 | 2,1E+08 | 3,141615 |
| 102400 | 4,19E+08 | 3,141665 |
| 102400 | 8,39E+08 | 3,141724 |
| 102400 | 1,68E+09 | 3,141682 |
Если что, значение числа Пи можно посмотреть с точностью до определенного знака здесь.
Источник картинки — википедия.
Источник
