Obliczanie wektorów i wartości własnych
−
)
sI
A
det(
Równanie charakterystyczne
0
=
0
0
1
1
1
=
+
+
+
+
−
−
b
s
b
s
b
s
n
n
n
L
Różne wartości własne
n
s
,
,
s L
1
n liniowo niezależnych prawych wektorów własnych
i
i
i
i
x
s
Ax
,
x
=
≠ 0
0
≠
=
i
T
i
T
i
T
i
x
y
,
x
y
Ax
y
s
w szczególności
i
T
i
i
T
i
i
x
x
Ax
x
s
=
Przekształcenie przez podobieństwo:
0
≠
P
det
AP
P
A
1
−
→
,
,
i
i
s
s
→
i
i
Px
x
→
,
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
y
I
b
A
b
A
b
A
n
n
n
⋅
=
+
+
+
+
−
−
0
0
1
1
1
L
[
]
y
A
b
b
b
y
Ay
y
A
y
A
n
n
n
n
−
==
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
−
−
−
0
1
1
2
1
M
M
M
L
M
M
W9-2
Metoda potęgowa
Dla dowolnego istnieją takie , że
. Wtedy
0
v
i
a
i
n
i
i
x
a
v
∑
=
=
1
0
i
i
n
i
i
i
n
i
i
x
s
a
Ax
a
Av
∑
∑
=
=
=
=
1
1
0
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
+
=
=
=
∑
∑
=
=
i
m
m
i
n
i
i
m
i
m
i
n
i
i
m
m
x
s
s
a
x
a
s
x
s
a
v
A
v
1
2
1
1
1
1
0
Jeśli A ma n liniowo niezal. wektorów własnych, jeśli wartość
własna s
1
jest dominującą i jeśli v
0
nie jest ortogonalny do x
1
, to
1
1
1
0
x
a
s
v
A
lim
m
m
m
=
∞
→
, czyli
m
T
m
T
m
m
T
m
T
m
v
y
v
y
lim
v
A
y
v
AA
y
lim
s
1
0
0
1
+
∞
→
∞
→
=
=
T
y
może mieć zera poza jedynką w miejscu odpowiadającym
elementowi
o największym module.
m
v
W9-3
Konieczna redukcja: np.
1
1
1
1
1
=
−
=
x
z
,
z
x
s
A
A
T
T
ma wartości
własne jak A poza s
1
, w miejscu której jest zero.
Odwrotna metoda potęgowa:
Przypuśćmy, że dysponujemy “dobrym” przybliżeniem σ wartości
własnej s
i
, takim że
j
i
s
s
i
j
−
<
−
≠
∀
σ
σ
. Wtedy (σ - s
i
)
-1
jest
dominującą wartością własną macierzy (σI - A)
-1
, stosujemy więc
metodę potęgową do niej:
v
m
=(σI - A)
-1
v
m-1
(σI - A)
v
m
=v
m-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.
Równanie jednej iteracji:
I
Q
Q
,
Q
A
Q
A
k
T
k
k
k
T
k
k
=
=
+
1
.
W9-5
Metody dla macierzy symetrycznych – np. metoda Jacobiego:
Przekształcenie (obrót) sparametryzowane wartością
φ
ϕ
≤
,
π
,
określone macierzą
)
(
R
q
,
p
ϕ
, która ma elementy macierzy
jednostkowej poza
ϕ
cos
r
r
q
,
q
p
,
p
=
=
,
ϕ
sin
r
r
p
,
q
q
,
p
=
−
=
.
Wtedy
1
−
=
=
−
))
(
R
(
))
(
R
(
)
(
R
q
,
p
T
q
,
p
q
,
p
ϕ
ϕ
ϕ
W macierzy A
k
wybieramy element
. Chcemy by
)
k
(
q
,
p
a
0
1
=
+
)
k
(
q
,
p
a
.
),
(
)
(
,
,
1
ϕ
ϕ
q
p
k
q
p
k
R
A
R
A
−
=
+
( )
( )
( )
k
q
p
k
q
q
k
p
p
k
q
p
a
a
a
ctg
a
,
,
,
)
1
(
,
2
)
2
(
0
−
=
⇔
=
+
ϕ
ϕ
tg
t
=
jest pierwiastkiem o mniejszym module równania
1
)
2
(
2
2
=
+
ϕ
ctg
t
t
Stąd wyznaczamy
ϕ
ϕ
cos
,
sin
.
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)
( )
∑∑
Jeżeli
≠
=
i
i
j
)
k
(
j
,
i
k
a
:
)
A
(
T
2
2
, to po jednym „wymiataniu”, w
którym wykonano
)
n
(
n
N
1
2
1
−
=
obrotów
(
)
2
2
2
)
A
(
T
C
)
A
(
T
k
N
k
≤
+
.
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 A
i
,
i
i
i
R
Q
A
=
,
- obliczamy
i
i
i
Q
R
A
=
+
1
Wtedy
i
i
T
i
i
i
i
T
i
i
i
i
Q
A
Q
Q
R
Q
Q
Q
R
A
=
=
=
+
1
, czyli dokonaliśmy
przekształcenia przez podobieństwo z ortogonalną macierzą
przekształcenia.
A
i
dąży do macierzy trójkątnej górnej z wartościami własnymi na
przekątnej.
W9-8