Algoritmi ominaisarvojen laskemiseen

Ominaisarvojen laskentaalgoritmi - algoritmi, jonka avulla voit määrittää tietyn matriisin ominaisarvot ja ominaisvektorit . Tehokkaiden ja vakaiden algoritmien luominen tähän ongelmaan on yksi laskennallisen matematiikan keskeisistä ongelmista .

Ominaisarvot ja ominaisvektorit

Kun reaali- tai kompleksilukujen yli on n × n neliömatriisi A , ominaisarvo λ ja sitä vastaava juurivektori v ovat pari, joka täyttää yhtälön [1]

\left(A-\lambda E\right)^{k}{\mathbf {v} }=0,

missä v on nollasta poikkeava n × 1 -sarakevektori, E on n × n -identtisyysmatriisi , k on positiivinen kokonaisluku ja λ ja v voivat olla komplekseja, vaikka A olisi todellinen. Jos k = 1 , vektoria kutsutaan yksinkertaisesti ominaisvektoriksi . Tässä tapauksessa A v = λ v . Millä tahansa matriisin A ominaisarvolla λ on sitä vastaava yksinkertainen [huomautus 1] ominaisvektori siten, että jos k on pienin kokonaisluku, jolloin ( A - λ E ) k v = 0 juurivektorille v , niin ( A - λ E ) k -1 v on yksinkertainen ominaisvektori. K :n arvo voidaan aina olla pienempi tai yhtä suuri kuin n . Erityisesti ( A -λE ) nv = 0 kaikille juurivektoreille v , jotka vastaavat λ : ta.

Minkä tahansa matriisin A ominaisarvon λ kohdalla ytimen ker( A - λ E ) koostuu kaikista ominaisvektoreista, jotka vastaavat λ :ta (yhdessä 0:n kanssa), ja sitä kutsutaan λ : n ominaisaliavaruudeksi ja vektoriavaruudeksi ker(( A - λ E ) n ) koostuu kaikista juurivektoreista (täytetty nollavektorilla) ja sitä kutsutaan juurialiavaruudeksi . Arvon λ geometrinen monikertaisuus on oman aliavaruutensa ulottuvuus. Arvon λ algebrallinen monikerta on sen juurialiavaruuden ulottuvuus. Muut termit liittyvät tasa-arvoon

p_{A}\left(z\right)={\rm {det))\left(zE-A\right)=\prod _{i=1}^{k}(z-\lambda _ {i})^{\alpha _{i)),

Tässä det on determinantti , λ i ovat kaikki matriisin A erillisiä ominaisarvoja ja α i ovat vastaavat algebralliset kertoimet. Funktio p A ( z ) on matriisin A karakteristinen polynomi . Siten algebrallinen monikertaisuus on ominaisarvojen moninkertaisuus ominaispolynomin juurina . Koska mikä tahansa ominaisvektori on juurivektori, geometrinen monikertaisuus on pienempi tai yhtä suuri kuin algebrallinen monikerta. Algebrallisten kertoimien summa on yhtä suuri kuin ominaispolynomin n aste. Yhtälöä p A ( z ) = 0 kutsutaan ominaisyhtälöksi , koska sen juuret ovat täsmälleen matriisin A ominaisarvot . Hamilton-Cayley-lauseen mukaan matriisi A itse täyttää saman yhtälön: p A ( A ) = 0 [huomautus 2] . Tämän seurauksena matriisin sarakkeiden tulee olla joko 0 tai juurivektoreita, jotka vastaavat ominaisarvoa λ j , koska matriisi tuhoaa ne $\textstyle \prod _{i\neq j}(A-\lambda _{i}E)^{\alpha _{i))$ $\textstyle (A-\lambda _{j}E)^{\alpha _{j)).$

Mikä tahansa joukko erillisten ominaisarvojen juurivektoreita on lineaarisesti riippumaton, joten koko C n :n perusta voidaan valita juurivektorijoukosta. Tarkemmin sanottuna tämä perusta { v i }n
i = 1voidaan valita ja järjestää niin

jos v i :llä ja v j :llä on sama ominaisarvo, niin tämä pätee myös mille tahansa v k :lle , jonka k on i :n ja j :n välillä ;
jos v i ei ole yksinkertainen ominaisvektori ja jos λ i on sen ominaisarvo, niin ( A - λ i E ) v i = v i -1 (erityisesti v 1 : n täytyy olla yksinkertainen ominaisvektori).

Jos nämä kantavektorit on järjestetty matriisin V = [ v 1 v 2 ... v n ] sarakkeiksi , niin V :llä voidaan muuttaa matriisi A normaaliin Jordan - muotoonsa :

