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

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

Алгоритм

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

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

Нехай дано:
$A={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{pmatrix}}\quad a_{ii}\neq 0\quad I={\begin{pmatrix}1&0&\cdots &0\\0&1&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &1\end{pmatrix}}$

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

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

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

Отримаємо:
$A={\begin{pmatrix}1&a_{12}^{1}&\cdots &a_{1n}^{1}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{pmatrix}}\qquad I={\begin{pmatrix}b_{11}^{1}&0&\cdots &0\\0&1&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &1\end{pmatrix}}$

• Будемо утворювати 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={\begin{pmatrix}1&a_{12}^{1}&\cdots &a_{1n}^{1}\\0&a_{22}^{1}&\cdots &a_{2n}^{1}\\\vdots &\vdots &\ddots &\vdots \\0&a_{2n}^{1}&\cdots &a_{nn}^{1}\end{pmatrix}}\qquad I={\begin{pmatrix}b_{11}^{1}&0&\cdots &0\\b_{21}^{1}&1&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\b_{n1}^{1}&0&\cdots &1\end{pmatrix}}$

• Продовжуємо виконувати аналогічні операції використовуючи формули : $a_{ij}^{k}={\frac {a_{ij}^{k}}{a_{ii}}}\qquad 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}}}\qquad 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={\begin{pmatrix}1&a_{12}^{1}&\cdots &a_{1n}^{1}\\0&1&\cdots &a_{2n}^{2}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &1\end{pmatrix}}\qquad I={\begin{pmatrix}b_{11}^{1}&0&\cdots &0\\b_{21}^{2}&b_{22}^{2}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\b_{n1}^{n}&b_{n2}^{n}&\cdots &b_{nn}^{n}\end{pmatrix}}$

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

Використаємо формулу: $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={\begin{pmatrix}1&0&\cdots &0\\0&1&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &1\end{pmatrix}}\qquad I=A^{-1}$

Приклад

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

$\left\{{\begin{array}{ccccccl}a&+&b&+&c&=&0\\4a&+&2b&+&c&=&1\\9a&+&3b&+&c&=&3\end{array}}\right.$

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

${\begin{pmatrix}1&1&1&|&0\\4&2&1&|&1\\9&3&1&|&3\end{pmatrix}}$

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

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

Отримаємо:

${\begin{pmatrix}1&\ 1&\ 1&|&0\\0&-2&-3&|&1\\0&-6&-8&|&3\end{pmatrix}}$

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

${\begin{pmatrix}1&1&1&|&\ 0\\0&1&{3 \over 2}&|&-{1 \over 2}\\0&0&1&|&\ 0\end{pmatrix}}$

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

${\begin{pmatrix}1&1&0&|&\ 0\\0&1&0&|&-{1 \over 2}\\0&0&1&|&\ 0\end{pmatrix}}$

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

${\begin{pmatrix}1&0&0&|&\ {1 \over 2}\\0&1&0&|&-{1 \over 2}\\0&0&1&|&\ 0\end{pmatrix}}$

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

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

Джерела

• Гельфанд И. М. Лекции по линейной алгебре. — 5-е. — Москва : Наука, 1998. — 320 с. — ISBN 5791300158.(рос.)
• Мальцев А. И. Основы линейной алгебры. — 3-е изд. — Новосибирск : Наука, 1970. — 400 с.(рос.)

Посилання

• 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