Ortogonalizacja Grama-Schmidta

Jakub Kaczmarek Szymon Grunt

15 grudnia 2012

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

1 / 24

Spis Tre±ci

1

Ortogonalne bazy q

1

,. . . ,q

n

Ortogonalno±¢

Ortonormalno±¢

2

Macierz ortogonalna Q

Macierz projkecji

3

Gram-Schmidt A→ Q

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

2 / 24

ORTOGONALNE BAZY q

1

,. . . ,q

n

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

3 / 24

Ortogonalne bazy q

1

,. . . ,q

n

- Ortogonalno±¢

Denicja

Ortogonalno±¢ (z gr. ortho  prosto, prosty, gonia  k¡t)  uogólnienie poj¦cia

prostopadªo±ci znanego z geometrii euklidesowej na abstrakcyjne przestrzenie z

okre±lonym iloczynem skalarnym, jak np. przestrzenie unitarne czy przestrzenie

ortogonalne.

Elementy x i y przestrzeni X z iloczynem skalarnym < ∗, ∗ > nazywa si¦

ortogonalnymi, gdy:
<

x, y >= 0

Relacj¦ < x, y >= 0 zapisuje si¦ symbolicznie x ⊥ y . Podzbiór A przestrzeni X

nazywa si¦ ukªadem ortogonalnym, gdy ka»de dwa ró»ne jego elementy s¡

ortogonalne.

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

4 / 24

Ortogonalne bazy q

1

,. . . ,q

n

- Ortogonalno±¢

Denicja

Ortogonalno±¢ (z gr. ortho  prosto, prosty, gonia  k¡t)  uogólnienie poj¦cia

prostopadªo±ci znanego z geometrii euklidesowej na abstrakcyjne przestrzenie z

okre±lonym iloczynem skalarnym, jak np. przestrzenie unitarne czy przestrzenie

ortogonalne.

Elementy x i y przestrzeni X z iloczynem skalarnym < ∗, ∗ > nazywa si¦

ortogonalnymi, gdy:
<

x, y >= 0

Relacj¦ < x, y >= 0 zapisuje si¦ symbolicznie x ⊥ y . Podzbiór A przestrzeni X

nazywa si¦ ukªadem ortogonalnym, gdy ka»de dwa ró»ne jego elementy s¡

ortogonalne.

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

4 / 24

Ortogonalne bazy q

1

,. . . ,q

n

- Ortonormalno±¢

Zaªozenia

Je±li kolumny q

1

do q

n

umie±cimy w macierzy Q





q

1

. . .

q

n





I kolumny s¡ ortonormalne to:

Q

T

Q =



q

T

1

q

T

n







q

1

. . .

q

n





=





1 0 0

0 1 0

0 0 1





Podsumowanie

Wynik pow»szego dziaªania uzale»niony jest od ortonormalnosci wektrów, gdzie:

q

T

i

q

j

=



0 jesli i 6= j

1 jesli i = j

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

5 / 24

Ortogonalne bazy q

1

,. . . ,q

n

- Ortonormalno±¢

Zaªozenia

Je±li kolumny q

1

do q

n

umie±cimy w macierzy Q





q

1

. . .

q

n





I kolumny s¡ ortonormalne to:

Q

T

Q =



q

T

1

q

T

n







q

1

. . .

q

n





=





1 0 0

0 1 0

0 0 1





Podsumowanie

Wynik pow»szego dziaªania uzale»niony jest od ortonormalnosci wektrów, gdzie:

q

T

i

q

j

=



0 jesli i 6= j

1 jesli i = j

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

5 / 24

Ortogonalne bazy q

1

,. . . ,q

n

- Ortonormalno±¢

Zaªozenia

Je±li kolumny q

1

do q

n

umie±cimy w macierzy Q





q

1

. . .

q

n





I kolumny s¡ ortonormalne to:

Q

T

Q =



q

T

1

q

T

n







q

1

. . .

q

n





=





1 0 0

0 1 0

0 0 1





Podsumowanie

Wynik pow»szego dziaªania uzale»niony jest od ortonormalnosci wektrów, gdzie:

