Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 9

W9-1

Obliczanie wektorów i wartości własnych
Równanie charakterystyczne

0

=

−

)

sI

A

det(

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

→

Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 9

W9-2

Wyznaczanie wartości własnych z równania charakterystycznego
Metoda Kryłowa wyznaczania współczynników wielomianu
charakterystycznego
Z tw. Calley’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

Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 9

W9-3

Metoda potęgowa

Dla dowolnego

0

v istnieją

i

a takie , że

i

n

i

i

x

a

v

∑

=

=

1

0

. Wtedy

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

m

v

o największym module.

Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 9

W9-4

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.

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

.

Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 9

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

)

k

(

q

,

p

a

. Chcemy by

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

.

Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 9

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.

Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 9

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.