\documentclass[11pt]{article}


\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{yfonts}
\input epsf
\usepackage [usenames,dvipsnames]{color}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\F}{\mathbb F}
\newcommand{\pa}{\partial}
\renewcommand{\P}{\mathcal P}
\newcommand{\cL}{\mathcal L}
\renewcommand{\O}{\Omega}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\def\ds{\displaystyle}
\def\ul{\underline}
\def\mb{\mathbf}
\usepackage{graphicx}
\usepackage{tikz}
\oddsidemargin=-0.0cm
\evensidemargin=-0.0cm
\topmargin=-0.0cm
\textwidth=7in
\textheight=9in
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}
\newtheorem{problem}{Problem}
\def\ds{\displaystyle}
\def\ul{\underline}
\def\mb{\mathbf}

\DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it}


\def\ds{\displaystyle}
\def\ul{\underline}


\newenvironment{solution}
  {\begin{proof}[Solution]}
  {\end{proof}}



%\textfrak{This: is: Fraktur}

%\textswab{This: is: Schwabacher}

%\textgoth{This: is: Gothic}




\title{\textgoth{Divided Differences}}
\pagestyle{myheadings}
\author{}
\date{}


\begin{document}
\maketitle
%\markboth{464 final}{464 final}
%{\color{red} stuff}


This document will discuss general divided differences.  A formula for Herite
interpolation will be derived. 

Let values of a function $f$ be given: $f(x_0), f(x_1), \dots, f(x_n)$, or
generally pairs $(x_j, y_j)$. First assume that $x_i\ne x_j$ if $i\ne j$. 
Define by induction,
\begin{align*}
f[x_j]&=f(x_j)\\
 [y_j]&=y_j\\
f[x_j,\dots, x_{j+k+1}] &= \frac{f[x_{j+1}, \dots, x_{j+k+1}] 
-f[x_j,\dots, x_{j+k}]}{x_{j+k+1}-x_j}\\
[y_j,\dots, y_{j+k+1}] &= 
\frac{[y_{j+1},\dots, y_{j+k+1}]- [y_j,\dots,y_{j+k}]}{x_{j+k+1}-x_j}.
\end{align*}

\begin{proposition}
Let 
\[
p_n(x) = [y_0]+[y_0,y_1](x-x_0)+ \dots + [y_0,\dots, y_n](x-x_0)(x-x_1)\dots
(x-x_{n-1}).
\]
Then $p_n$ is the unique polynomial of degree $n$ such that $p(x_j)=y_j, 
j=0,\dots , n$.
\end{proposition}
\begin{proof}
The proof is by induction.  It is true when $n=0$. It is clear, by induction,
that 
\[
p_{n-1}(x_j)= y_j, j=0,\dots, n-1. 
\]
Let $P$ be the interpolating polynomial.  Then $P(x_j)-p_{n-1}(x_j)=0, 
j=0,\dots, n-1$, so $P-p_{n-1}=c(x-x_0)\dots )(x-x_{n-1})$. Hence $c$ is the 
coefficient of  $x^n$ in $P$.  $P$ is unique and can be represented in 
another way.  Let $u,v$ be the polynomials of degree $n-1$ that interpolate at
$x_0, \dots, x_{n-1}$ and $x_1, \dots, x_n$ respectively.  By uniqueness
\[
P=\frac{(x-x_0)v+(x_n-x)u}{x_n-x_0},
\]
hence the coefficient of $x^n$ in $P$ is 
\[
\frac{[y_1,\dots, y_n]-[y_0,\dots,y_{n-1}]}{x_n-x_0}.
\]
\end{proof}

\begin{remark}
If $\sigma$ is a permutation,
\[
[x_0,x_1,\dots, x_n]=[x_{\sigma(0)},x_{\sigma(1)},\dots, x_{\sigma(n)}].
\]
\begin{proof}
The coefficients in the interpolating polynomial are unique. No matter how we
order the points, the leading term 
$(x-x_0)(x-x_1)\dots(x-x_n)=(x-x_{\sigma(0)})\dots(x-x_n)$.  The result 
follows. 
\end{proof}
\end{remark}
\begin{remark}
\begin{align*}
[x_0,x_1,\dots, x_n]=&\frac{y_0}{(x_0-x_1)(x_0-x_2) \dots (x_0-x_n)}+
\frac{y_1}{(x_1-x_0)(x_1-x_2)\dots (x_1-x_n)}+\dots\\ 
&+\frac{y_n}{(x_n-x_0)(x_n-x_1)\dots (x_n-x_{n-1})}.
\end{align*}
\end{remark}
\begin{proof}
The proposition implies that the coefficient of $x^n$ in the interpolating 
polynomial is $[y_0,y_1,\dots, y_n]$.   The result follows by computing
the coefficient of
$x^n$ in the Lagrange form of the interpolating polynomial
\begin{align*}
\frac{y_0(x-x_1)(x-x_2)\dots (x-x_n)}{(x_0-x_1)(x_0-x_2)\dots (x_0-x_n)}+
\dots + 
\frac{y_n(x-x_0)(x-x_1)\dots (x-x_{n-1})}{(x_n-x_0)(x_n-x_1)
\dots (x_n-x_{n-1})}.
\end{align*}
\end{proof}

