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.

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:

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:

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 L1, a zatim eliminisati y iz svih jednačina ispod L2. 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
Matrica je sad u ešalonskoj formi (koja je isto tako poznata kao trougaona forma)

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

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[уреди]

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

Literatura[уреди]

Spoljašnje veзе[уреди]