Последовательное исключение

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

История

Идея последовательного исключения неизвестных восходит к древнекитайской математике. В трактате «Математика в девяти книгах» (ок. II века до н. э.) содержались задачи, решаемые с помощью процедуры, аналогичной современному методу Гаусса. В Европе систематическое изложение метода впервые дал немецкий математик Карл Фридрих Гаусс в начале XIX века в работе «Disquisitiones generales circa seriem infinitam…» (1812). Гаусс использовал исключение для решения задач астрономии и геодезии, в частности для определения орбит астероидов. Позднее, в 1887 году, немецкий математик Вильгельм Йордан внёс усовершенствование, предложив после прямого хода выполнять обратный ход с приведением матрицы к единичной — так возник метод Гаусса — Жордана.

Основные понятия

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

\[ \begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2 \\ \dots \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m \end{cases} \]

где \(a_{ij}\) — коэффициенты, \(x_j\) — неизвестные, \(b_i\) — свободные члены, \(m\) — число уравнений, \(n\) — число неизвестных. Системе ставится в соответствие расширенная матрица размером \(m \times (n+1)\):

\[ \left(\begin{array}{cccc|c} a_{11} & a_{12} & \dots & a_{1n} & b_1 \\ a_{21} & a_{22} & \dots & a_{2n} & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} & b_m \end{array}\right) \]

Элементарные преобразования строк, не меняющие множества решений системы, включают:

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

Алгоритм метода Гаусса

Прямой ход

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

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

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

Обратный ход

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

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

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

Пример

Рассмотрим систему:

\[ \begin{cases} 2x + 3y - z = 1 \\ 4x + y + 2z = 3 \\ -2x + 5y + z = 2 \end{cases} \]

Расширенная матрица:

\[ \left(\begin{array}{ccc|c} 2 & 3 & -1 & 1 \\ 4 & 1 & 2 & 3 \\ -2 & 5 & 1 & 2 \end{array}\right) \]

Прямой ход:

• Ведущий элемент — 2. Делим первую строку на 2: \(\left(\begin{array}{ccc|c}1 & 1.5 & -0.5 & 0.5 \\ 4 & 1 & 2 & 3 \\ -2 & 5 & 1 & 2\end{array}\right)\).
• Обнуляем элементы ниже: из второй строки вычитаем первую, умноженную на 4; из третьей — первую, умноженную на -2. Получаем: \(\left(\begin{array}{ccc|c}1 & 1.5 & -0.5 & 0.5 \\ 0 & -5 & 4 & 1 \\ 0 & 8 & 0 & 3\end{array}\right)\).
• Ведущий элемент во второй строке — -5. Делим на -5: \(\left(\begin{array}{ccc|c}1 & 1.5 & -0.5 & 0.5 \\ 0 & 1 & -0.8 & -0.2 \\ 0 & 8 & 0 & 3\end{array}\right)\).
• Обнуляем элемент ниже: из третьей строки вычитаем вторую, умноженную на 8: \(\left(\begin{array}{ccc|c}1 & 1.5 & -0.5 & 0.5 \\ 0 & 1 & -0.8 & -0.2 \\ 0 & 0 & 6.4 & 4.6\end{array}\right)\).

Обратный ход:

• Из третьей строки: \(6.4z = 4.6 \Rightarrow z = 0.71875\).
• Из второй: \(y - 0.8 \cdot 0.71875 = -0.2 \Rightarrow y = 0.375\).
• Из первой: \(x + 1.5 \cdot 0.375 - 0.5 \cdot 0.71875 = 0.5 \Rightarrow x = 0.25\).

Решение: \(x = 0.25\), \(y = 0.375\), \(z = 0.71875\).

Классификация

Последовательное исключение может быть реализовано в различных модификациях в зависимости от целей и условий:

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

Применение

Последовательное исключение используется в широком спектре задач:

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

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

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

• Частичный выбор — в текущем столбце выбирается максимальный по модулю элемент.
• Полный выбор — максимальный элемент ищется во всей оставшейся подматрице.

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

Ограничения

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

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

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

• В 1947 году американский математик Джон фон Нейман впервые реализовал метод Гаусса на компьютере ENIAC для решения систем с 20 неизвестными.
• Метод Гаусса — Жордана используется в некоторых алгоритмах машинного обучения, например, при вычислении псевдообратной матрицы Мура — Пенроуза.
• В китайской математике метод последовательного исключения назывался «фан-чэн» (метод прямоугольных таблиц) и применялся для решения задач с 3–5 неизвестными.
• Число операций в методе Гаусса для системы \(n\) уравнений составляет примерно \(\frac{2}{3}n^3\) для прямого хода и \(\frac{1}{2}n^2\) для обратного.

Источники

• Гантмахер Ф. Р. Теория матриц. — М.: Наука, 1967.
• Стренг Г. Линейная алгебра и её применения. — М.: Мир, 1980.
• Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.: Бином, 2008.
• Golub G. H., Van Loan C. F. Matrix Computations. — 4th ed. — Johns Hopkins University Press, 2013.
• «Математика в девяти книгах» (перевод с китайского). — М.: Наука, 1974.