q

T

i

q

j

=



0 jesli i 6= j

1 jesli i = j

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

5 / 24

Macierz ortgonalna Q

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

6 / 24

Macierz ortgonalna Q

Ortogonalna macierz Q jest kwadratowa.

Je»eli macierz Q jest kwadratowa, to Q

T

Q = I

Mówi to nam, »e Q

T

=

Q

−

1

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

7 / 24

Macierz ortgonalna Q - Przykªady

Przykªad

Dowolna macierz permutacji Q na pewno posiada jednostkowe wektory w jej

kolumnach, s¡ one równie» prostopadªe wzgledem siebie

permQ =





0 0 1

1 0 0

0 1 0









0 1 0

0 0 1

1 0 0





=

I

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

8 / 24

Macierz ortgonalna Q - wektory jednostkowe

Przykªad

Dana macierz Q posiada ortgonalne kolumny ale sma nie jest ortogonalna, aby to

naprawi¢ nale»y podizeli¢ caªa macierz przez dªugosc wektorów, w tym przpadku

√

2

Q =



1

1

1 −1



tak wi¦c otrzymujemy

Q =

1

√

2



1

1

1 −1



=

"

1

√

2

1

√

2

1

√

2

−

1

√

2

#

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

9 / 24

Macierz ortgonalna Q - wektory jednostkowe

Przykªad

Dana macierz Q posiada ortgonalne kolumny ale sma nie jest ortogonalna, aby to

naprawi¢ nale»y podizeli¢ caªa macierz przez dªugosc wektorów, w tym przpadku

√

2

Q =



1

1

1 −1



tak wi¦c otrzymujemy

Q =

1

√

2



1

1

1 −1



=

"

1

√

2

1

√

2

1

√

2

−

1

√

2

#

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

9 / 24

Macierz ortgonalna Q - wektory jednostkowe

Przykªad

Dana macierz Q posiada ortgonalne kolumny ale sma nie jest ortogonalna, aby to

naprawi¢ nale»y podizeli¢ caªa macierz przez dªugosc wektorów, w tym przpadku

√

2

Q =



1

1

1 −1



tak wi¦c otrzymujemy

Q =

1

√

2



1

1

1 −1



=

"

1

√

2

1

√

2

1

√

2

−

1

√

2

#

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

9 / 24

Macierz ortgonalna Q - wektory jednostkowe

Przykªad 2

W tym przypadku mamy dan¡ macierz

Q =





1 −2

2

2 −1 −2

2

2

1





Jak wida¢ dªugosc poszeczególnych wektrów wynosi 3, dlatego te» mno»ymy

caª¡ macierz przez

1

3

Q =

1
3





1 −2

2

2 −1 −2

2

2

1





=





1

3

−

2

3

2

3

2

3

−

1

3

−

2

3

2

3

2

3

1

3





J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

10 / 24

Macierz ortgonalna Q - wektory jednostkowe

Przykªad 2

W tym przypadku mamy dan¡ macierz

Q =





1 −2

2

2 −1 −2

2

2

1





Jak wida¢ dªugosc poszeczególnych wektrów wynosi 3, dlatego te» mno»ymy

caª¡ macierz przez

1

3

Q =

1
3





1 −2

2

2 −1 −2

2

2

1





=





1

3

−

2

3

2

3

2

3

−

1

3

−

2

3

2

3

2

3

1

3





J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

10 / 24

Macierz ortgonalna Q - wektory jednostkowe

Przykªad 2

W tym przypadku mamy dan¡ macierz

Q =





1 −2

2

2 −1 −2

2

2

1





Jak wida¢ dªugosc poszeczególnych wektrów wynosi 3, dlatego te» mno»ymy

caª¡ macierz przez

1

3

Q =

1
3





1 −2

2

2 −1 −2

2

2

1





=





1

3

−

2

3

2

3

2

3

−

1

3

−

2

3

2

3

2

3

1

3





J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

10 / 24

Macierz ortgonalna Q - macierz projkecji

Macierz projkecji

Rozpatrujemy macierz Q z ortonormalnymi kolumnami.

