3
$\begingroup$

When trying to interpolate data points $(t_i,y_i)$, one can use Newton's polynomials which are spanned by the basis of $P_{n-1}$ given by polynomials of the form

$$ t-t_1, (t-t_1)(t-t_2), ..., \prod_{j=1}^{n-1} (t-t_j) $$

So, in the newton basis, an interpolant looks as

$$ \phi_{n-1}(t) = \alpha_1 + \alpha_2(t-t_1) + ... + \alpha_n (t-t_1)(t-t_2)...(t-t_{n-1})$$

now, one can do $\phi_{n-1}(t_i) = y_i $ to find $\alpha_i$ which requires to solve a lower triangular matrix.

Now, if we introduce the notion of divided differences,

$$ f[t_k] = y_k, f[t_1,t_2,...,t_k] = \frac{ f[t_2,t_3,...,t_k] - f[t_1,t_2,...,t_{k-1}] }{t_k-t_1} $$

observe that

$$ \phi_{n-1}(t_1) = \alpha_1 = y_1 = f[t_1] $$

Also,

$$ \phi_{n-1}(t_2) = \alpha_1 + \alpha_2 (t_2 - t_1) = y_2 $$

since $\alpha_1 = y_1$, we observe that $\alpha_2 = \dfrac{ y_2 - y_1 }{t_2 - t_1} = \dfrac{ f[t_2]-f[t_1]}{t_2-t_1} = f[t_1,t_2]$

So, we can claim that in general, $\alpha_k = f[t_1,...,t_k]$. Im trying to prove this by induction but I dont see a plan on how to use the induction hypothesis to check for $\alpha_{k+1}$. We can assume that result holds for $k$ so that we can write the interpolant $\phi_k(t)$ as

$$ \phi_k(t) = f[t_1] + f[t_1,t_2](t-t_1) + ..+ f[t_1,...,t_k] (t-t_1)...(t-t_{k-1}) + \alpha_{k+1} (t-t_1)...(t-t_{k}) $$

but, then how can we take from there?

$\endgroup$
3
$\begingroup$

The subject is better caught using a matricial reperesentation, and it is preferrable to index from $0$, as it provides a neater handling of the sums and products.

Given an assigned sequence $\left\{ {t_{\,0} ,t_{\,1} , \cdots ,t_{\,h} , \cdots } \right\}\quad \left| {\;t_{\,k} \ne t_{\,j} } \right.$, let's indicate by $\pi _{\,n} (t)$ the $n$-th degree polynomial $$ \pi _{\,n} (x,{\bf t}) = \prod\limits_{0\, \le \,j\, \le \,n-1} {\left( {x - t_{\,j} } \right)} $$ so that, with the convention of the null product, we have $$ \pi _{\,0} (x,{\bf t}) = 1\quad \pi _{\,1} (x,{\bf t}) = \left( {x - t_{\,0} } \right)\quad \cdots $$

We want to construct a polynomial of degree $h$ such that at the $h+1$ points $(t_0, \cdots,t_h)$ it takes the values $(f_0, \cdots,f_h)$, that is $$ p_{\,h} \left( {x,{\bf t},{\bf f}} \right)\;:\;\;p_{\,h} \left( {t_{\,k} ,{\bf t},{\bf f}} \right) = f_{\,k} \quad \left| {\,0 \le k \le h} \right. $$ While we could express it in terms of Lagrange polynomials, we want instead
to express it as a linear combination of the $\pi _{\,k} (x,{\bf t})$ polynomials $$ \eqalign{ & p_{\,h} \left( {x,{\bf t},{\bf f}} \right) = \left( {\matrix{ {\pi _{\,0} (x,{\bf t})} & {\pi _{\,1} (x,{\bf t})} & \cdots & {\pi _{\,h} (x,{\bf t})} \cr } } \right)\left( {\matrix{ {\beta _{\,0} } \cr {\beta _{\,1} } \cr \vdots \cr {\beta _{\,h} } \cr } } \right) = \cr & = \overline {{\bf \pi }_{\,h} } (x,{\bf t})\;{\bf \beta }_{\,h} \cr} $$ note that the vector ${\bf \pi }$ includes polynomials of varying degree.

