\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 2}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \scriptsize 2031259} \and \shortstack[c]{Andreas Steinel \\ \scriptsize
2029984}}
\date{}

\pagestyle{fancy}

\lhead{Assignment 2}
\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}{\frac}

\maketitle

\thispagestyle{empty}

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

\exercise{BasicBasics\texttrademark\ of Schemes}
Artificial time: $u_t = \Delta u = u_{xx}$. Furthermore, $u_{xx} = \frac{u_{j-1} - 2 u_j + u_{j+1}}{(\Delta x)^2}$.
We use $(\Delta x)^2 = 1$.
\begin{enumerate}
	\item explicit time marching scheme:
		\begin{eqnarray*}
			u_t & = & u_{xx} \\
			\frac{u_j^{(n+1)} - u_j^{(n)}}{\Delta t} & = & \frac{u_{j-1}^{(n)} - 2 u_j^{(n)} + u_{j+1}^{(n)}}{1} \\
			u_j^{(n+1)} & = & \Delta t \left(u_{j-1}^{(n)} - 2 u_j^{(n)} + u_{j+1}^{(n)}\right) + u_j^{(n)}
		\end{eqnarray*}
		\begin{center}
			\includegraphics[height=0.5\textheight]{ex1a.eps}
		\end{center}
	\item Jacobi iteration:
		\begin{eqnarray*}
			\Delta u & = & 0 \\
			\frac{u_{j-1}^{(n)} - 2 u_j^{(n)} + u_{j+1}^{(n)}}{1} & = & 0 \\
			u_j^{(n)} & = & \frac{1}{2} \left(u_{j-1}^{(n)} + u_{j+1}^{(n)}\right)
		\end{eqnarray*}
		So, use as iteration
		$$u_j^{(n+1)} = \frac{1}{2} \left(u_{j-1}^{(n)} + u_{j+1}^{(n)}\right)$$
		\begin{center}
			\includegraphics[height=0.5\textheight]{ex1b.eps}
		\end{center}
\end{enumerate}

\exercise{Direct coding}
We have $(\Delta u = 0)_i$ which needs
$$\left(\begin{array}{rrrrrr}1 & 0 & \cdots & \cdots & \cdots & 0 \\ 1 & -2 & 1 & \cdots & \cdots & 0 \\ & \ddots & \ddots & \ddots \\ 0 & \cdots & \cdots & 1 & -2 & 1 \\ 0 & \cdots & \cdots & \cdots & 0 & 1\end{array}\right) \left(\begin{array}{c}u_0 \\ \vdots \\ \vdots \\ \vdots \\ u_{10}\end{array}\right) = \left(\begin{array}{c}1 \\ \vdots \\ \vdots \\ \vdots \\ 4\end{array}\right)$$
This leads to the tri-diagonal system of equations $Ax = b$ where we want to derive $x$. By use of the Thomas algorithm, we get the right solution.

\exercise{Implicit coding}
We use instead of a forward difference scheme a backward difference scheme. With this, it reads:
\begin{eqnarray*}
	u_t & = & \frac{u_j^n - u_j^{n-1}}{\Delta t} \\
	u_{xx} & = & \frac{u_{j-1} - 2u_j + u_{j+1}}{\Delta x^2} \\
	\frac{u_j^{(n)} - u_j^{(n-1)}}{\Delta t} & = & u_{j-1}^{(n)} - 2u_j^{(n)} + u_{j+1}^{(n)} \\
	u_j^{(n)} & = & \Delta t \left(u_{j-1}^{(n)} + 2u_j^{(n)} + u_{j+1}^{(n)}\right) + u_j^{(n-1)}
\end{eqnarray*}
This yields an implicit time marching scheme.

\exercise{Jacobi strikes back}
We consider the one-dimensional Laplace equation
$$\Delta u = u_{xx} = 0$$
\begin{enumerate}
	\item Derive $u_{xx}$ using backward differences:
		\begin{eqnarray*}
			u_x & = & \frac{u_j - u_{j-1}}{\Delta x} \\
			u_{xx} & = & \frac{u_{x_j} - u_{x_{j-1}}}{\Delta x} \\
			& = & \frac{\frac{u_j - u_{j-1}}{\Delta x} - \frac{u_{j-1} - u_{j-2}}{\Delta x}}{\Delta x} \\
			& = & \frac{u_j - 2 u_{j-1} + u_{j-2}}{\Delta x}
		\end{eqnarray*}
	\item First of all, we have to rewrite the discretisation of the 1-D Laplace equation:
		\begin{eqnarray*}
			\frac{u_j - 2u_{j-1} + u_{j-2}}{\Delta x^2} & = & 0 \\
			u_j - 2u_{j-1} + u_{j-2} & = & 0 \\
			\Leftrightarrow u_j & = & 2u_{j-1} - u_{j-2}
		\end{eqnarray*}
		From this, it follows
			$$u_j^{(n+1)} = 2u_{j-1}^{(n)} - u_{j-2}^{(n)}$$
	\item
		\begin{itemize}
			\item Problems at the boundaries.
			\item Doesn't represent local derivative very well.
		\end{itemize}
\end{enumerate}

\end{document}