Метод Гаусса 🪜

В прошлом уроке ты получил полную теорию систем линейных уравнений: матричную форму $Ax = b$, расширенную матрицу $[A \mid b]$, теорему Кронекера — Капелли, разделение переменных на базисные и свободные, понятия общего и частного решения. Теория отвечает на вопрос «сколько решений у этой системы». Но она не отвечает на второй, куда более приземлённый вопрос: как эти решения найти.

Разница здесь примерно как между «у этого уравнения есть корень на отрезке $[1, 2]$, потому что функция меняет знак» и «корень равен $1{,}3247$». Первое — теорема существования, второе — результат работы алгоритма. Теорема Кронекера — Капелли говорит, что решение есть; метод Гаусса его выдаёт. Причём — и это важнее всего — выдаёт его тем же самым действием, которым мы вычисляли ранг: приведением расширенной матрицы к ступенчатому виду. Один проход элементарных преобразований одновременно и определяет ранги обеих матриц, и раскладывает решение по полочкам.

Метод Гаусса — это не «один из способов» решения систем. Это тот самый способ, которым системы решаются на практике: и на бумаге, когда неизвестных три, и в LAPACK, когда неизвестных сто тысяч. Правило Крамера, с которым ты познакомишься в следующем уроке, красивее в записи, но неприменимо к системам больше $4 \times 4$. Матричный метод $x = A^{-1}b$ концептуально прозрачен, но требует лишней работы. Метод Гаусса — единственный из школьно-университетских методов, который дожил до реальных вычислений и лежит внутри numpy.linalg.solve, scipy.linalg.lu, решателей нормальных уравнений в линейной регрессии и почти любого пакета, где вообще встречается матрица.

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

Отдельная большая тема этого урока — системы с параметром. Задача «при каких значениях $a$ система несовместна, при каких имеет единственное решение, а при каких бесконечно много» — самый частый тип задач на контрольных и самый полезный для понимания. Метод Гаусса разбирается с ней элегантно: гоним прямой ход как обычно, а в конце смотрим, при каких значениях параметра ведущий элемент последней строки обращается в ноль. Всё, что нужно, — не поделить случайно на выражение, которое может быть нулём.

Давай разберём алгоритм по шагам, доведём его до автоматизма на трёх десятках задач и заодно поймём, почему за 200 лет никто не придумал ничего принципиально лучше для плотных систем общего вида.

🎯 Ты узнаешь:

• как работает прямой ход метода Гаусса: ведущий элемент, обнуление столбца, аккуратная запись преобразований вида $R_2 \to R_2 - 2R_1$;

• как выполнять обратный ход и получать решение снизу вверх;

• как по ступенчатой матрице мгновенно распознать все три исхода: несовместность, единственное решение, бесконечное множество решений;

• что такое метод Гаусса — Жордана и приведённый ступенчатый вид (RREF), и когда он удобнее обычного обратного хода;

• как решать системы с параметром — полный разбор всех случаев без потери корней;

• почему метод Гаусса стоит примерно $\frac{2}{3}n^3$ операций и что это значит для систем с миллионом неизвестных;

• почему в машинной арифметике порядок строк влияет на ответ и что такое частичный выбор главного элемента;

• где метод Гаусса живёт внутри numpy, scipy и решателей линейной регрессии.

История: откуда это взялось?

Метод, который сегодня носит имя Гаусса, старше своего названия примерно на два тысячелетия. В древнекитайском трактате «Математика в девяти книгах» (Цзю чжан суань шу, составлен около II века до нашей эры) восьмая глава называется «Фан чэн» — буквально «прямоугольные таблицы». В ней разбираются системы из трёх и более линейных уравнений, а решаются они так: коэффициенты выкладываются счётными палочками в прямоугольную таблицу — по сути, матрицу, — а затем столбцы этой таблицы последовательно вычитаются друг из друга, пока в углу не остаётся одна палочка на одну неизвестную. Это в точности прямой ход метода Гаусса, только записанный по столбцам и без единой буквы.

Карл Фридрих Гаусс пришёл к тому же приёму в начале XIX века, и пришёл сугубо практически. В 1801 году итальянский астроном Джузеппе Пиацци обнаружил и вскоре потерял из виду карликовую планету Церера. Двадцатичетырёхлетний Гаусс восстановил её орбиту по нескольким наблюдениям — и прославился. Технически задача сводилась к методу наименьших квадратов, а метод наименьших квадратов сводится к решению системы так называемых нормальных уравнений. Именно для них Гаусс и описал систематическую процедуру исключения неизвестных — в работе Theoria Motus Corporum Coelestium (1809) и последующих трудах по обработке геодезических измерений. Никаких матриц он при этом не использовал: слово «матрица» появится у Сильвестра только в 1850 году, а сама алгебра матриц — у Кэли в 1858-м.

Немецкий геодезист Вильгельм Жордан в «Руководстве по геодезии» (Handbuch der Vermessungskunde, 1888) довёл идею до логического конца: если продолжать исключение не только вниз, но и вверх, обратный ход становится не нужен вовсе — решение читается прямо из матрицы. Так появился метод Гаусса — Жордана. Почти одновременно и независимо ту же схему опубликовал люксембургский математик Бернар-Изидор Клазен. Что характерно, оба были не чистыми математиками, а практиками, которым нужно было обрабатывать сотни измерений вручную.

А название «метод Гаусса» (Gaussian elimination) в современном виде закрепилось совсем недавно — в середине XX века, вместе с появлением ЭВМ. Американский математик Джордж Форсайт и его коллеги в 1950-х годах разбирали, какие численные алгоритмы стоит программировать, и именно тогда исключение по Гауссу получило статус базового алгоритма линейной алгебры. Тогда же Джеймс Уилкинсон провёл его строгий анализ ошибок округления и показал, что без выбора главного элемента метод может катастрофически терять точность, а с частичным выбором — на практике надёжен. Об этом мы отдельно поговорим в конце урока: это тот редкий случай, когда «академическая» деталь напрямую определяет, будет ли твой код выдавать правильные числа.

Прямой ход: превращаем систему в лестницу

Интуиция: исключаем неизвестные по одной

Представь, что у тебя три уравнения с тремя неизвестными и ты решаешь их школьным способом — методом подстановки. Из первого уравнения выражаешь $x$, подставляешь во второе и третье, получаешь два уравнения с $y$ и $z$. Потом из одного из них выражаешь $y$, подставляешь в оставшееся, получаешь одно уравнение с $z$. Решаешь его — и разматываешь всё обратно.

Метод Гаусса — это ровно та же логика, но без выражения неизвестных. Вместо «выразить $x$ и подставить» мы делаем одну операцию: вычитаем из уравнения другое уравнение, умноженное на подходящее число, так, чтобы $x$ сократился. Результат тот же, а записи в разы меньше — потому что уравнения можно записывать не полностью, а только строками коэффициентов.

Ключевая идея, которая делает это законным, была разобрана в прошлом уроке: элементарные преобразования строк не меняют множество решений системы. Разрешены ровно три операции:

• перестановка двух строк (переставили местами два уравнения — система та же);

• умножение строки на ненулевое число (умножили обе части уравнения на 3 — решения не изменились);

• прибавление к одной строке другой, умноженной на число (сложили два уравнения — любое решение исходной пары удовлетворяет и результату).

Каждое из них обратимо, поэтому новая система эквивалентна старой: ни одно решение не потеряется и ни одного лишнего не появится. А значит, можно спокойно «портить» матрицу до тех пор, пока она не станет удобной.

Как это устроено формально

Работаем с расширенной матрицей $[A \mid b]$ — матрицей коэффициентов, к которой справа приписан столбец свободных членов. Каждая строка матрицы — это одно уравнение; вертикальная черта отделяет левые части от правых и никак не участвует в вычислениях, она нужна только для читаемости.

Определение: Ведущий элемент (или пивот, от английского pivot — «опорная точка») очередного шага — это первый ненулевой элемент строки, вокруг которого мы обнуляем весь столбец ниже.

Алгоритм прямого хода:

1. Смотрим на первый столбец. Выбираем в нём ненулевой элемент — он станет ведущим. Если он не в первой строке, меняем строки местами.

2. Для каждой строки ниже вычисляем множитель $m_i = \dfrac{a_{i1}}{a_{11}}$ и делаем преобразование $R_i \to R_i - m_i R_1$. После этого весь первый столбец под ведущим элементом обнулён.

3. Мысленно вычёркиваем первую строку и первый столбец и повторяем процедуру для оставшейся подматрицы: находим ведущий элемент во втором столбце, обнуляем под ним, и так далее.

4. Останавливаемся, когда строки кончились или когда все оставшиеся строки нулевые.

Результат — ступенчатая матрица: в каждой следующей ненулевой строке ведущий элемент стоит правее, чем в предыдущей, а под каждым ведущим элементом только нули.

Запись преобразования обязательно фиксируй в явном виде: $R_3 \to R_3 - 2R_1$ читается как «новая третья строка равна старой третьей минус удвоенная первая». Это не педантизм: 90% ошибок в методе Гаусса — арифметические, и без пометок ты не найдёшь, где именно ошибся. Ещё одна важная деталь: при преобразовании $R_i \to R_i - m R_k$ меняется только строка $R_i$, строка $R_k$ остаётся нетронутой. Если менять обе строки одновременно, можно нечаянно потерять ведущий элемент.

Разбор примеров

Пример 1. Классический прямой ход $3 \times 3$.

Записываем расширенную матрицу:

Шаг 1. Ведущий элемент $a_{11} = 1$ — идеальный вариант, множители получатся целыми. Обнуляем первый столбец: $R_2 \to R_2 - 2R_1$ и $R_3 \to R_3 - R_1$.

