Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 9
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
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 9
Wyznaczanie wartości własnych z równania charakterystycznego
Metoda Kryłowa wyznaczania współczynników wielomianu
charakterystycznego
Z tw. Calley 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
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 9
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
ìÅ‚a1 m
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"
s1 yT Amv0 m" yTvm
yT może mieć zera poza jedynką w miejscu odpowiadającym
elementowi vm o największym module.
W9-3
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 9
Konieczna redukcja: np. A1 = A - s1x1zT , zT x1 = 1 ma wartości
własne jak A poza s1, w miejscu której jest zero.
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-4
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 9
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-5
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 9
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-6
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 9
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-7