V^{-1}AV={\begin{bmatrix}\lambda _{1}&\beta _{1}&0&\ldots &0\\0&\lambda _{2}&\beta _{2} &\lpisteet &0\\0&0&\lambda _{3}&\lpisteet &0\\\vpisteet &\vpisteet &\vpisteet &\dpisteet &\vpisteet \\0&0&0&\lpisteet &\lambda _{n}\end{bmatrix} },

missä λ i ovat ominaisarvoja, β i = 1 , jos ( A - λ i +1 ) v i +1 = v i ja β i = 0 muuten.

Jos W on käännettävä matriisi ja λ on matriisin A ominaisarvo vastaavalla juurivektorilla v , niin ( W - 1 AW -λE ) k W - k v = 0 . Siten λ on matriisin W - 1 AW ominaisarvo vastaavalla juurivektorilla W - kv . Näin ollen samanlaisilla matriiseilla on samat ominaisarvot.

Normaali-, hermiittiset ja reaalisymmetriset matriisit

Hermiittinen konjugaattimatriisi M * kompleksiseen matriisiin M on transponoitu matriisi, jonka kaikki elementit on korvattu konjugaattiarvoilla: M * = M T . Neliömatriisia A kutsutaan normaaliksi , jos se kommutoidaan hermiittisen konjugaatin kanssa: A * A = AA * . Matriisia kutsutaan hermiitiksi , jos se on yhtä suuri kuin sen konjugaatti: A * = A . Kaikki Hermitian matriisit ovat normaaleja. Jos A: lla on vain reaalialkiot, niin sen konjugaatti on vain transponoitu matriisi, ja se on hermiittinen jos ja vain jos se on symmetrinen . Kun tätä sovelletaan sarakkeisiin, konjugassia voidaan käyttää kanonisen pistetulon määrittämiseen C n :ssä: w • v = w * v [huomautus 3] . Normaaleilla, hermiittisillä ja todellisilla symmetrisillä matriiseilla on useita hyödyllisiä ominaisuuksia:

Jokainen normaalimatriisin juuriominaisvektori on yksinkertainen ominaisvektori.
Mikä tahansa normaali matriisi on samanlainen kuin diagonaalinen matriisi, koska sen normaali Jordan-muoto on diagonaalinen matriisi.
Normaalimatriisin eri ominaisarvoja vastaavat ominaisvektorit ovat ortogonaalisia.
Millä tahansa normaalimatriisilla A C n :llä on ortonormaali kanta, joka koostuu matriisin A ominaisvektoreista . Vastaava ominaisvektorimatriisi on unitaarinen .
Hermiittisen matriisin ominaisarvot ovat reaalilukuja, koska ( λ - λ) v = ( A * - A ) v = ( A - A ) v = 0 nollasta poikkeavalle ominaisvektorille v .
Jos matriisi A on todellinen, niin R n :llä on ortonormaali kanta, joka koostuu matriisin A ominaisvektoreista, jos ja vain jos A on symmetrinen.

Sekä todellisten että kompleksisten matriisien kaikki ominaisarvot voivat olla todellisia ilman, että ne ovat hermiittisiä matriisia. Esimerkiksi todellisella kolmiomatriisilla on kaikki ominaisarvonsa diagonaalissa, mutta se ei yleensä ole symmetrinen.

Kuntonumero

Mitä tahansa laskennallisen matematiikan ongelmaa voidaan pitää jonkin funktion ƒ laskemisena jostakin argumentista x . Tehtävän ehtoluku κ (ƒ, x ) on laskentatuloksen suhteellisen virheen suhde funktioparametrin suhteelliseen virheeseen ja riippuu sekä funktiosta että parametrista. Ehtonumero kuvaa kuinka paljon virhe kasvaa laskennan aikana. Tämän luvun desimaalilogaritmi osoittaa, kuinka monta merkkiä menetämme suhteessa alkuperäisiin tietoihin. Ehtonumero viittaa parhaaseen skenaarioon, mikä kuvastaa itse ongelman epävakautta ratkaisusta riippumatta. Mikään algoritmi ei voi antaa parempaa tulosta kuin ehtonumeron määräämä tulos, paitsi ehkä sattumalta. Huonosti suunniteltu algoritmi voi kuitenkin antaa huomattavasti huonompia tuloksia. Esimerkiksi, kuten alla mainitaan, normaalin matriisin ominaisarvojen löytämisen ongelma on aina hyvin ehdollinen, mutta polynomin juurien löytämisen ongelma voi olla erittäin huonosti ehdollinen . Sellaiset ominaisarvoalgoritmit, jotka toimivat etsimällä ominaispolynomin juuret, voivat olla huonosti ehdollisia, vaikka itse ongelma olisikin hyvin ehdoiteltu.

