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

LU-разложение (LU-декомпозиция, LU-факторизация) — это представление квадратной матрицы \(A\) в виде произведения двух матриц: нижней треугольной матрицы \(L\) (от англ. lower) и верхней треугольной матрицы \(U\) (от англ. upper). Формально это записывается как \(A = LU\). LU-разложение является одним из фундаментальных методов линейной алгебры, широко применяемым для решения систем линейных уравнений, вычисления определителей и обращения матриц. В отличие от метода Гаусса, который приводит матрицу к ступенчатому виду, LU-разложение позволяет выполнять эти операции более эффективно при многократных вычислениях с одной и той же матрицей.

¶Определение и условия существования

Пусть \(A\) — квадратная матрица размера \(n \times n\). LU-разложением называется пара матриц \(L\) и \(U\) таких, что:

• \(L\) — нижняя треугольная матрица с единицами на главной диагонали (нормированная форма);
• \(U\) — верхняя треугольная матрица;
• \(A = LU\).

LU-разложение существует не для всех матриц. Необходимым и достаточным условием существования является то, что все главные миноры матрицы \(A\) отличны от нуля. Если матрица \(A\) невырождена (det \(A \neq 0\)), то LU-разложение существует и единственно при условии, что диагональные элементы \(L\) равны 1. Если какой-либо главный минор равен нулю, то разложение в классической форме невозможно, но может быть выполнено с перестановками строк (см. LUP-разложение).

¶История

Идея разложения матрицы на треугольные множители восходит к работам Гаусса по методу исключения (начало XIX века). Однако систематическое изложение LU-разложения как самостоятельного метода связано с именем Алана Тьюринга, который в 1948 году ввёл понятие «треугольного разложения» в контексте численных методов. В 1950-х годах метод был развит в работах Джона фон Неймана и Германа Гольдштейна, а также в трудах советских математиков, таких как И. С. Березин и Н. П. Жидков. С развитием вычислительной техники LU-разложение стало стандартным алгоритмом в пакетах линейной алгебры (LAPACK, MATLAB, NumPy).

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

¶Прямой ход метода Гаусса

Наиболее распространённый способ получения LU-разложения — это модификация метода Гаусса. В процессе прямого хода исключения переменных матрица \(A\) приводится к верхней треугольной форме \(U\). При этом коэффициенты, используемые для обнуления элементов ниже главной диагонали, записываются в матрицу \(L\). Алгоритм для матрицы \(A\) размером \(n \times n\):

1. Для \(k = 1\) до \(n-1\):

• Для \(i = k+1\) до \(n\):
• Вычислить множитель \(l_{ik} = a_{ik} / a_{kk}\) (при условии \(a_{kk} \neq 0\)).
• Записать \(l_{ik}\) в матрицу \(L\) (на позицию \((i, k)\)).
• Для \(j = k\) до \(n\):
• \(a_{ij} = a_{ij} - l_{ik} \cdot a_{kj}\).

После завершения цикла матрица \(A\) становится верхней треугольной — это и есть \(U\). Матрица \(L\) заполняется единицами на главной диагонали и множителями \(l_{ik}\) ниже диагонали.

¶Пример

Рассмотрим матрицу \(A = \begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 6 & 5 & 4 \end{pmatrix}\).

• Шаг 1 (\(k=1\)): \(l_{21} = 4/2 = 2\), \(l_{31} = 6/2 = 3\). Вычитаем: \(a_{22} = 3 - 2 \cdot 1 = 1\), \(a_{23} = 3 - 2 \cdot 1 = 1\); \(a_{32} = 5 - 3 \cdot 1 = 2\), \(a_{33} = 4 - 3 \cdot 1 = 1\).
• Шаг 2 (\(k=2\)): \(l_{32} = 2/1 = 2\). Вычитаем: \(a_{33} = 1 - 2 \cdot 1 = -1\).

Получаем \(U = \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & -1 \end{pmatrix}\), \(L = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 2 & 1 \end{pmatrix}\). Проверка: \(LU = A\).

¶Виды LU-разложения

¶LUP-разложение (с перестановками)

Если матрица \(A\) не удовлетворяет условию существования LU-разложения (например, первый элемент равен нулю), применяется LUP-разложение: \(PA = LU\), где \(P\) — матрица перестановок (переставляющая строки). Это эквивалентно выполнению частичного выбора ведущего элемента в методе Гаусса. LUP-разложение существует для любой невырожденной матрицы.

