Mariusz PYRZ
SIMR (PW), Instytut Pojazdów
Metody numeryczne w mechanice
Wartości i wektory własne
7.
Mariusz PYRZ
SIMR (PW), Instytut Pojazdów
Metody numeryczne w mechanice
Wartości i wektory własne
7.
Wprowadzenie
Macierz kwadratowa A
nxn
moŜe być interpretowana jako macierz słuŜąca do
przekształcenia wektora n-elementowego. Dowolnemu wektorowi
x
∈
R
n
moŜna
przypisać
y
∈
R
n
taki, Ŝe
Ax=y
, gdzie A przedstawia przekształcenie liniowe.
Wynikiem przekształcenia liniowego wektora x jest :
• Zmiana długości x ( czyli norma ||x||
2
≠
||y||
2
),
• Zmiana kierunku (co m.in. róŜni przekształcenie liniowe x uzyskane za pomocą
2
• Zmiana kierunku (co m.in. róŜni przekształcenie liniowe x uzyskane za pomocą
macierzy A od pomnoŜenia x przez skalar).
JednakŜe jeŜeli istnieje wektor
x
taki, Ŝe Ax daje wektor równoległy do x
to wówczas x nazywamy wektorem własnym macierzy A.
Istnieje wówczas skalar
λ
taki Ŝe
Ax =
λ
x
i jest on nazywany wartością własną.
Wynik przekształcenia liniowego Ax jest „zredukowany” do pomnoŜenia tego
wektora x przez liczbę
λ
.
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
Interpretacja graficzna
Rysunek 1
Ax =
λ
x
Przykład obliczeniowy
3
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
1
4
2
3
=
A
0
4
4
0
=
A
Wektory własne ortogonalne
Definicje
Niech A będzie macierzą kwadratową rzędu n.
Wartością własną
macierzy A nazywamy liczbę
λ∈
C dla której istnieje
niezerowy wektor x
∈
C
n
zwany
wektorem własnym
(prawostronnym) taki, Ŝe
Ax =
λ
x lub inaczej (A-
λ
I)x=0 .
Aby istniał x
≠≠≠≠
0, trzeba aby macierz A-
λ
I była macierzą szczególną,
4
to jest
det(A-
λ
I)=0.
Widmo (spektrum)
macierzy A to zbiór jej wszystkich wartości własnych.
Promieniem spektralnym
macierzy A nazywamy liczbę
(czyli wartość własną o maksymalnym module).
ρ
λ
(
)
m a x
A
=
≤ ≤
1 i n
i
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
Definicje
Wektor własny jest wyznaczany z dokładnością do stałego mnoŜnika
(poniewaŜ Ax =
λ
x jest równowaŜne A(
α
x) =
λ
(
α
x) dla
α≠
0).
MoŜna zatem dobrać
α
tak, aby
||x||=1
.
normalizacja
5
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
Rysunek 2
Przykłady z mechaniki
Zagadnienia stateczności konstrukcji:
siły krytyczne i postacie wyboczenia
Zagadnienie drgań swobodnych (własnych):
6
częstotliwości i postacie drgań
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
Rysunek 3
Rysunek 4
Definicje i twierdzenia
Wielomian charakterystyczny (stopnia n) macierzy A :
w
A
(
λ
)=det(A-
λ
I).
Pierwiastkami wielomianu w
A
(
λ
) są wartości własne macierzy A.
Pierwiastki mogą być pojedyncze lub wielokrotne.
Macierze A i B są podobne jeśli istnieje nieosobliwa macierz podobieństwa S
7
det A
=
=
∏
λ
i
i
n
1
Macierze A i B są podobne jeśli istnieje nieosobliwa macierz podobieństwa S
taka Ŝe B=S
-1
AS.
Macierze podobne posiadają identyczny wielomian charakterystyczny
(to znaczy identyczne wartości własne).
w
B
(
λ
) = det(B-
λ
I) = det(S
-1
AS -
λ
S
-1
S) = det(S
-1
) det(A-
λ
I) det(S) = det(A-
λ
I)
czyli w
B
(
λ
) = w
A
(
λ
)
MoŜna wykazać, Ŝe wartości własne są niezaleŜne od bazy w jakiej
reprezentowana jest macierz A. W szczególności
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
Definicje i twierdzenia
Wektor własny x
B
macierzy B (podobnej do macierzy A) moŜna wyznaczyć
na podstawie wektora własnego x macierzy A za pomocą przekształcenia
x
B
= S
-1
x
(gdyŜ Ax =
λ
x
⇔
⇔
⇔
⇔
(S
-1
AS) (S
-1
x) =
λ
(S
-1
x) )
JeŜeli Ax =
λ
x to
(A-
µ
I)x =(
λ
-
µ
)x
A
k
x =
λ
k
x
8
(A-
µ
I)x =(
λ
-
µ
)x
A
k
x =
λ
k
x
A
-1
x =(1/
λ
)x (jeŜeli A
-1
istnieje)
Macierz rzeczywista symetryczna ma rzeczywiste wartości własne a jej
wektory własne, prznaleŜne do róŜnych wartości własnych, są do siebie
ortogonalne.
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
Metoda potęgowa – pozwala na wyznaczenie wartości własnej o
największym module (i odpowiadającego jej wektora własnego)
Odwrotna metoda potęgowa
- pozwala na wyznaczenie wartości własnej o najmniejszym module
Obliczanie pojedynczej wartości własnej
Ax=
λ
x
Ax
x
x
=
→
λ
λ
λ
max
max
,
- pozwala na wyznaczenie wartości własnej o najmniejszym module
(i odpowiadającego jej wektora własnego)
- pozwala na wyznaczenie wartości własnej o module najbliŜszym podanej
wartości (i odpowiadającego jej wektora własnego)
9
1
min
min
,
macierzy
λ
λ
λ
−
=
→
A x
x
x
A
(
)
,
A
I
x
x
x
−
=
→
≈
−
≈
µ
λ
λ µ
λ µ
1
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
Metody obliczania wielu wartości własnych
Ax=
λ
x
Obliczanie p wartości własnych macierzy
Pozwala obliczyć p wartości własnych o największych (lub najmniejszych)
modułach (i odpowiadających im wektorów własnych)
Metoda Rayleigh’a-Ritz’a,
Metoda podprzestrzennych iteracji
Metoda Lanczos’a
10
Metoda Lanczos’a
Obliczanie wszystkich wartości własnych macierzy
Rozwiązanie otrzymywane przez diagonalizację macierzy A
Metoda Jacobi ‘ego (do macierzy symetrycznych rzeczywistych)
Metoda QR
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
Ciąg wektorów x
(k)
jest zbieŜny do wektora x wraz z k
→∞
jeŜeli
Jest to równowaŜne
dla kaŜdej normy wektorowej.
Ciąg macierzy A
(k)
jest zbieŜny do macierzy A wraz z k
→∞
jeŜeli
ZbieŜność
( )
( )
( )
0
1
i
i
dla
i
n
−
→
≤ ≤
k
x
x
x
x
k
( )
− →
0
Ciąg macierzy A
(k)
jest zbieŜny do macierzy A wraz z k
→∞
jeŜeli
Jest to równowaŜne
dla kaŜdej normy wektorowej
lub inaczej
dla kaŜdej normy macierzowej.
11
( )
( )
( )
0
1
, 1
ij
ij
dla
i
n
j
n
−
→
≤ ≤
≤ ≤
k
A
A
∀
−
→
x
A
x
Ax
k
( )
0
A
A
k
( )
−
→
0
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
Pozwala obliczyć przybliŜenie wartości własnej
o największym module
oraz
odpowiadającego jej wektora własnego.
Algorytm
Wybrać wektor początkowy x
(0)
i znormalizować go
Dla iteracji k=1,2,3,… (aŜ do spełnienia warunku stopu) obliczyć
Metoda potęgowa (iteracji wektorów)
1
−
=
(k)
(k
)
(0)
(0)
(0)
x
q
=
x
opcjonalne oszacowanie wartości własnej*
(j) oznacza j-my element wektora.
*) zwykle liczone jako
Kryterium stopu: np.
||q
(k)
- q
(k-1)
||<
ε
12
1
( )
( )
(
)
( )
( )
(
)
( )
[
(
1,...,
0) ]
j
k
j
j
j
j
n
dla
λ
−
−
−
=
=
=
≠
=
(k)
(k
)
(k)
k 1
k 1
(k)
(k)
(k)
x
Aq
x
q
q
x
q
x
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
( )
(k)
( )
(k-1)
sup
j
j
k
j
λ
=
x
q
Przykład obliczeniowy
Normalizacja jest niezbędna aby nie przekroczyć zakresu reprezentacji
numerycznej liczb zmiennoprzecinkowych (moŜna uŜyć dowolnej normy).
Metoda potęgowa
numerycznej liczb zmiennoprzecinkowych (moŜna uŜyć dowolnej normy).
Szybkość zbieŜności zaleŜy od wyboru wektora startowego.
13
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
ZałóŜmy, Ŝe macierz A
n x n
ma n liniowo niezaleŜnych wektorów własnych.
Uszeregujmy w następujący sposób wartości własne (i odpowiadające im
wektory własne):
zakładamy pojedynczą największą wartość własną
z wektorów własnych budujemy bazę przestrzeni R
n
Wektor początkowy x
(0)
w bazie zbudowanej na wektorach własnych:
Idea metody potęgowej
1
2
...
n
λ
λ
λ
>
≥ ≥
1
2
n
v
v
v
moŜna przyjąć a
i
=1 (i=1,…,n) bo wektory
własne wyznaczane z dokładnością do stałej
W k-tym kroku metody x
(k) =
Ax
(k-1) =
AAx
(k-2) = … =
A
k
x
(0)
14
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
1 1
2
2
...
n
n
a
a
a
=
+
+ +
(0)
x
v
v
v
(
)
(
)
(
)
0
1
2
1
1
2
2
( )
1
1
2
1
2
1
1
1
...
...
/
...
/
k
k
k
k
k
k
k
k
n
n
n
k
k
k
k
k
n
n
λ
λ
λ
λ
λ λ
λ λ
λ
ε
=
=
+
+ +
=
+
+ +
=
=
+
+ +
=
+
( )
( )
x
A x
A v
A v
A v
v
v
v
v
v
v
v
( )
1
0
/
1
k
i
dla k
poniewaz
dla i
ε
λ λ
→
→ ∞
>
Odwrotna metoda potęgowa
Pozwala obliczyć przybliŜenie wartości własnej
o najmniejszym module
oraz odpowiadającego jej wektora własnego.
Polega ona na zastosowaniu metody potęgowej do macierzy A
-1
, poniewaŜ
wartości własne macierzy odwrotnej to odwrotność wartości własnych A.
max
min
i
i
i
i
1
1
λ
λ
=
15
W praktyce zamiast odwracać macierz A w algorytmie, tj. x
(k)
=A
-1
q
(k-1)
rozwiązuje się układy równań liniowych Ax
(k)
=q
(k-1)
, po wcześniejszym,
jednorazowym rozkładzie LU macierzy A=LU (na przykład metodą eliminacji
Gaussa).
i
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
Oblicza przybliŜenie wartości własnej
o najmniejszym module
oraz
odpowiadającego jej wektora własnego.
Algorytm
Wybrać wektor początkowy x
(0)
i znormalizować go
Dla iteracji k=1,2,3,… (aŜ do spełnienia warunku stopu)
Odwrotna metoda potęgowa
(0)
(0)
(0)
x
q
=
x
obliczyć x
(k)
rozwiązując układ równań
szacowanie wartości własnej
Kryterium stopu: np.
||q
(k)
- q
(k-1)
||<
ε
16
1
−
=
=
(k)
(k
)
(k)
(k)
(k)
Ax
q
x
q
x
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
(
)
( )
( )
(
)
( )
( )
( )
[
(
1,...,
0) ]
j
k
j
j
j
j
n
dla
λ
−
−
=
=
≠
k 1
k 1
(k)
q
q
x
Metoda Jacobi’ego
Wyznacza wszystkie wartości i wektory własne symetrycznej macierzy A
dokonując
transformacji
ortogonalizacyjnych
przez
podobieństwo
i
sprowadzając macierz do postaci diagonalnej diag(λ
1
,λ
2
,…, λ
n
) posiadającej
takie same wartościach własnych co A.
W procedurze diagonalizacyjnej, w iteracji k wyznaczana jest macierz
transformacji (rotacji elementarnej) dobierana tak, aby wyzerować wybrany
element pozadiagonalny. W związku z symetrią A
k-1
kaŜdorazowo anulują się
17
element pozadiagonalny. W związku z symetrią A
k-1
kaŜdorazowo anulują się
dwa elementy.
G
k
( , )
cos
sin
sin
cos
p q
p
q
p
q
=
−
L
N
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
O
Q
P
P
P
P
P
P
P
P
P
P
P
P
P
P
P
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
⋱
⋮
⋮
⋯
⋯
⋯
⋮
⋱
⋮
⋯
⋯
⋯
⋮
⋮
⋱
θ
θ
θ
θ
G
k
(p,q) - macierz rotacji o kąt
θ
w płaszczyźnie p-ego i q-ego
wektora bazowego (1
≤
p<q
≤
n)
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
Polega na przekształceniu (rozkładzie) macierzy A do postaci A=QR ,
zachowując właściwość podobieństwa macierzy. Macierz R jest macierzą
trójkątną górną, macierz Q jest macierzą ortogonalną (tzn. Q
T
Q = I).
Przekształcane iteracyjnie macierze są podobne (tj. mają identyczne wartości
własne), wartości własne wynikowej macierzy trójkątnej leŜą na przekątnej
głównej.
Metoda QR
Rozkład ortogonalny A=QR moŜe być dokonany za pomocą algorytmu Householdera lub
Givensa.
18
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
Normy wektorowe i macierzowe
normy wektorowe
1/ 2
2
1
2
1
1
1/
1
1
1
sup
n
n
i
i
i
i
p
n
p
i
i
p
i n
i
x
norma
x
norma euklidesowa
x
norma nieskonczona
x
=
=
∞
≤ ≤
=
=
=
=
=
∑
∑
∑
x
x
x
x
19
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012
normy macierzowe (stowarzyszone z normami wektorowymi)
A
Ax
Ax
x
A
Ax
x
A
Ax
x
A A
A
Ax
x
x C
x
x
x
x
*
x
n
=
=
=
=
L
NM
O
QP
=
=
=
=
L
N
M
O
Q
P
∈
=
≠
≠
≤ ≤
=
≠
∞
≠
∞
∞
≤ ≤
=
∑
∑
sup
sup
sup
sup
sup
(
)
sup
sup
/
1
0
1
0
1
1
1
1
2
0
2
2
1 2
0
1
1
j n
ij
i
n
i n
ij
j
n
a
a
ρ
• Macierz transponowana A
T
: a
T
ij
=a
ji
• Macierz sprzęŜona A* : a
*
ij
=â
ji
(â
ji
jest liczbą sprzęŜoną do a
ij
)
(dla macierzy rzeczywistej A, macierz A* jest równa macierzy transponowanej A
T
)
• Macierz hermitowska (samozprzęŜona) A*=A
• Macierz symetryczna jeŜeli A
T
=A
• Macierz unitarna jeŜeli A*A=I
(kolumny macierzy A są wówczas wektorami ortogonalnymi o normie 1)
Macierze- przydatne pojęcia
(kolumny macierzy A są wówczas wektorami ortogonalnymi o normie 1)
• Macierz kwadratowa unitarna A
-1
=A*
• Macierz normalna jeŜeli AA* = A*A
(macierze hermitowskie, unitarne, antyhermitowskie tj. A*=-A są normalne).
• JeŜeli macierz unitarna ma wszystkie elementy rzeczywiste, nazywamy ją
ortogonalną tj. A
T
A = AA
T
=I
20
M.Pyrz Metody numeryczne w mechanice – Wartości i wektory własne 03.2012