Cztery początkowe wykłady poświęcimy zagadnieniu własnemu. Naszym zadaniem będzie obliczenie, a raczej numeryczna aproksymacja wartości własnych danej macierzy kwadratowej (jednej, kilku, lub wszystkich). W ogólniejszym sformułowaniu możemy chcieć obliczyć również odpowiednie wektory własne.
Pierwszy wykład będzie dotyczyć przede wszystkim wrażliwości wartości i wektorów własnych na zaburzenia macierzy. Jak wiemy z podstawowego wykładu analizy numerycznej, jest to istotne z punktu widzenia numerycznej jakości algorytmów.
Zaczniemy od przypomnienia podstawowych pojęć i faktów z algebry liniowej dotyczących zagadnienia własnego, z których skorzystamy w dalszej części wykładu.
Liczbę (zespoloną) nazywamy wartością własną macierzy kwadratowej jeśli istnieje niezerowy wektor taki, że
Wektor nazywamy wektorem własnym odpowiadającym wartości własnej .
Równoważnie, jest wartością własną macierzy gdy jest zerem jej wielomianu charakterystycznego, tzn. gdy wyznacznik
gdzie jest macierzą identycznościową . Krotnością algebraiczną wartości własnej nazywamy jej krotność jako zera wielomianu charakterystycznego.
Zbiór wszystkich wektorów własnych odpowiadających danej wartości własnej , uzupełniony o wektor zerowy, czyli zbiór , jest podprzestrzenią liniową zwaną podprzestrzenią własną odpowiadającą . Wymiar tej podprzestrzeni to krotność geometryczna wartości własnej .
Wektory własne odpowiadające różnym wartościom własnym są liniowo niezależne.
Macierze są podobne gdy istnieje nieosobliwa macierz taka, że . Oczywiście, relacja ,,bycia macierzami podobnymi” jest symetryczna.
Macierze podobne mają te same wartości własne. Jeśli bowiem to , tzn. jest wartością własną , a odpowiadający jej wektor własny to .
Macierz jest diagonalizowalna gdy jest podobna do macierzy diagonalnej, czyli gdy istnieje nieosobliwa taka, że
Zauważmy, że wtedy możemy równoważnie zapisać , albo dla . Stąd elementy diagonalne macierzy są wartościami własnymi macierzy (gdzie ta sama wartość własna powtarza się tyle razy ile wynosi jej krotność), a kolumny macierzy są odpowiednimi wektorami własnymi.
Szczególne własności mają macierze hermitowskie albo, w przypadku rzeczywistym, macierze symetryczne, bowiem dla nich istnieją bazy ortonormalne (odpowiednio w lub ) wektorów własnych. Odpowiednie twierdzenie przypominamy jedynie w przypadku rzeczywistym, który ma zasadnicze znaczenie w obliczeniach praktycznych.
Niech będzie macierzą symetryczną o współczynnikach rzeczywistych,
Wtedy istnieje w baza ortonormalna wektorów własnych macierzy , tzn. istnieje układ wektorów własnych taki, że
Oczywiście, odpowiednie wartości własne , , są też rzeczywiste.
Powyższa własność macierzy symetrycznych oznacza tyle, że są one diagonalizowalne przy pomocy macierzy ortogonalnych. Rzeczywiście, oznaczając
mamy oraz
Zobaczmy najpierw, czy mamy w ogóle szansę numerycznego rozwiązania zadania znalezienia wartości własnych macierzy. W tym celu zbadamy jego uwarunkowanie, czyli wrażliwość na małe względne zaburzenia współczynników macierzy.
W ogólności, uwarunkowanie naszego zadania może być niestety dowolnie duże.
Niech macierz
Dla , macierz jest pojedynczą klatką Jordana, której jedyną wartością własną jest (o krotności algebraicznej i krotności geometrycznej ). Jeśli teraz zaburzymy wyraz w lewym dolnym rogu o to otrzymana macierz ma już różnych wartości własnych. Rzeczywiście, jej wielomian charakterystyczny
ma pierwiastki
Względne zaburzenie macierzy na poziomie powoduje więc względne zaburzenie wartości własnych na poziomie . Stąd, dla , uwarunkowanie rośnie do gdy .
Oczywiście, otrzymane oszacowanie nie oznacza, że w powyższym przykładzie w ogóle nie potrafimy aproksymować wartości własnej. Tracimy jednak na liczbie poprawnie obliczonych cyfr znaczących wyniku. Niech . Wtedy przy dokładności arytmetyki możemy spodziewać się jedynie wyniku z dokładnością do czterech cyfr znaczących, a przy dokładności z dokładnością do ośmiu cyfr znaczących. Co więcej, im większy format klatki Jordana tym gorzej.
Powyższy przykład pokazuje również, że praktycznie niemożliwe jest numeryczne wyznaczenie struktury macierzy. Nawet drobne zaburzenie macierzy powoduje bowiem, że pojedyncza klatka Jordana staje się macierzą diagonalizowalną.
Dalej będziemy już zakładać, że macierz jest diagonalizowalna, czyli że jej postać Jordana jest macierzą diagonalną. Wtedy mamy następujące oszacowanie Bauera-Fike'a.
Niech będzie macierzą diagonalizowalną o wartościach własnych , ,
Niech dalej będzie dowolną wartością własną macierzy `sąsiedniej' . Wtedy
gdzie oraz jest normą macierzy indukowaną przez dowolną normę -tą wektora.
Załóżmy bez zmniejszenia ogólności, że jest różne od każdej wartości własnej . Niech będzie wektorem własnym odpowiadającym wartości własnej macierzy . Wtedy
(1.1) |
Oznaczając mamy dalej
(1.2) |
czyli
Ponieważ to ostatecznie
Dla macierzy diagonalizowalnych zaburzenia wartości własnych są więc lipschitzowską funkcją zaburzeń macierzy, przy czym stała Lipschitza wynosi .
Podane oszacowanie jest globalne dla wszystkich wartości własnych. Zaburzenia macierzy mogą jednak w różny sposób przenosić się na zaburzenia różnych wartości własnych. Od czego to zależy? Tak jak w dowodzie twierdzenia Bauera-Fike'a, niech
Biorąc jedynie -tą współrzędną po obu stronach równania (1.2) dostajemy
(1.3) |
gdzie jest znormalizowaną -tą kolumną macierzy
tzn. . W szczególności, oraz
(ortogonalność ze względu na zwykły iloczyn skalarny). Stąd, jeśli i nie są ortogonalne to
Dla ustalenia uwagi załóżmy teraz, że minimum w twierdzeniu 1.2 jest osiągane dla , a podprzestrzenią własną wartości własnej jest
gdzie wektory własne tworzą bazę ortonormalną w . Jeśli wektor jest `dostatecznie blisko' podprzestrzeni własnej (co, jak pokażemy w następnym podrozdziale, jest prawdą dla dostatecznie małego zaburzenia ) to można w przybliżeniu oszacować z góry przez maksymalną wartość wyrażenia
po wszystkich takich, że . Niech więc , przy czym . Wobec tego, że dla każdego mamy
interesujące nas `max' jest najmniejsze gdy . Stąd dostajemy
Ponieważ oraz jest ortogonalny do , otrzymana nierówność sugeruje, że wartość własna może być bardzo wrażliwa na zaburzenia macierzy gdy odpowiadająca jej podprzestrzeń własna jest `prawie ortogonalna' do . Dobrze ilustruje to następujący przykład.
Rozpatrzmy macierz
gdzie jest `małe'. Wartości własne wynoszą i , natomiast wektory własne i są prawie liniowo zależne. Zaburzając macierz przez dodanie do wyrazu w lewym dolnym rogu dostajemy macierz o wartościach własnych i , a odpowiadające im wektory własne wynoszą i . Dodajmy, że w tym przypadku jest proporcjonalne do .
Przez zaburzenie wektora własnego będziemy rozumieć odległość wektora od podprzestrzeni własnej , tzn.
albo, równoważnie, długość rzutu ortogonalnego wektora na podprzestrzeń
Pokażemy, że podobnie jak przypadku wartości własnych, zaburzenie wektorów własnych jest lipszitzowską funkcją . W tym celu, wybierzmy w dowolną bazę ortonormalną
Niech będzie macierzą przejścia z bazy do ,
Wtedy
Wobec równości (1.3) mamy
Ponieważ na podstawie twierdzenia Bauera-Fike'a mamy
otrzymujemy następującą przybliżoną nierówność
(1.4) |
Uwaga. W przykładzie 1.2 istotnemu zaburzeniu uległy wartości własne, natomiast wektory własne nie. Jest to zrozumiałe w świetle ostatniego wyniku. W przypadku macierzy mamy bowiem i w konsekwencji wrażliwość wektorów własnych zależy tylko od różnicy .
Poniższy przykład dla macierzy symetrycznej (!) pokazuje jak ważne dla wrażliwości wektorów własnych jest odseparowanie różnych wartości własnych.
Wartościami własnymi macierzy symetrycznej
są i , a odpowiadająca baza wektorów własnych to i . Dla macierzy zaburzonej na poziomie (czyli różnicy wartości własnych),
wartościami własnymi są i , a bazę wektorów własnych tworzą i . Baza wektorów własnych została obrócona o możliwie maksymalny kąt .
W tej części będziemy zakładać, że macierz jest rzeczywista i symetryczna,
Ponieważ elementy i macierzy są w praktycznych obliczeniach reprezentowane przez tą samą zmienną, zasadne jest założenie, że macierz zaburzona jest również symetryczna, .
Przypomnijmy twierdzenie 1.1, które mówi, że dla macierzy symetrycznej istnieje baza ortonormalna jej wektorów własnych. Ponieważ dla macierzy ortogonanych mamy ,
To zaś, razem z twierdzeniem 1.2 implikuje, że każda watość własna macierzy sąsiedniej spełnia nierówność
Możemy jednak pokazać dużo więcej. Zachodzi bowiem następujące twierdzenie Weyla.
Niech będą wartościami własnymi macierzy , a wartościami własnymi macierzy sąsiedniej , gdzie . Wtedy dla wszystkich mamy
Dowód twierdzenia opiera się na następującej pożytecznej nierówności.
Dla dowolnej rzeczywistej macierzy symetrycznej mamy
(1.5) |
przy czym odpowiednie maksimum i minimum osiągane są dla oraz .
Niech i będą dowolnymi podprzestrzeniami o wskazanych wymiarach. Ponieważ suma wymiarów wynosi to istnieje wektor niezerowy . W konsekwencji
Biorąc maximum po i minimum po dostajemy, że w (1.5) lewa strona nie jest większa od prawej. Aby pokazać odwrotną nierówność, zauważmy, że dla i mamy odpowiednio
Dla dowodu twierdzenia 1.3 zastosujemy lemat 1.5 najpierw do macierzy , a potem do macierzy . Otrzymujemy odpowiednio
oraz podobnie nierówność odwrotną , czyli ostatecznie
Zanotujmy jeszcze, że wielkość
znana jest pod nazwą ilorazu Rayleigh'a.
Niech będzie podprzestrzenią własną odpowiadającą wartości własnej macierzy , a wektorem własnym odpowiadającym wartości własnej macierzy sąsiedniej . Niech dalej będzie kątem pomiędzy i podprzestrzenią . Wtedy
Rzeczywiście, to wynika bezpośrednio z twierdzenia 1.3, nierówności (1.4) oraz faktu, że macierz w (1.4) jest identycznością. Pokażemy teraz nierówność dokładną.
Dla ustalenia uwagi załóżmy, że oraz odpowiednia podprzestrzeń własna . Przedstawmy wektor własny , , w jednoznaczny sposób w postaci
gdzie i ,
Możemy też założyć, bez straty ogólności, że i , tzn. .
Przekształcając równanie dostajemy
Ponieważ każdy z wektorów dla należy do jądra macierzy symetrycznej to wektor jest ortogonalny do i tym samym możemy zapisać
Mamy dalej
a stąd i
Z kolei z równości dostajemy
skąd
Gdybyśmy teraz wiedzieli, że
(1.6) |
to moglibyśmy napisać
i ostatecznie
Pozostaje więc do pokazania równość (1.6). W tym celu, weźmy , gdzie , i . Wtedy
Dla danych i , wektor po prawej stronie ma największą normę gdy , przy czym bierzemy plus wtedy i tylko wtedy gdy i mają różne znaki. Dlatego poszukiwana norma wynosi
Zamieniając zmienne na , łatwo dostajemy, że optymalne spełnia , , a stąd dostajemy wynik
Pokazaliśmy, że wektory własne są mało wrażliwe na zaburzenia macierzy o ile wartości własne są odseparowane od siebie na poziomie dużo większym niż . W szczególności, jeśli dodatkowo , , to mamy jednolite oszacowanie
Przypomnijmy jeszcze przykład 1.3 pokazujący, że warunek odseparowania wartości własnych jest konieczny.
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.