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

Метод Гаусса — Йордана використовується для розв'язання систем лінійних алгебраїчних рівнянь, знаходження оберненої матриці, знаходження координат вектора у заданому базисі, відшукання рангу матриці. Метод є модифікацією методу Гаусса. Названий на честь Карла Фрідріха Гаусса та німецького математика та геодезиста Вільгельма Йордана.

Алгоритм

1. Обирається перша зліва колонка, що містить хоч одне ненульове значення.
2. Якщо верхнє число у цій колонці — нуль, то обмінюється увесь перший рядок матриці з іншим рядком матриці, де у цій колонці нема нуля.
3. Усі елементи першого рядка діляться на верхній елемент обраної колонки.
4. Від рядків, що залишились, віднімається перший рядок, помножений на перший елемент відповідного рядка, з метою отримання нуля в першому елементі кожного рядка (крім першого).
5. Далі, повторюємо ці операції із матрицею, отриманою з початкової матриці після викреслювання першого рядка та першого стовпчика.
6. Після повторення операцій n − 1 разів отримаємо верхню трикутну матрицю.
7. Віднімаємо від передостаннього рядка останній рядок, помножений на відповідний коефіцієнт, щоб у передостанньому рядку залишилась лише 1 на головній діагоналі.
8. Повторюємо попередній крок для наступних рядків. У результаті отримуємо одиничну матрицю і рішення на місці вільного вектора (над ним необхідно виконувати ті самі перетворення).

Розгорнутий алгоритм для знаходження оберненої матриці

Нехай дано:

$A=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right)a_{ii}\ne 0I=\left(\begin{array}{cccc}1& 0& \cdots & 0\\ 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right)$

Прямий хід (алгоритм утворення нулів під головною діагоналлю)

• Поділимо перший рядок матриці А на $a_{11}$ отримаємо: $a_{1j}^1=\frac{a_{1j}}{a_{11}}$, j — стовпець матриці А.

• Повторюємо дії для матриці I, за формулою: $b_{1s}^1=\frac{b_{1s}}{a_{11}}$, s — стовпець матриці I.

Отримаємо:

$A=\left(\begin{array}{cccc}1& a_{12}^1& \cdots & a_{1n}^1\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right)I=\left(\begin{array}{cccc}{b}_{11}^1& 0& \cdots & 0\\ 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right)$

• Будемо утворювати 0 у першому стовпці: $a_{2j}^1=a_{2j}-a_{1j}^1{a}_{21}\dots a_{nj}^1=a_{nj}-a_{1j}^1{a}_{n1}$.
• Повторюємо дії для матриці І, за формулами : $b_{2s}^1=b_{2s}-b_{1s}^1{a}_{21}\dots b_{ns}^1=b_{ns}-b_{1s}^1{a}_{n1}$

Отримаємо:

$A=\left(\begin{array}{cccc}1& a_{12}^1& \cdots & a_{1n}^1\\ 0& a_{22}^1& \cdots & a_{2n}^1\\ ⋮& ⋮& \ddots & ⋮\\ 0& a_{2n}^1& \cdots & a_{nn}^1\end{array}\right)I=\left(\begin{array}{cccc}{b}_{11}^1& 0& \cdots & 0\\ b_{21}^1& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ b_{n1}^1& 0& \cdots & 1\end{array}\right)$

• Продовжуємо виконувати аналогічні операції використовуючи формули : $a_{ij}^k=\frac{a_{ij}^k}{a_{ii}}{a}_{ij}^k=a_{ij}^{k-1}-a_{kj}^k{a}_{ik}^{k-1}$

за умови, що $k=1\to n,i=k+1\to n,j=1\to n$

• Повторюємо дії для матриці І, за формулами : $b_{ik}^k=\frac{b_{ik}^k}{a_{ii}}{b}_{is}^k=b_{is}^{k-1}-b_{ks}^k{a}_{ik}^{k-1}$

за умови, що $k=1\to n,i=k+1\to n,s=1\to n$.

Отримаємо:

$A=\left(\begin{array}{cccc}1& a_{12}^1& \cdots & a_{1n}^1\\ 0& 1& \cdots & a_{2n}^2\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right)I=\left(\begin{array}{cccc}{b}_{11}^1& 0& \cdots & 0\\ b_{21}^2& b_{22}^2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ b_{n1}^n& b_{n2}^n& \cdots & b_{nn}^n\end{array}\right)$

Зворотний хід (алгоритм утворення нулів над головною діагоналлю)

Використаємо формулу: $a_{ij}^{k-1}=a_{ij}^{k-1}-a_{ij}^k{a}_{ik}^i$, при умові, що $k=n\to 1,i=1\to k-1,j=1\to n$.

Повторюємо дії для матриці І, за формулою $b_{is}^{k-1}=b_{is}^{k-1}-b_{is}^k{a}_{ik}^i$, за умови, що $k=n\to 1,i=1\to k-1,s=1\to n$.

Остаточно отримуємо:

$A=\left(\begin{array}{cccc}1& 0& \cdots & 0\\ 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right)I=A^{-1}$

Приклад

Розв'яжемо систему рівнянь:

$\{\begin{array}{ccccccc}a& +& b& +& c& =& 0\\ 4a& +& 2b& +& c& =& 1\\ 9a& +& 3b& +& c& =& 3\end{array}$

Запишемо її у вигляді матриці 3×4, де останній стовпчик є вільним членом:

$\left(\begin{array}{ccccc}1& 1& 1& |& 0\\ 4& 2& 1& |& 1\\ 9& 3& 1& |& 3\end{array}\right)$

Виконаємо такі дії:

• До рядка 2 додамо: -4 * рядок 1.
• До рядка 3 додамо: -9 * рядок 1.

Отримаємо:

$\left(\begin{array}{ccccc}1& 1& 1& |& 0\\ 0& -2& -3& |& 1\\ 0& -6& -8& |& 3\end{array}\right)$

• До рядка 3 додамо: -3 * рядок 2.
• Рядок 2 ділимо на -2

$\left(\begin{array}{ccccc}1& 1& 1& |& 0\\ 0& 1& \frac{3}{2}& |& -\frac{1}{2}\\ 0& 0& 1& |& 0\end{array}\right)$

• До рядка 1 додамо: -1 * рядок 3.
• До рядка 2 додамо: -3/2 * рядок 3.

$\left(\begin{array}{ccccc}1& 1& 0& |& 0\\ 0& 1& 0& |& -\frac{1}{2}\\ 0& 0& 1& |& 0\end{array}\right)$

• До рядка 1 додамо: -1 * рядок 2.

$\left(\begin{array}{ccccc}1& 0& 0& |& \frac{1}{2}\\ 0& 1& 0& |& -\frac{1}{2}\\ 0& 0& 1& |& 0\end{array}\right)$

У правому стовпчику отримаємо рішення:

$a=\frac{1}{2};b=-\frac{1}{2};c=0$ .

Джерела

• Шаблон:Гантмахер.Теорія матриць
• Шаблон:Гельфанд.Линейная алгебра
• Шаблон:Мальцев.Основы линейной алгебры
• Рокіцький І. О. Застосування лінійної алгебри // І. О. Рокіцький, О. Б. Панасенко. — Вінниця: Вид. Главацька Р. В., 2012. — С. 144

Посилання

• 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