Метод Гаусса: реализация на Python

Метод Гаусса превращает запутанную систему в простую лесенку, из которой решение читается напрямую.

Метод Гаусса — алгоритм решения систем линейных уравнений путём элементарных преобразований строк, приводящих матрицу к треугольному (или ступенчатому) виду.

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

Разрешённые операции

Над строками системы можно делать три вещи, не меняя множество решений: переставлять строки местами, умножать строку на ненулевое число и прибавлять к одной строке другую, умноженную на число. Цель — обнулить всё под главной диагональю.

Прямой и обратный ход

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

def solve(A, b):
    n = len(A)
    M = [row[:] + [b[i]] for i, row in enumerate(A)]
    for col in range(n):
        # выбор ведущего элемента по максимуму модуля — устойчивость
        piv = max(range(col, n), key=lambda r: abs(M[r][col]))
        M[col], M[piv] = M[piv], M[col]
        pv = M[col][col]
        for r in range(n):
            if r != col and M[r][col] != 0:
                f = M[r][col] / pv
                for c in range(col, n + 1):
                    M[r][c] -= f * M[col][c]
    return [M[i][n] / M[i][i] for i in range(n)]

A = [[2, 1, -1], [-3, -1, 2], [-2, 1, 2]]
b = [8, -11, -3]
x = solve(A, b)
print("x =", [round(v, 4) for v in x])

Вывод:

x = [2.0, 3.0, -1.0]

Проверка

Алгоритм выдал $\vec{x} = (2, 3, -1)$. Подставив в первое уравнение: $2 \cdot 2 + 1 \cdot 3 - 1 \cdot (-1) = 4 + 3 + 1 = 8$ — сходится. Метод Гаусса решил систему $3 \times 3$ за конечное число арифметических действий, без всяких библиотек.

Как работает под капотом

Мы склеиваем матрицу $A$ и вектор $\vec{b}$ в расширенную матрицу $M$ (последний столбец — правая часть). Выбор ведущего элемента по максимальному модулю (partial pivoting) — не каприз, а защита от деления на крошечное число: без него ошибки округления могут раздуться и испортить ответ. После приведения к диагональному виду решение получается простым делением свободного члена на диагональный элемент. Число операций растёт как $n^3$ — кубически от размера системы.

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

Не делать выбор ведущего элемента. На бумаге это допустимо, но в числах с плавающей точкой ведёт к большой потере точности или делению на ноль.
Менять правую часть отдельно от строки. Все операции нужно выполнять над всей расширенной строкой целиком, включая столбец $\vec{b}$.
Применять метод вслепую к вырожденной системе (нулевой определитель). Тогда на диагонали возникает ноль и деление падает — нужно отдельно обрабатывать ранг и совместность.

Итог

Метод Гаусса приводит систему к треугольному/диагональному виду элементарными операциями над строками.
Три операции не меняют множество решений: перестановка, умножение на число, прибавление кратной строки.
Выбор ведущего элемента (pivoting) обеспечивает численную устойчивость.
Сложность — порядка $n^3$ операций.