|
| |
|
Слаботочка Книги §8. Метод Монте-Карло 235 Последовательно при п= 1,... получают случайные точки Р и вычисляют величины Snif), dnif), пользуясь рекуррентными соотношениями Uf) = tn-iif) + ПРп), Snif) = Ш)/гь, dm) = + {fipn) - sm))\ dm) = dn(/)/(n - 1), a также вычисляют значение A = yvdnif)/n. Начальные условия рекурсии: hif) = = /(Pi), di(/) = ddf) = 0. Если оказалось, что A e, то вычисления прекращаются; полагают I if) ~ Sivif) и считают, что с вероятностью I - у выполняется неравенство Ш) - Sr,if)\ е. Заметим, что в действительности неравенство /(/) - Srf{f)\ е выполняется с вероятностью, несколько меньшей чем 1 - у, хотя и близкой к ней. Задача 2. Проверить, что Dn{f) = Df). Для уменьшения погрешности метода Монте-Карло случайные узлы интегрирования берутся распределенными не равномерно, а с некоторой плотностью р(Р) /1, / р(Р) dP = 1. В этом случае полагают JG 1 /(/)5(/) = E/(i)/P(i)- Задача 3. Показать, что m{s{f)) = /(/), D{f) = ШУр) - {I{f)f. Убедиться в том, что переход к такому выбору случайных величин особенно целесообразен в случае f{P)/p{P) const. Часто в руководствах по использованию метода Монте-Карло говорится следующее. Метод Монте-Карло является универсальным методом вычисления интегралов высокой кратности. Порядок оценки скорости сходимости метода Монте-Карло есть 0{1/л/м) и не зависит от размерности интеграла, в то время как порядок гарантированных оценок скорости сходимости существенно ухудшается с ростом размерности. Для метода Монте-Карло при каждом п имеется эффективная оценка погрешности через величину y/dnif)/n, и, таким образом, вычисления прекращаются именно в тот момент, когда достигнута требуемая точность. Отнесемся осторожно к этому заявлению и рассмотрим различные соображения за и против метода Монте-Карло. § 9. Обсуждение правомерности использования недетерминированных методов решения задач Часть пользователей предубеждена против метода Монте-Карло и отрицает правомерность его использования, поскольку малость погрешности метода обеспечивается лишь с некоторой вероятностью. Выше мы уже обрисовали картину, складывающуюся при вычислении интегралов большой кратности, как почти полностью безнадежную в случае, если ставится цель получения приближенного значения интеграла с гарантированно малой оценкой погрешности. Такая обстановка и вызвала к жизни применение метода Монте-Карло. Уже при вычислении однократных интегралов гарантия малости погрешности метода может быть получена только при использовании строгих теоретических оценок. Применение таких оценок требует высокой математической квалификации исследователя, затрат его умственного труда и не может быть перепоручена ЭВМ. Таким образом, ориентировка на методы вычисления интегралов с гарантированной оценкой погрешности противоречит общей тенденции использования ЭВМ. Кроме того, при решении всякой задачи возможны ошибки в постановке задачи, в программе и т.д. В силу этих и ряда других причин редко можно дать стопроцентную гарантию малости погрешности результата расчета по отношению к реальной модели; некоторая вероятность ошибочности результатов вычислений имеется в любом случае. Все это подчеркивает, что полный отказ от метода Монте-Ка,рло только из-за его вероятностной природы является неоправданным. С другой стороны, при использовании метода Монте-Карло нужно учитывать следующие отрицательные эффекты. Для применения метода Монте-Карло необходимо иметь в распоряжении последовательность независимых точек Pj с заданным законом распределения. Обычно пользователь располагает датчиками случайных или так называемых псевдослучайных чисел, которые выдают последовательности случайных чисел, равномерно распределенных на отрезке [О, 1]. При помощи преобразований таких случайных величин получаются случайные числа с заданным законом распределения. На уервых ЭВМ датчиками случайных чисел были некоторые приборы, например использующие явление радиоактивного распада, которые вьщавали последовательности случайных величин, иногда даже удовлетворяющие требованию независимости в совокупности. Однако такие приборы работают с малой скоростью, и поэтому с увеличением производительности ЭВМ от них отказались. Вместо датчиков случайных чисел используют датчики псевдослучайных чисел - некоторые программы, выдающие последовательности чисел, которые рекомендуется рассматривать как случайные. Использование датчиков псевдослучайных чисел явилось прогрессивным шагом, позволившим широко применять вероятностные методы. Однако при использовании этих датчиков нужно всегда иметь в виду, какими свойствами обладают последовательности чисел, выдаваемые этими датчиками. Например, некоторые датчики псевдослучайных чисел вырабатывают последовательности чисел, которые можно рассматривать лишь как попарно независимые, а не как независимые в совокупности. В этом случае будет неправомерно пользоваться оценками погрешности, основанными на центральной предельной теореме. Пусть методом Монте-Карло вычисляется интеграл Hf) = fixi,..., x )dxi...dxs. Jo Jo Преположим, что в качестве узлов интегрирования мы хотим выбрать последовательность независимых равномерно распределенных точек единичного куба. Ес1ш датчик псевдослучайных чисел выдает последовательность 1,..- чисел, равномерно распределенных на отрезке [О, 1], то можно попытаться в качестве узлов интегрирования взять точки (Ci,..-,s)) Для законности применения неравенства Чебышева нужно выполнение предположения о независимости распределения любых точек Pj, т.е. независимости распределения совокупностей ((j-l)s-bb Cjs), ((г-1).5+Ь 5 Js)- При увеличении s это уаювие накладывает все более жесткие требования на датчики псевдослучайных чисел. Известно много реальных примеров неудачного применения метода Моите-Карло в случае больших я, вызванных следующей причиной. При использовании метода и оценке погрешности делались допущения о тех или иных статистических свойствах псевдослучайных чисел, в то время как эти предположения на самом деле не выполнялись. В результате делался вывод о малости значения погрешности, который на самом деле не был справедлив. Таким образом, опасность применения метода Монте-Карло заключается но большей части не в вероятностном характере оценки погрешности, а в том, что вероятностная оценка погрешности производится зачастую в предположении о свойствах датчиков случайных чисел, которые на самом деле не имеют места. Задача!. Пусть , 2 ~~ случайные независимые величины, равномерно распределенные на отрезке [О, 1]. Пусть {у}-дробная доля числа у, т.е. {у} = У~ [у], где [у] - целая часть у. Положим = {i + {п - 1)(2 - 6)}-Показать, что точки попарно независимы, равномерно распределены на [О, 1] и, согласно построениям предыдущего параграфа, ш)= [f{x)dxsMf) = J2f(jy Jo N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 [77] 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 |