Lineaarisen yhtälöjärjestelmän A v = b ratkaisutehtävälle , jossa A on käännettävä, ehtoluku κ ( A -1 , b ) saadaan kaavalla || A || op || A -1 || op , missä || || op on C n : n tavalliselle euklidiselle normille alisteinen operaattorinormi . Koska tämä luku on riippumaton b :stä ja on sama sekä A :lle että A -1 :lle , sitä kutsutaan yleisesti matriisin A ehtonumeroksi κ ( A ) . Tämä arvo κ ( A ) on myös matriisin A suurimman ominaisarvon ja sen pienimmän ominaisarvon suhteen itseisarvo. Jos A on unitaarinen , niin || A || op = || A -1 || op = 1 , joten κ ( A ) = 1 . Yleensä matriiseille operaattorinormin laskeminen on usein vaikeaa. Tästä syystä ehtoluvun arvioimiseen käytetään yleensä muita matriisinormeja .

Ominaisuusarvojen laskentaongelmaa varten Bauer ja Faik osoittivat , että jos λ on n × n diagonalisoitavan matriisin A ominaisarvo ominaisvektorimatriisin V kanssa , niin absoluuttinen virhe laskettaessa λ on κ :n ( V ) tulon rajoittama. ja absoluuttinen virhe A :ssa : [2] . Tämän seurauksena ehtonumero λ:n laskemiseksi on κ ( λ, A ) = κ ( V ) = || V || op || V -1 || op . Jos matriisi A on normaali, niin V on unitaarinen ja κ (λ, A ) = 1 . Siten normaalimatriisien ominaisarvojen laskentaongelma on hyvin ehdollinen. ${\displaystyle \;\;|\delta \lambda |\leqslant \kappa _{op}(V)\|\delta A\|_{op))$

Osoitettiin, että ominaisarvoa λ vastaavan normaalimatriisin A ominaisaliavaruuden laskentatehtävän ehtonumero on kääntäen verrannollinen λ :n ja matriisin A muiden, λ :sta poikkeavien ominaisarvojen väliseen vähimmäisetäisyyteen [3] . Erityisesti ongelma ominaisaliavaruuden määrittämisessä normaaleille matriiseille on hyvin ehdollinen eristetyille ominaisarvoille. Jos ominaisarvoja ei ole eristetty, parasta, mitä voimme toivoa, on määrittää läheisten ominaisarvojen kaikkien ominaisvektoreiden aliavaruus.

Algoritmit

Mikä tahansa normalisoitu polynomi on mukana tulevan matriisin ominaispolynomi , joten ominaisarvojen laskenta-algoritmia voidaan käyttää polynomien juurien löytämiseen. Abel-Ruffinin lause osoittaa, että minkä tahansa sellaisen algoritmin dimensiolle, joka on suurempi kuin 4, täytyy olla joko ääretön tai sisältää funktioita, jotka ovat monimutkaisempia kuin aritmeettiset alkeisoperaatiot tai murto-osat. Tästä syystä algoritmeja, jotka laskevat täsmälleen ominaisarvot äärellisessä määrässä vaiheita, on olemassa vain erityisille matriisiluokille. Yleisessä tapauksessa algoritmit ovat iteratiivisia ja antavat jokaisessa iteraatiossa ratkaisun seuraavan approksimation.

Jotkut algoritmit antavat kaikki ominaisarvot, toiset useita arvoja tai jopa yhden, mutta näitä algoritmeja voidaan käyttää kaikkien ominaisarvojen laskemiseen. Kun matriisin A ominaisarvo λ on määritetty, sitä voidaan käyttää joko pakottamaan algoritmi tuottamaan toinen ominaisarvo tai pelkistämään ongelma sellaiseksi, jossa λ ei ole ratkaisuna.

Pelkistys tehdään yleensä siirrolla: A korvataan A - μ E jollakin vakiolla μ . A - μE :lle löydetty ominaisarvo on lisättävä μ : ään matriisin A ominaisarvon saamiseksi . Esimerkiksi tehomenetelmässä μ = λ . Tehomenetelmän iteraatio löytää suurimman arvon absoluuttisena arvona, joten vaikka λ on ominaisarvon approksimaatio, tehomenetelmän iteraatio ei todennäköisesti löydä sitä toista kertaa. Päinvastoin, taaksepäin iteraatiomenetelmät löytävät pienimmän ominaisarvon, joten μ valitaan pois λ :sta sen toivossa, että se olisi lähempänä jotain muuta ominaisarvoa.