Since the above holds for whichever value of $x$, it shall hold in particular for each $x=t_k$, and we get the LT matrix equation you already know $$ \bbox[lightyellow] { \eqalign{ & \left( {\matrix{ {f_{\,0} } \cr {f_{\,1} } \cr \vdots \cr {f_{\,h} } \cr } } \right) = \left( {\matrix{ 1 & 0 & \cdots & 0 \cr 1 & {\left( {t_1 - t_0 } \right)} & \cdots & 0 \cr \vdots & \vdots & \ddots & \vdots \cr 1 & {\prod\limits_{0\, \le \,j\, \le \,0} {\left( {t_h - t_{\,j} } \right)} } & \cdots & {\prod\limits_{0\, \le \,j\, \le \,h - 1} {\left( {t_h - t_{\,j} } \right)} } \cr } } \right)\left( {\matrix{ {\beta _{\,0} } \cr {\beta _{\,1} } \cr \vdots \cr {\beta _{\,h} } \cr } } \right) = \cr & = {\bf f} = {\bf P}({\bf t})\;{\bf \beta } \cr} }\tag{1}$$

Consider now that the Divided Difference of a sequence $y_k$ wrt $x_k$ $$ \left\{ \matrix{ \left[ {y_{\,q} } \right] = y_{\,q} \hfill \cr \left[ {y_{\,q} ,\, \ldots ,\,y_{\,q + n} } \right] = {{\left[ {y_{\,q + 1} ,\, \ldots ,\,y_{\,q + n} } \right] - \left[ {y_{\,q} ,\, \ldots ,\,y_{\,q + n - 1} } \right]} \over {x_{\,q + n} - x_{\,q} }} \hfill \cr} \right. $$ can be expressed as a linear combination of the $y_k$ values as follows $$ \bbox[lightyellow] { \left[ {y_{\,q} ,\, \ldots ,\,y_{\,q + n} } \right] = \sum\limits_{0\, \le \,m\, \le \,n} {{{y_{m + q} } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m + q} - x_{\,k + q} } \right)} }}} }\tag{2}$$ because in fact, taking $q=0$ wlog, it is $$ \eqalign{ & \left[ {y_{\,1} ,\, \ldots ,\,y_{\,n + 1} } \right] - \left[ {y_{\,0} ,\, \ldots ,\,y_{\,n} } \right] = \cr & = \sum\limits_{0\, \le \,m\, \le \,n} {{{y_{m + 1} } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m + 1} - x_{\,k + 1} } \right)} }}} - \sum\limits_{0\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \sum\limits_{1\, \le \,m + 1\, \le \,n + 1} {{{y_{m + 1} } \over {\prod\limits_{1\, \le \,k + 1\, \ne \,m + 1\, \le \,n + 1} {\left( {x_{\,m + 1} - x_{\,k + 1} } \right)} }}} - \sum\limits_{0\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \sum\limits_{1\, \le \,m\, \le \,n + 1} {{{y_m } \over {\prod\limits_{1\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m} - x_{\,k} } \right)} }}} - \sum\limits_{0\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \sum\limits_{1\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{1\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m} - x_{\,k} } \right)} }}} + {{y_{n + 1} } \over {\prod\limits_{1\, \le \,k\, \le \,n} {\left( {x_{\,n + 1} - x_{\,k} } \right)} }} - {{y_0 } \over {\prod\limits_{1\, \le \,k\, \le \,n} {\left( {x_{\,0} - x_{\,k} } \right)} }} - \sum\limits_{1\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = - {{y_0 } \over {\prod\limits_{1\, \le \,k\, \le \,n} {\left( {x_{\,0} - x_{\,k} } \right)} }} + \sum\limits_{1\, \le \,m\, \le \,n} {y_m \left( {{1 \over {\prod\limits_{1\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m} - x_{\,k} } \right)} }} - {1 \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} \right)} + {{y_{n + 1} } \over {\prod\limits_{1\, \le \,k\, \le \,n} {\left( {x_{\,n + 1} - x_{\,k} } \right)} }} = \cr & = - {{\left( {x_{\,0} - x_{\,n + 1} } \right)y_0 } \over {\prod\limits_{1\, \le \,k\, \le \,n + 1} {\left( {x_{\,0} - x_{\,k} } \right)} }} + \sum\limits_{1\, \le \,m\, \le \,n} {y_m \left( {{{\left( {x_{\,m} - x_{\,0} } \right)} \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m} - x_{\,k} } \right)} }} - {{\left( {x_{\,m} - x_{\,n + 1} } \right)} \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m} - x_{\,k} } \right)} }}} \right)} + {{\left( {x_{\,n + 1} - x_{\,0} } \right)y_{n + 1} } \over {\prod\limits_{0\, \le \,k\, \le \,n} {\left( {x_{\,n + 1} - x_{\,k} } \right)} }} = \cr & = \left( {x_{\,n + 1} - x_{\,0} } \right)\sum\limits_{0\, \le \,m\, \le \,n + 1} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \left( {x_{\,n + 1} - x_{\,0} } \right)\left[ {y_{\,0} ,\, \ldots ,\,y_{\,n + 1} } \right] \cr} $$

