\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amsfonts}

\newcommand{\x}{\boldsymbol{x}}
\renewcommand{\v}{\boldsymbol{v}}
\newcommand{\w}{\boldsymbol{w}}
\renewcommand{\r}{\boldsymbol{r}}
\renewcommand{\a}{\boldsymbol{a}}
\renewcommand{\b}{\boldsymbol{b}}
\renewcommand{\c}{\boldsymbol{c}}
\newcommand{\e}{\boldsymbol{e}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\Range}{\operatorname{Range}}
\newcommand{\Ker}{\operatorname{Ker}}
\newcommand{\Span}{\operatorname{Span}}
\renewcommand{\dim}{\operatorname{dim}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}


\begin{document}

\title{Numerical Methods I}
\author{Problem Set 6}
\date{due in class, October 29, 2003}
\maketitle


\begin{enumerate}

\item It can be shown that the Conjugate Gradient (CG) method in the
absence of rounding errors terminates after at most $n$ steps,
yielding the exact solution.  Compare the number of operations for
solving a system of linear equations via $LU$ decomposition with the
number of operations for $n$ iterations of CG.

\emph{Remark:} Since $A$ must be symmetric and positive definite for
CG to be applicable, it is actually possible to half the number of
operations required for the $LU$ decomposition by using the so-called
Cholesky decomposition.  However, this does not change the overall
picture.  For background information, see SM, pp.~90--93.

\item \textbf{Project:} Modify your \textsf{Octave} code from
Homework~5 to use the Conjugate Gradient rather than the simple
Gradient method.  How do the two methods compare for the given test
problem?

\item
\begin{enumerate}
\item
Compute the Lagrange polynomial which interpolates a function
$f$ at three distinct nodes $x_0$, $x_1$, and $x_2$.
\item Use the result from part (a) to derive approximations for
$f'(x_1)$ and $f''(x_1)$.

\item Simplify the formulas from (b) for the case of equidistant
nodes.
\end{enumerate}

\item (From SM.)  Given a set of points
\[
  (x_0, y_0), (x_1, y_1), \dots, (x_{n+1},y_{n+1})
\]
with distinct $x_1,\dots,x_{n+1}$, let $q$ be the Lagrange polynomial
of degree $n$ interpolating the points with index $i=0,\dots,n$, and
let $r$ be the Lagrange polynomial of degree $n$ interpolating the
points with index $i=1,\dots,n+1$.  Show that the Lagrange polynomial
of degree $n+1$ interpolating all $n+2$ points is given by
\[
  p(x) = \frac{(x-x_0)\, r(x) - (x-x_{n+1}) \, q(x)}{x_{n+1}-x_0} \,.
\]

\item \textbf{Project:} (Runge's example.) Apply Lagrange
interpolation with $n$ equidistant interpolation points on the
interval $[-5,5]$ to the function
\[
  f(x) = \frac1{1+x^2} \,.
\]
Plot $f$ and the Lagrange polynomial $p_n$ for different values of
$n$. How does the error behave as $n$ increases?

\end{enumerate}
\end{document}
