\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{gastex}
%\usepackage{ngerman}
\usepackage{wasysym}
\usepackage{rotating}

\title{\textsc{Differential Equations in Image Processing and Computer Vision \\ \large Assignment T1}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \scriptsize 2031259} \\ Group 2: Thu, 12-14 (Markus Mainberger)}% \and \shortstack[c]{name\\ \scriptsize matr}}
\date{}

\pagestyle{fancy}

\lhead{Assignment T1}
\chead{}
\rhead{Dithmar (2031259)}
\lfoot{DIC}
\cfoot{Page \thepage}
\rfoot{SS 2008}

\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}{1}

\exercise{Convolution, Derivatives and Diffusion Equation}
\begin{enumerate}
	\item
		\begin{eqnarray*}
			(f * g')(x) & = & \int_{\SetR^2} f(y) (g(x-y))_x dy \quad \quad  \quad \quad \quad \quad \quad \quad (1) \\
			(f * g)'(x) & = & \int_{\SetR^2} (f(y) g(x-y))_x dy \\
			& = & \int_{\SetR^2} \big[\underbrace{(f(y))_x}_{=0} g(x-y) + f(y) (g(x-y))_x\big] dy \\
			(f * g)'(x) & = & \int_{\SetR^2} f(y) (g(x-y))_x dy = (f * g')(x) \quad \quad (2) \\
			(f * g)'(x) & \stackrel{Comm.}{=} & (g * f)'(x) \\
			& \stackrel{(2)}{=} & (g * f')(x) \\
			& \stackrel{Comm.}{=} & (f' * g)(x)
		\end{eqnarray*}
		\hfill \QED
	\item
		\begin{eqnarray*}
			u(x,t) & \stackrel{!}{=} & K_{\sqrt{2t}} (x) \\
			u_t & = & u_{xx} \quad x \in \SetR, t > 0
		\end{eqnarray*}
		We know from the lecture that
		\begin{eqnarray*}
			K_\sigma(x) & = & \frac{1}{\sigma \sqrt{2\pi}} \cdot \exp \left(-\frac{x^2}{2 \sigma^2}\right) \\
			\Rightarrow K_{\sqrt{2t}}(x) & = & \frac{1}{2\sqrt{\pi t}} \cdot \exp \left(-\frac{x^2}{4t}\right)
		\end{eqnarray*}
		I calculate the derivatives $u_t$ and $u_{xx}$ and check whether they are equal.
		\begin{eqnarray*}
			u_t & = & \frac{-\frac{1}{2}\pi}{2 (\pi t)^{3/2}} \exp \left(-\frac{x^2}{4t}\right) + \frac{1}{2\sqrt{\pi t}} \exp \left(- \frac{x^2}{4t}\right) \frac{x^2}{4t^2} \\
			& = & -\frac{\pi}{4 (\pi t)^{3/2}} \exp \left(-\frac{x^2}{4t}\right) + \frac{x^2}{8t^2\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right) \\
			& = & -\frac{\pi}{4\sqrt{\pi t} \pi t} \exp \left(-\frac{x^2}{4t}\right) + \frac{x^2}{8t^2\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right) \\
			& = & -\frac{2t}{8t^2\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right) + \frac{x^2}{8t^2\sqrt{\pi t}} \exp \left(- \frac{x^2}{4t}\right) \\
			u_t & = & \frac{x^2 - 2t}{8t^2\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right)
		\end{eqnarray*}
		\begin{eqnarray*}
			u_x & = & \frac{1}{2\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right) \frac{-2x}{4t} = -\frac{x}{4t\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right) \\
			u_{xx} & = & -\frac{1}{4t\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right) - \frac{x}{4t\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right) \left(-\frac{x}{2t}\right) \\
			& = & -\frac{1}{4t\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right) - \frac{x^2}{8t^2\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right) \\
			& = & -\frac{2t}{8t^2\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right) + \frac{x^2}{8t^2\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right) \\
			u_{xx} & = & \frac{x^2 - 2t}{8t^2\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right)
		\end{eqnarray*}
		One can easily see that $u_t = u_{xx}$ which means that $u(x,t) = K_{\sqrt{2t}}(x)$ is a solution. \hfill \QED
	\item In this case $u(x,t) = (K_{\sqrt{2t}} * f)(x)$. One can easily show that $u(x,t=0) = f(x)$ by using the given assumption:
		$$u(x,t=0) = (K_0 * f)(x) \stackrel{Ass.}{=} f(x) \quad \checkmark$$
		Now, one only has to show that $u_t = u_{xx}$.
		\begin{eqnarray*}
			u_t & = & ((K_{\sqrt{2t}} * f)(x))_t \\
			\stackrel{(a)}{\Leftrightarrow} u_t & = & ((K_{\sqrt{2t}})_t * f)(x) \\[0.3cm]
			u_{xx} & = & ((K_{\sqrt{2t}} * f)(x))_{xx} \\
			\stackrel{(a)}{\Leftrightarrow} u_{xx} & = & ((K_{\sqrt{2t}})_{xx} * f)(x)
		\end{eqnarray*}
		Since we know from part \textbf{b.}, that
		\begin{eqnarray*}
			(K_{\sqrt{2t}})_t & = & \frac{x^2 - 2t}{8t^2\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right) \\
			(K_{\sqrt{2t}})_x & = & -\frac{x}{4t\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right) \\
			(K_{\sqrt{2t}})_{xx} & = & \frac{x^2 - 2t}{8t^2\sqrt{\pi t}} \exp \left(-\frac{x^2}{4t}\right)
		\end{eqnarray*}
		we see that $(K_{\sqrt{2t}})_t$ and $(K_{\sqrt{2t}})_{xx}$ are the same. \\
		Since $(K_{\sqrt{2t}})_t$ and $(K_{\sqrt{2t}})_{xx}$ are the same, the terms $((K_{\sqrt{2t}})_t * f)(x) = ((K_{\sqrt{2t}} * f)(x))_t$ and $((K_{\sqrt{2t}})_{xx} * f)(x) = ((K_{\sqrt{2t}} * f)(x))_{xx}$ are the same for any given bounded continuous funtion $f$. \hfill \QED
\end{enumerate}

\exercise{Numerical Differentiation}
We want to approximate $f''$ with $f_{i-2}, f_{i-1}, f_i, f_{i+1}, f_{i+2}$. Doing a Taylor expansion results in the following:
\begin{eqnarray*}
	f_{i-2} & = & f_i - 2hf_i' + 2h^2f_i'' - \frac{4}{3}h^3f_i''' + \frac{2}{3}h^4f_i^{(4)} - \frac{4}{15}h^5f_i^{(5)} + O(h^6) \\
	f_{i-1} & = & f_i - hf_i' + \frac{1}{2}h^2f_i'' - \frac{1}{6}h^3f_i''' + \frac{1}{24}h^4f_i^{(4)} - \frac{1}{120}h^5f_i^{(5)} + O(h^6) \\
	f_i & = & f_i \\
	f_{i+1} & = & f_i + hf_i' + \frac{1}{2}h^2f_i'' + \frac{1}{6}h^3f_i''' + \frac{1}{24}h^4f_i^{(4)} + \frac{1}{120}h^5f_i^{(5)} + O(h^6) \\
	f_{i+2} & = & f_i + 2hf_i' + 2h^2f_i'' + \frac{4}{3}h^3f_i''' + \frac{2}{3}h^4f_i^{(4)} + \frac{4}{15}h^5f_i^{(5)} + O(h^6)
\end{eqnarray*}
Comparing the coefficients:
$$0 \cdot f_i + 0 \cdot f_i' + 1 \cdot f_i'' + 0 \cdot f_i''' + 0 \cdot f_i^{(4)} \stackrel{!}{=}  \alpha_{-2}f_{i-2} + \alpha_{-1}f_{i-1} + \alpha_0f_i + \alpha_1f_{i+1} + \alpha_2f_{i+2}$$
\begin{eqnarray*}
	f_i'' & = & (\alpha_{-2} + \alpha_{-1} + \alpha_0 + \alpha_1 + \alpha_2)f_i \\
	& & + (-2h\alpha_{-2} -h\alpha_{-1} + h\alpha_1 + 2h\alpha_2)f_i' \\
	& & + \left(2h^2\alpha_{-2} + \frac{1}{2}h^2\alpha_{-1} + \frac{1}{2}h^2\alpha_1 + 2h^2\alpha_2\right)f_i'' \\
	& & + \left(-\frac{4}{3}h^3\alpha_{-2} - \frac{1}{6}h^3\alpha_{-1} + \frac{1}{6}h^3\alpha_1 + \frac{4}{3}h^3\alpha_2\right)f_i''' \\
	& & + \left(\frac{2}{3}h^4\alpha_{-2} + \frac{1}{24}h^4\alpha_{-1} + \frac{1}{24}h^4\alpha_1 + \frac{2}{3}h^4\alpha_2\right)f_i^{(4)} + O(h^5)
\end{eqnarray*}
This gives the following system of equations:
\begin{eqnarray*}
	\left(\begin{array}{ccccc}1 & 1 & 1 & 1 & 1 \\ -2h & -h & 0 & h & 2h \\ 2h^2 & \frac{1}{2}h^2 & 0 & \frac{1}{2}h^2 & 2h^2 \\ -\frac{4}{3}h^3 & -\frac{1}{6}h^3 & 0 & \frac{1}{6}h^3 & \frac{4}{3}h^3 \\ \frac{2}{3}h^4 & \frac{1}{24}h^4 & 0 & \frac{1}{24}h^4 & \frac{2}{3}h^4\end{array}\right) \left(\begin{array}{c}\alpha_{-2} \\ \alpha_{-1} \\ \alpha_0 \\ \alpha_1 \\ \alpha_2\end{array}\right) & = & \left(\begin{array}{c}0 \\ 0 \\ 1 \\ 0 \\ 0\end{array}\right) \\
	\left(\begin{array}{ccccc}1 & 1 & 1 & 1 & 1 \\ -2 & -1 & 0 & 1 & 2 \\ 4 & 1 & 0 & 1 & 4 \\ -8 & -1 & 0 & 1 & 8 \\ 16 & 1 & 0 & 1 & 16\end{array}\right) \left(\begin{array}{c}\alpha_{-2} \\ \alpha_{-1} \\ \alpha_0 \\ \alpha_1 \\ \alpha_2\end{array}\right) & = & \left(\begin{array}{c}0 \\ 0 \\ 2/h^2 \\ 0 \\ 0\end{array}\right)
\end{eqnarray*}
Solving the equation system: (checked with Maple, everything's fine *gg*)
$$\left(\begin{array}{rrrrr|c}1 & 1 & 1 & 1 & 1 & 0 \\ -2 & -1 & 0 & 1 & 2 & 0 \\ 4 & 1 & 0 & 1 & 4 & 2/h^2 \\ -8 & -1 & 0 & 1 & 8 & 0 \\ 16 & 1 & 0 & 1 & 16 & 0\end{array}\right) \begin{array}{c}\ \\ \ \\ \ \\ \ \\ + 2 \cdot IV \end{array}$$
$$\left(\begin{array}{rrrrr|c}1 & 1 & 1 & 1 & 1 & 0 \\ -2 & -1 & 0 & 1 & 2 & 0 \\ 4 & 1 & 0 & 1 & 4 & 2/h^2 \\ -8 & -1 & 0 & 1 & 8 & 0 \\ 0 & -1 & 0 & 3 & 32 & 0\end{array}\right) \begin{array}{c}\ \\ \ \\ \ \\ - 4 \cdot II \\ \ \end{array}$$
$$\left(\begin{array}{rrrrr|c}1 & 1 & 1 & 1 & 1 & 0 \\ -2 & -1 & 0 & 1 & 2 & 0 \\ 4 & 1 & 0 & 1 & 4 & 2/h^2 \\ 0 & 3 & 0 & -3  & 0 & 0 \\ 0 & - 1 & 0 & 3 & 32 & 0\end{array}\right) \begin{array}{c}\ \\ \ \\ \ \\ \ \\ + \frac{1}{3} \cdot IV; (:2) \end{array}$$
$$\left(\begin{array}{rrrrr|c}1 & 1 & 1 & 1 & 1 & 0 \\ -2 & -1 & 0 & 1 & 2 & 0 \\ 4 & 1 & 0 & 1 & 4 & 2/h^2 \\ 0 & 3 & 0 & -3 & 0 & 0 \\ 0 & 0 & 0 & 1 & 6 & 0\end{array}\right) \begin{array}{c}\ \\ \ \\ + 2 \cdot II \\ \ \\ \ \end{array}$$
$$\left(\begin{array}{rrrrr|c}1 & 1 & 1 & 1 & 1 & 0 \\ -2 & -1 & 0 & 1 & 2 & 0 \\ 0 & -1 & 0 & 3 & 8 & 2/h^2 \\ 0 & 3 & 0 & -3 & 0 & 0 \\ 0 & 0 & 0 & 1 & 16 & 0\end{array}\right) \begin{array}{c}\ \\ \ \\ + \frac{1}{3} \cdot IV; (:2) \\ \ \\ \ \end{array}$$
$$\left(\begin{array}{rrrrr|c}1 & 1 & 1 & 1 & 1 & 0 \\ -2 & -1 & 0 & 1 & 2 & 0 \\ 0 & 0 & 0 & 1 & 4 & 1/h^2 \\ 0 & 3 & 0 &-3 & 0 & 0 \\ 0 & 0 & 0 & 1 & 16 & 0\end{array}\right) \begin{array}{c}\ \\ + 2 \cdot I \\ \ \\ \ \\ \ \end{array}$$
$$\left(\begin{array}{rrrrr|c}1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 2 & 3 & 4 & 0 \\ 0 & 0 & 0 & 1 & 4 & 1/h^2 \\ 0 & 3 & 0 & -3 & 0 & 0 \\ 0 & 0 & 0 & 1 & 16 & 0\end{array}\right)  \begin{array}{c}\ \\ \ \\ -V \\ \ \\ \ \end{array}$$
$$\left(\begin{array}{rrrrr|c}1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 2 & 3 & 4 & 0 \\ 0 & 0 & 0 & 0 & -12 & -1/h^2 \\ 0 & 3 & 0 & -3 & 0 & 0 \\ 0 & 0 & 0 & 1 & 16 & 0\end{array}\right)  \begin{array}{c}\Rightarrow \alpha_{-2} = -\frac{1}{12h^2} \\ \Rightarrow \alpha_0 = -\frac{5}{2h^2} \\ \Rightarrow \alpha_2 = -\frac{1}{12h^2} \\ \Rightarrow \alpha_{-1} = \frac{4}{3h^2} \\ \Rightarrow \alpha_1 = \frac{4}{3h^2} \end{array}$$
Finally we get:
\begin{eqnarray*}
	\alpha_{-2} = \alpha_2 & = & -\frac{1}{12h^2} \\
	\alpha_{-1} = \alpha_1 & = & \frac{4}{3h^2} \\
	\alpha_0 & = & -\frac{5}{2h^2}
\end{eqnarray*}
Let's plug that into
\begin{eqnarray*}
	f_i'' & = & \underbrace{(\alpha_{-2} + \alpha_{-1} + \alpha_0 + \alpha_1 + \alpha_2)}_{=0}f_i \\
	& & + \underbrace{(-2h\alpha_{-2} - h\alpha_{-1} + h\alpha_1 + 2h\alpha_2)}_{=0}f_i' \\
	& & + \underbrace{\left(2h^2\alpha_{-2} + \frac{1}{2}h^2\alpha_{-1} + \frac{1}{2}h^2\alpha_1 + 2h^2\alpha_2\right)}_{=1}f_i'' \\
	& & + \underbrace{\left(-\frac{4}{3}h^3\alpha_{-2} - \frac{1}{6}h^3\alpha_{-1} + \frac{1}{6}h^3\alpha_1 + \frac{4}{3}h^3\alpha_2\right)}_{=0}f_i''' \\
	& & + \underbrace{\left(\frac{2}{3}h^4\alpha_{-2} + \frac{1}{24}h^4\alpha_{-1} + \frac{1}{24}h^4\alpha_1 + \frac{2}{3}h^4\alpha_2\right)}_{=0}f_i^{(4)} \\
	& & + \underbrace{\left(-\frac{4}{15}h^5\alpha_{-2} - \frac{1}{120}h^5\alpha_{-1} + \frac{1}{120}h^5\alpha_1 + \frac{4}{15}h^5\alpha_2\right)}_{=0}f_i^{(5)} \\
	& & + \underbrace{\left(\frac{4}{45}h^6\alpha_{-2} + \frac{1}{720}h^6\alpha_{-1} + \frac{1}{720}h^6\alpha_1 + \frac{4}{45}h^6\alpha_2\right)}_{=-\frac{1}{90}h^4}f_i^{(6)} + O(h^7) \\[0.3cm]
	f_i'' & = & f_i'' - \frac{1}{90}h^4 f_i^{(6)} + O(h^7)
\end{eqnarray*}
It follows that the order of consistency is 4.

\end{document}
