Метод Гаусса — Жордана¶

Метод Гаусса — Жордана (также известный как метод полного исключения) — это алгоритм решения систем линейных алгебраических уравнений (СЛАУ), нахождения обратной матрицы и вычисления ранга матрицы. Является модификацией классического метода Гаусса, отличающейся тем, что преобразования проводятся не только для приведения матрицы к треугольному виду, но и для получения единичной матрицы. В результате система приводится к виду, из которого решение читается непосредственно, без обратного хода.

¶История

Метод назван в честь двух математиков: Карла Фридриха Гаусса (1777–1855) и Вильгельма Йордана (1842–1899). Гаусс разработал метод последовательного исключения переменных (метод Гаусса) в начале XIX века, который использовался для обработки геодезических данных и решения задач методом наименьших квадратов. В 1888 году немецкий геодезист и математик Вильгельм Йордан опубликовал работу, в которой предложил модификацию, позволяющую получать решение без обратного хода, — так называемый метод Гаусса — Жордана. В англоязычной литературе метод иногда ошибочно связывают с именем французского математика Камиля Жордана (из-за схожести фамилий), однако исторически приоритет принадлежит именно Вильгельму Йордану.

¶Описание алгоритма

Метод Гаусса — Жордана основан на элементарных преобразованиях строк расширенной матрицы системы. Эти преобразования включают:

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

Цель преобразований — привести расширенную матрицу к приведённому ступенчатому виду (reduced row echelon form, RREF), где:

• каждый ненулевой ряд начинается с единицы (ведущий элемент);
• ведущий элемент является единственным ненулевым элементом в своём столбце;
• все строки, состоящие только из нулей, находятся внизу.

¶Алгоритм для решения СЛАУ

1. Запись расширенной матрицы: составляется матрица, объединяющая матрицу коэффициентов системы и столбец свободных членов.
2. Прямой ход (исключение): для каждого столбца слева направо выбирается ведущий элемент (первый ненулевой элемент в текущей строке, начиная с верхней). Если ведущий элемент равен нулю, строки переставляются. Затем ведущий элемент приводится к единице делением всей строки на его значение. После этого из всех остальных строк (выше и ниже) вычитается текущая строка, умноженная на соответствующий коэффициент, чтобы обнулить все элементы в данном столбце, кроме ведущего.
3. Завершение: после обработки всех столбцов матрица приводится к единичной (если система имеет единственное решение). В столбце свободных членов получаются значения переменных.

¶Пример

Рассмотрим систему: `` x + 2y = 5 3x + 4y = 11 ``

Расширенная матрица: `` [1 2 | 5] [3 4 | 11] ``

1. Ведущий элемент первой строки — 1. Обнуляем элемент под ним: вычитаем из второй строки первую, умноженную на 3:

`` [1 2 | 5] [0 -2 | -4] ``

1. Делим вторую строку на -2:

`` [1 2 | 5] [0 1 | 2] ``

1. Обнуляем элемент над ведущим (второй столбец, первая строка): вычитаем из первой строки вторую, умноженную на 2:

`` [1 0 | 1] [0 1 | 2] `` Решение: x = 1, y = 2.

¶Применение метода

¶Решение систем линейных уравнений

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

¶Нахождение обратной матрицы

Для вычисления обратной матрицы A⁻¹ расширенная матрица формируется как [A | I], где I — единичная матрица того же размера. После приведения левой части к единичной матрице правая часть становится обратной матрицей. Если в процессе преобразований появляется нулевая строка в левой части, матрица A является вырожденной (не имеет обратной).

¶Вычисление ранга матрицы

Ранг матрицы равен количеству ненулевых строк в её приведённом ступенчатом виде. Метод Гаусса — Жордана позволяет эффективно определить ранг, так как после приведения к RREF все ненулевые строки линейно независимы.

¶Сравнение с методом Гаусса

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

¶Вычислительные аспекты

¶Численная устойчивость

При реализации на компьютере метод Гаусса — Жордана чувствителен к ошибкам округления. Для повышения устойчивости применяется выбор ведущего элемента:

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

¶Сложность

Алгоритмическая сложность метода Гаусса — Жордана составляет O(n³) операций для матрицы размера n×n. Для сравнения, метод Гаусса с обратным ходом имеет сложность O(2n³/3), что примерно на треть меньше.

¶Использование в компьютерной алгебре

Метод реализован во многих системах компьютерной алгебры, таких как MATLAB, GNU Octave, Mathematica, Maple, а также в библиотеках для Python (NumPy, SymPy). В этих системах функция приведения к RREF обычно называется rref или RowReduce.

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

• В некоторых учебниках метод Гаусса — Жордана называют «методом полного исключения», а классический метод Гаусса — «методом последовательного исключения».
• Метод может быть использован для решения не только СЛАУ, но и для проверки линейной зависимости векторов, нахождения базиса линейной оболочки и решения матричных уравнений.
• В 2010 году математик Джон Дербишир в своей книге «Простая одержимость» отметил, что метод Гаусса — Жордана является одним из самых фундаментальных алгоритмов линейной алгебры, лежащих в основе многих численных методов.

¶Критика

Несмотря на широкую распространённость, метод Гаусса — Жордана критикуется за избыточность вычислений при решении больших систем. Для задач с тысячами неизвестных предпочтительнее использовать итерационные методы (например, метод Якоби или метод Гаусса — Зейделя) или прямые методы с разреженными матрицами. Кроме того, при ручном счёте метод может быть более трудоёмким из-за необходимости обнулять элементы как ниже, так и выше ведущего.

¶Источники

• Гантмахер Ф. Р. Теория матриц. — М.: Наука, 1967.
• Ильин В. А., Позняк Э. Г. Линейная алгебра. — М.: Физматлит, 2004.
• Беклемишев Д. В. Курс аналитической геометрии и линейной алгебры. — М.: Физматлит, 2005.
• Strang G. Introduction to Linear Algebra. — 5th ed. — Wellesley-Cambridge Press, 2016.
• Jordan W. Handbuch der Vermessungskunde. — 1888.