LU-разложение по шагам

Разложение матрицы на нижнюю и верхнюю треугольные части, почему это быстрее повторного исключения и как разложение Холецкого уточняет метод.

LU-разложение представляет квадратную матрицу произведением нижней треугольной матрицы на верхнюю: A = L·U. Множители получаются прямо из метода Гаусса — U — это ступенчатый вид, а L хранит множители, с которыми вы к нему пришли.

Зачем это нужно

Потому что разложение можно использовать повторно. Решение Ax = b с нуля стоит около n³/3 операций. Когда L и U уже есть, каждая новая правая часть обходится всего в n²: сначала Ly = b прямой подстановкой, затем Ux = y обратной. При десятках правых частей выигрыш огромен.

Определитель тоже достаётся бесплатно — это произведение диагонали U, умноженное на −1 за каждую выполненную перестановку строк.

Выбор ведущего элемента

Не всякая матрица допускает простое A = L·U: ноль на месте ведущего элемента ломает метод. Решение — матрица перестановок, то есть P·A = L·U. На практике перестановки применяют в любом случае, потому что выбор наибольшего доступного ведущего элемента держит ошибки округления под контролем.

Холецкий: симметричный случай

Если A симметрична и положительно определена, она раскладывается как A = L·Lᵀ — достаточно одного треугольного множителя. Разложение Холецкого примерно вдвое быстрее LU и численно очень устойчиво, поэтому оно доминирует в оптимизации, методе наименьших квадратов и статистике (ковариационные матрицы симметричны и положительно определены по построению).

Если алгоритм в какой-то момент требует корень из отрицательного числа, матрица не была положительно определённой — так что Холецкий заодно служит проверкой этого свойства.