Naslov
Brze metode za rješavanje problema svojstvenih vrijednosti i utočnjavanje rješenja
(Fast Methods for Solving Eigenvalue Problems and Improving the Accuracy)

Autori
Horvat, Liljana

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, magistarski rad

Fakultet
Prirodoslovno-matematički fakultet, Matematički odjel

Mjesto
Zagreb

Datum
01.10

Godina
2001

Stranica
151

Mentor
Slapničar, Ivan

Sažetak
U uvodu je opisana problematika točnosti prilikom računanja svojstvenih vrijednosti, dan je primjer na kojem se vidi razlika u točnosti svojstvenih vrijednosti izračunatih brzim metodama i Jacobijevom metodom, te su dani osnovni algoritmi točnih metoda (rastav i Jacobi). Zatim je ukratko izložena osnovna ideja i algoritam kojeg su za utočnajvanje rješenja koristili Drmač i Veselić, te novi algoritam koji je istraživan u radnji. U drugom poglavlju navedene su osnovne definicije i perturbacijski teoremi za hermitski problem svojstvenih vrijednosti, a posebno oni koji se dalje koriste u radu. U trećem poglavlju opisane su brze metode za računanje rastava svojstvenih vrijednosti realnih simetričnih matrica. Prvi korak tih metoda je tridijagonalizacija zadane matrice, koja se može vršiti pomoću Householderovih reflektora ili Givensovih rotacija, s time što je prvi način dvostruko brži. Svojstveni problem tridijagonalne matrice potom se može riješiti QR metodom ili divide-and-conquer metodom. Dani su detaljni algoritmi za sve navedene metode. Nakon toga je napravljena detaljna analiza pogrešaka zaokruživanja za sve navedene metode, koristeći svojstva aritmetike računala. Kombinirajući rezultate analize pogrešaka s perturbacijskim teoremima, dane su ukupne ocjene pogreške za izračunate svojstvene vrijednosti i vektore za sva četiri promatrana algoritma (Householder i QR, Givens i QR, Householder i divide-and-conquer, te Givens i divide-and-conquer). Posebna vrijednost ovog dijela je u sistematičnom pristupu u kojem nisu korištene aproksimacije prvog reda veličine, tako da većina dobivenih ocjena vrijedi egzaktno. U četvrtom poglavlju opisane su matrice dobrog ponašanja, odnosno matrice kod kojih je moguće postići veću relativnu točnost izračunatih vrijednosti nego što to predviđa klasična teorija. Dani su i osnovni perturbacijski rezultati koji se temelje na radovima Veselića, Truhara i Slapničara. U petom poglavlju opisan je algoritam točne metode kojeg su razvili Veselić i Slapničar. Algoritam se sastoji od simetričnog indefinitnog rastava nakon kojega slijedi jednostrana $J$-ortogonalna Jacobijeva metoda. Također su dane ocjene za relativne pogreške izračunatih svojstevnih vrijednosti i vektora za matrice dobrog ponašanaja. U šestom poglavlju prvo je opisana strategija utočnjavanja rješenja Drmača i Veselića, te dani osnovni teoretski rezultati. Potom je detaljno opisan novi algoritam iterativnog utočnjavanja pomoću brzih metoda, uključujći strategije biranja podmatrica na kojem se utočnjavanje vrši. Predložene su dvije strategije: izbor po lošim elementima (svi retci i stupci koji sadrže izvandijagonalne elemente koji ne zadovoljavaju kriterij točnosti), i izbor po dobrim elementima (komplement redaka i stupaca koji sadrže izvandijagonalne elemente koji zadovoljavaju kriterij točnosti). Potom je na numeričkom primjeru detaljno ilustrirano funkcioniranje obaju strategija. Iako strategija izbora po dobrim elementima teoretski ne garantira da će matrica u sljedećoj iteraciji bolje zadovoljavati kriterije točnosti, navedeni primjer je ukazao na to da je ta strategija efikasnija. U sedmom poglavlju napravljeni su opsežni numerički eksperimenti. Uspoređeno je utočnjavanje pomoću brzih metoda s oba načina biranja podmatrice s točnom Jacobijevom metodom. Pokazalo se da je najoptimalniji algoritam za brzo utočnjavanje korištenje Householderove tridijagonalizacije i divide-and-conquer metode uz izbor podmatrice po dobrim elementima. Taj algoritam postiže zadovoljavajuću točnost izračunatih svojstvenih vrijednosti i vektora uz povećanje brzine od 30% u odnosu na točnu metodu.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA