Введите квадратную матрицу, откройте вкладку Разложения и нажмите LU(A). Поскольку ответ — пара матриц, а не одна, он целиком живёт в панели пошагового решения, которая открывается сама и в конце показывает L и U рядом. Cholesky(A) находится на той же вкладке — для симметричного случая, разобранного ниже.
Что представляют собой множители
LU записывает A = L·U, где L нижнетреугольная, а U верхнетреугольная. Ни в одной из них нет ничего загадочного: U — это в точности ступенчатый вид, который даёт метод Гаусса, а L хранит множители, использованные по дороге. Одно приведение даёт обе.
Разобранный пример
| 4 | 3 |
| 6 | 3 |
| 1 | 0 |
| 3/2 | 1 |
| 4 | 3 |
| 0 | −3/2 |
Число 3/2 в L — это множитель, обнуливший 6 под ведущим элементом. Заметьте, что определитель теперь достаётся даром: перемножьте диагональ U и получите 4 · (−3/2) = −6, умноженное на −1 за каждую выполненную перестановку строк.
Ради чего это делается
Разложение можно использовать повторно. Решить Ax = b с нуля стоит примерно n³/3 операций. Когда L и U уже есть, каждая новая правая часть стоит всего n²: решите Ly = b прямым ходом, затем Ux = y обратным. Если вы решаете одну и ту же систему для многих векторов b — обычное дело в инженерных расчётах и моделировании — экономия огромна. Для матрицы 100×100 и пятидесяти правых частей это одно разложение плюс пятьдесят дешёвых проходов вместо пятидесяти полных приведений.
Прямой и обратный ход на конкретных числах
Возьмите загруженную выше матрицу 3×3. Одно приведение даёт оба множителя:
| 2 | 1 | 1 |
| 4 | −6 | 0 |
| −2 | 7 | 2 |
| 1 | 0 | 0 |
| 2 | 1 | 0 |
| −1 | −1 | 1 |
| 2 | 1 | 1 |
| 0 | −8 | −2 |
| 0 | 0 | 1 |
Элементы L — это в точности множители, применённые при приведении: 2 обнулил 4, −1 обнулил −2, а −1 убрал остаток во втором столбце. Теперь решим Ax = b при b = (4, −2, 7). Сначала Ly = b, сверху вниз, где каждая строка сразу даёт новое значение, потому что справа от неё всё нулевое:
y₁ = 4; затем 2·4 + y₂ = −2, значит y₂ = −10; затем −4 + 10 + y₃ = 7, значит y₃ = 1.
Далее Ux = y, снизу вверх: x₃ = 1; затем −8x₂ − 2 = −10, значит x₂ = 1; затем 2x₁ + 1 + 1 = 4, значит x₁ = 1. Решение — (1, 1, 1), полученное без единого деления на что-либо, кроме диагонального элемента. Определитель достаётся из тех же множителей: 2 · (−8) · 1 = −16.
Выбор главного элемента
Не всякая матрица допускает простое A = L·U: ноль в позиции ведущего элемента ломает разложение. Выход — матрица перестановок, дающая P·A = L·U. На практике выбор главного элемента применяют в любом случае, потому что взятие наибольшего доступного ведущего элемента держит ошибки округления под контролем. Разложение единственно после фиксации соглашения; этот калькулятор использует соглашение Дулиттла, ставящее единицы на диагональ L.
Холецкий: симметричный случай
Если A симметрична и положительно определена, она раскладывается как A = L·Lᵀ — квадратный корень для матриц, требующий лишь одного треугольного множителя. Симметричность означает A = Aᵀ; положительная определённость означает, что каждое собственное значение больше нуля. Звучит ограничительно, но такие матрицы встречаются повсюду: матрицы ковариации, матрицы Грама, нормальные уравнения метода наименьших квадратов и матрицы жёсткости в методе конечных элементов симметричны и положительно определены по построению.
| 4 | 2 |
| 2 | 5 |
| 2 | 0 |
| 1 | 2 |
| 2 | 1 |
| 0 | 2 |
Каждый диагональный элемент L — это квадратный корень (здесь √4 = 2 и √(5 − 1²) = 2), и поэтому метод требует, чтобы подкоренное выражение оставалось положительным. Это требование и есть положительная определённость, что превращает алгоритм в тест: если разложение дошло до конца, матрица положительно определена; если под корнем встретилось неположительное число — нет. Холецкий примерно вдвое быстрее LU, занимает вдвое меньше памяти и устойчив без выбора главного элемента — поэтому решатели сначала проверяют симметрию и берут его при любой возможности.
Частые ошибки
- Считать, что раскладывается любая матрица. Ноль в позиции ведущего элемента ломает простое LU. Выход — матрица перестановок:
P·A = L·U. - Применять Холецкого к несимметричной матрице. A = L·Lᵀ симметрична по построению, поэтому у несимметричного входа такого разложения нет. Берите LU.
- Считать, что достаточно симметрии. Симметричная матрица с отрицательным собственным значением неопределённая и сорвётся посреди алгоритма.
- Ждать целых множителей. Диагональ Холецкого содержит квадратные корни, поэтому L обычно иррациональна, даже когда A целочисленная.
- Забывать перестановки строк в определителе. Каждая меняет его знак.