¶Разложение Холецкого

Для симметричных положительно определённых матриц существует частный случай — разложение Холецкого: \(A = LL^T\), где \(L\) — нижняя треугольная матрица с положительными диагональными элементами. Этот метод в два раза быстрее классического LU-разложения и устойчивее.

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

Для симметричных матриц, не обязательно положительно определённых, используется LDL-разложение: \(A = LDL^T\), где \(L\) — нижняя треугольная с единицами на диагонали, а \(D\) — диагональная матрица. Это обобщение разложения Холецкого.

¶Применение

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

LU-разложение наиболее часто используется для решения систем вида \(Ax = b\). После факторизации \(A = LU\) система сводится к двум треугольным системам:

1. \(Ly = b\) — решается прямой подстановкой (сверху вниз).
2. \(Ux = y\) — решается обратной подстановкой (снизу вверх).

Если требуется решить несколько систем с одной и той же матрицей \(A\), но разными правыми частями \(b\), LU-разложение выполняется один раз, что значительно экономит время.

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

Определитель матрицы \(A\) равен произведению диагональных элементов матрицы \(U\) (с учётом знака от перестановок в LUP-разложении): \(\det(A) = \prod_{i=1}^n u_{ii}\). Если использовалась матрица перестановок \(P\), то \(\det(A) = \det(P) \cdot \prod u_{ii}\), где \(\det(P) = \pm 1\) в зависимости от чётности перестановки.

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

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

¶Численные методы

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

¶Вычислительная сложность

Для матрицы размера \(n \times n\) прямое LU-разложение требует около \(\frac{2}{3}n^3\) операций с плавающей точкой (флопов). Решение треугольных систем требует \(O(n^2)\) операций. Таким образом, LU-разложение является асимптотически оптимальным методом для плотных матриц. Для разреженных матриц существуют специализированные модификации (например, разложение с использованием профильной структуры).

¶Устойчивость и выбор ведущего элемента

Классическое LU-разложение без перестановок может быть численно неустойчивым, если ведущие элементы \(a_{kk}\) малы. Для повышения устойчивости применяется частичный выбор ведущего элемента (перестановка строк так, чтобы наибольший по модулю элемент в столбце оказался на диагонали). Это приводит к LUP-разложению. Полный выбор ведущего элемента (перестановка строк и столбцов) даёт ещё большую устойчивость, но требует больше вычислений. В современных библиотеках (LAPACK) используется частичный выбор.

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

LU-разложение является частным случаем более общего QR-разложения (ортогональная матрица \(Q\) и верхняя треугольная \(R\)). QR-разложение более устойчиво, но требует вдвое больше операций. Для симметричных положительно определённых матриц предпочтительнее разложение Холецкого. В контексте решения систем с ленточными матрицами используется LU-разложение с сохранением ленточной структуры (например, метод прогонки для трёхдиагональных матриц).

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

• LAPACK (Linear Algebra PACKage) — библиотека на Фортране, предоставляющая подпрограммы DGETRF (LU-разложение с частичным выбором) и DGETRS (решение систем).
• MATLAB — функция lu(A) возвращает матрицы \(L\), \(U\) и \(P\).
• NumPy (Python) — функция numpy.linalg.lu().
• SciPy — функция scipy.linalg.lu().
• Julia — функция lu(A).
• R — функция lu() из пакета Matrix.
• GNU Octave — функция lu(A).

¶Интересные факты

• LU-разложение является основой для метода Гаусса — Жордана, используемого для нахождения обратной матрицы.
• В 1960-х годах советский математик В. В. Воеводин разработал эффективные алгоритмы LU-разложения для ЭВМ с ограниченной памятью.
• Для матриц большой размерности (более 10 000) LU-разложение может быть ускорено с помощью блочных алгоритмов, использующих кэш-память процессора.
• В квантовых вычислениях существуют алгоритмы, имитирующие LU-разложение для решения квантовых систем.

¶Источники

1. Тьюринг А. М. «О методах решения систем линейных уравнений» (1948).
2. Голуб Дж., Ван Лоун Ч. «Матричные вычисления» (3-е издание, 1996).
3. Березин И. С., Жидков Н. П. «Методы вычислений» (том 1, 1966).
4. Деммель Дж. «Вычислительная линейная алгебра» (1997).
5. LAPACK User's Guide (3rd edition, 1999).
6. Воеводин В. В. «Вычислительные основы линейной алгебры» (1977).