\documentclass[12pt,a4paper]{article}

%\newif\ifpdf
%\ifx\pdfoutput\undefined
%   \pdffalse
%\else
%   \pdfoutput=1
%   \pdftrue
%\fi

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

\pagestyle{fancy}

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

\exercise{Shake That!}
\begin{enumerate}
	\item As you like, the inline source code:
    \begin{tiny}
    \begin{verbatim}
function upwind()
  // constructing signal as follows:
  // sig   00000 11111 11111 00000 00000 ...
  // idx  -4   0 1     6     11    16    ...
  signal = zeros(50,1);
  signal(5:15,1) = 1;
  
  s  = 20;      // steps
  a  = 2.0;     // parameter a
  dx = 0.1;     // delta x
  dt = 0.025;   // delta t
  
  // plot original signal
  plot2d(1:50,signal,style=1)
  
  for i=1:s
    // build boundary-zero-ed signal and shift one to left
    n = size(signal,1)
    tmp = zeros(n+2,1)
    tmp(2:n+1,1) = signal(1:n,1);

    for j=1:n
     signal(j,1) = dt * a / dx * (tmp(j,1) - tmp(j+1,1)) + tmp(j+1,1)
    end
    
    // plot every 5 iterations
    if modulo(i,5) == 0
      plot2d(1:50,signal,style=i/5)
    end
  end
endfunction
    \end{verbatim}
    \end{tiny}
    The plot shows every fifth iteration and also includes the initial signal.
    \begin{center}

%    \ifpdf
%      \includegraphics[width=\linewidth]{upwind.pdf}
%    \else
      \includegraphics[width=\linewidth]{upwind.eps}
