promien spekralny macierzy
Artur Michalowski
Czy mozecie powiedziec, w jaki sposob mozna obliczyc promien spektralny
macierzy? Jak to sie robi w praktyce (tj. "recznie") a jak na komputerze
(metoda numeryczna)? Zwracam sie do was o pomoc, bo przejrzalem kilka
ksiazek, ale nic nie znalazlem :((
Pozdrawiam
PS odpowiedz prosilbym wyslac takze na priva
Andrzej Lewandowski
Artur Michalowski <artm...@priv3.onet.pl> wrote in message
news:3928E2E5...@priv3.onet.pl...
> witam wszystkich grupowiczow!
> Czy mozecie powiedziec, w jaki sposob mozna obliczyc promien spektralny
> macierzy? Jak to sie robi w praktyce (tj. "recznie") a jak na komputerze
> (metoda numeryczna)? Zwracam sie do was o pomoc, bo przejrzalem kilka
> ksiazek, ale nic nie znalazlem :((
Trzeba policzyc wartosc wlasna o najwiekszym module. Sa do tego metody
iteracyjne, mozna znalezc w dowolnej ksiazce o metodach numerycznych.
"Recznie" czasem stosuje sie roznego rodzaju oszacowania, np. twierdzenie
Gerszgorina. Na temat szacowania zobacz Turowicz, "Geometria zer wielomianow",
albo Gantmachera ("Tieria matric", po rusku).
O wartosciach wlasnych i metodach mumerycznych zobacz np. Ralston.
A.L.
Andrzej Błażewicz
Artur Michalowski napisal:
> witam wszystkich grupowiczow!
> Czy mozecie powiedziec, w jaki sposob mozna obliczyc promien spektralny
> macierzy? Jak to sie robi w praktyce (tj. "recznie") a jak na komputerze
> (metoda numeryczna)? Zwracam sie do was o pomoc, bo przejrzalem kilka
> ksiazek, ale nic nie znalazlem :((
> Pozdrawiam
> PS odpowiedz prosilbym wyslac takze na priva
>
>
Promien spektralny macierzy jest to maksimum jego wartosci wlasnych. Czyli
nalezy rozwiazac rownanie
det(A - \lambda) = 0
a nastepnie wyznaczyc najwieksza wartosc sposrod otrzymanych. Tak to sie
wlasnie robi recznie. A numerycznie np. poszukaj w jakiejs ksiazce z metod
numerycznych Algorytm Krylowa.
Pozdrawiam.
Andrzej Blazewicz.
--
Archiwum listy dyskusyjnej pl-sci-matematyka
http://www.newsgate.pl/archiwum/pl-sci-matematyka/
Pawel F. Gora
> Czy mozecie powiedziec, w jaki sposob mozna obliczyc promien spektralny
> macierzy? Jak to sie robi w praktyce (tj. "recznie") a jak na komputerze
> (metoda numeryczna)?
"W praktyce" oznacza "na komputerze", "ręcznie" oznacza "licząc
prosty przykład na ćwiczenia".
Biorę macierz A, liczę jej wartości własne l1, l2, ..., ln,
liczę ich moduły i promieniem spektralnym nazywam
max{|l1|, |l2|, ... , |ln|}. (_Moduły_ są istotne, bo
wartości własne mogą wyjść, a to ujemne, a to zespolone.)
Jeśli A jest mała (do kilkaset na kilkaset), to właściwie
mogę wziąć dowolny pakiet liczący wartości własne
(do ściągnięcia na przykład z netlibu http://www.netlib.org),
policzyć je i wybrać tę o największym module. Jeśli
nie zachodzi przypadek patologiczny (patrz niżej) i A jest
symetryczna, mogę też użyc nastepującej metody iteracyjnej
(wspomnianej tu metody Kryłowa):
0. Biorę losowy wektor i normuję go do jedności. Tak
otrzymany wektor nazywam x_0.
1. W k-tym kroku iteracji liczę
y_{k+1} = A x_k
x_{k+1} = y_{k+1}/||y_{k+1}||
Poza przypadkami patologicznymi (patrz niżej :-) taka
iteracja jest dość szybko zbieżna do y_{k+1} = +/- w x_{k},
a zatem x_{k} jest wektorem własnym A, w jest promieniem
spektralnym A, +/- w jest wartością własną.
Oczywiście po osiagnięciu zbieżności w = ||y_{k+1}||,
więc ustabilizowanie się tego ciągu norm można przyjąć
za praktyczne kryterium zbiezności.
(Formalnie można to uogólnić na przypadek A niesymetrycznego,
dopuszczający zespolone wartości własne, ale wówczas mogą
być problemy ze zbieżnością.) Dowód tego faktu zostawiam
jako proste ćwiczenie (wskazówka: rozłozyć x_0
w bazie wektorów własnych A).
Przypadki patologiczne: Procedura nie zbiegnie się,
jeśli
a) wektor x_0 został przypadkiem wybrany źle (tak, że
jego rzut na kierunek odpowiadający wartości własnej o największym
module jest bliski zeru). Wówczas procedura _może_ się zbiec,
ale nie do promienia spektralnego! Stąd wniosek praktyczny:
Trzeba procedurę powtarzać dla kilku niezaleznych wyborów wektora
początkowego - gdy za każdym razem dostaniemy to samo, to
pewnie mamy dobry wynik.
b) Największa na moduł wartość własna jest zdegenerowana
(istnieje kilka niezależnych liniowo wektorów odpowiadających
tej wartości własnej) lub "zdegenerowana na moduł" (promieniowi
spektralnemu odpowiada kilka różnych wartości własnych o tym
samym module, np +1 oraz -1). Wówczas procedura nie zbiega się
- układ szybko wpada do pewnej podprzestrzeni, ale w tej
podprzestrzeni nie ma żadnej zbieżności.
c) Wartość własna odpowiadająca promieniowi spektralnemu
co prawda nie jest zdegenerowana, ale istnieją inne wartości
własne bliskie tej o największym module - przykład:
wartościami własnymi są 1.000000 oraz 0.999999. Wówczas
w teorii zbieznośc jest, ale w praktyce (w prawdziwych
obliczeniach na prawdziwym komputerze) może być bardzo
wolna lub też - na skutek błędów zaokraglenia - procedura
może nie być zbieżna.
Jeśli A jest macierzą symetryczną, rzeczywistą (ogólniej:
hermitowską) i zachodzi b) lub c), to co prawda ciąg wektorów
x_k nie jest zbieżny, ale ciąg norm ||y_{k+1}|| może mimo
wszystko być zbieżny do promienia spektalnego. Zatem
praktyczna implementacja wygląda powinna wyglądać tak:
Losuję x_0, przeprowadzam iteracje aż do ustabilizowania się
ciągu norm. Jeśli osiagne zbiezność, losuję inne x_0
i powtarzam. Jeśli po kilku takich powtórzeniach ciągi norm
zbiegną się do tego samego, uznaję, ze zbiegły się do
promienia spektralnego. Jeśli nie uzyskam zbieżności
(w ciągu ustalonej liczby kroków ciag norm się nie ustabilizuje)
konstatuje, że metoda ta dla mojej macierzy zawodzi, co nie
jest sytuacją rzadką.
Jeśli natomiast macierz A jest duża, muszę użyć którejś
ze specjalistycznych metod diagonalizacji dużych macierzy
(lanczosa lub Davidsona). Oczywiscie w metodach tych nie liczy
się _wszystkich_ wartości własnych, ale na szczęście
wartości własne o największych modułach pojawiaja się jako
pierwsze. Jednak w wypadku degeneracji/słabego rozdzielenia
widma też mogą wystąpic problemy ze zbieznością.
> PS odpowiedz prosilbym wyslac takze na priva
To jest, wyjaśniam, bardzo nietaktowna prośba - znaczy
bowiem ona tyle: "Wy macie mieć czas żeby rozwiązać mój
problem, ale mnie nawet nie będzie się chciało sprawdzać
czy rozwiązanie się pojawiło".
Paweł Góra
Institute of Physics, Jagellonian University, Cracow, Poland
A physical entity does not do what it does because it is what it is,
but is what it is because it does what it does.