Pelkistys voidaan tehdä kaventamalla matriisi A matriisin A - λ E sarakeavaruuteen . Koska A - λ E on degeneroitunut, sarakeavaruuden ulottuvuus on pienempi. Ominaisarvon laskenta-algoritmia voidaan sitten soveltaa tähän kavennetun matriisin. Prosessia voidaan jatkaa, kunnes kaikki ominaisarvot on löydetty.

Jos algoritmi ei tuota k ominaisarvoa, on yleinen käytäntö käyttää taaksepäin iteraatioon perustuvaa algoritmia, jossa μ asetetaan ominaisarvon lähimpään approksimaatioon. Tämä johtaa nopeasti ominaisvektoriin, jonka ominaisarvo on lähimpänä μ :tä . Pienille matriiseille vaihtoehtona on käyttää tuotteen A - λ́ E sarakealiavaruutta kullekin muulle ominaisarvolle λ́.

Hessenberg-matriisit ja tridiagonaaliset matriisit

Koska kolmiomatriisin ominaisarvot ovat diagonaalisyötteitä, ei yleensä ole olemassa äärellistä menetelmää, kuten Gaussin eliminaatio , matriisin kolmiottamiseksi ominaisarvot säilyttäen, mutta jotain kolmiomatriisia lähellä voidaan saada. Ylempi Hessenberg-matriisi on neliömatriisi, jossa kaikki ensimmäisen osadiagonaalin alapuolella olevat elementit ovat nolla. Alempi Hessenberg-matriisi on neliömatriisi, jossa kaikki ensimmäisen superdiagonaalin yläpuolella olevat termit ovat nolla. Matriisit, jotka ovat sekä alempia että ylempiä Hessenberg-matriiseja, ovat kolmikulmaisia matriiseja . Hessenberg-matriisit ja kolmikulmaiset matriisit ovat lähtökohta monille ominaisarvojen laskentaalgoritmille, koska nolla-arvot vähentävät ongelman monimutkaisuutta. On olemassa useita menetelmiä matriisien pelkistämiseksi Hessenberg-matriiseiksi, joilla on samat ominaisarvot. Jos alkuperäinen matriisi on symmetrinen tai hermiittinen, tuloksena oleva matriisi on kolmikulmainen.

Jos tarvitaan vain ominaisarvoja, samankaltaisuusmatriisia ei tarvitse laskea, koska muunnetulla matriisilla on samat ominaisarvot. Jos tarvitaan myös ominaisvektoreita, tarvitaan samankaltaisuusmatriisi, joka muuntaa Hessenberg-matriisin ominaisvektorit alkuperäisen matriisin ominaisvektoreiksi.

Menetelmä	Koskee matriiseja	Tulos	Hinta ilman samankaltaisuusmatriisia	Hinta samankaltaisuusmatriisin kanssa	Kuvaus
Kotitalousmuutoksia	yleisnäkymä	Hessenbergin matriisi	2 n 3 ⁄ 3 +O(n2)[4]	4 n 3 ⁄ 3 +O(n2)[4]	Heijasta jokaista saraketta aliavaruuden suhteen nollataksesi sarakkeen alaelementit.
Antaa vuoroja	yleisnäkymä	Hessenbergin matriisi	4 n 3 ⁄ 3 +O(n2)[4]		Tasainen kierto suoritetaan yksittäisten elementtien nollaamiseksi. Kierrokset on järjestetty siten, että seuraavat kierrokset eivät vaikuta nollaelementteihin.
Arnoldin iteraatiot	yleisnäkymä	Hessenbergin matriisi			Gram–Schmidt- ortogonalisointi Krylov-aliavaruuksille suoritetaan .
Lanczos-algoritmi [5]	Eremiittiläinen	kolmikulmainen matriisi			Arnoldi-iteraatiot hermiittisille matriiseille.

Iteratiiviset algoritmit

Iteratiiviset algoritmit ratkaisevat ominaisarvojen laskentaongelman rakentamalla sekvenssejä, jotka konvergoivat ominaisarvoihin. Jotkut algoritmit antavat myös vektorisekvenssejä, jotka konvergoivat ominaisvektoreihin. Useimmiten ominaisarvojen sekvenssit ilmaistaan samankaltaisten matriisien sekvensseinä, jotka konvergoivat kolmio- tai diagonaalimuotoon, mikä helpottaa ominaisarvojen saamista. Ominaisuusvektorisekvenssit ilmaistaan vastaavina samankaltaisuusmatriiseina.

