Obliczanie wektorów i wartości własnych
Równanie charakterystyczne det( A - sI ) = 0
sn + bn-1sn-1 + L+ b1s + b0 = 0
Różne wartości własne s1 ,L,sn
n liniowo niezależnych prawych wektorów własnych
xi `" 0, Axi = si xi
T
yT Axi
xi Axi
si = , yT xi `" 0 w szczególności si =
T
yT xi xi xi
Przekształcenie przez podobieństwo:
-1
det P `" 0, A P AP, si si, xi Pxi
W9-1
Wyznaczanie wartości własnych z równania charakterystycznego
Metoda Kryłowa wyznaczania współczynników wielomianu
charakterystycznego
Z tw. Cayley a-Hamiltona
An + bn-1An-1 + L+ b1A + b0I = 0 " y
bn-1
Ą# ń#
ó# Ą#
M
ó# Ą#
[An-1 yMAn-2 yMLMAyM y]ó# b1 Ą# == - An y
ó#
b0 Ą#
Ł# Ś#
W9-2
Metoda potęgowa
n
Dla dowolnego v0 istnieją ai takie , że v0 =
"a xi. Wtedy
i
i =1
n n
Av0 =
"a Axi = "a si xi
i i
i =1 i =1
n n
# ś#
m
ź#
vm = Amv0 = xi ź#
"a sim xi = s1 ś# x1 + "a sim
i i
m
ś#a1
s1
i =1 i =2
# #
Jeśli A ma n liniowo niezal. wektorów własnych, jeśli wartość
własna s1 jest dominującą i jeśli v0 nie jest ortogonalny do x1 , to
Amv0
yT AAmv0 yTvm +1
lim = a1 x1, czyli s1 = lim = lim
m
m" m" m"
yT Amv0 yTvm
s1
yT może mieć zera poza jedynką w miejscu odpowiadającym
elementowi vm o największym module.
W9-3
Konieczna redukcja: np. A1 = A - s1x1zT , zT x1 = 1 ma wartości
własne jak A poza s1, w miejscu której jest zero.
Odwrotna metoda potęgowa:
Przypuśćmy, że dysponujemy dobrym przybliżeniem wartości
własnej si , takim że "j `" i - si < - sj . Wtedy ( - si)-1 jest
dominującą wartością własną macierzy (I - A)-1, stosujemy więc
metodę potęgową do niej:
vm=(I - A)-1vm-1 (I - A) vm=vm-1
W każdej iteracji musimy rozwiązać układ równań liniowych, ale
macierz współczynników prawej strony jest zawsze ta sama i równa
I A , wystarczy więc tylko raz przeprowadzić jej faktoryzację.
W9-4
Metody iteracyjne oparte na przekształceniach przez podobieństwo.
Nie istnieje algorytm sprowadzający macierz w skończonej liczbie
operacji do postaci diagonalnej (Jordana). Istnieją algorytmy
sprowadzające w skończonej liczbie operacji macierz symetryczną
do postaci trójprzekątniowej a macierz niesymetryczna do postaci
prawie-trójkątnej górnej.
Jeżeli macierz przekształcenia przez podobieństwo jest ortogonalna,
to przekształcenie to nie zmienia uwarunkowania wartości własnych
od wsp. macierzy.
T T
Równanie jednej iteracji: Ak +1 = Qk AkQk , Qk Qk = I .
W9-5
Metody dla macierzy symetrycznych np. metoda Jacobiego:
Przekształcenie (obrót) sparametryzowane wartością , Ć d" Ą ,
określone macierzą Rp ,q ( ), która ma elementy macierzy
jednostkowej poza rp , p = rq ,q = cos , rp ,q = -rq , p = sin .
Wtedy Rp ,q( - ) = ( Rp ,q( ))T = ( Rp ,q( ))-1
W macierzy Ak wybieramy element a( k ). Chcemy by a( k +1 ) = 0.
p ,q p ,q
Ak+1 = Rp,q(- )Ak Rp,q( ),
(
a(k ) - aqk )
p, p ,q
a(k+1) = 0 ! ctg(2 ) =
p,q
2a(k )
p,q
t = tg jest pierwiastkiem o mniejszym module równania
t2 + 2t ctg(2 ) = 1
Stąd wyznaczamy sin, cos .
W9-6
Sposoby wyboru zerowanych elementów
p,q- element o najw. module,
lub
(p,q)=(1,2),(1,3),...(1,n),(2,3),...,(2,n),....(n-1,n)
2
2 (
Jeżeli T ( Ak ) := (ai ,k )) , to po jednym wymiataniu , w
"" j
i j`"i
1
2 2
którym wykonano N = n( n - 1 ) obrotów T ( Ak + N ) d" C(T ( Ak )2).
2
Korzystne wcześniejsze sprowadzenie do postaci trójprzekątniowej.
W9-7
Metoda przekształcenia QR.
Dla macierzy rzeczywistej A istnieje ortogonalna Q i trójkątna
górna R , że A=QR.
Algorytm wyznaczania rozkładu QR wymaga skończonej liczby
operacji.
W i-tej iteracji metody QR:
- wyznaczamy rozkład QR macierzy Ai, Ai = Qi Ri,
- obliczamy Ai +1 = RiQi
Wtedy Ai +1 = RiQi = QiTQi RiQi = QiT AiQi, czyli dokonaliśmy
przekształcenia przez podobieństwo z ortogonalną macierzą
przekształcenia.
Ai dąży do macierzy trójkątnej górnej z wartościami własnymi na
przekątnej.
W9-8
Wyszukiwarka
Podobne podstrony:
metody numeryczne i w9Metody numeryczne w9Metody numeryczne w11metody numeryczne i w1metody numeryczne i w2barcz,metody numeryczne, opracowanie wykładuMetody numeryczne7metody numeryczne w1metody numeryczne cw 1Metody numeryczne macierzeMetody numeryczne aproksymacja3 Metody numeryczne rozwiązywania równań algebraicznychMetody numeryczne w6METODY NUMERYCZNE CZESC PIERWSZAMetody numeryczne2metody numeryczne dla informatykowwięcej podobnych podstron