ГЛАВА IV. ОБРАЩЕНИЕ МАТРИЦ И РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

§ 17. Метод решения системы линейных уравнений, связанных с методом простых итераций

Основная цель настоящего параграфа состоит в построении модели случайного процесса, связанного с решением системы линейных алгебраических уравнений.

Эта модель годится лишь для частного случая матриц, «близких» к единичной матрице в смысле, указанном ниже. Этот класс матриц совпадает с классом матриц, для которых соответствующая система линейных уравнений допускает решение по методу простых итераций. Модель строится по принципу марковского процесса, заканчивающегося с вероятностью единица в конечное число шагов. По-видимому, эта модель имеет главным образом теоретический интерес и сложна для практической реализаций. Практическое значение имеет применение таких. моделей для систем линейных уравнений, связанных с решением дифференциальных и интегральных уравнений математической физики.

Рассмотрим систему линейных уравнений, записанную в векторной форме:

Здесь А — -мерная матрица, а и -мерные векторы. Пусть имеет место случай, когда пригоден метод простых итераций, т. е. матрица А представима в виде

где Е — единичная матрица, а В имеет собственные числа, по модулю меньшие единицы.

Система (4.1) эквивалентна системе

Решение системы (4.1) представимо в виде

При сделанных предположениях обратная матрица может быть выражена рядом

Этот ряд сходится в том и только в том случае, если собственные числа матрицы В по модулю меньше единицы, т. е.

Подставим теперь выражение (4.3) в (4.2), выражая решение в виде ряда

Частные суммы последнего ряда можно получить известным итерационным приемом, полагая последовательно

Сходимость метода простых итераций эквивалентна сходимости последовательности Для вычисления перейдем к координатной записи. Будем обозначать элементы матрицы В через Тогда координата вектора равна

Вопрос состоит в том, чтобы найти метод вычисления суммы (4.5).

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

Тогда величины можно рассматривать как набор вероятностей для полной системы несовместимых со бытий.

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

Вынем наугад шар из урны и образуем случайную величину выбрав в качестве ее значения число если вынут шар сорта. Математическое ожидание величины равно, очевидно,

т. е. равно второму слагаемому ряда (4.5).

Постараемся теперь получить случайную величину, математическое ожидание которой равно третьему слагаемому ряда (4.5). Для этого обратимся сначала к урне и вынем из нее шар. Если оказался вынутым шар сорта, то обратимся к урне. Если в результате последующего обращения к урне вынут шар сорта, то положим значение величины равным

Ясно, что вероятность, с которой случайная величина принимает значение равна

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

Рассмотренная конструкция допускает простое обобщение, позволяющее получить случайную величину математическое ожидание которой равно сумме ряда (4.5), т. е.

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

Оценка ошибки производится с помощью неравенства (0.5). Конструкция случайной величины состоит в следующем. Представим каждый элемент матрицы В в виде произведения двух сомножителей

где

Координаты векторов правой части (4.1) представим в виде где

При этом будем предполагать, что выполнено равенство

Тогда равенство (4.5) можно представить в виде

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

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

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

Математическое ожидание величины равно

Подставляя (4.8) в (4.9) и сравнивая с (4.7), получаем

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

Тем самым получился некоторый процесс Монте-Карло для решения систем линейных алгебраических уравнений. Существуют и другие процессы такого рода, где статистическая модель годится для нахождения обратной матрицы или для решения системы с более общей матрицей А.

Преимущество изложенного метода решения состоит в следующем: при обычном методе решения систем линейных уравнений для вычисления одного неизвестного нужно определять и все остальные; в приведенном же способе этого делать не нужно, каждый раз определяется одна координата . Это проявляется в том, что число арифметических операций пропорционально числу уравнений, а не кубу этого числа, как в точных численных методах. Отсюда видно, что и здесь проявляется одна из основных черт метода Монте-Карло — его эффективность при решении многомерных задач.