
%\documentstyle{siam}
\documentclass[final,psfrag,twoside,epsfrag]{article}
\input{zmacros}
\textwidth 6.4in
\textheight 9in
\oddsidemargin -0.3in
\evensidemargin -0.3in
\topmargin -.5in

%\input{zmacros.tex}
\def\be{\begin{enumerate}}
\def\ee{\end{enumerate}}
%\newcommand{\vthin}{\vskip 5pt}


\pagestyle{empty}
\begin{document}
\hfill\vbox{\hbox{MA 780}\hbox{Homework \#1}
\hbox{\bf Due January 27}}
\vskip .2in
\baselineskip 14pt


\be
\vthin
\item  Let $A$ be the Vandermonde matrix generated by $\{ x_i\}$,
$i=0,\cdots,n$. Show that
\eqmno
det(A) = \prod_{0 \le j < i \le n} (x_i-x_j),
\enmno
and the solution of the polynomial interpolation exists and is unique if $x_i$'s   are  distinct.   
{\bf Hint:} Use mathematical induction and consider the determinant of the
following:
\eqmno
det \left |\begin {array}{ccccc}
 1 &  x_0&\cdots& x_0^n & x_0^{n+1} \\\noalign{\medskip}
1 & x_1&\cdots& x_1^n & x_1 ^{n+1} \\\noalign{\medskip}
\vdots&\vdots&\vdots&\vdots & \vdots \\\noalign{\medskip}
1 & x_n&\cdots& x_n^n & x_n ^{n+1} \\\noalign{\medskip}
1 &  x & \cdots& x^n & x^{n+1} \end
{array}\right | = \phi(x).
\enmno
It is easy to spot $n$ roots of $\phi(x)$ (if two rows are the same).
Write down the factorized form
of $\phi(x)$ and then use the induction to find the coefficient of
$x^{n+1}$. Finally, you can plug  $x_{n+1}$ in to $\phi(x)$ to get the desired
result.

\vthin
\item Let the nodal points be $x_i =0, \pi/6, \pi/4$, and the function
values be $y_i=\sin(x_i)$.
\be

\item Find the least squares approximation using $y= a_0 + a_1 x$.  How is the solution  defined?

\item Suppose that we use $y= a_0 + a_1 x + a_2 x^2 + a_3 x^3$. How to find the coefficients? How is the solution  defined?


\item
Find  {\em both} the Lagrange polynomial and Newton polynomial
interpolations. Show the two results are the same. Approximate $y(x)$
at $x=\pi/8$ and find the error $|\sin (\pi/8)-p_2(\pi/8)|$.
\item Give a least upper bound of the error $\dsp
\max_{0 \le x \le \pi/4} |\sin x - p_2(x)|$.
\ee
{\bf Hint:} Use the error estimate and notice that $|\cos x |\le 1$, find
the maximum/minimum of $\omega(x)$ between $0$ and $\pi/4$.

\vthin
\item Let $l_i(x)$ be the Lagrange polynomials, show the following:
\eqmno
&& \sum_{i=0}^n x_i^k l_i(x) = x^k, \qquad k=0,1,\cdots, n;  \\
&& \sum_{i=0}^n (x_i - x)^k l_i(x) = 0, \qquad k=1,2, \cdots, n.
\enmno
{\bf Hint:} For the second equality, use the binomial  expansion of  $(x_i - x)^k$ and make use
of  the first equality.  Note that $\dsp (a-b)^m = \sum_{k=0}^m (-1)^k C_m^k  a^{m-k} b^k$. 

\vthin
\item Use simple method to find the following divided differences:
\be
\item $f[2^0,2^1,\cdots,2^7]$ if $f(x)=x^7 + x^3 + 1$.
\item $f[2^0,2^1,\cdots,2^7,2^8]$ if $f(x)=x^7 + x^3 + 1$.
\item $f[x_0,x_1,x_2,\cdots,x_p]$ if
$\dsp f(x)=\omega_{n+1}(x)=\prod_{i=0}^n (x-x_i)$ assuming $p\le n$.
\ee
{\bf Hint:} Use  %(8.21) on page 343 and (8.18) on page 341.
\eqmno
  f[x_0,x_1,\cdots,x_n,x] = \frac{f^{(n+1)}(\xi) }{(n+1)!} \qquad  f[x_0,x_1,\cdots,x_n] =\sum_{i=0}^n \frac{f(x_i) }{ \omega'_{n+1}(x_i)  } .
\enmno

\vthin
\item Programming Part: Implement the Newton interpolation formula (see
the code on the class web-page, and Program 66 on page 342),
debug/test your code, and analyze your results.
\bi
\item Use $\{ \, 0, 0.1, 0.2, \cdots 0.9, 1 \, \}$ as nodal points.
\item Use $\left \{ \, \fr{k}{1000} \right \}, k=0, 1, \cdots, 1000$ as
output points.
\item Plot the exact solution and the approximation from the
polynomial interpolation on the same plot.

\item If you use Matlab, run Matlab function {\em interp1} and compare the
CPU time ({\em Matlab function cputime}).
{\bf Hint:} In Matlab, type {\em help interp1} and
{\em help cputime} for the usage. If the CPU numbers are too small, \emph{use format short e}.
\item Plot the error plot. You should label, title all the plots. You can
use Matlab command: {\em subplot} to put multiple plots into a single
paper.
\item Do the test for the following functions:
\be
\item f(x) = $e^x$.
\item $f(x) = \cos(10 \pi x)$.
\item $f(x) = \dsp \fr{1}{ 1 + 25 x^2}$
\ee
\ei
You should keep you code for late use. Note that: you need to submit your results and analysis, selected plots, along with your homework. Your programming code should be submitted to Moodle. 
\ee
\end{document}
