From db95e40862a3853102e8fc261e60b374910db00a Mon Sep 17 00:00:00 2001
From: =?utf8?q?Bj=C3=B8rn=20Rustad?= <bjorn@rustad.me>
Date: Sun, 11 Mar 2012 17:23:39 +0100
Subject: [PATCH] Write some more about SR-1 and CG

---
 rapport.tex | 52 +++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 43 insertions(+), 9 deletions(-)

diff --git a/rapport.tex b/rapport.tex
index 7fbda4a..ba7b6c7 100644
--- a/rapport.tex
+++ b/rapport.tex
@@ -7,6 +7,7 @@
 \usepackage{graphicx}
 \usepackage{color}
 \usepackage{xfrac}
+\usepackage{natbib}
 \usepackage{amssymb, amsmath}
 \setcounter{secnumdepth}{0}
 
@@ -38,12 +39,24 @@ Her må vi også skrive noe.
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \subsection{a)}
+\subsubsection{SR-1}
 SR-1 er en kvasi-newton-metode der vi ved hver iterasjon oppdaterer vårt
 estimat for hessianen, $B$, med en rang-1-matrise. Ved hvert steg trenger
-vi også inversen til $B$, som vi kaller $H$.
+vi også inversen til $B$, som vi kaller $H$. Vi ser på en enkel og noe
+naiv implementasjon av SR-1-metoden for løsning av testproblemet
+\begin{equation}
+  \label{eq:testproblem}
+  \min_{x\in\mathbb{R}^n} \left\{ \frac{1}{2} x'Ax + b'x \right\},
+\end{equation}
+og forklarer hva som skjer underveis, uten å komme med noen bevis for
+hvorfor metoden fungerer.
 
-Ved hver iterasjon starter vi med følgende oppdatering av gjeldende
-posisjon $x$
+Før første iterasjon setter vi $x$ til origo. Hessianen $B$ og inversen
+$H$ setter vi lik identitetsmatrisen, og gradienten $g$ er eksakt lik
+$-b$ fra likning \eqref{eq:testproblem}.
+
+Vi starter hver iterasjon med følgende oppdatering av gjeldende posisjon
+$x$:
 \begin{lstlisting}[language=Matlab]
 p = -H*g;
 x = x + p;
@@ -60,17 +73,38 @@ y = g + y;
 Siden denne koden er spesifikk til testproblemet har vi at gradienten i
 punktet $x$ er lik $A\cdot x - b$. Variabelen $y$ vil etter dette være
 lik endringen i gradienten $g_{k+1} - g_k$. Neste steg er å oppdatere
-vår hessian-tilnærming $B$ som følger
+vår hessian-tilnærming $B$ og inversen $H$
 \begin{lstlisting}[language=Matlab]
 v = y - B*p;
 B = B + v*v'/(v'*p);
-\end{lstlisting}
-Skal vi forklare dette? Til slutt må vi også oppdatere $H$ slik at den
-fortsatt er inversen til $B$.
-\begin{lstlisting}[language=Matlab]
 w = p - H*y;
 H = H + w*w'/(w'*y);
 \end{lstlisting}
-Og hvor mye skal vi forklare av dette?
+Dette er en rang-1-oppdatering som oppfyller XXX. Utledningen finnes i
+\citep*[p.~9123]{nocedal2006numerical}.
+Breakdowns!!!!!!!1
+
+\subsubsection{Konjugert gradient}
+Konjugert gradient er en metode som baserer seg på å bygge opp
+løsningen $x^*$ ved hjelp av en basis $\left\{p_i\right\}$. Denne
+basisen konstruerer vi slik at vektorene er ortogonale med hensyn på
+$A$-indreproduktet $\left<u,v\right>_A = u'Av$.
+
+Vi ser fortsatt på testproblemet \eqref{eq:testproblem} og som for
+SR-1-metoden starter vi med $x$ i origo, og $g = -b$. Ved første
+iterasjon velger vi stegretningen $p = -g$, altså den mest synkende
+retningen.
+
+Ved hver iterasjon finner vi steglengden $alfa$ og oppdaterer gjeldende
+posisjon $x$
+\begin{lstlisting}[language=Matlab]
+Ap = A*p;
+alfa = -(p'*g)./(p'*Ap);
+x = x + alfa*p;
+\end{lstlisting}
+der $alfa$ tilsvarer koefissienten $\alpha_i$ foran $p_i$ i
+dekomponeringen av løsningsvektoren $x^* = \sum_i\alpha_i p_i$
 
+\bibliographystyle{plain}
+\bibliography{refs}
 \end{document}
-- 
2.47.3