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

Если матрица СЛАУ ленточная трехдиагональная, то метод Гаусса принимает более компактную форму и называется методом прогонки. СЛАУ при этом имеет следующий вид:

(5.16)

При прямой прогонке каждое неизвестное x_i выражается через x_i+1 :

(5.17)

где

(5.18)

Обратная прогонка состоит в определении всех неизвестных, начиная с последнего, по формулам (5.17) и (5.18).

Всего производится приблизительно 9/2n арифметических действий.

Если выполнено условие преобладания диагональных элементов

, (5.19)

то в формулах прямого хода не возникнет деления на ноль.

Вычисление определителя происходит в соответствии с методом Гаусса:

(5.20)

5.6. Метод lu-разложения

Матрица A СЛАУ

, (5.21)

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

A = LU, (5.22)

где L - нижняя треугольная, а U - верхняя треугольная матрицы:

; . (5.23)

Тогда СЛАУ (22) эквивалентна двум СЛАУ с треугольными матрицами

(5.24)

(5.25)

Решение их элементарно.

Проблема в том, чтобы получить разложение (22). Это соотношение в покомпонентной форме имеет вид

(5.26)

и является системой n² уравнений относительно n² искомых коэффициентов матриц L и U. Однако, если записать эти уравнения в определенном порядке, то каждое из них будет содержать только одно неизвестное и легко решается:

(5.27)

По трудоемкости метод LU - разложения равноценен методу Гаусса.

Вычисление определителя соответствует разложению (22):

(5.28)

5.7. Метод квадратного корня

Если СЛАУ имеет симметричную матрицу, то для последней возможно представление

A = S^TDS, (5.29)

где S - верхняя треугольная матрица, D - диагональная матрица с элементами +1 или -1. СЛАУ (3) тогда принимает вид

, (5.30)

который эквивалентен трем СЛАУ

; (5.31)

; (5.32)

. (5.33)

Для нахождения коэффициентов матриц S и D разложение (29) записывается в покомпонентном виде

. (5.34)

Записывая уравнения (34) в определенном порядке, можно определить коэффициенты матриц S и D:

(5.35)

Метод квадратного корня требует приблизительно 1/3n³ арифметических действий.

Вычисление определителя соответствует разложению (29):

(5.36)

Здесь p - количество отрицательных элементов матрицы D.

Если матрица A - не только симметрична, но и положительно определенна, то в разложении (29) D - единичная матрица и тогда СЛАУ (3) принимает более простой вид

, (5.37)

который эквивалентен двум СЛАУ

; (5.38)

. (5.39)

Последовательность определения коэффициентов матрицы S аналогична (35).

Вычисление определителя:

(5.39)

5.7. Итерационные методы решения слау

Итерационные методы решения СЛАУ заключаются в построении последовательности векторов (k=0,1,2,…), сходящейся к вектору - решению :

. (5.40)

На практике приближенное решение считается найденным, если норма вектора невязки в (5.40) монотонно уменьшается с ростом k (метод сходится) и выполняется условие

, (5.41)

где - допустимая погрешность, а m достаточно велико, чтобы считать "точным" по сравнению с .

Кроме условия (5.41) на практике также применяется условие малости невязки для СЛАУ:

. (5.42)

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

Метод простой итерации строится приведением СЛАУ (1) к виду

(5.43)

после чего итерационный процесс принимает следующий вид:

(5.44)

где k = 0,1,2,… .

Достаточные условия сходимости:

(5.45)

или

. (5.46)

Оценки погрешности:

, (5.47)

если выполнено условие (45) или

, (5.48)

если выполнено условие (46).

Метод Зейделя является модификацией метода простой итерации:

(5.49)

Условия и оценки его сходимости какие же, как и для метода простой итерации. Дополнительное условие сходимости: если матрица СЛАУ симметричная положительноопределенная, то метод Зейделя сходится.

В методе релаксации каждая итерация состоит из двух шагов:

1. в соответствии с методом Зейделя (49) определяется промежуточное значение вектора ;

2. определяется очередное приближение вектора

. (5.50)

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

Для СЛАУ с симметричной положительноопределенной матрицей метод релаксации сходится при .