Projekce na podprostor

Line´ arn´ı algebra — 10. pˇ redn´ aˇ ska: Ortogonalita II

Dalibor Luk´aˇs

Katedra aplikovan´e matematiky FEI VˇSB–Technick´a univerzita Ostrava

email: dalibor.lukas@vsb.cz http://homel.vsb.cz/∼luk76/LA1

Text byl vytvoˇren v r´amci realizace projektu Matematika pro inˇzen´yry 21. stolet´ı(reg. ˇc. CZ.1.07/2.2.00/07.0332), na kter´em se spoleˇcnˇe pod´ılela Vysok´a ˇskola b´aˇnsk´a – Technick´a univerzita Ostrava a Z´apadoˇcesk´a univerzita v Plzni

Ortogonalita = kolmost

Pythagorova vˇeta: x, y ∈ R² : x⊥y ⇔ kxk² + kyk² = kx + yk²

kxk

kyk kx + yk

kx + yk² = (x + y) · (x + y) = x · x + y · y + 2x · y= kxk² + kyk² + 2x · y

Vektory x a y jsou ortogon´aln´ı(kolm´e), pokud x · y = 0.

Projekce na podprostor

1D

a b

p e

Projekce b na poprostor hai Najdi p := xa : (b − p)⊥a

2D

Projekce b na poprostor ha₁,a₂i

Najdi p := x₁a₁ + x₂a₂ : (b − p)⊥a₁ a (b − p)⊥a₂

Motivace

JPEG komprese je projekce na podprostor

p˚uvodn´ı bitmapa 10% komprese Fourierovou b´az´ı

Metoda nejmenˇ s´ıch ˇ ctverc˚ u = projekce na podprostor

Pˇr´ıklad: Opakovan´ym mˇeˇren´ım pulzu jsme namˇeˇrili hodnoty: 72, 75, 69, 73. Kolik je spr´avn´a hodnota?

Chceme naj´ıt x, kter´e nejv´ıce vyhovuje soustavˇe n´asleduj´ıc´ıch 4 rovnic o 1 nezn´am´e:b (1, 1, 1,1)^T

| {z }

=:A

x = (72, 75, 69, 73)^T

| {z }

=:b

.

Reˇsen´ım jeˇ x, kter´e minimalizuje n´asleduj´ıc´ı eukleidovskou normu chyby ˇreˇsen´ıb kAxb − bk² = (xb − 72)² + (xb − 75)² + (xb − 69)² + (bx − 73)².

Uk´aˇze se, ˇze v´ysledek splˇnuje norm´alovou rovnici A^T · A · xb = A^T · b

a v tomto pˇr´ıpadˇe se jedn´a o aritmetick´y pr˚umˇer (ve statistice ,,stˇredn´ı hodnota”) b

x = 1

4(72 + 75 + 69 + 73) = 72, 25.

Metoda nejmenˇ s´ıch ˇ ctverc˚ u = projekce na podprostor

Pˇr´ıklad: Proloˇzte body (1, 1), (2, 3) a (3,4) nejlepˇs´ı pˇr´ımkou.

Hled´ame parametry a, b ∈ R pˇr´ımky P :=

(x, y) ∈ R² : y(x) := ax + b tak, ˇze n´asleduj´ıc´ı chyba je minimalizov´ana (ve statistice ,,line´arn´ı regrese”)

k(y(1), y(2), y(3)) − (1,3,4)k² = (a · 1 + b − 1)² + (a · 2 + b − 3)² + (a · 3 + b − 4)².

0 1 2 3 4

0 1 2 3 4

5 Uk´aˇze se, ˇze v´ysledek y(x) := (3/2)x − 1/3 splˇnuje norm´alovou rovnici

A^T·A·

ba bb

= A^T·b, kde A :=



1 1 2 1 3 1



, b :=



1 3 4



.

V tomto pˇr´ıpadˇe ˇreˇsen´ıminimalizuje obsahy ˇctverc˚u, odtud n´azev metody.

Ortogon´ aln´ı podprostory

Definice

Podprostory U a V prostoru Rⁿ jsou ortogon´aln´ı, pokud

