<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\input{preamble}

\title{4 - 6 - OM DÃ˜DSLENGSEL}

\begin{document}
\pagenumbering{gobble}


\maketitle


\begin{oppgave}{1}
    Anta at vi har to funksjoner $f(x,y)$ og $g(x,y)$. Vi leter etter et punkt $(a,b)$ slik at bÃ¥de 
    \begin{equation*}
        f(a,b)=0 
        \quad \text{og} \quad
        g(a,b)=0.
        \end{equation*}
        likningene 
        \begin{equation*}
        f(x,y)=0 
        \quad \text{og} \quad 
        g(x,y)=0 
        \end{equation*}
        angir nivÃ¥kurver for funksjonene $f$ og $g$. Punktet $(a,b)$ mÃ¥ ligge pÃ¥ skjÃ¦ringspunktet mellom disse.
         \begin{center}
            \begin{tikzpicture}[thick]
              \draw[blue] (-2,0) circle (2cm) node[right,xshift=1cm,yshift=2cm]{$f(x,y)=0$};
              \draw[red] (0,-1) circle (1.5cm) node[right,xshift=1.5cm,yshift=0cm]{$g(x,y)=0$};
              \node[below right] at (-.3,.7){$\circ$};
              \node[below right] at (0,1.2){$(a,b)$};
                  \draw[-&gt;] (-3.5,0) -- (2.5,0) node[right]{$x$};
                  \draw[-&gt;] (-2.5,-1) -- (-2.5,1.3) node[above]{$y$};
            \end{tikzpicture}
          \end{center}
        Anta at du har en iterasjon $(x_n,y_n)$. Vi setter opp tangentplanene til $f$ og $g$ i $(x_n,y_n)$
        \begin{align*}
        z-f(x_n,y_n)&amp;= f_x(x_n,y_n)(x-x_n)+f_y(x_n,y_n)(y-y_n) \\[5pt]
        z-g(x_n,y_n)&amp;= g_x(x_n,y_n)(x-x_n)+g_y(x_n,y_n)(y-y_n).
        \end{align*}
        Hvis vi krever at $z=0$, fÃ¥r vi likninger for skjÃ¦ringslinjene mellom disse tangentplanene og $(x,y)$-planet 
        \begin{align*}
        -f(x_n,y_n)&amp;= f_x(x_n,y_n)(x-x_n)+f_y(x_n,y_n)(y-y_n) \\[5pt]
        -g(x_n,y_n)&amp;= g_x(x_n,y_n)(x-x_n)+g_y(x_n,y_n)(y-y_n).
        \end{align*}
        Iterasjonen $(x_{n+1},y_{n+1})$ defineres som skjÃ¦ringen mellom disse linjene.
         \begin{center}
            \begin{tikzpicture}[thick]
              \draw[blue] (-2,0) circle (2cm) ;
              \draw[red] (0,-1) circle (1.5cm);
              \node[below right] at (0,1.2){$(a,b)$};
               \node[below right] at (-.3,.7){$\circ$};
              \draw[green] (-.6,4) -- (2.6,-1);
               \draw[green](4,-.6) -- (-1,3);
        
              \node[below right] at (1,2.2){$(x_{n+1},y_{n+1})$};
               \node[below right] at (.73,1.78){$\circ$};
        
        
              \node[below right] at (2.3,3.2){$(x_n,y_n)$};
               \node[below right] at (2,3){$\circ$};
                  \draw[-&gt;] (-3.5,0) -- (2.5,0) node[right]{$x$};
                  \draw[-&gt;] (-2.5,-1) -- (-2.5,1.3) node[above]{$y$};
            \end{tikzpicture}
          \end{center}
        AltsÃ¥ er 
        \begin{align*}
        -f(x_n,y_n)&amp;= f_x(x_n,y_n)(x_{n+1}-x_n)+f_y(x_n,y_n)(y_{n+1}-y_n) \\[5pt]
        -g(x_n,y_n)&amp;= g_x(x_n,y_n)(x_{n+1}-x_n)+g_y(x_n,y_n)(y_{n+1}-y_n),
        \end{align*}
        et lineÃ¦rt likningssystem som definerer $(x_{n+1},y_{n+1})$. Matrisen er 
        \begin{equation*}
         \begin{pmatrix} &amp; f_x(x_n,y_n) &amp; f_y(x_n,y_n) &amp;  \\ &amp; g_x(x_n,y_n) &amp; g_y (x_n,y_n) &amp;   \end{pmatrix}
        \end{equation*}
        og vi skriver
        \begin{align*}
        -\begin{pmatrix}  \, f(x_n,y_n) \,   \\ \,  g(x_n,y_n) \,    \end{pmatrix} =   \begin{pmatrix}  f_x(x_n,y_n) &amp; f_y(x_n,y_n)   \\  g_x(x_n,y_n) &amp; g_y (x_n,y_n)   \end{pmatrix}   \begin{pmatrix}  \, x_{n+1}-x_n\,  \\ \,  y_{n+1}-y_n \,   \end{pmatrix}.
        \end{align*}
        NÃ¥ kan vi gange med 
        \begin{equation*}
         \begin{pmatrix}  f_x(x_n,y_n) &amp; f_y(x_n,y_n)  \\  g_x(x_n,y_n) &amp; g_y (x_n,y_n)   \end{pmatrix} ^{-1}
        \end{equation*}
        fra venstre, legge til $(x_n,y_n)$ pÃ¥ begge sider, og fÃ¥ Newtons metode for systemer 
        \begin{align*}
          \begin{pmatrix}  \, x_{n+1}\,  \\ \,  y_{n+1} \,   \end{pmatrix}  &amp;= \begin{pmatrix}  \, x_n\,   \\ \,  y_n \,   \end{pmatrix}  -\begin{pmatrix}  f_x(x_n,y_n) &amp; f_y(x_n,y_n) \\  g_x(x_n,y_n) &amp; g_y (x_n,y_n)   \end{pmatrix}^{-1}  \begin{pmatrix}  \, f(x_n,y_n) \,   \\ \,  g(x_n,y_n) \,    \end{pmatrix}.
        \end{align*}
        For lesbarhetens skyld lot jeg vÃ¦re Ã¥ skrive ut hva 
        \begin{equation*}
         \begin{pmatrix} &amp; f_x(x_n,y_n) &amp; f_y(x_n,y_n) &amp; \\ \\ &amp; g_x(x_n,y_n) &amp; g_y (x_n,y_n) &amp; \\  \end{pmatrix} ^{-1}
        \end{equation*}
        er, men du kan regne det ut ved Ã¥ huske fra lineÃ¦ralgebraen at 
        \begin{equation*}
        \begin{pmatrix} a &amp; b \\ c &amp; d \end{pmatrix}^{-1}=\frac{1}{ad-bc}\begin{pmatrix} d &amp; -b \\ -c &amp; a \end{pmatrix}.
        \end{equation*}
        Skrevet litt mer kompakt blir dette
        \begin{align*}
            \V x_{n+1}
            = 
            \V x_{n}
            - 
            \V f'(\V x_n)^{-1}
            \V f(\V x_n).
        \end{align*}