Now we consider the problem of finding the polynomial that interpolates
derivative data. To simplify notation consider the special case of finding
the polynomial $p$ of degree $7$ that satisfies
\[
p(x_0)=y_{00}, p^{(k)}(x_1)=y_{1k},k=0\dots, 3, p^{j}(x_2)=y_{2j}, 
j=0\dots 2.
\]
By using linear independence of the terms in this expression  
we see that every polynomial of degree $8$ is uniquely expressible in the form
\begin{align*} p(x)=& a_0+b_0(x-x_0)+b_1(x-x_0)(x-x_1)+b_2(x-x_0)(x-x_1)^2\\
&+ b_3(x-x_0)(x-x_1)^3 + b_4(x-x_0)(x-x_1)^4 + c_0(x-x_0)(x-x_1)^4(x-x_2)\\
&+c_1(x-x_0)(x-x_1)^4(x-x_2)^2.
\end{align*}
This can be proved, starting with $a_0$, by differentiating and evaluating. 
We want to find a formula for the coefficients. We consider the 
following matrix 
\[
\begin{matrix}
x_0&x_1&x_1&x_1&x_1&x_2&x_2&x_2\\
y_{00}&y_{10}&y_{10}&y_{10}&y_{10}&y_{20}&y_{20}&y_{20}
\end{matrix}
\]
We define 
\[
[p(x_0)]=y_{10}=p(x_0)=y_0,[p(x_1)]=y_{10}=p(x_1)=y_1, 
[p(x_2)]=y_{20}=p(x_2)=y_2.
\]
Next 
\begin{align*}
[y_0,y_1]=[p(x_0),p(x_1)] =&\frac{[p(x_1)]-[p(x_0)]}{x_1-x_0}, 
[y_1,y_1]=[p(x_1),p(x_1)]=y_{11}\\ 
[y_1,y_2]=[p(x_2),p(x_1)] =& \frac{[p(x_2)]-[p(x_1)]}{x_2-x_1}, 
[y_2,y_2]=[p(x_2),p(x_2]= y_{21}
\end{align*}
Continuing,
\begin{align*}
[y_0,y_1,y_1]=&\frac{[y_1,y_1]-[y_0,y_1]}{x_1-x_0}, [y_1,y_1,y_1]=y_{12}\\
[y_1,y_1,y_2]=&\frac{[y_1,y_2]-[y_1,y_1]}{x_2-x_1}, 
[y_1,y_2,y_2]=\frac{[y_2,y_2]-[y_1,y_2]}{x_2-x_2}\\
[y_2,y_2,y_2]=& y_{22}
\end{align*}
This pattern continues, in particular
\[
[y_1,y_1,y_1,y_1]= y_{13}
\]
\begin{theorem}
The coefficients of terms of the form 
\[
(x-x_0)^j(x-x_1)^k(x-x_2)^{\ell}
\]
are 

\[
[y_0,y_1,y_1,\dots, y_2,y_2, \dots,y_2].
\]
Explicitly
\begin{align*}
a_0=&[y_0], b_0=[y_0,y_1], b_1=[y_0,y_1,y_1], b_2=[y_0, y_1, y_1,y_1]\\
b_3=&[y_0,y_1,y_1,y_1,y_1], c_0=[y_0,y_1,y_1,y_1,y_1,y_2], 
c_1=[y_0,y_1,y_1,y_1,y_1,y_2,y_2],\\
 c_2=&[y_0,y_1,y_1,y_1,y_1,y_2, y_2,y_2].
\end{align*}

\end{theorem}
%\bibliographystyle{amsplain}
%\bibliography{header}

\end{document}