Шаг 2. Вторая строка целиком делится на $-5$ — грех не воспользоваться: $R_2 \to -\frac{1}{5}R_2$ даёт $(0, 1, 1 \mid 5)$. Умножение строки на ненулевое число разрешено и сильно упрощает жизнь.

Шаг 3. Обнуляем второй столбец под новым ведущим элементом: $R_3 \to R_3 + 4R_2$.

Прямой ход закончен: матрица ступенчатая, три ведущих элемента (в столбцах 1, 2, 3), количество ведущих элементов совпало с числом неизвестных. Это исход «единственное решение» — обратный ход разберём в следующем разделе, а ответ забегая вперёд: $(1, 2, 3)$.

Пример 2. Ведущий элемент оказался нулём.

В левом верхнем углу ноль. Делить на него нельзя, но это и не тупик: в первом столбце есть другие ненулевые элементы. Меняем первую и вторую строки местами ($R_1 \leftrightarrow R_2$) — это разрешённое элементарное преобразование, и система от него не меняется:

$R_3 \to R_3 - 2R_1$:

$R_3 \to R_3 + \frac{3}{2}R_2$:

Три ведущих элемента, единственное решение. Из последней строки $z = -1$, дальше $2y - 1 = 1 \Rightarrow y = 1$, затем $x + 1 - 3 = 0 \Rightarrow x = 2$. Ответ: $(2, 1, -1)$.

Нулевой ведущий элемент — это штатная ситуация, а не поломка алгоритма. Ноль в углу означает лишь, что переменная $x$ не входит в первое уравнение; порядок уравнений в системе произволен, и мы вправе поставить наверх любое из них. Провал наступает только в одном случае: если весь столбец ниже (включая текущую строку) состоит из нулей. Тогда в этом столбце ведущего элемента нет вообще, соответствующая переменная становится свободной, и мы переходим к следующему столбцу — но об этом в разделе про три исхода.

Пример 3. Прямой ход $4 \times 4$ с дробями.

Ведущий элемент $2$ даст дробные множители $\frac12$. Хитрость, экономящая нервы: переставим строки так, чтобы наверху стояла строка с единицей. $R_1 \leftrightarrow R_2$:

$R_2 \to R_2 - 2R_1$, $R_3 \to R_3 - R_1$, $R_4 \to R_4 - R_1$:

Вторая строка делится на $-3$: $R_2 \to -\frac13 R_2 = (0, 1, 1, -1 \mid -2)$.

$R_3 \to R_3 + 3R_2$, $R_4 \to R_4 + R_2$:

$R_4 \to R_4 - \frac14 R_3 = \left(0, 0, 0, 2 + \frac14 \mid 5 + \frac74\right) = \left(0, 0, 0, \frac94 \mid \frac{27}{4}\right)$:

Четыре ведущих элемента на четыре неизвестных — единственное решение $(1, 2, -1, 3)$, которое мы получим обратным ходом чуть ниже.

Почему это важно: прямой ход — это ровно та же процедура, которой в прошлых уроках находили ранг матрицы, только применённая к расширенной матрице. Один проход даёт сразу три вещи: ранг $A$ (число ведущих элементов слева от черты), ранг $[A \mid b]$ (число ненулевых строк целиком) и заготовку для вычисления решения. Именно поэтому в реальных вычислениях никто не считает ранги отдельно, а потом решает систему отдельно — всё делается за один проход.

Обратный ход: разматываем лестницу снизу вверх

Интуиция: последнее уравнение самое простое

После прямого хода система выглядит как лестница: в последнем уравнении осталась одна неизвестная, в предпоследнем — две, и так далее. Это и есть весь смысл прямого хода: превратить запутанную систему в такую, где есть уравнение, решаемое в одно действие.

Обратный ход разматывает лестницу в обратном порядке. Находим последнюю неизвестную из последнего уравнения. Подставляем её в предпоследнее — там становится одна неизвестная, находим её. Подставляем обе в третье снизу — и так до самого верха. Никаких фокусов, только аккуратная арифметика.

Формально, если после прямого хода получена верхнетреугольная система с ненулевыми ведущими элементами $u_{11}, u_{22}, \dots, u_{nn}$, то

Формула выглядит грозно, но читается просто: «берём правую часть строки, вычитаем всё, что уже известно, делим на ведущий элемент».

Разбор примеров

Пример 4. Обратный ход для примера 1.

Ступенчатая матрица из примера 1:

Возвращаемся к уравнениям:

Третье уравнение: $3z = 9 \Rightarrow z = 3$.

Второе: $y + 3 = 5 \Rightarrow y = 2$.

Первое: $x + 3\cdot 2 + 2\cdot 3 = 13 \Rightarrow x + 12 = 13 \Rightarrow x = 1$.

Проверка подстановкой в исходную систему обязательна и занимает десять секунд: $1 + 6 + 6 = 13$ ✓, $2 + 2 - 3 = 1$ ✓, $1 - 2 + 3 = 2$ ✓.

Ответ: $(x, y, z) = (1, 2, 3)$.

Пример 5. Обратный ход для системы $4 \times 4$ из примера 3.

Из четвёртой строки: $\frac94 x_4 = \frac{27}{4} \Rightarrow x_4 = 3$.

Из третьей: $4x_3 - 3 = -7 \Rightarrow 4x_3 = -4 \Rightarrow x_3 = -1$.

Из второй: $x_2 + (-1) - 3 = -2 \Rightarrow x_2 = 2$.

Из первой: $x_1 + 4 - 1 - 3 = 1 \Rightarrow x_1 = 1$.

Ответ: $(1, 2, -1, 3)$. Проверка по первой строке исходной системы: $2\cdot 1 + 2 - (-1) + 3 = 2 + 2 + 1 + 3 = 8$ ✓.

Пример 6. Когда ведущие элементы дробные.

Третья строка: $-\frac35 z = -\frac65 \Rightarrow z = 2$.

Вторая: $\frac52 y - \frac12 \cdot 2 = \frac{11}{2} \Rightarrow \frac52 y = \frac{11}{2} + 1 = \frac{13}{2} \Rightarrow y = \frac{13}{5}$.

Первая: $2x - \frac{13}{5} + 6 = 4 \Rightarrow 2x = 4 - 6 + \frac{13}{5} = -2 + \frac{13}{5} = \frac{3}{5} \Rightarrow x = \frac{3}{10}$.

Ответ: $\left(\frac{3}{10}, \frac{13}{5}, 2\right)$. Дроби в ответе — норма, а не признак ошибки: коэффициенты системы целые, но решение почти никогда не бывает целым. Как раз поэтому руками метод Гаусса удобнее вести в обыкновенных дробях, а не в десятичных — десятичные придётся округлять, а обыкновенные остаются точными до самого конца.

Почему это важно: обратный ход стоит всего $\approx n^2$ операций против $\approx \frac{2}{3}n^3$ у прямого хода. Для $n = 1000$ это разница между миллионом и семьюстами миллионами операций — то есть обратный ход по времени практически бесплатен. Это факт с далеко идущими последствиями: если тебе нужно решить много систем с одной и той же матрицей $A$, но разными правыми частями, дорогую часть работы (прямой ход) достаточно сделать один раз. Ровно на этом наблюдении построено LU-разложение, о котором пойдёт речь в разделе про машинное обучение.

Три исхода прямого хода: как читать ступенчатую матрицу

Интуиция: смотрим на последние строки

Прямой ход всегда доводится до конца — он не «ломается» и не «зависает». Но результат может выглядеть по-разному, и по этому виду мгновенно читается ответ на главный вопрос: сколько у системы решений. Три случая, и никаких других.

Исход 1: противоречивая строка. В ступенчатой матрице появилась строка вида

Как уравнение она читается $0\cdot x_1 + 0 \cdot x_2 + \dots + 0 \cdot x_n = c$, то есть $0 = c$. Ни один набор чисел этому не удовлетворяет. Система несовместна, решений нет. На языке прошлого урока: $\operatorname{rank}(A) < \operatorname{rank}([A \mid b])$, потому что эта строка добавляет ранга расширенной матрице, но не добавляет ранга матрице коэффициентов.

Исход 2: ведущих элементов ровно $n$. Каждой неизвестной достался свой ведущий элемент, ступеньки идут «без пропусков», нулевых строк либо нет, либо они пусты и справа тоже. Тогда обратный ход однозначно определяет все $x_i$ — единственное решение. Здесь $\operatorname{rank}(A) = \operatorname{rank}([A \mid b]) = n$.

Исход 3: ведущих элементов $r < n$. Некоторым столбцам ведущий элемент не достался. Переменные, отвечающие этим столбцам, — свободные, их ровно $n - r$ штук. Переменные при ведущих элементах — базисные, они выражаются через свободные. Система имеет бесконечно много решений, а ответ записывается в параметрическом виде.

Именно поэтому ступенчатый вид так ценен: он разом отвечает и на вопрос теоремы Кронекера — Капелли, и даёт готовый рецепт вычисления решения.

Как записывать общее решение

Механика такая. Свободным переменным присваиваем произвольные параметры: $x_{j_1} = t_1$, $x_{j_2} = t_2$, и так далее. Дальше обратным ходом выражаем базисные переменные через эти параметры. Результат — общее решение: формула, в которую можно подставить любые значения параметров и получить решение системы. Подставив конкретные числа (например, все нули), получишь частное решение.

Важная деталь оформления: свободными нужно объявлять именно те переменные, чьи столбцы не содержат ведущих элементов. Если объявить свободной «неправильную» переменную, выражения могут не сойтись или получатся лишние деления на ноль.

Разбор примеров

Пример 7. Несовместная система.

$R_2 \to R_2 - 2R_1 = (0, 1, 2 \mid 1)$, $R_3 \to R_3 - 3R_1 = (0, 1, 2 \mid 2)$:

$R_3 \to R_3 - R_2 = (0, 0, 0 \mid 1)$:

Последняя строка читается как $0 = 1$. Система несовместна.

Что произошло по существу: третье уравнение — это сумма первого и второго ($1+2=3$, $2+5=7$, $3+8=11$), поэтому его левая часть обязана равняться $1 + 3 = 4$. А в системе стоит $5$. Левые части согласованы, правые — нет; геометрически три плоскости образуют «треугольную призму» без общей точки.

Пример 8. Бесконечно много решений, одна свободная переменная.

$R_2 \to R_2 - 2R_1 = (0, 0, 1 \mid 1)$, $R_3 \to R_3 - 3R_1 = (0, 0, 1 \mid 1)$:

$R_3 \to R_3 - R_2 = (0,0,0\mid 0)$ — нулевая строка целиком, включая правую часть. Это не противоречие, а просто лишнее уравнение:

Ведущие элементы стоят в столбцах 1 и 3, значит $x$ и $z$ — базисные, а $y$ — свободная. Полагаем $y = t$, $t \in \mathbb{R}$.

Из второй строки: $z = 1$.

Из первой: $x + 2t + 3 = 4 \Rightarrow x = 1 - 2t$.

Общее решение: $(x, y, z) = (1 - 2t,\ t,\ 1)$, $t \in \mathbb{R}$.

Частное решение при $t = 0$: $(1, 0, 1)$. Проверим: $1 + 0 + 3 = 4$ ✓, $2 + 0 + 7 = 9$ ✓, $3 + 0 + 10 = 13$ ✓. При $t = 2$: $(-3, 2, 1)$, проверяем первое уравнение: $-3 + 4 + 3 = 4$ ✓.

Полезная привычка: всегда подставляй два разных значения параметра. Если формула верна при обоих, почти наверняка она верна вообще; если сходится только при $t = 0$, ты ошибся в выражении базисных переменных.

Пример 9. Две свободные переменные.

$R_2 \to R_2 - 2R_1 = (0,0,1,1,0 \mid 1)$, $R_3 \to R_3 - R_1 = (0,0,3,-1,2 \mid 3)$:

Во втором столбце ведущего элемента нет — ниже первой строки там сплошные нули. Это нормально: переходим к третьему столбцу, ведущий элемент $1$ во второй строке. $R_3 \to R_3 - 3R_2 = (0,0,0,-4,2\mid 0)$:

Ведущие элементы в столбцах 1, 3, 4 — базисные переменные $x_1, x_3, x_4$; свободные — $x_2$ и $x_5$, их $5 - 3 = 2$ штуки. Полагаем $x_2 = s$, $x_5 = u$.

Из третьей строки: $-4x_4 + 2u = 0 \Rightarrow x_4 = \dfrac{u}{2}$.

Из второй: $x_3 + \dfrac{u}{2} = 1 \Rightarrow x_3 = 1 - \dfrac{u}{2}$.

Из первой: $x_1 + 2s - \left(1 - \dfrac{u}{2}\right) + \dfrac{u}{2} + u = 3$, то есть $x_1 = 4 - 2s - 2u$.

Общее решение: $\left(4 - 2s - 2u,\ s,\ 1 - \dfrac{u}{2},\ \dfrac{u}{2},\ u\right)$, $s, u \in \mathbb{R}$.

Проверка при $s = 0, u = 2$: получаем $(0, 0, 0, 1, 2)$. Подставляем: $0 + 0 - 0 + 1 + 2 = 3$ ✓, $0+0-0+3+4 = 7$ ✓, $0+0+0+0+6=6$ ✓.

Почему это важно: три исхода — это не абстрактная классификация, а рабочая диагностика. В прикладной задаче несовместность обычно означает ошибку в постановке: например, в балансе потоков «втекает» больше, чем «вытекает». Бесконечное множество решений означает, что данных недостаточно и нужно доопределить задачу дополнительным условием — так, в задаче о транспортных потоках свободная переменная соответствует «круговому» потоку по кольцу, который нельзя определить из одних лишь балансов в узлах. Умение сразу распознать исход по виду матрицы экономит часы бессмысленных вычислений.

Метод Гаусса — Жордана и приведённый ступенчатый вид

Интуиция: зачем идти вверх

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

Это и есть метод Гаусса — Жордана. Он делает больше работы на этапе исключения, но полностью снимает обратный ход.

Определение: матрица имеет приведённый ступенчатый вид (reduced row echelon form, RREF), если она ступенчатая, каждый ведущий элемент равен $1$, и в столбце каждого ведущего элемента все остальные элементы равны нулю.

Ключевое свойство RREF: он единственный. Обычных ступенчатых видов у одной матрицы бесконечно много — они зависят от того, какими множителями ты пользовался; а приведённый ступенчатый вид один и не зависит от пути. Именно поэтому в компьютерной алгебре стандартной «канонической формой» матрицы считают RREF, и именно его возвращает sympy.Matrix.rref().

Алгоритм Гаусса — Жордана

1. Выполняем обычный прямой ход до ступенчатого вида.

2. Каждую ненулевую строку делим на её ведущий элемент — все ведущие элементы становятся единицами.

3. Идём снизу вверх: с помощью нижних строк обнуляем всё, что стоит над каждым ведущим элементом.

Результат: слева единичная матрица (если решение единственное), справа — сразу ответ.

Разбор примеров

Пример 10. Гаусс — Жордан для системы с единственным решением.

Прямой ход. $R_2 \to R_2 - 2R_1 = (0, -3, -3 \mid 0)$, $R_3 \to R_3 - 3R_1 = (0, -7, -1 \mid -6)$:

$R_2 \to -\frac13 R_2 = (0, 1, 1 \mid 0)$, затем $R_3 \to R_3 + 7R_2 = (0, 0, 6 \mid -6)$:

Нормируем третью строку: $R_3 \to \frac16 R_3 = (0, 0, 1 \mid -1)$.

Теперь обратный проход Жордана. Обнуляем третий столбец над ведущей единицей: $R_2 \to R_2 - R_3 = (0, 1, 0 \mid 1)$, $R_1 \to R_1 - R_3 = (1, 2, 0 \mid 4)$:

Обнуляем второй столбец над ведущей единицей: $R_1 \to R_1 - 2R_2 = (1, 0, 0 \mid 2)$:

Слева единичная матрица, справа — готовый ответ: $x = 2$, $y = 1$, $z = -1$. Проверка: $2 + 2 - 1 = 3$ ✓, $4 + 1 + 1 = 6$ ✓, $6 - 1 - 2 = 3$ ✓.

Пример 11. RREF для недоопределённой системы.

Возьмём матрицу из примера 8 и доведём её до RREF:

Из RREF общее решение читается вообще без вычислений: первая строка говорит $x + 2y = 1$, то есть $x = 1 - 2y$; вторая — $z = 1$; $y$ свободна. Получаем $(1 - 2t, t, 1)$ — тот же ответ, что мы получали обратным ходом, но добывать его пришлось на один шаг быстрее.

В этом и состоит практическое преимущество Гаусса — Жордана: когда свободных переменных много, RREF заметно удобнее обычного обратного хода, потому что базисные переменные выражаются через свободные напрямую, каждая своей строкой, без цепочки подстановок. Когда же решение единственное, лишняя работа не окупается — обычного обратного хода достаточно.

Проверка в sympy

Ручные вычисления полезно сверять с машиной. В sympy приведённый ступенчатый вид расширенной матрицы получается одной строкой:

from sympy import Matrix, symbols, linsolve

M = Matrix([[1, 2, 3, 4],
            [2, 4, 7, 9],
            [3, 6, 10, 13]])   # последний столбец — правая часть
R, pivots = M.rref()
print(R)        # Matrix([[1, 2, 0, 1], [0, 0, 1, 1], [0, 0, 0, 0]])
print(pivots)   # (0, 2) — ведущие элементы в столбцах 1 и 3

x, y, z = symbols('x y z')
A = Matrix([[1, 2, 3], [2, 4, 7], [3, 6, 10]])
b = Matrix([4, 9, 13])
print(linsolve((A, b), x, y, z))   # {(1 - 2*y, y, 1)}

Обрати внимание на вторую компоненту, которую возвращает rref(): это кортеж номеров столбцов с ведущими элементами (нумерация с нуля). По нему сразу видно, какие переменные базисные, а какие свободные — не нужно ничего высматривать глазами.

Несколько правых частей за один прямой ход

Прямой ход зависит только от матрицы $A$: множители $m_i = a_{i1}/a_{11}$ и все последующие вычисляются по коэффициентам, а правая часть просто «едет прицепом». Значит, если нужно решить несколько систем с одной и той же матрицей, но разными правыми частями $b^{(1)}, b^{(2)}, \dots$, дорогой прямой ход достаточно выполнить один раз: припиши к матрице все правые части сразу и обрабатывай расширенный блок $[A \mid b^{(1)} \mid b^{(2)}]$.

Пример 12. Две правые части.

Пусть матрица системы и две правые части такие:

Записываем всё в одну таблицу:

$R_2 \to R_2 - 2R_1$, $R_3 \to R_3 - R_1$:

$R_3 \to R_3 - R_2$:

Дальше обратный ход выполняем дважды, по одному разу на каждый столбец правых частей.

Для $b^{(1)}$: $z = 2$; $-3y + 6 = 3 \Rightarrow y = 1$; $x + 2 - 2 = 1 \Rightarrow x = 1$. Решение $(1, 1, 2)$.

Для $b^{(2)}$: $z = -1$; $-3y - 3 = -3 \Rightarrow y = 0$; $x + 0 + 1 = 3 \Rightarrow x = 2$. Решение $(2, 0, -1)$.

Проверка первого: $1 + 2 - 2 = 1$ ✓, $2 + 1 + 2 = 5$ ✓, $1 - 1 + 6 = 6$ ✓. Второго: $2 + 0 + 1 = 3$ ✓, $4 + 0 - 1 = 3$ ✓, $2 - 0 - 3 = -1$ ✓.

