1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 32
Текст из файла (страница 32)
Вычисление интегралов методом Монте-Карло195числителе выписанного выражения. Кроме того, Πi (xi ) > 0, откудаможно заключить, что ci > 0.Напомним, что сумма весов формул Гаусса равна длине интервала интегрирования (как и для всех интерполяционных квадратурныхформул, см. §2.12г). Как следствие, величина (2.147) при этом ограничена, и квадратурный процесс по формулам Гаусса всегда сходится.Завершая тему, можно отметить, что ситуация со сходимостью квадратур оказывается в целом более благоприятной, чем для интерполяционных процессов.2.16Вычисление интеграловметодом Монте-КарлоВ методе Монте-Карло, называемом также методом статистического моделирования, искомое решение задачи представляется в видекакой-либо характеристики специально построенного случайного процесса.
Затем этот процесс моделируется, с помощью ЭВМ или какимито другими средствами, и по его реализации мы вычисляем нужнуюхарактеристику, т. е. решение задачи. Наиболее часто решение задачпредставляется так называемым математическим ожиданием (среднимзначением) специально подобранной случайной величины.В качестве примера рассмотрим задачу вычисления определённогоинтегралаZ bf (x) dx(2.149)aот непрерывной функции f (x). Согласно известной из интегральногоисчисления теореме о среднем (см., к примеру, [37])Z bf (x) dx = (b − a) f (c)aдля некоторой точки c ∈ [a, b]. Смысл «средней точки» c можно понятьглубже с помощью следующего рассуждения. Пусть интервал интегрирования [a, b] разбит на N равных подинтервалов. По определению интеграла Римана, если xi — точки из этих подинтервалов, тоZ bNNXb−a1 Xf (xi )f (xi ) = (b − a) ·f (x) dx ≈NN i=1ai=11962.
Численные методы анализадля достаточно больших N . Сумма в правой части — это произведениеширины интервала интегрирования (b − a) на среднее арифметическоезначений подинтегральной функции f в точках xi , i = 1, 2, . . . , N . Таким образом, интеграл от f (x) по [a, b] есть не что иное, как «среднеезначение» функции f (x) на интервале [a, b], умноженное на ширинуэтого интервала.Но при таком взгляде на искомый интеграл нетрудно заметить, что«среднее значение» функции f (x) можно получить каким-либо существенно более эффективным способом, чем простое увеличение количества равномерно расположенных точек xi . Например, можно попытаться раскидывать эти точки случайно по [a, b], но «приблизительноравномерно».
Резон в таком образе действий следующий: случайный,но равномерный выбор точек xi позволит в пределе иметь то же «среднее значение» функции, но, возможно, полученное быстрее, так какпри случайном бросании есть надежда, что будут легче учтены почтивсе «представительные» значения функции на [a, b].Для формализации высказанных идей целесообразно привлечь аппарат теории вероятностей. Эта математическая дисциплина исследуетслучайные явления, которые подчиняются свойству «статистическойустойчивости», т.
е. обнаруживают закономерности поведения в больших сериях повторяющихся испытаний. Одними из основных понятийтеории вероятностей являются понятия вероятности, случайной величины и её функции распределения. Случайной величиной называетсяпеременная величина, значения которой зависят от случая и для которой определена так называемая функция распределения вероятностей.Вероятность — это величина, выражающая относительную частоту интересующего нас события, которая обычно устанавливаюется в большой серии испытаний. Функция распределения показывает, следовательно, вероятность появления тех или иных значений этой случайнойвеличины. Конкретное значение, которое случайная величина принимает в результате отдельного опыта, обычно называют реализациейслучайной величины.Случайные и «приблизительно равномерные» точки моделируютсятак называемым равномерным вероятностным распределением, в котором при большом количестве испытаний (реализаций) в любые подинтервалы исходного интервала [a, b], имеющие равную длину, попадаетпримерно одинаковое количество точек.На этом пути мы и приходим к простейшему методу Монте-Карлодля вычисления определённого интеграла (2.149):1972.16.
Вычисление интегралов методом Монте-КарлоРис. 2.26. Вычисление объёма области методом Монте-Карло.фиксируем натуральное число N ;организуем реализации ξi , i = 1, 2, . . . , N , дляслучайной величины ξ, имеющей равномерноераспределение на интервале [a, b] ;(искомый интеграл) ←.(2.150)Nb−a Xf (ξi ) ;·Ni=1Получение равномерно распределённой случайной величины (каки других случайных распределений) является не вполне тривиальнойзадачей. Но она удовлетворительно решена на существующем уровнеразвития вычислительной техники и информатики. Так, практическиво всех современных языках программирования имеются средства длямоделирования простейших случайных величин, в частности, равномерного распределения на интервале.Рассмотрим теперь задачу определения площади фигуры с криволинейными границами (Рис.
2.26). Погрузим её в прямоугольник состоронами, параллельными координатным осям, имеющий известныеразмеры, и станем случайным образом раскидывать точки внутри этого прямоугольника. Ясно, что при равномерном распределении случайных бросаний вероятность попадания точки в рассматриваемую фигу-1982. Численные методы анализару равна отношению площадей этой фигуры и объемлющего её прямоугольника. С другой стороны, это отношение будет приблизительноравно относительной доле количества точек, которые попали в фигуру. Оно может быть вычислено в достаточно длинной серии случайныхбросаний точек в прямоугольник.На основе сформулированной выше идеи можно реализовать ещёодин способ вычисления интеграла от функции одной переменной.
Помещаем криволинейную трапецию, ограниченную графиком интегрируемой функции, в прямоугольник на плоскости 0xy. Затем организуемравномерное случайное бросание точек в этом прямоугольнике и подсчитываем относительную частоту точек, попадающих ниже графикаинтегрируемой функции. Искомый интеграл равен её произведению наплощадь большого прямоугольника (см. Рис. 2.27).y0xРис. 2.27. Один из способов приближённого вычисленияопределённого интеграла методом Монте-КарлоРезультаты вычислений по методу Монте-Карло сами являются случайной величиной, и два результата различных решений одной и тойже задачи, вообще говоря, могут отличаться друг от друга. Можнопоказать, что второй (геометрический) способ вычисления интеграламетодом Монте-Карло уступает по качеству результатов первому способу, основанному на нахождении «среднего значения» функции, таккак среднеквадратичный разброс получаемых оценок (называемый втеории вероятностей дисперсией) у него больше [31].Сформулированные выше идеи и основанные на них алгоритмы вдействительности применимы для интегрирования функций от произвольного количества переменных.
Более того, вероятностные оценки2.17. Правило Рунге для оценки погрешности199погрешности, пропорциональные N −1/2 , также не зависят от размерности n пространства, в котором берётся интеграл, тогда как для традиционных детерминистских методов интегрирования они ухудшаютсяс ростом n. Начиная c 7–8 переменных методы Монте-Карло уже превосходят по своей эффективности классические кубатурные формулыи являются главным методом вычисления многомерных интегралов.В заключение параграфа — краткий исторический очерк. Идея моделирования случайных явлений очень стара. В современной историинауки использование статистического моделировния для решения конкретных практических задач можно отсчитывать с конца XVIII века,когда Ж.-Л.
Бюффоном (в 1777 году) был предложен способ определения числа π с помощью случайных бросаний иглы на бумагу, разграфлённую параллельными линиями.23 Тем не менее, идея использованияслучайности при решении различных задач не получила большого развития вплоть до Второй мировой войны, т.
е. до середины XX века.В 1944 году в связи с работами по созданию атомной бомбы в США,поставившими ряд очень больших и сложных задач, С. Улам и Дж. фонНейман предложили широко использовать для их решения статистическое моделирование и аппарат теории вероятностей.24 Этому способствовало появление к тому времени электронных вычислительныхмашин, позволивших быстро выполнять многократные статистическиеиспытания (Дж. фон Нейман также принимал активное участие в создании первых цифровых ЭВМ). С конца 40-х годов XX века начинается широкое развитие метода Монте-Карло и методов статистическогомоделирования во всём мире.
В настоящее время их успешно применяют для решения самых разнообразных задач практики (см., к примеру,[31, 58] и цитированную там литературу).2.17Правило Рунгедля оценки погрешностиПредположим, что нам необходимо численно найти интеграл илипроизводную функции, либо решение дифференциального или интегрального уравнения, т. е. решить какую-либо задачу, где фигурирует23 Наиболее известная «докомпьютерная» реализация метода Бюффона была осуществлена американским астрономом А.
Холлом [72].24 Интересно, что примерно в те же самые годы в СССР решение аналогичныхзадач советского атомного проекта было успешно выполнено другими методами.2002. Численные методы анализасетка на интервале вещественной оси или в пространстве бо́льшего числа измерений. Пусть для решения этой задачи применяется численныйметод порядка p, так что главный член его погрешности равен Chp , гдеh — шаг рассматриваемой сетки, а C — величина, напрямую от h не зависящая. Как правило, значение C не известно точно и его нахождениенепосредственно из исходных данных задачи является делом трудными малоперспективным. Мы могли видеть, к примеру, что для задачинтерполирования и численного интегрирования выражение для этойконстанты вовлекает оценки для производных высоких порядков отрассматриваемой функции либо её разделённые разности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
