Polynomial Interpolation and Its Error Term
Fit the unique polynomial of degree at most n through n + 1 points with distinct x values, build its Lagrange and Newton forms, and bound its error.
What a learner can do afterwards
- Construct an interpolating polynomial in both Lagrange and divided-difference form
- State the error term and use it to bound the interpolation error on an interval
- Show with a worked example why more equally spaced points can make the fit worse
1 · Read
For n+1 points with distinct x values, exactly one polynomial of degree at most n matches every value. Its degree may be smaller. Higher-degree polynomials can also match. To prove uniqueness within the limit, subtract two candidates. Their difference has n+1 distinct roots, more than a nonzero polynomial of degree at most n can have. The difference must be zero. Repeated inputs with different outputs cannot be matched by any function.
For data (a,u) and (b,v), where a differs from b, the interpolating line is p(x)=u+m(x-a), with slope m=(v-u)/(b-a). Equivalently, p(x)=u(b-x)/(b-a)+v(x-a)/(b-a). To check any proposed interpolant, substitute each node and compare with its recorded value. The residual is the polynomial's value minus the recorded value; it must be zero at every matched node.
For nodes x_0,...,x_n and values y_0,...,y_n, form L_i(x) by multiplying (x-x_j)/(x_i-x_j) over all j other than i. Distinct nodes make the denominators nonzero. This basis polynomial is 1 at its own node and 0 at every other node. Lagrange form is p(x)=sum of y_i L_i(x). Evaluate each basis term, weight it by its data value and add. To find a coefficient, expand the weighted terms and collect the required power.
For (-1,2), (0,1) and (1,2), the basis polynomials are x(x-1)/2, 1-x^2 and x(x+1)/2. Multiply them by 2, 1 and 2. Their sum is x(x-1)+(1-x^2)+x(x+1)=x^2+1. The x^2 coefficients add to 1-1+1=1. Substitution checks the data: p(-1)=2, p(0)=1 and p(1)=2.
Write f[a] for the value at node a. Divided differences are f[a,b]=(f[b]-f[a])/(b-a) and f[a,b,c]=(f[b,c]-f[a,b])/(c-a). Newton's quadratic form is p(x)=f[a]+f[a,b](x-a)+f[a,b,c](x-a)(x-b). At each higher level, subtract adjacent differences and divide by the spacing of the outer nodes. Each new coefficient multiplies the product of factors for the preceding nodes.
For (0,2), (2,6) and (4,18), the adjacent first differences are (6-2)/2=2 and (18-6)/2=6. The second difference is (6-2)/(4-0)=1. Newton form gives p(x)=2+2x+x(x-2)=x^2+2. Both Newton and Lagrange form give this polynomial because each matches the same data within the same degree limit.
To add a point (t,v), keep the old interpolant p_n and add K times product(x-x_i) over the old nodes. This product vanishes at every old node, preserving its value. Choose K=(v-p_n(t))/product(t-x_i) to match the new value. The new node t must differ from all old nodes. If the old polynomial already matches the new value, K is zero.
Let p_n be the polynomial of degree at most n matching f at n+1 distinct nodes x_i. Assume f has n+1 continuous derivatives on a closed interval containing the nodes and x. For a non-node x, f(x)-p_n(x)=f^(n+1)(c) times product(x-x_i)/(n+1)!, where c is inside the smallest interval containing the nodes and x. The superscript denotes derivative order. At a node the error is zero. The nodal product replaces the Taylor remainder's power.
If |f^(n+1)(t)| <= M throughout the interval, the absolute error is at most M/(n+1)! times |product(x-x_i)|. For a line through the values at endpoints a<b, use |f''| <= M and divide by 2. Inside [a,b], |(x-a)(x-b)| is at most h^2/4, where h=b-a. The uniform absolute-error bound is therefore M h^2/8. An upper bound on f'' alone does not bound absolute error.
Use Runge's function f(x)=1/(1+25x^2) on [-1,1]. Nodes -1,0,1 give p_2(x)=1-25x^2/26. Adding the equally spaced nodes -0.5 and 0.5 gives p_4(x)=1-(3225/754)x^2+(1250/377)x^4. Substitution verifies both fits at their nodes. Every sampled value is positive. At x=0.9, f(x)=4/85, p_2(x)=23/104 and p_4(x)=-109/377. Positive data do not force positive values between nodes.
At x=0.9, the three-node absolute error is |4/85-23/104|, about 0.1741. The five-node error is |4/85+109/377|, about 0.3362. More nodes gave a less accurate fit here. This compares one point, not the worst error on the interval. High-degree equally spaced interpolation of Runge's function develops large errors near the ends. Chebyshev nodes cluster toward both ends and give convergence for this function, not an accuracy guarantee for every function.
Distinct nodes fix one polynomial within a degree limit. Lagrange and Newton give the same fit. Derivative bounds control error; more equally spaced nodes need not improve it.
Lesson, practice questions and flashcards written for this dataset.
Readings, extra questions and flashcards written for this dataset. Linked Taylor-remainder videos by Khan Academy provide prerequisite review.
More to read
The degree limit matters
Suppose a polynomial already matches a list of recorded values at distinct nodes x_i. Multiplying all the factors (x-x_i) produces a polynomial that vanishes at every node. Adding any constant multiple of that product to the existing fit preserves every recorded value. Thus matching the data alone does not select one polynomial.
The uniqueness theorem adds a degree restriction. With n+1 distinct nodes, there is exactly one matching polynomial of degree at most n. Its degree can be lower. Data taken from a line, for example, are still matched by that line even when there are more than two nodes.
Why can there be only one candidate within the limit? Subtract two candidates. Their difference has degree at most n and vanishes at all n+1 nodes. A nonzero polynomial within that degree limit cannot have so many distinct roots. The difference is zero, so the candidates are identical.
Repeated inputs need separate attention. Data demanding both p(2)=3 and p(2)=7 are incompatible. No function can meet both requirements.
Two ways to construct the same polynomial
Lagrange construction builds one basis polynomial per node. For node x_i, multiply (x-x_j)/(x_i-x_j) over every other node. At another node, one numerator becomes zero. At its own node, every ratio equals 1. Weight this basis polynomial by the recorded value y_i, then add the weighted terms.
Newton construction uses divided differences. Start with slopes between adjacent nodes. Subtract adjacent slopes and divide by the spacing of their outer nodes to obtain second divided differences. Continue this process for higher orders. The coefficients multiply 1, (x-x_0), (x-x_0)(x-x_1), and products containing more preceding-node factors.
For data (0,3), (1,4) and (3,12), the adjacent slopes are 1 and 4. The second divided difference is (4-1)/(3-0)=1. Newton form gives 3+x+x(x-1)=x^2+3. Evaluating at 0, 1 and 3 confirms all three recorded values.
To extend an existing fit, add a multiple of its old-node product. This correction preserves the old values because it vanishes at their nodes. Choose its coefficient by evaluating the product at the new node and dividing the missing output by that value.
Turning a remainder formula into a bound
Taylor and ordinary interpolation use different information. Taylor matches a value and derivatives at one center. Ordinary interpolation matches values at distinct nodes. Both have remainder formulas involving a derivative and a factorial.
Let p_n be the polynomial of degree at most n matching f at n+1 distinct nodes x_i. Assume f has n+1 continuous derivatives on an interval containing the nodes and the evaluation point x. If x is not a node, the error is f^(n+1)(c) times product(x-x_i)/(n+1)!. The superscript denotes derivative order. The unknown c is inside the smallest interval containing x and all the nodes. At a node, matching gives zero error directly.
For an absolute-error bound, find M that bounds the absolute value of the required derivative throughout that interval. Multiply M/(n+1)! by the absolute nodal product. The derivative's upper bound without absolute values is insufficient: a large negative derivative can also cause a large absolute error.
For a line using the endpoint values on [a,b], the absolute nodal product is at most (b-a)^2/4. Combining this with the divisor 2 gives M(b-a)^2/8.
The two linked Taylor-remainder videos review the preceding topic. They do not construct interpolation through distinct nodes or prove its remainder theorem.
Checking a fit away from its nodes
For f(x)=1/(1+25x^2) on [-1,1], interpolation at -1,0,1 gives p_2(x)=1-25x^2/26. Adding the nodes -0.5 and 0.5 gives p_4(x)=1-(3225/754)x^2+(1250/377)x^4. Each formula can be checked by substituting its nodes.
At the unsampled point x=0.9, the function equals 4/85. The interpolants give 23/104 and -109/377. Subtracting each approximation from the true value and taking absolute values gives errors of about 0.1741 and 0.3362. The fit using more nodes is less accurate at this point.
Every sampled function value is positive, yet the five-node interpolant is negative at 0.9. Passing through positive samples does not force a polynomial to stay positive between them.
This calculation concerns one point, not the maximum error on the interval. Runge's phenomenon describes the large errors near the ends that develop in high-degree equally spaced interpolation of this function. Chebyshev nodes cluster toward both ends and give convergence for it. Their success here does not establish accuracy for every function.
Explore more
2 · Watch
به انگلیسیTake it off screen
Where it sits
17 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.