|
|
| Linia 1: |
Linia 1: |
| ==Wyznaczanie wektorów i wartości własnych==
| |
|
| |
|
| Niech będzie dana rzeczywista kwadratowa macierz <math>A</math> wymiaru <math>N</math>. Wektorem własnym <math>x\in C^N</math> oraz
| |
| odpowiadającą mu wartością własną <math>\lambda \in C</math> nazwiemy taką parę, dla której
| |
|
| |
| <center><math>A x = \lambda x,
| |
| </math></center>
| |
|
| |
| przy czym <math>x\neq 0</math>.
| |
|
| |
| Zadanie wyznaczania {hopla} wartości własnych !hopla! i wektorów własnych macierzy ma bardzo
| |
| szerokie zastosowania w tak odległych do siebie dziedzinach jak np. analiza
| |
| odporności konstrukcji mechanicznych (wieżowce, mosty, wagony kolejowe) na
| |
| wibracje, czy też rankingowanie stron internetowych w wyszukiwarce Google.
| |
|
| |
| {{przyklad|[Uzupelnij]||
| |
| [Odporność budynku na trzęsienie ziemi]
| |
| Rozważmy prosty układ mechaniczny opisujący, naturalnie w pewnym
| |
| jedynie przybliżeniu, zachowanie się układu <math>N</math> ciężkich płyt połączonych ze
| |
| sobą relatywnie elatycznymi dźwigarami --- co może np. modelować konstrukcję
| |
| wieżowca.
| |
|
| |
| {}{Model wieżowca poddanego drganiom poprzecznym}
| |
|
| |
| Wiadomo, że jeśli częstotliwości drgań własnych tego wieżowca będą bliskie
| |
| częstotliwości siły wymuszającej (o niewielkiej amplitudzie), to konstrukcja
| |
| wpadnie w rezonans i w końcu rozpadnie się wskutek zbyt wielkich przemieszczeń.
| |
| Wychylenia naszych płyt z położenia równowagi są opisywane układem pewnych
| |
| równań różniczkowych.
| |
| Teoria matematyczna takich równań różniczkowych pokazuje, że częstotliwości
| |
| drgań własnych to nic innego jak ''wartości własne'' pewnej
| |
| {niesymetrycznej} macierzy
| |
| wymiaru <math>2N</math>,
| |
| która powstaje ze współczynników równania różniczkowego opisującego dynamikę
| |
| tego układu.
| |
| }}
| |
|
| |
| {{przyklad|[Uzupelnij]||
| |
| [Macierz Google'a]
| |
| Podstawowy algorytm rankingowania stron WWW w {http://www.wikipedia.org/pagerank}{wyszukiwarce Google}
| |
| sprowadza się do znalezienia rzeczywistego ''wektora własnego'' <math>\pi</math> pewnej silnie
| |
| rozrzedzonej macierzy <math>A</math> (gigantycznego rozmiaru, równego liczbie indeksowanych
| |
| stron, czyli w chwili pisania tego tekstu około XXXX stron), odpowiadającego wartości własnej równej 1:
| |
|
| |
| <center><math>A \pi = \pi.
| |
| </math></center>
| |
|
| |
| Współrzędne wektora <math>\pi</math>
| |
| interpretuje się jako wartość rankingową kolejnych stron WWW. Aby wszystko miało
| |
| sens, współrzędne wektora muszą być z przedziału [0,1]. Pewne
| |
| twierdzenia matematyczne i subtelny dobór macierzy <math>A</math> gwarantują, że taki
| |
| wektor <math>\pi</math> zawsze istnieje i jest jedyny! Co więcej, wartość 1 jest
| |
| dominującą wartością własną <math>A</math>, a to z kolei ma ważne znaczenie dla tzw.
| |
| {sec:metoda-potegowa}{metody potęgowej} numerycznego wyznaczania takiego wektora.
| |
| }}
| |
|
| |
| {{przyklad|[Uzupelnij]||
| |
| [Wyznaczanie miejsc zerowych wielomianu]
| |
| Jak wiadomo, wartości własne to miejsca zerowe wielomianu charakterystycznego
| |
| macierzy <math>P(\lambda) = \det(A - \lambda I)</math>. Zachodzi także fakt odwrotny, to
| |
| znaczy miejsca zerowe wielomianu są wartościami pewnej macierzy, np. miejsca
| |
| zerowe wielomianu
| |
|
| |
| <center><math>p(\lambda) = p_1 \lambda^N + \ldots + p_N \lambda + p_{N+1}
| |
| </math></center>
| |
|
| |
| są wartościami własnymi m.in. macierzy stowarzyszonej,
| |
|
| |
| <center><math>A = \begin{pmatrix}
| |
| -p_2/p_1 & -p_3/p_1 & \cdots & -p_{N+1}/p_1\\
| |
| 1 & & & \\
| |
| & 1 & & \\
| |
| & & \ddots & \\
| |
| & & & 1
| |
| \end{pmatrix}
| |
| </math></center>
| |
|
| |
| Funkcja Octave'a !compan(p)! wyznacza macierz stowarzyszoną dla zadanego
| |
| wielomianu o współczynnikach w wektorze <math>p = [p_1,\ldots,p_N, p_{N+1}]^T</math>. Z tej
| |
| macierzy korzysta następnie funkcja Octave'a !roots! właśnie w taki
| |
| sposób wyznacza pierwiastki wielomianów: jako wartości własne macierzy
| |
| stowarzyszonej.
| |
| }}
| |
|
| |
| {{przyklad|[Uzupelnij]||
| |
|
| |
| Praktyczne zadanie z macierzą symetryczną
| |
| }}
| |
|
| |
| W praktyce obliczeniowej spotyka się zazwyczaj kilka typów zagadnień:
| |
|
| |
| * Wyznaczenie dominującej wartości własnej (to znaczy: największej co do
| |
| modułu) i odpowiadającego jej wektora własnego (a może kilku wektorów?)
| |
|
| |
| * Wyznaczenie najmniejszej co do modułu wartości własnej i wektorów jej
| |
| odpowiadających (zauważmy, że to jest np. zadanie wyznaczenia ''jądra
| |
| macierzy osobliwej'' --- wtedy wiemy a priori, że szukana najmniejsza co do modułu
| |
| wartość własna to zero)
| |
|
| |
| * Wyznaczenie wartości własnej najbliższej zadanej liczbie (to jest właśnie
| |
| odpowiedź na pytanie jak blisko częstości wymuszającej są częstości drgań
| |
| własnych budynku)
| |
|
| |
| * Wyznaczenie wszystkich wartości własnych
| |
|
| |
| * Wyznaczenie wszystkich wartości i wektorów własnych (tzw. pełne
| |
| zagadnienie własne)
| |
|
| |
| Jak domyślamy się, dla macierzy rozrzedzonych dużego wymiaru pełne zagadnienie
| |
| własne jest zbyt kosztowne, gdyż najczęściej macierz wektorów własnych --- nawet
| |
| dla macierzy rzadkiej --- jest gęsta.
| |
|
| |
| Ponieważ w zastosowaniach bardzo często pojawiają się macierze rzeczywiste
| |
| symetryczne (powyższe przykłady pokazują, że nie tylko!) szczegółową analizę
| |
| metod numerycznych ograniczymy do tego przypadku, gdyż wtedy zachodzi
| |
|
| |
| {{twierdzenie|[Uzupelnij]||
| |
| [o symetrycznym zadaniu włanym]
| |
|
| |
| Każda macierz rzeczywista symetryczna <math>A</math> wymiaru <math>N</math> ma rozkład
| |
|
| |
| <center><math>A = Q\Lambda Q^T,
| |
| </math></center>
| |
|
| |
| gdzie <math>Q\in R^{N\times N}</math> jest ortogonalna (tzn. <math>Q^TQ = I</math>), a jej kolumnami są
| |
| wektory własne <math>A</math>, natomiast <math>\Lambda\in
| |
| R^N</math> jest diagonalna z
| |
| wartościami własnymi <math>A</math> na diagonali:
| |
|
| |
| <center><math>\Lambda = \beginpmatrix \lambda_1 & & \\ & \ddots & \\ & &
| |
| \lambda_N\endpmatrix .
| |
| </math></center>
| |
|
| |
| }}
| |
|
| |
| ===Uwarunkowanie zadania===
| |
|
| |
| {{twierdzenie|[Uzupelnij]||
| |
| [Bauer-Fike]
| |
|
| |
| Niech <math>A\in R^{N\times N}</math> będzie diagonalizowalna, to
| |
| znaczy dla pewnej macierzy <math>X</math> zachodzi
| |
|
| |
| <center><math>X^{-1} A X = \beginpmatrix \lambda_1 & & \\ & \ddots & \\ & &
| |
| \lambda_N\endpmatrix ,
| |
| </math></center>
| |
|
| |
| a więc (gdyż macierz po prawej stronie jest podobna do <math>A</math>) <math>\lambda_i\in C</math>,
| |
| <math>i=1,\ldots,N</math> są
| |
| wartościami własnymi <math>A</math>. Rozważmy macierz zaburzoną <math>\tilde{A}</math> i jakąś jej
| |
| wartość własną <math>\tilde{\lambda}</math>. Wtedy istnieje wartość własna <math>\lambda_j</math>
| |
| macierzy <math>A</math> taka, że
| |
|
| |
| <center><math>|\lambda_j - \tilde{\lambda}| \leq \mbox{cond}_2(X) ||A - \tilde{A}||_2.
| |
| </math></center>
| |
|
| |
| }}
| |
|
| |
| Ponieważ dla rzeczywistej macierzy symetrycznej macierz przejścia <math>X</math> jest
| |
| ortogonalna,
| |
| <math>X^{-1} = X^T</math>, to mamy <math>\mbox{cond}_2(X) = 1</math> i w konsekwencji zachodzi
| |
|
| |
| {{wniosek|[Uzupelnij]||
| |
| [Wartości własne macierzy symetrycznej są doskonale uwarunkowane]
| |
| Przy oznaczeniach jak {thm:Bauer-Fike}{twierdzeniu Bauera-Fike'a}, jeśli
| |
| dodatkowo założymy, że macierz <math>A</math> jest rzeczywista i symetryczna, to
| |
|
| |
| <center><math>\min_{j=1,\ldots,N}|\lambda_j - \tilde{\lambda}| \leq ||A - \tilde{A}||_2.
| |
| </math></center>
| |
|
| |
| }}
| |
|
| |
| Z drugiej strony, dla macierzy niediagonalizowalnych, uwarunkowanie wartości
| |
| własnych może być
| |
| dowolnie duże, co ilustruje poniższy
| |
|
| |
| {{przyklad|[Uzupelnij]||
| |
|
| |
| <center><math>A_\epsilon = \beginpmatrix a & 1 \\ \epsilon & a \endpmatrix
| |
| </math></center>
| |
|
| |
| Weźmy dla uproszczenia <math>a=0</math>.
| |
| Wartości własne <math>A_\epsilon</math> to zera wielomianu <math>p_\epsilon(\lambda) = \lambda^2 - \epsilon</math>,
| |
| zatem <math>\lambda_\epsilon = \pm \sqrt{\epsilon}</math> i w konsekwencji
| |
|
| |
| <center><math>|\lambda_\epsilon - \lambda_0| / ||A_\epsilon - A_0|| = \sqrt{\epsilon}/\epsilon
| |
| \rightarrow \infty,
| |
| </math></center>
| |
|
| |
| gdy <math>\epsilon \rightarrow 0^+</math>, a więc uwarunkowanie takiego zadania jest
| |
| nieskończone: dowolnie mała zmiana macierzy powoduje zaburzenie wartości
| |
| własnych niewspółmiernie wielkie wobec zaburzenia danych. Dodatkowo, wartości własne i wektory własne macierzy <math>A</math> dla
| |
| ujemnego parametru <math>\epsilon</math> są zespolone!
| |
|
| |
| {eigencond.png}{Zachowanie się wartości własnych macierzy <math>A</math> (z
| |
| parametrem <math>a=1</math>) w otoczeniu <math>\delta = 0</math>}
| |
|
| |
| }}
| |
|
| |
| Bardziej spektakularny przykład pochodzi od Wilkinsona:
| |
|
| |
| {{przyklad|[Uzupelnij]||
| |
| [Perfidny wielomian Wilkinsona]
| |
| Niech
| |
|
| |
| <center><math>p(\lambda) = (\lambda -1)(\lambda - 2) \cdots (\lambda - 20).
| |
| </math></center>
| |
|
| |
| Zmiana współczynnika przy <math>\lambda^{19}</math> o <math>10^{-7}</math> skutkuje presunięciem niektórych
| |
| miejsc zerowych nawet o kilka jednostek na płaszczyźnie zespolonej! Poniżej
| |
| pokazujemy to na numerycznym przykładzie, gdzie prócz w/w zaburzenia mamy
| |
| dodatkowo z zaburzeniami powstałymi wskutek wyznaczenia współczynników
| |
| wielomianu w arytmetyce zmiennoprzecinkowej.
| |
|
| |
| {wilkinson.png}{Zera oryginalnego i lekko zaburzonego perfidnego wielomianu
| |
| Wilkinsona.}
| |
|
| |
| Jak widzimy, zera bardzo mało zaburzonego wielomianu mogą stać się wyraźnie nie-rzeczywiste!
| |
|
| |
| }}
| |
|
| |
| Jeśli chodzi o wektory własne, ich wrażliwość na zaburzenia macierzy jest
| |
| bardziej skomplikowana i zależy m.in. od uwarunkowania wartości własnych (czego
| |
| łatwo się domyślić) oraz od tego, jak blisko siebie leżą wartości własne.
| |
|
| |
| ===Lokalizacja wartości własnych===
| |
|
| |
| Jak okaże się za chwilę, czasem warto mieć ogólne rozeznanie o tym, gdzie ''z
| |
| grubsza'' leżą wartości własne danej macierzy <math>A</math>. W tym celu mogą być nam
| |
| pomocne dwa fakty:
| |
|
| |
| {{fakt|[Uzupelnij]||
| |
|
| |
| Dowolna wartość własna <math>\lambda\in C</math> macierzy <math>A</math> spełnia
| |
|
| |
| <center><math>|\lambda| \leq ||A||,
| |
| </math></center>
| |
|
| |
| gdzie <math>||A||</math> jest dowolną normą macierzową indukowaną przez normę wektorową.
| |
| }}
| |
|
| |
| Rzeczywiście, skoro istnieje wektor <math>x\neq 0</math> taki, że <math>Ax = \lambda x</math>, to stąd
| |
| <math>||Ax||/||x|| = |\lambda|</math>, więc fakt powyższy wynika już z definicji normy
| |
| macierzy:
| |
|
| |
| <center><math>||A|| = \max_{y\neq 0}\frac{||Ay||}{||y||} \geq ||Ax||/||x||.
| |
| </math></center>
| |
|
| |
| Drugie twierdzenie jest równie proste w dowodzie, ale daje trochę więcej
| |
| informacji o lokalizacji widma.
| |
|
| |
| {{twierdzenie|[Uzupelnij]||
| |
| [Gerszgorina]
| |
| Wartości własne macierzy <math>A</math> leżą w sumie (teoriomnogościowej) dysków <math>K_i</math> na
| |
| płaszczyźnie zespolonej,
| |
|
| |
| <center><math>K_i = \{z \in C: |z - a_{ii}| \leq \sum_{j\neq i} |a_{ij}| \}, \qquad i =
| |
| 1,\ldots N.
| |
| </math></center>
| |
|
| |
| }}
| |
|
| |
| {{przyklad|[Uzupelnij]||
| |
| [Koła Gerszgorina]
| |
| Niech
| |
|
| |
| <center><math>A = \begin{pmatrix}
| |
| 1.08930 & 1.38209 & -1.00037 & 0.69355 & 2.32178 \\
| |
| 0.14211 & 1.74696 & 1.68440 & 0.30664 & 1.26718 \\
| |
| -0.74620 & 2.02686 & -0.68293 & 0.19684 & 0.35854 \\
| |
| 0.83517 & 0.74987 & 1.71331 & 1.09765 & -0.44321 \\
| |
| 1.02132 & -2.62155 & 0.79247 & 1.11408 & 0.48076 \\
| |
| \end{pmatrix}
| |
| </math></center>
| |
|
| |
| {gershgorindisks.png}{Lokalizacja wartości własnych macierzy <math>A</math> kołami Gerszgorina oraz zgrubna
| |
| lokalizacja wewnątrz okręgu
| |
| o promieniu równym <math>||A||_1</math>. Dokładne wartości własne zaznaczone trójkącikami.}
| |
|
| |
| }}
| |
|
| |
| {{przyklad|[Uzupelnij]||
| |
| [Widmo macierzy jednowymiarowego Laplasjanu]
| |
| Norma daje:
| |
|
| |
| Tw. Gerszgorina daje:
| |
|
| |
| W rzeczywistości,
| |
|
| |
| }}
| |
|
| |
| ===Metoda potęgowa, odwrotna potęgowa, RQI===
| |
|
| |
| ====Metoda potęgowa====
| |
|
| |
| Przypuśćmy, że wartości własne macierzy <math>A\in R^{N\times N}</math> spełniają
| |
|
| |
| <center><math>|\lambda_1| > |\lambda_2| \geq \ldots \geq |\lambda_N|,
| |
| </math></center>
| |
|
| |
| (to znaczy, istnieje dokładnie jedna ''dominująca'' wartość własna macierzy
| |
| <math>A</math>.
| |
|
| |
| Załóżmy także, że istnieje baza złożona z wektorów własnych <math>q_1,\ldots,q_N</math> tej
| |
| macierzy (tak jest np. dla macierzy symetrycznej na mocy
| |
| {thm:symetric-eig}{twierdzenia o własnościach symetrycznego zadania
| |
| własnego}).
| |
|
| |
| Kierunek własny <math>q_k</math> jakiejś macierzy <math>A</math> ma taką własność, że poddany działaniu przekształcenia
| |
| <math>A</math> wydłuża się <math>\lambda_k</math> razy, wobec tego, dowolny wektor <math>x\in R^N</math> poddany
| |
| działaniu <math>A</math> najbardziej wydłuży się w kierunku <math>q_1</math>. Iterując tę procedurę,
| |
| powinniśmy dostawać w wyniku wektory, w których coraz bardziej dominuje kierunek
| |
| <math>q_1</math>. Formalnie, niech
| |
|
| |
| <center><math>x = \alpha_1q_1 + \ldots + \alpha_Nq_N,
| |
| </math></center>
| |
|
| |
| wtedy
| |
|
| |
| <center><math>Ax = A \left( \sum_i \alpha_iq_i \right) = \sum_i \alpha_i A q_i
| |
| = \sum_i \alpha_i \lambda_i q_i
| |
| </math></center>
| |
|
| |
| i w konsekwencji
| |
|
| |
| <center><math>A^kx = \sum_i \alpha_i \lambda_i^k q_i = \lambda_1^k\left(\alpha_1q_1 +
| |
| \alpha_2\left(\frac{\lambda_2}{\lambda_1}\right)^kq_2 + \ldots +
| |
| \alpha_N\left(\frac{\lambda_N}{\lambda_1}\right)^kq_N \right).
| |
| </math></center>
| |
|
| |
| Ponieważ z założenia, że istnieje dokładnie jedna dominująca wartość własna,
| |
| <math>\left|\frac{\lambda_N}{\lambda_1}\right| < 1</math>, to wyrażenie w nawiasie dąży do
| |
| <math>\alpha_1q_1</math> i w konsekwencji wektory <math>x_k = A^kx</math> dążą, gdy
| |
| <math>k\rightarrow\infty</math>, do kierunku wektora własnego <math>q_1</math>, to znaczy wektora
| |
| odpowiadającego dominującej wartości własnej <math>A</math> (o ile tylko <math>\alpha_1
| |
| \neq 0</math>).
| |
|
| |
| Szybkość zbieżności metody potęgowej jest liniowa, o współczynniku zależnym od
| |
| stosunku <math>\lambda_2/\lambda_1|</math>. W patologicznym przypadku, gdy <math>|\lambda_1|
| |
| \approx |\lambda_2|</math>, może więc okazać się, że metoda praktycznie nie jest
| |
| zbieżna.
| |
|
| |
| W praktyce nie wyznaczamy wzorem <math>x_k = (A^k)\cdot x</math>, lecz raczej korzystamy z
| |
| metody iteracyjnej
| |
|
| |
| [title<nowiki>=</nowiki>Metoda potęgowa]
| |
| <math>x_0</math> <nowiki>=</nowiki> dowolny wektor startowy; k <nowiki>=</nowiki> 0;
| |
| while ( !stop )
| |
| {
| |
| <math>y_k</math> <nowiki>=</nowiki> <math>Ax_{k-1}</math>;
| |
| <math>x_k</math> <nowiki>=</nowiki> <math>y_k/||y_k||_\infty</math>;
| |
| k++;
| |
| }
| |
|
| |
| Warunek normowania ma m.in. na celu zapobieżenie powstawania nadmiaru i
| |
| niedomiaru (gdy <math>|\lambda_1| < 1</math>, to <math>||A^kx|| \rightarrow 0</math>, a gdy
| |
| <math>|\lambda_1| > 1</math>, to <math>||A^kx|| \rightarrow \infty</math>). Przy okazji,
| |
| <math>||y_k||_\infty \rightarrow |\lambda_1|</math>, a więc mamy także sposób na wyznaczenie
| |
| przybliżenia dominującej wartości własnej.
| |
|
| |
| Zazwyczaj jako warunek stopu wybiera się kryterium małej poprawki, <math>||x_k -
| |
| x_{k-1}|| \leq \epsilon</math>, lub warunek małego residuum, <math>||Ax_k - \lambda_{1,k}
| |
| x_k||\leq \epsilon</math>, gdzie <math>\lambda_{1,k}</math> jest przybliżeniem <math>\lambda_1</math>
| |
| dostępnym na <math>k</math>-tej iteracji.
| |
|
| |
| {}{Zasada działania metody potęgowej}
| |
|
| |
| Metoda potęgowa doskonale sprawdza się, gdy macierz <math>A</math> jest macierzą
| |
| rozrzedzoną --- np. w przypadku macierzy Google'a.
| |
|
| |
| ====Odwrotna metoda potęgowa====
| |
|
| |
| Zauważmy, że dla dowolnej macierzy kwadratowej <math>A</math> o wartościach własnych
| |
| <math>\lambda_k</math> i odpowiadających im wektorach własnych <math>q_k</math>, mamy:
| |
|
| |
| * Macierz <math>A-\sigma I</math> ma wartości własne <math>\lambda_k - \sigma</math> oraz wektory
| |
| własne <math>q_k</math>,
| |
|
| |
| * Jeśli dodatkowo <math>A</math> jest nieosobliwa, to macierz <math>A^{-1}</math> ma wartości
| |
| własne <math>1/\lambda_k</math> oraz wektory własne <math>q_k</math>
| |
|
| |
| Łącząc te dwie własności mamy, że
| |
|
| |
| {{stwierdzenie|[Uzupelnij]||
| |
| [Transformacja widma macierzy]
| |
| Macierz <math>(A-\sigma I)^{-1}</math> (o ile istnieje),
| |
| to ma wartości własne równe <math>\frac{1}{\lambda_k - \sigma}</math> i wektory własne
| |
| identyczne z <math>A</math>.
| |
| }}
| |
|
| |
| Skoro tak, to jeśli najbliższą <math>\sigma</math> wartością własną <math>A</math> jest <math>\lambda_j</math>,
| |
| wówczas metoda potęgowa zastosowana do macierzy <math>(A-\sigma I)^{-1}</math> zbiegnie do
| |
| <math>q_j</math>. To prowadzi do następującego algorytmu, odwrotnej metody potęgowej:
| |
|
| |
| [title<nowiki>=</nowiki>Odwrotna metoda potęgowa]
| |
| <math>x_0</math> <nowiki>=</nowiki> dowolny wektor startowy; k <nowiki>=</nowiki> 0;
| |
| while( !stop )
| |
| {
| |
| Rozwiąż układ równań <math>(A-\sigma I)y_k = x_{k-1}</math>;
| |
| <math>x_k</math> <nowiki>=</nowiki> <math>y_k/||y_k||_\infty</math>;
| |
| k++;
| |
| }
| |
|
| |
| ====Metoda Rayleigh====
| |
|
| |
| Z własności metody potęgowej, metoda odwrotna potęgowa jest zbieżna tym
| |
| szybciej, im bliżej <math>\lambda_j</math> jest przesunięcie <math>\sigma</math> (w stosunku do
| |
| pozostałych wartości własnych). Dlatego dobrze byłoby --- dla zwiększenia
| |
| szybkości zbieżności iteracji --- poprawiać wartość przesunięcia <math>\sigma</math>,
| |
| korzystając z dotychczas wyznaczonego wektora <math>x_k \approx q_j</math> i ilorazu
| |
| Rayleigh:
| |
|
| |
| <center><math>\lambda_j = \frac{q_j^TAq_j}{q_j^Tq_j} \approx \frac{x_k^TAx_k}{x_k^Tx_k}
| |
| </math></center>
| |
|
| |
| [title<nowiki>=</nowiki>Metoda RQI (Rayleigh Quotient Iteration)]
| |
| <math>x_0</math> <nowiki>=</nowiki> dowolny wektor startowy; <math>\sigma_0</math> <nowiki>=</nowiki> przybliżenie <math>\lambda_j</math>; k <nowiki>=</nowiki> 0;
| |
| while( !stop )
| |
| {
| |
| Rozwiąż układ równań <math>(A-\sigma_k I)y_k = x_{k-1}</math>;
| |
| <math>x_k</math> <nowiki>=</nowiki> <math>y_k/||y_k||_2</math>;
| |
| <math>\sigma_{k+1}</math> <nowiki>=</nowiki> <math>x_k^TAx_k</math>;
| |
| k++;
| |
| }
| |
|
| |
| (wybierając normowanie wektora <math>x</math> w normie euklidesowej upraszczamy co nieco
| |
| algorytm).
| |
|
| |
| Wielką zaletą metody RQI jest jej szybkość zbiezności: kwadratowa gdy wartość
| |
| własna jest pojedyncza, a nawet sześcienna w przypadku macierzy symetrycznej.
| |
|
| |
| Wadą metody RQI jest to, że na każdym jej kroku należy rozwiązywać układ równań
| |
| z ''inną'' macierzą.
| |
|
| |
| {{uwaga|[Uzupelnij]||
| |
| [Gdy złe uwarunkowanie pomaga...]
| |
| Przez pewien czas numerycy odnosili się do tej metody z rezerwą,
| |
| twierdząc, i słusznie, że im lepszym przybliżeniem <math>q_j</math> będzie <math>\sigma_k</math>, tym
| |
| bardziej rośnie uwarunkowanie <math>A-\sigma_k I</math>, a tym samym --- błąd numerycznego
| |
| rozwiązywania układu z tą macierzą będzie coraz większy i metoda będzie tracić
| |
| stabilność. Tymczasem okazuje się, że --- choć rzeczywiście tak jest ---
| |
| wektor błędu ma kierunek praktycznie zgodny z kierunkiem poszukiwanego wektora
| |
| <math>q_j</math>, a tym samym tylko ''pomaga'' w zbieżności metody!
| |
| }}
| |
|
| |
| ===Metoda dziel i rządź, metoda QR===
| |
|
| |
| {}{Secular equation}
| |
|
| |
| ======
| |
|
| |
| ===Biblioteki===
| |
