Gauss-Jordan algoritmo

Aljebra linealean, Gauss-Jordan algoritmoa ekuazio linealetako sistema bateko soluzioa, matrize bateko heina eta matrize bateko alderantzizkoa kalkulatzeko metodo bat da. Algoritmoa XIX. mendeko Carl Friedrich Gauss eta Wilhelm Jordan alemaniar matematikariek garatu zuten, antzinako txinatar matematikariek metodoa ezagutzen bazuten ere.

Algoritmoaren printzipioak

Ekuazioen arteko honako eragiketa elemental hauek eginez gero, ekuazio linealetako sistemaren soluzioa eta matrizearen heina ez dira aldatuko eta determinanteak aldaketa jakinak izango ditu:

• lerro edo zutabeen leku aldatzea;
• ekuazio edo lerro bat (edo zutabe bat) konstante batez biderkatu edo zatitzea;
• lerro (ekuazio) edo zutabe baten multiploa beste lerro edo zutabe batekin batu edo kentzea.

Algoritmoaren garapena

Ekuazio linealetako sistemak

Ekuazio linealetako sistemetan (m ekuazio eta n-1 ezezagun, $\displaystyle m\leq n-1$) sistema matrize moduan adierazi eta eragiketa elementalal erabiliz matrize mailakatu murriztu bat lortzen saiatu behar da:

${\begin{pmatrix}a_{11}&a_{12}&a_{13}&\ldots &a_{1,n}\\a_{21}&a_{22}&a_{23}&&\vdots \\a_{31}&a_{32}&a_{33}&\ddots &\vdots \\\vdots &\vdots &\vdots &\ddots &a_{m-1,n}\\a_{m1}&a_{m2}&a_{m3}&\ldots &a_{m,n}\end{pmatrix}}\rightarrow {\begin{pmatrix}1&0&0&\ldots &0&b_{1,m+1}&\ldots &b_{1n}\\0&1&0&&\vdots &\vdots &&\vdots \\0&0&1&\ddots &\vdots &\vdots &\ddots &\vdots \\\vdots &\vdots &\vdots &&0&b_{m-1,m+1}&\ddots &b_{m-1,n}\\0&0&0&\ldots &1&b_{m,m+1}&\ldots &b_{m,n}\end{pmatrix}}$

Aurreko modu horretan, soluzioa berehalakoa da eta sistema bateragarri eta mugatuen kasuan azken zutabeko balioekin dator bat.

Beste aukera, eragiketa elementalak burutuz baita ere, matrize triangeluar bat osatzea da. Matrize horretatik ere aise ebazten da sistema lineala:

${\begin{pmatrix}a_{11}&a_{12}&a_{13}&\ldots &a_{1n}\\a_{21}&a_{22}&a_{23}&&\vdots \\a_{31}&a_{32}&a_{33}&\ddots &\vdots \\\vdots &\vdots &\vdots &\ddots &a_{m-1,n}\\a_{m1}&a_{m2}&a_{m3}&\ldots &a_{m,n}\end{pmatrix}}\rightarrow {\begin{pmatrix}b_{11}&b_{12}&\ldots &b_{1,m-1}&b_{1,m}&\ldots &b_{1n}\\0&b_{22}&&\vdots &\vdots &&\vdots \\0&0&\ddots &\vdots &\vdots &\ddots &\vdots \\\vdots &\vdots &\vdots &b_{m-1,m-1}&b_{m-1,m}&\ddots &b_{m-1,n}\\0&0&0&\ldots &b_{mm}&\ldots &b_{m,n}\end{pmatrix}}$

Sistema bateragarri mugatuak

Ekuazio linealetako sistema bateragarri determinatuak soluzio bakarra duten horiek dira. Sistema hauek matrize moduan adierazten direnean, zutabe kopurua lerro kopurua gehi 1 da eta azken zutabea ekuazioaren termino independente edo konstanteari dagokio. Gauss-Jordan algoritmoa garatzen denean sistema hauetan, matrize mailakatura heltzeko eragiketa elementalak burutu ondoren, koefizienteen matrizea (konstanteen zutabea kenduta duen matrizea) matrize diagonala eta unitarioa da. Adibidez:

${\begin{aligned}&2x+&4y&+&6z&=&4\\&x+&y&+&z&=&2\\&3x+&3y&+&z&=&0\end{aligned}}\ \rightarrow {\begin{pmatrix}2&4&6&4\\1&1&1&2\\3&3&1&0\\\end{pmatrix}}$

Matrize mailakatu murriztura heltzeko pausoak hauek dira:

${\begin{pmatrix}2&4&6&4\\1&1&1&2\\3&3&1&0\\\end{pmatrix}}\rightarrow (L_{1}/2){\begin{pmatrix}1&2&3&2\\1&1&1&2\\3&3&1&0\\\end{pmatrix}}\rightarrow (-L_{1}+L_{2}){\begin{pmatrix}1&2&3&2\\0&-1&-2&0\\3&3&1&0\\\end{pmatrix}}\rightarrow (-3L_{1}+L_{3})$ ${\begin{pmatrix}1&2&3&2\\0&-1&-2&0\\0&-3&-8&-6\\\end{pmatrix}}\rightarrow (-L_{2}){\begin{pmatrix}1&2&3&2\\0&1&2&0\\0&-3&-8&-6\\\end{pmatrix}}\rightarrow (-2L_{2}+L_{1}){\begin{pmatrix}1&0&-1&2\\0&1&2&0\\0&-3&-8&-6\\\end{pmatrix}}\rightarrow (3L_{2}+L_{3})$ ${\begin{pmatrix}1&0&-1&2\\0&1&2&0\\0&0&-2&-6\\\end{pmatrix}}\rightarrow {L_{3}/-2}{\begin{pmatrix}1&0&-1&2\\0&1&2&0\\0&0&1&3\\\end{pmatrix}}\rightarrow {L_{3}+L_{1}}{\begin{pmatrix}1&0&0&5\\0&1&2&0\\0&0&1&3\\\end{pmatrix}}\rightarrow {-2L_{3}+L_{2}}{\begin{pmatrix}1&0&0&5\\0&1&0&-6\\0&0&1&3\\\end{pmatrix}}$

Hasierako sistema honela geratzen da, beraz:

${\begin{aligned}x&=&5\\y&=&-6\\z&=&3\end{aligned}}$

Ikus daitekeenez, lerro berriak sortzeko aldi bakoitzean matrizeko elementu bat erabiltzen da pivot edo oinarri gisa. Kalkuluen lehenengo lerroan matrizeko diagonaleko lehenengo elementua erabiltzen da pivot moduan, diagonaleko bigarrena bigarren lerroan eta hirugarrena hirugarrenean.

Sistema matrize triangeluar batera helduz ebaztea ere posible da:

${\begin{pmatrix}2&4&6&4\\1&1&1&2\\3&3&1&0\\\end{pmatrix}}\rightarrow (-L_{1}/2+L_{2}){\begin{pmatrix}2&4&6&4\\0&-1&-2&0\\3&3&1&0\\\end{pmatrix}}\rightarrow (-3L_{1}/2+L_{3}){\begin{pmatrix}2&4&6&4\\0&-1&-2&0\\0&-3&-8&-6\\\end{pmatrix}}\rightarrow (-3L_{2}+L_{3})$ ${\begin{pmatrix}2&4&6&4\\0&-1&-2&0\\0&0&-2&-6\\\end{pmatrix}}$

Sistema honela geratzen da, beraz:

${\begin{aligned}2x+4y+6z&=&4\\-y+-2z&=&0\\-2z&=&-6\end{aligned}}$

Sistema honetatik berehala lortzen da soluzioa, hirugarren ekuazioa ebatziz, ondoren bigarrenean ordeztuz eta ebatziz eta azkenik lehenengoan ordeztuz eta ebatziz berriz ere.

Sistema bateragarri mugagabeak

Sistema bateragarri mugagabeak soluzio infinitu dituzten horiek dira. Ekuazio eta ezezagun kopurua berdina denean, sistema hauek matrize mailakatu murriztua edo matrize triangeluarra lortzeko prozesuan lerro batean (edo gehiagotan) balio guztiak 0 direnean hautematen dira. Adibidez:

${\begin{aligned}&x+&3y&-&4z&=&-1\\&2x-&y&+&3z&=&4\\&3x+&2y&-&z&=&3\end{aligned}}\ \rightarrow {\begin{pmatrix}1&3&-4&-1\\2&-1&3&4\\3&2&-1&3\\\end{pmatrix}}$

Matrize triangeluar bat garatzeko Gauss-Jordan algoritmoa garatuz:

${\begin{pmatrix}1&3&-4&-1\\2&-1&3&4\\3&2&-1&3\\\end{pmatrix}}\rightarrow (-2L_{1}+L_{2}){\begin{pmatrix}1&3&-4&-1\\0&-7&11&6\\3&2&-1&3\\\end{pmatrix}}\rightarrow (-3L_{1}+L_{3}){\begin{pmatrix}1&3&-4&-1\\0&-7&11&6\\0&-7&11&6\\\end{pmatrix}}\rightarrow (-L_{2}+L_{3})$ ${\begin{pmatrix}2&4&6&4\\0&-7&11&6\\0&0&0&0\\\end{pmatrix}}$

Sistema honela geratzen da:

${\begin{aligned}&2x+&4y&+&6z&=&4\\&&-7y&+&11z&=&6\\\end{aligned}}$

Sistema bateragarri mugagabea da, hiru ezezagun eta independenteak diren bi ekuazio dituelako. Aldagai aske moduan z aldagaia hartzen bada, sistema ekuazio hauetatik ebatzi beharko litzateke:

${\begin{aligned}&2x+&4y&=&4-&6z&\\&&-7y&=&6-&11z&\\\end{aligned}}$

Sistema bateraezinak

Sistema bateraezinak soluziorik ez duten horiek dira. Gauss-Jordan algoritmoa garatuz, matrize mailakatu murriztua edo matrize triangeluarra lortzeko prozesuan zehar, lerro batean koefiziente guztiak 0 eta konstantea 0 ez izatean hautematen dira:

