2.5. Метод Халецкого

При решении системы уравнений Ax=b методом Халецкого [2-4, 10,11] используется «теорема о LU разложении» (см. §1.3) согласно которой можно написать

A=LU, (2.20)

где

L= , U= .

Тогда согласно формуле (2.20) элементы l_ij , u_ij определяются по формулам

(ij>1). (2.21)

(2.22)

Далее искомый вектор х вычисляется решением двух систем уравнений

Ly=b,

Ux=y.

Так как матрицы L и U треугольные, эти системы решаются по формулам

(2.23)

где a_in+1=b_i , (i=1,…,n).

(2.24)

Формулы (2.21)-(2.24) составляют алгоритм метода.

2.6. Метод квадратных корней

Метод квадратных корней [2, 3, 11] применяется при решении системы уравнений

Ах=b, (2.25)

когда матрица А – симметричная, т.е. А=А^Т , (a_ij=a_ji). При detA0 согласно «теореме о LU разложении» (см. §1.3) можно записать A=LU, где U=T, L=T^T. Тогда

А=Т^Т Т, (2.26)

где

Т= , Т^Т= .

Расписывая, формулу (2.26) получим формулы для вычисления t_ij

Отсюда находим

(2.27)

Система линейных алгебраических уравнений (2.25) имеет единственное решение, если t_ii0 (i=1,…,n), так как detA=(detT)²=(t₁₁^.t₂₂^. _… ^.t_nn)²0.

Используя, формулу (2.26) систему уравнений (2.25) можно переписать в виде двух систем уравнений

Т^Тy=b, (2.28)

Тх=у. (2.29)

Расписывая, систему уравнений (2.28) получим

(2.30)

Расписывая, систему уравнений (2.29) получим

(2.31)

Из формулы (2.30) находим

(2.32)

Из формул (2.31) определяем неизвестные

(2.33)

Формулы (2.27), (2.32) и (2.33) составляют алгоритм метода квадратных корней.

2.7. Метод прогонки

Метод прогонки [9, 11] предназначен для решения системы линейных уравнений

Ax=b, (2.34)

когда матрица А – трехдиагональная и ненулевые элементы определяются следующим образом: a_ij0, если j=i-1, j=i, j=i+1.

Введем обозначения

a_ii-1=-a_i , a_ii=c_i , a_ii+1=-d_i .

Тогда система уравнений (2.34) запишется в виде

(2.35)

Решение (2.35) будем искать в виде

x_i=_ix_i+1+_i , (2.36)

где _i , _i – неизвестные прогоночные коэффициенты. Подставив, найденные из (2.36) x_i-1 в среднее уравнение из системы (2.35), получим для 2in-1 :

(2.37)

Из сравнения (2.36) и (2.37) следует, что

(2.38)

Зная ₁ , ₁ по формулам (2.38) можно найти все _i , _i для i=2, 3,…, n, то есть провести прямой ход прогонки.

Если удастся найти x_n , то по формуле (2.36) при известных _i , _i можно вычислить неизвестные x_i для i=n-1, n-2,…, 1, то есть провести обратный ход прогонки. Поэтому дальше определяем ₁ , ₁ и x_n .

Из первого уравнения системы (2.35) найдем

что вместе с уравнение

х₁=₁х₂+₁

из (2.36) при i=1 дает

(2.39)

Далее, из последнего уравнения системы (2.35) и из (2.36) при i=n-1 имеем систему уравнений

откуда находим

(2.40)

Таким образом, алгоритм метода прогонки при решении СЛАУ (2.35) заключается в следующем:

1. по формулам (2.39) и (2.38) вычисляются коэффициенты _i , _i для i=1, 2,…,n (прямой ход);

2) по формулам (2.40) и (2.36) вычисляются неизвестные x_i для i=n-1, n-2,…, 1 (обратный ход).

Метод прогонки реализуется, если нет деления на нуль в формулах (2.38)-(2.40). Для выполнения этого условия достаточно, чтобы detA0.

Так как при использовании метода прогонки заранее неизвестен detA , то необходим простой способ оценки устойчивости метода.

Достаточные условия устойчивости метода прогонки. Для устойчивости метода прогонки достаточно выполнение неравенств:

Рассмотренный здесь вариант метода прогонки называется правой прогонкой. Название метода следует из того, что при обратном ходе неизвестные x_i вычисляются справа налево, т.е. сначала x_n , x_n-1 и т.д.

Существует метод левой прогонки, в котором неизвестные x_i вычисляются слева направо, т.е. сначала х₁ , х₂ и так далее.

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