1.1.2 Связь метода Гаусса с разложением матрицы на множители. Теорема об lu разложении.

Пусть дана система Aх=b (1.1), которая при прямом ходе преобразуется в эквивалентную систему (1.6) и запишем ее в виде

Cх=y, (1.6*)

где С – верхняя треугольная матрица с единицами на главной диагонали, полученная из (1.6) делением последнего уравнения системы на с_mm.

Как связаны в системе (1.1) элементы b и элементы y из (1.6*)?

Если внимательно посмотреть на прямой ход метода Гаусса, то можно увидеть, что

.

Для произвольного j имеем

, (1.7)

где j= , d_ji – числовые коэффициенты:

. (1.8)

Можно записать систему:

b=Dy,

где D−нижняя треугольная матрица с элементами на главной диагонали (j= , ).

В связи с тем, что в методе Гаусса угловые коэффици­енты не равны нулю , то на главной диагонали матрицы D стоят не нулевые элементы. Следовательно, эта матрица имеет обратную, тогда y=D^-1b, Сx= D^-1b.

Тогда

DCx=b. (1.9)

В результате использования метода Гаусса, получили разложение матрицы А на произведение двух матриц

A = DC,

где D − нижняя треугольная матрица, у которой элементы на главной диагонали не равны нулю, а C – верхняя тре­угольная матрица с единичной диагональю.

Таким образом, если задана матрица A и вектор b, то в методе Гаусса сначала производится разложение этой матрицы А на произведение D и C, а затем последова­тельно решаются две системы:

Dy=b,

Cx=y. (1.10)

Из последней системы находят искомый вектор x. При этом разложение матрицы А на произведение СD – есть прямой ход метода Гаусса, а решение систем (1.10) обратный ход. Обозначим нижнюю треугольную матрицу через L, верхнюю треугольную матрицу − U.

Теорема об LU разложении

Введем обозначения: − угловой минор порядка j матрицы А, т.е.

Теорема. Пусть все угловые миноры матрицы А не равны нулю (Δ_j0 для j= ). Тогда матрицу А можно представить единственным образом в виде произведе­ния А=L*U.

Идея доказательства. Рассмотрим матрицу А второго порядка и будем искать разложение этой матрицы в виде L и U.

.

Сопоставляя эти два равенства, определяем элементы матриц L и U (перемножим и приравняем неизвестные). Система имеет единственное решение. Методом математической индукции сказанное можно обобщить для матрицы размерности mm.

Следствие. Метод Гаусса (схему единственного деле­ния) можно применять только в том случае, когда угловые миноры матрицы А не равны нулю.

1.1.3 Метод Гаусса с выбором главного элемента

Может оказаться так, что система (1.1) имеет единст­венное решение, хотя какой либо из миноров матрицы А равен нулю. Заранее неизвестно, что все угловые миноры матрицы А не равны нулю. В этом случае можно использовать метод Гаусса с выбором главного элемента.

1. Выбор главного элемента по столбцу, когда на k-ом шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент при неизвестном х_k в уравнениях с номерами i=k,k+1,…,m. Затем уравнение, соответствующее выбранному коэффициенту, меняют местами с k-ым уравнением системы, чтобы ведущий элемент занял место коэффициента .После перестановки исключение неизвестного х_k выполняют как в схеме единственного деления.

ПРИМЕР. Пусть дана система второго порядка

Предположим, чтоа₂₁>а₁₁, тогда переставим уравнения

и применяем первый шаг прямого хода метода Гаусса. В этом случае имеет место перенумерация строк.

2. Выбор главного элемента по строке, т.е. производится перенумерация неизвестных системы.

При а₁₂> а₁₁, на первом шаге вместо неизвестного х₁ исключают х₂:

.

К этой системе применяем первый шаг прямого хода метода Гаусса.

3. Поиск главного элемента по всей матрице заклю­чается в совместном применении методов 1 и 2. Всё это приводит к уменьшению вычислительной погрешности, но может замедлить процесс решения задачи.