Мы сэкономили целый прямой ход. Для $3 \times 3$ экономия символическая, а вот для $n = 1000$ — это разница между двумя секундами и одной: прямой ход стоит $\approx \frac23 n^3$, а каждый дополнительный обратный ход всего $\approx n^2$.

Почему это важно: идея «дорогая часть работы зависит только от $A$» — это, по сути, готовая формулировка LU-разложения. Ту же самую мысль в промышленных библиотеках доводят до конца: результат прямого хода запоминают в виде двух треугольных матриц и потом решают сколько угодно систем с новыми правыми частями почти даром. Отсюда же следует практическое правило: если тебе нужно решить $Ax = b$ для десятка разных $b$, не вызывай solve десять раз с нуля — либо собери все правые части в одну матрицу, либо разложи $A$ один раз (scipy.linalg.lu_factor и затем lu_solve).

Системы с параметром: разбор всех случаев

Интуиция: параметр решает, где сломается лестница

Система с параметром — это на самом деле не одна система, а целое семейство систем: для каждого значения $a$ получается своя. Вопрос «реши систему» здесь заменяется на «опиши поведение всего семейства»: при каких $a$ решений нет, при каких оно единственное, при каких их бесконечно много.

Метод Гаусса разбирается с этим на удивление прямолинейно. Гоним прямой ход как обычно, стараясь не делить на выражения с параметром (потому что они могут обращаться в ноль). В конце смотрим на последнюю строку: она имеет вид $(0\ \ 0\ \ \dots\ \ 0\ \ f(a) \mid g(a))$. Дальше три ветки:

• $f(a) \ne 0$ — есть ведущий элемент, все неизвестные базисные, решение единственное;

• $f(a) = 0$ и $g(a) \ne 0$ — противоречивая строка, система несовместна;

• $f(a) = 0$ и $g(a) = 0$ — строка обнулилась целиком, ведущих элементов меньше, чем неизвестных, решений бесконечно много.

Критические значения параметра — это в точности корни $f(a) = 0$. Для квадратной системы они совпадают с корнями $\det A = 0$, что даёт удобный способ проверки: посчитал определитель как функцию от $a$, нашёл корни — вот и все подозрительные точки, остальные значения дают единственное решение.

Главная ловушка этого типа задач — деление на выражение с параметром внутри прямого хода. Если ты в какой-то момент написал $R_2 \to R_2 - \frac{2}{a-1}R_1$, ты молча предположил, что $a \ne 1$, и весь дальнейший разбор случая $a = 1$ будет неверным. Лечится двумя способами: либо избегать таких делений (переставлять строки так, чтобы ведущим оказался числовой элемент), либо честно выписать «случай $a = 1$ разбираем отдельно» и потом действительно разобрать.

Разбор примеров

Пример 13. Система $2 \times 2$ с параметром — все три исхода.

Соблазн — сразу поделить первую строку на $a$. Не делаем: $a$ может быть нулём. Вместо этого переставим строки, чтобы наверху был числовой ведущий элемент:

$R_2 \to R_2 - aR_1$:

Последняя строка: $(1 - a^2)y = 1 - a$, то есть $(1-a)(1+a)\,y = 1 - a$.

Случай 1: $1 - a^2 \ne 0$, то есть $a \ne 1$ и $a \ne -1$. Ведущий элемент ненулевой:

Единственное решение $\left(\dfrac{1}{a+1},\ \dfrac{1}{a+1}\right)$.

Случай 2: $a = 1$. Строка превращается в $(0\ \ 0 \mid 0)$ — нулевая целиком. Система вырождается в одно уравнение $x + y = 1$: бесконечно много решений, общее решение $(1 - t,\ t)$, $t \in \mathbb{R}$. Геометрически обе прямые совпали.

Случай 3: $a = -1$. Строка превращается в $(0\ \ 0 \mid 1 - (-1)) = (0\ \ 0 \mid 2)$ — противоречие $0 = 2$. Система несовместна. Геометрически: прямые $-x + y = 1$ и $x - y = 1$ параллельны и не совпадают.

Сверимся с определителем: $\det \begin{pmatrix} a & 1 \\ 1 & a \end{pmatrix} = a^2 - 1$, корни $a = \pm 1$ — ровно те две подозрительные точки, что мы нашли. Проверим формулу на конкретном значении: при $a = 2$ она даёт $x = y = \frac13$, подставляем в исходную систему: $2\cdot\frac13 + \frac13 = 1$ ✓, $\frac13 + 2\cdot\frac13 = 1$ ✓.

Пример 14. Система $3 \times 3$ с параметром.

Ведущий элемент — числовая единица, деление на параметр не грозит. $R_2 \to R_2 - 2R_1$, $R_3 \to R_3 - R_1$:

Второй ведущий элемент снова числовая единица — отлично. $R_3 \to R_3 - (a-1)R_2$:

Итоговая ступенчатая матрица:

Критические значения читаются прямо из последней строки: $a = 2$ и $a = -3$.

Случай 1: $a \ne 2$ и $a \ne -3$. Ведущий элемент ненулевой, три ведущих на три неизвестных — единственное решение:

Решение: $\left(1,\ \dfrac{1}{a+3},\ \dfrac{1}{a+3}\right)$. Любопытно, что $x$ не зависит от параметра вовсе.

Случай 2: $a = -3$. Последняя строка становится $(0\ \ 0\ \ 0 \mid -(-3-2)) = (0\ \ 0\ \ 0 \mid 5)$ — противоречие. Система несовместна.

Случай 3: $a = 2$. Последняя строка обнуляется целиком: $(0\ \ 0\ \ 0 \mid 0)$. Остаются два ведущих элемента на три неизвестных, значит одна свободная переменная. Матрица принимает вид

Свободная переменная $z = t$. Из второй строки $y = 1 - 4t$. Из первой $x = 1 - y + z = 1 - (1 - 4t) + t = 5t$.

Общее решение при $a = 2$: $(5t,\ 1 - 4t,\ t)$, $t \in \mathbb{R}$.

Проверим при $t = 1$, то есть точку $(5, -3, 1)$, подставив в исходную систему с $a = 2$: $5 - 3 - 1 = 1$ ✓, $10 - 9 + 2 = 3$ ✓, $5 - 6 + 3 = 2$ ✓. И при $t = 0$: $(0, 1, 0)$ даёт $0 + 1 - 0 = 1$ ✓, $0 + 3 + 0 = 3$ ✓, $0 + 2 + 0 = 2$ ✓.

Контроль по определителю: $\det A = -(a-2)(a+3)$ — те же самые корни $2$ и $-3$. И контроль общей формулы: при $a = 0$ она даёт $\left(1, \frac13, \frac13\right)$, подставляем в систему с $a = 0$: $1 + \frac13 - \frac13 = 1$ ✓, $2 + 1 + 0 = 3$ ✓, $1 + 0 + 1 = 2$ ✓.

Пример 15. Параметр в правой части.

Параметр не обязан сидеть среди коэффициентов — он бывает и справа, и тогда матрица $A$ фиксирована, а меняется только совместность.

$R_2 \to R_2 - 2R_1 = (0, 1, 3 \mid 1)$, $R_3 \to R_3 - 3R_1 = (0, 1, 3 \mid c - 3)$:

$R_3 \to R_3 - R_2 = (0, 0, 0 \mid c - 4)$.

Матрица $A$ имеет ранг 2 при любом $c$ — параметр на неё не влияет. А расширенная матрица имеет ранг 2 только при $c = 4$.

Ответ: при $c \ne 4$ система несовместна; при $c = 4$ совместна и имеет бесконечно много решений. Найдём их: свободная $z = t$, из второй строки $y = 1 - 3t$, из первой $x = 1 - 2(1-3t) + t = 7t - 1$. Общее решение $(7t - 1,\ 1 - 3t,\ t)$.

Проверка при $t = 1$: $(6, -2, 1)$. Подставляем: $6 - 4 - 1 = 1$ ✓, $12 - 10 + 1 = 3$ ✓, $18 - 14 + 0 = 4$ ✓.

Единственного решения здесь не бывает ни при каком $c$ — ранг матрицы коэффициентов равен 2 и от параметра не зависит, а неизвестных три. Полезно помнить: если параметр стоит только справа, он способен переключать систему между «несовместна» и «совместна», но никогда не меняет число ведущих элементов слева.

Почему это важно: задачи с параметром — это тренажёр на аккуратность, который безжалостно ловит две вещи: незаконное деление на выражение, способное обратиться в ноль, и забытый разбор граничного случая. Ровно те же ошибки всплывают в коде: функция, которая делит на «маленькое» число без проверки, ведёт себя нормально на тестовых данных и взрывается на боевых. А в прикладном смысле параметр — это чаще всего физическая величина: сопротивление резистора, коэффициент модели, доля вещества в смеси; критические значения параметра означают «при этой настройке система вырождается» и обычно соответствуют реальным особым режимам.

Сколько стоит метод Гаусса: откуда берётся $n^3$

Интуиция: треугольник вместо квадрата

Посчитаем работу честно, по шагам. Пусть система квадратная, $n$ уравнений и $n$ неизвестных.

На первом шаге мы обнуляем первый столбец под ведущим элементом. Строк ниже — $(n-1)$ штука. Для каждой из них нужно: одно деление (вычислить множитель $m_i$) и затем пересчёт всех оставшихся элементов строки — их $n-1$ слева плюс один в правой части, итого $n$ чисел, на каждое умножение и вычитание. Получается примерно $2n$ операций на строку и $\approx 2n(n-1)$ операций на весь первый шаг.

