5.6. Случай очень большого числа переменных.
Методы Монте-Карло, изложенные в §§ 2, 3, 4, часто используются в вычислительной практике, так как классические численные методы решения интегральных уравнений в многомерном случае приводят к весьма сложным расчетным схемам. Методы настоящего параграфа, напротив, сравнительно редко используются, так как эти задачи хорошо решаются численными средствами линейной алгебры. Пожалуй, только в задачах с большим числом переменных методы Монте-Карло могут успешно конкурировать с методами линейной алгебры [115],
Предположим, что требуется оценить одну компоненту
решения
системы (55), у которой все
В этом случае ряд
сходится быстрее, чем геометрическая прогрессия
при заданной точности можно ограничиться каким-то определенным количеством t слагаемых:
Будем считать, что
Для того чтобы по компонентам вектора
вычислить все компоненты вектора
необходимо проделать
умножений (операциями сложения, как более простыми, мы пренебрегаем). У вектора
нам нужна лишь одна компонента
Следовательно, общее количество умножений, затрачиваемых при расчете по формуле (77), равно
Рассмотрим теперь метод п. 5.3. Пусть все
это значит, что каждый номер
с равной вероятностью может принимать значения
независимо
Такой выбор можно (см. стр. 46) осуществлять по формуле
где у — очередное случайное число.
Для реализации цепи с такими вероятностями перехода надо: 1) выбрать
выбрать
и найти элемент
выбрать
и найти
т. д. до
Значение случайной величины (67), соответствующей (77), будет вычисляться по формуле
Если матрицу
заранее умножить на
то на расчет одного значения С будет затрачиваться всего
умножении (
на
и
). И если для достижения требуемой точности придется вычислить N цепей, то общее количество умножений при таком способе расчета равно
Очевидно, расчет методом Монте-Карло будет экономичнее, чем расчет
формуле (77), если
Легко показать, что величина N — количество цепей, необходимое для достижения заданной вероятной ошибки — ограничена при
. В самом деле, как известно, N пропорционально дисперсии
Но
и так как
Последняя граница ни от
, ни от t не зависит. Квадратному неравенству (78) удовлетворяют все
такие, что
Так как
, то это неравенство можно заменить более простым
Наконец, так как при
отношение
то последнее неравенство, а вместе с ним и (78), будет выполнено при любом
если только
Например, если
то метод Монте-Карло выгоднее, чем расчет по формуле (77), для систем порядка