Zagadnienie własne









ow

pierwiastk

n

dokladnie

ma

styczny;

charaktery

wielomian

0

det













I

A

0

x

I

A

x

Ax







W większości zastosowań w chemii i fizyce rozważamy
macierze rzeczywiste symetryczne. W takim przypadku
macierz znormalizowanych wektorów własnych jest
ortonormalna, tj. V

-1

=V

T

Macierz wektorów własnych V=(v

1

,v

2

,...,v

n

) przekształca

zatem macierz A do postaci diagonalnej:

Λ

AV

V

1



























n







1

Twierdzenie Gershgorina o wartościach własnych

Wartości własne dowolnej macierzy (rzeczywistej lub zespolonej)
leżą w zbiorze będącym sumą mnogościową kół scentrowanych na
odpowiednich elementach diagonalnych i o promieniach równych
sumie elementów pozadiagonalnych.





















i

k

ik

ii

i

a

a

z

C

Metody numerycznego rozwiązywania zagadnienia
własnego

1. Metoda potęgowa (iteracji wektorów): można ją stosować dla

znajdowania wartości własnej o największym module i
odpowiadającego jej wektora własnego.

2. Znajdowanie wielomianu charakterystycznego a następnie jego

zer (metoda Kryłowa).

3. Metoda Jacobiego (znajdowanie zarówno wartości jak i wektorów

własnych macierzy symetrycznych; droga i ma raczej znaczenie
historyczne).

4. Metoda rozkładu LR.

5. Metody rozkładu QR.

a) Metoda Householdera;

b) Metoda Givensa;

c) Metoda ortogonalizacji Schmidta.

Metody QR i LR umożliwiają znalezienie albo tylko samych wartości

własnych albo wartości i wektorów własnych. Ich zastosowanie
jest zwykle poprzedzone są sprowadzeniem macierzy do postaci
Hessenberga.

Metoda potęgowa (iteracji wektorów)

1. Wybieramy przybliżenie początkowe wektora własnego

odpowiadającego wartości własnej o największym module.

2. Kolejne przybliżenie wektora własnego obliczamy z wzoru:

)

(

)

(

)

1

(

p

p

p

Ax

Ax

x





3. Jeżeli x

i

(p+1)

/x

i

(p)

różnią się o mniej niż zadana dokładność dla

każdego i, kończymy iterację. Wtedy x

(p)

jest szukanym

wektorem własnym a wielkość jest przybliżeniem
wartości własnej o największym module.

W ten sposób można też znaleźć kolejne wartości i wektory własne.

Po znalezieniu pierwszego wektora własnego tworzymy wektor
do niego ortogonalny i prowadzimy ortogonalizując za każdym
razem otrzymany wektor do pierwszego wektora własnego.
Przykładowo, dla drugiego wektora własnego:

)

(

)

(

p

T

p

Ax

x













)

(
2

)

1

(
2

)

1

(
2

1

1

)

(
2

)

(
2

)

1

(
2

1

p

p

p

T

p

p

p

y

y

x

x

x

Ax

Ax

y













Dowód zbieżności metody iteracji potęgowej dla
największej co do modułu wartości własnej

Wektor x

(0)

można zapisać jako kombinację liniową wektorów

własnych:

n

n

c

c

c

v

v

v

x











2

2

1

1

)

0

(

Ponieważ x

(p)

otrzymuje się z x

(0)

przez p-krotne lewostronne

mnożenie przez A oraz Av

i

=v

i

mamy:





n

p

n

n

p

p

n

n

razy

p

p

c

c

c

c

c

c

v

v

v

v

v

v

A

AA

x





























 





2

2

2

1

1

1

2

2

1

1

)

(

Jeżeli 

1

jest wartością własną największą co do modułu to mamy:

1

,

1

,

2

1

2

2

,

1

1

1

1

,

,

2

2

2

,

1

1

1

)

1

(

)

(

)

