|
| |
|
Слаботочка Книги I{f)= [ f{P)dP. Jg § 8. Метод Монте-Карло При построении квадратурных формул вместе с формулой, как правило, получалась оценка ее погрешности на некотором классе функций. Например, для одномерной формулы трапеций была получена оценка погрешности вида const-2Ar~ на классе функций со второй производной, ограниченной но модулю постоянной Лг; здесь iV-число узлов интегрирования. Такого рода оценки погрешности называют гарантированными оценками погрешности на классе функций. На основании этой оценки можно гарантировать, что погрешность приближенного значения интеграла не превосходит определенной величины для всех подынтегральных функций из рассматриваемого класса. Оценивая погрешность метода как оценку на классе функций, при оценке погрешности конкретного интеграла мы ориентируемся на величину, нолучаюп];уюся в случае интегрирования худшей функции рассматриваемого класса. Для ряда классов функций эта оценка погрешности на классе настолько плоха, что не дает никакой надежды на получение приближенного значения интеграла с требуемой точностью. Например, согласно теоремам из § 7, не суп];еству-ет методов с оценкой погрешности на классе функций С1...д(Л,..., Л), лучшей, чем dAN~ (здесь s - кратность вычисляемого интеграла). Предположим, что требуется гарантировать оценку погрешности, меньшую чем 0,01d. Тогда число узлов N должно удовлетворять неравенству dAN ! 0,01d, т.е. должно вьшолняться неравенство N 100*. Поскольку вычисление каждого значения подынтегральной функции требует обычно большого числа арифметических операций, уже при s = 6 такое требование на число узлов оказывается практически невыполнимым. Мы оказались в положении, когда на основе указанной выше оценки погрешности нет возможности вычислить значение интеграла с гарантированной оценкой погрешности 0,01йЛ, поскольку это потребует непомерных затрат времени ЭВМ. Одш из способов разрешения создавшегося противоречия состоит в более детальном описании классов подынтегральных функций. Другим выходом из создавшейся обстановки является отказ от получения строгой гарантированной оценки погрешности и получение оценки погрешности лишь с определенной степенью достоверности. В частности, при конструировании методов интегрирования в гл? 3 и в § 7 мы шли по пути отказа от строгой оценки погрешности: погрешность оценивалась через разность результатов вычисления приближенного значения интеграла при различных методах интегрирования. Одним из методов приближенного вычисления значений интегралов, при котором погрешность оценивается не гарантированно, а лишь с некоторой степенью достоверности, является метод Монте-Карло. Пусть требуется вычислить приближенное значение интеграла где Положим N: , Вследствие указанных свойств величин Sj имеем С вероятностью I - г] выполняется неравенство {неравенство Чебышева) \sM~iif)\Vm)IW)- (1) Полагая ij = 0,01, получаем: с вероятностью 99% выполняется неравенство \SNif)~I{f)\lOVD{f)/N. Еще лучшая оценка получается в предположении, что точки Pj не только попарно независимы, но и независимы в совокупности. Тогда, согласно центральной предельной теореме, случайная величина iSN{f)-I{f)) D{f)/N распределена асимптотически нормально с функцией распределения I ГУ Г Для упрощения выкладок предполагаем, что мера области G рав- на 1. Как правило, это условие бывает выполнено, поскольку при практической реализации метода Монте-Карло область интегрирования обычно преобразуется в единичный куб. Предположим, что каким-то образом удалось получить N случайных попарно независимых точек Pi,...,P/v, равномерно распределенных в G. Далее через M{s) будем обозначать математическое ожидание случайной величины s, а через D{s)-ее дисперсию. Случайные величины Sj - f{Pj) попарно независимы и одинаково распределены, причем Misj) = Jj{P)dP=I{f) D{sj) = M{sj) - {M{sj)f = DU), D{f) = I{f)-{lU)f- Po{y) = l--jj ехр-с/*. Таким образом, при больших N с вероятностью, близкой к ро{у), выполняется неравенство \SN{f)-I{f)\yjD{})lN. Полагая у = 3 и у = 5, получаем, что неравенства \SN{f)-I{f)\S/D{f)jN и \SN{f)-Hf)\5./D{f)jN выполняются соответственно с вероятностями 0,997 и 0,99999. Сформулированные выше утверждения называются иногда правилами трех сигм и пяти сигм соответственно. В правой части всех этих оценок стоит неизвестная величина D{f) = I{f) - {I{f)), которую можно оценить на основании информацрш о вычисленных значениях f{Pj)- Задача 1. Показать, что ЩЛ = j;M[sj{f) - SMf- (2) Поскольку на основавши закона больших чрюел с большой вероятностью выполняется приближенное равенство то с большой вероятностью выполняется и приближенное равенство где (л = ,Е{лл-з.{лУ. Приведем схему применения метода Монте-Карло при ц{С) - 1. Пусть - уровень надежности, с которым желательно получить приближенное значение интеграла, е - заданная точность. Определяют у из равенства Вероятность того, что случайная величина с такой функцией распределения не превосходит по модулю значение у > О, асимптотически равна 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 |