LUP-разложение¶

LUP-разложение (также LUP-декомпозиция, от англ. Lower, Upper, Permutation) — это представление квадратной невырожденной матрицы в виде произведения трёх матриц: нижней треугольной (L), верхней треугольной (U) и матрицы перестановок (P). В отличие от LU-разложения, LUP-разложение существует для любой невырожденной матрицы, даже если её главные миноры равны нулю, и широко применяется в вычислительной математике для решения систем линейных уравнений, обращения матриц и вычисления определителей.

¶Определение и формальная запись

Пусть \(A\) — квадратная матрица размера \(n \times n\) с ненулевым определителем (\(\det A \neq 0\)). LUP-разложением называется представление:

\[ P A = L U, \]

где:

• \(P\) — матрица перестановок (получается из единичной матрицы перестановкой строк);
• \(L\) — нижняя треугольная матрица с единицами на главной диагонали;
• \(U\) — верхняя треугольная матрица.

Эквивалентная форма записи: \(A = P^{-1} L U = P^{T} L U\), так как матрица перестановок ортогональна (\(P^{-1} = P^{T}\)).

¶История

Идея разложения матрицы на треугольные множители восходит к работам Карла Фридриха Гаусса (начало XIX века), который использовал метод исключения для решения систем линейных уравнений. Однако формальное LU-разложение в современном виде было предложено в 1940-х годах Аланом Тьюрингом в контексте численных методов. Необходимость введения матрицы перестановок (P) возникла из-за того, что при прямом ходе метода Гаусса без выбора главного элемента может возникнуть деление на ноль, если ведущий элемент равен нулю. LUP-разложение с частичным выбором главного элемента (перестановка строк) стало стандартным алгоритмом в линейной алгебре, реализованным в большинстве библиотек численных вычислений (LAPACK, MATLAB, NumPy).

¶Алгоритм построения

¶Частичный выбор главного элемента

На каждом шаге \(k\) (от 1 до \(n-1\)) алгоритм выполняет следующие действия:

1. Поиск ведущего элемента: среди элементов \(a_{ik}\) для \(i = k, k+1, \dots, n\) находится максимальный по модулю. Если он равен нулю, матрица вырождена, и разложение невозможно.
2. Перестановка строк: строки \(k\) и \(p\) (где \(p\) — индекс найденного элемента) меняются местами. Это фиксируется в матрице перестановок \(P\).
3. Исключение: для всех строк \(i > k\) вычисляется множитель \(l_{ik} = a_{ik} / a_{kk}\), после чего из строки \(i\) вычитается строка \(k\), умноженная на \(l_{ik}\). Элементы \(a_{ik}\) заменяются на \(l_{ik}\) (они образуют поддиагональную часть матрицы \(L\)).

После завершения прямого хода верхняя треугольная часть полученной матрицы становится матрицей \(U\), а поддиагональные элементы (с единичной диагональю) — матрицей \(L\).

¶Полный выбор главного элемента

В более сложной версии (LUP с полным выбором) переставляются не только строки, но и столбцы, что даёт разложение вида \(P A Q = L U\), где \(Q\) — ещё одна матрица перестановок. Это повышает численную устойчивость, но требует дополнительных вычислительных затрат.

¶Свойства

• Существование: LUP-разложение существует для любой невырожденной матрицы. Для вырожденных матриц разложение может не существовать или быть неединственным.
• Единственность: при фиксированной стратегии выбора главного элемента разложение единственно. Матрица \(L\) всегда имеет единицы на диагонали, а диагональные элементы \(U\) могут быть любыми ненулевыми.
• Вычислительная сложность: алгоритм требует \(O(n^3)\) арифметических операций, что совпадает с LU-разложением без перестановок.
• Численная устойчивость: частичный выбор главного элемента значительно улучшает устойчивость по сравнению с LU-разложением без перестановок, особенно для матриц с малыми ведущими элементами.

¶Применение

¶Решение систем линейных уравнений

Для системы \(A x = b\) LUP-разложение позволяет решить её в три этапа:

1. Найти разложение \(P A = L U\).
2. Решить систему \(L y = P b\) (прямая подстановка).
3. Решить систему \(U x = y\) (обратная подстановка).

Этот метод — основа большинства прямых решателей (direct solvers) в вычислительной математике.

¶Вычисление определителя

Определитель матрицы \(A\) вычисляется как произведение диагональных элементов матрицы \(U\), умноженное на знак перестановки (\(\det P = \pm 1\)):

\[ \det A = \det(P^{-1}) \det(L) \det(U) = (\pm 1) \cdot 1 \cdot \prod_{i=1}^{n} u_{ii}. \]

¶Обращение матрицы

Обратная матрица \(A^{-1}\) может быть найдена путём решения \(n\) систем \(A x_i = e_i\) (где \(e_i\) — столбцы единичной матрицы) с использованием LUP-разложения. Это эффективнее, чем явное вычисление обратной по формуле Крамера.

¶Другие задачи

• Вычисление ранга матрицы (через количество ненулевых диагональных элементов \(U\)).
• Решение переопределённых систем (метод наименьших квадратов) — в комбинации с QR-разложением.
• Предобуславливание в итерационных методах решения систем.

¶Пример

Рассмотрим матрицу \(A = \begin{pmatrix} 0 & 2 \\ 1 & 1 \end{pmatrix}\). На первом шаге ведущий элемент \(a_{11}=0\), поэтому требуется перестановка строк: меняем местами первую и вторую строки. Получаем \(P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\), \(P A = \begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix}\). Далее выполняем исключение: множитель \(l_{21} = 0/1 = 0\). В результате:

\[ L = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad U = \begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix}. \]

Проверка: \(P A = L U\) — верно.

¶Связь с другими разложениями

• LU-разложение — частный случай LUP, когда \(P = I\) (единичная матрица). Существует только для матриц, у которых все главные миноры не равны нулю.
• QR-разложение (ортогональная и верхняя треугольная матрицы) — альтернатива для решения систем, более устойчивая, но требующая больше операций.
• Разложение Холецкого — для симметричных положительно определённых матриц, является частным случаем LU без перестановок.

¶Реализации в программном обеспечении

LUP-разложение реализовано в большинстве систем компьютерной алгебры и численных библиотек:

• LAPACK (функции dgetrf и sgetrf) — стандартный интерфейс для Фортрана и C.
• MATLAB — функция lu (с опцией 'vector' для вывода вектора перестановок).
• NumPy (Python) — scipy.linalg.lu и numpy.linalg.lu (в NumPy 2.0+).
• Julia — функция lu из пакета LinearAlgebra.
• Wolfram Mathematica — LUDecomposition.

¶Ограничения и альтернативы

• LUP-разложение требует квадратной невырожденной матрицы. Для прямоугольных или вырожденных матриц используются QR-разложение или сингулярное разложение (SVD).
• Для очень больших разреженных матриц (например, возникающих в методе конечных элементов) прямое LUP-разложение может быть неэффективным из-за заполнения (fill-in); применяются итерационные методы или специальные перестановки для минимизации заполнения (например, метод вложенных сечений).

¶Источники

1. Тьюринг, А. М. «Rounding-off errors in matrix processes». — The Quarterly Journal of Mechanics and Applied Mathematics, 1948.
2. Голуб, Дж., Ван Лоун, Ч. «Матричные вычисления». — М.: Мир, 1999.
3. Деммель, Дж. «Вычислительная линейная алгебра». — М.: Мир, 2001.
4. LAPACK Users' Guide, 3rd ed. — SIAM, 1999.
5. Strang, G. «Linear Algebra and Its Applications», 4th ed. — Brooks/Cole, 2006.