(

lim

lim

lim





















































i

n

p

n

n

i

p

i

p

i

n

p

n

n

i

p

i

p

p

p

i

p

i

p

p

i

p

v

c

v

c

v

c

v

c

v

c

v

c

x

x

q





Metoda Jacobiego

Macierz symetryczną A sprowadzamy do postaci diagonalnej przy
pomocy iterowania transformacji jej dwuwymiarowych “klatek”
macierzami obrotów, które zerują pozadiagonalne elementy “klatek”.





























































)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

1

(

cos

sin

sin

cos

p

p

p

p

p

p

p

T

p

p









S

S

A

S

A

k-ta
kolumna

l-ta
kolumna

k-ty wiersz

l-ty wiesz













2

2

)

(

)

(

)

(

)

(

)

(

2

1

)

(

)

(

)

(

)

(

)

(

)

(

)

1

(

)

(

)

(

)

(

)

(

)

(

)

1

(

)

1

(

)

(

)

(

)

(

)

(

2

)

(

)

(

2

)

(

)

1

(

)

(

)

(

)

(

)

(

2

)

(

)

(

2

)

(

)

1

(

)

(

)

(

)

(

)

(

)

1

(

)

(

)

(

)

(

)

(

)

1

(

)

(

)

(

)

(

)

(

)

1

(

)

(

)

(

)

(

)

(

)

1

(

,

2

1

,

cos

2

sgn

sin

2

cos

2

1

2

tg

,

,

2

cos

2

sin

2

1

cos

sin

2

cos

sin

cos

sin

2

sin

cos

,

,

cos

sin

cos

cos

,

,

cos

sin

sin

cos







































































































































































p

ll

p

kk

p

kl

p

p

p

p

ll

p

kk

p

kl

p

p

ij

p

ij

p

p

kl

p

p

ll

p

kk

p

lk

p

kl

p

p

p

kl

p

p

ll

p

p

kk

p

ll

p

p

p

kl

p

p

ll

p

p

kk

p

kk

p

p

il

p

p

kj

p

il

p

p

il

p

p

ik

p

ik

p

p

lj

p

p

kj

p

lj

p

p

lj

p

p

kj

p

kj

a

a

a

a

a

a

l

j

k

i

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

l

k

i

a

a

a

a

a

a

l

k

j

a

a

a

a

a

a

Do transformacji najlepiej wybrać taką parę indeksów k i l, że
odpowiedni element pozadiagonalny macierzy A

(p)

ma największy

modł. Iteracja Jacobiego kończy się gdy wszystkie elementy
pozadiagonalne macierzy A

(p)

są mniejsze co do modułu niż zadana

dokładność.

Metoda Jacobiego daje również macierz wektorów własnych, która
jest iloczynem kolejnych (ortonornalnych) macierzy S

)

(

)

(

)

1

(

N

p

S

S

S

V







Metoda LR

)

(

)

(

1

)

(

)

(

)

(

)

1

(

)

(

)

(

2

)

(

22

)

(

1

)

(

12

)

(

11

)

(

)

(

2

)

(

1

)

(

21

)

(

)

(

)

(

)

(

1

1

1

p

p

p

p

p

p

p

nn

p

n

p

p

n

p

p

p

p

n

p

n

p

p

p

p

p

r

r

r

r

r

r

l

l

l

L

A

L

L

R

A

R

L

R

L

A



















































































(przekształcenie podobieństwa)

Ciąg macierzy A

(p)

dąży do w ogólności do macierzy trójkątnej

górnej a jeżeli macierz A jest symetryczna to do macierzy
diagonalnej, której elementami diagonalnymi są wartości własne
macierzy A.

Do przekształcenia LR wykorzystujemy algorytm eliminacji
Gaussa.

)

(

)

(

)

(

)

(

)

(

)

1

(

)

(

1

)

(

)

(

)

(

2

)

(

22

)

(

1

)

(

12

)

(

11

)

(

)

(

)

(

2

)

(

1

)

(

2

)

(

22

)

(

21

)

(

1

)

(

12

)

(

11

)

(

)

(

)

(

)

