EZLAMA
LA · Přednáška 10–11

Projekce a nejmenší čtverce

Ortogonální průmět, Gramova matice, MNČ, ortogonální doplněk.

Ortogonální průmět do podprostoru, metoda nejmenších čtverců přes normální rovnice a ortogonální doplněk.

Zdroj: Přednáška 10–11

14.1Proč se vůbec používá ortogonální projekce

Máš vektor vv, který neleží v daném podprostoru UU (například bod mimo přímku). Potřebuješ najít ten vektor v0∈Uv_0\in U, který je k vv nejblíže.

Tím nejlepším přiblížením je ortogonální průmět v0v_0: rozdíl v−v0v-v_0 je kolmý na celý podprostor.

v0∈U,(v−v0)⊥U.\boxed{v_0\in U,\qquad (v-v_0)\perp U.}

Intuice: z bodu nad přímkou spustíš kolmici na přímku. Pata kolmice je nejbližší bod.

14.2Projekce na přímku generovanou jedním vektorem

Je-li U=span⁡(u)U=\operatorname{span}(u), kde u≠0u\ne0, pak

proj⁡U(v)=(v,u)(u,u)u.\boxed{\operatorname{proj}_U(v)=\frac{(v,u)}{(u,u)}u.}

Postup:

  1. Spočti skalární součin (v,u)(v,u).
  2. Spočti (u,u)(u,u) — druhou mocninu délky uu.
  3. Poděl a výsledek vynásob celým vektorem uu.
  4. Ověř (v−v0,u)=0(v-v_0,u)=0.
Příklad

Příklad krok za krokem

Nechť v=(2,0)v=(2,0) a přímka UU je generovaná u=(1,1)u=(1,1).

(v,u)=2⋅1+0⋅1=2.(v,u)=2\cdot1+0\cdot1=2.

(u,u)=12+12=2.(u,u)=1^2+1^2=2.

v0=22(1,1)=(1,1).v_0=\frac22(1,1)=\boxed{(1,1)}.

Rozdíl v−v0=(1,−1)v-v_0=(1,-1); kontrola (1,−1)⋅(1,1)=0(1,-1)\cdot(1,1)=0.

Navíc délka chyby ∥v−v0∥=2\|v-v_0\|=\sqrt2 je menší než vzdálenost od vv k libovolnému jinému bodu na této přímce.

14.3Projekce do podprostoru s ortogonální bází

Pokud UU má ortogonální bázi (u1,…,uk)(u_1,\ldots,u_k), můžeme projekce jednoduše sečíst:

v0=∑i=1k(v,ui)(ui,ui)ui.\boxed{v_0=\sum_{i=1}^k\frac{(v,u_i)}{(u_i,u_i)}u_i.}

Je-li báze dokonce ortonormální, jmenovatele jsou 1:

v0=∑i=1k(v,ei)ei.\boxed{v_0=\sum_{i=1}^k(v,e_i)e_i.}

Proč: při kolmých bázových vektorech se jednotlivé směry navzájem neovlivňují. V obecné neortogonální bázi se ovlivňují — musíš řešit soustavu.

14.4Projekce při obecné bázi: Gramova matice

Měj bázi U=(u1,…,uk)U=(u_1,\ldots,u_k), vektory nemusí být kolmé. Hledáme

v0=λ1u1+⋯+λkuk.v_0=\lambda_1u_1+\cdots+\lambda_ku_k.

Kolmost rozdílu na každý generátor vyjadřuje

(v−v0,uj)=0pro j=1,…,k.(v-v_0,u_j)=0\quad\text{pro }j=1,\ldots,k.

Po dosazení:

∑i=1kλi(ui,uj)=(v,uj).\sum_{i=1}^k\lambda_i(u_i,u_j)=(v,u_j).

Vznikne soustava

Gλ=c,\boxed{G\lambda=c,}

kde

G=((ui,uj))i,j=1kje Gramova matice,G=\big((u_i,u_j)\big)_{i,j=1}^k\quad\text{je Gramova matice},

c=((v,u1),…,(v,uk))T.c=((v,u_1),\ldots,(v,u_k))^T.

Gramova matice je symetrická; pro lineárně nezávislé uiu_i je regulární a kladně definitní. To znamená, že soustava má právě jedno řešení.

14.5Celý příklad obecné projekce

Chceme promítnout v=(1,0,0)v=(1,0,0) na podprostor

U=span⁡(u1,u2),u1=(1,0,1),u2=(0,1,1).U=\operatorname{span}(u_1,u_2),\quad u_1=(1,0,1),\quad u_2=(0,1,1).

Krok 1: Gramova matice.

(u1,u1)=12+02+12=2,(u_1,u_1)=1^2+0^2+1^2=2,