%    \fi

    \end{center}
	\item We know from the lecture
		\begin{eqnarray*}
			u_i \approx u(i \Delta x) & \stackrel{(2.12)}{=} & u(x) \\
			u_{i-1} \approx u((i-1) \Delta x) & \stackrel{(2.12)}{=} & u(x - \Delta x) \\
			u^n \approx u(n \Delta t) & \stackrel{(2.12)}{=} & u(t) \\
			u^{n+1} \approx u((n+1) \Delta t) & \stackrel{(2.12)}{=} & u(t + \Delta t)
		\end{eqnarray*}
		Let's compute the Taylor expansions:
		\begin{eqnarray*}
			u(x) & = & u(x) \\
			u(x - \Delta x) & = & u(x) + [(x - \Delta x) - x] u'(x) + \dfrac{[(x + \Delta x) - x]^2}{2} u''(x) \\
			& & + \dfrac{[(x - \Delta x) - x]^3}{6} u'''(x) + \dfrac{[(x + \Delta x) - x]^4}{24} u''''(x) \\
			& & + \dfrac{[(x - \Delta x) - x]^5}{120} u'''''(x) + \OnotO(\Delta x^6)
		\end{eqnarray*}
		
		\begin{eqnarray*}
			u(t) & = & u(t) \\
			u(t + \Delta t) & = & u(t) + [(t + \Delta t) - t] u'(t) + \dfrac{[(t + \Delta t) - t]^2}{2} u''(t) \\
			& & + \dfrac{[(t + \Delta t) - t]^3}{6} u'''(t) + \dfrac{[(t + \Delta t) - t]^4}{24} u''''(t) \\
			& & + \dfrac{[(t + \Delta t) - t]^5}{120} u'''''(t) + \OnotO(\Delta x^6)
		\end{eqnarray*}
		
		Let's compute the local truncation error (neglecting the arguments $x$ and $t$, respectively):
		\begin{eqnarray*}
        L(u) = \frac{ u_i^{n+1} - u_i^n}{\Delta t} + a \: \frac{ u_i^n - u_{i-1}^n }{ \Delta x} - 0
		\end{eqnarray*}
		
		\begin{eqnarray*}
			L(u) & = & \dfrac{1}{\Delta t} \left[u + \Delta t u_t + \dfrac{\Delta t^2}{2} u_{tt} + \dfrac{\Delta t^3}{6}
            u_{ttt} \right. \\
			& & \quad \quad \left. + \dfrac{\Delta t^4}{24} u_{tttt} + \dfrac{\Delta t^5}{120} u_{ttttt} + \OnotO(\Delta t^6)\right] \\
			& & - \dfrac{u}{\Delta t} + a \left( \dfrac{u}{\Delta x} \right. \\
			& & - \dfrac{1}{\Delta x} \left[u - \Delta x u_x + \dfrac{\Delta x^2}{2} u_{xx} - \dfrac{\Delta x^3}{6}
            u_{xxx}  \right. \\
			& & \quad \quad \quad \left. \left. + \dfrac{\Delta x^4}{24} u_{xxxx} - \dfrac{\Delta x^5}{120} u_{xxxxx} +
            \OnotO(\Delta x^6)\right] \right) \\
			& = & \underbrace{(u_t + a u_x)}_{=0} \underbrace{+ \dfrac{\Delta t}{2} u_{tt} + \dfrac{\Delta t^2}{6} u_{ttt}
            + \dfrac{\Delta t^3}{24} u_{tttt} + \dfrac{\Delta t^4}{120} u_{ttttt} + \OnotO(\Delta t^5)}_{\OnotO(\Delta t)} \\
			& & + \underbrace{ a \left( -\dfrac{\Delta x}{2} u_{xx} + \dfrac{\Delta x^2}{6} u_{xxx} - \dfrac{\Delta
            x^3}{24} 
            u_{xxxx} + \dfrac{\Delta x^4}{120} u_{xxxxx} + \OnotO(\Delta x^5)\right)}_{\OnotO(\Delta x)}\\
			\Big[  & = & \left(\frac{\Delta t}{2} u_{tt} - a \frac{\Delta x}{2} u_{xx}\right) + \OnotO((\Delta
            t)^2) + \OnotO((\Delta x)^2) \Big]\\
			& = & \OnotO(\Delta t) + \OnotO(\Delta x)
		\end{eqnarray*}
	\item We have
		$$u_t + a u_x = 0 \Leftrightarrow u_t = -a u_x.$$
		\begin{eqnarray*}
			u_{tt} & = & (-a u_x)_t \\
			& = & -a (u_x)_t \\
			u_{xx} & = & \left(-\dfrac{1}{a} u_t\right)_x \\
			& = & -\dfrac{1}{a} (u_t)_x \\
			& = & -\dfrac{1}{a} (u_x)_t
		\end{eqnarray*}
		Now, let's check the relationship:
		\begin{eqnarray*}
			u_{tt} & = & a^2 u_{xx} \\
			-a (u_x)_t & = & a^2 \left(-\dfrac{1}{a}\right) (u_x)_t \\
			a & = & a \quad \checkmark
		\end{eqnarray*}
        \item
        We use the second last line of the computation of $L(u)$ which reads
        \begin{eqnarray*}
        L(u) &=& \frac{\Delta t}{2} u_{tt} - a \frac{\Delta x}{2} u_{xx} + \OnotO((\Delta t)^2) + \OnotO((\Delta x)^2) \\
        &\stackrel{\text{Hint 2}}{=}& \frac{\Delta t}{2} u_{tt} - a \frac{\Delta x}{2} u_{xx} + \OnotO((\Delta x)^2) \\
        &\stackrel{\text{Hint 3}}{=}& \frac{\Delta t}{2} (a^2 u_{xx}) - a \frac{\Delta x}{2} u_{xx} + \OnotO((\Delta x)^2) \\
        &=& u_{xx} \: \left( \frac{a^2 \: \Delta t  - a \: \Delta x }{2} \right) + \OnotO((\Delta x)^2) \\
        &\stackrel{\text{Hint 2}}{=}& u_{xx} \: \left( \frac{a^2 \: (\lambda \Delta x)  - a \Delta x }{2}\right)  + \OnotO((\Delta x)^2) \\
        &=& u_{xx} \: \underbrace{\left( \frac{a \: \Delta x}{2} \: (a \: \lambda - 1) \right)}_{\alpha(\Delta x)}  + \OnotO((\Delta x)^2) \\
        \end{eqnarray*}
        \QED

        The term $u_{xx} \alpha(\Delta x)$ leads to a smoothing of the signal which depends heavily on $a$.

        \item
        We derived in the previous two parts of this exercise the first level order accurate solution with the leading
        error term. If we want to modify the given equation of the upwind scheme in such a way that it is second-order
        accurate, we have to build an equation so that the first order error term cancels out.

        In this part of the exercise, we have to prove that the following equation is second-order accurate:
        \begin{eqnarray*}
        u_t + a u_x &=& \frac{a\Delta x}{2} (1-a\lambda) u_{xx} \\
        u_t + a u_x + \frac{a\Delta x}{2} (a\lambda -1 ) u_{xx} &=& 0
        \end{eqnarray*}
        With the result from the previous exercise we get immediately the second-order accuracy.
        \begin{eqnarray*}
        L(u) &=& \underbrace{\left( u_t + a u_x + u_{xx} \left(\frac{a \: \Delta x}{2} \: (a \: \lambda - 1)
                 \right)\right)}_{=0} + \OnotO((\Delta x)^2)
        \end{eqnarray*}
        \QED

