Метод Гаусса

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

История

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

В европейской математике метод последовательного исключения неизвестных впервые систематически описал Исаак Ньютон в своей работе «Всеобщая арифметика» (1707 год). Однако широкое распространение алгоритм получил после работ Карла Фридриха Гаусса, который в начале XIX века разработал его для решения задач астрономии и геодезии, в частности для вычисления орбит небесных тел. Гаусс не только формализовал процесс исключения, но и предложил способ оценки точности решения. Впоследствии метод был усовершенствован немецким математиком Вильгельмом Йорданом, который в 1888 году предложил модификацию, известную как метод Гаусса — Жордана, позволяющую получать не ступенчатую, а единичную матрицу.

Основная идея и алгоритм

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

Прямой ход (исключение)

Цель прямого хода — привести расширенную матрицу к ступенчатому (или треугольному) виду. Для этого выполняются элементарные преобразования строк:

1. Перестановка строк — меняются местами две строки матрицы.
2. Умножение строки на ненулевое число — каждый элемент строки умножается на одно и то же число.
3. Прибавление к одной строке другой строки, умноженной на число — к элементам одной строки поэлементно прибавляются элементы другой строки, умноженные на некоторый коэффициент.

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

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

Обратный ход (подстановка)

После приведения матрицы к ступенчатому виду система уравнений принимает вид, где из последнего уравнения можно сразу выразить одну переменную. Затем, подставляя её в предыдущие уравнения, последовательно находят все остальные неизвестные. Этот процесс называется обратным ходом.

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

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

Классификация систем по методу Гаусса

В процессе применения метода Гаусса можно определить тип системы линейных уравнений:

• Совместная и определённая: после приведения к ступенчатому виду количество ненулевых строк равно числу неизвестных. Система имеет единственное решение.
• Совместная и неопределённая: количество ненулевых строк меньше числа неизвестных. В этом случае некоторые переменные (свободные) можно выразить через другие (базисные), и система имеет бесконечно много решений.
• Несовместная: в процессе преобразований появляется строка, где все коэффициенты при неизвестных равны нулю, а свободный член отличен от нуля (например, 0x + 0y + 0z = 5). Такая система не имеет решений.

Вычислительная сложность

Метод Гаусса является алгоритмом с кубической сложностью. Для системы из n уравнений с n неизвестными количество арифметических операций (умножений и сложений) составляет примерно 2n³/3. Это делает его эффективным для систем с числом уравнений до нескольких тысяч. Для очень больших систем (сотни тысяч и миллионы уравнений) используются итерационные методы, такие как метод Якоби или метод Гаусса — Зейделя.

Применение

Метод Гаусса применяется в различных областях:

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

Ограничения и численная устойчивость

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

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

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

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

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

Источники

• Ильин В. А., Позняк Э. Г. Линейная алгебра. — М.: Физматлит, 2004.
• Беклемишев Д. В. Курс аналитической геометрии и линейной алгебры. — М.: Наука, 1984.
• Гантмахер Ф. Р. Теория матриц. — М.: Наука, 1988.
• «Математика в девяти книгах» (Цзю чжан суань шу), перевод и комментарии. — М.: Наука, 1974.
• Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P. Numerical Recipes: The Art of Scientific Computing. — Cambridge University Press, 2007.