LU-факторизация.

Как было показано выше, основные вычислительные затраты в методе Гаусса связаны с приведением матрицы системы ЛАУ к треугольному виду (вычислительная сложность прямого хода метода Гаусса на порядок превосходит вычислительные затраты на обратный ход). В связи с этим во многих задачах оказывается целесообразным оптимизировать метод Гаусса с целью сохранения данных, полученных на этапе прямого хода. Данная модификация метода Гаусса получила название - факторизация. Само название указывает на то, что суть данного метода состоит в разложении матрицы на два сомножителя и – соответственно нижнюю и верхнюю треугольные матрицы.

Основной теоретический результат, касающийся существования и единственности представления матрицы вида заключается в следующем

Теорема. Если , то существует матрица перестановок такая, что имеет место разложение

, (2.8)

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

Согласно приведенной теореме - факторизация может использоваться для произвольной невырожденной матрицы.

Алгоритм вычисления матриц и во многом повторяет прямой ход метода Гаусса. В частности, из равенства (2.7) следует

. (2.9)

Умножим равенство (2.9) на произведение матриц , в результате имеем:

.

Из полученного равенства следует

. (2.10)

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

. (2.11)

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

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

Алгоритм разложения полезен в тех случаях, когда требуется решить несколько систем ЛАУ с одной и той же матрицей и разными правыми частями. После того как разложение матрицы получено, задача решения системы линейных алгебраических уравнений сводится к последовательному решению двух систем с матрицами треугольного вида: . Таким образом, однократное выполнение разложения позволяет на порядок сократить вычислительные затраты при серийных расчетах (многократных решениях систем ЛАУ с одинаковой матрицей).