(

p

p

T

p

p

p

p

T

p

p

p

nn

p

n

p

p

n

p

p

p

p

nn

p

n

p

n

p

n

p

p

p

n

p

p

p

p

p

p

r

r

r

r

r

r

q

q

q

q

q

q

q

q

q

Q

A

Q

Q

R

A

Q

Q

R

Q

R

Q

A































































































Metoda QR

(macierze Q są ortonormalne)

Przekształcenie macierzy do postaci Hessenberga

AC

C

B

B

1

1

,

2

22

21

1

12

11





































nn

n

n

n

n

b

b

b

b

b

b

b

b











Jeżeli A jest macierzą symetryczną to macierz Hessenberga B
ma postać trójdiagonalną.

Macierz B jest podobna do macierzy A, zatem ma te same
wartości własne co macierz A, natomiast jej wektory y własne
są związane z wektorami własnymi macierzy A zależnością
y=C

-1

x.

Kolejne iloczyny R

(p)

Q

(p)

w procedurze iteracyjnej mają postać

Hessenberga co powoduje znaczną oszczędność rachunków.
Oszczędność jest jeszcze większa w przypadku gdy A jest
macierzą symetryczną.

Metoda Givensa













































1

1

)

(

)

(

)

(

)

(

)

(













j

j

j

j

j

c

s

s

c

G

Macierz A przekształcamy przy pomocy ioczynu elementarnych
macierzy Givensa. Macierz G

(j)

jest konstruowana w taki sposób

aby dla danego wektora z=[z

1

,z

2

,…,z

k

]

T

zachodziło Gz=||z||[1,0,

…,0]

T

.

j-ta kolumna

i-ty wiersz

   























































































0

1

:

Mamy

0

,

0

1

0

,

1

,

2

)

(

1

)

(

)

(

)

(

)

(

)

(

1

)

(

)

(

1

2

)

(

1

)

(

2

)

1

(

)

(

1

2

2

)

(

1

2

)

(

1



















j

j

j

j

j

j

j

j

j

j

j

j

j

j

j

j

j

j

j

z

z

c

s

s

c

s

c

z

s

z

c

z

z













A

G

G

G

G

G

G

G

A

Q

R

G

G

G

G

G

G

G

G

G

G

Q

)

(

1

)

1

(

1

)

2

(

1

)

1

(

2

)

2

(
2

)

2

(
2

)

2

(

1

)

2

(

1

)

2

(

2

)

3

(

2

)

1

(
2

)

2

(

1

)

3

(

1

)

(

1

1

2

1

n

T

n

T

n

n

n

T

T

n

T

T

T

n

T

T

T

n

T

n

T

T





































Macierz G

(1)

=G

1

(2)

G

1

(3)

…G

1

(n)

sprowadza pierwszą kolumnę

macierzy A do postaci 

(1)

||a

1

(2)

||[1,0,…,0]

T

. Kolejne

przekształcenie macierzy A

(2)

=G

(1)

A macierzą G

(2)

=G2

(1)

G

2

(2)

…

G

2

(n-1)

zeruje wszystkie elementy drugiej kolumny macierz A

(2)

oprócz pierwszych dwóch, itp.

Metoda Householdera

 

 

)

1

(

)

2

(

)

1

(

)

1

(

)

1

(

)

1

(

)

2

(

2

)

2

(

22

)

2

(

1

)

2

(

12

)

2

(

11

)

(

)

1

(

)

1

(

)

(

)

(

,

1

)

(

)

(

)

(

2

1

)

(

)

2

(

)

2

(

1

)

2

(

12

)

2

(

11

)

1

(

)

2

(

)

1

(

1

)

1

(

21

)

1

(

1

)

1

(

11

)

1

(

11

1

1

1

2

1

)

1

(

,

0

~

0

sgn

2

~

sgn

2















































































































































































n

i

n

in

i

ii

n

n

i

i

i

i

ni

i

i

i

i

i

i

ii

i

ii

i

T

i

i

i

i

n

i

n

n

T

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

H

H

H

Q

QR

A

A

A

H

A

a

v

v

v

v

I

H

A

A

H

A

a

v

v

v

v

I

H



















