Обирається перша зліва колонка, що містить хоч одне ненульове значення.
Якщо верхнє число у цій колонці — нуль, то обмінюється увесь перший рядок матриці з іншим рядком матриці, де у цій колонці нема нуля.
Усі елементи першого рядка діляться на верхній елемент обраної колонки.
Від рядків, що залишились, віднімається перший рядок, помножений на перший елемент відповідного рядка, з метою отримання нуля в першому елементі кожного рядка (крім першого).
Далі, повторюємо ці операції із матрицею, отриманою з початкової матриці після викреслювання першого рядка та першого стовпчика.
Після повторення операцій n − 1 разів отримаємо верхню трикутну матрицю.
Віднімаємо від передостаннього рядка останній рядок, помножений на відповідний коефіцієнт, щоб у передостанньому рядку залишилась лише 1 на головній діагоналі.
Повторюємо попередній крок для наступних рядків. У результаті отримуємо одиничну матрицю і рішення на місці вільного вектора (над ним необхідно виконувати ті самі перетворення).
Розгорнутий алгоритм для знаходження оберненої матриці
ред.
Нехай дано:
A
=
(
a
11
a
12
⋯
a
1
n
a
21
a
22
⋯
a
2
n
⋮
⋮
⋱
⋮
a
n
1
a
n
2
⋯
a
n
n
)
a
i
i
≠
0
I
=
(
1
0
⋯
0
0
1
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
1
)
{\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}}}
Прямий хід (алгоритм утворення нулів під головною діагоналлю)
ред.
Поділимо перший рядок матриці А на
a
11
{\displaystyle a_{11}}
отримаємо:
a
1
j
1
=
a
1
j
a
11
{\displaystyle a_{1j}^{1}={\frac {a_{1j}}{a_{11}}}}
, j — стовпець матриці А .
Повторюємо дії для матриці I, за формулою:
b
1
s
1
=
b
1
s
a
11
{\displaystyle b_{1s}^{1}={\frac {b_{1s}}{a_{11}}}}
, s — стовпець матриці I .
Отримаємо:
A
=
(
1
a
12
1
⋯
a
1
n
1
a
21
a
22
⋯
a
2
n
⋮
⋮
⋱
⋮
a
n
1
a
n
2
⋯
a
n
n
)
I
=
(
b
11
1
0
⋯
0
0
1
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
1
)
{\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 у першому стовпці:
a
2
j
1
=
a
2
j
−
a
1
j
1
a
21
…
a
n
j
1
=
a
n
j
−
a
1
j
1
a
n
1
{\displaystyle a_{2j}^{1}=a_{2j}-a_{1j}^{1}a_{21}\;\dots \;a_{nj}^{1}=a_{nj}-a_{1j}^{1}a_{n1}}
.
Повторюємо дії для матриці І, за формулами :
b
2
s
1
=
b
2
s
−
b
1
s
1
a
21
…
b
n
s
1
=
b
n
s
−
b
1
s
1
a
n
1
{\displaystyle b_{2s}^{1}=b_{2s}-b_{1s}^{1}a_{21}\;\dots \;b_{ns}^{1}=b_{ns}-b_{1s}^{1}a_{n1}}
Отримаємо:
A
=
(
1
a
12
1
⋯
a
1
n
1
0
a
22
1
⋯
a
2
n
1
⋮
⋮
⋱
⋮
0
a
2
n
1
⋯
a
n
n
1
)
I
=
(
b
11
1
0
⋯
0
b
21
1
1
⋯
0
⋮
⋮
⋱
⋮
b
n
1
1
0
⋯
1
)
{\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}}}
Продовжуємо виконувати аналогічні операції використовуючи формули :
a
i
j
k
=
a
i
j
k
a
i
i
a
i
j
k
=
a
i
j
k
−
1
−
a
k
j
k
a
i
k
k
−
1
{\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}}
за умови, що
k
=
1
→
n
,
i
=
k
+
1
→
n
,
j
=
1
→
n
{\displaystyle k=1\to n,i=k+1\to n,j=1\to n}
Повторюємо дії для матриці І, за формулами :
b
i
k
k
=
b
i
k
k
a
i
i
b
i
s
k
=
b
i
s
k
−
1
−
b
k
s
k
a
i
k
k
−
1
{\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}}
за умови, що
k
=
1
→
n
,
i
=
k
+
1
→
n
,
s
=
1
→
n
{\displaystyle k=1\to n,\;i=k+1\to n,\;s=1\to n}
.
Отримаємо:
A
=
(
1
a
12
1
⋯
a
1
n
1
0
1
⋯
a
2
n
2
⋮
⋮
⋱
⋮
0
0
⋯
1
)
I
=
(
b
11
1
0
⋯
0
b
21
2
b
22
2
⋯
0
⋮
⋮
⋱
⋮
b
n
1
n
b
n
2
n
⋯
b
n
n
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}}}
Зворотний хід (алгоритм утворення нулів над головною діагоналлю)
ред.
Використаємо формулу:
a
i
j
k
−
1
=
a
i
j
k
−
1
−
a
i
j
k
a
i
k
i
{\displaystyle a_{ij}^{k-1}=a_{ij}^{k-1}-a_{ij}^{k}a_{ik}^{i}}
, при умові, що
k
=
n
→
1
,
i
=
1
→
k
−
1
,
j
=
1
→
n
{\displaystyle k=n\to 1,\;i=1\to k-1,\;j=1\to n}
.
Повторюємо дії для матриці І, за формулою
b
i
s
k
−
1
=
b
i
s
k
−
1
−
b
i
s
k
a
i
k
i
{\displaystyle b_{is}^{k-1}=b_{is}^{k-1}-b_{is}^{k}a_{ik}^{i}}
, за умови, що
k
=
n
→
1
,
i
=
1
→
k
−
1
,
s
=
1
→
n
{\displaystyle k=n\to 1,\;i=1\to k-1,\;s=1\to n}
.
Остаточно отримуємо:
A
=
(
1
0
⋯
0
0
1
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
1
)
I
=
A
−
1
{\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}}
Розв'яжемо систему рівнянь:
{
a
+
b
+
c
=
0
4
a
+
2
b
+
c
=
1
9
a
+
3
b
+
c
=
3
{\displaystyle \left\{{\begin{array}{ccccccl}a&+&b&+&c&=&0\\4a&+&2b&+&c&=&1\\9a&+&3b&+&c&=&3\end{array}}\right.}
Запишемо її у вигляді матриці 3×4, де останній стовпчик є вільним членом:
(
1
1
1
|
0
4
2
1
|
1
9
3
1
|
3
)
{\displaystyle {\begin{pmatrix}1&1&1&|&0\\4&2&1&|&1\\9&3&1&|&3\end{pmatrix}}}
Виконаємо такі дії:
До рядка 2 додамо: -4 * рядок 1.
До рядка 3 додамо: -9 * рядок 1.
Отримаємо:
(
1
1
1
|
0
0
−
2
−
3
|
1
0
−
6
−
8
|
3
)
{\displaystyle {\begin{pmatrix}1&\ 1&\ 1&|&0\\0&-2&-3&|&1\\0&-6&-8&|&3\end{pmatrix}}}
До рядка 3 додамо: -3 * рядок 2.
Рядок 2 ділимо на -2
(
1
1
1
|
0
0
1
3
2
|
−
1
2
0
0
1
|
0
)
{\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.
(
1
1
0
|
0
0
1
0
|
−
1
2
0
0
1
|
0
)
{\displaystyle {\begin{pmatrix}1&1&0&|&\ 0\\0&1&0&|&-{1 \over 2}\\0&0&1&|&\ 0\end{pmatrix}}}
До рядка 1 додамо: -1 * рядок 2.
(
1
0
0
|
1
2
0
1
0
|
−
1
2
0
0
1
|
0
)
{\displaystyle {\begin{pmatrix}1&0&0&|&\ {1 \over 2}\\0&1&0&|&-{1 \over 2}\\0&0&1&|&\ 0\end{pmatrix}}}
У правому стовпчику отримаємо рішення:
a
=
1
2
;
b
=
−
1
2
;
c
=
0
{\displaystyle a={\frac {1}{2}}\;;\ b=-{\frac {1}{2}}\;;\ c=0}
.