U»ywamy projekcji na przestrzenie kolumnowe, wtedy macierz projekcji to:

P = Q(Q

T

Q)

−

1

Q

T

=

QQ

T

=

I

Przypu±¢my, »e macierz jest kwadratowa, posiada ortonormlane, niezale»ne

kolumny. Wtedy przestrzeni¡ kolumnow¡ jest caªa przestrze«. Macierz projkecji dla

caªej przestrzeni jest macierz¡ identyczno±ciow¡.

Zatem QQ

T

=

I

Dzieje sie tak tylko wtedy, gdy macierz Q jest kwadratowa!!!

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

11 / 24

Macierz ortgonalna Q - macierz projkecji

Macierz projkecji

Rozpatrujemy macierz Q z ortonormalnymi kolumnami.

U»ywamy projekcji na przestrzenie kolumnowe, wtedy macierz projekcji to:

P = Q(Q

T

Q)

−

1

Q

T

=

QQ

T

=

I

Przypu±¢my, »e macierz jest kwadratowa, posiada ortonormlane, niezale»ne

kolumny. Wtedy przestrzeni¡ kolumnow¡ jest caªa przestrze«. Macierz projkecji dla

caªej przestrzeni jest macierz¡ identyczno±ciow¡.

Zatem QQ

T

=

I

Dzieje sie tak tylko wtedy, gdy macierz Q jest kwadratowa!!!

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

11 / 24

Macierz ortgonalna Q - macierz projkecji

Macierz projkecji

Rozpatrujemy macierz Q z ortonormalnymi kolumnami.

U»ywamy projekcji na przestrzenie kolumnowe, wtedy macierz projekcji to:

P = Q(Q

T

Q)

−

1

Q

T

=

QQ

T

=

I

Przypu±¢my, »e macierz jest kwadratowa, posiada ortonormlane, niezale»ne

kolumny. Wtedy przestrzeni¡ kolumnow¡ jest caªa przestrze«. Macierz projkecji dla

caªej przestrzeni jest macierz¡ identyczno±ciow¡.

Zatem QQ

T

=

I

Dzieje sie tak tylko wtedy, gdy macierz Q jest kwadratowa!!!

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

11 / 24

Macierz ortgonalna Q - macierz projkecji

Macierz projkecji

Rozpatrujemy macierz Q z ortonormalnymi kolumnami.

U»ywamy projekcji na przestrzenie kolumnowe, wtedy macierz projekcji to:

P = Q(Q

T

Q)

−

1

Q

T

=

QQ

T

=

I

Przypu±¢my, »e macierz jest kwadratowa, posiada ortonormlane, niezale»ne

kolumny. Wtedy przestrzeni¡ kolumnow¡ jest caªa przestrze«. Macierz projkecji dla

caªej przestrzeni jest macierz¡ identyczno±ciow¡.

Zatem QQ

T

=

I

Dzieje sie tak tylko wtedy, gdy macierz Q jest kwadratowa!!!

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

11 / 24

Macierz ortgonalna Q - macierz projkecji

Macierz projkecji

Rozpatrujemy macierz Q z ortonormalnymi kolumnami.

U»ywamy projekcji na przestrzenie kolumnowe, wtedy macierz projekcji to:

P = Q(Q

T

Q)

−

1

Q

T

=

QQ

T

=

I

Przypu±¢my, »e macierz jest kwadratowa, posiada ortonormlane, niezale»ne

kolumny. Wtedy przestrzeni¡ kolumnow¡ jest caªa przestrze«. Macierz projkecji dla

caªej przestrzeni jest macierz¡ identyczno±ciow¡.

Zatem QQ

T

=

I

Dzieje sie tak tylko wtedy, gdy macierz Q jest kwadratowa!!!

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

11 / 24

Macierz ortgonalna Q - macierz projkecji

Cechy macierzy projkecji

1

Jest symetryczna

2

Podwójne u»ycie projekcji nic nie zmeinia
(

QQ

T

)(

QQ

T

) =

QQ

T

(=

I -kiedy macierz Q jest kwadratowa)

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

12 / 24

Macierz ortgonalna Q - macierz projkecji

