Ortogonalizacja Grama-Schmidta
Jakub Kaczmarek Szymon Grunt
15 grudnia 2012
J.Kaczmarek, S.Grunt
Ortogonolizacja Grama-Schmidta
15 grudnia 2012
1 / 24
Ortogonalizacja Grama-Schmidta
Jakub Kaczmarek Szymon Grunt
15 grudnia 2012
J.Kaczmarek, S.Grunt
Ortogonolizacja Grama-Schmidta
15 grudnia 2012
1 / 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±¢
De nicja
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±¢
De nicja
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
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
=
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
=
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
=
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
=
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
=
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
(
T
)(
T
) =
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
(
T
)(
T
) =
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
(
T
)(
T
) =
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 - 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
