POLITECHNIKA POZNA‹SKA

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