Cechy macierzy projkecji

1

Jest symetryczna

2

Podwójne u»ycie projekcji nic nie zmeinia
(

QQ

T

)(

QQ

T

) =

QQ

T

(=

I -kiedy macierz Q jest kwadratowa)

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

12 / 24

Macierz ortgonalna Q - macierz projkecji

Cechy macierzy projkecji

1

Jest symetryczna

2

Podwójne u»ycie projekcji nic nie zmeinia
(

QQ

T

)(

QQ

T

) =

QQ

T

(=

I -kiedy macierz Q jest kwadratowa)

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

12 / 24

Macierz ortgonalna Q - macierz projkecji

Zalety macierzy projekcji

Jakie zalety zwi¡zane s¡ z macierzami projekcji ?

Caªy baªagan zwi¡zany z rozwi¡zaniami staj¦ si¦ trywilany, kiedy mamy

ortonormaln¡ baz¦ kolumnow¡, np:

A

T

Ax= A

T

b

W tym momenecie A to Q, wi¦c:

Q

T

Qx= Q

T

b

x= Q

T

b (poniewa» Q

T

Q = I )

Nast¦pstwa

x

i

=

q

T

i

b

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

13 / 24

Macierz ortgonalna Q - macierz projkecji

Zalety macierzy projekcji

Jakie zalety zwi¡zane s¡ z macierzami projekcji ?

Caªy baªagan zwi¡zany z rozwi¡zaniami staj¦ si¦ trywilany, kiedy mamy

ortonormaln¡ baz¦ kolumnow¡, np:

A

T

Ax= A

T

b

W tym momenecie A to Q, wi¦c:

Q

T

Qx= Q

T

b

x= Q

T

b (poniewa» Q

T

Q = I )

Nast¦pstwa

x

i

=

q

T

i

b

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

13 / 24

Macierz ortgonalna Q - macierz projkecji

Zalety macierzy projekcji

Jakie zalety zwi¡zane s¡ z macierzami projekcji ?

Caªy baªagan zwi¡zany z rozwi¡zaniami staj¦ si¦ trywilany, kiedy mamy

ortonormaln¡ baz¦ kolumnow¡, np:

A

T

Ax= A

T

b

W tym momenecie A to Q, wi¦c:

Q

T

Qx= Q

T

b

x= Q

T

b (poniewa» Q

T

Q = I )

Nast¦pstwa

x

i

=

q

T

i

b

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

13 / 24

Macierz ortgonalna Q - macierz projkecji

Zalety macierzy projekcji

Jakie zalety zwi¡zane s¡ z macierzami projekcji ?

Caªy baªagan zwi¡zany z rozwi¡zaniami staj¦ si¦ trywilany, kiedy mamy

ortonormaln¡ baz¦ kolumnow¡, np:

A

T

Ax= A

T

b

W tym momenecie A to Q, wi¦c:

Q

T

Qx= Q

T

b

x= Q

T

b (poniewa» Q

T

Q = I )

Nast¦pstwa

x

i

=

q

T

i

b

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

13 / 24

Macierz ortgonalna Q - macierz projkecji

Zalety macierzy projekcji

Jakie zalety zwi¡zane s¡ z macierzami projekcji ?

Caªy baªagan zwi¡zany z rozwi¡zaniami staj¦ si¦ trywilany, kiedy mamy

ortonormaln¡ baz¦ kolumnow¡, np:

A

T

Ax= A

T

b

W tym momenecie A to Q, wi¦c:

Q

T

Qx= Q

T

b

x= Q

T

b (poniewa» Q

T

Q = I )

Nast¦pstwa

x

i

=

q

T

i

b

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

13 / 24

Macierz ortgonalna Q - macierz projkecji

Zalety macierzy projekcji

Jakie zalety zwi¡zane s¡ z macierzami projekcji ?

Caªy baªagan zwi¡zany z rozwi¡zaniami staj¦ si¦ trywilany, kiedy mamy

ortonormaln¡ baz¦ kolumnow¡, np:

A

T

Ax= A

T

b

W tym momenecie A to Q, wi¦c:

