Numerička linearna algebra

Numerička linearna algebra je grana numeričke matematike koja se bavi algoritmima korištenima u linearnoj algebri. Temeljni problem izučavan u numeričkoj linearnoj algebri su algoritmi za rješavanje sustava linearnih jednadžbi, koji su pak doveli do algoritama za dekompoziciju matrica, kao što su LR dekompozicija ili QR dekompozicija. Veći značaj se pridaje i razvoju algoritama za određivanje svojstvenih vrijednosti matrica.

Numerička metoda Gaussovih eliminacija

Metoda 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, ukoliko je sustav konzistentan, tj. rješiv). Također pivotiranjem se smanjuje mogućnost propagiranja greške u aritmetici računala koja nastaje oduzimanjem velikih bliskih brojeva.

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]\displaystyle{ 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.

Osnovna upotreba LR dekompozicije je kod rješavanja linearnih sustava. Tada linearni sustav, u matričnom zapisu [math]\displaystyle{ Ax = b }[/math] prevodimo u sustav [math]\displaystyle{ LRx = b }[/math], odnosno uvođenjem supstitucije [math]\displaystyle{ y=Rx }[/math], problem prevodimo u njemu ekvivalentan problem rješavanja dva sustava:

[math]\displaystyle{ Ly = b }[/math] i [math]\displaystyle{ Rx = y. }[/math]

Ovi su sustavi numerički puno brži za rješavanje budući su matrice L i R trokutaste, pa se u oba slučaja radi o izvrednjavanju (unaprijed ili unazad).

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 ukoliko se u zadanom sustavu mijenjaju samo desne strane, a u praksi to često i jest tako (koeficijenti sustava obično dolaze iz odabranog modela, a lijeve strane jednakosti iz mjerenja). Bez prethodne dekompozicije, sustav bi sa svakim novim mjerenjem morali nanovo rješavati.

QR dekompozicija matrice

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 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.