Therefore, in matrix notation we will have $$ \bbox[lightyellow] { \eqalign{ & \left( {\matrix{ {\left[ {f_{\,0} } \right]} \cr {\left[ {f_{\,0} ,f_{\,1} } \right]} \cr \vdots \cr {\left[ {f_{\,0} , \ldots ,f_{\,h} } \right]} \cr } } \right) = \left( {\matrix{ 1 & 0 & \cdots & 0 \cr {{1 \over {\left( {t_{\,0} - t_{\,1} } \right)}}} & {{1 \over {\left( {t_{\,1} - t_{\,0} } \right)}}} & \cdots & 0 \cr \vdots & \vdots & \ddots & \vdots \cr {{1 \over {\prod\limits_{0\, \le \,k\, \ne \,0\, \le \,h} {\left( {t_{\,0} - t_{\,k} } \right)} }}} & {{1 \over {\prod\limits_{0\, \le \,k\, \ne \,1\, \le \,h} {\left( {t_{\,1} - t_{\,k} } \right)} }}} & \cdots & {{1 \over {\prod\limits_{0\, \le \,k\, \ne \,h\, \le \,h} {\left( {t_{\,h} - t_{\,k} } \right)} }}} \cr } } \right) \left( {\matrix{ {f_{\,0} } \cr {f_{\,1} } \cr \vdots \cr {f_{\,h} } \cr } } \right) = \cr & = {\bf D}_{\,{\bf div}} ({\bf t})\;{\bf f} \cr} }\tag{3}$$

The crucial point is that $$ \bbox[lightyellow] { {\bf D}_{\,{\bf div}} ({\bf t}) = {\bf P}({\bf t})^{\, - \,{\bf 1}} }\tag{4}$$ which in connection with (1) demonstrates the thesis.