На втором шаге подматрица стала меньше: строк $(n-2)$, чисел в строке $(n-1)$. Стоимость $\approx 2(n-1)(n-2)$. И так далее: шаги дешевеют квадратично.

Суммируем:

Вот и весь куб. Он берётся из того, что мы делаем $\approx n$ шагов, на каждом обрабатываем $\approx n$ строк, а в каждой строке $\approx n$ чисел: три вложенных цикла длины $n$.

Обратный ход стоит существенно меньше: на $i$-й строке нужно $\approx (n-i)$ умножений и вычитаний плюс одно деление, в сумме $\approx n^2$ операций. То есть

Для $n = 1000$ это $6{,}7\cdot 10^8$ против $10^6$: обратный ход занимает 0,15% общего времени. Практически весь метод Гаусса — это прямой ход.

Метод Гаусса — Жордана обходится примерно в $n^3$ операций, то есть в полтора раза дороже связки «прямой ход + обратный ход». Он платит за удобство чтения ответа; поэтому в вычислительных библиотеках для решения систем используют обычный Гаусс, а Гаусса — Жордана оставляют для ручных выкладок и символьных вычислений.

Что это значит на практике

Кубическая сложность — это очень конкретное обещание: удвоил размер задачи — время выросло в восемь раз. Проверим на реальных замерах numpy.linalg.solve (за которым стоит LAPACK, то есть тот же Гаусс с выбором главного элемента):

• $n = 500$: $\frac23 n^3 \approx 8{,}3\cdot 10^7$ операций, замер — около $0{,}018$ с;

• $n = 1000$: $\approx 6{,}7 \cdot 10^8$ операций, замер — около $0{,}030$ с;

• $n = 2000$: $\approx 5{,}3 \cdot 10^9$ операций, замер — около $0{,}103$ с.

Обрати внимание: время растёт медленнее, чем в восемь раз при удвоении. Это не опровержение теории, а эффект того, что на маленьких матрицах процессор недогружен: при $n = 500$ получается $\approx 4{,}6$ гигафлопса, а при $n = 2000$ — уже $\approx 52$ гигафлопса. Асимптотика $n^3$ проявляется честно, начиная с размеров в несколько тысяч, когда накладные расходы становятся незаметны.

Теперь экстремальный случай. $n = 10^6$ — миллион неизвестных, вполне реальный размер для задачи из вычислительной физики или большой регрессии:

На машине, выдающей $10^{11}$ операций в секунду (это хороший многоядерный сервер), это $6{,}7\cdot 10^6$ секунд — около 77 суток непрерывного счёта. И это ещё не самая большая проблема: чтобы просто хранить плотную матрицу $10^6 \times 10^6$ в формате float64, нужно $10^{12}\cdot 8$ байт = 8 терабайт оперативной памяти.

Отсюда фундаментальный вывод: плотный метод Гаусса не масштабируется на очень большие системы. Для них используют либо разреженные варианты (когда почти все коэффициенты нули и хранить надо только ненулевые), либо итерационные методы, которые вообще не приводят матрицу к ступенчатому виду, а строят последовательность приближений к решению.

Почему это важно: оценка $\frac23 n^3$ — это то, что позволяет за полминуты прикинуть, реализуема ли задача вообще, до того как ты напишешь первую строку кода. Система на 5000 неизвестных решится за секунды; на 50 000 — за часы и с 20 гигабайтами памяти; на 500 000 плотным методом не решится никогда. В следующем уроке ты увидишь метод, у которого дела с масштабированием обстоят несравнимо хуже: правило Крамера через определители растёт факториально и непригодно уже при $n = 15$.

Численная устойчивость: почему порядок строк меняет ответ

Интуиция: деление на почти-ноль

В точной арифметике метод Гаусса безупречен: если ведущий элемент отличен от нуля, всё работает, и никакого «почти нуля» не бывает — число либо ноль, либо нет. Но компьютер считает не точно. Тип float64 хранит примерно 16 значащих десятичных цифр, и каждая операция округляет результат.

Вот где это больно бьёт. Множитель $m_i = a_{i1}/a_{11}$ обратно пропорционален ведущему элементу. Если ведущий элемент крошечный, множитель огромен. А умножение строки на огромное число и вычитание её из другой строки уничтожает информацию: маленькие слагаемые попросту исчезают при округлении, потому что не помещаются в мантиссу рядом с большими.

Честный численный пример

Возьмём систему

Её точное решение: $x = \dfrac{1}{1 - \varepsilon}$, $y = \dfrac{1 - 2\varepsilon}{1 - \varepsilon}$. При крошечном $\varepsilon$ это практически $x = 1$, $y = 1$. Матрица прекрасная, никакой вырожденности: определитель равен $\varepsilon - 1 \approx -1$.

Наивный Гаусс (берём ведущим то, что стоит в углу): $m = 1/\varepsilon$, преобразование $R_2 \to R_2 - m R_1$ даёт $(1 - m)y = 2 - m$, откуда $y = \dfrac{2 - m}{1 - m}$, а затем $x = \dfrac{1 - y}{\varepsilon}$.

Прогоняем это в numpy с $\varepsilon = 10^{-17}$ и типом float64. Множитель $m = 10^{17}$. Компьютер вычисляет $1 - 10^{17}$ и получает ровно $-10^{17}$: единица не помещается в мантиссу рядом с $10^{17}$ и молча теряется. Точно так же $2 - 10^{17}$ даёт ровно $-10^{17}$. Значит

Правильный ответ $x = 1$, полученный $x = 0$. Ошибка 100% — не «немножко неточно», а полностью неверный ответ, полученный по абсолютно правильной формуле.

При $\varepsilon = 10^{-16}$ картина не лучше, просто ерунда выглядит иначе: наивный ход даёт $x = 2{,}220446049250313$ вместо $1$ — ошибка 122%.

Тот же счёт с перестановкой строк. Ставим наверх строку с большим по модулю элементом первого столбца:

Теперь множитель $m = \varepsilon = 10^{-17}$, крошечный. $R_2 \to R_2 - \varepsilon R_1$ даёт $(1 - \varepsilon)y = 1 - 2\varepsilon$, то есть $y = 1{,}0$, и дальше $x = 2 - y = 1{,}0$. Ответ правильный: $(1{,}0,\ 1{,}0)$, ровно то же, что выдаёт numpy.linalg.solve.

Разница между катастрофой и правильным ответом — одна перестановка строк. Математически обе системы идентичны; численно они ведут себя противоположно.

Как это выглядит «на бумаге»

Чтобы почувствовать эффект без гигантских степеней, посчитай ту же систему с $\varepsilon = 10^{-4}$, округляя каждый промежуточный результат до трёх значащих цифр (так работали механические калькуляторы, и так же, только с 16 цифрами, работает float64).

Наивно: $m = 10^{4}$; $1 - 10^4 = -9999 \to -10000$ (три значащих цифры!); $2 - 10^4 = -9998 \to -10000$; $y = 1{,}00$; $x = (1 - 1{,}00)/10^{-4} = 0$. Снова ноль.

С перестановкой: $1 - 10^{-4} = 0{,}9999 \to 1{,}00$; $1 - 2\cdot 10^{-4} \to 1{,}00$; $y = 1{,}00$; $x = 2 - 1{,}00 = 1{,}00$. Точный ответ: $x = 1{,}00010001\ldots$, $y = 0{,}99989999\ldots$ — три значащих цифры совпали идеально.

Частичный выбор главного элемента

Отсюда стандартное правило, которое реализовано во всех численных библиотеках:

Частичный выбор главного элемента (partial pivoting): на каждом шаге прямого хода среди всех кандидатов в ведущие элементы текущего столбца (то есть в текущей строке и ниже) выбирают элемент с наибольшим модулем и перестановкой строк выводят его в ведущую позицию.

Логика прямолинейна: чем больше по модулю ведущий элемент, тем меньше по модулю множители $m_i = a_{ik}/a_{kk}$. При выборе максимума все множители автоматически оказываются не больше единицы по модулю, и катастрофического роста чисел не происходит.

Три важных уточнения.

Во-первых, перестановка строк ничего не стоит: это не арифметика, а перенумерация. Поэтому pivoting добавляет к методу Гаусса $O(n^2)$ сравнений — на фоне $\frac23 n^3$ арифметических операций это бесплатно.

Во-вторых, pivoting нужен даже тогда, когда ведущий элемент не нулевой, а просто маленький. Именно это отличает численную версию алгоритма от учебной: на бумаге строки переставляют только чтобы избавиться от нуля, в коде — чтобы избавиться от «почти нуля».

В-третьих, есть ещё полный выбор (complete pivoting), когда максимум ищут по всей оставшейся подматрице и переставляют не только строки, но и столбцы. Он надёжнее теоретически, но требует $O(n^3)$ сравнений и на практике почти не используется: частичного выбора хватает в подавляющем большинстве реальных задач.

И честное предупреждение: pivoting лечит не всё. Есть системы, у которых сам ответ дико чувствителен к малейшему изменению коэффициентов, — там никакой алгоритм не спасёт, потому что проблема в самой матрице, а не в способе счёта. Количественная мера этой чувствительности существует, и с ней ты познакомишься в уроке про матричный метод; здесь достаточно запомнить, что выбор главного элемента защищает от ошибок алгоритма, но не от плохих свойств задачи.

Почему это важно: это тот случай, когда «теоретическая тонкость» напрямую определяет, работает ли твой код. Если ты когда-нибудь напишешь метод Гаусса руками — например, в учебных целях или внутри специализированного решателя — и забудешь pivoting, он будет проходить все тесты на аккуратных матрицах и молча выдавать мусор на реальных данных. Именно поэтому в промышленном коде системы решают не самописным Гауссом, а вызовом numpy.linalg.solve или scipy.linalg.solve, за которыми стоит LAPACK с частичным выбором главного элемента и сорока годами вылизывания.

