Czesc!
Zajmuje sie duzymi ukladami rownan liniowych, ktore sa zle uwarunkowane
oraz przedeterminowane. Potrzebuje narzedzia do obliczania wartosci wlasnych
i wektorow wlasnych macierzy wspolczynnikow ukladu. Rozmiary macierzy
wspolczynnikow ukladu sa co najmniej
(72 X 58) i moga dochodzic do rozmiaru (kilka tysiecy X kilka tysiecy). Czy
istnieje jakies narzedzie do takich obliczen? Jakie sa ograniczenia
narzedzi, ktore licza wektory i wartosci wlasne?
Pozdrowienia
Pawel Zych
Czesc!
Zajmuje sie duzymi ukladami rownan liniowych, ktore sa zle uwarunkowane
oraz przedeterminowane. Potrzebuje narzedzia do obliczania wartosci wlasnych
i wektorow wlasnych macierzy wspolczynnikow ukladu.
Sprawdzilbym SAL i NAG. IMHO Linux bedzie mial mniejsze ograniczenia
- duze macierze, ew. mozna bedzie puscic program docelowo na jakims
powazniejszym sprzecie.
Matlab jest oki tylko ma duza wade czas oczekiwania na wyniki jest b.duzy
W MATLABIE można przekompilować skrypt i skrócić czas z 10x
Pozdrawiam Najman
Wiadomośc zła: Pojęcia wektorów i wartości własnych są zdefiniowane
tylko dla macierzy kwadratowych, zatem NIE DA SIĘ policzyć wektorów
i wartości własnych macierzy układu nadokreślonego (domyślam się,
że "przedeterminowany" wzięło się z "overdetermined", a to się po
polsku tłumaczy "nadokreślony" właśnie). Ten smutny fakt wynika po
prostu z tego, że jak masz macierz WxK, to możesz przez nią mnożyć
kolumnowe wektory K wymiarowe i dostajesz kolumnowe wektory
W wymiarowe, a skoro tak, to równość definiująca wartości i wektory
własne (A to twoje macierz)
A x = lambda x
nigdy nie jest spełniona (jeszcze ściślej: po prostu nie ma sensu),
bo po lewej i prawej masz wektory o różnej długości. Sorry, Winnetou.
Wiadomość dobra: Skoro rozwiązujesz nadokreślone i źle uwarunkowane
układy równań, jest metoda, która być może rozwiązuje twój problem,
a której na pewno powinieneś spróbować, a mianowicie Singular Value
Decomposition (SVD, brak "oficjalnej" nazwy polskiej, powiedzmy więc
"rozkład wedle wartości osobliwych"). SVD da ci po pierwsze
identyfikację "kierunków" (cudzysłów świadomie, bez cudzysłowu byłoby
dla macierzy kwadratowych), które powodują największe zaburzenia
numeryczne (dla macierzy kwadratowych odpowiadałyby one
wartościom własnym bliskim zeru), po drugie możliwość systematycznego
wyeliminowania tych "kierunków", po trzecie możliwość przybliżonego
(w sensie najmniejszych kwadratów) rozwiązywania nadokreślonych
układów równań (także w połączeniu z pierwszym i drugim). Jeśli
nie wiesz, co to jest SVD, wystarczy jeśli przeczytasz opis
w Numerical Recipes (wersja on-line pod http://www.nr.com),
natomiast procedur poszukaj albo w Netlibie (http://www.netlib.org),
albo zrób net search z hasłem SVD.
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.
Pojęcia wektorów i wartości własnych są zdefiniowane
tylko dla macierzy kwadratowych, zatem NIE DA SIĘ policzyć wektorów
i wartości własnych macierzy układu nadokreślonego
Rzeczywiście, w przypadku macierzy (w X k) zwykły problem wartości własnych
traci swoje znaczenie.
Nie rozważam układu liniowego z taką macierzą w separacji, ale powiększam go
o układ A`x=c (A` jest transpozycją A rozmiaru(k X w))
i łączę oba układy w jeden duży: S * z = a
| 0 A |
S = : | A` 0 |
z` = : [x,y]
a` =: [b,c]
Teraz podstawowe równanie wartości własnych wygląda tak: S * w = lambda * w,
a jeśli położę w` = [u, v] wtedy:
A * v = lambda * u (1)
A` * u = lambda * v (2)
Tym razem mam parę równań zamiast jednego (ang. shifted eigenvalue problem -
problem wartości własnych z przesunięciem?- czy tak to będzie po polsku?).
Tym razem nie przeszkadza mi heterogeniczność przestrzeni do których należą
wektory v (z
przestrzeni K) i u (z przestrzeni W).
Problem wartości własnych postawiony w ten sposób jest zawsze ważny i
całkowicie rozwiązywalny, bo jest tylko sformułowaniem zwykłego problemu
wartości własnych z macierzą symetryczną. Powinienem uzyskać k + w wektorów
własnych (wzajemnie ortogonalnych), które należa do k + w niezaleznych
wartości własnych (niekoniecznie różnych).
Wektory u_i tak samo jak v_i mogą zostać sformułowane nizależnie - pierwsze
równanie mnożę lewostronnie przez A`, drugie przez A:
A` * A * v = lambda ^2 * v (3)
A * A` *u = lamda^2 * u (4)
Uzyskuję z (3) k wzajemnie ortogonalnych wektorów v_i i z (4) w wzajemnie
ortogonalnych wektorów u_j. Wektory mogą służyć jako zbiór wektorów bazowych
rozpinających przestrzenie K i odpowiednio W. Po ułożeniu tych wektorów
bazowych w kolumnach uzyskuję dwie macierze kwadratowe: U złożoną z w
wektorów u_1, u_2, ... , u_w i macierz V złożoną z v_1, v_2, ... , v_k.
W zapisie równań macierzowych (1) i (2) wyglądają tak:
A * V = U * L (5)
A` * U = V * L` (6), dla każdego lambda <0,
L to macierz diagonalna (przekątniowa ?) z wartościami własnymi na
przekątnej (przekątni?, diagonali ?)
A * v_i = 0
A` * u_j = 0, dla zerowej wartości własnej.
Pomnożę teraz prawostronnie równanie (5) przez V` (V` jest ortogonalna i
spełnia warunki ortogonalności: V` * V = V * V` = I, I macierz jednostkowa)
i napiszę podstawowe twierdzenie o dekompozycji (rozkładzie) macierzy:
A = U * L * V` (7)
U ma wymiar (w X w), A (w X k), V` (k X k), zaś L (w X k).
Jeśli poukładam wartości własne na przekątnej L tak, że zerowe wartości
własne napiszę na końcu tej przekątnej to z mnożenia (7) wyniknie
następująca postać rozkładu:
A = U_p * L_p * V`_p, gdzie p - rząd macierzy A.
Mogę teraz zdefiniować B =: V * L^(-1) * U`, B - naturalna odwrotność A
i rozwiązać początkowy układ ( A * y = b) jako: y = B * b. Rozwiązanie to
jest zbieżne (dla układów nadokreślonych ale nie w przypadku gdy y ma jakąś
projekcję w V_0, czyli gdy układ jest niekompletny) z rozwiązaniem
minimalnokwadratowym:
A` * A * y = A` * b
Nie jest jednak moim celem rozwiązywanie takich układów za pomocą
uciążliwego badania wektorów i wartości własnych. Chcę jednak sprawdzić,
stosując (7) i rozważając indywidualne równania:
lambda_i * v`_i * y = u`_i * b, i = 1, ... ,k
jak macierz A oddziałuje na poszczególne komponenty spektralne rozwiązania
(poprzez analogię do filtrów liniowych).
Czyli innymi słowy, które z niewiadomych da się określić, a które są "poza
zasiegiem".
Jeżeli chciałbyć mi pomóc, to miałbym jeszcze kilka pytań. Czekam na
odpowiedź.
P.S.
Jak przetłumaczyć: "shifted eigenvalue problem"?
Paweł Zych
niezrzeszony
Pojęcia wektorów i wartości własnych są zdefiniowane
tylko dla macierzy kwadratowych, zatem NIE DA SIĘ policzyć wektorów
i wartości własnych macierzy układu nadokreślonego
Rzeczywiście, w przypadku macierzy (w X k) zwykły problem wartości własnych
traci swoje znaczenie.
Nie rozważam układu liniowego z taką macierzą w separacji, ale powiększam go
o układ A`x=c (A` jest transpozycją A rozmiaru(k X w))
i łączę oba układy w jeden duży: S * z = a
| 0 A |
S = : | A` 0 |
z` = : [x,y]
a` =: [b,c]
Teraz podstawowe równanie wartości własnych wygląda tak: S * w = lambda * w,
a jeśli położę w` = [u, v] wtedy:
A * v = lambda * u (1)
A` * u = lambda * v (2)
Tym razem mam parę równań zamiast jednego (ang. shifted eigenvalue problem -
problem wartości własnych z przesunięciem?- czy tak to będzie po polsku?).
Tym razem nie przeszkadza mi heterogeniczność przestrzeni do których należą
wektory v (z
przestrzeni K) i u (z przestrzeni W).
Problem wartości własnych postawiony w ten sposób jest zawsze ważny i
całkowicie rozwiązywalny, bo jest tylko sformułowaniem zwykłego problemu
wartości własnych z macierzą symetryczną. Powinienem uzyskać k + w wektorów
własnych (wzajemnie ortogonalnych), które należa do k + w niezaleznych
wartości własnych (niekoniecznie różnych).
Wektory u_i tak samo jak v_i mogą zostać sformułowane nizależnie - pierwsze
równanie mnożę lewostronnie przez A`, drugie przez A:
A` * A * v = lambda ^2 * v (3)
A * A` *u = lamda^2 * u (4)
Uzyskuję z (3) k wzajemnie ortogonalnych wektorów v_i i z (4) w wzajemnie
ortogonalnych wektorów u_j. Wektory mogą służyć jako zbiór wektorów bazowych
rozpinających przestrzenie K i odpowiednio W. Po ułożeniu tych wektorów
bazowych w kolumnach uzyskuję dwie macierze kwadratowe: U złożoną z w
wektorów u_1, u_2, ... , u_w i macierz V złożoną z v_1, v_2, ... , v_k.
W zapisie równań macierzowych (1) i (2) wyglądają tak:
A * V = U * L (5)
A` * U = V * L` (6), dla każdego lambda <0,
L to macierz diagonalna (przekątniowa ?) z wartościami własnymi na
przekątnej (przekątni?, diagonali ?)
A * v_i = 0
A` * u_j = 0, dla zerowej wartości własnej.
Pomnożę teraz prawostronnie równanie (5) przez V` (V` jest ortogonalna i
spełnia warunki ortogonalności: V` * V = V * V` = I, I macierz jednostkowa)
i napiszę podstawowe twierdzenie o dekompozycji (rozkładzie) macierzy:
A = U * L * V` (7)
U ma wymiar (w X w), A (w X k), V` (k X k), zaś L (w X k).
Jeśli poukładam wartości własne na przekątnej L tak, że zerowe wartości
własne napiszę na końcu tej przekątnej to z mnożenia (7) wyniknie
następująca postać rozkładu:
A = U_p * L_p * V`_p, gdzie p - rząd macierzy A.
Mogę teraz zdefiniować B =: V * L^(-1) * U`, B - naturalna odwrotność A
i rozwiązać początkowy układ ( A * y = b) jako: y = B * b. Rozwiązanie to
jest zbieżne (dla układów nadokreślonych ale nie w przypadku gdy y ma jakąś
projekcję w V_0, czyli gdy układ jest niekompletny) z rozwiązaniem
minimalnokwadratowym:
A` * A * y = A` * b
Nie jest jednak moim celem rozwiązywanie takich układów za pomocą
uciążliwego badania wektorów i wartości własnych. Chcę jednak sprawdzić,
stosując (7) i rozważając indywidualne równania:
lambda_i * v`_i * y = u`_i * b, i = 1, ... ,k
jak macierz A oddziałuje na poszczególne komponenty spektralne rozwiązania
(poprzez analogię do filtrów liniowych).
Czyli innymi słowy, które z niewiadomych da się określić, a które są "poza
zasiegiem".
Jeżeli chciałbyć mi pomóc, to miałbym jeszcze kilka pytań. Czekam na
odpowiedź.
P.S.
Jak przetłumaczyć: "shifted eigenvalue problem"?
Paweł Zych
niezrzeszony
[...]
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.