Решение систем линейных уравнений методом Гаусса, методом Монте-Карло и методом ортогонализации

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

Опишем алгоритм решения методом Монте-Карло системы линейных уравнений [6]. Пусть исходная система (1.1) записана в виде:

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n + a_{1n + 1} = 0

a₂₁x₁ + a₂₂x₂ + … +  a_2nx_n + a_{2n + 1} = 0                                  (2.1)

                              ……………………………………

a_n1x₁ +  a_n2x₂ +  … + a_nnx_n + a_{nn + 1} = 0

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

x₁ = a₁₁x₁ + a₁₂x₂ +  a₁₃x₃ + … + a_1nx_n + a_{1n + 1}

                                    x₂ = a₂₁x₁ + a₂₂x₂ +  a₂₃x₃ + … + a_2nx_n + a_{2n + 1}                       (2.2)

                                          ……………………………………………….

x_n = a_n1x₁ + a_n2x₂ +  a_n3x₃ + … + a_nnx_n + a_{nn + 1}

Будем предполагать, что для системы (2.2) имеют место соотношения:

.  (i = 1, 2, …, n)                             (2.3)

От системы (2.1) к системе (2.2), удовлетворяющей соот­ношениям (2.3), можно перейти с помощью таких преобразований.

Пусть для фиксированного i

.                                     (2.4)

Если в i-м уравнении системы (2.1) коэффициент a_ii>0, то делим каждый член этого уравнения на –L, в противном случае делим каждый член уравнения на L.

Обозначим

и .                                  (2.5)

Полученные числа и будут коэффициентами системы (2.2).

Сопоставим теперь i-му уравнению этой системы разбиение отрезка [0; 1] на n + l отрезков точками s_j, каждая из которых мест координату, определяемую соотношениями

(j = 1, 2, ..., n).                                   (2.6)

Кроме того, положим s₀ = 0 и s_n+1 = 1.

Рассмотрим процесс «случайного блуждания» некоторой частицы, которая в начальный момент находится в точке s, i-го раз­биения отрезка [0; 1]. Воспользовавшись возможностью получения случайных чисел, равномерно распределенных на отрезке [0; 1], рассмотрим такое случайное число c. Если оно удовлетворяет соотношению

s_{j – 1}< c ≤ s_j (j = 1, 2, ..., n)                                   (2.7)

для точек рассматриваемого i-го разбиения, то считаем, что час­тица переходит из точки s_i i-го разбиения в точку s_j j-го разбиения. Снова получаем случайное число и рассматриваем его положение относительно точек j-го разбиения. Если в этом разбиении полу­ченное число лежит на отрезке , то считаем, что частица переходит из точки s_j j-го разбиения в точку s_k k-го разбиения. В том случае, когда для некоторого разбиения очередное случайное число попадет на отрезок  считаем, что частица переходит в точку s_n+1 и процесс случайного блуждания заканчивается. После­довательность точек s_i, s_j, s_k, ..., s_l, s_m, s_n+1 назовем траекторией частицы. Свяжем с этой траекторией случайную величину y_i, задаваемую соотношением

,                              (2.8)

где

, , ..., ,                  (2.9)

а величина определяется равенством

.                                                    (2.10)

Можно доказать, что математическое ожидание случайной величины y_i, равно значению корня x_i системы (2.2). Этот факт дает способ практического отыскания x_i. Осуществим M реализаций случайного блуждания частицы по траектории, начинающейся в точке s_i. Обозначим через Y сумму значений случай­ной величины y_i, полученных во всех реализациях. Тогда будем иметь приближенное равенство

.                                                          (2.11)

Следует иметь в виду, что при решении систем линейных урав­нений методом Монте-Карло точность получаемых результатов сравнительно невысока. Повышение точности вычислений требует значительного увеличения числа реализаций, а значит, и времени решения системы. Вместе с тем ни один из известных методов решения систем линейных уравнений (кроме метода Монте-Карло) не позволяет вычислить значение одного корня системы, не вычисляя значения других корней.

3 Решение систем линейных уравнений методом ортогонализации

Очень часто программа решения системы линейных уравнений должна быть использована не для решения одной, отдельно взятой системы, а как составная часть более общей программы. Естественно, что «встраиваемая» программа должна быть как можно компактнее, не должна требовать никаких проверок сходимости или значитель­ных преобразований исходной, системы. Поэтому опишем сейчас еще один метод решения системы линейных уравнений – метод ортогонализации.

Пусть исходная система записана в виде:

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n + a_{1n + 1} = 0

a₂₁x₁ + a₂₂x₂ + … +  a_2nx_n + a_{2n + 1} = 0                                  (3.1)

                              ……………………………………

a_n1x₁ +  a_n2x₂ +  … + a_nnx_n + a_{nn + 1} = 0

Левую часть каждого уравнения системы можно рассматри­вать как скалярное произведение двух векторов:

a_i=(a_i1, a_i2, …, a_in, a_in+1)

x = (x₁,  x₂,   ...,   x_n,   1).

Таким образом, решение системы (3.1) сводится к построению вектора, ортогонального к каждому вектору a_i. Добавим к системе векторов a_i, линейно независимый от них вектор a_n+1 = (0, 0, ..., 0, 1). В векторном пространстве размерности n + 1 будем строить такой его ортонормированный базис