LDU — разложение

Можно доказать, что существование LU-разложения для матрицы гарантирует, что и матрица допускает LU-разложение: главные миноры матриц и совпадают. Из разложения.

(7).

при матрице нижнетреугольной и — верхнетреугольной следует, что.

(8).

Поскольку обе матрицы в правой части являются нижнетреугольными, то и их произведение также будет нижнетреугольной матрицей. Таким образом, матрица должна быть одновременно верхнеи нижнетреугольной. Следовательно, она — диагональная и.

(9).

при — верхнетреугольной с единицами на главной диагонали.

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

(10).

Компактная схема LDU — разложения:

Метод Гаусса

Согласно источнику [5], вычисления с помощью метода Гаусса (который называют также методом последовательного исключения неизвестных) состоят из двух основных этапов: прямого хода и обратного хода. Прямой ход метода заключается в последовательном исключении неизвестных из системы для преобразования ее к эквивалентной системе с треугольной матрицей. На этапе обратного хода производят вычисления значений неизвестных. Рассмотрим простейший вариант метода Гаусса, называемый схемой единственного деления.

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

(12).

Остальные уравнения системы (1) запишем в виде.

(13).

где .

Система (1) имеет матрицу вида:

Дальше осуществляется работа с укороченной системой, т.к. входит только в 1-ое уравнение.

(14).

2-й шаг. На этом шаге исключается неизвестное из уравнений с номерами. Если ведущий элемент второго шага, то из укороченной системы аналогично исключается неизвестное и получается матрица коэффициентов такого вида:

Это система с верхней треугольной матрицей.

Обратный ход метода. Из последнего уравнения системы (1) находим, из предпоследнего из первого уравнения — .

Общая формула для вычислений:

(15).

(16).

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

Ограничение метода единственного деления заключается в том, что ведущие элементы наом шаге исключения не равны нулю, т. е. .

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