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

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

Алгоритм

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 с.(рос.)
• Рокіцький І. О. Застосування лінійної алгебри // І. О. Рокіцький, О. Б. Панасенко. — Вінниця: Вид. Главацька Р. В., 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