Line´ arn´ı algebra — 10. pˇ redn´ aˇ ska: Ortogonalita II Dalibor Luk´ aˇ s Katedra aplikovan´e matematiky ˇ FEI VSB–Technick´ a univerzita Ostrava email:
[email protected] http://www.am.vsb.cz/lukas/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´an ˇsk´a – Technick´a univerzita Ostrava a Z´apadoˇcesk´a univerzita v Plzni
Ortogonalita = kolmost Pythagorova vˇ eta: x, y ∈ R2 : x⊥y ⇔ kxk2 + kyk2 = kx + yk2
kx + yk kyk kxk kx + yk2 = (x + y) · (x + y) = x · x + y · y + 2x · y= kxk2 + kyk2 + 2x · y Vektory x a y jsou ortogon´ aln´ı (kolm´e), pokud x · y = 0.
Projekce na podprostor 1D
b
e a p
Projekce b na poprostor hai Najdi p := xa : (b − p)⊥a
2D Projekce b na poprostor ha1, a2i Najdi p := x1a1 + x2a2 : (b − p)⊥a1 a (b − p)⊥a2
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 b, kter´e nejv´ıce vyhovuje soustavˇe n´asleduj´ıc´ıch 4 rovnic o 1 nezn´am´e: (1, 1, 1, 1)T x = (72, 75, 69, 73)T . | {z } | {z } =:A
=:b
ˇ sen´ım je x Reˇ b, kter´e minimalizuje n´asleduj´ıc´ı eukleidovskou normu chyby ˇreˇsen´ı kA x b − bk2 = (b x − 72)2 + (b x − 75)2 + (b x − 69)2 + (b x − 73)2.
Uk´aˇze se, ˇze v´ysledek splˇnuje norm´alovou rovnici
AT · A · x b = AT · b
a v tomto pˇr´ıpadˇe se jedn´a o aritmetick´y pr˚ umˇer (ve statistice ,,stˇredn´ı hodnota”) 1 x b = (72 + 75 + 69 + 73) = 72, 25. 4
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. 2 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)k2 = (a · 1 + b − 1)2 + (a · 2 + b − 3)2 + (a · 3 + b − 4)2.
5
Uk´aˇze se, ˇze v´ysledek y(x) := (3/2)x − 1/3 splˇnuje norm´alovou rovnici 1 1 1 b a AT ·A· b = AT ·b, kde A := 2 1 , b := 3 . b 3 1 4
4
3
2
V tomto pˇr´ıpadˇe ˇreˇsen´ı minimalizuje obsahy ˇctverc˚ u, odtud n´azev metody.
1
0 0
1
2
3
4
Ortogon´ aln´ı podprostory Definice Podprostory U a V prostoru Rn jsou ortogon´ aln´ı, pokud ∀u ∈ U
∀v ∈ V :
u · v = 0.
V
U
V U 0
0
Ortogon´ aln´ı podprostory N (A)⊥R(A) Mˇejme matici A ∈ Rm×n. Pˇripomeˇnme si jej´ı nulov´y prostor N (A) := {x ∈ Rn : A · x = 0} = {x ∈ Rn : ∀i ∈ {1, . . . , m} : ari · 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) := {α1ar1 + · · · + αmarm : α1, . . . , αm ∈ R} = H(AT ). Analogicky: N (AT )⊥H(A) nebot’ H(A) = R(AT ).
Ortogon´ aln´ı projektory 1D
b
e a p
Mˇejme a, b ∈ Rm. Projekc´ı vektoru b na podprostor hai se rozum´ı u´loha Najdi p := xa : (b − p) ⊥a. | {z } =e
Uvaˇzujme nyn´ı a, b ∈ Rm×1 jako sloupcov´e vektory. Z definice ortogonality dost´av´ame T T b ·a 1 b ·a T a·a ·b x= T , p= a= T T a ·a a ·a |a · a {z } =:P
Matice P ∈ Rm×m se naz´yv´a ortogon´ aln´ı projektor.
Ortogon´ aln´ı projektory Ortogon´ aln´ı projekce na line´ arn´ı obal vektor˚ u Mˇejme a1, . . . , an ∈ Rm. Ortogon´aln´ı projekc´ı vektoru b ∈ Rm na poprostor ha1, . . . , ani se rozum´ı u´loha Najdi p := x · · + xna}n : (b − p) ⊥ai pro kaˇzd´e i ∈ {1, . . . , n}, | 1a1 + ·{z | {z } =A·x
=e
kde A := (a1, . . . , am) ∈ Rm×n . Podm´ınka ortogonality
0 = eT · A = (b − A · x)T · A vede na norm´ alovou rovnici AT · A · x = AT · b, kter´a m´a jednoznaˇcn´e ˇreˇsen´ı, jsou-li vektory a1, . . . , an lin. nez´avisl´e. V´ysledn´y vektor T −1 T p = A · (A · A) · A · b, {z } | =:P
kde P ∈ Rm×m je ortogon´ aln´ı projektor.
Ortogon´ aln´ı projektory Vlastnosti Uvaˇzujme line´arnˇe nez´avisl´e sloupce matice A := (a1, . . . , an) ∈ Rm×n . Ortogon´ aln´ı projektor na H(A) je matice (lin. zobrazen´ı) −1 T · AT P=A· A ·A a m´a tyto vlastnosti
• P je symetrick´a, tj. PT = P (plyne ze symetrie AT · A), • P je idempotentn´ı (staˇc´ı aplikovat jednou), tj. −1 −1 T T T T ·A = ·A · A· A ·A P·P= A· A ·A −1 −1 T T T · A ·A · A ·A =A· A ·A · AT = P. | {z } =I
Doplˇ nkov´ y projektor
Matice I−P je ortog. projektor na ortogon´aln´ı doplnˇek N (AT ). Plat´ı: N (AT )⊥H(A).
Ortogon´ aln´ı projektory N (AT ) ⊕ H(A) = Rn Mˇejme matici A ∈ Rm×n s lin. nez´avisl´ymi sloupci. Uˇz v´ıme, ˇze N (AT )⊥H(A). Z Frobeniovy vˇety plyne, ˇze dim N (AT ) + dim H(A) = n, a tedy existuje rozklad libovoln´eho vektoru x = y + z, kde y ∈ N (AT ) a z ∈ H(A). Tento rozklad je jednoznaˇcn´y x = (I − P) · x + P · x, | {z } | {z } ∈N (AT )
∈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 := (a1, . . . , an) ∈ Rm×n s lin. nez´avisl´ymi sloupci a b ∈ Rm. 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: b = P · b, A·x
−1 · AT je ortogon´aln´ı projektor na H(A). Jelikoˇz A m´a lin. kde P := A · A · A nez´avisl´e sloupce, soustava je ekvivalentn´ı norm´ alov´ e rovnici T
b = AT · b. AT · A · x
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 T −1 T −1 T −1 T P = A · (A · A) · A = A · A · (A ) · A = 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 b, kter´e ,,nejv´ıce” vyhovuje soustavˇe n´asleduj´ıc´ıch 4 rovnic o 1 nezn´am´e: 1 72 1 75 ·x = . 1 69 1 73 | {z } | {z } =:A
=:b
Ortogon´aln´ı projekce prav´e strany na H(A) vede na norm´alovou rovnici 72 1 75 1 , b = (1, 1, 1, 1) · (1, 1, 1, 1) · · x 69 1 73 1 coˇz d´av´a ˇreˇsen´ı jako aritmetick´y pr˚ umˇer namˇeˇren´ych hodnot 1 x b = (72 + 75 + 69 + 73)= 72, 25. 4
Ortogon´ aln´ı projektory Pˇ r´ıklad: Proloˇ zte body (1, 1), (2, 3) a (3, 4) nejlepˇ s´ı pˇ r´ımkou. 2 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 1 2 1 · a = 3 . b 3 1 4 | {z } | {z } =:A
=:b
Ortogon´aln´ı projekce prav´e strany na H(A) vede na norm´alovou rovnici 1 1 1 a 1 2 3 1 2 3 b · 3 , · 2 1 · b = 1 1 1 1 1 1 b 4 3 1 jehoˇz ˇreˇsen´ı je
b a = 3/2,
bb = −1/3.
Ortogon´ aln´ı projektory Gram–Schmidt˚ uv ortogonalizaˇ cn´ı/ortonormalizaˇ cn´ı algoritmus Mˇejme b´azi E := (e1, . . . , en) prostoru Rn. Ortogonalizujme/ortonormalizujme ji. f1 := e1,
q1 :=
1 f1, kf1k
i−1 X
1 ei · fj , qi := fi, pro i ∈ {2, . . . , n}. fi := ei + αij fj , kde αij = − f · f kf k j j i j=1 V´ysledkem je ortog. b´aze F := (f1, . . . , fn), resp. ortonorm. b´aze Q := (q1, . . . , qn). Gram–Schmidt˚ uv algoritmus pomoc´ı ortogon´ aln´ıch projektor˚ u Uvaˇzujme vˇsechny vektory jako sloupcov´e, pak pro i ∈ {2, . . . , n} i−1 i−1 i−1 X eT · fj X X 1 i T fi = ei − Pj · ei. · fj = ei − fj · fj ·ei= I − T T f · fj f · fj j=1 j j=1 j=1 |j {z } =:Pj
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 ∈ Rm×n a b ∈ Rm. Pokud b 6∈ H(A), pak soustava A·x=b b ∈ Rn na ˇreˇsen´ı minimalizuje normu chyby, tj. nem´a ˇreˇsen´ı. ,,Nejlepˇs´ı” kandid´at x b − bk2 ≤ kA · (b ∀y ∈ Rn : kA · x x + y) − bk2.
Nerovnici lze pˇrepsat takto:
T T T T T T b 0≤y · A · A · y +2y · A · A · x − 2y · A · b. | {z } =kA·yk2
Vezmˇeme lib. vektor z kanonick´e b´aze ei ∈ Rn, ε > 0 a zvolme dvˇe y := ±εei, pak b − AT · b)i. 0 ≤ εkA · vk2 ± 2(AT · A · x
Jelikoˇz obˇe nerovnosti plat´ı pro lib. mal´e ε > 0 a libovoln´y index i ∈ {1, . . . , n}, pak b = AT · b, AT · A · x
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
p kvkB := B(u, u).
Pˇ r´ıklad: B(x, y) := 2x1y1 − x1y2 − x2y1 + 2x2y2 je skal´ arn´ı souˇ c´ın na R2. B je zjevnˇe symetrick´a biline´arn´ı forma. Pˇr´ısluˇsn´a kvadr. forma Q(x) := B(x, x) = 2(x1)2 − 2x1x2 + 2(x2)2 = (x1)2 + (x2)2 + (x1 − x2)2 > 0 pro x 6= 0, tedy Q je pozitivnˇe definitn´ı.
Skal´ arn´ı souˇ cin B(p, q) :=
R1 0
p(x) q(x) dx je (L2) skal´ arn´ı souˇ cin na P1.
Zvolme kanonickou b´azi E := (1, x) prostoru P1. Matice biline´arn´ı formy je ! R1 R1 1 1 x dx B(1, 1) B(1, x) 1 dx R 01 2 = 1 12 . BE := = R 01 B(x, 1) B(x, x) 2 3 0 x dx 0 x dx
Biline´arn´ı forma je tedy symetrick´a. Klasifikujme jej´ı matici kongruencemi 1 1 1 0 1 2 r2:=−r1+2r2 1 2 s2:=−s1+2s2 1 , −−−−−−−→ −−−−−−−→ 1 1 1 0 6 0 2 3 3 a jelikoˇz 1, 13 > 0, kvadratick´a forma je pozitivnˇe definitn´ı.
Fourierova b´ aze, viz jpeg, je ortonorm´ aln´ı v tomto skal´ arn´ım souˇ cinu.
