د جوردان گاوس میتود

د جوردان گاوس میتود (د ړنگولو نامعلومه طریقه) — یو میتود دی چې د جبري خطي معادلو سیستم لپاره کارول کېږي، د معکوس ماټریسونو لپاره ډېر کارول کېږي.

پرمختللی الگورېتم د معکوس ماټریس د پیداکولو لپاره

Пусть дано:

$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}^{2}\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\rightarrow n,i=k+1\rightarrow n,j=1\rightarrow 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\!&\vline &\!0\\4&2&1\!&\vline &\!1\\9&3&1\!&\vline &\!3\end{pmatrix}}$

Проведём следующие действия:

• К строке 2 добавим: −4 × Строку 1.
• К строке 3 добавим: −9 × Строку 1.

Получим:

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

• К строке 3 добавим: −3 × Строку 2.
• Строку 2 делим на −2

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

• К строке 1 добавим: −1 × Строку 3.
• К строке 2 добавим: −3/2 × Строку 3.

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

• К строке 1 добавим: −1 × Строку 2.

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

В правом столбце получаем решение:

$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 Matlab
• Algorithm for Gauss-Jordan elimination in Python