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

\pagestyle{fancy}

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

\exercise{Shift invariance of the Laplace operator}
Let's compute the following (by the use of the chain rule):
\begin{eqnarray*}
	u_x(x',y') & = & \frac{\partial u}{\partial x'} \frac{\partial x'}{\partial x} + \frac{\partial u}{\partial y'} \frac{\partial y'}{\partial x} \\
	& = & u_{x'} \cdot 1 + u_{y'} \cdot 0 \\
	& = & u_{x'} \\
	u_y(x',y') & = & \frac{\partial u}{\partial x'} \frac{\partial x'}{\partial y} + \frac{\partial u}{\partial y'} \frac{\partial y'}{\partial y} \\
	& = & u_{x'} \cdot 0 + u_{y'} \cdot 1 \\
	& = & u_{y'} \\
	u_{xx}(x',y') & = & (u_{x'})_{x'} \cdot 1 = u_{x'x'} \\
	u_{yy}(x',y') & = & (u_{y'})_{y'} \cdot 1 = u_{y'y'} \\[0.5cm]
	\Rightarrow u_{xx} + u_{yy} & = & u_{x'x'} + u_{y'y'}
\end{eqnarray*}
\QED

\exercise{What's the Matrix, what's the matrix?}

\exercise{Crossing Derivatives}

\exercise{Cooking norms}
\begin{enumerate}
	\item $\displaystyle \frac{1}{\sqrt{n}} \|x\|_2 \stackrel{(1)}{\leq} \|x\|_\infty \stackrel{(2)}{\leq} \|x\|_2 \stackrel{(3)}{\leq} \sqrt{n} \|x\|_\infty$
	\begin{itemize}
		\item Showing (1):
			\begin{eqnarray*}
				\frac{1}{\sqrt{n}} \cdot \sqrt{\sum_{i=1}^n |x_i|^2} & \leq & \frac{1}{\sqrt{n}} \sqrt{\sum_{i=1}^n \max |x_i|^2} \\
				& = & \frac{1}{\sqrt{n}} \sqrt{n \cdot \max_{i=1,...,n} |x_i|^2} \\
				& = & \frac{\sqrt{n}}{\sqrt{n}} |\max_{i=1,...,n} |x_i|| \\
				& = & \frac{\sqrt{n}}{\sqrt{n}} \max_{i=1,...,n} |x_i| \\
				& = & \|x\|_\infty
			\end{eqnarray*}
		\item Showing (2): Let $|x_m| := \max_{i=1,...,n} |x_i|$ with $m \in \{1,...,n\}$.
			\begin{eqnarray*}
				\left(\max_{i=1,...,n} |x_i|\right)^2 & = & |x_m|^2 \\
				& \leq & |x_m|^2 + \sum_{i=1, i \neq m}^n |x_i|^2 \\
				& = & \sum_{i=1}^n |x_i|^2 \\
				\Rightarrow \|x\|_\infty = \max_{i=1,...,n} |x_i| & \leq & \sqrt{\sum_{i=1}^n |x_i|^2} = \|x\|_2
			\end{eqnarray*}
		\item Showing (3): \\
			This follows directly from (1) by multiplying with $\sqrt{n}$.
	\end{itemize}
	\item $\displaystyle \frac{1}{\sqrt{n}} \|x\|_1 \stackrel{(4)}{\leq} \|x\|_2 \stackrel{(5)}{\leq} \|x\|_1 \stackrel{(6)}{\leq} \sqrt{n} \|x\|_2$
	\begin{itemize}
		\item Showing (6):
			\begin{eqnarray*}
				\sum_{i=0}^n |x_i| & = & \left(\left(\sum_{i=0}^n 1 \cdot |x_i|\right)^2\right)^{1/2} \\
				& \stackrel{\text{(Cauchy-Schwarz)}}{\leq} & \left(\sum_{i=1}^n 1^2\right)^{1/2} \cdot \left(\sum_{i=1}^n |x_i|^2\right)^{1/2} \\
				& = & \sqrt{n} \|x\|_2
			\end{eqnarray*}
		\item Showing (5):
			\begin{eqnarray*}
				\|x\|_2 & = & \sqrt{\sum_{i=1}^n |x_i|^2} \\
				& \leq & \sum_{i=1}^n \sqrt{|x_i|^2} \\
				& = & \sum_{i=1}^n |x_i| \\
				& = & \|x\|_1
			\end{eqnarray*}
		\item Showing (4): \\
			Follows directly from (6) by dividing by $\sqrt{n}$.
	\end{itemize}
\end{enumerate}

\exercise{Proving Banach}
We know according to (7.13), that
$$\| F(x) - F(y) \| \leq q \|x-y\| \quad x,y \in D$$
Let $x_{n+1} = F(x_n)$, then we get
$$\|x_{n+1} - x_n\| = \|F(x) - F(y)\| \leq q \|x_n - x_{n-1}\|$$
By induction, one finally gets
$$\|x_{n+1} - x_n\| \leq q^n \|x_1 - x_0\| \quad \quad (1)$$
Let's compute the following for $m > n$:
\begin{eqnarray*}
	\|x_m - x_n\| & \stackrel{\text{Def. 7.2, N4}}{\leq} & \|x_m - x_{m-1}\| + \|x_{m-1} - x_n\| \\
	& \stackrel{\text{Def. 7.2, N4}}{\leq} & \|x_m - x_{m-1}\| + \|x_{m-1} - x_{m-2}\| + \|x_{m-2} - x_n\| \\
	& \leq & \sum_{i=n}^{m-1} \|x_{i+1} - x_i\| \\
	& \stackrel{(1)}{\leq} & \|x_1 - x_0\| \cdot \sum_{i=n}^{m-1} q^i \quad (2)
\end{eqnarray*}
Now, one is able to proof the a priori statement.
\begin{eqnarray*}
	\|x_n - x\| & = & \lim_{m \to \infty} \|x_m - x_n\| \\
	& \stackrel{(2)}{\leq} & \lim_{m \to \infty} \|x_1 - x_0\| \cdot \sum_{i=n}^{m-1} q^i \\
	& = & \|x_1 - x_0\| \cdot \sum_{i=n}^\infty q^i \\
	& = & \|x_1 - x_0\| \left(\frac{1}{1-q} - \sum_{i=0}^{n-1} q^i\right) \\
	& = & \|x_1 - x_0\| \left(\frac{1}{1-q} - \frac{1 - q^n}{1 - q}\right) \\
	& = & \|x_1 - x_0\| \cdot \frac{q^n}{1-q} \\[0.5cm]
	\Rightarrow \|x_n - x\| & = & \frac{q^n}{1-q} \cdot \|x_1 - x_0\|
\end{eqnarray*}
\QED

\end{document}