(u1,u2)=1⋅0+0⋅1+1⋅1=1,(u_1,u_2)=1\cdot0+0\cdot1+1\cdot1=1,

(u2,u2)=02+12+12=2.(u_2,u_2)=0^2+1^2+1^2=2.

G=(2112).G=\begin{pmatrix}2&1\\1&2\end{pmatrix}.

Krok 2: pravá strana.

(v,u1)=1,(v,u2)=0.(v,u_1)=1,\qquad(v,u_2)=0.

c=(10).c=\begin{pmatrix}1\\0\end{pmatrix}.

Krok 3: řeš Gλ=cG\lambda=c.

{2λ1+λ2=1,λ1+2λ2=0.\begin{cases}2\lambda_1+\lambda_2=1,\\\lambda_1+2\lambda_2=0.\end{cases}

Z druhé λ1=−2λ2\lambda_1=-2\lambda_2. Dosadíme do první: −4λ2+λ2=1-4\lambda_2+\lambda_2=1, tedy λ2=−1/3\lambda_2=-1/3 a λ1=2/3\lambda_1=2/3.

Krok 4: sestav projekci.

v0=23(1,0,1)−13(0,1,1)=(2/3,−1/3,1/3).v_0=\frac23(1,0,1)-\frac13(0,1,1) =\boxed{(2/3,-1/3,1/3)}.

Krok 5: kontrola kolmosti.

v−v0=(1/3,1/3,−1/3).v-v_0=(1/3,1/3,-1/3).

(v−v0,u1)=1/3−1/3=0,(v-v_0,u_1)=1/3-1/3=0,

(v−v0,u2)=1/3−1/3=0.(v-v_0,u_2)=1/3-1/3=0.

Obě podmínky platí. Toto je nejbližší vektor z UU k původnímu vv.

14.6Proč průmět minimalizuje vzdálenost

Každý jiný vektor w∈Uw\in U lze porovnat s projekcí v0v_0:

v−w=(v−v0)+(v0−w).v-w=(v-v_0)+(v_0-w).

První člen je kolmý na UU, druhý v UU leží, tedy jsou kolmé. Pythagorova věta:

∥v−w∥2=∥v−v0∥2+∥v0−w∥2≥∥v−v0∥2.\|v-w\|^2=\|v-v_0\|^2+\|v_0-w\|^2\ge\|v-v_0\|^2.

Rovnost nastává jen když w=v0w=v_0. Proto je projekce nejlepší a jednoznačná.

14.7Metoda nejmenších čtverců (MNČ)

Soustava Ax=bAx=b může být neslučitelná: neexistuje xx přesně splňující všechny rovnice. Například chceš proložit přímku několika experimentálními body, které neleží dokonale na přímce.

Namísto přesného řešení hledáme x0x_0, který minimalizuje

∥Ax−b∥2.\boxed{\|Ax-b\|^2.}

To znamená součet druhých mocnin chyb — odtud název nejmenší čtverce.

14.8Normální rovnice

Vektor Ax0Ax_0 je ortogonální projekce bb do sloupcového prostoru AA. Proto chyba r=b−Ax0r=b-Ax_0 musí být kolmá na každý sloupec AA:

AT(b−Ax0)=0.A^T(b-Ax_0)=0.

Upravíme:

ATb−ATAx0=0.A^Tb-A^TAx_0=0.

ATAx0=ATb.\boxed{A^TAx_0=A^Tb.}

Tomu se říká normální rovnice.

Pozor: i když původní Ax=bAx=b nemá řešení, normální rovnice řešení mají. Pokud jsou sloupce AA lineárně nezávislé, je matice ATAA^TA regulární a řešení x0x_0 je jediné:

x0=(ATA)−1ATb.x_0=(A^TA)^{-1}A^Tb.

Pokud jsou sloupce závislé, normální rovnice mohou mít více řešení; všechna dávají stejné nejlepší přiblížení Ax0Ax_0. V numerické praxi bývá vhodnější QR rozklad než přímé počítání (ATA)−1(A^TA)^{-1}, ale ve výuce je vzorec názorný.

14.9Velký příklad: proložení přímky třemi body

Chceme model y≈a+bxy\approx a+bx pro body

(xi,yi)=(0,1),(1,2),(2,2).(x_i,y_i)=(0,1),(1,2),(2,2).

Žádná přímka těmito třemi body neprochází přesně, proto hledáme nejlepší.

Krok 1: matice modelu. Každá rovnice a+bxi≈yia+bx_i\approx y_i dává řádek (1,xi)(1,x_i):

A=(101112),x=(ab),y=(122).A=\begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix},\quad x=\begin{pmatrix}a\\b\end{pmatrix},\quad y=\begin{pmatrix}1\\2\\2\end{pmatrix}.

