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

5.2. Случайная цепь для решения алгебраической системы.

Очевидно, все методы Монте-Карло, приведенные в § 2, применимы для оценки решений уравнения (57) и дают нам возможность оценить решение системы (55). Однако специфика уравнения (57) позволяет упростить эти методы и дать им иную интерпретацию.

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

Величины очевидно, должны быть неотрицательными и удовлетворять условиям нормировки

Правила (59) можно интерпретировать как равномерное распределение случайной точки внутри соответственно или . Можно, однако, совсем отказаться от фиксации положения этой точки и говорить только об отрезке, в котором эта точка расположена. Тогда — это вероятность того, что начальная точка траектории попадет в вероятность того, что случайная точка из перейдет в . При такой интерпретации вместо траектории случайной точки достаточно рассмотреть последовательность случайных номеров

тех отрезков в которые эта точка попадет.

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

где начальные вероятности и вероятности переходов должны удовлетворять условиям нормировки (60).

В теории вероятностей такие цепи называются цепями Маркова с конечным числом состояний [71]. Веса вдоль цепи (61) вычисляются по формуле

или по рекуррентной формуле

Формулы эти — следствие (4) и (5).

Условимся говорить, что распределение вероятностей допустимо по отношению к вектору если для тех а, для которых значение Аналогично распределение допустимо по отношению к матрице если для тех пар для которых

Как известно, из теории матриц, для того чтобы

ряд сходился для любого вектора необходимо и достаточно, чтобы все собственные значения матрицы А, представляющие собой корни уравнения лежали внутри единичного круга (на комплексной плоскости): при . Достаточным условием может служить неравенство

Сформулируем для системы (55) теорему, вытекающую из теоремы . Пусть бесконечная цепь строится по правилам (62), где допустимы по отношению к соответственно, и рассмотрим случайную величину

Теорема 8. Если все собственные значения матрицы по абсолютной величине меньше единицы, то математическое ожидание случайной величины равно

Повторим доказательство со стр. 177 применительно к рассматриваемому случаю. Так как

то, принимая во внимание (63), получим, что

Затем

причем существование этого математического ожидания обеспечивается условиями теоремы

Если какие-нибудь из элементов матрицы равны нулю, то обычно целесообразно выбрать соответствующие вероятности перехода (ср. п. 3.2.1 гл. 3). В противном случае, если в цепи окажется переход которому отвечает то из (63) видно, что все можно считать, что цепь, попав в останавливается: любые дальнейшие переходы значения величины не изменят.

Если матрица А содержит целую строку из нулей: , то, конечно, нельзя все соответствующие вероятности выбрать нулевыми: это противоречило бы условию (60). Тогда можно положить при , так что

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