Menetelmä	Koskee matriiseja	Tulos	Hinta per askel	Lähentyminen	Kuvaus
Tehomenetelmä	yleisnäkymä	suurin ominaisarvo ja vastaava vektori	O ( n2 ) _	Lineaarinen	Moninkertainen matriisin kertominen mielivaltaisesti valitulla alkuvektorilla, jota seuraa normalisointi.
Käänteinen tehomenetelmä	yleisnäkymä	μ:tä lähinnä oleva ominaisarvo ja vastaava vektori		Lineaarinen	Tehoiteraatio matriisilla ( A - μ E ) -1
Rayleighin iteraatiomenetelmä	yleisnäkymä	μ:tä lähinnä oleva ominaisarvo ja vastaava vektori		kuutio	Tehoiteraatio matriisilla ( A - μ i E ) -1 , missä μ i on Rayleigh-suhde edellisestä iteraatiosta.
Ehdollinen taaksepäin iterointi [6] tai LOBPCG	positiivinen selvä reaalisymmetrinen	μ:tä lähinnä oleva ominaisarvo ja vastaava vektori			Käänteinen iteraatio esikäsittelyllä (matriisin A likimääräinen inversio ).
puolitusmenetelmä [7]	todellinen symmetrinen kolmikulmainen	mikä tahansa ominaisarvo		Lineaarinen	Etsii puolittamismenetelmällä ominaispolynomin juuret ja Sturm-sekvenssin ominaisuudet .
Laguerren iteraatiot	todellinen symmetrinen kolmikulmainen	mikä tahansa ominaisarvo		Kuutio [8]	Käyttää Laguerren menetelmää ominaispolynomin juurien ja Sturm-sekvenssin ominaisuuksien laskemiseen .
QR-algoritmi [9]	hessenberg	kaikki ominaisarvot	O ( n2 ) _	kuutio	Dekompositio A = QR , jossa Q on ortogonaalinen, R on kolmio, sitten käytetään iteraatiota RQ :han .
QR-algoritmi [9]	hessenberg	kaikki ominaisarvot	6 n 3 + O ( n 2 )	kuutio
Jacobin menetelmä	todella symmetrinen	kaikki ominaisarvot	O ( n 3 )	neliöllinen	Käyttää Givensin kiertoa yrittääkseen päästä eroon diagonaalisista elementeistä. Yritys epäonnistuu, mutta vahvistaa diagonaalia.
hajota ja hallitse	Eremiittinen kolmikulmainen	kaikki ominaisarvot	O ( n2 ) _		Matriisi jaetaan alimatriiseiksi, jotka diagonalisoidaan ja yhdistetään sitten uudelleen.
hajota ja hallitse	Eremiittinen kolmikulmainen	kaikki ominaisarvot	( 4 ⁄ 3 ) n 3 + O ( n 2 )
Homotopian menetelmä	todellinen symmetrinen kolmikulmainen	kaikki ominaisarvot	O ( n 2 ) [10]		Laskennallinen homotoopia rakennetaan.
Spektrikonvoluutiomenetelmä	todella symmetrinen	μ:tä lähinnä oleva ominaisarvo ja vastaava ominaisvektori			Esikäsitelty takaisin iteraatio sovellettu kohtaan ( A - μ E ) 2
MRRR-algoritmi [11]	todellinen symmetrinen kolmikulmainen	jotkin tai kaikki ominaisarvot ja vastaavat ominaisvektorit	O ( n2 ) _		"Multiple Relatively Robust Representations" - Käänteinen iteraatio suoritetaan puolueettoman matriisin LDL T -hajotuksella .

Suora laskenta

Ei ole olemassa yksinkertaisia algoritmeja matriisien ominaisarvojen suoraan laskemiseen yleisessä tapauksessa, mutta monille erityisluokille matriisien ominaisarvot voidaan laskea suoraan. Se:

Kolmiomatriisit

Koska kolmiomatriisin determinantti on sen diagonaalielementtien tulo, kolmiomatriisin T . Siten T :n ominaisarvot ovat sen diagonaalisia elementtejä. $\mathrm {det} \left(\lambda ET\right)={\prod }_{i}\left(\lambda -T_{ii}\right)$

Hajottavat polynomiyhtälöt

Jos p on mikä tahansa polynomi ja p ( A ) = 0, niin matriisin A ominaisarvot täyttävät saman yhtälön. Jos polynomi p voidaan kertoa, niin A :n ominaisarvot ovat sen juurissa.

Esimerkiksi projektori on neliömatriisi P , joka täyttää yhtälön P 2 = P . Vastaavan skalaaripolynomiyhtälön λ 2 = λ juuret ovat 0 ja 1. Projektorilla on siis 0 ja 1 ominaisarvoina. Ominaisarvon 0 monikertaisuus on P : n vika , kun taas 1:n monikertaisuus on P :n arvo .