Krok 2: spočítej ATAA^TA.

ATA=(111012)(101112)=(3335).A^TA=\begin{pmatrix}1&1&1\\0&1&2\end{pmatrix} \begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix} =\begin{pmatrix}3&3\\3&5\end{pmatrix}.

Krok 3: spočítej ATyA^Ty.

ATy=(111012)(122)=(56).A^Ty=\begin{pmatrix}1&1&1\\0&1&2\end{pmatrix}\begin{pmatrix}1\\2\\2\end{pmatrix} =\begin{pmatrix}5\\6\end{pmatrix}.

Krok 4: řeš normální rovnice.

{3a+3b=5,3a+5b=6.\begin{cases}3a+3b=5,\\3a+5b=6.\end{cases}

Odečtením: 2b=12b=1, tedy b=1/2b=1/2. Z první: 3a+3/2=53a+3/2=5 → 3a=7/23a=7/2 → a=7/6a=7/6.

y≈76+12x.\boxed{y\approx\frac76+\frac12x.}

Krok 5: vyhodnoť chyby. Předpovědi jsou 7/6,5/3,13/67/6,5/3,13/6. Odchylky od pozorování jsou −1/6,1/3,−1/6-1/6,1/3,-1/6. Součet jejich čtverců:

136+19+136=16.\frac1{36}+\frac19+\frac1{36}=\frac16.

Kontrola normality chyby: součet odchylek −1/6+1/3−1/6=0-1/6+1/3-1/6=0; součet odchylek násobených hodnotami xix_i: 0+1/3−2/6=00+1/3-2/6=0. To jsou přesně rovnice ATr=0A^Tr=0.

14.10Ortogonální doplněk

Pro podprostor UU euklidovského prostoru VV definujeme

U⊥={v∈V:(v,u)=0 pro kazˇdeˊ u∈U}.\boxed{U^\perp=\{v\in V:(v,u)=0\text{ pro každé }u\in U\}.}

Ortogonální doplněk obsahuje všechny vektory kolmé na celý UU. Je opět podprostorem.

V konečné dimenzi platí

dim⁡U+dim⁡U⊥=dim⁡V.\boxed{\dim U+\dim U^\perp=\dim V.}

Postup

Univerzální postup výpočtu ortogonálního doplňku

  1. Znáš-li bázi u1,…,uku_1,\ldots,u_k prostoru UU, napiš obecný v=(x1,…,xn)v=(x_1,\ldots,x_n).
  2. Sepiš podmínky (v,ui)=0(v,u_i)=0 pro každé ii.
  3. Vyřeš vzniklou homogenní soustavu.
  4. Vektorové řešení přepiš jako obal bázových vektorů U⊥U^\perp.
  5. Zkontroluj dimenzi: dim⁡U⊥=n−dim⁡U\dim U^\perp=n-\dim U.

Příklad:

U=span⁡((1,1,0),(0,1,1))⊂R3.U=\operatorname{span}((1,1,0),(0,1,1))\subset\mathbb R^3.

Nechť v=(x,y,z)v=(x,y,z). Kolmost:

x+y=0,y+z=0.x+y=0,\quad y+z=0.

Zvol y=ty=t, pak x=−t,z=−tx=-t,z=-t.

U⊥=span⁡((−1,1,−1)),dim⁡U⊥=1.\boxed{U^\perp=\operatorname{span}((-1,1,-1)),\quad\dim U^\perp=1.}

Dva generátory UU jsou LN, tedy dim⁡U=2\dim U=2. Kontrola: 2+1=32+1=3.

14.11Časté chyby

  • U projekce máš jmenovatel (u,u)=∥u∥2(u,u)=\|u\|^2, nikoli ∥u∥\|u\|.
  • Pro neortogonální bázi sečteš jednotlivé jednoduché projekce; to obecně nefunguje. Použij Gramovu soustavu.
  • V MNČ zaměníš ATAA^TA a AATAA^T; pro neznámé x∈Rnx\in\mathbb R^n mají normální rovnice rozměr n×nn\times n.
  • Myslíš, že MNČ dává přesné řešení Ax=bAx=b. Obvykle jen minimalizuje chybu.
  • U ortogonálního doplňku ověříš kolmost jen na jednu náhodnou kombinaci, místo na všechny bázové vektory.
  • Výsledný doplněk má dimenzi odporující dim⁡U+dim⁡U⊥=dim⁡V\dim U+\dim U^\perp=\dim V.

Zkouška: nauč se minimálně projekci na přímku, obecnou projekci přes Gramovu matici, normální rovnice MNČ a výpočet ortogonálního doplňku pomocí homogenní soustavy.