I am struggling to understand the Hermite interpolation algorithm using divided differences. I am reading from Pg.23/24 here
In their notation, $m_j$ denotes the
"number of derivatives that we have to interpolate for each point $x_j$"
So, for example, $m_0$ is the number of derivatives that we have to interpolate for the point $x_0$.
Then they write We let $n$ denote the total number of points including their multiplicities
Okay, this I understand. However, their next line is what confuses me:
Why do they have $m_1, m_2, \cdots , m_{\ell}$ as underbraces there? Don't the $m_j$ variables denote the number of derivatives that we have to interpolate for the $x_j$ point? In the following example, you can see my confusion.
Then they say the interpolation polynomial is $p_{n-1}(x) = f[y_0] + \sum_{j=1}^{n-1}f[y_0, \cdots, y_j] \prod_{k=0}^{j-1}(x - y_k)$
I want to walk through their $2.18$ example of finding the interpolating polynomial that satisfies $p(x_0) = f(x_0), p(x_1) = f(x_1), \; p'(x_1) = f'(x_1)$.
So we have two nodes $x_0, x_1$. We have zero derivatives that we have to interpolate at $x_0$ so $m_1 = 0$. There is one derivative that we have to interpolate at $x_1$ so $m_2 = 1$. $n$ is suppose to be the total number of points including their multiplicities so $n = 3$, but from my logic it should be equal to only $1$ since $n = m_1 + m_2$.
What is going on?
The zeroth derivative counts as a derivative we have to interpolate. You knew that from the fact that Lagrange interpolation works. Also there is a typo; it should be: $$\{y_0,\dots,y_{n-1}\}=\{\underbrace{x_0,\dots,x_0}_{m_0},\underbrace{x_1,\dots,x_1}_{m_1},\dots,\underbrace{x_{\ell},\dots,x_{\ell}}_{m_{\ell}}\}$$ Having fixed up that possibly confusing typo in your text, we have to interpolate the function at $x_0$, so $m_0=1$. Then we have to interpolate both the function and its first derivative at $x_1$. so $m_1=2$. In general, if you have to interpolate the function and its first $n$ derivatives at $x_j$, then $m_j=n+1$. There is also a typo in your last formula. It should read: $$p_{n-1}(x)=f[y_0]+\sum_{j=1}^{n-1}f[y_0,\dots,y_j]\prod_{k=0}^{j-1}(x-x_k)$$ So we take divided differences: $$\begin{align}f[y_0]&=y(x_0)=y_0\\ f[y_0,y_1]&=\frac{y(x_1)-y(x_0)}{x_1-x_0}=\frac{y_1-y_0}{x_1-x_0}\\ f[y_2,y_1]&=\lim_{x\rightarrow x_1}\frac{y(x)-y(x_1)}{x-x_1}=y^{\prime}(x_1)=y_1^{\prime}\\ f[y_0,y_1,y_2]&=\frac{f[y_2,y_1]-f[y_1,y_0]}{x_2-x_0}=\frac{y_1^{\prime}-\frac{y_1-y_0}{x_1-x_0}}{x_1-x_0}=\frac{(x_1-x_0)y_1^{\prime}-y_1+y_0}{(x_1-x_0)^2}\\ p_2(x)&=y_0+\frac{y_1-y_0}{x_1-x_0}(x-x_0)+\frac{(x_1-x_0)y_1^{\prime}-y_1+y_0}{(x_1-x_0)^2}(x-x_0)(x-x_1)\end{align}$$ So let's check it out: $$\begin{align}p_2(x_0)&=y_0+0+0\\ p_2(x_1)&=y_0+(y_1-y_0)+0=y_1\\ p_2^{\prime}(x_1)&=0+\frac{y_1-y_0}{x_1-x_0}+\frac{(x_1-x_0)y_1^{\prime}-y_1+y_0}{x_1-x_0}=y_1^{\prime}\end{align}$$ So it looks good!