\end{oppgave}

\begin{oppgave}{2}
    Her er rustkode for denne og oppgave 7 (laga dem i en smell for sammenlikning):\\
    \url{https://folk.ntnu.no/mortano/rust/optimering/}
\end{oppgave}



\begin{oppgave}{3}
    Det er jo fordi gradienten er null i et kritisk punkt. 
    Hvis du partiellderiverer
    \begin{align*}
        V(x,y)=x^3 + x^2y + xy^2 + 2y^3 - x^2 - y^2 - xy- x -y.
    \end{align*}
    og setter begge lik null, 
    fÃ¥r du likningsssettet i oppgave 2. 
\end{oppgave}


\begin{oppgave}{4}
    Formelen 
    \begin{align*}
        \V x_{n+1}
        = 
        \V x_{n}
        - 
        V''(\V x_n)^{-1}
        V' (\V x_n)
    \end{align*}
    er den samme som Newtons metode, 
    bare med $V' = \V f$.
\end{oppgave}

\begin{align*}
    \V x_{n+1}
    = 
    \V x_{n}
    + 
    \alpha_n \V p_n
\end{align*}

\begin{oppgave}{5}
    Du hiver deg selvfÃ¸lgelig rett utfor sÃ¥ bratt som overhodet mulig. 
\end{oppgave}

\begin{oppgave}{6}
    NÃ¥r du velger en retning $p_n$ er det sikkert lurt Ã¥ dra ned til 
    bunnpunktet pÃ¥ kursen du staker ut. 
    Eller er det det? 
    Ikke nÃ¸dvendigvis, 
    faktisk. 
    Det er ofte like greit Ã¥ stoppe litt fÃ¸r og finne en ny retning. 
\end{oppgave}

\begin{oppgave}{7}    
    \url{https://folk.ntnu.no/mortano/rust/optimering/}
\end{oppgave}

\begin{oppgave}{8}    
    Funksjonen
    \begin{align*}
        V(\V x) =
        \|A\V x - \V b\|^2
    \end{align*}
    er aldri negativ, 
    og mÃ¥ler avstanden mellom $A\V x$ og $\V b$. 
    Avstanden skal vÃ¦re null om $A\V x = \V b$ har entydig lÃ¸sning, 
    og minst mulig ved overbestemte systemer, 
    for eksempel ved regresjon. 
    Dersom du har underbestemte systemer, 
    finnes det gjerne mange $\V x$ som gir $V(\V x) = 0$. 
\end{oppgave}

\begin{oppgave}{9}    
    La oss begynne med Ã¥ derivere $\V x^T A \V x$. 
    Her mÃ¥ man holde tungen beint i munnen. 
    Det er best Ã¥ skrive 
    \begin{align*}
        \V x^T A \V x = \hspace*{2mm}
        \begin{matrix}
            a_{11}x_1x_1 + a_{12} x_1x_2 + \cdots + a_{1n}x_1x_n \\[2mm]
            a_{21}x_2x_1 + a_{12} x_2x_2 + \cdots + a_{2n}x_2x_n \\[2mm]
            \vdots \\[2mm]
            a_{n1}x_nx_1 + a_{n2} x_nx_2 + \cdots + a_{nn}x_nx_n 
        \end{matrix}
    \end{align*}
    Den deriverte av denne er rekkevektoren 
    \begin{align*}
        \nabla \V x^T A \V x &amp;= \hspace*{2mm}
        \begin{matrix}
            (2a_{11}x_1 + \left(  a_{12} + a_{21} \right) x_2 + \cdots + \left(  a_{1n} + a_{n1} \right)x_n, \\[2mm]
            \left(  a_{21} + a_{12} \right)x_1 + 2a_{22}x_2 + \cdots + \left(  a_{2n} + a_{n2} \right)x_n, \\[2mm]
            \vdots \\[2mm]
            \left(  a_{n1} + a_{1n} \right)x_1 +\left(  a_{n2} + a_{2n} \right)x_2 + \cdots + 2a_{nn}x_n )
        \end{matrix}
        \\[4mm]&amp;= 
        \V x^T\left( A + A^T \right)
        \\[4mm]&amp;= 
        2\V x^TA 
    \end{align*}
    Dersom $\V x $ er en sÃ¸ylevektor,
    fÃ¥r vi altsÃ¥  
    \begin{align*}
        \nabla V(\V x) = \V x^TA-\V b^T = \left( A\V x-\V b \right)^T
    \end{align*}
    som har entydig nullpunkt i $A^{-1}\V b$ siden $A$ er positivt definitt, 
    og dermed er inverterbar siden ingen av egenverdiene kan vÃ¦re null.
    Hessematrisen blir bare $A$, 
    og siden denne er positivt definitt mÃ¥ det kritiske punktet vÃ¦re et minimumspunkt. 
\end{oppgave}


\begin{oppgave}{10}
    La 
    \[
        V\left( \V x \right) = \V x^T A \V x - \V x^T \V b.
    \] 
    Vi bruker kjerneregelen og setter lik null:
    \begin{align*}
        \frac{d}{d\alpha_n}V(\V x_n + \alpha_n \V p_n) 
        &amp;=
        \nabla V(\V x_n + \alpha_n \V p_n)^T \V p_n \\
        &amp;=
       \left( A\left( \V x_n + \alpha_n \V p_n \right)-\V b  \right)^T \V p_n= 0
    \end{align*}
    som gir 
    \begin{align*}
        \alpha_n =  
       \frac{\left(\V b - A\V x_n   \right)^T \V p_n}{\V p_n^T A \V p_n}.
    \end{align*}
    Dette kan gjÃ¸res for generelle andreordens polynomer, 
    men vi skal bare studere denne, 
    sÃ¥ jeg plager deg ikke med det generelle tilfellet. 
\end{oppgave}



\begin{oppgave}{11}
\end{oppgave}
    \begin{center}
        \includegraphics[scale=.5]{../figurer/steepestdescent-1.png}
    \end{center}

\begin{oppgave}{12}    
    Her er det relativt enkelt Ã¥ modifisere koden i oppgave 2. 
\end{oppgave}





\begin{oppgave}{13}
    Dette var pensum i TMA4106 og jeg tror vi sier oss ferdige med det. 
\end{oppgave}

\begin{oppgave}{14}
    Vi ganger likningen 
    \begin{align*}
        \V x
        =
        \sum_k
        \alpha_k \V p_k.
    \end{align*}
    med $\V p_l^TA$ fra venstre og fÃ¥r  
    \begin{align*}
        \V p_l^T A \V x
        =
        \sum_k
        \alpha_k \V p_l^T A\V p_k
        =
        \alpha_k\V p_l^T A\V p_k 
    \end{align*}
    og bruker at $A\V x = \V b$, 
    slik at     
    \begin{align*}
        \alpha_k = 
        \frac{\V p_k^T \V b}{\V p_k^TA\V p_k}=
        \frac{( \V p_k,\V b)}{(\V p_k,\V p_k)_A}.
    \end{align*}
\end{oppgave}


\begin{oppgave}{15}
    Samme triks, 
    vi ganger med $\V p_k^T A$ fra venstre og krever at indreproduktet skal bli null:
    \begin{align*}
        0=&amp;
        \V p_k^T A
        \V p_{k+1}\\
        =&amp;
        \V p_k^T A
        \left(
        -\V r_{k+1}+
        \beta_{k+1} \V p_k
        \right)\\
        =&amp;
        -\V p_k^T A
        \V r_{k+1}+
        \beta_{k+1} 
        \V p_k^T A
        \V p_k
    \end{align*}
    slik at 
    \begin{align*}
        \beta_{k+1}
        = 
        \frac{(\V r_{k+1}, \V p_k)_A}{(\V p_k,\V p_k)_A}.
    \end{align*}
\end{oppgave}

\begin{oppgave}{16}
    Dette er litt hardt for TMA4121, 
    ihvertfall i Ã¥r. 
    Kanskje neste Ã¥r. 
\end{oppgave}

\begin{oppgave}{17}
    Dette er for hardt for eksamen. 
\end{oppgave}

\begin{comment}

\clearpage

\section*{UKENS NÃ˜TTER}

\begin{oppgave}{1}
    EstimÃ©r $\mu$ og $\sigma$ i kaieksemplet pÃ¥ side 1. 
    Dette kan gjÃ¸res pÃ¥ mange mÃ¥ter. 
\end{oppgave}

\begin{oppgave}{2}    
    Har det noen hensikt Ã¥ kjÃ¦re Newtons metode pÃ¥ et lineÃ¦rt system?
\end{oppgave}

Dersom $A$ er symmetrisk og positivt definitt, 
finnes det en mye mer fornuftig retning Ã¥ kjÃ¸re enn brattest utfor, 
nemlig langs med halvaksene til de elliptiske nivÃ¥kurvene. 

\begin{oppgave}{3}
    Forklar at med strategien fra oppgave 10 trenger du egentlig bare 
    to iterasjoner for Ã¥ komme frem til minimumspunktet dersom 
    du velger $\V p_n$ slik. 
\end{oppgave}


\begin{comment}


varmelikningsmatrisen

conjugate gradients - definitte matriser 

fft

pseudoinvers - normalikningene

schurfaktorisering

qr - dette er kun gramschmidt

lu

hÃ¸lder cauchy schwarz


\end{comment}



\end{document}
</pre></body></html>