In fact $$ \eqalign{ & \left[ {y_{\,0} ,\, \ldots ,\,y_{\,n} } \right]\quad \left| {\;y = f(x) = \prod\limits_{0\, \le \,j\, \le \,g - 1} {\left( {x - x_{\,j} } \right)} } \right.\quad = \cr & = \sum\limits_{0\, \le \,m\, \le \,n} {{{f\left( {x_m } \right)} \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \left[ {g \le n} \right]\sum\limits_{g\, \le \,m\, \le \,n} {{{f\left( {x_m } \right)} \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \left[ {g \le n} \right]\sum\limits_{g\, \le \,m\, \le \,n} {{{\prod\limits_{0\, \le \,j\, \le \,g - 1} {\left( {x_{\,m} - x_{\,j} } \right)} } \over {\prod\limits_{0\, \le \,k\,\, \le \,g - 1} {\left( {x_{\,m} - x_{\,k} } \right)} \prod\limits_{g\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \left[ {g \le n} \right]\sum\limits_{g\, \le \,m\, \le \,n} {{1 \over {\prod\limits_{g\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m} - x_{\,k} } \right)} }}} = \cr & = \left[ {g \le n} \right]\sum\limits_{0\, \le \,m\, \le \,n - g} {{1 \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n - g} {\left( {x_{\,m + g} - x_{\,k + g} } \right)} }}} = \cr & = \left[ {g \le n} \right]\left[ {1_{\,g} ,\, \ldots ,\,1_{\,g + \left( {n - g} \right)} } \right] = \left[ {g = n} \right] \cr} $$ where the second step follows from being $f(x_m)=0$ for $m<g$ and where $[g \le n],\,[g = n]$ denotes the Iverson bracket.

$\endgroup$
2
$\begingroup$

I would like to show how the missing induction step can be carried out. We have $n+1$ distinct nodes $x_0, x_1, \dotsc, x_n$. Let $p$ denote the polynomial of degree at most $n-1$ which interpolates $f$ at the first $n$ nodes, i.e., $x_0, x_1, \dotsc x_{n-1}$. Then by our induction hypothesis $$p(x) = f[x_0,x_1,\dotsc,x_{n-1}] x^{n-1} + r(x)$$ where $r$ is a polynomial of degree at most $n-2$. Let $q$ denote the polynomial of degree at most $n-1$ which interpolates $f$ at the last $n$ nodes, i.e., $x_1, x_2, \dotsc x_n$. Then by our induction hypothesis $$q(x) = f[x_1,x_2,\dotsc,x_n] x^{n-1} + s(x)$$ where $s$ is a polynomial of degree at most $n-2$. Now, consider the polynomial $t$ given by $$t(x) = p(x)\frac{x_n-x}{x_n-x_0} + q(x)\frac{x-x_0}{x_n-x_0}$$ I claim that $t$ is unique polynomial which interpolates $f$ at all $n+1$ nodes. We have $$ t(x_0) = p(x_0) \cdot 1 + q(x_0) \cdot 0 = p(x_0) = f(x_0),$$ because $p$ interpolates $f$ at $x_0$. We have $$ t(x_n) = p(x_n) \cdot 0 + q(x_n) \cdot 1 = q(x_n) = f(x_n),$$ because $q$ interpolates $f$ at $x_n$. For $1<i<n$ we have $$ t(x_i) = q(x_i)\left(\frac{x_n-x_i}{x_n-x_0}\right) + q(x_i)\left(\frac{x_i-x_0}{x_n-x_0}\right) = f(x_i) \frac{(x_n-x_i) + (x_i-x_0)}{x_n-x_0} = f(x_i),$$ because $p$ and $q$ both interpolate $f$ at $x_i$. This shows that $t$ is the polynomial of degree at most $n$ which interpolates $f$ at the $n+1$ nodes. We have $$t(x) = c_n t^n + u(x)$$ where $c_n$ is a constant and $u$ is a polynomial of degree at most $n-1$. The formula for $c_n$ follows readily from the expressions for $p$, $q$ and $t$. We have \begin{align} t(x) &= \frac{\Big(f[x_1,x_2,\dotsc,x_n]x^{n-1} +r(x)\Big)(x-x_0) - \Big(f[x_0,x_1,\dotsc,x_{n-1}]x^{n-1}+s(x)\Big)(x-x_n)}{x_n-x_0} \\ &= \left(\frac{f[x_1,x_2,\dotsc,x_n]-f[x_0,x_1,\dotsc,x_{n-1}]}{{x_n-x_0}} \right) x^n + \text{lower order terms.} \end{align} We see that the choice of $$ f[x_0,x_1,\dots,x_n] = \frac{f[x_1,x_2,\dotsc,x_n]-f[x_0,x_1,\dotsc,x_{n-1}]}{{x_n-x_0}}$$ is exactly what is needed to complete our induction step.


The construction of $t$ in terms of $p$ and $q$ is the foundation for Neville's algorithm for evaluating the interpolating polynomial.

$\endgroup$

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.