∀u ∈ U ∀v ∈ V : u · v = 0.

U V

0

U

V

0

Ortogon´ aln´ı podprostory

N(A)⊥R(A)

Mˇejme matici A ∈ R^m×n. Pˇripomeˇnme si jej´ı nulov´y prostor

N(A) := {x ∈ Rⁿ : A · x = 0} = {x ∈ Rⁿ : ∀i ∈ {1, . . . , m} : a^r_i · x = 0} . Vid´ıme, ˇze vektory x z nulov´eho prostoru jsou kolm´e na vˇsechny ˇr´adky matice A, tedy i na jejich libovolnou lin. kombinaci, coˇz jsou prvky z ˇr´adkov´eho prostoru

R(A) := {α₁a^r₁ + · · · + α_ma^r_m : α₁, . . . , α_m ∈ R} = H(A^T).

Analogicky: N(A^T)⊥H(A) nebot’ H(A) = R(A^T).

Ortogon´ aln´ı projektory

1D

a b

p

e Mˇejme a, b ∈ R^m. Projekc´ı vek-

toru b na podprostor hai se rozum´ı

´uloha

Najdi p := xa : (b − p)

| {z }

=e

⊥a.

Uvaˇzujme nyn´ıa, b ∈ R^m×1 jako sloupcov´e vektory. Z definice ortogonality dost´av´ame x = b^T · a

a^T · a, p =

b^T · a a^T · a

a = 1

a^T · a a · a^T

| {z }

=:P

· b

Matice P ∈ R^m×m se naz´yv´a ortogon´aln´ı projektor.

Ortogon´ aln´ı projektory

Ortogon´aln´ı projekce na line´arn´ı obal vektor˚u

Mˇejme a₁, . . . ,a_n ∈ R^m. Ortogon´aln´ı projekc´ı vektoru b ∈ R^m na poprostor ha₁, . . . ,a_ni se rozum´ı ´uloha

Najdi p := x|₁a₁ + · · ·{z + x_na_n}

=A·x

: (b − p)

| {z }

=e

⊥a_i pro kaˇzd´e i ∈ {1, . . . , n},

kde A := (a₁, . . . ,a_m) ∈ R^m×n. Podm´ınka ortogonality 0 = e^T · A = (b − A · x)^T · A vede na norm´alovou rovnici

A^T · A · x = A^T · b,

kter´a m´a jednoznaˇcn´e ˇreˇsen´ı, jsou-li vektory a₁, . . . ,a_n lin. nez´avisl´e. V´ysledn´y vektor p = A · (A^T · A)⁻¹ · A^T

| {z }

=:P

· b,

kde P ∈ R^m×m je ortogon´aln´ı projektor.

Ortogon´ aln´ı projektory

Vlastnosti

Uvaˇzujme line´arnˇe nez´avisl´e sloupce matice A := (a₁, . . . ,a_n) ∈ R^m×n. Ortogon´aln´ı projektor na H(A) je matice (lin. zobrazen´ı)

P = A · A^T · A−1

· A^T a m´a tyto vlastnosti

• P je symetrick´a, tj. P^T = P (plyne ze symetrie A^T · A),

• P je idempotentn´ı (staˇc´ı aplikovat jednou), tj.

P · P =

A · A^T · A−1

· A^T

·

A · A^T · A−1

· A^T

=

= A · A^T · A−1

· A^T · A

| {z }

=I

· A^T · A−1

· A^T= P.

Doplˇnkov´y projektor

Matice I−P je ortog. projektor na ortogon´aln´ı doplnˇek N(A^T). Plat´ı: N(A^T)⊥H(A).

Ortogon´ aln´ı projektory

N(A^T) ⊕ H(A) = Rⁿ

Mˇejme matici A ∈ R^m×n s lin. nez´avisl´ymi sloupci. Uˇz v´ıme, ˇze N(A^T)⊥H(A).

Z Frobeniovy vˇety plyne, ˇze

dimN(A^T) + dimH(A) = n,

a tedy existuje rozklad libovoln´eho vektoru x = y + z, kde y ∈ N(A^T) a z ∈ H(A).

Tento rozklad je jednoznaˇcn´y

x = (I − P) · x

| {z }

∈N(A^T)

+ P| {z }· x

∈H(A)

,

kde P je ortogon´aln´ı projektor na H(A) a I − P je jeho ortogon´aln´ı doplnˇek.

Ortogon´ aln´ı projektory

Norm´alov´a rovnice

Mˇejme matici A := (a₁, . . . ,a_n) ∈ R^m×n s lin. nez´avisl´ymi sloupci a b ∈ R^m. Pokud b 6∈ H(A), pak soustava

A · x = b

nem´a ˇreˇsen´ı. Pˇresto m˚uˇze m´ıt smysl ˇreˇsit n´asleduj´ıc´ı soustavu:

A · xb = P · b, kde P := A · A^T · A−1

· A^T je ortogon´aln´ı projektor na H(A). Jelikoˇz A m´a lin.

nez´avisl´e sloupce, soustava je ekvivalentn´ı norm´alov´e rovnici A^T · A · xb = A^T · b.

Pokud b ∈ H(A), pak P·b = b a norm´alov´a rovnice je ekvivalentn´ı s p˚uvodn´ı. Pokud je nav´ıc A (ˇctvercov´a) regul´arn´ı, pak

P = A · (A^T · A)⁻¹ · A^T = A · A⁻¹

· (A^T)⁻¹ · A^T

= I.

Ortogon´ aln´ı projektory

Pˇr´ıklad: Opakovan´ym mˇeˇren´ım pulzu jsme namˇeˇrili hodnoty: 72, 75, 69, 73. Kolik je spr´avn´a hodnota?

Chceme naj´ıt x, kter´e ,,nejv´ıce” vyhovuje soustavˇe n´asleduj´ıc´ıch 4 rovnic o 1 nezn´am´e:b





 1 1 1 1







| {z }

=:A

·x =





 72 75 69 73







| {z }

=:b

.

Ortogon´aln´ı projekce prav´e strany na H(A) vede na norm´alovou rovnici

(1, 1, 1,1) ·





 1 1 1 1





 · xb = (1,1,1,1) ·





 72 75 69 73





,

coˇz d´av´a ˇreˇsen´ı jako aritmetick´y pr˚umˇer namˇeˇren´ych hodnot xb = 1

4(72 + 75 + 69 + 73)= 72,25.

Ortogon´ aln´ı projektory

Pˇr´ıklad: Proloˇzte body (1, 1), (2, 3) a (3,4) nejlepˇs´ı pˇr´ımkou.

Hled´ame parametry a, b ∈ R pˇr´ımky P :=

(x, y) ∈ R² : y(x) := ax + b , tj. chceme ˇreˇsit soustavu rovnic 

 1 1 2 1 3 1





| {z }

=:A

· a

b

=



 1 3 4





| {z }

=:b

.

Ortogon´aln´ı projekce prav´e strany na H(A) vede na norm´alovou rovnici 1 2 3

1 1 1

·



1 1 2 1 3 1



 · ba

bb

=

1 2 3 1 1 1

·



1 3 4



 ,

jehoˇz ˇreˇsen´ı je

ba = 3/2, bb = −1/3.

Ortogon´ aln´ı projektory

Gram–Schmidt˚uv ortogonalizaˇcn´ı/ortonormalizaˇcn´ı algoritmus

Mˇejme b´azi E := (e₁, . . . ,e_n) prostoru Rⁿ. Ortogonalizujme/ortonormalizujme ji.

f₁ := e₁, q₁ := 1

kf₁kf₁,

f_i := e_i −

Xi−1 j=1

α_ijf_j, kde α_ij = e_i · f_j

f_j · f_j, q_i := 1

kf_ikf_i, pro i ∈ {2, . . . , n}.

V´ysledkem je ortog. b´aze F := (f₁, . . . ,f_n), resp. ortonorm. b´aze Q := (q₁, . . . ,q_n).

Gram–Schmidt˚uv algoritmus pomoc´ı ortogon´aln´ıch projektor˚u Uvaˇzujme vˇsechny vektory jako sloupcov´e, pak pro i ∈ {2, . . . , n}

