POLITECHNIKA POZNASKA
Rzutowanie.
Metoda najmniejszych kwadratów.
Autorzy:
Bartªomiej Graczyk
Paweª Talerzak
19 grudnia 2012
POLITECHNIKA POZNASKA
Rzutowanie.
Metoda najmniejszych kwadratów.
Autorzy:
Bartªomiej Graczyk
Paweª Talerzak
19 grudnia 2012
B.Graczyk P.Talerzak
Rzutowanie. Metoda najmniejszych kwadratów.
Rzutowanie macierzy i najmniejsze kwadraty
Rzutowanie
Na ostatnim wykªadzie, dowiedzieli±my si¦, »e P = A(A
T
A)
−1
A
T
jest macierz¡, któ-
ra rzutuje wektor b na przestrzeni rozªo»onej przez kolumny Macierzy A. Je»eli b jest
prostopadªy to przestrzeni kolumnowej, to znaduje si¦ w lewej przestrzeni zerowej
N (A
T
)
macierzy A i Pb=0. Je»eli wektor b znajduje si¦ w przestrzeni kolumnowej
to b = Ax dla niewiadomej x, oraz P b = b.
Przykªadowy wektor b¦dzie miaª skªadnik p w przestrzeni kolumnowej oraz skªad-
nik e, prostopadªy do przestrzeni kolumnowej (w lewej przestrzeni zerowej); to rzut
ten jest skªadnikiem w przestrzeni kolumnowej.
Macierz rzutuj¡ca b na N(A
T
)
jest I˘P :
e = p − b
e = (I − P )b
Oczywi±cie, I − P ma wszystie wªa±ciwo±ci macierzy rzutowania
Najmniejsze kwadraty
.
Rysunek 1: Trzy punkty i najbli»sza do nich prosta.
Chcemy znale¹¢ najblizsz¡ prost¡ b = C + Dt do punktów (1,1), (2,2) i (3,2).
Zabieg, którego u»yjemy nazywa si¦ regresj¡ liniow¡. Ta technika jest najbardziej
u»yteczna, je»eli »aden z tych punktów nie jest odstaj¡cy.
Przez najbli»sz¡ lini¦ mamy na my±li tak¡, która minimalizuje bª¡d reprezento-
wany przez odlegªo±¢ tych punktów od prostej. Mierzymy ten bª¡d dodaj¡c kwadraty
tych odlegªo±ci. Innymi sªowy, chcemy zminimalizowa¢ || Ax − b ||
2
=|| e ||
2
.
1
B.Graczyk P.Talerzak
Rzutowanie. Metoda najmniejszych kwadratów.
Je»eli prosta przechodzi przez wszystkie 3 punkty, uzyskamy równania:
1 = C + D
2 = C + 2D
2 = C + 3D
jednak»e, jest to nierozwi¡zywalne. Odpowiada to równaniu Ax = b, gdzie
A =
1 1
1 2
1 3
, x =
"
C
D
#
i b =
1
2
2
Istniej¡ dwa sposoby ogl¡dania tego. W przestrzeni prostej, staramy si¦ znale¹¢
e
1
,e
2
oraz e
3
, które s¡ pionow¡ odlegªo±ci¡ prostej od punktów zamieszczonych na
ukªadzie wspóªrz¦dnych. Skªadniki p
1
,p
2
,p
3
s¡ warto±ciami C + Dt obok ka»dego
punktu; p ≈ b.
Inny sposób to je±li mamy wektor b w trójwymiarowej przestrzeni R
3
, to rzutu-
jemy p na przestrze« kolumnow¡ macierzy A oraz rzutujemy e na N(A
T
)
.
Teraz znajdziemy ˆx =
"
ˆ
C
ˆ
D
#
oraz p. Wiemy, »e:
A
T
Aˆ
x = A
T
− b
"
3
6
6 14
# "
ˆ
C
ˆ
D
#
=
"
5
11
#
Z tego otrzymujemy zwykªe równania:
3 ˆ
C + 6 ˆ
D = 5
6 ˆ
C + 14 ˆ
D = 11
Rozwi¡zujemy to »eby znale¹¢ ˆ
D =
1
2
i C =
2
3
.
Mogli±my tak»e u»y¢ rachunku, by znale¹¢ minimum poni»szej funkcji dwóch
zmiennych:
e
1
2
+ e
2
2
+ e
3
2
= (C + D − 1)
2
+ (C + 2D − 2)
2
+ (C + 3D − 2)
2
Tak i tak, ko«czymy rozwi¡zywa¢ ukªad równa«, by znale¹¢ najbli»sz¡ prost¡ do
naszych punktów, równ¡ b =
2
3
+
1
2
t
.
To daje nam:
i
p
i
e
i
1
7/6
-1/6
2
5/3
1/3
3
13/6
-1/6
Lub p =
7/6
5/3
13/6
i e =
−1/6
2/6
−1/6
. Zauwa»my, »e p i e s¡ ortogonalne, a tak»e,
»e e jest prostopadªe do kolumn macierzy A.
2
B.Graczyk P.Talerzak
Rzutowanie. Metoda najmniejszych kwadratów.
Macierz A
T
A
Podsumowuj¡c, macierz A
T
A jest odwracalna. Czy jest to udowodnione?
Je±li macierz A ma niezale»ne kolumny to A
T
A jest odwracalna.
Aby to udowodni¢ mo»emy zaªo»y¢, »e A
T
Ax = 0 i pokaza¢, »e równanie x = 0
musi by¢ prawdziwe.
A
T
A
x = 0
x
T
A
T
A
x = x
T
0
(A
x)
T
(A
x) = 0
A
x = 0
Poniewa» macierz A ma niezale»ne kolumny, to Ax = 0 tylko wtedy, gdy x = 0.
Dopóki kolumny macierzy A s¡ niezale»ne, mo»emy u»ywa¢ regresji liniowej by
znale¹¢ przybli»one rozwi¡zania dla nierozwi¡zywalnego systemu liniowego ukªadu
równa«. Kolumny macierzy A b¦d¡ niezale»ne, wtedy, gdy b¦d¡ ortonormalne, to
znaczy je±li s¡ one prostopadªymi wektorami jednostkowymi jak
1
0
0
,
0
1
0
i
0
0
1
, lub jak
"
cosθ
sinθ
#
i
"
−sinθ
cosθ
#
3