Burden & Faires, 9th Ed. - §3.1–3.2

Chapter 5: Lagrange Interpolation & Neville's Method

Existence & uniqueness · Lagrange basis polynomials · Interpolation error · Neville's iterated algorithm · Runge's phenomenon

Interpolation answers a different question than root-finding: given a handful of data points, what single polynomial passes through all of them - and how much can we trust its value between the points we know? This chapter builds the Lagrange form of that polynomial from scratch, gives an exact formula for how wrong it can be, and ends with a cautionary result (Runge's phenomenon) that upends the intuition "more data points always means a better fit."

Section 3.1 (Burden & Faires)

The Interpolation Problem

Existence and Uniqueness

Theorem 5.1 - Existence & Uniqueness of the Interpolating Polynomial
If $x_0,x_1,\ldots,x_n$ are $n+1$ distinct numbers and $f$ is a function defined at each of them, then there exists a unique polynomial $P(x)$ of degree at most $n$ with $P(x_i)=f(x_i)$ for each $i=0,\ldots,n$.

Uniqueness follows from a short argument: if two degree-$\le n$ polynomials agreed at $n+1$ distinct points, their difference would be a degree-$\le n$ polynomial with $n+1$ roots - impossible unless it is identically zero (the Fundamental Theorem of Algebra). Existence is what Lagrange's construction below proves directly, by simply building one.

Lagrange Basis Polynomials

Definition - Lagrange Basis & Interpolating Polynomial
For nodes $x_0,\ldots,x_n$, define the $k$th Lagrange basis polynomial $$L_{n,k}(x) = \prod_{\substack{i=0\\ i\neq k}}^{n} \frac{x-x_i}{x_k-x_i}$$ which has the defining property $L_{n,k}(x_j)=\begin{cases}1 & j=k\\0 & j\neq k\end{cases}$. The interpolating polynomial is then simply a weighted sum: $$P_n(x) = \sum_{k=0}^{n} f(x_k)\,L_{n,k}(x)$$ Every basis polynomial "activates" only at its own node and vanishes at every other - so the sum automatically passes through every data point.
Lagrange basis polynomials for nodes $x_0=0,\,x_1=1,\,x_2=2,\,x_3=3$. Each $L_k(x)$ equals exactly $1$ at its own node (dot) and $0$ at every other node - "All + P(x)" overlays every basis function together with the resulting interpolant through sample data $f=(1,3,2,5)$.
📘 Example 5.1 - Building $P_2(x)$ by Hand
Use nodes $x_0=2,\,x_1=2.5,\,x_2=4$ with $f(x)=1/x$ to construct the Lagrange interpolating polynomial and approximate $f(3)=1/3$. Solution $f(x_0)=0.5,\; f(x_1)=0.4,\; f(x_2)=0.25$. $$L_0(3) = \frac{(3-2.5)(3-4)}{(2-2.5)(2-4)} = \frac{(0.5)(-1)}{(-0.5)(-2)} = \frac{-0.5}{1} = -0.5$$ $$L_1(3) = \frac{(3-2)(3-4)}{(2.5-2)(2.5-4)} = \frac{(1)(-1)}{(0.5)(-1.5)} = \frac{-1}{-0.75} = 1.3333$$ $$L_2(3) = \frac{(3-2)(3-2.5)}{(4-2)(4-2.5)} = \frac{(1)(0.5)}{(2)(1.5)} = \frac{0.5}{3} = 0.1667$$ $$P_2(3) = (0.5)(-0.5) + (0.4)(1.3333) + (0.25)(0.1667) = -0.25+0.53333+0.04167 = 0.325$$ $P_2(3) = 0.325$ against the true value $f(3)=0.33333\ldots$ - absolute error $\approx0.00833$, a $2.5\%$ relative error from just 3 data points.

The Interpolation Error Formula

Theorem 5.2 - Interpolation Error
Suppose $x_0,\ldots,x_n\in[a,b]$ are distinct and $f\in C^{n+1}[a,b]$. For every $x\in[a,b]$, there exists $\xi(x)\in(a,b)$ such that $$f(x) - P_n(x) = \frac{f^{(n+1)}(\xi(x))}{(n+1)!}\prod_{i=0}^{n}(x-x_i)$$ This is the direct descendant of Taylor's Theorem's remainder from Chapter 1 - the same $\dfrac{f^{(n+1)}(\xi)}{(n+1)!}$ structure, but with $(x-x_0)^{n+1}$ replaced by the product over all the interpolation nodes, since a Taylor polynomial is really just the special case of interpolation with all nodes collapsed onto a single point.
📘 Example 5.2 - Verifying the Error Bound
Bound the error in Example 5.1's approximation of $f(3)$ using Theorem 5.2, and compare to the actual error. Solution $f(x)=1/x \Rightarrow f'''(x) = -6/x^4$. On $[2,4]$, $|f'''(x)|$ is maximized at $x=2$: $|f'''(2)|=6/16=0.375$. $$|f(3)-P_2(3)| \le \frac{0.375}{3!}\,|(3-2)(3-2.5)(3-4)| = \frac{0.375}{6}(1)(0.5)(1) = 0.03125$$ Bound: $0.03125$. Actual error from Example 5.1: $0.00833$ - well inside the bound, as expected, since the bound uses the worst-case $\xi$ over the whole interval rather than the (unknown) exact one.
Section 3.2 (Burden & Faires)

Neville's Method

Motivation
The Lagrange form is elegant but wasteful in practice: adding a single new data point means the entire polynomial must be rebuilt from scratch - none of the previous basis polynomials can be reused, since every $L_{n,k}$ depends on all the nodes. Neville's Method instead builds up a triangular table of increasingly higher-degree interpolants, reusing every previous computation.
Neville's Recursive Formula
Let $Q_{i,j}$ denote the degree-$j$ interpolating polynomial (evaluated at a fixed point $x$) through nodes $x_{i-j},\ldots,x_i$. Then $Q_{i,0}=f(x_i)$, and $$Q_{i,j} = \frac{(x-x_{i-j})Q_{i,j-1} - (x-x_i)Q_{i-1,j-1}}{x_i - x_{i-j}}$$ $Q_{n,n}$ - the bottom-right corner of the table - is $P_n(x)$, the full interpolant through all $n+1$ nodes, evaluated at the target $x$.
📘 Example 5.3 - Neville's Table for $f(x)=\ln x$
Given $f(x)=\ln x$ tabulated at $x_0,\ldots,x_4 = 1.0,\,1.3,\,1.6,\,1.9,\,2.2$, use Neville's Method to approximate $f(1.5)=\ln(1.5)=0.4054651\ldots$ Solution $f(x_i) = 0,\,0.262364,\,0.470004,\,0.641854,\,0.788457$.
$x_i$$Q_{i,0}$$Q_{i,1}$$Q_{i,2}$$Q_{i,3}$$Q_{i,4}$
1.00.000000
1.30.2623640.437274
1.60.4700040.4007910.406871
1.90.6418540.4127200.4047670.405702
2.20.7884570.4463830.4071100.4052880.405529
Sample computation of $Q_{2,1}$ (linear interpolant through $x_1=1.3,x_2=1.6$, at $x=1.5$): $$Q_{2,1} = \frac{(1.5-1.3)(0.470004) - (1.5-1.6)(0.262364)}{1.6-1.3} = \frac{(0.2)(0.470004)-(-0.1)(0.262364)}{0.3} = 0.400791$$ $Q_{4,4}=P_4(1.5)=0.405529$ against true $\ln(1.5)=0.405465$ - error $\approx6.4\times10^{-5}$, and every intermediate column is itself a usable lower-degree estimate, essentially free.
Column-by-column convergence of Neville's table from Example 5.3: each diagonal entry $Q_{i,i}$ is the best available polynomial estimate of $\ln(1.5)$ using $i+1$ nodes. Notice the estimate is already accurate to 3 decimal places using only 3 nodes ($Q_{2,2}$).
Section 3.2 continued

Runge's Phenomenon

More Nodes Can Make Things Worse
Theorem 5.2's error bound has a product term $\prod(x-x_i)$ that can grow with $n$ faster than $f^{(n+1)}/(n+1)!$ shrinks - especially with equally spaced nodes. The classic demonstration is Runge's function $f(x) = \dfrac{1}{1+25x^2}$ on $[-1,1]$: as the polynomial degree increases with equally spaced nodes, the interpolant fits beautifully near the center but develops wild, growing oscillations near the endpoints.
$f(x)=\dfrac{1}{1+25x^2}$ (gray) vs. its degree-$n$ interpolant (red) through $n+1$ equally spaced nodes (dots). Raise $n$: the fit near $x=0$ improves, but the oscillations near $x=\pm1$ grow - eventually without bound. This is exactly why later methods (Chapter 7's cubic splines) use many low-degree pieces instead of one high-degree polynomial.
📘 Example 5.4 - Quantifying the Blow-Up
Using equally spaced nodes on $[-1,1]$ for $f(x)=1/(1+25x^2)$, compare the interpolation error near $x=0.95$ as the number of nodes grows. Solution (computed directly from the Lagrange formula)
Nodes ($n+1$)Degree $n$Error near $x=0.95$
54$\approx0.34$
98$\approx1.01$
1312$\approx3.66$
2120$\approx58.3$
The error near the edge of the interval doesn't shrink as more equally spaced nodes are added - it explodes, eventually exceeding the function's own range ($f\in[0,1]$ everywhere) by orders of magnitude. The fix is not "more nodes" but "different node placement" (Chebyshev nodes, clustered near the endpoints) or "piecewise low-degree interpolation" - the subject of Chapters 6–7.
Practice

Practice Problem

Try this problem yourself before expanding the solution below.

✏️ Practice Problem 5.1 - Cubic Lagrange Interpolation of $\ln(x)$
Using the data $(1,\ln 1), (2,\ln 2), (3,\ln 3), (4,\ln 4)$, construct the degree-3 Lagrange interpolating polynomial and use it to approximate $\ln(2.5)$. Then find a theoretical error bound and compare it to the actual error. Solution The data are $(1,0), (2,0.693147), (3,1.098612), (4,1.386294)$. Building the four Lagrange basis polynomials $L_0,L_1,L_2,L_3$ and evaluating $P_3(x)=\sum_i y_i L_i(x)$ at $x=2.5$ gives $$P_3(2.5) = 0.921221.$$ The true value is $\ln(2.5)=0.916291$, so the actual error is $|0.921221-0.916291|=0.004931$.

For the bound, $f''''(x) = -6/x^4$ for $f(x)=\ln x$, and $|f''''(\xi)|\le 6$ on $[1,4]$ (largest at $x=1$). The interpolation error formula gives $$|f(2.5)-P_3(2.5)| \le \frac{\max|f''''(\xi)|}{4!}\prod_{i=0}^{3}|2.5-x_i| = \frac{6}{24}\,(1.5)(0.5)(0.5)(1.5) = 0.140625.$$ $P_3(2.5)=0.921221$, actual error $\approx0.004931$, theoretical bound $0.140625$ - the true error is well inside the (fairly loose) bound.
Connections Across the Course
  • The error formula's structure - $(n+1)$th derivative over $(n+1)!$ - is identical in spirit to the Taylor remainder of Chapter 1 and reappears for numerical differentiation (Chapter 8) and integration (Chapter 9), both of which are derived by differentiating or integrating an interpolating polynomial.
  • Runge's phenomenon is the direct motivation for divided-difference and especially cubic-spline methods, which sidestep high-degree polynomials entirely.
  • Neville's table-building idea - reusing lower-order results - reappears in spirit in Romberg integration (Chapter 10).
Scroll to Top