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