Yfirlit

• Línulega óháðir vigrar
• Grunnur
• Gram-Schmidt reiknirit
• Fylki

Línulega háðir vigrar

Mengi af \(n\)-vigrum \(a_1,\ldots,a_k\) er línulega háð ef til eru tölur \(\beta_1,\ldots,\beta_k\), þ.a.

\[ \beta_1 a_1 + \ldots \beta_k a_k = 0 \] og a.m.k ein \(\beta_i \neq 0\).

• Mjög mikilvægt hugtak
• Mengið af vigrunum er línulega háð, ekki hver og einn vigur.
• sama og að segja að eitt \(a_i\) er línuleg samantekt af hinum
• \(\{a_1\}\) er línulega háð ef \(a_1=0\)
• \(\{a_1,a_2\}\) er línulega háð ef einn er margfeldi af hinum
• ef eitthvert \(a_i=0\) er mengið línulega háð
• Við segjum líka að vigrarnir \(a_1,\ldots,a_n\) eru línulega háðir (þegar við meinum í raun mengið)

Línulega óháðir vigrar

Mengi af \(n\)-vigrum \(a_1,\ldots,a_k\) er línulega óháð ef eina lausnin á jöfnunni

\[ \beta_1 a_1 + \ldots \beta_k a_k = 0 \] er \(\beta_1=\ldots=\beta_k = 0\)

• Við segjum að vigrarnir \(a_1,\ldots,a_n\) eru línulega óháðir eða bara óháðir
• Andstæðan við línulega háðir

• Það er ekki hægt að skrifa neitt \(a_i\) sem línulega samantekt af hinum vigrunum.

• Dæmi: einingavigrarnir \(e_1,\ldots,e_n\) eru línulega óháðir.

Línuleg samantekt óháðra vigra

Ef \(a_1,\ldots,a_k\) eru óháðir vigrar og \(x\) er línuleg samantekt af þeim, þ.e.

\[ x = \beta_1 a_1 + \ldots + \beta_k a_k \]

þá eru stuðlarnir \(\beta_i\) ákvarðaðir. Það er ef til eru stuðlar \(\gamma_i\) þ.a.

\[ x = \gamma_1 a_1 + \ldots + \gamma_k a_k \]

þá er \(\gamma_i = \beta_i\) fyrir \(i=1,\ldots,k\).

• þetta þýðir að það er bara ein leið til að skrifa \(x\) sem línulega samantekt og við getum fundið stuðlana.
• sönnunnin byggist á að nota \(x-x=0\) og skrifa \(x\) á tvo vegu \[ (\beta_1-\gamma_1)a_1 + \ldots + (\beta_k - \gamma_k)a_k = 0 \] svo eina lausnin er ef allir stuðlar eru \(0\) þ.e. \(\beta_i=\gamma_i\)

Mesti fjöldi óháðra vigra

Ef \(a_1,\ldots,a_k\) eru línulega óháðir vigrar þá gildir \(k\le n\).

• Mengi af línulega óháðum \(n\)-vigrum getur í mesta lagi verið af stærð \(n\)
• Sönnun í bók, byggist á þrepun yfir víddina.
• Mengi af \(n\)-vigrum af stærð \(\ge n+1\) er alltaf línulega háð.

Grunnur

Mengi af \(n\) línulega óháðum \(n\)-vigrum \(a_1,\ldots,a_n\) er kallað grunnur.

Sérhvern \(n\)-vigur \(b\) er hægt að skrifa sem línulega samantekt af þeim

\[ b = \alpha_1 a_1 + \ldots + \alpha_n a_n \]

• stuðlarnir \(\alpha_i\) eru ótvírætt ákvarðaðir
• kallað framsetning á \(b\) í grunninum \(a_1,\ldots,a_n\)
• Einingavigrarnir \(e_1,\ldots,e_n\) mynda grunn.
• Höfum séð útvíkkunina fyrir \(x\) í grunninum \[ x = x_1 e_1 + \ldots + x_n e_n \]
• Fyrir aðra grunna verða stuðlarnir ekki jafn augljósir

Hornréttir vigrar

Mengi af \(n\)-vigrum \(a_1,\ldots, a_k\) eru innbyrðis hornréttir ef \(a_i^Ta_j = 0\) fyrir \(i\neq j\).

