\documentclass[10pt,letterpaper]{article}
\usepackage{graphicx,amssymb}
\usepackage[colorlinks=true]{hyperref}

\topmargin -0.5in
\textheight 9in
\oddsidemargin=-0.05in
\evensidemargin=-0.05in
\textwidth 6.5in
\pagestyle{empty}

\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand\ben{\begin{enumerate}}
\newcommand\een{\end{enumerate}}
\newcommand\vg{\vspace{2ex}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\ie}{{\it i.e.\ }}
\newcommand{\eg}{{\it e.g.\ }}
\newcommand{\eps}{\varepsilon}
\newcommand{\mbf}[1]{{\mathbf #1}}
\newcommand{\tbox}[1]{{\mbox{\tiny #1}}}
\newcommand{\emach}{\eps_\tbox{mach}}
\newcommand{\vt}[2]{\left[\begin{array}{l}#1\\#2\end{array}\right]}%2-col-vec
\newcommand{\mt}[4]{\left[\begin{array}{ll}#1&#2\\#3&#4\end{array}\right]}%2x2

\begin{document}
\title{Math 56 Compu \& Expt Math, Spring 2014: Homework 4}
\date{\vspace{-2ex} due 10am Thursday April 24th}
\maketitle

{\em Exploring beautiful properties and applications
of things Fourier. A bit shorter to let you recover from midterm.}

\ben

\item 
Fourier series theory.
As in lecture, let $\|\cdot\|$ be the $L_2$-norm on $(0,2\pi)$.
\ben
\item
Find a {\em unit-norm} function orthogonal to $f(x) = x$ on $0\le x < 2\pi$.
[Hint: do what you'd do in vector-land, eg pick some simple new
function and project away its $f$ component].
\item
Combine the Fourier series for the $2\pi$-periodic function
defined by $f(x) = x$ for $0\le x < 2\pi$ that
we computed on the worksheet with Parseval's relation to
evaluate $\sum_{m=1}^\infty m^{-2}$
%(Check your answer! Bonus if use (d) to prove a similar sum)
\item
Compute the Fourier series for the $2\pi$-periodic function
defined by $f(x) = x^2$ in $-\pi\le x < \pi$.
[Hint: shift the domain of integration to a convenient one.]
Comment on how $\hat{f}_m$ decays for this continuous (but not $C^1$)
function compared to the discontinuous function in (b).
\item
Take a general $f$ written as a Fourier series,
and take the derivative of both sides\footnote{You may assume that you
can pass the derivative through the sum.}.
What then is the $m$th Fourier coefficient of $f'$ ?
Prove that if $|f'|$ is bounded, $|\hat{f}_m|  = O(1/|m|)$, or better.
\item 
Use the previous idea to prove a bound on the decay of
Fourier coefficients when $f$ has $k$ bounded derivatives.
What bound follows if $f\in C^\infty$ (arbitrarily smooth)?
Can you give this a name?
\een

\item Getting to know your DFT. Use numerical exploration followed by proof
(each proof is very quick):
\ben
\item Produce a color image of the real part of the DFT matrix $F$ for $N=256$.
Explain one of the {\em curves} seen in the image.
\item What is $F^2$ ? [careful: matrix product, also don't forget the 0-indexing]. What does $F^2$ do to a vector? (this should be very simple!)
Now, for general $N$, prove your claim [Hint: use $\omega$]
\item What then is $F^4$ ? Prove this.
\item What are the eigenvalues of $F$? Use your previous result to prove
this.
\item What is the condition number of $F$? Prove this using a result from lecture.
\een

\item The power of trigonometric interpolation, i.e.\ using just
a few
samples of a periodic function to reconstruct the function {\em everywhere}.
(Applications to modeling data, etc.)
\ben
\item Let's interpolate $f(x) = e^{\sin x}$.
For $N=40$, by using the $1/N$-weighted samples
at the nodes $x_j=2\pi j/N$, $j=0,\ldots,N-1$, and ${\tt fft}$ to do the DFT,
find $\tilde{f}_m$. Plot their magnitudes on a
log vertical scale vs $m=0,\ldots,N-1$. Relate to \#1(e).
By what $|m|$ have the coefficients decayed to $\emach$ times the largest?
(This is the effective band-limit of the function at this tolerance.)
\item
Using $\tilde{f}_m$ as good approximations to the true Fourier coefficients in
$-N/2<m<N/2$, plot the ``intepolant''
given by this truncated Fourier series,
on the fine grid {\tt 0:1e-3:2*pi}.
Overlay the samples $Nf_j=f(x_j)$ as blobs.
[Hint: Remember the negative $m$'s are wrapped into the upper half of the DFT output. Debug until the interpolant passes through the samples]
\item By looping over the above for different $N$, make
a labeled
semi-log plot of the maximum error (taken over the fine grid)
between the interpolant and $f$, vs $N$,
for even $N$ between 2 and 40.
At what $N$ is convergence to $\emach$ reached?
(Pretty amazing, eh?) Relate to (a).
\een
% do spectral differentiation, or leave for later?
% use smooth



\item Let's prove that, amongst all trigonometric polynomials
of degree at most $N/2$, the $N/2$-truncated Fourier series for $f$
is the {\em best approximation} to $f$ in the $L_2(0,2\pi)$ norm.
\ben
\item Let $g$ be a general trig.\ poly.\ which can be written
$g = \sum_{|n|\le N/2} (\hat{f}_n + c_n) e^{inx}$
for some coefficient ``deviations'' $c_n$. Recall
$f = \sum_{n=- \infty}^{\infty} \hat{f}_n e^{inx}$.
Write the squared $L_2$-norm of the error which is the difference of $g$ and $f$:
\begin{eqnarray*}
||\mbox{error}||^2 &=& ||f-g||^2\\
&=& \left|\left|\sum_{|n|>N/2} \hat{f}_n e^{inx} - \sum_{|n|\le N/2} c_n e^{inx} \right|\right|^2.
\end{eqnarray*}
\item Using the definition of the norm, expand this expression for $||\mbox{error}||^2$ (you should obtain four terms, two of which will vanish). Whatever you do, do not multiply any of the big sums out. Can you use this expanded form to bound $||\mbox{error}||^2$ below by 
$ \left|\left|\sum_{|n|>N/2} \hat{f}_n e^{inx} \right|\right|^2$?
\item What does this say about how small the error can get? From this lower bound conclude that the error is minimized precisely when each $c_n = 0$,
ie when $g$ is the truncated Fourier series of $f$.
\een


\item A quickie on run-times.
Consider the ``matvec'' problem computing $\mbf{y} =A\mbf{x}$ for $A$ an
$n$-by-$n$ matrix.
Write a little code using random $A$ and $\mbf{x}$ for $n=4000$,
which measures the runtime of Matlab's native {\tt A*x}, and
your own naive double loop to compute the same thing.
Express your answers in ``flops'' (flop per sec), and give the ratio.
Marvel at how fast the built-in library is.

%\item Make a plot showing how many microseconds ($\mu$s = $10^{-6}$ s) it
%takes to do a FFT of a random vector of length $n$,
%varying $n$ over integers between 8100 to 8200 (use eg 100 repetitions
%for each $n$ to get runtimes that are long enough to measure accurately).
%Which few $n$ values have faster FFTs than the others?
%One of these values is easy to explain; do so [hint: prime factorization].
%\een


\een
\end{document}
