\input{preamble}

\title{4 - 5 - MER LINEÆRALGEBRA}

\begin{document}
\pagenumbering{gobble}

%primtall

\maketitle

La oss begynne med litt geometrisk fikling.

\begin{oppgave}{1}
    Skriv en rutine som tar inn 
    $A \in \mathbb{R}^{2\times 2}$ 
    og plotter $A\V x$ for alle $\V x$ på enhetssirkelen.
\end{oppgave}

Fikk du til dette, 
vil du oppdage at koden din alltid produserer 
ellipser, 
ihvertfall så lenge $A$ har linært uavhengige kolonner. 
La oss finne ut mer om disse ellipsoidene. 
Trikset er å studere 
$A^TA$ og $AA^T$. 
Vi lar $n > p$,
slik at $A$ er høyt og tynn og $A^T$ er lang og flat. 
Dette er ikke noen essensiell restriksjon, 
men vi gjør den fordi det hjelper litt på visualiseringen.

\begin{oppgave}{2}
    Både
    $A^TA$ og $AA^T$ 
    er ortogonalt diagonaliserbare. 
    Hvorfor?
\end{oppgave}

Siden 
$A^TA$ er ortogonalt diagonaliserbar,
finnes det et ortonormalt sett med egenvektorer. 
La oss sette disse opp i en ortogonal matrise $V$.
Det samme gjelder for $AA^T$; 
la oss sette disse egenvektoren opp i en ortonormal matrise $U$.

\begin{oppgave}{3}
    Hva er dimensjonene til 
    $A^TA$, $AA^T$, $V$ og $U$?\\
    Hvor mange av egenverdiene 
    til $AA^T$ kan være forskjellige fra null?
\end{oppgave}

Her er enda en observasjon.

\begin{oppgave}{4}
    Vis at dersom $\V v$ er 
    en egenvektor til $A^TA$ med egenverdi $\lambda$,
    er $A\V v$ en egenvektor til $AA^T$. 
    Hva er egenverdien? 
    Kan du si noe om fortegnet? 
\end{oppgave}

\clearpage

Hvis du skjønte forrige oppgave, 
skjønner du forhåpentligvis at $A^TA$ og $AA^T$ 
har de samme egenverdiene så
lenge du ser bort fra multiplisiteten til de egenverdiene som er null.
La oss nå anta at $\V v$ er en egenvektor til $A$ med lengde 1.

\begin{oppgave}{5}
    Hva er lengden til $A\V v$?
\end{oppgave}