Метод Гаусса в машинном обучении

Может показаться, что «решение систем уравнений» — это что-то из курса, а не из работы. На деле метод Гаусса встроен почти во всё, что ты будешь запускать: от одной строчки numpy.linalg.solve до обучения линейных моделей и работы физических симуляторов. Разберём, где именно.

numpy.linalg.solve — это Гаусс с pivoting

Когда ты пишешь

import numpy as np
x = np.linalg.solve(A, b)

внутри не происходит ничего таинственного. NumPy вызывает LAPACK-процедуру dgesv, которая делает ровно две вещи: сначала прямой ход метода Гаусса с частичным выбором главного элемента (результат сохраняется как LU-разложение), затем обратный ход для правой части. Никаких определителей, никаких обратных матриц, никакого правила Крамера — только исключение неизвестных, тот же самый алгоритм, который ты только что делал руками.

То же самое происходит в scipy.linalg.solve, в torch.linalg.solve, в MATLAB-овском операторе обратного деления A\b и в решателях R. Метод Гаусса — это буквально индустриальный стандарт для плотных систем.

LU-разложение: «Гаусс, у которого запомнили ход»

Функция scipy.linalg.lu возвращает три матрицы: $P$, $L$ и $U$, такие что $PA = LU$. Не вдаваясь в технику (это отдельная большая тема), объясню идею, которая нам уже знакома: $U$ — это ступенчатая матрица, полученная прямым ходом; $L$ хранит все множители $m_i$, которые мы использовали при исключении; $P$ фиксирует, какие строки мы переставляли ради pivoting.

Смысл в том, что прямой ход стоит $\frac23 n^3$, а его результат зависит только от матрицы $A$. Если запомнить этот результат, то каждую новую систему с той же матрицей, но другой правой частью можно решить за $n^2$ операций — то есть в сотни раз быстрее. Именно это и делает связка:

from scipy.linalg import lu_factor, lu_solve

lu, piv = lu_factor(A)           # дорого: один прямой ход, ~2/3 n^3
x1 = lu_solve((lu, piv), b1)     # дёшево: ~n^2
x2 = lu_solve((lu, piv), b2)     # дёшево

Ситуация «одна матрица, много правых частей» встречается сплошь и рядом: шаги по времени в численном решении уравнений физики, разные целевые переменные в регрессии на одних и тех же признаках, разные наборы граничных условий. Мы разбирали учебную версию этого приёма в примере 12 — LU-разложение просто доводит идею до промышленной формы.

Почему решают систему, а не обращают матрицу

Один из самых устойчивых антипаттернов в коде выглядит так:

w = np.linalg.inv(A) @ b      # так не надо
w = np.linalg.solve(A, b)     # так надо

Математически это одно и то же. Вычислительно — нет, и по двум причинам.

Во-первых, стоимость. Явное вычисление $A^{-1}$ — это, по существу, решение $n$ систем с правыми частями $e_1, \dots, e_n$ (столбцами единичной матрицы), плюс потом ещё умножение матрицы на вектор. Итого примерно $2n^3$ операций против $\frac23 n^3$ у solve — в три раза дороже, причём даром: сама матрица $A^{-1}$ тебе не нужна, нужен только вектор $x$.

Во-вторых, точность. Каждая дополнительная арифметическая операция вносит своё округление. Путь «обратить, потом умножить» делает существенно больше операций, чем прямой путь «решить», и накапливает больше ошибки. На хороших матрицах разница незаметна, на плохих — принципиальна.

Правило простое: если в твоём коде встречается inv, почти всегда его нужно заменить на solve. Явная обратная матрица нужна редко — например, когда сама $A^{-1}$ является ответом (в задачах статистики, где элементы обратной матрицы имеют собственный смысл).

МНК и нормальные уравнения

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

где $X$ — матрица признаков (строки — объекты, столбцы — признаки), $y$ — вектор ответов, $w$ — искомые веса. Матрица $X^TX$ квадратная размера $d \times d$, где $d$ — число признаков, и симметричная.

Эту систему решают именно методом Гаусса, точнее — его специализированным вариантом для симметричных матриц, разложением Холецкого, которое использует симметрию и потому вдвое дешевле: $\frac13 n^3$ вместо $\frac23 n^3$. Идея та же самая — исключение неизвестных, только с учётом того, что матрица симметрична и, если признаки не вырождены, положительно определена.

Практическая деталь: если признаки линейно зависимы (мультиколлинеарность, о которой шла речь в уроке про ранг), матрица $X^TX$ вырождена, прямой ход упирается в нулевой ведущий элемент — и solve честно бросает LinAlgError: Singular matrix. Ровно поэтому в реальных пайплайнах либо добавляют регуляризацию (в гребневой регрессии решают $(X^TX + \lambda I)w = X^Ty$, и добавка $\lambda I$ гарантирует невырожденность), либо решают задачу через numpy.linalg.lstsq, который вместо нормальных уравнений использует более устойчивое разложение и корректно работает даже с вырожденной матрицей.

Ещё одна тонкость, которую полезно знать заранее: составление $X^TX$ само по себе ухудшает численные свойства задачи — квадратичная форма «сжимает» разброс значений и усиливает чувствительность к округлениям. Поэтому промышленные реализации линейной регрессии (тот же sklearn.linear_model.LinearRegression) не строят $X^TX$ вовсе, а работают напрямую с $X$ через другие разложения. Названия — QR и SVD — ты встретишь в следующих модулях курса; здесь важно только понимать, что все они выросли из одной и той же идеи исключения.

Разреженные системы и итерационные методы

Метод Гаусса в чистом виде хорош для плотных матриц — тех, где почти все элементы ненулевые. Но огромная доля реальных систем разреженная: в матрице миллион строк, а в каждой строке всего 5–10 ненулевых элементов. Такие системы возникают в графовых задачах, в конечно-элементных расчётах, в рекомендательных системах, в анализе сетей.

Наивный Гаусс на такой матрице проваливается по неожиданной причине: исключение порождает новые ненулевые элементы на местах, где раньше были нули (это явление называется fill-in). Матрица, которая занимала 100 мегабайт в разреженном формате, в процессе исключения раздувается до терабайтов. Существуют специальные разреженные варианты метода (в scipy.sparse.linalg.spsolve), которые борются с fill-in хитрым переупорядочиванием строк и столбцов, и они отлично работают до определённого размера.

За этим размером начинается территория итерационных методов — сопряжённых градиентов, GMRES и их родственников. Они устроены принципиально иначе: не приводят матрицу ни к какому виду, а строят последовательность приближений, на каждом шаге лишь умножая матрицу на вектор (что для разреженной матрицы очень дёшево). Итерационные методы не дают точного ответа за конечное число шагов, зато позволяют решать системы с миллиардами неизвестных. Это отдельная большая тема, но полезно знать, где заканчивается зона ответственности метода Гаусса.

Где ещё это всплывает

Полезно держать в голове короткий список мест, где под капотом работает исключение неизвестных:

• интерполяция и сплайны: коэффициенты кубического сплайна находятся из трёхдиагональной системы, которая решается модифицированным Гауссом (метод прогонки) за $O(n)$ операций;

• фильтр Калмана: на каждом шаге обновления решается небольшая линейная система;

• графовые вероятностные модели и цепи Маркова: стационарное распределение находится как решение системы $\pi P = \pi$;

• компьютерная графика и физические движки: расчёт сил связей в системе твёрдых тел — это линейная система, решаемая на каждом кадре;

• балансировка и оптимизация: шаг метода Ньютона в оптимизации — это решение системы с матрицей вторых производных.

Во всех этих случаях от тебя не требуется писать Гаусса руками. Требуется другое: понимать, что происходит внутри, уметь оценить стоимость ($n^3$ — это не шутка), распознать вырожденность по сообщению об ошибке и знать, что solve лучше inv. Именно это понимание и отличает человека, который использует библиотеку осознанно, от того, кто ждёт, что она «как-нибудь сама».

Практика: 30 заданий

Базовые задания (1–10)

Задание 1. Реши методом Гаусса систему $\begin{cases} 2x + y = 5 \\ x - 3y = -1 \end{cases}$

Задание 2. Реши систему $\begin{cases} 2x + 3y = 4 \\ 4x - y = 1 \end{cases}$

Задание 3. Система уже приведена к ступенчатому виду. Выполни обратный ход: $\begin{cases} x + y - z = 4 \\ 3y + 2z = 7 \\ 4z = 8 \end{cases}$

Задание 4. Реши методом Гаусса: $\begin{cases} x + y + z = 6 \\ 2x - y + z = 7 \\ 3x + 2y - z = 9 \end{cases}$

Задание 5. При каких значениях $k$ система $\begin{cases} 2x - 3y = 4 \\ 4x - 6y = k \end{cases}$ совместна? Сколько решений у неё в этом случае?

Задание 6. Реши систему и запиши общее решение: $\begin{cases} x + y + z = 6 \\ 2x + 3y + z = 13 \end{cases}$

Задание 7. Реши систему, в которой первый ведущий элемент нулевой: $\begin{cases} 3y + z = -1 \\ x + 2y - z = -3 \\ 2x + y + 3z = 7 \end{cases}$

Задание 8. Реши систему методом Гаусса — Жордана, доведя расширенную матрицу до приведённого ступенчатого вида: $\begin{cases} x + 2y + 3z = 9 \\ 2x + 3y + z = 7 \\ 3x + y + 2z = 8 \end{cases}$

Задание 9 (прикладное). Есть два сплава меди с алюминием: первый содержит 30% меди, второй — 70% меди. Сколько килограммов каждого сплава нужно взять, чтобы получить 40 кг сплава с содержанием меди 45%?

Задание 10. Оцени, сколько арифметических операций требует прямой ход метода Гаусса для системы с $n = 100$ неизвестными, и во сколько раз это больше, чем обратный ход.

