Главная > Математика > Численные методы Монте-Карло
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.6. Случай очень большого числа переменных.

Методы Монте-Карло, изложенные в §§ 2, 3, 4, часто используются в вычислительной практике, так как классические численные методы решения интегральных уравнений в многомерном случае приводят к весьма сложным расчетным схемам. Методы настоящего параграфа, напротив, сравнительно редко используются, так как эти задачи хорошо решаются численными средствами линейной алгебры. Пожалуй, только в задачах с большим числом переменных методы Монте-Карло могут успешно конкурировать с методами линейной алгебры [115],

Предположим, что требуется оценить одну компоненту решения системы (55), у которой все

В этом случае ряд сходится быстрее, чем геометрическая прогрессия при заданной точности можно ограничиться каким-то определенным количеством t слагаемых:

Будем считать, что Для того чтобы по компонентам вектора вычислить все компоненты вектора необходимо проделать умножений (операциями сложения, как более простыми, мы пренебрегаем). У вектора нам нужна лишь одна компонента Следовательно, общее количество умножений, затрачиваемых при расчете по формуле (77), равно

Рассмотрим теперь метод п. 5.3. Пусть все это значит, что каждый номер с равной вероятностью может принимать значения независимо Такой выбор можно (см. стр. 46) осуществлять по формуле где у — очередное случайное число.

Для реализации цепи с такими вероятностями перехода надо: 1) выбрать выбрать и найти элемент выбрать и найти т. д. до Значение случайной величины (67), соответствующей (77), будет вычисляться по формуле

Если матрицу заранее умножить на то на расчет одного значения С будет затрачиваться всего умножении ( на и ). И если для достижения требуемой точности придется вычислить N цепей, то общее количество умножений при таком способе расчета равно

Очевидно, расчет методом Монте-Карло будет экономичнее, чем расчет формуле (77), если

Легко показать, что величина N — количество цепей, необходимое для достижения заданной вероятной ошибки — ограничена при . В самом деле, как известно, N пропорционально дисперсии Но и так как Последняя граница ни от , ни от t не зависит. Квадратному неравенству (78) удовлетворяют все такие, что

Так как , то это неравенство можно заменить более простым

Наконец, так как при отношение то последнее неравенство, а вместе с ним и (78), будет выполнено при любом если только

Например, если то метод Монте-Карло выгоднее, чем расчет по формуле (77), для систем порядка

<< Предыдущий параграф Следующий параграф >>
Оглавление