§ 18. Вторая вероятностная модель для решения системы линейных алгебраических уравнений

Рассмотренный выше способ решения системы линейных уравнений был предложен в работе [23].

Ниже рассматривается отличный от него способ решения линейных систем, пригодный для того же класса матриц. Рассмотрим этот способ для случая нахождения обратной матрицы Представим элементы матрицы в виде

где

Рассмотрим марковский процесс, представляющий собой систему обладающую -состоянием: так, что при этом переходные вероятности определены условием

Значение параметра а мы подчиним лишь условию

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

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

Описываемый марковский процесс специально предназначен для вычисления элементов столбца матрицы

Из определения нашего марковского процесса следует, что история «жизни» процесса с вероятностью, равной единице, описывается такой схемой:

т. е. прежде, чем перейти в особое состояние, система должна побывать в состоянии. Для того чтобы вычислить элемент матрицы мы возьмем в качестве начального состояния процесса состояние .

Согласно общей схеме мы определим связанную с рассматриваемым марковским процессом случайную величину являющуюся функцией от истории «жизни» процесса.

Для этого мы положим

в том случае, когда история «жизни» процесса описывается схемой (4.10). При этом мы обозначили

В том случае, когда история «жизни» процесса описывается схемой мы полагаем

Подсчитаем теперь среднее значение этой случайной величины:

Сравнивая (4.12) с (4.11), мы видим, что

Таким образом, мы получили метод для вычисления элементов обратной матрицы.

Вычислим дисперсию случайной величины §:

Нетрудно также написать выражение для средней длительности «жизни» рассматриваемого марковского процесса:

Выбор представления матрицы В в виде (4.10) и выбор значения параметра а должны производить исходя из условия минимальности времени вычисления при заданной точности, т. е. из условия минимальности произведения