Eleminimi gausian

Në matematikë, eliminimi Gausian, i njohur gjithashtu si reduktimi i rreshtave, është një algoritëm për zgjidhjen e sistemeve të ekuacioneve lineare . Ai përbëhet nga një varg veprimesh të kryera mbi matricën e koeficientëve. Kjo metodë mund të përdoret gjithashtu për të llogaritur rank-un e një matrice, përcaktorin e një matrice katrore dhe të anasjelltën e një matrice të kthyeshme . Metoda është emërtuar sipas Karl Fridrih Gausit (1777-1855). Për të kryer reduktimin e rreshtit në një matricë, përdoret një varg veprimesh elementare mbi rreshta për të modifikuar matricën derisa gjysma e poshtme e matricës (nën diagonale) të mbushet me zero, sa më shumë që të jetë e mundur. Ekzistojnë tre lloje të veprimeve elementare mbi rreshta:

• Ndërrimi i dy rreshtave,
• Shumëzimi i një rreshti me një numër jozero,
• Shtimi i një shumëfishi të një rreshti në një rresht tjetër.

Duke përdorur këto veprime, një matricë mund të shndërrohet gjithmonë në një matricë trekëndore të sipërme, dhe në fakt në një matricë që është në formë ekelon rreshti . Sapo të gjithë koeficientët kryesorë (hyrja më e majtë $\neq 0$ në çdo rresht) të jenë 1, dhe çdo shtyllë që përmban një koeficient kryesor ka zero diku tjetër, matrica thuhet se është në formën e shkallëzuar-rresht të reduktuar . Kjo formë përfundimtare është unike; me fjalë të tjera, është e pavarur nga vargu i veprimeve të rreshtave. Për shembull, në vargun vijues të veprimeve mbi rreshta (ku dy veprime elementare mbi rreshta të ndryshëm kryhen në hapin e parë dhe të tretë), matricat e tretë dhe të katërt janë ato në formë ekelon rreshti dhe matrica përfundimtare është unike në formën e shkallëzuar-rresht të reduktuar.

$${\begin{bmatrix}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{bmatrix}}\to {\begin{bmatrix}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{bmatrix}}$$

Forma shkalle

Për çdo rresht të një matrice, nëse rreshti nuk përbëhet vetëm nga zero, atëherë koeficienti më i majtë jozero quhet koeficienti kryesor (ose pivoti ) i atij rreshti. Pra, nëse dy koeficientë kryesorë janë në të njëjtën kolonë, atëherë një operacion rreshti i tipit 3 mund të përdoret për të bërë një nga ata koeficientë zero. Më pas, duke përdorur veprimet e ndërrimit të rreshtave, mund të renditen gjithmonë rreshtat në mënyrë që për çdo rresht jo zero, koeficienti kryesor të jetë në të djathtë të koeficientit kryesor të rreshtit të mësipërm. Nëse ndodh kësjtu, atëherë matrica thuhet se është në formën ekelon-rresht. Pra, pjesa e poshtme e majtë e matricës përmban vetëm zero, dhe të gjitha rreshtat zero janë nën rreshtat jozero. Fjala "ekelon" përdoret këtu sepse mund të mendohet përafërsisht që rreshtat të renditen sipas madhësisë së tyre, ku më i madhi është në krye dhe më i vogli në fund.

Për shembull, matrica e mëposhtme është në formë rresht ekelon, dhe koeficientët kryesorë të saj tregohen me të kuqe:

$${\begin{bmatrix}0&\color {red}{\mathbf {2} }&1&-1\\0&0&\color {red}{\mathbf {3} }&1\\0&0&0&0\end{bmatrix}}.$$

Shembull i algoritmit

Supozoni se qëllimi është gjetja dhe përshkrimi i grupit të zgjidhjeve për sistemin e mëposhtëm të ekuacioneve lineare:

$${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\qquad (L_{1})\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\qquad (L_{2})\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\qquad (L_{3})\end{alignedat}}$$

Tabela më poshtë është procesi i reduktimit të rreshtit të zbatuar njëkohësisht në sistemin e ekuacioneve dhe matricën e zgjeruar të lidhur me të. Në praktikë, zakonisht nuk merremi me sistemet si ekuacione, por në vend të kësaj përdoret matrica e zgjeruar, e cila është më e përshtatshme për llogaritje kompjuterike. Procedura e reduktimit mbi rreshta mund të përmblidhet si më poshtë: eliminoni x nga të gjitha ekuacionet nën $L_{1}$, dhe më pas eliminoni y nga të gjitha ekuacionet nën $L_{2}$. Kjo do ta vendosë sistemin në formë trekëndore . Pastaj, duke përdorur zëvendësimin prapa, çdo e panjohur mund të zgjidhet.

