\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,amssymb}
\usepackage[pdftex]{graphicx}
\usepackage[pdftex,colorlinks=true,plainpages=false]{hyperref}
\newcommand{\T}{^\mathsf{T}}
\newcommand{\fl}{\mathit{fl}}
\begin{document}
\begin{center}
{\Large COMPUTER SCIENCE 314}\\
{\Large Numerical Methods} \\
{\large SPRING 2013} \\
 ASSIGNMENT \# 4 (25 points) \\
{\small February 19}
\end{center}

\subsection*{Announcement}
\begin{itemize}
\item Exam 4 is on Thursday, March 21 from noon to 12:25 pm.
 It covers material from this homework, Sections 3.1--3.5 of the textbook,
 and Chapter~4 of the class notes.
\end{itemize}

\subsection*{Due Thursday, March 7 at noon.}

\begin{enumerate}

\item[0.]
 Read Sections 3.1--3.5 of the textbook.

\item (4 points)
It can be shown that $1 \cdot 2 + 2 \cdot 3 + \cdots + n(n + 1)$, $n \geq 0$,
 is a cubic polynomial in $n$.  Construct this polynomial by
 Lagrange interpolation.  (You need not simplify your answer.)

\item (9 points)
 Assume we want to construct a piecewise cubic Hermite interpolant for data
\begin{equation}
(x_1, y_1), (x_2, y_2), ..., (x_n, y_n) 
\end{equation}
where $x_1 < x_2 < \cdots < x_n$.
\begin{enumerate}
\item
 Obtain a formula for a first derivative value $d_k$ at $x = x_k$
 based on differentiating the polynomial interpolant for the points
 $(x_{k-1}, y_{k-1})$, $(x_{k}, y_{k})$, and $(x_{k+1}, y_{k+1})$.
 Please express your answer in terms of the $h_k$ rather than the $x_k$.
 You may also use the $\delta_k$ instead of the $y_k$.
\item
 How would your answer to part~(a) change if, say, $x_k < x_{k-1} < x_{k+1}$?
\item Obtain a formula for a first derivative $d_1$ at $x = x_1$
 based on differentiating the polynomial interpolant for the points
 $(x_{1}, y_{1})$, $(x_{2}, y_{2})$, and $(x_3, y_3)$, and,
 as much as possible, {\em reuse your solution to part~(a)}.
\end{enumerate}

\item (12 points)
 In this problem you compare two parameterizations for a cubic spline
 interpolant of data points
{\small\begin{verbatim}
x  1  0.8  0.6  0 -0.6 -0.8 -1
y  0  0.6  0.8  1  0.8  0.6  0
\end{verbatim}}\noindent
 For the first parameter use the index numbers of the points.
 For the second parameter use distance along the piecewise linear path
 connecting the points, i.e, 0, $\sqrt{0.4}$,\ldots.
 Cf.\ Exercises 3.4 and 3.5 of the textbook.
 Implement your solution as a function M-file using at most 2 subfunctions.
 Use {\tt splinetx} or some other program that implements non-a-knot
 boundary conditions.
 Plot each interpolant using {\tt axis equal} and save each plot in a file.
 The plot should also mark the points being interpolated.
 Possibly useful functions: {\tt cumsum}, {\tt linspace}.

\newcounter{myenumi}\setcounter{myenumi}{\value{enumi}}
\end{enumerate}

\newpage
\subsection*{{\em DRAFT} Problems not to hand in}

However, solutions will be provided.
\begin{enumerate}
\setcounter{enumi}{\value{myenumi}}

\item Suppose a function $f(x)$ has $n$ distinct real roots,
 and $p(x)$ is a polynomial of lowest degree that interpolates
 $f(x)$ at those real roots.  What is the degree of $p(x)$?

\item
 Give the Lagrange form of the lowest degree polynomial that interpolates
 the function $f(x) = x^3 + x^2 + x + 1$ at the points
 $x = 0$, 1, and 2.
 (You need not simplify your polynomial.)

\item
 \begin{enumerate}
 \item
 Let $x_0$ be an arbitrary point on the real line.
 Precisely for what set of functions $f(x)$
 (defined for all real $x$)
 is it true that
 $$f(x) \equiv f(x_0).$$
 \item
 Let $x_0$ and $x_1$ be two different arbitrary points.
 Precisely for what set of functions $f(x)$
 is it true that
 $$f(x)
 \equiv \frac{x - x_0}{x_1 - x_0}f(x_1) + \frac{x - x_1}{x_0 - x_1}f(x_0).$$
 \item
 Let $x_0$, $x_1$, \ldots, $x_n$ be $n + 1$
 different arbitrary points and the
 $l_j(x)$ are the (Lagrange) fundamental polynomials for this set of points.
 Precisely for what set of functions $f(x)$
 is it true that
 $$f(x) \equiv  \sum_{j=0}^n f(x_j) l_j(x). $$
 \end{enumerate}

\item
 Suppose that a function is tabulated at equally spaced points $x = a + kh$
 and that this table is
 stored in an array in elements $y[k]$, $k = 0, 1, \ldots, n$.
 Write an algorithm that for any $x$ in the range
 $a$ to $a + nh$ returns a value obtained
 from the tabulated values by piecewise linear interpolation.
 You should use the ceiling or floor function.
 (The floor of a real number $x$ is the greatest integer $p$ such that
 $p \leq x$ and the ceiling is the least integer $q$ such that $x \leq q$.)

\item
 Suppose we wish to interpolate a given function on a given 
interval using function values at 21 points on 
the interval.  We could choose these points to be equally spaced, to
be more closely spaced in the middle, or to be more closely spaced at 
the ends.
\begin{itemize}
\item[(a)] For interpolation by a polynomial of degree 20, which is the
best choice?
\item[(b)] For piecewise linear interpolation which is the best choice?
\end{itemize}

\item Do Exercise 3.16 from the textbook for {\tt linear}, {\tt spline},
 and {\tt polynomial}.

\end{enumerate}

\subsection*{{\em DRAFT} Learning objectives}

\begin{itemize}
\item State and apply the fundamental theorem of algebra.
\item Give sufficient conditions
 for existence and uniqueness of an interpolating polynomial.
\item
 Obtain an interpolating polynomial by the method of undetermined coefficients.
\item Construct nodal basis functions for polynomial interpolation.
\item State and apply the Lagrange construction of an interpolating polynomial.
\item Program Lagrange interpolation.
\item
 Give the circumstances under which high degree interpolation performs poorly.
\item Program piecewise linear interpolation.
\item Explain
 the advantage of piecewise cubic interpolation over polynomial interpolation.
\item Explain the difference between cubic and piecewise cubic interpolation.
\item Construct nodal basis functions for cubic Hermiate interpolation.
\item Define a cubic spline.
\item What is a good set of values for representing a cubic splines?
\item What conditions must these values satisfy to be a cubic splines?
\item To what extent are cubic spline interpolants underdetermined?
\item What are the not-a-knot conditions?
\item How can interpolation be applied to fitting a curve (rather than
 a function) to two-dimensional data?
\item What makes the application of function interpolation to curve fitting
 not unique?
\end{itemize}

\end{document}