Numerička linearna algebra: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
m Ispr. wikipoveznica |
m RpA: WP:NI, WP:HRV |
||
Redak 5:
Metoda [[Gaussove elinminacije|Gaussovih eliminacija]] je jedna od standardnih metoda za rješavanje sustava linearnih jednadžbi. No numerička implementacija metode ima svojih posebnosti. Prvo je važno istaknuti da algoritam mora biti opisan na način da se jednostavno implementira u računalu. Stoga se u svakom koraku metode element na dijagonali dijeljenjem retka uvijek prvo svodi na jedinicu, pa se potom množenjem do suprotnih koeficijenta i zbrajanjem redova svi elementi ispod dijagonale svode na nulu. Nakon što se matrica sustava svela na gornje trokutasti oblik, izvrednjavanjem unazad od posljednjeg stupca prema prvome, matrica sustava se svodi na dijagonalni oblik, iz kojega iščitavamo rješenja. Takav način rješavanja numerički je optimalan, budući metoda nakon manjeg broja obavljenih računa utvrđuje da li je sustav konzistentan, tj. da li postoji rješenje.
Unaprjeđenje metode predstavlja uvođenje (parcijalnog ili potpunog) ''pivotiranja''. Tim se postupkom na mjesto radnog elementa na dijagonali (tzv. ''pivotni elemenet'') dovodi (po apsolutnoj vrijednosti) najveći element matrice. Kod parcijalnog pivotiranja najveći element se bira samo u dijelu aktivnog stupca ispod dijagonale, dok se kod potpunog pivotiranja takav element bira u podmatrici koju čine reci ispod i stupci desno od pivotnog elementa. Pivotiranjem se osigurava da pivotni element nije jednak nuli (naravno,
== LR dekompozicija matrice ==
''LR dekompozicija'' matrice A (u literaturi se također naziva i ''LU dekompozicijom'') je algoritam kojim se formiraju matrice L i R za koje je <math> A = L \cdot R</math> gdje je L donje-trokutasta, a R gornje-trokutasta matrica. Sam postupak se ne razlikuje bitno od numeričke Gaussove eliminacije; opet množenjem pivotnih elemenata do suprotnih koeficjenata poništavamo elemente ispod glavne dijagonale, no ovoga puta te množitelje pamtimo. Oni će, nakon korekcije predznaka sačinjavati elemenete matrice L. Matrica R je gornje-trokutasta matrica koja preostane od matrice A nakon provođenja prvog dijela Gaussovih eliminacija.<ref>http://www.mathos.unios.hr/~ntruhar/NLA.pdf str. 57-77. Pristupljeno: 26. rujna 2013.</ref>
Osnovna upotreba LR dekompozicije je kod rješavanja linearnih sustava. Tada linearni sustav, u matričnom zapisu <math> Ax = b</math> prevodimo u sustav <math> LRx = b</math>, odnosno uvođenjem supstitucije <math> y=Rx</math>, problem prevodimo u njemu ekvivalentan problem rješavanja dva sustava:
Redak 17:
Postupak LR dekompozicije se, kao i numerička metoda Gaussovih eliminacija može provesti s pivotiranjem, pri čemu je permutacije redova (i/ili stupaca) potrebno pamtiti u posebnoj matrici permutacija, koja se uobičajeno označava s P.
Prednost metode je u tome što se LR dekompozicija provodi samo na matrici A, dok se desna strana jednakosti sustava, vektor b, koristi tek kod izvrednjavanja. To nam omogućava višekratnu upotrebu istog rezultata dekompozicije
== QR dekompozicija matrice ==
Redak 23:
''QR dekompozicija matrice'' A je rastav matrice A na umnožak matrica Q i R, pri čemu je Q ortogonalna, a R gornje-trokutasta matrica. Metoda se najčešće upotrebljava prilikom rješavanja sustava koji se formira u linearnoj [[Metoda najmanjih kvadrata|metodi najmanjih kvadrata]]. Također, na osnovu QR dekompozicije razvijena je i metoda za traženje svojstvenih vrijednosti matrice, ''QR metoda''.
Neka matrica A ima ''n'' linearno nezavisnih stupaca (ne mora nužno biti punog ranga, ni kvadratna). Tada stupci matrice Q predstavljaju ortonormiranu bazu vektorskog prostora razapetog stupcima matrice A. Za konstrukciju ortonormirane baze, upotrebljava se standardni [[Gram–Schmidtov postupak]]. Posljedica ortogonalnosti matrice Q je trokutasta forma matrice R.<ref>http://lavica.fesb.hr/mat2/ls/node5.html {{Webarchive|url=https://web.archive.org/web/20130927170141/http://lavica.fesb.hr/mat2/ls/node5.html |date=27. rujna 2013. }} Pristupljeno: 26. rujna 2013.</ref>
== Određivanje svojstvenih vrijednosti ==
| |||