Q

T

Qx= Q

T

b

x= Q

T

b (poniewa» Q

T

Q = I )

Nast¦pstwa

x

i

=

q

T

i

b

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

13 / 24

Macierz ortgonalna Q - macierz projkecji

Zalety macierzy projekcji

Jakie zalety zwi¡zane s¡ z macierzami projekcji ?

Caªy baªagan zwi¡zany z rozwi¡zaniami staj¦ si¦ trywilany, kiedy mamy

ortonormaln¡ baz¦ kolumnow¡, np:

A

T

Ax= A

T

b

W tym momenecie A to Q, wi¦c:

Q

T

Qx= Q

T

b

x= Q

T

b (poniewa» Q

T

Q = I )

Nast¦pstwa

x

i

=

q

T

i

b

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

13 / 24

Gram-Schmidt A→ Q

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

14 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Cel

Celem ortogonalizacji Grama - Schmidta jest otrzymanie ortogalnych wektrów z

niezale»nych wektrów.

Mamy dane 2 niezale»ne wetory a,b.

a = A natomiast b 6= B Poniewa» b nie jest ortogonalny do A. Szukamy wektora

ortogonalnego. Jak to zorbi¢ ?

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

15 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Cel

Celem ortogonalizacji Grama - Schmidta jest otrzymanie ortogalnych wektrów z

niezale»nych wektrów.

Mamy dane 2 niezale»ne wetory a,b.

a = A natomiast b 6= B Poniewa» b nie jest ortogonalny do A. Szukamy wektora

ortogonalnego. Jak to zorbi¢ ?

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

15 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Cel

Celem ortogonalizacji Grama - Schmidta jest otrzymanie ortogalnych wektrów z

niezale»nych wektrów.

Mamy dane 2 niezale»ne wetory a,b.

a = A natomiast b 6= B Poniewa» b nie jest ortogonalny do A. Szukamy wektora

ortogonalnego. Jak to zorbi¢ ?

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

15 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Pomysª

Niezale»nie od ilo±ci wymiarów, metoda jest taka sama.

Rzutujemy wektro b na wektor a.

B = b −

A

T

b

A

T

A

A, gdzie

A

T

b

A

T

A

A to operator rzutowania b na a.

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

16 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Pomysª

Niezale»nie od ilo±ci wymiarów, metoda jest taka sama.

Rzutujemy wektro b na wektor a.

B = b −

A

T

b

A

T

A

A, gdzie

A

T

b

A

T

A

A to operator rzutowania b na a.

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

16 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Pomysª

Niezale»nie od ilo±ci wymiarów, metoda jest taka sama.

Rzutujemy wektro b na wektor a.

B = b −

A

T

b

A

T

A

A, gdzie

A

T

b

A

T

A

A to operator rzutowania b na a.

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

16 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Sprawdzenie

Jak dokonujmey sprawdzenia, czy otrzymane wektor B rzeczywi±cie jest

prostopadaªe do wektora A?

Iloczyn skalarny A i B musi równa¢ si¦ 0, wi¦c:

A

T

B = A

T



b −

A

T

b

A

T

A

A



=

0

W miejsce B podstawiamy ró»nic¦ pierwotnego b i jego rzutu na wektor A.

Ostani krok

Ostanim krokiem jest znalezienie ortonormalnych wektorów q

1

i q

2

, gdzie:

q

1

=

A

||

A||

, q

2

=

B

||

B||

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

17 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Sprawdzenie

Jak dokonujmey sprawdzenia, czy otrzymane wektor B rzeczywi±cie jest

prostopadaªe do wektora A?

Iloczyn skalarny A i B musi równa¢ si¦ 0, wi¦c:

A

T

B = A

T



b −

A

T

b

A

T

A

A



=

0

W miejsce B podstawiamy ró»nic¦ pierwotnego b i jego rzutu na wektor A.

Ostani krok

Ostanim krokiem jest znalezienie ortonormalnych wektorów q

1

i q

2

, gdzie:

q

1

=

A

||

A||

, q

2

=

B

||

B||

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

17 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Sprawdzenie