Lengden til $A\V v$ kalles \textbf{singulærverdi},
og vi bruker bokstaven $\sigma_k$. 
Kolonnene i $U$ og $V$ kalles henholdsvis de \textbf{venstre og høyre singulærvektorene}.
Hvis du tenker nøye på alt du har gjort til nå, 
vil du se at det går an å skrive 
\[
    A = U\Sigma V^T
\]
der $\sigma$-ene sitter i den rektangulære diagonalmatrisen $\Sigma$.
Dette kalles \textbf{SVD-faktoriseringen}\footnote{\url{https://en.wikipedia.org/wiki/Singular_value_decomposition}} 
til $A$. 
Denne finnes alltid, 
og dersom du sorterer singulærverdiene i synkende rekkefølge 
($\sigma_1$ er størst) og velger alle positive,
er $\Sigma$ entydig. 
De unitære matrisene $U$ og $V$ vil ikke nødvendigvis være entydige, 
men de er det i noen tilfeller.

\begin{oppgave}{6}
    Hvordan ser $\Sigma$ ut?
    Finn svd-faktoriseringen til 
    \[
        A=
        \left(\;
        \begin{matrix}
        1 & 0\\  
        0 & 1\\  
        1 & 1 
        \end{matrix}
        \;\right)
    \] 
\end{oppgave}

Singulærverdidekomposisjonen er en av de viktigste matrisefaktoriseringene. 
Har du den har du mye,
og pythonkommandoen heter numpy.linalg.svd.
Nå skal vi se litt på hva svd kan brukes til. 
Det første er kompresjon. 
Vi kan skrive $A$ slik:
\begin{align*}
    A = \sigma_1\V u_1  \V v_1^* + 
    \sigma_2\V u_2  \V v_2^* + 
    \sigma_3\V u_3 \V v_3^* + \cdots +
    \sigma_r\V u_r  \V v_r^* 
\end{align*}
der $r$ er antallet singulærverdier som ikke er null. 
Vi ser nå at dersom det er bare er to av singulærverdiene som er over for eksempel maskinpresisjon, 
er all informasjon i matrisen inneholdt i uttrykket 
\begin{align*}
    A = \V u_1 \sigma_1 \V v_1^* + 
    \V u_2 \sigma_2 \V v_2^*.
\end{align*}

\begin{oppgave}{7}
    La oss lage et bilde av en katt. 
    Lag deg en matrise $A$ i python med tilfeldige tall mellom -1 og 1. 
    Dette er bakgrunnen. 
    Sett så ett element til 10 eller 100 eller noe sånt. 
    Dette er katten.
    Kjør svd på $A$ og skriv ut 
    \begin{align*}
        A - \V u_1 \sigma_1 \V v_1^*  
        \hspace*{10mm}
        \text{og}
        \hspace*{10mm}
        A - \left(\V u_1 \sigma_1 \V v_1^* + 
        \V u_2 \sigma_2 \V v_2^*\right).
    \end{align*}
            
\end{oppgave}



\clearpage


Å jobbe med lineæralgebra til maskinpresisjon på laptopen din 
kan være ganske forskjellig fra å jobbe med penn og papir og platonsk kjærlighet.
Nå skal vi se på dette. 
Du husker forhåpentligvis indreproduktet $(\cdot,\cdot)$. 
Vi sier at lengden 
\[
\| \mathbf x \|=\sqrt{(\mathbf x, \mathbf x)}
\]
er \textbf{indusert} av indreproduktet $(\cdot, \cdot)$.
Men det finnes også lengder som ikke er indusert av et indreprodukt. 
Derfor har vi egne aksiomer for lengde: 
\begin{itemize}
\item $\| \mathbf x \| > 0$ dersom $\mathbf x \neq \mathbf 0$
\item $\| a\mathbf x \| =|a|\| \mathbf x \| $
\item $\| \mathbf x +\mathbf y \|\leq \| \mathbf x \| + \| \mathbf y \|$
\end{itemize}
På fagspråket sier man \textbf{norm} istedet for lengde.
Det finnes mange lengder som ikke er indusert av indreprodukt


\begin{oppgave}{8}
Vis at 
$
\| \mathbf x \|_2=\sqrt{(\mathbf x, \mathbf x)}
$
er en lengde. 
\end{oppgave}

\begin{oppgave}{9}
Vis at 
$
\| \mathbf x \|_\infty = \max_{k} |x_k|
$
og 
$
\| \mathbf x \|_1 = \sum_{k} |x_k|
$
er lengder når $\mathbf x \in \mathbb C^n$. Forklar subskriptene. 
\end{oppgave}

\begin{oppgave}{10}
Alle lengdene over er spesialtilfeller av $p$-normen
\[
\| \mathbf x \|_p=\sqrt[p]{\sum_k |x_k|^p}.
\]
Skisser enhetssirkelen i $\mathbb{R}^2$ for forskjellige valg av $p$.\\
Fun fact: Fontenen på Sergelplassen i Stockholm har form som enhetssirkelen for $p=4$.
\end{oppgave}

Du kan også slenge inn en vektmatrise,
og skrive
$
\| \mathbf x \|=
\| A\mathbf x \|_p.
$

\begin{oppgave}{11}
    Finn en $A$ slik at enhetssirkelen blir en ellipse. 
\end{oppgave}


Dette leder oss inn på
\textbf{matrisenormen indusert av $\|\cdot\|$}:
\[
\|A\|=\max_{\|\mathbf x\|=1} \|A\mathbf x \|
\]

\begin{oppgave}{12}
Vis at dette er en lengde. 
\end{oppgave}
 
Alt etter hva slags norm du putter inn i definisjonen over,
får du forskjellige matrisenormer. 
Heldigvis trenger vi ikke stappe inn masse vektorer i $A$ 
og finne ut hvilken som gjør $A\V x$ lengst, 
for noen har gjort det for oss. 
For eksempel er 
\begin{align*}
    \| A\|_1 = \max_{1\leq k \leq n} \|\V a_k\| 
    \hspace*{10mm}
    \text{($\V a_k$ er kolonne $k$ i $A$)}.
\end{align*}
For $\infty$-normen gjelder det samme,
men med rad $k$ istedet for kolonne $k$.
Det finnes også matriselengder som ikke er indusert av indreprodukt.
Det viktigste eksemplet er kanskje  \textbf{frobeniuslengden}
\[
\|A\|_F=
\sqrt{\left( \sum_{k=1}^{n}\sum_{l=1}^{p} a_{kl}^2 \right)}.
\]
Denne kan også skrives
\[
\|A\|_F
=\text{tr}(A^TA)
=\text{tr}(AA^T).
\]
der tr er noe som kalles \textbf{sporet}. 
Sporet til en matrise er summen av diagonalelementene. 


\clearpage

Den viktigste matrisenormen er normen indusert av det vanlige skalarproduktet,
altså 2-normen. 
Velger vi denne,
blir $\|A\|=\sigma_1$,
altså den største singulærverdien. 

\begin{oppgave}{13}
    Vis dette.
\end{oppgave}

Det er en fun fact of life som ikke er helt triviell å bevise, 
nemlig at antall lineært uavhengige rader og kolonner i en matrise alltid er det samme. 

\begin{oppgave}{14}
    Dobbeltsjekk dette for matrisen 
    \[
        \left(\;
        \begin{matrix}
        1 & 2 & 3 & 4 \\  
        2 & 3 & 4 & 5\\  
        3 & 4 & 5 & 6\\  
        \end{matrix}
        \;\right)
    \] 
\end{oppgave}

Men nå må vi huske på at lineær avhengighet er en platonsk abstraksjon. 
Du finner aldri tre dønn lineært avhengige vektorer i en anvendelse der det er målefeil
og unøyaktigheter og fuglene vet hva. 
Det som i praksis kan skje, 
er derimot at vektorer er \textit{nesten lineært avhengige},
og dette skaper all slags problemer i praksis. 

Så hva vil det si at vektorer er nesten lineært avhengige?
Dette kan skje på to måter. 

\begin{oppgave}{15}
    Gå tilbake til TMA4101 og repeter definisjonen av lineær uavhengighet 
    og finn ut hvordan vektorer kan være nesten lineært uavhengige. 
\end{oppgave}

Tommelfingerregel er at du får problemer når kolonner peker i nesten samme retning 
eller har veldig varierende lengde.
Alt i alt definerer vi derfor noe som kalles kondisjonstall:
\begin{align*}
    \kappa(A)
    = 
    \frac{\sigma_1}{\sigma_r}
\end{align*}
der $\sigma_1$ 
og 
$\sigma_r$ 
er den største og minste singulærverdien. 

\begin{oppgave}{16}
    Vis at dersom $A$ er inverterbar, 
    er 
    \begin{align*}
        \kappa(A)
        =
        \|A\|_2\|A^{-1}\|_2.
    \end{align*} 
\end{oppgave}

For å få en følelse for kondisjonstallet,
er det best å fikle litt med noen matriser.
I python heter det np.linalg.cond.
Problemet med store kondisjonstall,
er at \textit{små endringer i matrisen gir store endringer i annet,
for eksempel egenverdier.}
Dette gjør at modeller kan bli ubrukelige i praksis,
siden små målefeil kan gi store svingninger i hva slags prediksjoner modellen spyr ut. 

\begin{oppgave}{17}
    Regn ut kondisjonstallet til 
    \[
        \left(\;
        \begin{matrix}
        1 & a \\
        b & 1 
        \end{matrix}
        \;\right)
    \] 
    for forskjellige verdier for $a$ og $b$.
    For en illustrasjon av hvordan ting går skeis, 
    kan du prøve å regne ut egenverdier og egenvektorer når $a=1000$ og $b=0$ eller $b=.0001$.
\end{oppgave}



Det finnes et viktig matrisemåletall,
nemlig \textbf{spektralradien}
\begin{align*}
    \rho(A) = \max_k |\lambda_k|.
\end{align*}

\begin{oppgave}{18}
    Vis at dette ikke er en lengde. 
\end{oppgave}





\end{document}
