next up previous
Next: About this document ...

Innfeldisrm og afer minnstu kvarata

2. tgfa

Innfeldisrm eru srstk tegund vigurrma, ar sem er til innfeldi auk hinna lnulegu agera. $\mathbf{R}^n$ er vitanlega vigurrm, me hefbundinni skilgreiningu innfeldi.

Vi hfum huga , hvernig er hgt a lsa (ea sp) vigri mlinga, $\mathbf{y} \in \mathbf{R}^n$ , sem ``bestan'' htt, a gefnum rum mlivigrum, $ \mathbf{x}_1, \mathbf{x}_2, \ldots,
\mathbf{x}_p$. Nnar tilteki viljum vi gera kvaratsummuna


\begin{displaymath}
\vert\vert\mathbf{y} - (b_1 \mathbf{x}_1 + b_2 \mathbf{x}_2 + \ldots + b_p \mathbf{x}_p\vert\vert^2
\end{displaymath} (1)

sem minnsta. Vi munum gera r fyrir v framan af a vigrarnir $\mathbf{x}_1, \ldots, \mathbf{x}_p \in \mathbf{R}^n$ su hir.

Tknum n me $\mathbf{X}$ $n\times p$ fylki, sem hefur $\mathbf{x}_1, \ldots, \mathbf{x}_p$ sem dlkvigra, .e.


\begin{displaymath}
X=\left [ \mathbf{x}_1 \mathbf{x}_2 \ldots \mathbf{x}_p \right ]
\end{displaymath} (2)

og ltum $\mathbf{b}$ vera $p\times 1$ fylki (ea vigurinn) $\left (
b_1, b_2, \ldots, b_p\right )'$.

viljum vi reyna a finna ann vigur $\mathbf{b}$ sem lgmarkar $\vert\vert\mathbf{y}-\mathbf{X} \mathbf{b}\vert\vert^2$.

Minnumst ess, a grunnur fyrir vigurrm er safn vigra, $\mathbf{v}_1,
\mathbf{v}_2, \ldots, \mathbf{v}_p$ sem spanna vigurrmi. Einingargrunnur er grunnur $\mathbf{v}_1,
\mathbf{v}_2, \ldots, \mathbf{v}_p$ sem er annig a hver vigur hefur lengdina einn, .e. $\vert\vert\mathbf{v}_i\vert\vert=1$ $\forall i$.

Minnumst ess a ofanvrp einingarvigra verur einfaldara en ella. Ef $\mathbf{v}$ er einingarvigur og reikna skal ofanvarp vigursins $\mathbf{x}$ $\mathbf{v}$ fst:


\begin{displaymath}
proj_{\mathbf{v}} \left ( \mathbf{x} \right ) = \frac {\math...
...{v} = \left ( \mathbf{x}
\cdot \mathbf{v} \right ) \mathbf{v}.
\end{displaymath} (3)

Nokkur atrii um ofanvrp og grunna

Gram-Schmidt aferin

Ltum $W=span\{\mathbf{x}_1, \ldots, \mathbf{x}_p\}$ vera a hlutrm $\mathbf{R}^n$ sem er spanna af $\mathbf{x}_1, \ldots, \mathbf{x}_p$, .e. $W$ samanstendur af eim vigrum $\mathbf{w}$ sem rita m forminu $\mathbf{w}=b_1 \mathbf{x}_1+ b_2 \mathbf{x}_2 + \ldots +
b_p \mathbf{x}_p$ me einhverju tilteknu vali stulum. etta er jafngilt v a rita megi $\mathbf{w}=\mathbf{X} \mathbf{b}$ fyrir einhvern vigur, $\mathbf{b}$.

m finna (hornrttan) einingargrunn $W$ me svokallari Gram-Schmidt afer. Aferin er annig, a fyrst er notast vi einingarvigur stefnu $\mathbf{x}_1$. Nsti vigur er byggur $\mathbf{x}_2$ en gerur hann annig r gari, a hann veri hornrttur fyrsta vigurinn. etta er gert me v a taka leifina eftir ofanvarp.

1) Ltum $\mathbf{v}_1=\mathbf{x}_1/\vert\vert\mathbf{x}_1\vert\vert$ vera fyrsta einingarvigurinn.

2) Finnum ofanvarp $\mathbf{x}_2$ $\mathbf{v}_1$ og reiknu leif:


