\documentclass[12pt,a4paper]{article}

\usepackage{amstext}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{cancel}
\usepackage{fancyhdr}
\usepackage{listings}
\usepackage{pstricks}
\usepackage{pst-plot}
\usepackage{wasysym}
\usepackage{rotating}

\title{\textsc{Numerical Algorithms for Visual Computing II \\ \large Assignment 6}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \scriptsize 2031259} \and \shortstack[c]{Andreas Steinel \\ \scriptsize
2029984}}
\date{}

\pagestyle{fancy}

\lhead{Assignment 6}
\chead{}
\rhead{Dithmar (2031259), Steinel (2029984)}
\lfoot{NAVC II}
\cfoot{Page \thepage}
\rfoot{WS 2008/2009}

\begin{document}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\newcommand{\exercise}[1]{\subsection{#1}}
\renewcommand{\theenumi}{\textbf{\alph{enumi}}}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[2]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[#1]{#2}\\[0.2cm]
	\end{figure}
	}

\newcommand{\m}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\+}{\phantom{-}}
\newcommand{\f}{\dfrac}

\maketitle

\thispagestyle{empty}

\newpage
\setcounter{page}{1}
\setcounter{section}{6}

\exercise{Proving Stuff I}
\begin{eqnarray*}
	F(x)  &=& \frac{1}{2} (Ax, x)_2 - (b, x)_2 \\
	      &=& \frac{1}{2} \sum_{j=1}^n \: x_j A_i x_j - \sum_{j=1}^n b_j x_j \\
	\frac{\partial}{\partial x_i} F(x) &=& A_i x_i - b_i \\
    \frac{\partial}{\partial x} F(x)   &=& Ax - b \\
    \frac{\partial^2}{\partial x_i \partial x_j} F(x) & = & A_{ij} \\
    \frac{\partial^2}{\partial x \partial x} F(x) &=& A
\end{eqnarray*}
So, the solution is unique due to the fact that $Ax -b = 0$ has a unique solution for $A$ being a SPD matrix. It is also a minimum
($F''(x) > 0$) because the Hessian is a SPD matrix, which leads always to positive minors. From a unique minimum, the strict convexity follows.

\exercise{Proving Stuff II}
%We have
%\begin{eqnarray*}
%	f_{x,p} (\lambda) & = & F(x + \lambda p) \\
%	& = & \frac{1}{2} \big(A (x+ \lambda p), (x + \lambda p)\big)_2 - \big(b, (x + \lambda p)\big)_2 \\
%	& = & \frac{1}{2} (x + \lambda p)^\top A (x + \lambda p) - b^\top (x + \lambda p) \\
%	& = & \frac{1}{2} \Big[x^\top A x + \lambda p^\top A x + \underbrace{\lambda x^\top A p}_{= \lambda p^\top A x} + \lambda^2 p^\top A p\Big] - b^\top \big(x + \lambda p\big) \\
%	& = & \frac{1}{2} \Big[x^\top A x + 2 \lambda p^\top A x + \lambda^2 p^\top A p\Big] - b^\top (x + \lambda p)
%\end{eqnarray*}
%For $\lambda = \lambda_{opt}$ it looks as follows:
%\begin{eqnarray*}
%	f_{x,p} (\lambda_{opt}) & = & \frac{1}{2} \Big[x^\top A x + 2 \lambda_{opt} p^\top A x + \lambda_{opt}^2 p^\top A p\Big] - b^\top (x + \lambda_{opt} p) \\
%	& = & \frac{1}{2} \Big[x^\top A x + 2 \lambda_{opt} p^\top A x + \lambda_{opt}^2 p^\top A p\Big] - b^\top x - \lambda_{opt} b^\top p
%\end{eqnarray*}
%\begin{eqnarray*}
%	f_{x,p}' (\lambda_{opt}) & = & p^\top A x + \lambda_{opt} p^\top A p - b^\top p \\
%	& = & p^\top A x + \frac{r^\top p}{p^\top A p} p^\top A p - b^\top p \\
%	& = & p^\top A x + r^\top p - b^\top p \\
%	& = & p^\top A x + (b - Ax)^\top p - b^\top p \\
%	& = & \big(Ax, p\big)_2 + \big(b - Ax, p\big)_2 - \big(b, p\big)_2 \\
%	& = & 0
%\end{eqnarray*}
%The first constraint $f_{x,p}' (\lambda_{opt}) = 0$ is fulfilled. Now, let's look whether $f_{x,p}'' (\lambda) > 0$:
%\begin{eqnarray*}
%	f_{x,p}' (\lambda) & = & p^\top A x + \lambda p^\top A p - b^\top p \\
%	f_{x,p}'' (\lambda) & = & p^\top A p
%\end{eqnarray*}
%Since $A$ is a SPD matrix and $p_i^2 > 0 \; (i \in \{1, ..., n\})$, we have that $f_{x,p}'' (\lambda) > 0$.

\begin{eqnarray*}
F(x+\lambda p) &=& \frac{1}{2} \left(A (x+\lambda p), (x+\lambda p) \right)_2 - \left(b, (x+\lambda p)\right)_2 \\
\frac{\partial}{\partial \lambda} F(x) &=& \sum p_i A_i (x_i + \lambda p_i) - \sum b_i p_i \\
&=& \sum p_i A_i x_i + \lambda \sum p_i A_i p_i - \sum b_i p_i \\
\sum b_i p_i &=& \sum p_i A_i x_i + \lambda \sum p_i A_i p_i \\
\lambda_{opt} &=& \frac{\sum b_i p_i - \sum p_i A_i x_i}{\sum p_i A_i p_i } \\
&=& \frac{(b - Ax, p)_2}{(Ap,p)_2}
\end{eqnarray*}

\exercise{Scheming Schemes}
\begin{eqnarray*}
x_{m+1} &=& x_m + \underbrace{\left(  \frac{ ( \overbrace{b-Ax_m}^{r_m},p_m)_2 }{(Ap_m,p_m)_2} \right)}_\lambda p_m \\
        &=& x_m + \frac{ ( b,p_m)_2 -(Ax_m ,p_m)_2 }{(Ap_m,p_m)_2} p_m \\
        &=& \underbrace{x_m - \frac{1}{(Ap_m,p_m)_2} (Ax_m,p_m)_2 p_m}_{\text{dependent on }x_m} +
        \underbrace{\frac{1}{(Ap_m,p_m)_2} (b,p_m)_2 p_m}_{\text{dependent on }b} \\
        &\vdots& \\
        &=& M x_m + N b
\end{eqnarray*}
\ \\
\noindent \textit{Please check what's wrong with this one:} \\
Setting $M := -A$ and $N := I$, we get for
$$x_{m+1} = \phi (x_m, b) = Mx_m + Nb$$
exactly what we want:
$$x_{m+1} = b - Ax_m$$
According to Definition 8.1, the scheme is linear. Let's now check, with the help of Theorem 8.4, whether the system is consistent:
$$M = I - NA \stackrel{N=I}{=} I - IA = I -A = -A$$
The scheme is also consistent.


\exercise{A Descent into the Maelstrom}
\textit{Scilab.}
\begin{center}
\begin{tabular}{c|c}
	iteration & 2-norm \\ \hline
	5 & 0.439979925508511 \\
	10 & 0.034501431810018 \\
	15 & 0.003597990227066 \\
	20 & 0.000282139723372 \\
	25 & 0.000029423009832 \\
	30 & 0.000002307232463 \\
	35 & 0.000000240610300 \\
	40 & 0.000000018867679 \\
	45 & 0.000000001967620 \\
	50 & 0.000000000154293 \\
	55 & 0.000000000016090 \\
	60 & 0.000000000001262 \\
	65 & 0.000000000000132 \\
	70 & 0.000000000000010
\end{tabular}
\end{center}
If you run the code, you will see the following:
\begin{verbatim}
Iteration 05 leads to an error of 0.439979925508511
Iteration 10 leads to an error of 0.034501431810018
Iteration 15 leads to an error of 0.003597990227066
Iteration 20 leads to an error of 0.000282139723372
Iteration 25 leads to an error of 0.000029423009832
Iteration 30 leads to an error of 0.000002307232463
Iteration 35 leads to an error of 0.000000240610300
Iteration 40 leads to an error of 0.000000018867679
Iteration 45 leads to an error of 0.000000001967620
Iteration 50 leads to an error of 0.000000000154293
Iteration 55 leads to an error of 0.000000000016090
Iteration 60 leads to an error of 0.000000000001262
Iteration 65 leads to an error of 0.000000000000132
Iteration 70 leads to an error of 0.000000000000010
\end{verbatim}

%\exercise{Descending even further}
\setcounter{subsection}{5}

\exercise{A Descent into the Maelstrom with CG}
\textit{Scilab.} \\
In comparison to the steepest descent method which needs more than 70 iterations to almost reach an error of 0, the CG method needs only two iterations to be there. In other words, the CG method is much faster than the steepest descent method.

%\exercise{Comparison of different methods}
%\textit{Scilab.}

\end{document}
