Interpolation: Divided Differences
\(P_n(x) = a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1) + \cdots + a_n(x-x_0)(x-x_1)\cdots(x-x_{n-1})\)
\[ \class{emph}{\begin{bmatrix} 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & (x_1-x_0) & 0 & \cdots & 0 & 0\\ 1 & (x_2-x_0) & (x_2-x_0)(x_2-x_1) & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & (x_{n-1}-x_0) & (x_{n-1}-x_0)(x_{n-1}-x_1) & \cdots & \prod_{j-0}^{n-2}(x_{n-1}-x_j) & 0\\ 1 & (x_n-x_0) & (x_n-x_0)(x_n-x_1) & \cdots & \prod_{j=0}^{n-2}(x_n - x_j) & \prod_{j=0}^{n-1}(x_n-x_j)\\ \end{bmatrix}} \begin{bmatrix} a_0\\a_1\\a_2\\\vdots\\a_{n-1}\\a_n \end{bmatrix} = \class{emph}{\begin{bmatrix} y_0\\y_1\\y_2\\\vdots\\y_{n-1}\\y_n \end{bmatrix}} \]
\(P_n(x) = P_{n-1}(x) + a_n(x-x_0)(x-x_1)(x-x_2)\cdots (x-x_{n-1})\)
Given \(n+1\) points \((x_0,y_0)\), \((x_1, y_1)\), …, \((x_n, y_n)\) with \(x_i\)’s all distinct.
Suppose \(S\) is a non-empty subset of \(\{0,1,2,\ldots,n\}\), denote \(\left\lvert S\right\rvert\) the cardinality of \(S\).
Let \(P_S\) be the unique polynomial of degree at most \(\left\lvert S\right\rvert - 1\) that interpolates the points \(\{(x_i,y_i)\mid i \in S\}\).
Given \(i \not\in S\), the result from the previous slide:
\(P_n(x) = P_{n-1}(x) + a_n(x-x_0)(x-x_1)(x-x_2)\cdots (x-x_{n-1})\)
can be written as
\[P_{S\cup\{i\}}(x) = P_S(x) + a_{S,i} \prod_{j\in S} (x - x_j)\]
Let \(0 \le j \le k \le n\), and consider the set \(S = \{j,j+1,j+2,\ldots,k\}\).
We get the following:
So far we got
\[A(x_{k+1}-x_{j})\cdots(x_{k+1}-x_{k}) = {\color{green}\left(y_{k+1} - P_{\{j+1,\dots,k\}}(x_{k+1})\right)} - a(x_{k+1}-x_{j+1})(x_{k+1}-x_{j+2})\cdots(x_{k+1}-x_{k})\]
\[P_{\{j+1, j+2, \ldots, k, k+1\}}(x) = P_{\{j+1,\dots,k\}}(x) + c(x-x_{j+1})(x-x_{j+2})\cdots(x-x_k)\]
\[y_{k+1} = P_{\{j+1,\dots,k\}}(x_{k+1}) + c(x_{k+1}-x_{j+1})(x_{k+1}-x_{j+2})\cdots(x_{k+1}-x_k)\]
\[\begin{aligned} A(x_{k+1}-x_{j})\cdots(x_{k+1}-x_{k}) &= {\color{green}c(x_{k+1}-x_{j+1})(x_{k+1}-x_{j+2})\cdots(x_{k+1}-x_k) }\\ &\quad {} - a(x_{k+1}-x_{j+1})(x_{k+1}-x_{j+2})\cdots(x_{k+1}-x_{k})\\ &= (c - a)(x_{k+1}-x_{j+1})(x_{k+1}-x_{j+2})\cdots(x_{k+1}-x_{k}) \end{aligned}\]
\[A = \frac{(c - a)(x_{k+1}-x_{j+1})(x_{k+1}-x_{j+2})\cdots(x_{k+1}-x_k)}{(x_{k+1}-x_{j})(x_{k+1}-x_{j+1})(x_{k+1}-x_{j+2})\cdots(x_{k+1}-x_{k})} = \frac{c-a}{x_{k+1} - x_j}\]
\[A = \frac{c-a}{x_{k+1} - x_j}\]
where:
Notation:
These are called divided differences.
Given \(n+1\) points \((x_0,f(x_0))\), \((x_1, f(x_1))\), …, \((x_n, f(x_n))\) with \(x_i\)’s all distinct.
Define
\[ \begin{aligned} f[x_k] &= f(x_k) \text{ for } k = 1, 2, \ldots, n\\ f[x_j,\ldots,x_k] &= \frac{f[x_{j+1},\ldots,x_k] - f[x_j,\ldots,x_{k-1}]}{x_k - x_j} \text{ for } 0 \le j < k \le n \end{aligned} \]
Then the Newton’s form of interpolating polynomial is
\(P_n(x) = a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1) + \cdots + a_n(x-x_0)(x-x_1)\cdots(x-x_{n-1})\)
where \(a_k = f[x_0,\ldots,x_k]\) for \(k = 0, 1, \ldots, n\).
Find a polynomial \(p\) of degree 2 such that \(p(-1) = 11\), \(p(1) = -1\), and \(p(2) = 2\).