Toinen esimerkki on matriisi A , joka täyttää yhtälön A 2 = α 2 E jollekin skalaarille α . Ominaisuusarvojen tulee olla yhtä suuria kuin ±α . Suunnitteluoperaattorit

P_{+}={\frac {1}{2}}\left(E+{\frac {A}{\alpha }}\right)

P_{-}={\frac {1}{2}}\left(E-{\frac {A}{\alpha }}\right)

tyydyttää tasa-arvot

AP_{+}=\alpha P_{+}\quad AP_{-}=-\alpha P_{-}

P_{+}P_{+}=P_{+}\quad P_{-}P_{-}=P_{-}\quad P_{+}P_{-}=P_{-}P_{+} =0.

Matriisien P + ja P - sarakeavaruudet ovat matriisin A ominaisvektoreiden aliavaruuksia , jotka vastaavat +α :ta ja -α :aa .

Matriisit 2×2

Dimensiolle 2–4 on olemassa radikaalikaavoja, joita voidaan käyttää ominaisarvojen laskemiseen. 2x2- ja -matriiseilla tämä on yleinen käytäntö, mutta 4x4-matriiseille juurikaavojen kasvava monimutkaisuus tekee tästä lähestymistavasta vähemmän houkuttelevan.

2×2 matriiseille

A={\begin{bmatrix}a&b\\c&d\end{bmatrix)),

ominaispolynomi on

{\rm {det)){\begin{bmatrix}\lambda -a&-b\\-c&\lambda -d\end{bmatrix))=\lambda ^{2}\,-\,\left (a+d\oikea)\lambda \,+\,\left(ad-bc\right)=\lambda ^{2}\,-\,\lambda \,{\rm {tr))(A)\ ,+\,{\rm {det}}(A).

Ominaisarvot löytyvät toisen asteen yhtälön juurina :

\lambda ={\frac {{\rm {tr}}(A)\pm {\sqrt ({\rm {tr}}^{2}(A)-4{\rm {det}}( A)}}}{2}}.

Jos se määritellään kahden ominaisarvon väliseksi etäisyydeksi, se on helppo laskea $\textstyle {\rm {gap}}\left(A\right)={\sqrt ({\rm {tr}}^{2}(A)-4{\rm {det}}(A) }}$

{\frac {\partial \lambda }{\partial a))={\frac {1}{2))\left(1\pm {\frac {ad}({\rm {gap))( A)))\right),\qquad {\frac {\partial \lambda }{\partial b))={\frac {\pm c}({\rm {rako))(A)))

vastaavilla kaavoilla c :lle ja d :lle . Tästä seuraa, että laskenta on hyvin ehdollinen, jos ominaisarvot on eristetty.

Ominaisuusvektorit voidaan saada käyttämällä Hamilton-Cayleyn lausetta . Jos λ 1 , λ 2 ovat ominaisarvoja, niin ( A - λ 1 E )( A - λ 2 E ) = ( A - λ 2 E )( A - λ 1 E ) = 0 , joten sarakkeet ( A - λ 2 ) E ) asetetaan nollaan matriisin ( A - λ 1 E ) avulla ja päinvastoin. Olettaen, että mikään matriiseista ei ole nolla, jokaisen matriisin sarakkeiden tulee sisältää ominaisvektorit toiselle ominaisarvolle (jos matriisi on nolla, niin A on identiteettimatriisin tulo vakiolla ja mahdollisilla ei- nollavektori on ominaisvektori).

Esimerkiksi anna

A={\begin{bmatrix}4&3\\-2&-3\end{bmatrix)),

silloin tr( A ) = 4 - 3 = 1 ja det( A ) = 4(-3) - 3(-2) = -6 , joten ominaisyhtälö on

0=\lambda ^{2}-\lambda -6=(\lambda -3)(\lambda +2),

ja ominaisarvot ovat 3 ja −2. Nyt

A-3E={\begin{bmatrix}1&3\\-2&-6\end{bmatrix}}

\qquad A+2E={\begin{bmatrix}6&3\\-2&-1\end{bmatrix}}

Molemmissa matriiseissa sarakkeet eroavat toisistaan skalaarikertoimien mukaan, joten mikä tahansa sarake voidaan valita. Joten (1, -2) voidaan käyttää ominaisarvoa −2 vastaavana ominaisvektorina ja (3, -1) ominaisarvon 3 ominaisvektorina, joka voidaan helposti tarkistaa kertomalla matriisilla A .

Matriisit 3×3

Jos A on 3 × 3 matriisi, ominaisyhtälö on:

{\rm {det))\left(\alpha EA\right)=\alpha ^{3}-\alpha ^{2}{\rm {tr))(A)-\alpha {\frac { 1}{2}}\vasen({\rm {tr}}(A^{2})-{\rm {tr}}^{2}(A)\oikea)-{\rm {det}}( A)=0.

Tämä yhtälö voidaan ratkaista Cardanon tai Lagrangen menetelmillä, mutta matriisin A affiinimuunnos yksinkertaistaa huomattavasti lauseketta ja johtaa suoraan trigonometriseen ratkaisuun . Jos A = pB + qE , niin A: lla ja B :llä on samat ominaisvektorit ja β on matriisin B ominaisarvo silloin ja vain jos α = pβ + q on matriisin A ominaisarvo . Jos laitamme ja , saamme $\textstyle q={\rm {tr))(A)/3$ ${\displaystyle \textstyle p=\left({\rm {tr))\left((A-qE)^{2}\oikea)/6\oikea)^{1/2))$

{\rm {det))\left(\beta EB\right)=\beta ^{3}-3\beta -{\rm {det))(B)=0.

Korvaus β = 2cos θ ja jokin yksinkertaistaminen käyttämällä identiteettiä cos 3 θ = 4cos 3 θ - 3cos θ vähentää yhtälön arvoon cos 3 θ = det( B ) / 2 . Tällä tavalla,

\beta =2{\rm {cos}}\left({\frac {1}{3}}{\rm {arccos}}\left({\rm {det}}(B)/2\ oikea)+{\frac {2k\pi }{3}}\right),\quad k=0,1,2.

Jos det( B ) on kompleksiluku tai suurempi kuin 2 absoluuttisena arvona, kaikkien kolmen k -arvon käänteiskosini tulee ottaa samasta haarasta. Ongelmaa ei esiinny, jos A on todellinen ja symmetrinen, mikä johtaa yksinkertaiseen algoritmiin: [12]

% Kun on annettu todellinen symmetrinen 3x3 matriisi A, laske ominaisarvot p1 = A ( 1 , 2 ) ^ 2 + A ( 1 , 3 ) ^ 2 + A ( 2 , 3 ) ^ 2 jos ( p1 == 0 ) % A on diagonaali. eig1 = A ( 1 , 1 ) eig2 = A ( 2 , 2 ) eig3 = A ( 3 , 3 ) muu q = jälki ( A ) / 3 p2 = ( A ( 1 , 1 ) - q ) ^ 2 + ( A ( 2 , 2 ) - q ) ^ 2 + ( A ( 3 , 3 ) - q ) ^ 2 + 2 * p1 p = neliö ( p2 / 6 ) B = ( 1 / p ) * ( A - q * E ) % E on identiteettimatriisi r = det ( B ) / 2 % Tarkassa aritmetiikassa symmetriselle matriisille -1 <= r <= 1 %, mutta laskentavirhe voi jättää sen hieman tämän alueen ulkopuolelle. jos ( r <= - 1 ) phi = pi / 3 elseif ( r >= 1 ) phi = 0 muu phi = acos ( r ) / 3 loppu % ominaisarvot täyttävät eig3 <= eig2 <= eig1 eig1 = q + 2 * p * cos ( phi ) eig3 = q + 2 * p * cos ( phi + ( 2 * pi / 3 )) eig2 = 3 * q - eig1 - eig3 %, koska jälki(A) = eig1 + eig2 + eig3 loppu

Jälleen A :n ominaisvektorit voidaan saada käyttämällä Hamilton-Cayleyn lausetta . Jos α 1 , α 2 , α 3 ovat matriisin A eri ominaisarvoja , niin ( A - α 1 E ) ( A - α 2 E ) ( A - α 3 E ) = 0 . Sitten minkä tahansa kahden matriisin tulon sarakkeet sisältävät kolmannen ominaisarvon ominaisvektorit. Kuitenkin , jos a3 = a 1 , niin ( A - α1E ) 2 ( A - α2E ) = 0 ja ( A - α2E ) ( A - α1E ) 2 = 0 . _ _ Siten varsinaisen juurialiavaruuden α 1 kattaa sarakkeet A - α 2 E , kun taas tavallinen oikea aliavaruus kattaa sarakkeet ( A - α 1 E ) ( A - α 2 E ) . Tavallinen oikea aliavaruus α 2 kattaa sarakkeet ( A - α 1 E ) 2 .

Esimerkiksi anna

A={\begin{bmatrix}3&2&6\\2&2&5\\-2&-1&-4\end{bmatrix}}.

Ominainen yhtälö on

0=\lambda ^{3}-\lambda ^{2}-\lambda +1=(\lambda -1)^{2}(\lambda +1),

ominaisarvoilla 1 (kerroin 2) ja −1. Laskea

