Gausova eliminacija

Gausova eliminacija, takođe poznata kao redna redukcija, algoritam je u linearnoj algebri za rešavanje sistema linearnih jednačina. On se obično se shvata kao niz operacija koje se izvode na odgovarajućoj matrici koeficijenata. Ova metoda se takođe može koristiti za nalažene ranga matrice, za izračunavanje determinante matrice i za izračunavanje inverzibilne kvadratne matrice. Metoda je dobila ime po Karlu Fridrihu Gausu (1777-1855), mada je kineskim matematičarima bila poznata još 179. godine.

Da bi se izvršila redna redukcija na matrici, koristi se niz elementarnih rednih operacija da bi se matrica modifikovala sve dok se donji levi ugao matrice ne ispuni nulama, što je više moguće. Postoje tri tipa elementarnih rednih operacija:

Zamena dva reda,
Množenje reda nenultim brojem,
Dodavanje umnoška jednog reda na drugi red.

Pomoću ovih operacija, matrica se uvek može transformisati u gornju trouglastu matricu, i zapravo onu koja je u obliku rednog ešalona. Nakon što su svi vodeći koeficijenti (najlevlji nenulti elementi u svakom redu) 1, i svaka kolona koja sadrži vodeći koeficijent ima nule na drugim mestima, kaže se da je matrica u obliku redukovanog rednog ešelona. Ovaj završni oblik je jedinstven; drugim rečima, on je nezavisan od sekvence korištenih rednih operacija. Na primer, u sledećem nizu rednih operacija (gde višestruke elementarne operacije mogu da budu izvršene u svakom koraku), treća i četvrta matrica su u rednoj ešalonskoj formi, a konačna matrica je jedinstvena redukovana redna ešelonska forma.

\left[{\begin{array}{rrr|r}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{array}}\right]

Korišćenje rednih operacija za konvertovanje matrice u redukovanu rednu ešalonsku formu se ponekad naziva Gaus–Džordanovom eliminacijom. Pojedini autori koriste termin Gausova eliminacija kao naziv procesa kojim se formira gornja trougaona forma, ili (neredukovana) redna ešalonska forma. Iz računskih razloga, pri rešavanju sistema linearnih jednačina, ponekad je poželjno zaustaviti redne operacije pre nego što se matrica potpuno redukuje.

Definicije i primeri algoritma

Proces redukcije redova koristi elementarne operacije nad redovima i može se podeliti u dva dela. Prvi deo (koji se ponekad naziva eliminacija prema napred) svodi dati sistem na rednu ešalonsku formu, iz čega se može znati da li nema rešenja, postoji jedinstveno rešenje ili beskonačno mnogo rešenja. Drugi deo (koji se ponekad naziva povratna zamena) nastavlja da koristi operacije nad redovima dok se ne nađe rešenje; drugim rečima, matrica se stavlja u oblik redukovanog rednog ešelona.

Jedno drugačije gledište, koja se ispostavilo kao vrlo korisno za analizu algoritma, jeste da redukcija redova stvara matričnu dekompoziciju originalne matrice. Elementarne operacije nad redovima mogu se posmatrati kao množenje na levoj strani originalne matrice elementarnim matricama. Alternativno, niz elementarnih operacija koje redukuju pojedinačni red mogu se posmatrati kao množenje Frobenijusovom matricom. Tada prvi deo algoritma izračunava LU dekompoziciju,^[1] dok drugi deo ispisuje originalnu matricu kao proizvod jedinstveno utvrđene invertibilne matrice i jedinstveno određene matrice redukovanog ešelona reda.

Ešelonska forma

Za svaki red matrice, ako se red ne sastoji samo od nula, tada se najlevlji element koji nije nula naziva vodećim koeficijentom (ili pivotom) tog reda. Dakle, ako su dva vodeća koeficijenta u istoj koloni, tada se redna operacija tipa 3 može koristiti da se jedan od tih koeficijenata pretvori u nulu. Zatim, pomoću operacije zamene redova, redovi se mogu poređati tako da je za svaki nenulti red, vodeći koeficijent desno od vodećeg koeficijenta prethodnog reda. Ako je to slučaj, kaže se da je matrica u obliku rednog ešalona. Donji levi deo matrice sadrži samo nule, i svi nulti redovi su ispod nenultih redova. Ovde se koristi reč „ešalon” jer se može smatrati da su redovi rangirani po njihovoj veličini, pri čemu je najveći na vrhu, a najmanji na dnu.^[2]^[3]

Na primer, sledeća matrica je u obliku rednog ešalona, i njeni vodeći koeficijenti su prikazani crvenom bojom:

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

Ona je u ešalonskom je obliku zato što je nulti red na dnu, a vodeći koeficijent drugog reda (u trećoj koloni) je desno od vodećeg koeficijenta prvog reda (u drugoj koloni).

Za matricu se kaže da je u obliku redukovanog rednog ešalona ako su svi vodeći koeficijenti jednaki 1 (što se može postići korišćenjem elementarnih rednih operacija tipa 2) i u svakoj koloni koja sadrži vodeći koeficijent svi ostali elementi su jednaki nuli (što se može postići korišćenjem elementarnih rednih operacija tipa 3).

Primeri algoritma

Pretpostavimo da je cilj da se pronađe i opiše skup rešenja za sledeći sistem linearnih jednačina:

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