• staðlaðir ef \(||a_i|| = 1\) fyrir \(i=1,\ldots,k\)
• þverstaðlað (e. orthonormal) ef bæði skilyrðin gilda
• þverstaðlað mengi af vigrum er línulega óháð
• því gildir \(k\le n\)
• þegar \(k=n\) mynda \(a_1,\ldots,a_n\) þverstaðlaðan grunn

Þverstöðluð útvíkkun

Ef \(a_1,\ldots,a_n\) er þverstaðlaður grunnur þá er einfalt að finna stuðlana fyrir framsetninguna

\[ x = (a_1^Tx)a_1 + \ldots + (a_n^Tx)a_n \]

Til að sanna formúluna þarf bara að taka innfeldið við \(a_i\)

Reiknirit fyrir línulega óháða vigra

• við þurfum reiknirit sem getur ákvarðað hvort \(a_1,\ldots,a_k\) eru línulega óháðir
• ef þeir eru ekki óháðir þá viljum við finna einn vigur sem er línuleg samantekt af hinum
• Gram-Schmidt reikniritið leysir þetta vandamál og hefur mörg önnur notagildi.

Gram-Schmidt

Látum \(a_1,\ldots,a_k\) vera \(n\)-vigra

Fyrir \(i=1,\ldots,k\)

1. Hornrétt: látum \(\tilde{q}_i = a_i - (q_1^Ta_i)q_1 - \ldots - (q^T_{i-1}a_i)q_{i-1}\)
2. Háðir?: ef \(\tilde{q}_i = 0\), þá hættum við
3. Stöðlun: \(q_i = \tilde{q_i}/||\tilde{q_i}||\)

• Ef reikniritið hættir ekki í skrefi 2. þá eru \(a_1,\ldots,a_k\) línulega óháðir
• Ef reikniritið hættir í skrefi 2. þá er \(a_i\) línuleg samantekt af \(a_1,\ldots,a_{i-1}\)

Gram-Schmidt reikniritið

• Inntak \(n\)-vigrar \(a_1,\ldots,a_k\)
• Úttak \(n\)-vigrar \(q_1,\ldots,q_k\), ef það hættir ekki snemma
• \(q\) vigrarnir eru þverstaðlaðir
• \(a_i\) er línuleg samantekt af \(q_1,\ldots,q_i\)
• \(q_i\) er línuleg samantekt af \(a_1,\ldots,a_i\)
• Þarf ca. \(2nk^2\) reikniaðgerðir. Ef \(k=n\) verður þetta \(2n^3\) aðgerðir.

Fylki

Fylki er kassi af tölum, t.d.

\[ \begin{bmatrix} 0 & 1 & -2 & 0.2\\ 1.4 & 0 & -1 & 10\\ 3.1 & -1 & 4 & 5 \end{bmatrix} \]

• stærðin er gefin með (fjöldi raða)\(\times\)(fjöldi dálka), fylkið að ofan er t.d. \(3\times4\) fylki
• tölurnar eru kallaðar stök
• \(B_{i,j}\) er stak/tala í fylkinu \(B\)
• röðin er \(i\) og dálkurinn er \(j\), byrjum að telja í 1 eins og með vigra.
• tvö fylki eru eins ef þau eru jafnstór og öll samsvarandi stök eru þau sömu.

fylki og vigrar

\(m\times n\) fylki \(A\) er

• mjótt ef \(m > n\)
• breitt ef \(m < n\)
• ferningslaga ef \(m=n\)
• \(n\times 1\) fylki samsvarar \(n\)-vigri
• \(1\times 1\) fylki samsvarar tölu
• \(1\times n\) er kallað línuvigur, t.d \[ \begin{bmatrix} 1 & 4 & -2 & 5\end{bmatrix} \] sem er ekki eins og (dálk) vigurinn \[\begin{bmatrix} 1 \\ 4 \\ -2 \\ 5\end{bmatrix}\]

Dálkar og raðir í fylki

Látum \(A\) vera \(m\times n\) fylki með stök \[ A_{i,j}, \qquad i=1,\ldots,m, \quad j=1,\ldots,n \]

• \(j\)-ti dálkvigurinn er \(m\)-vigurin \[\begin{bmatrix} A_{1,j}\\ \vdots \\ A_{m,j} \end{bmatrix} \]

• \(i\)-ti línuvigurinn er \[ \begin{bmatrix} A_{i,1} & \cdots & A_{i,n} \end{bmatrix} \]

Blokkfylki

Rétt eins og við stöflum upp vigrum getum við búið til blokkfylki eins og t.d.

\[ A = \begin{bmatrix}B & C \\ D & E\end{bmatrix} \] Þar sem \(B,C,D,E\) eru fylki

• \(B,C,D,E\) eru hlutfylki eða blokkir í \(A\)
• fylki í sömu röð verða að hafa sama fjölda raða
• fylki í sama dálk verða að hafa sama fjölda dálka

Dálkar og raðir fylkja

Ef \(A\) er \(m\times n\) fylki þá getum við skrifað það sem blokkfylki af dálkunum \(a_1,\ldots,a_n\)

\[ A = \begin{bmatrix}a_1 & a_2 & \cdots & a_n\end{bmatrix} \]

eða sem blokkfylki af röðunum \(b_1,\ldots,b_m\)

\[ A = \begin{bmatrix}b_1 \\ b_2 \\ \vdots \\ b_m \end{bmatrix} \]

Dæmi um fylki

• myndir, \(X_{i,j}\) er pixel \((i,j)\) í svart-hvítri mynd
• einkunnir, \(A_{i,j}\) er einkunn nemanda \(i\) fyrir dæmi \(j\)
• eiginleika fylki, \(X_{i,j}\) er gildi á eiginleika \(i\) fyrir hlut \(j\).
• net, \(G_{i,j}\) er 1 ef það er leggur frá hnúti \(i\) til \(j\), \(0\) annars

Sérstök fylki

• \(m\times n\) fylkið með öll stök núll, er kallað \(0_{m\times n}\) eða bara \(0\)
• \(I\) einingafylkið er ferningslaga fylki \(I_{i,i} = 1\) og \(I_{i,j} = 0\) ef \(i\neq j\), t.d.

\[ \begin{bmatrix}1 & 0 \\ 0 & 1 \end{bmatrix}, \qquad \begin{bmatrix}1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix} \]

• Fylki er kallað strjált ef mörg stök eru \(0\).
• \(0\) og \(I\) eru dæmi um strjál fylki.
• Þurfum minna minni til að geyma þau og ýmsar aðgerðir eru hraðvirkari
• \(nnz(A)\) er fjöldi staka sem er ekki \(0\).

Hornalínu og þríhyrningsfylki

• hornalínufylki er ferningslaga fylki með \(A_{i,j} = 0\) ef \(i\neq j\)
• \(diag(a_1,\ldots,a_n)\) er hornalínufylki með \(A_{i,i}=a_i, i=1,\ldots,n\)
• neðra þríhyrningsfylki ef \(A_{i,j} = 0\), fyrir \(i < j\)
• efra þríhyrningsfylki ef \(A_{i,j} = 0\), fyrir \(i > j\)

Bylt fylki

Byltan af \(m\times n\) fylkinu \(A\), táknað \(A^T\) er skilgreind sem \(n\times n\) fylkið \[ (A^T)_{i,j} = A_{j,i}, \qquad i=1,\ldots,n, \quad j=1,\ldots,m \]

Í bylta fylkinu verða dálkar að röðum og öfugt.

Margföldun og samlagning

• Summan skilgreind eins og fyrir vigra, fylkin verða að vera af sömu stærð \[ (A+B)_{i,j} = A_{i,j} + B_{i,j} \]

• margföldun með tölu \[ (\alpha A)_{i,j} = \alpha \cdot A_{i,j} \]

• margir eiginleikar sem leiða beint af þessum skilgreiningum
• \(A+B = B + A\)
• \(\alpha(A+B) = \alpha A + \alpha B\)
• \((A+B)^T = A^T + B^T\)

• \((A^T)^T = A\)

Fylki í numpy

Sjá python notebook f8.ipynb

Margföldun fylkja og vigra

Fyrir \(m\times n\) fylki \(A\) og \(n\)-vigur \(x\) skilgreinum við fylkjamargföldunina \(y=Ax\) sem

\[y_i = A_{i,1}x_1 + \ldots + A_{i,n}x_n, \quad i=1,\ldots,m\]

• Ef \(A\) hefur raðirnar \(b_1^T,\ldots,b_m^T\) þá er \[y_i = b_i^Tx\]

• \(y=Ax\) er í raun mörg innfeldi á milli raða \(A\) og vigursins \(x\)

Dálktúlkun

\(y=Ax\) má skrifa sem

\[ y = x_1a_1 + x_2a_2 + \ldots + x_na_n \] þar sem \(a_1,\ldots,a_n\) eru dálkar \(A\).

• \(y=Ax\) er línuleg samantekt af dálkum \(A\) með stuðlana \(x_1,\ldots,x_n\).
• mikilvægt dæmi: \(Ae_j = a_j\)
• dálkar \(A\) eru línulega óháðir ef \(Ax=0\) leiðir til þess að \(x=0\).

Dæmi

• \(X = [x_1 \cdots x_N]\) er \(n\times N\) gagnafylki
• dálkur \(x_j\) er \(n\)-vigur sem lýsir hlut \(j\)
• \(X_{i,j}\) er gildið á eiginleika \(i\) fyrir hlut \(j\)
• \(n\)-vigurinn \(w\) eru vigtir
• \(s = X^Tw\) er \(N\)-vigur af útkomum fyrir hvern hlut \(s_j = x_j^Tw\)

Varpanir

• Margar varpanir í tví- og þrívídd er hægt að setja fram sem margföldun \(y = Ax\)
• Snúningur um hornið \(\theta\) \[ y = \begin{bmatrix}\cos(\theta) & -\sin(\theta) \\ \sin(\theta) & -\cos(\theta)\end{bmatrix} x \]
• snúningur í þrívídd um vigur er mun flóknari

Línuleg föll

Útvíkkum skilgreininguna á línulegum föllum til að leyfa niðurstöðunni að vera vigur

\(f: \mathbf{R}^n \to \mathbf{R}^m\) er vörpun/fall frá \(n\)-vigrum til \(m\)-vigra.

• skrifum \(f(x) = (f_1(x),\ldots,f_m(x))\) til að lýsa stökunum í útkomunni \(f(x)\)
• skrifum \(f(x_1,\ldots,x_n)\) til að lýsa stökunum í inntakinu \(x\)
• fallið \(f\) er línulegt ef fyrir öll \(x,y,\alpha,\beta\) gildir \[ f(\alpha x + \beta y) = \alpha f(x) + \beta f(y) \]
• jafngildir því að öll föllin \(f_1,\ldots,f_m\) eru línuleg

Ef \(A\) er \(m\times n\) fylki skilgreinum við \(f\) sem \(f(x) = Ax\)

• Öll slík föll, \(f\), eru línuleg
• Ef \(f\) er eitthvert línulegt fall \(f: \mathbf{R}^n \to \mathbf{R}^m\), þá er til \(m\times n\) fylki \(A\) þ.a. \(f(x) = Ax\)
• \(f(x) = x_1f(e_1) + \ldots + x_nf(e_n)\) svo að \[ A = \begin{bmatrix}f(e_1) & f(e_2) & \cdots & f(e_n)\end{bmatrix} \]

Línuleg jöfnuhneppi

mengi af \(m\) línulegum jöfnum í \(n\) breytum \(x_1,\ldots,x_n\)

\[ \begin{aligned} A_{11} x_1 + A_{12}x_2 + \ldots + A_{1n}x_n &= b_1\\ A_{21} x_1 + A_{22}x_2 + \ldots + A_{2n}x_n &= b_2\\ &\vdots\\ A_{m1} x_1 + A_{m2}x_2 + \ldots + A_{mn}x_n &= b_m\\ \end{aligned} \]

• \(n\)-vigurinn \(x\) eru óþekktu stærðirnar
• \(A_{i,j}\) eru stuðlarnir og \(A\) er stuðlafylkið
• \(b\), \(m\)-vigurinn er kallaður "hægri hliðin"
• Táknað sem \(Ax=b\)

Línuleg jöfnuhneppi

Línulega jöfnuhneppið \(Ax=b\) þar sem \(A\) er \(m\times n\) fylki, \(b\) er \(m\)-vigur og \(x\) er \(n\)-vigur er kallað

• vanákvarðað ef \(m < n\) (A er breitt)
• ferningslaga ef \(m=n\) (A ferningslaga)
• ofákvarðað ef \(m > n\) (A er mjótt)
• \(x\) er kallað lausn ef það uppfyllir \(Ax=b\)

• Það er háð \(A\) og \(b\) hvort til sé

  • engin lausn
  • nákvæmlega ein lausn
  • óendanlega margar lausnir

Fyrir næstu viku

Klára kafla 8, sleppum kafla 9 og byrjum á kafla 10.