\begin{displaymath}
proj_{\mathbf{v_1}} \left ( \mathbf{x_2} \right ) = \left ( \mathbf{x_2}
\cdot \mathbf{v_1} \right ) \mathbf{v_1}.
\end{displaymath} (4)


\begin{displaymath}
\mathbf{r}_1=\mathbf{x}_2-proj_{\mathbf{v_1}}\left ( \mathbf{x_2} \right )
\end{displaymath} (5)


\begin{displaymath}
\mathbf{v}_2=\mathbf{r_1}/\vert\vert\mathbf{r_1}\vert\vert
\end{displaymath} (6)

3) er $\vert\vert\mathbf{v}_1\vert\vert=\vert\vert\mathbf{v}_2\vert\vert=1$, $span\{\mathbf{v}_1,
\mathbf{v}_2\}=span\{\mathbf{x}_1, \mathbf{x}_2\}$ og $\mathbf{v}_1
\perp \mathbf{v}_2$, annig a $\mathbf{v}_1, \mathbf{v}_2$ mynda hornrttan einingargrunn fyrir $span\{\mathbf{x}_1, \mathbf{x}_2\}$

4) Gerum n r fyrir a $\mathbf{v}_1, \ldots, \mathbf{v}_s$ s hornrttur einingargrunnur fyrir $span\{\mathbf{x}_1, \ldots, \mathbf{x}_s\}$. reiknum vi ofanvarp $\mathbf{x}_{s+1}$ $W_s=span\{\mathbf{v}_1, \ldots, \mathbf{v}_s\}$ me jfnunni

