\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}}

\def\nl{\vphantom\vdots\\}

\begin{document}

\title{Numerical Methods I -- Problem Set 7}
\author{Fall Semester 2005}
\date{Due November 4}

\maketitle


\begin{enumerate}

\item Let $f$ be twice continuously differentiable and let $s_L$ be
the linear spline that interpolates $f$ at a set of equidistant knots
$x_i=x_0+ih$ where $i=0,\dots,n$.  Show that
\[
  |f(x) - s_L(x)| \leq \frac18 \, h^2 \, \max_{\xi\in[x_0,x_n]}
   |f''(\xi)|
\]
for any $x\in [x_0,x_n]$.

\emph{Hint:} Notice that a linear spline is determined by Lagrange
interpolation on the interval between two nodes.  Hence, use the error
estimate for Lagrange interpolation from the lecture.

\item (From SM.)  An interpolating spline of degree $n$ has prescribed
values at the knots, and is required to have $n-1$ continuous
derivatives.  How many additional conditions are required to specify
the spline uniquely?

\item A so-called \emph{clamped spline} is a cubic interpolating
spline with specified values of the first derivative at the first and
the last knot.  In the following, consider equidistant knots $x_i=i$,
$i=0,\dots, n$.  We write
\[
  s_i(x) = a_i \, (x-x_i)^3 + b_i \, (x-x_i)^2 + c_i \, (x-x_i) +
  d_i
\]
to denote the spline function on the $i$th interval;  $y_i$, $y_i'$,
and $y_i''$ denote the value of the spline, and its first and second
derivative at the $i$th node, respectively.

\begin{enumerate}

\item Show that
  \begin{gather*}
    a_i = 2 \, (y_{i-1} - y_i) + y_i' + y_{i-1}' \,, \\
    b_i = 3 \, (y_{i-1} - y_i) + 2 \, y_i' + y_{i-1}' \,, \\
    c_i = y_i' \,, \\
    d_i = y_i \,.
  \end{gather*}
  
\item Conclude from part (a) that
  \[
  \begin{pmatrix}
    4 & 1 & & & \cdots & 0 \nl
    1 & 4 & 1 & & & \vdots \nl
      & 1 & 4 & 1 \nl
      & & \ddots & \ddots & \ddots \nl
    \vdots & & & 1 & 4 & 1 \nl
    0 & \cdots & & & 1 & 4 \nl
  \end{pmatrix}
  \begin{pmatrix}
    y_1' \nl y_2' \nl y_3' \nl \vdots \nl y_{n-2}' \nl y_{n-1}' \nl
  \end{pmatrix}
  = 3 
  \begin{pmatrix}
    y_2 - y_0 \nl
    y_3 - y_1 \nl
    y_4 - y_2 \nl
    \vdots \nl
    y_{n-1} - y_{n-3} \nl
    y_n - y_{n-2}  \nl
  \end{pmatrix}
  -
  \begin{pmatrix}
    y_0' \nl 0 \nl 0 \nl \vdots \nl 0 \nl y_n'
  \end{pmatrix} \,.
  \]

\end{enumerate}


\item \textbf{Project:} Solve the above system of linear
equations for $n=10$, $y_i=0$ for all $i=0,\dots,10$, $y_{10}'=0$, and
$y_0' = a$.  Plot the resulting spline function.  How does the spline
depend on the value of $a$?


\item \textbf{Project:} Modify your \textsf{Octave} code from
Homework~6 to use the Chebycheff nodes
\[
  x_i = 5 \, \cos \frac{i \, \pi}{n}
\]
where $i=0,\dots,n$, rather than equidistant nodes, when computing the
Lagrange polynomial for the function
\[
  f(x) = \frac1{1+x^2} \,.
\]
on the interval $[-5,5]$.  What difference does it make?

\end{enumerate}
\end{document}
