\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amsfonts,colortbl,graphicx}

\def\e{\mathrm{e}}
\def\i{\mathrm{i}}
\def\d{\mathrm{d}}

\begin{document}

\title{General Mathematics and CPS II}
\author{Exercise 22}
\date{May 8, 2015}
\maketitle



\begin{enumerate}

\item Compute the discrete Fourier transform of the vector
$(v_0, \dots, v_{N-1})$ with $N$ even and
\[
  v_j =
  \begin{cases}
    1 & \text{for } j < N/2 \,, \\
    0 & \text{otherwise} \,.
  \end{cases}
\]

\emph{Note:} The case $k=0$ is special, but if you think of your
expression for $\hat v_k$ as being defined for arbitrary
$k \in \mathbb R$, you should find that
$\lim_{k \to 0} \hat v_k = \hat v_0$.

\item Solve the difference equation
\begin{gather*}
  t_n = 2 \, t_{n-1} + 2^{n+1} \,, \\
  t_1 = 0 \,.
\end{gather*}

\item The first question on the previous exercise sheet suggests a way
to differentiate a periodic function $u \colon [0, 2\pi] \to \mathbb
R$ numerically:
\begin{itemize}
\item Sample $u$ on the equidistant grid $x_j = jh$ with
$h = 2 \pi/N$.  
\item Compute the discrete Fourier coefficients $\tilde u_k$ of the
vector of samples.
\item Set $\tilde w_k = \i k \, \tilde u_k$.
\item Finally, take the inverse DFT to obtain an approximation for
$u'$ sampled on the grid.
\end{itemize}
The approximation error for the derivative can be estimated in much
the same way as the error estimate for trigonometric interpolation in
Section~3 of the handout.  Again, the reconstruction formula must use
the symmetrized wave number range $k = -N/2, \dots, N/2-1$.

A practical difficulty arises from the convention used by virtually
all standard FFT software libraries in which $j=0,\dots,N-1$ and
$k=0,\dots,N-1$.  In particular, the input and output data arrays are
arranged in precisely this order.  With which factor, then, must the
$i$th element, with respect to the order imposed by the software, of
the vector $(\tilde u_0, \dots, \tilde u_{N-1})$ be multiplied so that
differentiation is computed correctly?



\end{enumerate}
\end{document}
