Как мы видели, получить LU-разложение для произвольной квадратной невырожденной матрицы A удается не всегда. Требуется необращение в нуль в процессе вычислений её ведущих элементов. Сложности могут возникать и тогда, когда эти элементы не равны нулю, но близки к нему. Поэтому в прикладных задачах вместо LU-разложений чаще используются так называемые LUP-разложения A: P×A=L× U, где L и U имеют описанную ранее структуру, а P - матрица перестановок, у которой в каждой строке и каждом столбце по одному элементу, равному единице, а остальные элементы равны нулю. Заметим, что матрица P×A получается из A перестановкой строк, а A×P - перестановкой столбцов. Далее, определитель P равен ± 1,  P^-1=P^T и произведение двух матриц перестановки P и Q снова является матрицей перестановки.

Для получения LUP-разложения используют одну из модификаций метода Гаусса исключения неизвестных. Ядром её, как и для LU-разложения, остаются декомпозиционные преобразования (2)-(4), но каждому рекурсивному шагу предшествует операция перестановки местами двух строк соответствующей матрицы, обеспечивающая получение ненулевых ведущих элементов.

Опишем подробнее процесс LUP-разложения, то есть нахождения по A трех матриц L, U и P. Пусть наибольший по модулю элемент нулевого столбца находится в строке с номером k. Если таких номеров несколько, то возьмем наименьший из них. Поменяем местами строки 0 и k. Эта операция равносильна умножению A слева на матрицу перестановки Q, получаемую из единичной матрицы по правилам:

Q := E(n), Q_0,0 := 0, Q_k,k_,k := 0, Q_k,0 := 1, Q_0,k := 1                                    (6)

Теперь для матрицы B = Q×A [ B = (B_i,j) (i, j = 0 .. n-1) ] можно провести декомпозиционный шаг (2), не опасаясь деления на нуль:

                                   (7)

Дополнение Шура A₁ = D - v × m / B_0,0 является невырожденной матрицей размера (n-1)´(n-1), ибо в противном случае вырожденной оказалась бы матрица B, а значит, и A. По индуктивному предположению построим для A₁ LUP-разложение:

P₁×( D - v × m / B_0,0) = L₁U₁,                                                  (8)

где P₁, L₁ и U₁ имеют размеры (n-1)´(n-1) и, кроме того, L₁ - нижняя треугольная матрица с единицами на главной диагонали, U₁ - верхняя треугольная матрица, P₁ - матрица перестановки.

Рассмотрим матрицу перестановки такого вида:

.                                                               (9)

Имеем

Здесь в последней строке преобразований введены обозначения:

                                           (10)

Поскольку L₁ - нижняя треугольная матрица с единицами на главной диагонали, а U₁ - верхняя треугольная матрица, то соответствующую структуру имеют L и U. Тем самым получено конструктивное доказательство возможности LUP-разложения всякой квадратной невырожденной матрицы A.

адача 2. LUP-разложение. Составить рекурсивную программу-функцию, находящую LUP-разложение для невырожденных квадратных матриц A размером n´n. При неудаче функция должна возвращать пользовательское сообщение об ошибке.

Решение. Воспользуемся описанным выше модифицированным методом Гаусса. В качестве базы рекурсии может быть взят случай n=0, при котором задача решается очевидным способом: L=id, U=A_0,0×id, P=id. Далее, соотношения (6)-(10) задают правило декомпозиции. Рекурсивная функция LUP(A) полностью построена именно на этих соображениях. Результат вычислений, если это не сообщение об ошибке, выводится в виде составного массива - вектора c матричными компонентами L, U и P.

                        (11)

Контрольный пример.

Замечание.