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

\pagestyle{fancy}

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

\exercise{Types of PDEs}
\begin{itemize}
	\item $u_t = u_{xx}$
		\begin{itemize}
			\item order: second-order PDE
			\item linearity: linear
			\item type: $A = 1, E = -1$ and all others are 0.
				$$B^2 - 4AC = 0 - 4 \cdot 1 \cdot 0 = 0 \Rightarrow \text{parabolic.}$$
		\end{itemize}
	\item $u_{tt} = u_{xx}$
		\begin{itemize}
			\item order: second-order PDE
			\item linearity: linear
			\item type: $A = 1, C = -1$ and all others are 0.
				$$B^2 - 4AC = 0 - 4 \cdot 1 \cdot (-1) = 4 > 0 \Rightarrow \text{hyperbolic.}$$
		\end{itemize}
	\item $u_{xx} + u_{yy} = 0$
		\begin{itemize}
			\item order: second-order PDE
			\item linearity: linear
			\item type: $A = 1, C = 1$ and all others are 0.
				$$B^2 - 4AC = 0 - 4 \cdot 1 \cdot 1 = -4 < 0 \Rightarrow \text{elliptic.}$$
		\end{itemize}
	\item $x u_x + y u_y + u^2 = 0$
		\begin{itemize}
			\item order: first-order PDE
			\item linearity: non-linear
			\item type: $D = x, E = y, F = u$ and all others are 0.
				$$B^2 - 4AC = 0 \Rightarrow \text{parabolic.}$$
		\end{itemize}
\end{itemize}

