Пусть 
– данная 
– матрица, а 
и 
– соответственно нижняя (левая) и верхняя (правая) треугольные матрицы. Справедливо следующее утверждение.
Теорема 5.1. Если все главные миноры квадратной матрицы 
отличны от нуля, то существуют такие нижняя 
и верхняя 
треугольные матрицы, что 
. Если элементы диагонали одной из матриц или фиксированы (ненулевые), то такое разложение единственно.
Определим 
(при 
) и 
(при 
) такие, чтобы
Выполнив перемножение матриц, на основе поэлементного приравнивания левых и правых частей приходим к -матрице уравнений
относительно -матрицы неизвестных
(5.8)
Специфика этой системы позволяет находить неизвестные (5.8) одно за другим в следующем порядке.
Из первой строки уравнений имеем
;
из оставшейся части первого столбца уравнений
;
из оставшейся части второй строки
;
из оставшейся части второго столбца
и т.д. Последним находится элемент
Легко видеть, что все отличные от 0 и 1 элементы матриц и могут быть однозначно вычислены с помощью всего двух формул:
(5.9)
(5.10)
При практическом выполнении разложения матрицы нужно иметь в виду следующие два обстоятельства:
1. организация вычислений по формулам (5.9)-(5.10) должна предусматривать переключение счета с одной формулы на другую в соответствии с показанным выше процессом получения неизвестных, приведшим к этим формулам. Это удобно делать, ориентируясь на матрицу неизвестных (5.8), а именно, первая строка (5.8) вычисляется по формуле (5.9) при 
, 
; первый столбец (5.8) (без первого элемента) – по формуле (5.10) при 
, 
, и т. д.
2. препятствием для осуществимости описанного процесса LU-разложения матрицы может оказаться равенство нулю диагональных элементов матрицы , поскольку на них выполняется деление по формуле (5.10). Отсюда требование теоремы, накладываемое на главные миноры.
Заметим, что 
, т. е. первый диагональный элемент матрицы совпадает с первым минором и по условию должен быть отличным от нуля. Второй диагональный элемент матрицы
не равен нулю, если отличен от нуля второй главный минор, и т. д. Ясно, что вместо проверки на равенство нулю главных миноров данной матрицы удобнее делать такую проверку для элементов в процессе их вычисления, причем, чтобы уменьшить влияние погрешностей округлений, лучше сравнивать модули с малой положительной константой (допуском). Для определенных классов матриц требования теоремы о разложении заведомо выполняются. Это относится, например, к матрицам с диагональным преобладанием, т. е. к таким, для которых
Если матрица исходной системы (5.1) разложена в произведение треугольных и , то, значит, вместо (5.1а) можно записать эквивалентное (5.1) уравнение
.
Введя вектор вспомогательных переменных 
, последнее можно переписать в виде системы
Таким образом, решение данной системы с квадратной матрицей коэффициентов свелось к последовательному решению двух систем с треугольными матрицами коэффициентов.
Получим сначала формулы для вычисления элементов 
вспомогательного вектора 
. Для этого запишем уравнение 
в развернутом виде:
Очевидно, что все могут быть последовательно найдены при 
по формуле
. (5.11)
Развернем теперь векторно-матричное уравнение 
:
(5.12)
Отсюда значения неизвестных 
находятся в обратном порядке, т. е. при 
по формуле
(5.13)
Решение линейных систем с помощью LU-разложения – это другая система реализации метода Гаусса. В отличие от рассмотренной в параграфе 5.1, так называемой, схемы единственного деления эту называют компактной схемой Гаусса или схемой Холецкого.
Вычисление определителя LU-факторизованной матрицы опирается на свойство определителя произведения матриц и сводится к перемножению 
чисел:
Для обращения матрицы с помощью LU-факторизации можно применить тот же прием, который рассмотрен в параграфе 5.2, т.е. -кратно использовать формулы (5.11) и (5.13) для получения столбцов матрицы 
; при этомв качестве 
в (5.11) должны фигурировать только 0 или 1: для нахождения первого столбца полагаем 
, для второго – 
и т.д. Можно однако вывести и специальные формулы для выражения элементов обратной матрицы через элементы матриц и . Продемонстрируем это.
Пусть матрицы и обратимы (матрица обратима всегда). Тогда
Умножая последнее равенство поочередно на слева и на справа, будем иметь
и 
(5.14)
Анализ уравнений (5.14) позволяет выразить элементы 
матрицы в виде
Чаще схемой Холецкого называют описываемый в следующем параграфе, основанный на той же идее способ решения симметричных линейных систем (метод квадратных корней).
(5.15)
(5.16)
(5.17)
Схематично последовательность вычислений элементов обратной матрицы можно изобразить пронумерованными стрелками следующим образом:
При этом стрелка 1 означает, что фиксируем 
и ведем счет по формулам (5.15), (5.16) при 
; стрелка 2 – счет по формуле (5.17) при 
и 
и т. д.
