LU-разложение: оптимизация решения систем линейных уравнений

Суть факторизации матриц

Теорема об LU-разложении утверждает, что квадратную матрицу A (при соблюдении определенных условий) можно представить в виде произведения двух матриц: A = L * U. Здесь L (Lower) — это нижнетреугольная матрица, на главной диагонали которой стоят единицы, а все элементы выше диагонали равны нулю. U (Upper) — это верхнетреугольная матрица, у которой все элементы ниже главной диагонали строго равны нулю. Матрица U фактически является тем самым ступенчатым видом, который получается в конце прямого хода метода Гаусса. А матрица L бережно хранит в себе все коэффициенты (множители), с помощью которых мы обнуляли элементы под главной диагональю в процессе гауссовых преобразований строк.

Зачем нужно разлагать матрицу?

Главное преимущество LU-разложения проявляется тогда, когда нам нужно решить множество СЛАУ с одной и той же матрицей коэффициентов A, но с разными векторами свободных членов B. Если использовать обычный метод Гаусса, нам пришлось бы повторять весь трудоемкий процесс приведения к ступенчатому виду (требующий кубического времени, O(n^3) операций) для каждого нового вектора B. С помощью LU-разложения мы выполняем тяжелую операцию факторизации матрицы A только один раз. После этого решение системы AX = B превращается в решение двух простейших систем: LY = B и UX = Y. Поскольку матрицы L и U являются треугольными, эти системы решаются мгновенной прямой и обратной подстановкой (за квадратичное время, O(n^2) операций). При тысячах различных векторов B экономия времени становится астрономической.

Проблема нулевых ведущих элементов и PLU-разложение

Классическое LU-разложение существует не всегда. Если в процессе исключения на главной диагонали появляется ноль (или число, очень близкое к нулю), алгоритм застопорится из-за деления на ноль или приведет к катастрофическому росту вычислительной ошибки. Чтобы избежать этого, алгоритм модернизируют с помощью стратегии частичного выбора ведущего элемента (pivoting). На каждом шаге алгоритм ищет в текущем столбце наибольший по модулю элемент и переставляет строки так, чтобы этот элемент оказался на диагонали. Математически эти перестановки записываются с помощью специальной матрицы перестановок P. В результате получается надежное PLU-разложение: P * A = L * U, которое существует для абсолютно любой невырожденной квадратной матрицы и отличается высочайшей вычислительной стабильностью.

Разложение Холецкого для симметричных матриц

Существует крайне важный частный случай LU-разложения, применяемый для симметричных и положительно определенных матриц (которые сплошь и рядом встречаются в задачах физики, машинном обучении и статистике). Французский математик Андре-Луи Холецкий доказал, что для таких матриц разложение можно сделать еще более элегантным: A = L * L^T. То есть верхнетреугольная матрица является просто транспонированной версией нижнетреугольной матрицы L. Разложение Холецкого не требует перестановок строк, оно в два раза быстрее классического LU-разложения и потребляет в два раза меньше оперативной памяти. Именно метод Холецкого лежит в основе алгоритмов фильтра Калмана и решения нормальных уравнений в методе наименьших квадратов.