Метод Гаусса — Жордана (метод полного исключения неизвестных) — метод, который используется для решения квадратных систем линейных алгебраических уравнений, нахождения обратной матрицы, нахождения координат вектора в заданном базисе или отыскания ранга матрицы. Метод является модификацией метода Гаусса. Назван в честь К. Ф. Гаусса и немецкого геодезиста и математика Вильгельма Йордана[1].
Алгоритм
- Выбирают первый слева столбец матрицы, в котором есть хоть одно отличное от нуля значение.
- Если самое верхнее число в этом столбце есть ноль, то меняют всю первую строку матрицы с другой строкой матрицы, где в этой колонке нет нуля.
- Все элементы первой строки делят на верхний элемент выбранного столбца.
- Из оставшихся строк вычитают первую строку, умноженную на первый элемент соответствующей строки, с целью получить первым элементом каждой строки (кроме первой) ноль.
- Далее проводят такую же процедуру с матрицей, получающейся из исходной матрицы после вычёркивания первой строки и первого столбца.
- После повторения этой процедуры раз получают верхнюю треугольную матрицу
- Вычитают из предпоследней строки последнюю строку, умноженную на соответствующий коэффициент, с тем, чтобы в предпоследней строке осталась только 1 на главной диагонали.
- Повторяют предыдущий шаг для последующих строк. В итоге получают единичную матрицу и решение на месте свободного вектора (с ним необходимо проводить все те же преобразования).
- Чтобы получить обратную матрицу, нужно применить все операции в том же порядке к единичной матрице.
Пример
Для решения следующей системы уравнений:
![\left\{\begin{array}{ccccccl}
a &+& b &+& c &=& 0\\
4a &+& 2b &+& c &=& 1\\
9a &+& 3b &+& c &=& 3 \end{array}\right.](//upload.wikimedia.org/math/5/0/6/506a8bdecccefd73b3d8918173793fbd.png)
Запишем её в виде матрицы 3×4, где последний столбец является свободным членом:
![\begin{pmatrix}
1 & 1 & 1 \!& \vline &\! 0 \\
4 & 2 & 1 \!& \vline &\! 1 \\
9 & 3 & 1 \!& \vline &\! 3
\end{pmatrix}](//upload.wikimedia.org/math/9/f/b/9fb4831b49aa2813cfa90d17576af5e6.png)
Проведём следующие действия:
- К строке 2 добавим: −4 × Строку 1.
- К строке 3 добавим: −9 × Строку 1.
Получим:
![\begin{pmatrix}
1 &\ 1 &\ 1 \!& \vline &\! 0 \\
0 & -2 & -3 \!& \vline &\! 1 \\
0 & -6 & -8 \!& \vline &\! 3
\end{pmatrix}](//upload.wikimedia.org/math/2/7/9/2795285936b9bd0d5caf3828453446b8.png)
- К строке 3 добавим: −3 × Строку 2.
- Строку 2 делим на −2
![\begin{pmatrix}
1 & 1 & 1 \!& \vline &\!\ 0 \\
0 & 1 & {3 \over 2} \!& \vline &\! -{1 \over 2} \\
0 & 0 & 1 \!& \vline &\!\ 0
\end{pmatrix}](//upload.wikimedia.org/math/b/1/b/b1bdf8d1b71a04c5d99c22ac1be97c48.png)
- К строке 1 добавим: −1 × Строку 3.
- К строке 2 добавим: −3/2 × Строку 3.
![\begin{pmatrix}
1 & 1 & 0 \!& \vline &\!\ 0 \\
0 & 1 & 0 \!& \vline &\! -{1 \over 2} \\
0 & 0 & 1 \!& \vline &\!\ 0
\end{pmatrix}](//upload.wikimedia.org/math/2/a/7/2a7cc7b1287fb466cd66e38fdba983b8.png)
- К строке 1 добавим: −1 × Строку 2.
![\begin{pmatrix}
1 & 0 & 0 \!& \vline &\!\ {1 \over 2} \\
0 & 1 & 0 \!& \vline &\! -{1 \over 2} \\
0 & 0 & 1 \!& \vline &\!\ 0
\end{pmatrix}](//upload.wikimedia.org/math/c/f/d/cfd16b806ae64cefe362ce4668a50084.png)
В правом столбце получаем решение:
- .
Примечания
- ↑ Транскрипция фамилии Йордан как «Жордан» является ошибочной, но она общепринята и встречается в большинстве русскоязычных источников.
Литература
- Lipschutz, Seymour, and Lipson, Mark. «Schaum’s Outlines: Linear Algebra». Tata McGraw-hill edition. Delhi 2001. pp. 69-80.
Ссылки
Примеры реализации алгоритма:
- Algorithm for Gauss-Jordan elimination in Matlab
- Algorithm for Gauss-Jordan elimination in Python