${\begin{aligned}&x+&y&=&5\\-&2x-&2y&=&8\end{aligned}}\ \rightarrow {\begin{pmatrix}1&1&5\\-2&-2&8\\\end{pmatrix}}$

${\begin{pmatrix}1&1&5\\-2&-2&8\\\end{pmatrix}}\rightarrow (2L_{1}+L_{2}){\begin{pmatrix}1&1&5\\0&0&18\\\end{pmatrix}}$

0x+0y=18 ezinezkoa denez, sistemak ez du soluziorik.

Matrize baten alderantzizkoa

Gauss-Jordan algoritmoa matrize baten alderantzizkoa kalkulatzeko ere erabil daiteke. Adibidez, matrize honen alderantzizkoa egiteko:

$A={\begin{pmatrix}2&1&-1\\-3&-1&2\\-2&1&2\end{pmatrix}}$

$\left({\begin{array}{ccc|ccc}2&1&-1&1&0&0\\-3&-1&2&0&1&0\\-2&1&2&0&0&1\end{array}}\right)\rightarrow (L_{1}/2)\left({\begin{array}{ccc|ccc}1&1/2&-1/2&1/2&0&0\\-3&-1&2&0&1&0\\-2&1&2&0&0&1\end{array}}\right)\rightarrow (3L_{1}+L_{2})\left({\begin{array}{ccc|ccc}1&1/2&-1/2&1/2&0&0\\0&1/2&1/2&3/2&1&0\\-2&1&2&0&0&1\end{array}}\right)\rightarrow (2L_{1}+L_{3})$ $\left({\begin{array}{ccc|ccc}1&1/2&-1/2&1/2&0&0\\0&1/2&1/2&3/2&1&0\\0&2&1&1&0&1\end{array}}\right)\rightarrow (2L_{2})\left({\begin{array}{ccc|ccc}1&1/2&-1/2&1/2&0&0\\0&1&1&3&2&0\\0&2&1&1&0&1\end{array}}\right)\rightarrow (-L_{2}/2+L_{1})\left({\begin{array}{ccc|ccc}1&0&-1&-1&-1&0\\0&1&1&3&2&0\\0&2&1&1&0&1\end{array}}\right)\rightarrow (-2L_{2}+L_{3})$ $\left({\begin{array}{ccc|ccc}1&0&-1&-1&-1&0\\0&1&1&3&2&0\\0&0&-1&-5&-4&1\end{array}}\right)\rightarrow (-L_{3})\left({\begin{array}{ccc|ccc}1&0&-1&-1&-1&0\\0&1&1&3&2&0\\0&0&1&5&4&-1\end{array}}\right)\rightarrow (L_{3}+L_{1})\left({\begin{array}{ccc|ccc}1&0&0&4&3&-1\\0&1&1&3&2&0\\0&0&1&5&4&-1\end{array}}\right)\rightarrow (-L_{3}+L_{2})$ $\left({\begin{array}{ccc|ccc}1&0&0&4&3&-1\\0&1&0&-2&-2&1\\0&0&1&5&4&-1\end{array}}\right)$

Horrela, hasierako matrizearen alderantzizkoa hau da:

$A^{-1}={\begin{pmatrix}4&3&-1\\-2&-2&1\\5&4&-1\end{pmatrix}}$

Matrize baten determinantea

Matrize baten determinantea kalkulatzeko ere erabil daiteke Gauss-Jordan algoritmoa. Matrizeko lerroak aldatzerakona, determinantearen balioan aldaketa hauek gertatzen direla hartu behar da kontuan:

• bi lerro (edo zutabe) lekuz aldatzen badira, determinatearen balioaren zeinua bakarrik aldatzen da;
• lerro bat konstante batez biderkatzean, determinantearen balioa ere konstante horretaz biderkatzen da;
• lerro bati beste baten konbinazio lineala gehitzen bazaio, determinantearen balioa ez da aldatzen.

Gauss-Jordan algoritmoa garatzean, matrize triangeluar batera heldu behar da. Matrize triangeluar honetako determinantea diagonaleko elementuen biderkadura da. Algoritmoa garatzean egin diren aldaketak kontuan hartuz, jatorrizko matrizearen determinantea kalkulatuko da. Adibidez (berdintzen artean egindako aldaketak agertzen dira):

${\begin{vmatrix}-1/2&0&-1\\2&1&0\\-3&2&7\end{vmatrix}}=(-2L_{1})=-1/2{\begin{vmatrix}1&0&2\\2&1&0\\-3&2&7\end{vmatrix}}=(-2L_{1}+L_{2}2)=-1/2{\begin{vmatrix}1&0&2\\0&1&-4\\-3&2&7\end{vmatrix}}=(3L_{1}+L_{2})=-1/2{\begin{vmatrix}1&0&2\\0&1&-4\\0&2&13\end{vmatrix}}=$ $(-2L_{2}+L_{3})=-1/2{\begin{vmatrix}1&0&2\\0&1&-4\\0&0&21\end{vmatrix}}=-1/2\times 1\times 1\times 21=-10.5$

Kanpo estekak

• Datuak: Q2658