f_i = e_i −

Xi−1 j=1

e^T_i · f_j

f_j^T · f_j · f_j = e_i −

Xi−1 j=1

1

f_j^T · f_j f_j · f_j^T

| {z }

=:P_j

·e_i=



I −

Xi−1 j=1

P_j



 · e_i.

Metoda nejmenˇ s´ıch ˇ ctverc˚ u = ortogon´ aln´ı projekce prav´ e strany

,,Nejlepˇs´ı” kandid´at na ˇreˇsen´ı minimalizuje normu chyby.

Mˇejme matici A ∈ R^m×n a b ∈ R^m. Pokud b 6∈ H(A), pak soustava A · x = b

nem´a ˇreˇsen´ı. ,,Nejlepˇs´ı” kandid´at bx ∈ Rⁿ na ˇreˇsen´ı minimalizuje normu chyby, tj.

∀y ∈ Rⁿ : kA · bx − bk² ≤ kA · (bx + y) − bk². Nerovnici lze pˇrepsat takto:

0 ≤ y|^T · A{z^T · A · y}

=kA·yk²

+2y^T · A^T · A · bx − 2y^T · A^T · b.

Vezmˇeme lib. vektor z kanonick´e b´aze e_i ∈ Rⁿ, ε > 0 a zvolme dvˇe y := ±εe_i, pak 0 ≤ εkA · vk² ± 2(A^T · A · xb − A^T · b)_i.

Jelikoˇz obˇe nerovnosti plat´ı pro lib. mal´e ε > 0 a libovoln´y index i ∈ {1, . . . , n}, pak A^T · A · xb = A^T · b,

tedy opˇet ˇreˇs´ıme norm´alovou rovnici.

Skal´ arn´ı souˇ cin

Zobecnˇen´ı pojm˚u

Mˇejme vektorov´y prostor V a symetrickou biline´arn´ı formu B : V × V → R, jej´ıˇz pˇr´ısluˇsn´a kvadratick´a forma Q(v) := B(v,v) je pozitivnˇe definitn´ı.

• B je skal´arn´ı souˇcin na V.

• Nenulov´e vektory u,v ∈ V jsou ortogon´aln´ı vzhledem k B, pokud (u,v)_B := B(u, v) = 0.

• B indukuje normu vektoru v ∈ V kvk_B := p

B(u, u).

Pˇr´ıklad: B(x,y) := 2x₁y₁ − x₁y₂ − x₂y₁ + 2x₂y₂ je skal´arn´ı souˇc´ın na R². B je zjevnˇe symetrick´a biline´arn´ı forma. Pˇr´ısluˇsn´a kvadr. forma

Q(x) := B(x,x) = 2(x₁)² − 2x₁x₂ + 2(x₂)² = (x₁)² + (x₂)² + (x₁ − x₂)² > 0 pro x 6= 0, tedy Q je pozitivnˇe definitn´ı.

Skal´ arn´ı souˇ cin

B(p, q) := R₁

0 p(x)q(x)dx je (L2) skal´arn´ı souˇcin na P₁.

Zvolme kanonickou b´azi E := (1, x) prostoru P₁. Matice biline´arn´ı formy je

B_E :=

B(1,1) B(1, x) B(x,1) B(x, x)

=

R1

0 1dx R₁

0 x dx R ₁

0 x dx R₁

0 x² dx

!

=

1 ¹₂

1 2

1 3

.

Biline´arn´ı forma je tedy symetrick´a. Klasifikujme jej´ı matici kongruencemi 1 ¹₂

1 2

1 3

r₂:=−r₁+2r₂

−−−−−−−→

1 ¹₂ 0 ¹₆

s₂:=−s₁+2s₂

−−−−−−−→



1 0 0 1 3



 ,

a jelikoˇz 1, ¹₃ > 0, kvadratick´a forma je pozitivnˇe definitn´ı.

Fourierova b´aze, viz jpeg, je ortonorm´aln´ı v tomto skal´arn´ım souˇcinu.