Ominaisarvojen ja -vektoreiden iteratiivinen etsiminen

Abstract

Karakteristisen polynomin nollakohtina neliömatriisin ominaisarvot voidaan ratkaista algebrallisesti yksinkertaisissa tapauksissa, joissa karakteristisen polynomin tekijöihinjako tunnetaan juurilausekkeiden tulona. Jos polynomi on neljännettä astetta korkeampi, ei sen nollakohtia voida yleisesti ottaen ilmaista äärellisinä juurilausekkeina Abelin-Ruffinin lauseen nojalla. Siksi kokoa 4 x 4 suurempien neliömatriisien ominaisarvoille on yleensä etsittävä likiarvot iteratiivisesti. Polynomiyhtälöiden ratkaisijat eivät tule kyseeseen, koska polynomin nollakohdat voivat olla pahasti häiriöalttiita polynomin kertoimien suhteen, missä tapauksessa liukulukulaskennassa kasautuvat pyöritysvirheet tekevät ominaisarvon likiarvon merkityksettömäksi. Karakteristisen polynomin määritelmä matriisideterminanttina aiheuttaa myös sen, että suuren matriisin karakteristisen polynomin esittämiseksi tarvitaan raskas symbolinen determinantin kehityslasku. Työssä esitellään numeerisia menetelmiä, joilla matriisin ominaisarvojen ja -vektoreiden muodostamat parit, ominaisparit, lasketaan karakteristista polynomia käyttämättä.

Karakteristiselle polynomille teoreettisesti ekvivalentti vaihtoehto ominaisarvojen määrityksessä on matriisin Schurin hajotelma. Hajotelman muodostamisen yhteydessä löydetään tutkittavan matriisin kanssa similaarinen yläkolmiomatriisi, jonka diagonaalilla etsityt ominaisarvot ovat. Numeerisesti tämän yläkolmiomatriisin muodostaminen on iteratiivinen prosessi, jossa alkuperäiseen matriisiin sovelletaan peräkkäin similaarisuusmuunnoksia, kunnes muunnettu matriisi on halutun tarkkuuden päässä yläkolmiomatriisista. Iteraation aikavaativuutta voidaan pienentää muuntamalla alkuperäinen matriisi ensin äärellisellä määrällä similaarisuusmunnoksia Hessenbergin matriisiksi eli ensimmäistä aladiagonaalia vaille yläkolmiomatriisiksi. Hessenbergin matriisin laskemisen edellyttämät similaarisuusmuunnokset voidaan toteuttaa numeerisesti vakaasti käyttämällä ortogonaalisia Householderin reflektiomatriiseja tai Givensin rotaatiomatriiseja.

Varsinaisia ominaisarvoiteraatioita on useanlaisia, joista sopiva valitaan muun muassa sen perusteella, millainen matriisin rakenne on ja mikä osa matriisin ominaispareista täytyy ratkaista. Tässä työssä käsiteltävät iteratiiviset menetelmät ovat potenssiinkorotusmenetelmä, Jacobin menetelmä ja QR-menetelmä. Niiden laskenta-algoritmit esitetään yksinkertaistettuina sivuuttamalla esimerkiksi kompleksisten ominais\-arvojen etsiminen. Laskentaohjelmat käyttävät algoritmeista monimutkaisempia toteutuksia, jotka ovat aikavaativuudeltaan pienempiä ja numeerisesti vakaampia.