[Algorytm] Wartości własne macierzy

[Arciv]

Mam problem z napisaniem algorytmu do wyznaczania wartości własnych macierzy.

Niby prosto jest zaimplementować ten algorytm z standardowego wyznacznika macierzy \(\displaystyle{ (A-\lambda I)}\) jednak mam tutaj problem z obliczeniem wielomianu charakterystycznego, tzn. obliczanie go dla macierzy \(\displaystyle{ 2\times 2}\) oraz \(\displaystyle{ 3\times 3}\) nie stanowi problemu, ale mój program ma w założeniach obliczać wartości własne nawet dla macierzy \(\displaystyle{ 640\times 640}\) a nie wiem jak takowy wielomian otrzymać z wzorów na wyznacznik.

Szukając algorytmu po źródłach znalazłem w "Metodach przybliżonych obliczeń" Położego algorytm Kryłowa pozwalający obliczyć wielomian charakterystyczny, jednak po kilku próbach przeliczenia tego ręcznie dla stosunkowo małych macierzy nie daje on zadowalających wyników.

Oczywiście stosowałem też metodę Jacobiego jednak jest ona niezbyt precyzyjna.

Reasumując, jeżeli zna ktoś prawidłowy i dokładny algorytm wyznaczania wartości własnych macierzy bądź chociaż wielomianu charakterystycznego, bardzo proszę o pomoc.

Pozdrawiam!

[Fibik]

Obliczamy ten wielomian bez problemu, a potem wyliczasz zera wielomianu.

Kolejne zera wielomianu wyliczamy jakąś tam metodą numeryczną, i z tzw. deflacją.
Zera wyliczamy w kolejności od najmniejszego (modułu), wtedy błędy są najmniejsze.

Ja kiedyś obliczałem to metodą Laguerra - 3go rzędu z arytm. na zespolonych.

[Zordon]

Obliczamy ten wielomian bez problemu,

Czyli jak?

[steal]

A może spróbuj użyć

Kod: Zaznacz cały

http://matrix.umcs.lublin.pl/~lbocian/Studia/Pracownia_obliczen_numerycznych_II/algorytm_qr.htm

?

[Fibik]

Jak obliczać wielomiany to mówiłem: metoda + deflacja.



deflacja czynnikiem liniowym i kwadratowym, ponieważ niektóre zera są zespolone, więc symetryczne, czyli można wyliczamy po dwa (unikamy wtedy dzieleń przez wielomiany z zespolonymi wsp. - mamy cały czas wielomian z rzeczywistymi wsp.).

Ja stosowałem metodę Laguerra, bo ona sama znajduje zera w poprawnej kolejności - od najmniejszego, wystarczy wystartować od x = 0.
[gdybyśmy chcieli użyć metody Newtona, albo innej podobnej - sieczne czy coś tam, byłby tam problem ze znalezieniem zespolonych, bo ta metoda nigdy nie wskoczy w urojone, gdy startujemy z rzeczywistej]

Potem deflacja, liniowa lub kwadratowa, zależnie czy mamy zespolone czy rzeczywiste zero;
no i loop - liczymy kolejne zero.

Przykładowe równanie:
\(\displaystyle{ x^5 + 2x^4 + 4x^3 + 8x^2 + 16x + 32 = 0}\)
więc wpisuję współczynniki wielomianu: 1,2,4,8,16,32... i mam wyniki:
-1 - i1.73205080756888
-1 + i1.73205080756888
-2
1 - i1.73205080756888
1 + i1.73205080756888

[Arciv]

@Fabik, jak pisałem nie mam problemu z wyznaczeniem miejsc zerowych wielomianu, a z wyznaczeniem samego wielomianu.

@steal, dzięki bardzo. Z tego co się zorientowałem algorytm Jacobiego jest przydatny jedynie dla macierzy symetrycznych o rozmiarach \(\displaystyle{ <25}\), potem QR bije go szybkością obliczeń na głowę, no ale z tym też mam problem.

Macierz \(\displaystyle{ n\times n}\). Wykonuje się \(\displaystyle{ n-2}\) iteracji (tu wybieram metodę eliminacji Gaussa bo daje najmniejszą ilość obliczeń), otrzymując \(\displaystyle{ n}\) macierzy, z których ostatnia jest macierzą Hessenberga. O ile w algorytmie Jacobiego po iteracji dającej wymaganie niski błąd, wartości własne znajdują się na diagonalnej macierzy to w QR nie rozumiem gdzie one są.

[steal]

Dla macierzy symetrycznej wartości własne będą na diagonali macierzy \(\displaystyle{ A^{(k)}}\) z ostatniej iteracji.

[Arciv]

Dla macierzy symetrycznej wartości własne będą na diagonali macierzy \(\displaystyle{ A^{(k)}}\) z ostatniej iteracji.

A jak z pozostałymi przypadkami? Np. macierz trójkątna górna/dolna, zwykła macierzy niesymetryczna?

[steal]

Bodajże macierz trójkątna, z zespolonymi wartościami własnymi na diagonali.

[Arciv]

Reasumując macierz symetryczna \(\displaystyle{ <25\longrightarrow}\)algorytm Jacobiego, wartości własne na diagonelnej.
Dowolna macierz\(\displaystyle{ \longrightarrow}\)rozkład QR, wartości na diagonalnej macierzy z ostatniej iteracji.

Dziękuję bardzo za pomoc, myślę że już z tym dam radę napisać algorytm.

[Fibik]

O ile pamiętam nie ma większych problemów wyliczeniem tego wyznacznika,
dlatego robiłem ten algor do zer wielomianów zamiast pieprzyć się z tymi zdecydowanie wolniejszymi iteracyjnymi metodami wyliczania własnych.

[Zordon]

O ile pamiętam nie ma większych problemów wyliczeniem tego wyznacznika,

Aha.

[Fibik]

A co, jest z tym problem?

Kiedyś męczyłem te sprawy z układami linowych rr. pierwszego rzędu, no i ostatecznie doszedłem do wniosku że problem wyliczania wprost z tych macierzy, i tak jest równoważny w praktyce z jednym równaniem n-tego rzędu, czyli wystarczy rozwiązać ten wielomian charakterystyczny.

A było to chyba z 10 lat temu więc może czegoś nie pamiętam...
nie ma dobrego algorytmu do przekształcenia układu w jedno równanie?

Obroty Givensa czy inne takie manewry, są dobre ale chyba do rzadkich macierzy...

Aha! Precyzja double za mała - tylko 15 cyfr to strasznie słabiutko...
No to bierzemy double-double albo quad-double - 60 cyfr to już kosmos.