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

5.4. Обращение матрицы.

Пусть задана квадратная матрица Требуется вычислить элементы обратной матрицы удовлетворяющей соотношению , где Е — единичная матрица:

Если все собственные значения матрицы В удовлетворяют условию

то задача эта может быть решена методом последовательных приближений. В самом деле, обозначим через А матрицу

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

и

Докажем, что если матрица А удовлетворяет условиям теоремы 8, то для того, чтобы вычислить элемент матрицы С, можно использовать цепи п. 5.3; надо лишь, кроме , выбрать еще

В самом деле, мы видели, что , где компонента решения уравнения (56). Однако это решение равно

так что его компонента есть

В частном случае, когда получим, что , что и требовалось доказать.

Подставив в (67) вместо f вектор , получим соответствующий этому случаю метод Монте-Карло: при достаточно большом N

здесь снова s — номер цепи, а сумма с условием означает, что суммируются только те для которых номер

5.4.1. Численный пример:

найти матрицу С, обратную к матрице

собственные значения которой, очевидно, равны

Сперва по формуле (68) вычислим матрицу

Затем выберем матрицу вероятностей перехода, допустимую по отношению к матрице А, например:

1) Чтобы оценить элементы , надо строить цепи, начинающиеся с . Так как в первой строке матрицы (70) лишь то все цепи окажутся одинаковыми:

Веса вдоль такой цепи меняются на множитель —

Осреднение в (69) не нужно, достаточно одной цепи для получения точного результата

2) Столь же просто оцениваются элементы и : цепь начинается с так как в третьей строке матрицы (70) лишь один ненулевой элемент то далее Итак, все цепи будут одинаковыми

а соответствующие веса (с учетом того, что ) равны

Поэтому

3) И только для вычисления нужно действительно строить случайные цепи, начинающиеся с и производить расчеты. Впрочем, в этом случае различные типы цепей легко классифицируются, ибо во второй строке матрицы (70) лишь отличны от нуля.

Цепь, начало которой , может несколько раз оставаться в . Но если окажется, что , то дальше уже все Следовательно, общий вид такой

Соответствующие такой цени веса легко вычислить: так как то

Интересующие нас суммы весов вдоль такой цепи равны

Из этих соотношений сразу следует, что

Оставшийся элемент можно вычислить аналитически, если записать, что вероятность получить цепь (71) равна (см. начало стр. 39)

и вместо формулы (69) воспользоваться точным выражением для математического ожидания

Итак, обратная матрица С равна

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

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