\exercise{Taylor expansions and difference schemes}
\begin{itemize}
	\item Taylor expansion: \\
		Analogously to (2.12) in the script, we have:
		\begin{eqnarray*}
			x & \equiv & j \Delta x, \\
			x+2 \Delta x & \equiv & (j+2) \Delta x, \\
			x-2 \Delta x & \equiv & (j-2) \Delta x
		\end{eqnarray*}
		We then get for the Taylor expansion:
		\begin{eqnarray*}
			u(x + 2 \Delta x) & = & \sum_{k=0}^p \frac{(2 \Delta x)^k}{k!} u^{(k)}(x) + \OnotO(\Delta x^{p+1}) \\
			& = & u(x) + (2 \Delta x) u'(x) + \frac{(2 \Delta x)^2}{2!} u''(x) + \frac{(2 \Delta x)^3}{3!} u'''(x) \\
			& & + \frac{(2 \Delta x)^4}{4!} u''''(x) + \frac{(2 \Delta x)^5}{5!} u'''''(x) + \OnotO(\Delta x^6) \\
			& = & u(x) + 2 \Delta x u'(x) + 2 \Delta x^2 u''(x) + \frac{4 \Delta x^3}{3} u'''(x) \\
			& & + \frac{2 \Delta x^4}{3} u''''(x) + \frac{4 \Delta x^5}{15} u'''''(x) + \OnotO(\Delta x^6) \\
			u(x - 2 \Delta x) & = & \sum_{k=0}^p \frac{(-2 \Delta x)^k}{k!} u^{(k)}(x) + \OnotO(\Delta x^{p+1}) \\
			& = & u(x) - 2 \Delta x u'(x) + 2 \Delta x^2 u''(x) - \frac{4 \Delta x^3}{3} u'''(x) \\
			& & + \frac{2 \Delta x^4}{3} u''''(x) - \frac{4 \Delta x^5}{15} u'''''(x) + \OnotO(\Delta x^6)
		\end{eqnarray*}
	\item Local truncation error: \\
		Analogously to (2.11), we can discretize $u''(j\Delta x)$ by
		$$\frac{u_{j+2} - 2u_j + u_{j-2}}{4 \Delta x^2} = 0 \quad , j \in \SetZ$$
		Let's compute the local truncation error (neglecting the argument $x$ as done in the lecture):
		\begin{eqnarray*}
			L_{2 \Delta x} (u(x)) & = & \frac{1}{4 \Delta x^2} \Big[u + 2 \Delta x u' + 2 \Delta x^2 u'' + \frac{4 \Delta x^3}{3} u''' \\
			& & \quad \quad + \frac{2 \Delta x^4}{3} u'''' + \frac{4 \Delta x^5}{15} u''''' + \OnotO(\Delta x^6) \Big] \\
			& & - \frac{2u}{4 \Delta x^2} \\
			& & + \frac{1}{4 \Delta x^2} \Big[u - 2 \Delta x u' + 2 \Delta x^2 u'' - \frac{4 \Delta x^3}{3} u''' \\
			& & \quad \quad + \frac{2 \Delta x^4}{3} u'''' - \frac{4 \Delta x^5}{15} u''''' + \OnotO(\Delta x^6) \Big] \\
			& = & \frac{1}{4 \Delta x^2} \Big[4 \Delta x^2 u'' + \underbrace{\frac{4 \Delta x^4}{3} u'''' + \OnotO(\Delta x^6)}_{\OnotO(\Delta x^4)}\Big]
		\end{eqnarray*}
		\begin{eqnarray*}
			L_{2 \Delta x} (u(x)) & = & \underbrace{u''}_{=0} + \OnotO(\Delta x^2) \\
			& = & \OnotO(\Delta x^2)
		\end{eqnarray*}
\end{itemize}

\exercise{Big \OnotO\ I}
\begin{enumerate}
\item Prove $\OnotO(h^p) + \OnotO(h^q) \in \OnotO(h^p)$ with $\varphi_p \in \OnotO(h^p)$ and $\varphi_q \in \OnotO(h^q)$.
\begin{eqnarray*}
  \OnotO(h^p) + \OnotO(h^q) &=& \lim_{h\rightarrow 0} \frac{\varphi_p}{h^p} + \lim_{h\rightarrow 0} \frac{\varphi_q}{h^q} \\
    &=& \lim_{h\rightarrow 0} \dfrac{\varphi_p + \frac{\varphi_q}{h^{q-p}}}{h^p}\\
    &=& \lim_{h\rightarrow 0} \dfrac{\varphi_p + \varphi'_p}{h^p}\\
    &=& \OnotO(h^p)
\end{eqnarray*}
whereas $\varphi'_p = \frac{\varphi_q}{h^{q-p}}$ is $\in \OnotO(h^p)$

\item Prove $\OnotO(h^p) \OnotO(h^q) \in \OnotO(h^{p+q})$ analogously to part a)
\begin{eqnarray*}
  \OnotO(h^p) \OnotO(h^q) &=& \lim_{h\rightarrow 0} \frac{\varphi_p}{h^p} \lim_{h\rightarrow 0} \frac{\varphi_q}{h^q} \\
    &=& \lim_{h\rightarrow 0} \dfrac{\varphi_p \varphi_q}{h^p h^q}\\
    &=& \lim_{h\rightarrow 0} \dfrac{\varphi_{p+1} }{h^{p+q}}\\
    &=& \OnotO(h^{p+1})
\end{eqnarray*}

\item $\OnotO(h^p) - \OnotO(h^p) \in \OnotO(h^p)$ follows directly by part a) due to the fact that $-\OnotO(h^p) = -1 * \OnotO(h^p) = \OnotO(h^p)$ and $q = p$ (as in notation from part a)).

\item As already said in the lecture, the left part is not defined due to the fact that $0 \in O(h^p) \; \forall p$.
\end{enumerate}

\exercise{Big \OnotO\ II}
\begin{enumerate}
	\item
		\begin{eqnarray*}
			a(h) \cdot b_1(h) & = & (h + h^2 + 10^{20}h^3)(h + h^2 + 10^{20}h^3 + 10^{-100}h^4) \\
			& = & h^2 + h^3 + 10^{20}h^4 + 10^{-100}h^5 \\
			&  & + h^3 + h^4 + 10^{20}h^5 + 10^{-100}h^6 \\
			& & + 10^{20}h^4 + 10^{20}h^5 + 10^{20} \cdot 10^{20} h^6 + 10^{20} \cdot 10^{-100} h^7 \\
			& = & h^2 + 2h^3 + (2 \cdot 10^{20} + 1)h^4 + (2 \cdot 10^{20} + 10^{-100})h^5 \\
			& & + (10^{-100} + 10^{40})h^6 + 10^{-80}h^7 \\
			& = & \sum_{i=2}^7 \OnotO(h^i) \\
			& \stackrel{(3a)}{=} & \OnotO(h^2)
		\end{eqnarray*}
	\item
		\begin{eqnarray*}
			b_1(h) - a(h) & = & h + h^2 + 10^{20}h^3 + 10^{-100}h^4 - (h + h^2 + 10^{20}h^3) \\
			& = & 10^{-100}h^4 \\
			& = & \OnotO(h^4)
		\end{eqnarray*}
	\item
		\begin{eqnarray*}
			b_1(h) + b_2(h) & = & h + h^2 + 10^{20}h^3 + 10^{-100}h^4 \\
			& & - h - h^2 + 10^{20}h^3 + 10^{-100}h^4 \\
			& = & 2 \cdot 10^{20}h^3 + 2 \cdot 10^{-100}h^4 \\
			& = & \sum_{i=3}^4 \OnotO(h^i) \\
			& \stackrel{(3a)}{=} & \OnotO(h^3)
		\end{eqnarray*}
\end{enumerate}

\end{document}
