Metodę potęgową można traktować jako iteracje podprzestrzeni
jednowymiarowej startujące ze . Naturalnym
uogólnieniem tego procesu są iteracje podprzestrzeni o wyższych
wymiarach. Właśnie iteracje podprzestrzeni są punktem wyjścia
konstrukcji obecnie najpopularniejszego algorytmu QR, którego zadaniem
jest obliczenie jednocześnie wszystkich wartości własnych.
Chociaż metody prezentowane w tym rozdziale mogą być stosowane
w większej ogólności, dla uproszczenia będziemy zakładać, że
macierz jest nieosobliwa, rzeczywista i symetryczna,
tzn.
i
. Przypomnijmy,
że wtedy istnieje baza ortonormalna
wektorów
własnych macierzy,
![]() |
Będziemy również zakładać, że wartości własne są uporządkowane tak, że
![]() |
Niech oraz
będzie
podprzestrzenią o wymiarze
. Dla
rozpatrzmy
następujące iteracje:
![]() |
Oczywiście, wobec nieosobliwości wszystkie podprzestrzenie
mają też wymiar
.
Pokażemy, że przy pewnych niekrępujących założeniach ciąg podprzestrzeni
zbiega do podprzestrzeni własnej
![]() |
przy czym przez ,,zbieżność” rozumiemy tu zbieżność do zera kąta pomiędzy tymi podprzestrzeniami.
Przypomnijmy, że kąt pomiędzy dwiema podprzestrzeniami
definiujemy jako
![]() |
(Jako ćwiczenie można wykazać, że jeśli
to
.)
Niech
![]() |
Jeśli to
![]() |
Niech będzie wektorem spełniającym
. Wtedy
![]() |
gdzie nie wszystkie dla
, są są zerowe, oraz
. Stąd
![]() |
(3.1) |
Jeśli teraz dla
oraz
to
z (3.1) wynika, że
![]() |
co kończy dowód.
∎W praktyce, iteracje podprzestrzeni realizujemy reprezentując
kolejne przez ich bazy ortonormalne. Wtedy algorytm,
zwany w tym przypadku również iteracjami ortogonalnymi,
przybiera następującą postać.
Wybieramy macierz kolumnowo-ortogonalną
formatu
jako
macierz startową, a następnie dla
iterujemy:
![]() |
przy czym w drugiej linii następuje ortonormalizacja macierzy realizowana
poprzez rozkład tej macierzy na iloczyn macierzy kolumnowo-ortonormalnej
formatu
i macierzy trójkątnej górnej
formatu
.
Dokonuje się tego znanym nam już algorytmem wykorzystującym odbicia Householdera.
łatwo zauważyć, że jeśli przyjmiemy, iż wektory-kolumny macierzy
tworzą bazę ortonormalną podprzestrzeni
to w kolejnych krokach
wektory-kolumny
tworzą bazę ortonormalną podprzestrzeni
. Rzeczywiście, ponieważ
to kolumny
stanowią bazę
. Kolumny te są z kolei liniową kombinacją
kolumn
, czyli rozpinają tą samą podprzestrzeń co kolumny
.
Poczynimy teraz kluczową obserwację. Przypuśćmy, że wszystkie wartości
własne są parami różne. Gdybyśmy rozpoczynali iteracje
od macierzy
składającej się jedynie z
początkowych kolumn macierzy
, przy czym
, to otrzymane
w procesie iteracyjnym macierze
i
(formatu
i
) byłyby odpowiednio
,,okrojonymi” macierzami
i
. Stąd, jeśli wszystkie wartości własne
macierzy
mają różne moduły, to dla każdego takiego
podprzestrzeń
rozpięta na początkowych
wektorach macierzy
,,zbiega” do podprzestrzeni własnej
, przy czym
![]() |
Z powyższej obserwacji wynika, że gdybyśmy realizowali iteracje
podprzestrzeni przyjmując i startując z macierzy identycznościowej
formatu
to mielibyśmy zbieżność
do podprzestrzeni własnych
dla wszystkich
.
W przypadku gdy pracujemy na bazach ortogonalnych i startujemy z ,
zbieżność tą można wyrazić również w następujący sposób. Oznaczmy
![]() |
Niech będzie macierzą przejścia od bazy
do
,
![]() |
Dla , niech
![]() |
gdzie jest podmacierzą formatu
, a pozostałe
podmacierze odpowiednio formatów
,
,
. Jeśli
i
to
![]() |
Niech ,
, gdzie
i
są formatu
. Wtedy
![]() |
Mnożąc to równanie z lewej strony przez dostajemy
. Stąd
![]() |
Oznaczając zauważamy, że
i
. Stąd wektor
zawiera współczynniki
rzutu ortogonalnego
na
w bazie
. Z definicji normy drugiej
i twierdzenia 3.1 dostajemy więc
![]() |
Rozumując analogicznie i wykorzystując fakt, że
![]() |
dostajemy taką samą nierówność dla .
Z lematu 3.1 wynika natychmiast, że jeśli moduły wartości
własnych macierzy są parami różne to wyrazy pozadiagonalne
macierzy
zbiegają do zera, a ponieważ
jest
ortogonalna, to
zbiegają do jedynki. Algorytm (IO)
można więc uzupełnić o obliczanie w każdym kroku macierzy
![]() |
która powinna zbiegać do
.
Fakt ten, łącznie z analizą szybkości zbieżności, pokażemy
formalnie w następnym podrozdziale.
Załóżmy, że realizujemy algorytm iteracji ortogonalnych (IO) z macierzą
początkową . Wtedy
, skąd
![]() |
Oznaczając widzimy, że ostatnia równość to nic innego jak
rozkład ortogonalno-trójkątny macierzy
,
![]() |
Prawdziwe są więc związki rekurencyjne
![]() |
![]() |
![]() |
||
![]() |
![]() |
|||
![]() |
![]() |
![]() |
Zależności te prowadzą do ALGORYTMU QR, który oblicza
kolejne macierze i
w następujący sposób.
![]() |
||||
![]() |
||||
(QR) | ![]() |
Przypomnijmy, że w rozkładzie ortogonalno-trójkątnym macierz
ortogonalna jest wyznaczona jednoznacznie z dokładnością do znaków
jej wektorów-kolumn. Dlatego macierze (a tym samym także
)
powstałe w wyniku realizacji algorytmów (IO) i (QR) nie muszą być
takie same. Algorytmy te są jednak równoważne w następującym sensie.
Niech ,
i
,
będą macierzami
powstałymi w wyniku realizacji odpowiednio algorytmów (IO) i (QR). Wtedy
![]() |
gdzie są pewnymi macierzami diagonalnymi z elementami
na głównej przekątnej.
Zastosujemy indukcję względem . Dla
mamy
oraz
.
Załóżmy, że lemat jest prawdziwy dla
, tzn.
. Wtedy, z jednej strony
![]() |
a z drugiej strony
![]() |
Mamy więc
![]() |
przy czym równości te przedstawiają dwa rozkłady ortogonalno-trójkątne
tej samej macierzy . A jeśli tak, to czynniki
ortogonalne tych rozkładów różnią się jedynie znakami kolumn.
Równoważnie, istnieje macierz diagonalna
z elementami
na głównej
przekątnej taka, że
![]() |
Stąd
![]() |
Dowód kończy następujący rachunek:
![]() |
Zauważmy jeszcze, że jeśli przez i
oznaczymy odpowiednio elementy macierzy
i
oraz
z
to
![]() |
To oznacza, że dla elementy te różnią się jedynie znakiem,
a dla
są sobie równe.
Jesteśmy już gotowi do przedstawienia twierdzeń o zbieżności metody QR.
Dla , niech
i
.
Niech dalej
![]() |
gdzie podmacierze są
formatu
, a pozostałe podmacierze formatów odpowiednio
,
i
. Wtedy,
przyjmując
![]() |
mamy \tg oraz
![]() |
![]() |
![]() |
(3.2) | ||
![]() |
![]() |
![]() |
(3.3) | ||
![]() |
![]() |
![]() |
(3.4) |
Wobec wykazanej w lemacie \tg (teoretycznej) równoważności metody
QR i iteracji (IO), nierówność została
już udowodniona w twierdzeniu 3.1. Aby pokazać (3.3),
zapiszemy
w postaci
, gdzie
i
składają się odpowiednio z pierwszych
i z ostatnich
kolumn
macierzy
. Wtedy
![]() |
gdzie . Pisząc
,
podobnie jak dla
, mamy teraz
![]() |
Ponieważ to
, natomiast
, jak pokazaliśmy w dowodzie
lematu 3.1.
Pisząc z kolei
![]() |
w analogiczny sposób pokazujemy, że
i
. Stąd mamy
![]() |
Dokładnie tak samo pokazujemy oszacowanie dla .
Aby pokazać (3.2) zauważmy, że wobec mamy też
. Ale
![]() |
co w połączeniu z (3.3) dowodzi (3.2).
W końcu, wobec mamy
![]() |
Nierówność (3.4) wynika teraz z nierówności
, (3.2), (3.3),
oraz
.
Z twierdzenia 3.2 wynika, że elementy pozadiagonalne
macierzy zbiegają do zera liniowo, przy czym iloraz zbieżności
zależy od wartości
. Dokładniej,
dla danego elementu
macierzy
, gdzie
,
prawdziwe jest oszacowanie
![]() |
(gdzie skorzystaliśmy także z faktu, że moduł pojedynczego elementu macierzy jest nie większy od normy drugiej tej macierzy).
A jaka jest zbieżność elementów diagonalnych do wartości własnych
macierzy
? Oznaczmy
![]() |
Dla wszystkich mamy
![]() |
Elementy diagonalne macierzy
zbiegają więc do
wartości własnych
macierzy
co najmniej jak
dla
,
dla
,
oraz
dla
.
Tak jak w przypadku metody potęgowej, można spróbować przyspieszyć zbieżność
metody QR poprzez przesunięcie widma macierzy , czyli zastosowanie QR do macierzy
. Oznaczmy przez
kolejne macierze powstające
w tym procesie. Z wcześniejszej analizy metody QR wynika, że jeśli
![]() |
to wyraz w prawym dolnym rogu macierzy
zbiega do
i zbieżność jest tym lepsza
im
jest bliższe
. Dlatego ważne jest, aby
wybrać tak, aby dobrze aproksymowała jedną z wartości własnych macierzy
.
Oczywiście, przesunięcie możnaby w każdym kroku wybierać w zależności
od aktualnie dostępnej informacji. Metoda wyglądałaby wtedy następująco:
![]() |
||||
![]() |
||||
(QR-shift) | ![]() |
Jasne, że
![]() |
tzn. kolejne macierze są ortogonalnie podobne. Okazuje się, że
QR ma jeszcze jedną ważną własność.
Oznaczmy przez
ostatnią kolumnę macierzy
, przez
wyraz w prawym dolnym rogu macierzy trójkątnej górnej
, oraz przez
ostatni wersor. Wtedy dla każdego
mamy
![]() |
![]() |
![]() |
||
![]() |
![]() |
|||
![]() |
![]() |
|||
![]() |
![]() |
czyli
![]() |
To zaś oznacza, że w kolejnych krokach iteracji QR z przesunięciami
ostatnia kolumna macierzy
jest taka sama jak wektor
w odwrotnej
metodzie potęgowej z wektorem startowym
i kolejnymi przesunięciami
. A jeśli tak, to możemy wykorzystać wyniki rozdziału 2.4
i stwierdzić, że dobrym wyborem przesunięcia jest
![]() |
Przy tak dobranym dostajemy asymptotycznie zbieżność sześcienną
elementu
do
.
Dla informacji podamy jeszcze, że możliwy jest też wybór
przesunięcia Wilkinsona, gdzie jako bierze się tą
wartość własną macierzy
,
![]() |
która jest najbliższa , a jeśli obie są jednakowo oddalone
od
to mniejszą z nich. Wtedy co prawda nie zwiększamy szybkości
zbieżności, ale za to metoda jest zawsze zbieżna.
Pozostałe wartości własne macierzy możemy obliczyć stosując deflację.
Mianowicie, gdy już jesteśmy dostatecznie blisko wartości własnej
(co zwykle osiąga się wykonując kilka kroków QR i sprawdza przez obliczenie
residuum
) to uznajemy, że
wyrazy w ostatniej kolumnie i ostatnim wierszu macierzy
, poza wyrazem
, są zerowe i redukujemy problem do macierzy formatu
.
Oczywiście, ten ogólny przepis wymaga właściwej implementacji.
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
Projekt współfinansowany przez Unię Europejską w ramach
Europejskiego Funduszu Społecznego.
Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.