0
$\begingroup$

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:enter image description here

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?

$\endgroup$
0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Ah this makes so much sense now! I feel sorta silly for have asked. Thank you! $\endgroup$ – Taln Feb 23 '18 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.