AE={\begin{bmatrix}2&2&6\\2&1&5\\-2&-1&-5\end{bmatrix)),\qquad A+E={\begin{bmatrix}4&2&6\\2&3&5\\-2& -1&-3\end{bmatrix}}

ja sitten

(AE)^{2}={\begin{bmatrix}-4&0&-8\\-4&0&-8\\4&0&8\end{bmatrix)),\qquad (AE)(A+E)={\ alku{bmatrix}0&4&4\\0&2&2\\0&-2&-2\end{bmatrix}}

Sitten (-4, -4, 4) on ominaisvektori funktiolle −1 ja (4, 2, -2) on ominaisvektori luvulle 1. Vektorit (2, 3, -1) ja (6, 5, -3) ovat arvoa 1 vastaavat juurivektorit, joista mikä tahansa voidaan yhdistää (-4, -4, 4) ja (4, 2, -2) matriisin A juurivektorien perustaksi .

Katso myös

Luettelo ominaisarvon laskentaalgoritmeista

Kommentit

↑ Termiä "yksinkertainen" käytetään tässä vain korostamaan eroa "omavektorin" ja "juurivektorin" välillä.
↑ jossa vakiotermi kerrotaan identiteettimatriisilla E .
↑ Tämä järjestys skalaaritulossa (konjugaattielementti vasemmalla) on fyysikojen suosima. Algebraistit suosivat usein merkintää w • v = v * w .

Muistiinpanot

↑ Sheldon Axler. Alas Determinantit! // American Mathematical Monthly. - 1995. - Numero. 102 . - S. 139-154 .
↑ FL Bauer, CT Fike. Normit ja poissulkemislauseet // Numero. Matematiikka. - 1960. - Numero. 2 . - S. 137-141 .
↑ SC Eisenstat, ICF Ipsen. Suhteelliset häiriötulokset diagonalisoitavien matriisien ominaisarvoille ja ominaisvektoreille // BIT. - 1998. - T. 38 , no. 3 . - S. 502-9 . - doi : 10.1007/bf02510256 .
↑ 1 2 3 William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numeeriset reseptit C. - 2nd. - Cambridge University Press, 1992. - ISBN 0-521-43108-5 .
↑ Kh. D. Ikramov. Harvat matriisit. - 1982. - T. 20. - (Tieteen ja tekniikan tuloksia. Ser. Mat. anal.).
↑ K. Neymeyr. Geometrinen teoria esiehdolliseen käänteiseen iteraatioon IV: Nopeimmissa konvergenssitapauksissa. // Linear Algebra Appl. - 2006. - T. 415 , no. 1 . - S. 114-139 . - doi : 10.1016/j.laa.2005.06.022 .
↑ Wilkinson, 1970 , s. 274, Bisection Method
↑ T. Y Li, Zhonggang Zeng. Laguerren iteraatio symmetrisen kolmikulmaisen ominaisongelman ratkaisemisessa - Revisited // SIAM Journal on Scientific Computing . – 1992.
↑ Parlett, 1983 , s. 156, luku 8, QR- ja QL-algoritmit
↑ Moody T. Chu. Huomautus homotopiamenetelmästä lineaarisille algebrallisille ominaisarvotehtäville // Lineaarialgebra Appl. - 1988. - T. 105 . - S. 225-236 . - doi : 10.1016/0024-3795(88)90015-8 .
↑ Inderjit S. Dhillon, Beresford N. Parlett, Christof Vömel. MRRR-algoritmin suunnittelu ja toteutus // ACM Transactions on Mathematical Software . - 2006. - T. 32 , no. 4 . - S. 533-560 . - doi : 10.1145/1186785.1186788 .
↑ Oliver K. Smith. Symmetrisen 3 × 3 matriisin ominaisarvot // ACM:n tiedonsiirto . - T. 4 , no. 4 . - S. 168 . - doi : 10.1145/355578.366316 .

Kirjallisuus

J. Golub, C. Van Lone. Matriisilaskelmat. - Moskova: Mir, 1999. - ISBN 5-03-002406-9 .
B. Parlett. Symmetrinen ominaisarvon ongelma. - Moskova: Mir, 1983.
J. H. Wilkinson. Algebrallinen ominaisarvotehtävä. - Moskova: "Nauka" Fysikaalisen ja matemaattisen kirjallisuuden pääpainos, 1970.

Lue lisää

Adam W. Bojanczyk, Adam Lutoborski. Symmetrisen 3X3-matriisin Euler-kulmien laskeminen // SIAM Journal on Matrix Analysis and Applications. - Tammikuu 1991. - T. 12 , no. 1 . - S. 41-48 . - doi : 10.1137/0612005 .