Метод Гаусса или LU-разложение матрицы: когда что использовать

Курсовая по численным методам: матрица 100×100 одна, а правых частей десять — шаги неявной схемы, итерации Ньютона, варианты нагрузки. Одногруппник десять раз запускает метод Гаусса с нуля. Работает. Медленно, но работает — и вопрос преподавателя «сколько операций потрачено зря?» остаётся без ответа. Ответ некомфортный: почти 90% арифметики — повторённое исключение, которое можно было оплатить один раз.

Разложим оба подхода по одному каркасу: где живут множители исключения, что такое прямой и обратный ход, сколько стоит каждая стратегия при n = 10 и n = 100, зачем нужен выбор ведущего элемента и когда Гаусса достаточно. Теория — в уроках СЛАУ методом Гаусса и численные методы СЛАУ; слова — термины метод Гаусса и система линейных уравнений.

Гаусс — процесс, LU — продукт#

Метод Гаусса — рецепт: исключить x₁ из всех уравнений ниже первого, затем x₂ и так далее, после чего подняться обратным ходом. LU-разложение — не рецепт, а результат: матрица A представлена произведением треугольных множителей —

Честная связь между ними проста: Гаусс без перестановок строк — это и есть построение LU. Множитель $l_{ik}=a_{ik}/a_{kk}$, на который умножается i-я строка при обнулении, записывается ровно на место обнуляемого элемента. Прямой ход закончился — нижний треугольник заполнен множителями, верхний — итогом исключения. Факторизация — тот же прямой ход, которому велели всё запомнить по дороге. Поэтому и цена общая: n³/3 умножений-делений на исключение плюс n² на обратный ход за систему.

Мини-пример стоит двух абзацев теории. Возьмём A из двух строк: первый шаг исключения делит вторую строку на ведущий 2 и вычитает первую — множитель l₂₁ = 4/2 = 2.

Решение системы распадается на два треугольных хода:

Уточнение о подсчёте: во всей статье считаются умножения и деления; вместе со сложениями цифры примерно удваиваются (2n³/3 и 2n² операций), но каждое соотношение остаётся прежним. В учебниках и в оценках производительности библиотек встречаются обе конвенции — смотрите, что именно посчитано.

Многие правые части: где LU окупается#

Сценарий «одна матрица, много столбцов b» — не экзотика. Неявные схемы для уравнений математической физики на каждом шаге по времени решают систему с одной и той же матрицей; итерации Ньютона обновляют Якобиан редко, а системы решают на каждой итерации; метод наименьших квадратов при переборе моделей; серийные расчёты в проектировании. Вопрос каждый раз один: платить ли за исключение повторно?

Порог окупаемости ниже, чем кажется: уже вторая правая часть делает LU выгодным. При n = 10 это 533 операции против 867 — экономия 38%. Дальше разрыв только растёт:

Масштаб виден в последней строке: при n = 1000 десятая правая часть через LU стоит миллион операций — 0,3% от повторного прогона Гаусса. А подстановки даже при десяти правых частях занимают лишь 23% всей работы LU при n = 100. Исключение доминирует в бюджете — пока его не оплатили раз и навсегда.

PA = LU: перестановки и устойчивость#

В чистом виде A = LU существует не всегда: если какой-то угловой минор нулевой, на очередном шаге ведущий элемент обратится в ноль и исключение встанет. Простой контрпример — матрица с нулём в левом верхнем углу и единицами на антидиагонали. Есть причина серьёзнее нуля: делить на крошечный ведущий опасно, ошибки округления вспухают. Реализация поступает радикально: перед каждым шагом строки переставляются так, чтобы наверху оказался наибольший по модулю элемент столбца. Это частичный выбор ведущего элемента.

С перестановками факторизуется не сама A, а PA, и решение Ax = b идёт двумя ходами: Ly = Pb, затем Ux = y. О устойчивости — без сказок: частичный выбор сдерживает рост промежуточных элементов, и на практике метод надёжен, катастрофические контрпримеры экзотичны. Но если матрица плохо обусловлена, не спасёт никакая факторизация: ошибка правой части усиливается примерно в число cond(A) раз — это свойство задачи, а не алгоритма. Разбор погрешностей — в уроке источники погрешностей, точные формулировки — в термине число обусловленности.

Симметричным положительно определённым матрицам положена скидка — разложение Холецкого:

Холецкий дорабатывает LU наполовину: корни из диагонали втягиваются в треугольный множитель, перестановки не нужны вовсе. Такие матрицы постоянно возникают в методе наименьших квадратов и в конечноэлементных расчётах — там выбор очевиден.

Обращение матрицы и когда Гаусса достаточно#

Обращение — это n систем с единичными правыми частями. Через LU: n³/3 на факторизацию и n подстановок по n² — итого 4n³/3. При n = 100 это 1 333 333 умножений против 343 333 на одно решение — почти вчетверо дороже. Отсюда правило: явная A⁻¹ нужна, только когда нужна именно она — анализ чувствительности, формулы для дисперсий оценок, непредсказуемый порядок правых частей. Решать Ax = b умножением на готовую обратную — расточительство: предварительная цена обращения обнуляет выгоду. Тонкости — в уроке обратная матрица.

Когда достаточно Гаусса? Список короткий и честный: одна система; ручной счёт до четвёртого порядка; разовая проверка; учебные задачи, где важно увидеть исключение глазами. Бонусы прямого хода бесплатны: det A равен произведению диагональных элементов U со знаком от числа перестановок (детали — в уроке определители), а ранг читается по ненулевым элементам той же диагонали — родство с уроком ранг матрицы прямое.

Границы применимости тоже полезно знать. Огромные разреженные системы от сеточных расчётов при исключении обрастают новыми ненулевыми элементами, память кончается — там начинается территория итерационных методов. А правило Крамера с его n + 1 определителями (метод Крамера, подробности — в уроке Крамер и матричный метод) проигрывает исключению по трудоёмкости уже при n = 4.

1. 1
   Шаг 1: решить систему 3×3 методом Гаусса, сохраняя все промежуточные матрицы.
2. 2
   Шаг 2: выписать множители l₂₁, l₃₁, l₃₂ — убедиться, что это в точности числа, на которые умножались строки.
3. 3
   Шаг 3: собрать L и U, перемножить и сверить с A: факторизация сошлась.
4. 4
   Шаг 4: решить Ly = b и Ux = y; сравнить с ответом Гаусса — совпадёт до последнего знака.
5. 5
   Шаг 5: взять второй столбец b и повторить только треугольные ходы. Исключение не повторяется — вот и вся экономия LU в миниатюре.

Дальше по теме: теория — СЛАУ методом Гаусса, матрицы и операции и численные методы СЛАУ; соседние сюжеты — обратная матрица, определители и ранг матрицы. Практика — тренажёр матриц, тренажёр СЛАУ, разбор задач по СЛАУ и задачи на СЛАУ. О выборе между дисциплинами шире — сравнение матанализ или линейная алгебра.