\end{enumerate}

\exercise{No Time To Chill}
\begin{enumerate}
	\item We know from the lecture that
		$$u_i^{n+1} = u_i^n - a \dfrac{\Delta t}{\Delta x} (u_i^n - u_{i-1}^n)$$
		can be expressed by a scheme function $\mathcal{H}$
		$$\mathcal{H}(u_{i-1}^n, u_i^n) = u_i^n - a \dfrac{\Delta t}{\Delta x} (u_i^n - u_{i-1}^n).$$
		A scheme is monotone if
		\begin{eqnarray*}
			\dfrac{\partial \mathcal{H}}{\partial u_{i-1}^n} & = & a \dfrac{\Delta t}{\Delta x} \geq 0 \\
			\dfrac{\partial \mathcal{H}}{\partial u_i^n} & = & 1 - a \dfrac{\Delta t}{\Delta x} \geq 0 \\
			& & \Leftrightarrow \Delta t \leq \dfrac{\Delta x}{a}
		\end{eqnarray*}
		\begin{enumerate}
			\item
				\begin{eqnarray*}
					\Delta t & \leq & \dfrac{\Delta x}{a_1} = \dfrac{2}{5} \geq 0 \\
					a_1 \dfrac{\Delta t}{\Delta x}  & \leq & 0.5 \cdot \dfrac{0.4}{0.2} = 1 \geq 0 \quad \checkmark
				\end{eqnarray*}
				For $\Delta t \leq \dfrac{2}{5} = 0.4$, the scheme is monotone.
			\item
				\begin{eqnarray*}
					\Delta t & \leq & \dfrac{\Delta x}{a_2} = \dfrac{1}{25} \geq 0 \\
					a_2 \dfrac{\Delta t}{\Delta x}  & \leq & 5 \cdot \dfrac{0.04}{0.2} = 1 \geq 0 \quad \checkmark
				\end{eqnarray*}
				For $\Delta t \leq \dfrac{1}{25} = 0.04$, the scheme is monotone.
		\end{enumerate}
	\item For the resulting conditions, we get a discrete minimum-maximum-principle for $\Delta t \leq \dfrac{2}{5}$ and $\Delta t \leq \dfrac{1}{25}$, respectively, since the monotony property implies for hyperbolic PDEs an upper and lower bound in the $L_\infty$-norm. This directly implies stability.
\end{enumerate}

\end{document}