Jak dokonujmey sprawdzenia, czy otrzymane wektor B rzeczywi±cie jest

prostopadaªe do wektora A?

Iloczyn skalarny A i B musi równa¢ si¦ 0, wi¦c:

A

T

B = A

T



b −

A

T

b

A

T

A

A



=

0

W miejsce B podstawiamy ró»nic¦ pierwotnego b i jego rzutu na wektor A.

Ostani krok

Ostanim krokiem jest znalezienie ortonormalnych wektorów q

1

i q

2

, gdzie:

q

1

=

A

||

A||

, q

2

=

B

||

B||

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

17 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Sprawdzenie

Jak dokonujmey sprawdzenia, czy otrzymane wektor B rzeczywi±cie jest

prostopadaªe do wektora A?

Iloczyn skalarny A i B musi równa¢ si¦ 0, wi¦c:

A

T

B = A

T



b −

A

T

b

A

T

A

A



=

0

W miejsce B podstawiamy ró»nic¦ pierwotnego b i jego rzutu na wektor A.

Ostani krok

Ostanim krokiem jest znalezienie ortonormalnych wektorów q

1

i q

2

, gdzie:

q

1

=

A

||

A||

, q

2

=

B

||

B||

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

17 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Gram-Schmitd dla 3 wektorów

Wektor C musi byc prostopadªy do wektora A i wektora B.

C = c −

A

T

c

A

T

A

A −

B

T

c

B

T

B

B, gdzie:

A

T

c

A

T

A

A - jest operatorem rzutowania c na A,

B

T

c

B

T

B

B - jest operatorem rzutowania c na B

Nale»y pami¦ta¢ o znalezieniu ortormalnego wektora q

3

=

C

||

C||

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

18 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Gram-Schmitd dla 3 wektorów

Wektor C musi byc prostopadªy do wektora A i wektora B.

C = c −

A

T

c

A

T

A

A −

B

T

c

B

T

B

B, gdzie:

A

T

c

A

T

A

A - jest operatorem rzutowania c na A,

B

T

c

B

T

B

B - jest operatorem rzutowania c na B

Nale»y pami¦ta¢ o znalezieniu ortormalnego wektora q

3

=

C

||

C||

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

18 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Gram-Schmitd dla 3 wektorów

Wektor C musi byc prostopadªy do wektora A i wektora B.

C = c −

A

T

c

A

T

A

A −

B

T

c

B

T

B

B, gdzie:

A

T

c

A

T

A

A - jest operatorem rzutowania c na A,

B

T

c

B

T

B

B - jest operatorem rzutowania c na B

Nale»y pami¦ta¢ o znalezieniu ortormalnego wektora q

3

=

C

||

C||

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

18 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Gram-Schmitd dla 3 wektorów

Wektor C musi byc prostopadªy do wektora A i wektora B.

C = c −

A

T

c

A

T

A

A −

B

T

c

B

T

B

B, gdzie:

A

T

c

A

T

A

A - jest operatorem rzutowania c na A,

B

T

c

B

T

B

B - jest operatorem rzutowania c na B

Nale»y pami¦ta¢ o znalezieniu ortormalnego wektora q

3

=

C

||

C||

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

18 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Gram-Schmitd dla 3 wektorów

Wektor C musi byc prostopadªy do wektora A i wektora B.

C = c −

A

T

c

A

T

A

A −

B

T

c

B

T

B

B, gdzie:

A

T

c

A

T

A

A - jest operatorem rzutowania c na A,

B

T

c

B

T

B

B - jest operatorem rzutowania c na B

Nale»y pami¦ta¢ o znalezieniu ortormalnego wektora q

3

=

C

||

C||

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

18 / 24

Gram-Schmidt A→ Q - Przykªady

Przykªad 1

A =





1 1

1 0

1 2





;

a =





1

1

1





;

b =





1

0

2





Podstawmy do wzoru B =

b −

A

T

b

A

T

A

A



A =





1

1

1





;

B =





1

0

2





−

3
3





1

1

1





=





0

−

1

1





Obliczamy q

1

i q

2

:

q

1

=

1

