From 1e8e7be1f5d022b4251a90f1707a50a5732cbba9 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Mon, 12 Mar 2012 16:18:54 +0100 Subject: [PATCH] Write some more on problem 3 --- rapport.tex | 91 ++++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 84 insertions(+), 7 deletions(-) diff --git a/rapport.tex b/rapport.tex index ba7b6c7..ab3caaa 100644 --- a/rapport.tex +++ b/rapport.tex @@ -74,15 +74,21 @@ 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$ og inversen $H$ -\begin{lstlisting}[language=Matlab] +\begin{lstlisting}[numbers=left,escapeinside={@}{@},language=Matlab] v = y - B*p; -B = B + v*v'/(v'*p); +@\label{lst:hessoppdatering}@B = B + v*v'/(v'*p); w = p - H*y; -H = H + w*w'/(w'*y); +@\label{lst:invoppdatering}@H = H + w*w'/(w'*y); \end{lstlisting} -Dette er en rang-1-oppdatering som oppfyller XXX. Utledningen finnes i -\citep*[p.~9123]{nocedal2006numerical}. -Breakdowns!!!!!!!1 +Dette er en rang-1-oppdatering som er konstruert slik at den oppfyller +sekant-likningen. Utledningen finnes i +\citep*[s.~144]{nocedal2006numerical}. + +SR-1-metoden kan bryte sammen hvis nevneren i oppdateringen på linje +\ref{lst:hessoppdatering} eller \ref{lst:invoppdatering} er lik null. +Hvis dette er tilfellet kan man f.eks. droppe å oppdatere $B$ og $H$ i +dette steget. Ved neste iterasjon står vi i et annet punkt, og vi får +dermed en annen oppdatering og antageligvis ikke det samme problemet. \subsubsection{Konjugert gradient} Konjugert gradient er en metode som baserer seg på å bygge opp @@ -103,7 +109,78 @@ 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$ +dekomponeringen av løsningsvektoren $x^* = \sum_i\alpha_i p_i$. Videre +oppdaterer vi gradienten og konstruerer neste vektor $p$ i basisen. +\begin{lstlisting}[language=Matlab] +g = g + alfa*Ap; +beta = (g'*Ap)./(p'*Ap); +p = -g + beta*p; +\end{lstlisting} +Ettersom $A$ er hessianen til testproblemet, og den er konstant, kan vi +oppdatere gradienten ved å legge til hessianen ganget med steget. Den +neste $p$-en lager vi ved en slags Gram-Schmidt-ortogonalisering. En +full utledning av metoden og konvergensegenskapene finnes i +\citep*[s.~102]{nocedal2006numerical}. + +\subsection{b)} +Hvis vi starter SR-1-metoden med $B=A$ og $H=A^{-1}$, tilsvarer det +newtons metode, og den vil konvergere i ett steg. Hvis vi starter i +punktet $x_0$ er det neste punktet gitt ved +\begin{equation} + \label{eq:sr1exact} + x_1 = x_0 - Hg = x_0 - A^{-1}g = x_0 - A^{-1}\left(Ax_0-b\right) = +A^{-1}b = x^*, +\end{equation} +som er den eksakte løsningen. + +\subsection{c)} +Litt numerisk eksperimentering tyder på at mange, men ikke alle, +søke-retningene i SR-1-metoden er tilnærmet ortogonale. Tabell +\ref{tab:indreprod} alle indreproduktene med verdi over $10^{-13}$ for +et testproblem med kondisjons-tall $\kappa = 30.0$. Som forventet gir +indreproduktet av søkevektorene med seg selv de største verdiene, og ut +over disse har det sneket seg inn indreprodukt av søke-vektorer som ikke +er så langt unna hverandre i itereringen. + +\begin{table} + \caption{Alle $A$-indreproduktene mellom søkeretningene, med verdi +over $10^{-13}$} + \label{tab:indreprod} + \begin{center} + \begin{tabular}{ c c } +$\left<1, 1\right>$ & 272.4474186805212000 \\ +$\left<1, 2\right>$ & 54.4486696594180870 \\ +$\left<2, 2\right>$ & 25.3888003438768630 \\ +$\left<3, 3\right>$ & 7.9225899576207715 \\ +$\left<4, 4\right>$ & 0.0640184413770905 \\ +$\left<4, 5\right>$ & 0.0039836459279243 \\ +$\left<4, 6\right>$ & 0.0039836459279241 \\ +$\left<5, 5\right>$ & 0.0009487468712036 \\ +$\left<6, 6\right>$ & 0.3033157832899873 \\ +$\left<7, 7\right>$ & 0.6161043921383534 \\ +$\left<8, 8\right>$ & 0.0452342561587233 \\ +$\left<9, 9\right>$ & 0.0032857049368393 \\ +$\left<10, 10\right>$ & 0.0000401791556377 \\ +$\left<11, 11\right>$ & 0.0000000160341393 \\ +$\left<11, 12\right>$ & 0.0000000160341393 \\ +$\left<12, 12\right>$ & 0.0000000160341393 \\ + \end{tabular} + \end{center} +\end{table} + +\subsection{d)} +Søkeretningene i SR-1-metoden kan i noen tilfeller ta deg lenger vekk +fra den eksakte løsningen. Dette reflekterer unøyaktigheter i den +tilnærmede hessianen, men er ikke så lett å oppdage hvis man ikke vet +den eksakte løsningen. Vi forsøkte forskjellige måter å unngå dette, +uten at noen av de så ut til å virke særlig bra. + +Som nevnt tidligere kan SR-1-metoden bryte sammen i oppdateringen av +hessianen søke-retningene, og vi implementerte den foreslåtte løsningen, +uten at det hjalp mot de dårlige søke-retningene. + +SR-1-metoden beholder ikke den positiv definitte egenskapen til +hessian-tilnærmingen. \bibliographystyle{plain} \bibliography{refs} -- 2.47.3