\begin{displaymath}
proj_{W_s}(\mathbf{x}_{s+1})=
(\mathbf{x}_{s+1}\cdot \mathbf...
...1 +
\ldots
+ (\mathbf{x}_{s+1}\cdot \mathbf{v}_s)\mathbf{v}_s,
\end{displaymath} (7)

leifina me
\begin{displaymath}
\mathbf{r}_{s+1}=x_{s+1}-proj_{W_s}(\mathbf{x}_{s+1})
\end{displaymath} (8)

og a lokum nsta einingarvigur me
\begin{displaymath}
\mathbf{v}_{s+1}=\mathbf{r}_{r+1}/\vert\vert\mathbf{r}_{r+1}\vert\vert.
\end{displaymath} (9)

annig smum vi hornrttan einingargrunn, $\mathbf{v}_1,
\mathbf{v}_2, \ldots, \mathbf{v}_p$.

Athugasemd: Hr hfum vi nota ann eiginleika hornrtts einingargrunns, $\mathbf{v}_1, \ldots, \mathbf{v}_s$ a ofanvarpi, $proj_{W_s}(\mathbf{x}_{s+1})$ span ess grunns, $W_s=span\{\mathbf{v}_1, \ldots, \mathbf{v}_s\}$, er gefi me $(\mathbf{x}_{s+1}\cdot \mathbf{v}_1)\mathbf{v}_1 +
\ldots
+ (\mathbf{x}_{s+1}\cdot \mathbf{v}_s)\mathbf{v}_s$.

Setning: Ef $W\subseteq \mathbf{R}^n$ er hlutrm og $\mathbf{u}$ er vigur, er til $\mathbf{w} \in W$ .a. a m skrifa $\mathbf{u}=\mathbf{w}+\mathbf{w}^\perp$ ar sem $\mathbf{w}^\perp$ er $\perp$ ll stk $W$. nefnist $\mathbf{w}$ ofanvarp $\mathbf{u}$ $W$, rita $proj_W(\mathbf{u})$.

Snnun: Ltum $\mathbf{v}_1, \ldots, \mathbf{v}_p$ vera einhvern einingargrunn $W$ (etta er alltaf hgt v ekki er unnt a velja meira en $n$ ha vigra r $W$ og ef fundnir eru hir vigrar sem spanna $W$ m sma r eim einingargrunn me Gram-Schmidt afer).

Skilgreinum $\mathbf{w}=
(\mathbf{u}\cdot \mathbf{v_1}) \mathbf{v_1} + \ldots (\mathbf{u}\cdot
\mathbf{v_p}) \mathbf{v_p}$ og $\mathbf{w}^\perp = \mathbf{u} -
\mathbf{w}$.

fst a $\mathbf{w}^\perp$ er $\perp$ $\mathbf{v}_i$ fyrir ll $i$. Srhvert stak $\mathbf{u}$ $W$ er lnuleg samantekt af $\mathbf{v}_1, \ldots, \mathbf{v}_p$ svo $\mathbf{w}^\perp \perp \mathbf{u}$.

Lausn minnstu kvarata vandamlsins

Upphaflega spurningin var: Hvernig m gera $\vert\vert\mathbf{y}-\mathbf{X} \mathbf{b}\vert\vert^2$ sem minnst?

Vi hfum snt a vi getum fundi ofanvarp $\mathbf{y}$ span dlka $\mathbf{X}$, .e. $W=span\{\mathbf{x}_1, \ldots, \mathbf{x}_p\}$, kalla $proj_W(\mathbf{y})$.

gildir a ef $\mathbf{w} \in W$, $\mathbf{w}=\mathbf{X} \mathbf{b}$:


\begin{displaymath}
\mathbf{y} - \mathbf{w} = (\mathbf{y} - proj_W(\mathbf{y}))+(proj_W(\mathbf{y})-\mathbf{w})
\end{displaymath} (10)

og vigrarnir tveir hgra megin jafnaarmerkis eru hornrttir svo um gildir regla Pagorasar:


\begin{displaymath}
\vert\vert\mathbf{y} - \mathbf{w}\vert\vert^2 = \vert\vert\m...
...rt^2 \ge \vert\vert\mathbf{y} - proj_W(\mathbf{y})\vert\vert^2
\end{displaymath} (11)

og v er $proj_W(\mathbf{y})$ nr $\mathbf{y}$ en nokkur annar vigur $W$.

Svar: $\vert\vert\mathbf{y}-\mathbf{X} \mathbf{b}\vert\vert^2$ verur minnst ef $\mathbf{X}
\mathbf{b} = proj_W(\mathbf{y})$.

N er leifin, $\mathbf{y}-proj_W(\mathbf{y})$, hornrtt alla vigra $W$, og ar me lka dlkvigra $X$-fylkisins. a ir a $\mathbf{x}_i \cdot (\mathbf{y}-proj_W(\mathbf{y}))=0$ fyrir ll $i$. En innfeldi m lka rita sem fylkjamargfeldi, svo a $\mathbf{x}_i' (\mathbf{y}-proj_W(\mathbf{y}))=0$ gildir fyrir ll $i$ og v fst lka $\mathbf{X}'(\mathbf{y}-proj_W(\mathbf{y}))=\mathbf{0}$. Munum n, a besti $\mathbf{b}$-vigurinn er annig a $\mathbf{X}
\mathbf{b} = proj_W(\mathbf{y})$.

Vi hfum v snt eftirfarandi: S vigur $\mathbf{b}$ sem gefur $\mathbf{X}\mathbf{b}$ nst $\mathbf{y}$ uppfyllir jfnuhneppi $\mathbf{X}'(\mathbf{y}-\mathbf{X}\mathbf{b})=\mathbf{0}$ og ar me:


\begin{displaymath}
\mathbf{X}'\mathbf{X}\mathbf{b}=\mathbf{X}'\mathbf{y}
\end{displaymath} (12)

essar jfnur eru kallaar normal jfnurnar.




next up previous
Next: About this document ...
Gunnar Stefansson 2000-10-27