6.2 Neville’s method
Often we want only the value \(P(x)\) at one point, and we do not know in advance how many nodes are needed. Neville’s method builds the value up recursively from interpolants on fewer points. Let \(P_{m_1,m_2,\dots ,m_k}\) denote the polynomial interpolating \(f\) at the nodes \(x_{m_1},\dots ,x_{m_k}\).
Theorem 6.2.1. Let \(x_i\neq x_j\) be two of the nodes \(x_0,\dots ,x_k\). Then \[P(x) = \frac {(x-x_j)P_{0,\dots ,j-1,j+1,\dots ,k}(x)-(x-x_i)P_{0,\dots ,i-1,i+1,\dots ,k}(x)}{x_i-x_j}\] is the polynomial interpolating \(f\) at all of \(x_0,\dots ,x_k\).
Proof. Write \(Q = P_{\dots \hat j\dots }\) (omitting \(x_j\)) and \(\hat Q = P_{\dots \hat i\dots }\) (omitting \(x_i\)). The right-hand side has degree at most \(k\). At a node \(x_r\) with \(r\neq i,j\), both \(Q\) and \(\hat Q\) equal \(f(x_r)\), so the right-hand side is \(\frac {(x_r-x_j)-(x_r-x_i)}{x_i-x_j}f(x_r) = f(x_r)\). At \(x_i\) it is \(\frac {(x_i-x_j)Q(x_i)}{x_i-x_j} = f(x_i)\), and at \(x_j\) it is \(\frac {-(x_j-x_i)\hat Q(x_j)}{x_i-x_j} = f(x_j)\). By uniqueness it is the interpolating polynomial. □
Writing \(Q_{i,j}\) for the polynomial interpolating at the \(j+1\) consecutive nodes \(x_{i-j},\dots ,x_i\), the theorem gives Neville’s method: \[Q_{i,0} = f(x_i),\qquad Q_{i,j}(x) = \frac {(x-x_{i-j})Q_{i,j-1}(x)-(x-x_i)Q_{i-1,j-1}(x)}{x_i-x_{i-j}} .\] The entries are computed row by row; each new row uses one more node, and the agreement of successive entries indicates the accuracy.
Example 6.2.2. The table gives values of the Bessel function \(J_0\) (the solution of \(xy''+y'+xy = 0\) with \(y(0) = 1\)). Use Neville’s method to approximate \(f(1.5)\).
| \(x\) | \(1.0\) | \(1.3\) | \(1.6\) | \(1.9\) | \(2.2\) |
| \(f(x)\) | \(0.7651977\) | \(0.6200860\) | \(0.4554022\) | \(0.2818186\) | \(0.1103623\) |
Solution. For example \(Q_{1,1}(1.5) = \frac {(1.5-1.0)(0.6200860)-(1.5-1.3)(0.7651977)}{1.3-1.0} = 0.5233449\). The full table is
| \(x_i\) | \(Q_{i,0}\) | \(Q_{i,1}\) | \(Q_{i,2}\) | \(Q_{i,3}\) | \(Q_{i,4}\) |
| \(1.0\) | \(0.7651977\) | ||||
| \(1.3\) | \(0.6200860\) | \(0.5233449\) | |||
| \(1.6\) | \(0.4554022\) | \(0.5102968\) | \(0.5124715\) | ||
| \(1.9\) | \(0.2818186\) | \(0.5132634\) | \(0.5112857\) | \(0.5118127\) | |
| \(2.2\) | \(0.1103623\) | \(0.5104270\) | \(0.5137361\) | \(0.5118302\) | \(0.5118200\) |
The last two columns agree to about \(2\times 10^{-5}\), and \(Q_{4,4}(1.5) = 0.5118200\); the true value is \(J_0(1.5) = 0.5118277\).
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.