√

3





1

1

1





=






1

√

3

1

√

3

1

√

3






;

q

2

=

1

√

2





0

−

1

1





=






0

−

1

√

2

1

√

2






J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

19 / 24

Gram-Schmidt A→ Q - Przykªady

Przykªad 1

A =





1 1

1 0

1 2





;

a =





1

1

1





;

b =





1

0

2





Podstawmy do wzoru B =

b −

A

T

b

A

T

A

A



A =





1

1

1





;

B =





1

0

2





−

3
3





1

1

1





=





0

−

1

1





Obliczamy q

1

i q

2

:

q

1

=

1

√

3





1

1

1





=






1

√

3

1

√

3

1

√

3






;

q

2

=

1

√

2





0

−

1

1





=






0

−

1

√

2

1

√

2






J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

19 / 24

Gram-Schmidt A→ Q - Przykªady

Przykªad 1

A =





1 1

1 0

1 2





;

a =





1

1

1





;

b =





1

0

2





Podstawmy do wzoru B =

b −

A

T

b

A

T

A

A



A =





1

1

1





;

B =





1

0

2





−

3
3





1

1

1





=





0

−

1

1





Obliczamy q

1

i q

2

:

q

1

=

1

√

3





1

1

1





=






1

√

3

1

√

3

1

√

3






;

q

2

=

1

√

2





0

−

1

1





=






0

−

1

√

2

1

√

2






J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

19 / 24

Gram-Schmidt A→ Q - Przykªady

Przykªad 1

A =





1 1

1 0

1 2





;

a =





1

1

1





;

b =





1

0

2





Podstawmy do wzoru B =

b −

A

T

b

A

T

A

A



A =





1

1

1





;

B =





1

0

2





−

3
3





1

1

1





=





0

−

1

1





Obliczamy q

1

i q

2

:

q

1

=

1

√

3





1

1

1





=






1

√

3

1

√

3

1

√

3






;

q

2

=

1

√

2





0

−

1

1





=






0

−

1

√

2

1

√

2






J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

19 / 24

Gram-Schmidt A→ Q - Przykªady

Przykªad 1

A =





1 1

1 0

1 2





;

a =





1

1

1





;

b =





1

0

2





Podstawmy do wzoru B =

b −

A

T

b

A

T

A

A



A =





1

1

1





;

B =





1

0

2





−

3
3





1

1

1





=





0

−

1

1





Obliczamy q

1

i q

2

:

q

1

=

1

√

3





1

1

1





=






1

√

3

1

√

3

1

√

3






;

q

2

=

1

√

2





0

−

1

1





=






0

−

1

√

2

1

√

2






J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

19 / 24

Gram-Schmidt A→ Q - Przykªady

Przykªad 1

Zatem:

A =





1 1

1 0

1 2





;

Q =






1

√

3

0

1

√

3

−

1

√

2

1

√

3

1

√

2






J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

20 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Przykªad 2

A =



3 2

1 2



;

a =



3

1



;

b =



2

2



A =



3

1



;

B =



2

2



−

4
5



3

1



=



−

2

5

6

5



q

1

=

1

√

10



3

1



=

"

3

√

10

1

√

10

#

;

q

2

=

1

q

40

25



−

2

5

6

5



=

"

−

1

√

10

3

√

10

#

Zatem:

A =



3 2

1 2



;

Q =

"

3

√

10

−

1

√

10

1

√

10

3

√

10

#

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

21 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Przykªad 2

A =



3 2

1 2



;

a =



3

1



;

b =



2

2



A =



3

1



;

B =



2

2



−

4
5



3

1



=



−

2

5

6

5



q

1

=

1

√

10



3

1



=

"

3

√

10

1

√

10

#

;

q

2

=

1

q

40

25



−

2

5

6

5



=

"

−

1

√

10

3

√

10

#

Zatem:

A =



3 2

1 2



;

Q =

"

3

√

10

−

1

√

10

1

√

10

3

√

10

#

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

21 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Przykªad 2

A =



3 2

1 2



;

a =



3

1



;

b =



2

2



A =



3

1



;

B =



2

2