Donja tabela predstavlja postupak redne redukcije koji se simultano primjenjuje na sistem jednačina i pridruženu dopunjenu matricu. U praksi se obično ne radi sa sistemima u smislu jednačina, već se koristi dopunjena matrica, koja je pogodnija za računarske manipulacije. Postupak redne redukcije može se sumirati na sledeći način: ukloniti x iz svih jednačina ispod L₁, a zatim eliminisati y iz svih jednačina ispod L₂. Ovim se sistem dovodi u trouglasti oblik. Zatim se pomoću povratne supstitucije može rešiti svaka nepoznata.

Sistem jednačina	Redne operacije	Dopunjena matrica
${\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 je sad u ešalonskoj formi (koja je isto tako poznata kao trougaona forma)
${\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]$

Druga kolona opisuje koje su redne operacije izvršene. U prvom koraku je x eliminisano iz L₂ dodavanjem 3/2L₁ na L₂. Zatim je x eliminisano iz L₃ dodavanje L₁ na L₃. Ove redne operacije su označene u tabeli kao

{\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2},\\L_{3}+L_{1}&\to L_{3}.\end{aligned}}

Nakon što je y eliminisano iz trećeg reda, rezultat je sistem linearnih jednačina trouglastog oblika, te je tako prvi deo algoritma okončan. Sa računarske tačke gledišta, brže je rešiti promenljive u reverznom redosledu, koristeći proces poznat kao povratna supstitucija. Može se videti da je rešenje z = −1, y = 3, i x = 2. U ovom slučaju postoji jedinstveno rešenje originalnog sistema jednačina.

Umesto zaustavljanja nakon formiranja ešalonske forme matrice, moglo bi se nastaviti sve dok matrica ne bude u obliku redukovanog rednog ešelona, kao što je to učinjeno u tabeli. Proces redne redukcije dok se ne formira redukovana matrica, ponekad se naziva i Gaus-Džordanovom eliminacijom, da bi se razlikovao od zaustavljanja nakon postizanja ešalonske forme.

Reference

^ Schwarzenberg-Czerny, A. (1995). „On matrix factorization and efficient least squares solution”. Astronomy and Astrophysics Supplement Series. 110: 405. Bibcode:1995A&AS..110..405S.
^ Leon, Steve (2009), Linear Algebra with Applications (8th изд.), Pearson, ISBN 978-0136009290
^ Meyer, Carl D. (2000), Matrix Analysis and Applied Linear Algebra, SIAM, ISBN 978-0-89871-454-8

Literatura

Atkinson, Kendall A. (1989), An Introduction to Numerical Analysis (2nd изд.), New York: John Wiley & Sons, ISBN 978-0471624899 .
Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor S. (2006), Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2nd изд.), Wiley-Interscience, ISBN 978-0-471-79156-0 .
Calinger, Ronald (1999), A Contextual History of Mathematics, Prentice Hall, ISBN 978-0-02-318285-3 .
Farebrother, R.W. (1988), Linear Least Squares Computations, STATISTICS: Textbooks and Monographs, Marcel Dekker, ISBN 978-0-8247-7661-9 .
Lauritzen, Niels, Undergraduate Convexity: From Fourier and Motzkin to Kuhn and Tucker .
Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd изд.), Johns Hopkins, ISBN 978-0-8018-5414-9 .
Grcar, Joseph F. (2011a), „How ordinary elimination became Gaussian elimination”, Historia Mathematica, 38 (2): 163—218, arXiv:0907.2397 , doi:10.1016/j.hm.2010.06.003
Grcar, Joseph F. (2011b), „Mathematicians of Gaussian elimination” (PDF), Notices of the American Mathematical Society, 58 (6): 782—792
Higham, Nicholas (2002), Accuracy and Stability of Numerical Algorithms (2nd изд.), SIAM, ISBN 978-0-89871-521-7 .
Katz, Victor J. (2004), A History of Mathematics, Brief Version, Addison-Wesley, ISBN 978-0-321-16193-2 .
Kaw, Autar; Kalu, Egwu (2010). „Numerical Methods with Applications: Chapter 04.06 Gaussian Elimination” (PDF) (1st изд.). University of South Florida.
Lipson, Marc; Lipschutz, Seymour (2001), Schaum's outline of theory and problems of linear algebra, New York: McGraw-Hill, стр. 69—80, ISBN 978-0-07-136200-9 .
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Section 2.2”, Numerical Recipes: The Art of Scientific Computing (3rd изд.), New York: Cambridge University Press, ISBN 978-0-521-88068-8, Архивирано из оригинала 19. 03. 2012. г., Приступљено 22. 08. 2019
Bunch, James R.; Hopcroft, John (1974), „Triangular factorization and inversion by fast matrix multiplication”, Mathematics of Computation, 28 (125): 231—236, ISSN 0025-5718, JSTOR 2005828, doi:10.2307/2005828 .
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms, MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3 .
Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, ISBN 978-0-521-38632-6 . See Section 3.5. N − 1
Householder, Alston S. (1975), The Theory of Matrices in Numerical Analysis, New York: Dover Publications, MR 0378371 .
Okunev, Pavel; Johnson, Charles R. (1997), Necessary And Sufficient Conditions For Existence of the LU Factorization of an Arbitrary Matrix, arXiv:math.NA/0506382  .
Poole, David (2006), Linear Algebra: A Modern Introduction (2nd изд.), Canada: Thomson Brooks/Cole, ISBN 978-0-534-99845-5 .
Trefethen, Lloyd N.; Bau, David (1997), Numerical linear algebra, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 978-0-89871-361-9 .