\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\newcommand{\R}{{\mathbb R}}
\newcommand{\points}[1]{\phantom{.}\hfill \textbf{(#1~points)}}

\begin{document}

\begin{center}
  \begin{huge}
    MATH 609-602: Numerical Methods
  \end{huge}
\end{center}

\begin{tabular}{ll}
Lecturer: & Prof. Wolfgang Bangerth \\
& Blocker Bldg., Room 507D \\
& (979) 845 6393 \\
& \texttt{bangerth@math.tamu.edu}\\[5pt]
Teaching Assistant: & Seungil Kim \\
& Blocker Bldg., Room 507A \\
& (979) 862 3259 \\
& \texttt{sgkim@math.tamu.edu}
\end{tabular}

\section*{Homework assignment 7 -- due Tuesday 10/25/2005}


\paragraph{Problem 1 (Polynomial interpolation, again; last week's homework
  didn't show what I intended to show, see the answer sheets).}
Compute the polynomial $p_{2N}(x)$ of order $2N$ such that
\begin{itemize}
\item $p_{2N}(0) = 1$,
\item $p_{2N}(\pm\frac jN) = 0$ for $j=1,\ldots,N$.
\end{itemize}
Plot these polynomials for $N=2,4,6,8,12,20$ in the interval $-1\le x \le
1$. What happens as $N$ becomes larger?
\points{3}


\paragraph{Problem 2 ($L^\infty$ norm for functions).} For vectors, the
$l^\infty$ norm equals the magnitude of the largest component of the
vector. Similarly, for a function $f(x), a\le x\le b$, we define the infinity
norm (now written with an upper-case $L^\infty$ to indicate that this is the
norm of a function, rather than a vector) as
\begin{align*}
  \|f\|_{L^\infty(a,b)} = \max_{a\le x\le b} |f(x)|.
\end{align*}

Consider the functions $p_{2N}(x)$ computed in Problem 1. These functions are
made to interpolate data points $(x_i,y_i)$ for which all data points $y_i$
lie in the range $0\le y_i\le 1$. Yet, as you should have seen from the graphs
produced for Problem 1, $p_{2N}(x)$ does not respect this range; the
interpolating polynomials oscillate wildly between interpolation points. 

For the 6 polynomials $p_{2N}(x)$ computed in Problem 1 for $N=2,4,6,8,12,20$,
compute $\|p_{2N}\|_{L^\infty(-1,1)}$.

(Note: The maximum of a function $f$ of course satisfies $f'=0$. For the
polynomial $p_{2N}$ of order $2N$, this means that you are looking for a zero
of a polynomial of order $2N-1$. This problem is not solvable in general if
$N\ge 3$ --
unless the coefficients of the polynomial satisfy some really lucky
coincidence -- so I will be satisfied if you can come up with any idea,
rigorous or not, to find an approximate value of the infinity norm of
$p_{2N}$, as long as you explain how you compute it.)
\points{3}

\paragraph{Problem 3 (Least-squares approximation).} Take the same $2N+1$
points as in Problem 1. For $N=6,8,12,20$, compute the best least-squares
approximating polynomials of order 4, i.e. the polynomial $p_4(x)$ such that
\begin{align*}
  \left(\sum_{i=1}^N |p_4(x_i)-y_i|^2 \right)^{1/2}
\end{align*}
is minimal. Plot them for the range $-1\le x \le 1$. Compare to the
corresponding polynomials from Problem 1. What is the behavior of the
least-squares approximates between the data points $(x_i,y_i)$?
\points{5}


\paragraph{Problem 4 (Extrapolation).}
We have measured the following 10 data points:
\begin{center}
  \begin{tabular}{c||c|c|c|c|c|c|c|c|c|c}
    $x_i$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
    $y_i$ & 1.51 & 2.01 & 2.49 & 2.98 & 3.51 & 4.01 & 4.49 & 5.02 & 5.52 & 5.98
  \end{tabular}
\end{center}
It seems reasonable to assume a linear relationship between $x$ and
$y$. Compute
\begin{itemize}
\item the interpolating polynomial $p_9^{inter}(x)$ for these 10 data points;
\item the linear least-squares polynomial $p_1^{ls}(x)$ that best approximates
  these data points. 
\end{itemize}
Plot both in the interval $-2\le x\le 12$, together with the data points. If
we want to extrapolate the measured behavior (i.e., predict the behavior of
$y$ outside the range $1\le x\le 10$ within which we have obtained
measurements), what can you conclude from the plots? In particular, what are
the values $p_9^{inter}(12)$ and $p_1^{ls}(12)$ that the two functions predict
for $x=12$? What value would you expect from the linear model that was clearly
the basis on which the data points were obtained?  \points{5}




\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: