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.