Sistemi i ekuacioneve	Veprimet rresht	Matrica e zgjeruar
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\end{alignedat}}$		$\left[{\begin{array}{rrr|r}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&2y&{}+{}&z&{}={}&5&\end{alignedat}}$	${\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2}\\L_{3}+L_{1}&\to L_{3}\end{aligned}}$	$\left[{\begin{array}{rrr|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&2&1&5\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&&&-z&{}={}&1&\end{alignedat}}$	$L_{3}+-4L_{2}\to L_{3}$	$\left[{\begin{array}{rrr|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right]$
Matrica tashmë është në formën ekelon (e quajtur edhe forma trekëndëshe)
${\begin{alignedat}{4}2x&{}+{}&y&&&{}={}7&\\&&{\tfrac {1}{2}}y&&&{}={}{\tfrac {3}{2}}&\\&&&{}-{}&z&{}={}1&\end{alignedat}}$	${\begin{aligned}L_{2}+{\tfrac {1}{2}}L_{3}&\to L_{2}\\L_{1}-L_{3}&\to L_{1}\end{aligned}}$	$\left[{\begin{array}{rrr|r}2&1&0&7\\0&{\frac {1}{2}}&0&{\frac {3}{2}}\\0&0&-1&1\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&\quad &&{}={}&7&\\&&y&\quad &&{}={}&3&\\&&&\quad &z&{}={}&-1&\end{alignedat}}$	${\begin{aligned}2L_{2}&\to L_{2}\\-L_{3}&\to L_{3}\end{aligned}}$	$\left[{\begin{array}{rrr|r}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]$
${\begin{alignedat}{4}x&\quad &&\quad &&{}={}&2&\\&\quad &y&\quad &&{}={}&3&\\&\quad &&\quad &z&{}={}&-1&\end{alignedat}}$	${\begin{aligned}L_{1}-L_{2}&\to L_{1}\\{\tfrac {1}{2}}L_{1}&\to L_{1}\end{aligned}}$	$\left[{\begin{array}{rrr|r}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]$

Kolona e dytë përshkruan se cilat operacione të rreshtave janë kryer. Pra, për hapin e parë, x eliminohet nga $L_{2}$ duke shtuar $3/2L_{1}$ tek $L_{2}$.

Zbatime

Historikisht, zbatimi i parë i metodës së reduktimit të rreshtave është për zgjidhjen e sistemeve të ekuacioneve lineare. Më poshtë janë disa aplikime të tjera të rëndësishme të algoritmit.

Llogaritja e përcaktorëve

Për të shpjeguar se si eliminimi Gaussian lejon llogaritjen e përcaktorit të një matrice katrore, duhet të kujtojmë se si veprimet e rreshtave elementare e ndryshojnë përcaktorin:

• Ndërrimi i dy rreshtave e shumëzon përcaktorin me -1
• Shumëzimi i një rreshti me një skalar jozero e shumëzon përcaktorin me të njëjtin skalar
• Shtimi në një rresht i një shumëfishi skalar të një tjetri nuk e ndryshon përcaktorin.

Nëse eliminimi Gaussian i zbatuar mbi një matricë katrore A prodhon një matricë të shkallës ekelon B, le të jetë $d$ prodhimi i skalarëve me të cilët është shumëzuar përcaktori, duke përdorur rregullat e mësipërme. Atëherë përcaktorja e A është herësi me $d$ i prodhimit të elementeve të diagonales së B :

$$\det(A)={\frac {\prod \operatorname {diag} (B)}{d}}.$$

Gjetja e inversit të një matrice

Një variant i eliminimit Gaussian i quajtur eliminimi Gauss-Jordan mund të përdoret për të gjetur të anasjelltën e një matrice, nëse ajo ekziston. Nëse A është një matricë katrore n × n, atëherë mund të përdoret reduktimi i rreshtave për të llogaritur matricën e saj të anasjelltë, nëse ajo ekziston. Së pari, matrica identitare n × n shtohet në të djathtë të A, duke formuar një matricë bllok n × 2 n [$A$ | $I$ ] . Tani, nëpërmjet zbatimit të veprimeve të rreshtave elementare, gjeni formën e reduktuar të shkallës së kësaj matrice n × 2n . Matrica A është e kthyeshme nëse dhe vetëm nëse blloku i majtë mund të reduktohet në matricën e identitetit I ; në këtë rast blloku i djathtë i matricës përfundimtare është $A^{-1}$ . Nëse algoritmi nuk është në gjendje të reduktojë bllokun e majtë në I, atëherë A nuk është i kthyeshëm.

Për shembull, merrni parasysh matricën e mëposhtme:

$$A={\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}}.$$

Duke kryer veprimet e rreshtave, mund të kontrollohet që forma e ekelonit të rreshtit të reduktuar të kësaj matrice të shtuar është

$$[I|B]=\left[{\begin{array}{rrr|rrr}1&0&0&{\frac {3}{4}}&{\frac {1}{2}}&{\frac {1}{4}}\\0&1&0&{\frac {1}{2}}&1&{\frac {1}{2}}\\0&0&1&{\frac {1}{4}}&{\frac {1}{2}}&{\frac {3}{4}}\end{array}}\right].$$