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

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

Алгоритм

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

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

Нехай дано:

${\displaystyle 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}}}$

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

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

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

Отримаємо:

${\displaystyle 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 у першому стовпці: ${\displaystyle a_{2j}^{1}=a_{2j}-a_{1j}^{1}a_{21}\;\dots \;a_{nj}^{1}=a_{nj}-a_{1j}^{1}a_{n1}}$.
• Повторюємо дії для матриці І, за формулами : ${\displaystyle b_{2s}^{1}=b_{2s}-b_{1s}^{1}a_{21}\;\dots \;b_{ns}^{1}=b_{ns}-b_{1s}^{1}a_{n1}}$

Отримаємо:

${\displaystyle 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}}}$

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

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

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

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

Отримаємо:

${\displaystyle 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}}}$

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

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

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

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

${\displaystyle 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}}$

Приклад

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

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

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

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

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

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

Отримаємо:

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

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

${\displaystyle {\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.

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

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

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

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

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

Джерела

Посилання

• 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 Python