−

4
5



3

1



=



−

2

5

6

5



q

1

=

1

√

10



3

1



=

"

3

√

10

1

√

10

#

;

q

2

=

1

q

40

25



−

2

5

6

5



=

"

−

1

√

10

3

√

10

#

Zatem:

A =



3 2

1 2



;

Q =

"

3

√

10

−

1

√

10

1

√

10

3

√

10

#

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

21 / 24

Gram-Schmidt A→ Q - Ortogonalizacja Grama-Schmidta

Przykªad 2

A =



3 2

1 2



;

a =



3

1



;

b =



2

2



A =



3

1



;

B =



2

2



−

4
5



3

1



=



−

2

5

6

5



q

1

=

1

√

10



3

1



=

"

3

√

10

1

√

10

#

;

q

2

=

1

q

40

25



−

2

5

6

5



=

"

−

1

√

10

3

√

10

#

Zatem:

A =



3 2

1 2



;

Q =

"

3

√

10

−

1

√

10

1

√

10

3

√

10

#

J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

21 / 24

Gram-Schmidt A→ Q - A = QR

A = QR

Podobnie jak w dekompozycji LU, macierz A mo»na przedsatwi¢ za pomoc¡

iloczyny macierzy Q i macierzy R.





a

1

a

2





=





q

1

q

2







a

T

1

q

1

a

T

2

q

1

0

a

T

2

q

2



J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

22 / 24

Gram-Schmidt A→ Q - A = QR

A = QR

Podobnie jak w dekompozycji LU, macierz A mo»na przedsatwi¢ za pomoc¡

iloczyny macierzy Q i macierzy R.





a

1

a

2





=





q

1

q

2







a

T

1

q

1

a

T

2

q

1

0

a

T

2

q

2



J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

22 / 24

Gram-Schmidt A→ Q - Przykªad

Przykªad

A =





1 2 4

0 0 5

0 3 6





;

a =





1

0

0





;

b =





2

0

3





;

c =





4

5

6





A =





1

0

0





;

B =





2

0

3





−

2





1

0

0





=





0

0

3





C =





4

5

6





−

4





1

0

0





−

2





0

0

3





=





0

5

0





J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

23 / 24

Gram-Schmidt A→ Q - Przykªad

Przykªad

A =





1 2 4

0 0 5

0 3 6





;

a =





1

0

0





;

b =





2

0

3





;

c =





4

5

6





A =





1

0

0





;

B =





2

0

3





−

2





1

0

0





=





0

0

3





C =





4

5

6





−

4





1

0

0





−

2





0

0

3





=





0

5

0





J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

23 / 24

Gram-Schmidt A→ Q - Przykªad

Przykªad cd.

A =





1

0

0





;

B =





0

0

3





;

C =





0

5

0





q

1

=





1

0

0





;

q

2

=

1
3





0

0

3





;

q

3

=

1
5





0

5

0





A = QR zatem:





1 2 4

0 0 5

0 3 6





=





1 0 0

0 0 1

0 1 0









1 2 4

0 3 6

0 0 5





J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

24 / 24

Gram-Schmidt A→ Q - Przykªad

Przykªad cd.

A =





1

0

0





;

B =





0

0

3





;

C =





0

5

0





q

1

=





1

0

0





;

q

2

=

1
3





0

0

3





;

q

3

=

1
5





0

5

0





A = QR zatem:





1 2 4

0 0 5

0 3 6





=





1 0 0

0 0 1

0 1 0









1 2 4

0 3 6

0 0 5





J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

24 / 24

Gram-Schmidt A→ Q - Przykªad

Przykªad cd.

A =





1

0

0





;

B =





0

0

3





;

C =





0

5

0





q

1

=





1

0

0





;

q

2

=

1
3





0

0

3





;

q

3

=

1
5





0

5

0





A = QR zatem:





1 2 4

0 0 5

0 3 6





=





1 0 0

0 0 1

0 1 0









1 2 4

0 3 6

0 0 5





J.Kaczmarek, S.Grunt

Ortogonolizacja Grama-Schmidta

15 grudnia 2012

24 / 24