\documentclass[11pt]{article}

\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{amsmath,amsfonts,amssymb}

\setlength{\textwidth}{6.2in}
\setlength{\oddsidemargin}{0.3in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{8.7in}
\setlength{\voffset}{-.7in}
\setlength{\headsep}{26pt}
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt}

% input some useful macros:
\input{macros.tex}

\begin{document}

AMath 584 \hfill Name:  INSERT YOUR NAME HERE\\
Homework 4 \hfill UWNetID: INSERT YOUR NETID\\
Due to dropbox by 6pm PDT, November 30, 2011

%--------------------------------------------------------------------------
\vskip 0.5cm
\hrule
\vskip 0.5cm

Use latex for this assignment!
Submit a pdf file to the dropbox.  

You do not need to call it {\tt am584hw4.pdf}, but please submit a single
{\tt pdf} file.


%--------------------------------------------------------------------------
\vskip 1cm
\hrule
{\bf Problem \#1.}
Read the handout on interpolation found on the Homework 4 website.

Consider the problem of interpolating the following three data points
$(t_i,y_i)$  with a polynomial of degree 2:

\[
(1990,200),~~(2000,300),~~(2010,600).
\]

The $t_i$ values might be years, as in the previous homework.  

There are many
different bases that could be used for the space of quadratic polynomials. 
For each basis below, do the following (using Matlab or Python):

\begin{itemize}
\item Determine the matrix $A$ that you would need to use in
order to solve for the polynomial coefficients $c$ by solving a system of
the form $Ac=y$.
\item Determine the singular value decomposition of $A$ and print out the 3
singular values.
\item Use these to determine the condition number of $A$ in the 2-norm.
\item Solve the system to determine the coefficients of the polynomial.
Print out all digits of the coefficients (e.g. use {\tt format long e} in
Matlab or {\tt print "\%21.16e" \% c[i]} to print the $i$'th coefficient in
Python. 
\item Evaluate the polynomial at 1000 points in the interval from $t=1980$ to
$t=2020$ in order to plot the polynomial over this range.  
\end{itemize} 
Note that the polynomials you plot should be (mathematically) identical even
though the basis functions used and hence the coefficients obtained in each
case will be different.  You can put all the plots on the same graph (so you
should just see one line to plotting accuracy).  Also plot the three data
points.

\vskip 10pt
{\bf (a)~} Standard monomial basis:
\[
\phi_1(t) = 1,\quad \phi_2(t) = t, \quad \phi_3(t)=t^2.
\]

{\bf (b)~} Shifted monomial basis (as in Homework 3):
\[
\phi_1(t) = 1,\quad \phi_2(t) = t-2000, \quad \phi_3(t)=(t-2000)^2.
\]

{\bf (c)~} Newton form (Note that $A$ should be lower triangular!):
\[
\phi_1(t) = 1,\quad \phi_2(t) = t-1990, \quad \phi_3(t)=(t-1990)(t-2000).
\]


{\bf (d)~} Lagrange form (Note that $A$ should be diagonal!):
\[
\phi_1(t) = (t-2000)(t-2010),\quad \phi_2(t) = (t-1990)(t-2010), 
\quad \phi_3(t)=(t-1990)(t-2000).
\]
\vskip 0.5cm
{\bf Solution:}

% insert your solution here!

%--------------------------------------------------------------------------
\vskip 1cm
\hrule
{\bf Problem \#2.}

The Lagrange form in the problem above gives the matrix with the
smallest condition number and solving the system is trivial.  Using the
coefficients from this form, rewrite the resulting polynomial in the
standard form $p(t) = a_1 + a_2t + a_3t^2$ (i.e. determine the $a_i$).
Compare these with the coefficients found in part (a) of Problem 1.  What is
the relative error in each?


\vskip 0.5cm
{\bf Solution:}
% insert your solution here!


%--------------------------------------------------------------------------
\vskip 1cm
\hrule
{\bf Problem \#3.}

{\bf (a)~} 
The errors found in Problem 2 aren't as large as you might expect from the
condition number of the matrix.  Use the singular value decomposition to
construct a set of data $y$  with $\|y\|_2 = 1$
for this interpolation problem and a perturbation
$\delta y$ with $\|\delta y\|_2 = 10^{-10}$ so that changing $y$ to $\bar y = 
y+\delta
y$ changes the interpolation coefficients computed from $c$ to $\bar c$
with $\|c-\bar c \|/\|c\|$ larger than $\|\delta y\|/\|y\|$ by a factor of
$\kappa$.  You should find that two of the coefficients no longer have any
accuracy even though the change in $y$ was tiny.

{\bf (b)~} Since the coefficients $\bar c$ are so different from $c$, you
might expect that evaluating $\bar p(t) = \bar c_1 + \bar c_2t + \bar
c_3t^2$ would give very different results than evaluating
$p(t)=c_1+c_2t+c_3t^2$.  Plot the
difference between these two functions over the interval from 1980 to 2020
and observe that the error is actually very small.  Explain this by looking
more carefully at the size of the coefficients and the errors in each.

\vskip 0.5cm
{\bf Solution:}
% insert your solution here!


%--------------------------------------------------------------------------
\vskip 1cm
\hrule
{\bf Problem \#4.}

The Newton form of the interpolating polynomial is often the easiest form to
use and a fairly stable way to compute it.  But it is not usually computed
by solving a lower triangular system as you did in Problem 1(c). Instead the
divided difference table is used as explained in the handout on
interpolation. Apply this technique to Problem 1(c) by hand to make sure you
understand it and obtain the same coefficients.

\vskip 0.5cm
{\bf Solution:}
% insert your solution here!
%--------------------------------------------------------------------------


\end{document}