Средние задания (11–20)

Задание 11. Покажи методом Гаусса, что система несовместна: $\begin{cases} x + y + z = 3 \\ 2x + 3y + z = 7 \\ 3x + 4y + 2z = 12 \end{cases}$

Задание 12. Реши систему трёх уравнений с четырьмя неизвестными и запиши общее решение:

Задание 13. Реши систему $4 \times 4$:

Задание 14. Исследуй систему в зависимости от параметра $a$: $\begin{cases} x + 2y = 3 \\ 3x + ay = 1 \end{cases}$

Задание 15. При каких значениях $c$ система совместна и каково её общее решение?

Задание 16 (прикладное, электрические цепи). В разветвлённой цепи ток $I_1$ втекает в узел и разделяется на $I_2$ и $I_3$. По законам Кирхгофа получена система

Найди все три тока (в амперах).

Задание 17 (прикладное, химия). Уравняй реакцию горения пропана

составив систему по балансу атомов каждого элемента и решив её методом Гаусса.

Задание 18 (прикладное, транспортные потоки). Четыре перекрёстка $A \to B \to C \to D \to A$ соединены односторонними улицами с потоками $x_1$ ($A\to B$), $x_2$ ($B \to C$), $x_3$ ($C \to D$), $x_4$ ($D \to A$). Балансы «сколько машин въехало = сколько выехало» дают систему

Найди общее решение и объясни, почему единственного решения быть не может.

Задание 19. Реши две системы с одной матрицей за один прямой ход:

Задание 20. Приведи расширенную матрицу к приведённому ступенчатому виду (RREF) и запиши общее решение:

Продвинутые задания (21–30)

Задание 21. Исследуй систему в зависимости от параметра $a$ и найди решение в каждом случае:

Задание 22. Система содержит два параметра. Исследуй её при всех значениях $a$ и $b$:

Задание 23. Реши систему четырёх уравнений с пятью неизвестными:

Задание 24. Система с буквенными правыми частями:

При каком соотношении между $a$, $b$ и $c$ система совместна? Найди решение в этом случае.

Задание 25 (комбинированное). Система имеет нулевой элемент в левом верхнем углу и параметр $a$:

Исследуй её при всех значениях $a$ и запиши общее решение там, где решений бесконечно много.

Задание 26. Реши однородную систему методом Гаусса и найди все её решения:

Задание 27 (численная устойчивость). Реши систему

двумя способами, округляя каждый промежуточный результат до трёх значащих цифр: (а) наивным методом Гаусса, взяв ведущим элементом $0{,}001$; (б) с частичным выбором главного элемента. Сравни с точным ответом.

Задание 28. Плотная система с $n = 300$ неизвестными решается методом Гаусса за $0{,}02$ секунды. Оцени время решения системы с $n = 1200$ на той же машине и посчитай, сколько арифметических операций для этого потребуется.

Задание 29. Реши систему $4 \times 4$ с нулевым первым ведущим элементом:

Задание 30 (капстоун, ML). По пяти точкам $t = -2, -1, 0, 1, 2$ с наблюдениями $y = 2, 1, 3, 5, 10$ строится квадратичная модель $\hat{y} = w_0 + w_1 t + w_2 t^2$ методом наименьших квадратов. Нормальные уравнения $(X^TX)w = X^Ty$ для этих данных имеют вид

Реши эту систему методом Гаусса и запиши уравнение подобранной параболы.

Частые ошибки

Ошибка 1. Меняют обе строки при преобразовании $R_i \to R_i - mR_k$.

Как выглядит: вычитая первую строку из третьей, человек «заодно» изменяет и первую. Почему возникает: путаница с тем, какая строка «активная». Как правильно: при преобразовании $R_i \to R_i - mR_k$ меняется только строка $R_i$; строка $R_k$ (та, что с ведущим элементом) остаётся неприкосновенной до конца текущего шага. Если её испортить, обнулённые столбцы перестанут быть обнулёнными.

Ошибка 2. Забывают преобразовать правую часть.

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

Ошибка 3. Умножают строку на ноль или «делят строку на строку».

Как выглядит: попытка «упростить» строку операцией, которой в списке разрешённых нет. Почему возникает: аналогия с обычными уравнениями, где можно делить одно на другое. Как правильно: разрешены ровно три операции — перестановка строк, умножение строки на ненулевое число, прибавление к строке другой строки, умноженной на число. Умножение на ноль уничтожает уравнение (и решения появляются лишние), деление строки на строку вообще не определено.

Ошибка 4. Путают строку $(0\ 0\ \dots\ 0 \mid 0)$ и строку $(0\ 0\ \dots\ 0 \mid c)$ при $c \ne 0$.

Как выглядит: увидев нулевую слева строку, человек объявляет систему несовместной, не глядя на правую часть — или, наоборот, вычёркивает противоречивую строку как «пустую». Почему возникает: обе строки внешне похожи. Как правильно: строка, нулевая целиком, — это лишнее (зависимое) уравнение, его просто отбрасывают. Строка с нулями слева и ненулём справа — это $0 = c$, приговор системе. Разница в одном числе, а выводы противоположные.

Ошибка 5. Делят на выражение с параметром, не оговорив, что оно не ноль.

Как выглядит: в задаче с параметром появляется преобразование $R_2 \to R_2 - \frac{3}{a-2}R_1$, а потом отдельно разбирается случай $a = 2$ — на основе матрицы, которая была получена незаконным делением. Почему возникает: желание довести прямой ход до конца одной формулой. Как правильно: либо переставить строки так, чтобы ведущим оказался числовой элемент (как в примере 14 и задании 25), либо честно зафиксировать «дальше считаем $a \ne 2$» и разобрать случай $a = 2$ с самого начала, подставив значение параметра в исходную систему.

Ошибка 6. Объявляют свободными не те переменные.

Как выглядит: в ступенчатой матрице ведущие элементы стоят в столбцах 1 и 3, а человек по привычке берёт свободной последнюю переменную $x_3$. Почему возникает: в большинстве учебных примеров свободные переменные действительно оказываются последними, и это запоминается как правило. Как правильно: свободные — это переменные, чьи столбцы не содержат ведущих элементов, и никак иначе. Посмотри на позиции пивотов и выпиши номера «пропущенных» столбцов; в sympy их выдаёт второй элемент результата rref().

Ошибка 7. Проверяют ответ подстановкой только в первое уравнение.

Как выглядит: ответ подставлен в первую строку, сошёлся, задача сдана — а ошибка была в третьей строке. Почему возникает: экономия времени. Как правильно: проверять во все уравнения исходной системы (не преобразованной!). Для параметрических задач — ещё и в двух-трёх конкретных значениях параметра по обе стороны от критического. Проверка стоит минуту, а ловит львиную долю арифметических ошибок.

Ошибка 8. Считают, что нулевой ведущий элемент означает «система решений не имеет».

Как выглядит: увидев ноль в очередной позиции пивота, человек останавливается и пишет «несовместна». Почему возникает: смешение двух разных ситуаций. Как правильно: ноль в позиции ведущего элемента означает всего лишь «нужно поискать замену». Если ниже в этом столбце есть ненулевой элемент — переставляем строки и продолжаем. Если весь столбец нулевой — соответствующая переменная свободна, переходим к следующему столбцу. Несовместность распознаётся только по противоречивой строке, и никак иначе.

Ошибка 9. В машинных вычислениях используют наивный Гаусс без выбора главного элемента.

Как выглядит: самописная функция gauss(A, b) даёт правильные ответы на учебных примерах и бессмысленные — на реальных данных. Почему возникает: на бумаге pivoting не нужен, поэтому его не переносят в код. Как правильно: в численном коде на каждом шаге выбирать ведущим элемент с наибольшим модулем в столбце. А лучше — не писать Гаусса самому, а вызывать numpy.linalg.solve или scipy.linalg.solve.

Ошибка 10. Пишут np.linalg.inv(A) @ b вместо np.linalg.solve(A, b).

Как выглядит: код работает, но втрое медленнее и точнее не становится. Почему возникает: буквальный перенос формулы $x = A^{-1}b$ из учебника в код. Как правильно: solve дешевле (примерно $\frac23 n^3$ против $2n^3$) и численно надёжнее, потому что делает меньше операций. Явная обратная матрица нужна лишь тогда, когда сама $A^{-1}$ является ответом задачи.

Главное запомнить

• Метод Гаусса состоит из двух этапов: прямой ход приводит расширенную матрицу $[A \mid b]$ к ступенчатому виду, обратный ход находит неизвестные снизу вверх.

• Прямой ход использует только три элементарных преобразования строк (перестановка, умножение на ненулевое число, прибавление кратной строки), и все они сохраняют множество решений системы.

• Ведущий элемент (пивот) — первый ненулевой элемент строки; вокруг него обнуляется весь столбец ниже с помощью преобразований $R_i \to R_i - m_i R_k$, где $m_i = a_{ik}/a_{kk}$.

• Три исхода прямого хода читаются прямо по ступенчатой матрице: строка $(0\ \dots\ 0 \mid c)$, $c \ne 0$ — система несовместна; число ведущих элементов равно числу неизвестных — единственное решение; ведущих меньше, чем неизвестных — бесконечно много решений и $n - r$ свободных переменных.

• Нулевой ведущий элемент — не поломка, а повод переставить строки. Если весь столбец нулевой, соответствующая переменная свободна, и мы переходим к следующему столбцу.

• Метод Гаусса — Жордана доводит матрицу до приведённого ступенчатого вида (RREF), где все ведущие элементы равны единице и являются единственными ненулевыми в своих столбцах. RREF единственный для данной матрицы; в sympy его даёт Matrix.rref().

• В задачах с параметром прямой ход ведут без деления на выражения с параметром, а критические значения ищут как корни ведущего элемента последней строки; они же — корни уравнения $\det A = 0$ для квадратной системы.

• Прямой ход стоит $\approx \frac23 n^3$ операций, обратный — $\approx n^2$. Удвоение размера системы увеличивает время примерно в 8 раз.

• Если правых частей несколько, а матрица одна, прямой ход достаточно выполнить один раз — на этой идее построено LU-разложение.

• В машинной арифметике деление на маленький ведущий элемент разрушает точность. Лечение — частичный выбор главного элемента: ведущим берут максимальный по модулю элемент столбца.

• В реальном коде системы решают вызовом numpy.linalg.solve (внутри — Гаусс с pivoting из LAPACK), а не вычислением обратной матрицы: solve втрое дешевле и надёжнее, чем inv с последующим умножением.

Связь с другими темами курса

Что нужно было знать до этого урока

Из урока 157 про операции над матрицами пришла матричная запись системы $Ax = b$ — без неё пришлось бы каждый раз выписывать уравнения полностью. Из урока 162 про ранг матрицы — понятие элементарных преобразований и ступенчатого вида: прямой ход метода Гаусса и есть процедура нахождения ранга, просто применённая к расширенной матрице. Из урока 161 про обратную матрицу — идея метода Гаусса — Жордана в форме $(A \mid E) \to (E \mid A^{-1})$; в этом уроке мы применили ту же схему не к единичной матрице справа, а к столбцу свободных членов. И, конечно, из урока 163 — вся теория совместности: теорема Кронекера — Капелли, деление переменных на базисные и свободные, общее и частное решение. Метод Гаусса — это вычислительная реализация той теории.

Что изучить дальше

В уроке 165 про правило Крамера ты увидишь альтернативный, формульный способ решения систем через определители — красивый, но применимый только к квадратным невырожденным системам и катастрофически дорогой при больших $n$; сравнение стоимости с методом Гаусса там будет отдельной темой. В уроке 166 про матричный метод разберётся формула $x = A^{-1}b$ и появится количественная мера чувствительности системы к возмущениям — та самая, которой нам не хватило в разделе про устойчивость. В уроке 167 про однородные системы метод Гаусса станет инструментом для построения фундаментальной системы решений уравнения $Ax = 0$: то, что мы в задании 26 записали как «все решения пропорциональны вектору $(-1,1,1)$», получит там строгую формулировку и общую теорию. Дальше, в темах про векторные пространства, ступенчатый вид окажется способом находить базис пространства строк, а в разделах про разложения матриц (LU, QR и далее) выяснится, что прямой ход метода Гаусса — это по сути и есть построение LU-разложения, только выброшенное в мусор, вместо того чтобы быть сохранённым.

Где это нужно в жизни

💻 Программирование. Любая работа с матрицами упирается в решение систем: numpy.linalg.solve, scipy.linalg.lu_factor, torch.linalg.solve — всё это метод Гаусса с pivoting. Понимание алгоритма позволяет читать сообщения об ошибках («Singular matrix» — это про нулевой ведущий элемент), выбирать правильную функцию (solve вместо inv) и оценивать, потянет ли задача заданный размер.

🤖 ML/AI. Линейная регрессия через нормальные уравнения, гребневая регрессия, шаг метода Ньютона в оптимизации, обновление в фильтре Калмана, вычисление стационарного распределения марковской цепи — везде под капотом решение линейной системы. Понимание, почему при мультиколлинеарности solve падает с ошибкой, экономит часы отладки.

📊 Data Science. Балансировка потоков, восстановление пропущенных значений через линейные ограничения, межотраслевые балансы (модель Леонтьева — это буквально система $x = Ax + d$), калибровка моделей по нескольким условиям одновременно. Многие «формулы из статьи» на практике реализуются как одна строка solve.

🔬 Наука. Метод конечных элементов и метод конечных разностей превращают дифференциальные уравнения в огромные линейные системы. Балансировка химических реакций, расчёт цепей по законам Кирхгофа, определение орбит по наблюдениям — исторически именно последняя задача и породила метод Гаусса.

💰 Финансы. Составление портфеля с заданными характеристиками, построение кривой доходности по нескольким инструментам, распределение затрат между подразделениями по внутренним расчётам — задачи, естественно формулируемые как система линейных уравнений с ограничениями.

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

• Методу больше двух тысяч лет. В китайском трактате «Математика в девяти книгах» (около II века до н. э.) восьмая глава «Фан чэн» описывает решение систем из трёх и более линейных уравнений раскладкой счётных палочек в прямоугольную таблицу и последовательным вычитанием столбцов. Это в точности прямой ход метода Гаусса, изложенный за восемнадцать веков до рождения Гаусса — и без единого алгебраического символа.

• Гаусс не считал это своим достижением. Он применял исключение неизвестных как рабочий инструмент при обработке астрономических и геодезических измерений методом наименьших квадратов и никогда не оформлял процедуру как отдельный «метод». Название Gaussian elimination закрепилось лишь в середине XX века, когда с появлением ЭВМ понадобилось систематизировать численные алгоритмы.

• Метод Гаусса — это официальный тест производительности суперкомпьютеров. Рейтинг TOP500 строится по результатам бенчмарка HPL (High Performance Linpack), который решает большую плотную систему линейных уравнений методом Гаусса с частичным выбором главного элемента. Производительность в этом тесте считают по формуле $\frac23 n^3 + 2n^2$ операций — той самой оценке, которую мы вывели в этом уроке.

• У частичного pivoting есть страшный теоретический худший случай. Джеймс Уилкинсон построил матрицы, на которых элементы в процессе исключения растут в $2^{n-1}$ раз даже при выборе максимального элемента столбца, — для $n = 60$ это множитель порядка $10^{18}$, полная потеря точности. При этом за десятилетия практического использования такие матрицы почти никогда не встречались в реальных задачах. Расхождение между теоретическим худшим случаем и практическим поведением алгоритма остаётся одним из самых известных открытых сюжетов численного анализа.

• Гаусс — Жордана назван по геодезисту, и он дороже обычного Гаусса. Вильгельм Жордан, придумавший «доисключение вверх», был профессором геодезии, а не чистым математиком, и его интересовала обработка измерений вручную. Его схема требует примерно $n^3$ операций против $\frac23 n^3$ у связки «прямой + обратный ход» — то есть на 50% больше. Поэтому в вычислительных библиотеках Гаусса — Жордана для решения систем не используют: он живёт в учебниках и в системах символьных вычислений, где важна каноничность формы, а не скорость.

Лайфхаки и полезные трюки

1. Ставь наверх строку с единицей. Перед началом прямого хода посмотри на первый столбец: если где-то есть $1$ или $-1$, переставь эту строку наверх. Множители $m_i$ станут целыми, и дробей в вычислениях будет в разы меньше. Пример из урока: в системе с ведущим элементом $2$ мы переставили строки и весь дальнейший счёт шёл в целых числах.

2. Сокращай строки на общий множитель. Строку $(0, -5, -5 \mid -25)$ можно смело поделить на $-5$ и получить $(0, 1, 1 \mid 5)$. Это разрешённое элементарное преобразование, и оно радикально упрощает следующие шаги. Главное — не забыть про правую часть.

3. Считай в обыкновенных дробях, а не в десятичных. $\frac{11}{3}$ точно, $3{,}67$ — уже нет. Округление на промежуточном шаге вручную приводит ровно к тем же эффектам, что мы разбирали в разделе про численную устойчивость, только заметнее. Десятичные дроби оставь для финального ответа.

4. Проверяй ответ подстановкой в исходную систему, а не в преобразованную. Если ошибка была в самом первом преобразовании, проверка по промежуточной матрице её не поймает — там всё «сходится». Подставляй только в те уравнения, что даны в условии.

5. В параметрических задачах избегай ведущих элементов с параметром. Если во втором столбце стоят элементы $a$ и $2$, бери ведущим двойку и переставляй строки. Тогда не придётся оговаривать «при $a \ne 0$» и потом отдельно разбирать этот случай — критические значения проявятся сами собой в последней строке.

6. Для параметрических задач сверяйся с определителем. Корни уравнения $\det A(a) = 0$ — это полный список подозрительных значений параметра. Если после прямого хода твой ведущий элемент последней строки обнуляется не при тех значениях, ты где-то ошибся в арифметике.

7. Проверяй общее решение при двух значениях параметра. Формула вида $(1 - 2t,\ t,\ 1)$ часто «случайно» верна при $t = 0$ и неверна вообще. Подставь $t = 0$ и $t = 1$ (или $t = 2$) — вторая проверка ловит почти все ошибки в выражении базисных переменных через свободные.

8. Сверяйся с sympy, пока набиваешь руку. Matrix([[...]]).rref() даёт приведённый ступенчатый вид расширенной матрицы и кортеж номеров ведущих столбцов, а linsolve((A, b), x, y, z) — готовое общее решение с параметрами. Расхождение с твоим ответом — сигнал искать арифметическую ошибку (и почти всегда она у человека, а не у sympy).

Метод Гаусса — редкий случай, когда учебный алгоритм и промышленный алгоритм — это буквально одно и то же. Тот же прямой ход, который ты только что тридцать раз проделал руками на матрицах $3\times 3$, крутится внутри LAPACK на матрицах $30\,000 \times 30\,000$, и единственное существенное отличие промышленной версии — выбор главного элемента, о котором мы отдельно поговорили. Это даёт неплохую перспективу: научившись решать системы аккуратно и понимая, где алгоритм спотыкается, ты понимаешь не «школьный приём», а рабочий инструмент, на котором держится вычислительная линейная алгебра. В следующем уроке мы посмотрим на альтернативу — правило Крамера, дающее решение готовой формулой через определители, — и заодно разберёмся, почему эта красивая формула проиграла методу Гаусса в реальных вычислениях с разгромным счётом.