MGU Mathematics Series — Numerical Methods
Part II: Roots, Interpolation, and Approximation of Functions
Error · Algorithms · Convergence · Stability · Modeling
Chapter 4 of 14
4
MGU Mathematics Series  ·  Numerical Methods  ·  Library Textbook Edition

Chapter 4:
Interpolation and
Polynomial Approximation

Constructing functions that pass through known data points — linear interpolation, Lagrange's formula, Newton divided differences, interpolation error, Runge's phenomenon, and piecewise methods

■ Part II of V  ·  Roots, Interpolation, and Approximation ■

■ 14 Sections  •  Chapter 4 of 14 ■

Prerequisite: Calculus — functions, derivatives, Taylor series. Linear Algebra — systems of equations helpful.

Chapter 4 — Front Matter

Chapter Introduction and Learning Objectives

This chapter introduces interpolation as one of the most fundamental and widely used ideas in numerical mathematics. Interpolation answers a deceptively simple question: given a collection of known data points, what value does the underlying function take between them?

In calculus, students work primarily with functions given by explicit formulas. But in science, engineering, finance, and data analysis, functions are rarely known in formula form. Instead, they appear as tables of measurements: temperatures recorded at discrete hours, pressures sampled at specific depths, voltages read at particular time steps, or population figures gathered in census years. Between those recorded values, the function's behavior is unknown. Interpolation provides a systematic, mathematically principled way to estimate it.

This chapter develops polynomial interpolation from its foundations. The central theme is consistent throughout: interpolation is controlled estimation between known values, and that control requires understanding what an interpolating polynomial guarantees and where it can break down.

Opening Question

A civil engineer measures the deflection of a bridge deck at five support points. The deck is continuous, but instruments record data only at the five sensor locations. The engineer needs to estimate the deflection at a point midway between two sensors to verify that safety tolerances are met. No formula describes the bridge's deformation under this particular load — there is only the table of five measured values. How should the engineer estimate the deflection at the unmeasured location? How confident should that estimate be? What happens if the estimation method is poorly chosen? These are the questions of interpolation.

14Sections
10Objectives
20Key Terms
14Total Chapters

Learning Objectives

After completing this chapter, students should be able to:

  1. 1Explain what interpolation is and why it is needed in numerical practice.
  2. 2Construct a linear interpolant between two data points and estimate function values.
  3. 3Explain the existence and uniqueness of the interpolating polynomial for distinct data points.
  4. 4Construct the Lagrange interpolating polynomial for a small set of data points.
  5. 5Build and use a divided difference table to construct Newton's interpolating polynomial.
  6. 6State the interpolation error formula and use it to estimate the error in a polynomial interpolant.
  7. 7Explain why the choice of interpolation nodes affects accuracy.
  8. 8Describe Runge's phenomenon and explain why high-degree polynomial interpolation over equally spaced points can fail.
  9. 9Construct a piecewise linear interpolant and explain why piecewise methods are often preferred.
  10. 10Identify situations where polynomial interpolation is unsafe or unreliable.
Why This Chapter Matters

Interpolation sits at the intersection of almost every numerical application in this textbook. Root-finding methods in Chapter 3 sometimes depend on interpolated estimates. Splines and least squares in Chapter 5 extend interpolation for noisy data. Numerical differentiation in Chapter 6 and numerical integration in Chapter 7 both derive their formulas from interpolating polynomials. ODE and PDE solvers in Chapters 12 and 13 use interpolation to reconstruct continuous solutions from discrete time steps. Beyond this course, interpolation appears in graphics rendering, signal reconstruction, medical imaging, satellite navigation, financial modeling, and the construction of mathematical tables used in embedded systems and calculators.

Chapter 4 — Contents

Sections at a Glance

Sections 4.1 – 4.2
The Setup: What Interpolation Is and Where Data Comes From
Nodes · Data Points · Interpolants · Interpolation vs. Extrapolation · Sources of Data
Section 4.1

What Interpolation Does

Interpolation is the process of constructing a function that passes exactly through a given set of known data points and then using that function to estimate values at locations where the function is not directly known.

The word comes from the Latin interpolare, meaning to refurbish or alter something between its endpoints. In mathematics, interpolation inserts estimated values between known ones.

The fundamental setup is this. Suppose that measurements or calculations have produced a collection of data points. Each point consists of an input value and a corresponding output value:

\[(x_0, y_0), \quad (x_1, y_1), \quad (x_2, y_2), \quad \ldots, \quad (x_n, y_n)\]

The input values \(x_0, x_1, \ldots, x_n\) are called interpolation nodes or simply nodes. They must be distinct: no two nodes may have the same \(x\)-value. The output values \(y_0, y_1, \ldots, y_n\) are the function values at those nodes.

An interpolant is any function \(p\) satisfying:

\[p(x_i) = y_i \quad \text{for each } i = 0, 1, 2, \ldots, n\]

The interpolant passes exactly through every data point. Once constructed, it can be evaluated at any input value \(x\) lying between the nodes to produce an estimated function value.

It is important to notice what interpolation does not require. It does not require knowing the formula for the underlying function. It does not require understanding why the data takes the values it does. Interpolation works from the data alone.

Interpolation
Estimation Between Nodes
When the evaluation point \(x\) lies between the smallest and largest nodes, the process is interpolation. This is the reliable region of the method.
Extrapolation
Estimation Beyond Nodes
When \(x\) lies outside the range of the nodes, the process is extrapolation. Polynomials may diverge rapidly outside the data range. Treat extrapolation with considerable caution.
Choice of Interpolant
Polynomials Are Most Common
Many functions can serve as interpolants. This chapter focuses on polynomials because they are easy to construct, evaluate, differentiate, and integrate. Piecewise polynomials appear in Sections 4.10 and 5.
Section 4.2

Data Points and Function Values

Before building any interpolant, it is worth pausing to think carefully about the data itself. Where does interpolation data come from? What assumptions are hidden in the setup?

Sources of Interpolation Data

Physical measurements. A thermometer records temperature at specific hours, a strain gauge measures deflection at specific loads, a flow meter records velocity at specific depths. Between those measurements, the physical quantity varies continuously, but the instrument only recorded values at the chosen moments or locations.

Function tables. Before electronic computation, enormous tables of \(\sin x\), \(\ln x\), \(e^x\), and other functions were published for use in calculations. To find a value at an argument not listed in the table, readers interpolated between the nearest entries.

Computational simulations. A finite element solver computes temperature at mesh nodes, and the temperature between nodes must be inferred by interpolation. An ODE solver computes a solution at discrete time steps, and continuous values at other times are recovered by interpolation.

Deliberately chosen evaluation points. When approximating a complicated function by a simpler one, a student might evaluate the complicated function at \(n+1\) chosen nodes and use those values to build a polynomial approximation.

Assumption of a Smooth Underlying Function

Interpolation works best when the underlying function is smooth: continuously differentiable, without sharp corners, sudden jumps, or violent oscillations. When the underlying function is rough or discontinuous, polynomial interpolation between smooth nodes can produce estimates far from the true values. Students should ask about the smoothness of the underlying quantity before applying interpolation.

Sections 4.3 – 4.6
Building Interpolating Polynomials: Linear, Lagrange, and Newton
Linear Interpolation · Uniqueness · Lagrange Basis · Divided Differences · Newton Form
Section 4.3

Linear Interpolation

The simplest and most familiar form of interpolation uses two data points and a straight line.

Suppose two data points \((x_0, y_0)\) and \((x_1, y_1)\) are known, with \(x_0 \neq x_1\). The linear interpolant through these two points is the unique line passing through both. Its formula is:

\[p_1(x) = y_0 + \frac{y_1 - y_0}{x_1 - x_0}(x - x_0)\]

This is the point-slope form of a line, with slope \(\dfrac{y_1 - y_0}{x_1 - x_0}\). To estimate the function value at an intermediate point \(x\) with \(x_0 < x < x_1\), simply evaluate \(p_1(x)\).

Geometrically, linear interpolation connects the two known data points with a straight line segment and reads off the height of that segment at the desired input. The smaller the interval \([x_0, x_1]\), the more reliable the linear approximation is, because any smooth function looks approximately linear at a sufficiently small scale.

Example 4.1
Linear Interpolation from a Temperature Table
  • Problem A weather station records temperatures at 8:00 AM (14.2°C) and 10:00 AM (18.6°C). Estimate the temperature at 9:00 AM.
  • Think Two data points: \((8, 14.2)\) and \((10, 18.6)\). The desired time, 9 AM, lies between them. Linear interpolation is appropriate as a first estimate.
  • Method Apply the linear interpolation formula with \(x_0 = 8\), \(y_0 = 14.2\), \(x_1 = 10\), \(y_1 = 18.6\), \(x = 9\).
  • Compute \[p_1(9) = 14.2 + \frac{18.6 - 14.2}{10 - 8}(9 - 8) = 14.2 + \frac{4.4}{2}(1) = 14.2 + 2.2 = 16.4\]
  • Check The estimate 16.4°C lies halfway between 14.2 and 18.6, which makes sense because 9:00 AM lies halfway between 8:00 AM and 10:00 AM. Geometrically consistent.
  • Interpret The estimated temperature at 9:00 AM is approximately 16.4°C, assuming the temperature changes approximately linearly over this two-hour window. Whether this is accurate depends on how well the linearity assumption holds in practice.
Interpretation Note

Linear interpolation is an approximation, not a measurement. The estimate says only that if the temperature changed at a constant rate between 8 AM and 10 AM, then the 9 AM value would be 16.4°C. The actual temperature might differ if the warming rate accelerated, decelerated, or fluctuated.

Section 4.4

Polynomial Interpolation

Linear interpolation uses one polynomial of degree 1 to pass through two data points. The natural generalization uses a polynomial of higher degree to pass through more data points.

The main result. Given \(n + 1\) distinct nodes \(x_0, x_1, \ldots, x_n\) and corresponding values \(y_0, y_1, \ldots, y_n\), there exists exactly one polynomial \(p_n\) of degree at most \(n\) satisfying:

\[p_n(x_i) = y_i \quad \text{for each } i = 0, 1, \ldots, n\]

This polynomial is called the interpolating polynomial for the given data. Its existence and uniqueness are proven in numerical analysis courses; for this textbook, students should accept the result and focus on how to construct and use it.

Why degree at most \(n\)? With \(n + 1\) data points, a polynomial of degree \(n\) has \(n + 1\) free coefficients — those of \(x^0, x^1, \ldots, x^n\). Setting those coefficients to satisfy \(n + 1\) interpolation conditions determines the polynomial uniquely.

One polynomial, many representations. There is only one interpolating polynomial for a given dataset, but it can be written in different algebraic forms. Lagrange's formula and Newton's divided difference formula produce the same polynomial written differently. Students should think of these as two representations of one underlying mathematical object, not two different polynomials.

The Uniqueness Theorem

Theorem. Given \(n+1\) distinct interpolation nodes and corresponding data values, there exists exactly one polynomial of degree at most \(n\) that passes through all \(n+1\) data points.

This result is fundamental. It tells students that no matter which construction method is used — Lagrange, Newton, or direct coefficient-solving — the resulting polynomial is always the same object.

Section 4.5

Lagrange Interpolation

The Lagrange form of the interpolating polynomial expresses it as a sum of carefully chosen basis polynomials. It is elegant and theoretically important, even though Newton's form is often more efficient for computation.

The Lagrange Basis Polynomials

For each index \(i = 0, 1, \ldots, n\), the Lagrange basis polynomial \(L_i(x)\) is defined by:

\[L_i(x) = \prod_{\substack{j=0 \\ j \neq i}}^{n} \frac{x - x_j}{x_i - x_j}\]

Key property — the cardinal condition. The Lagrange basis polynomials satisfy:

\[L_i(x_j) = \begin{cases} 1 & \text{if } j = i \\ 0 & \text{if } j \neq i \end{cases}\]

At node \(x_i\), the basis polynomial \(L_i\) equals one. At every other node, it equals zero. This is what makes the Lagrange construction work: each basis polynomial "picks out" exactly one data point.

The Lagrange interpolating polynomial assembles the basis functions weighted by the data values:

\[p_n(x) = \sum_{i=0}^{n} y_i L_i(x) = y_0 L_0(x) + y_1 L_1(x) + \cdots + y_n L_n(x)\]

Verification. At any node \(x_k\):

\[p_n(x_k) = \sum_{i=0}^{n} y_i L_i(x_k) = y_k \cdot 1 + \sum_{i \neq k} y_i \cdot 0 = y_k\]

The interpolant passes through every data point exactly, as required.

Example 4.2
Lagrange Interpolation Through Three Points
  • Problem Given \((1, 2)\), \((3, 8)\), \((5, 14)\), construct the Lagrange interpolating polynomial and estimate the value at \(x = 2\).
  • Think Three data points determine a polynomial of degree at most 2. Construct three Lagrange basis polynomials and assemble.
  • Compute L₀ \[L_0(x) = \frac{(x - 3)(x - 5)}{(1 - 3)(1 - 5)} = \frac{(x-3)(x-5)}{(-2)(-4)} = \frac{(x-3)(x-5)}{8}\]
  • Compute L₁ \[L_1(x) = \frac{(x - 1)(x - 5)}{(3 - 1)(3 - 5)} = \frac{(x-1)(x-5)}{(2)(-2)} = \frac{(x-1)(x-5)}{-4}\]
  • Compute L₂ \[L_2(x) = \frac{(x - 1)(x - 3)}{(5 - 1)(5 - 3)} = \frac{(x-1)(x-3)}{(4)(2)} = \frac{(x-1)(x-3)}{8}\]
  • Evaluate at x=2 \(L_0(2) = \frac{(-1)(-3)}{8} = \tfrac{3}{8}\), \quad \(L_1(2) = \frac{(1)(-3)}{-4} = \tfrac{3}{4}\), \quad \(L_2(2) = \frac{(1)(-1)}{8} = -\tfrac{1}{8}\)

    \[p_2(2) = 2 \cdot \tfrac{3}{8} + 8 \cdot \tfrac{3}{4} + 14 \cdot \left(-\tfrac{1}{8}\right) = \tfrac{6}{8} + 6 - \tfrac{14}{8} = -1 + 6 = 5\]
  • Check The three data points lie on the line \(y = 3x - 1\), since \(3(2) - 1 = 5\). The interpolating polynomial degenerates to the line when the data is collinear — a useful self-check.
  • Interpret The estimated value at \(x = 2\) is \(p_2(2) = \mathbf{5}\).
Student Warning

Constructing Lagrange basis polynomials by hand becomes tedious for large datasets. The Lagrange form is most useful for theoretical analysis and for situations with a small number of points. For practical computation with many nodes, Newton's divided difference form (Section 4.6) is more efficient — and adding a new data point requires only one new column in the table, not a complete reconstruction.

Algorithm: Lagrange Interpolation

Algorithm: Lagrange Interpolation
Purpose: Evaluate the interpolating polynomial at a given point x
Inputs:
  nodes x_0, x_1, ..., x_n  (distinct)
  values y_0, y_1, ..., y_n
  evaluation point x
Steps:
  Set result = 0
  For each i from 0 to n:
    Set L_i = 1
    For each j from 0 to n:
      If j ≠ i:
        Set L_i = L_i * (x - x_j) / (x_i - x_j)
    Set result = result + y_i * L_i
Output: result  (the interpolated value at x)
Reliability notes:
  Works for any number of distinct nodes.
  Adding a new data point requires recomputing all basis polynomials.
  Numerical cancellation can occur when x is far from the nodes.
Section 4.6

Newton Divided Differences

Newton's divided difference method constructs the interpolating polynomial in a form that is efficient to compute and easy to update when new data points are added. It is the preferred method for hand calculations with more than two or three points, and it underpins many advanced numerical methods.

Defining Divided Differences

The zeroth-order divided difference at a single node \(x_i\) is simply the function value:

\[f[x_i] = y_i\]

The first-order divided difference at two nodes \(x_i, x_{i+1}\) is the slope of the line through those two points:

\[f[x_i, x_{i+1}] = \frac{f[x_{i+1}] - f[x_i]}{x_{i+1} - x_i}\]

In general, the \(k\)-th order divided difference is defined recursively:

\[f[x_i, x_{i+1}, \ldots, x_{i+k}] = \frac{f[x_{i+1}, \ldots, x_{i+k}] - f[x_i, \ldots, x_{i+k-1}]}{x_{i+k} - x_i}\]

Newton's interpolating polynomial is assembled using the top-diagonal coefficients from the divided difference table:

\[p_n(x) = f[x_0] + f[x_0, x_1](x - x_0) + f[x_0, x_1, x_2](x - x_0)(x - x_1) + \cdots\] \[\quad + \; f[x_0, x_1, \ldots, x_n](x - x_0)(x - x_1)\cdots(x - x_{n-1})\]
Example 4.3
Newton's Divided Differences for ln x
  • Problem Given data approximating \(\ln x\):
    \(x\)\(f(x)\)
    1.00.000
    1.50.405
    2.00.693
    2.50.916
    Construct Newton's polynomial and estimate \(f(1.8)\).
  • Think Four data points yield degree at most 3. Build the divided difference table, extract the top-row coefficients, write Newton's polynomial, and evaluate at \(x = 1.8\).
  • First-order \(f[x_0,x_1] = \frac{0.405 - 0.000}{1.5-1.0} = 0.810\)
    \(f[x_1,x_2] = \frac{0.693 - 0.405}{2.0-1.5} = 0.576\)
    \(f[x_2,x_3] = \frac{0.916 - 0.693}{2.5-2.0} = 0.446\)
  • Second-order \(f[x_0,x_1,x_2] = \frac{0.576 - 0.810}{2.0-1.0} = -0.234\)
    \(f[x_1,x_2,x_3] = \frac{0.446 - 0.576}{2.5-1.5} = -0.130\)
  • Third-order \(f[x_0,x_1,x_2,x_3] = \dfrac{-0.130 - (-0.234)}{2.5 - 1.0} = \dfrac{0.104}{1.5} \approx 0.0693\)
  • Newton polynomial \[p_3(x) = 0 + 0.810(x-1.0) - 0.234(x-1.0)(x-1.5) + 0.0693(x-1.0)(x-1.5)(x-2.0)\]
  • Evaluate at 1.8 Using \((1.8-1.0)=0.8\), \((1.8-1.5)=0.3\), \((1.8-2.0)=-0.2\):

    \[p_3(1.8) = 0 + 0.810(0.8) - 0.234(0.8)(0.3) + 0.0693(0.8)(0.3)(-0.2)\] \[= 0.648 - 0.05616 - 0.003326 \approx \mathbf{0.5888}\]
  • Check & Interpret The true value \(\ln(1.8) \approx 0.5878\). The estimate 0.5888 differs by about 0.001 — accurate to 3 decimal places for a smooth function with step size 0.5. This is a reasonable result.
Reliability Note

The divided difference computation can accumulate roundoff error, particularly in the higher-order differences when function values are nearly equal. Retain sufficient decimal places throughout the table to avoid premature rounding that corrupts later columns.

Algorithm: Newton Divided Difference Interpolation

Algorithm: Newton Divided Difference Interpolation
Purpose: Construct and evaluate the interpolating polynomial via divided differences
Inputs:
  nodes x_0, x_1, ..., x_n  (distinct, any order)
  values y_0, y_1, ..., y_n
  evaluation point x
Steps:
  Initialize divided difference table: dd[i][0] = y_i for all i
  For order k from 1 to n:
    For i from 0 to n-k:
      dd[i][k] = (dd[i+1][k-1] - dd[i][k-1]) / (x_{i+k} - x_i)
  Coefficients: c_k = dd[0][k] for k = 0, 1, ..., n
  Evaluate using Horner's method:
    Set result = c_n
    For k from n-1 down to 0:
      result = result * (x - x_k) + c_k
Output: result  (the interpolated value at x)
Reliability notes:
  Adding a new node x_{n+1} requires only one new column in the table.
  Horner's method minimizes floating-point operations.
  The same polynomial results regardless of node ordering.
Sections 4.7 – 4.10
Error, Node Placement, Runge's Phenomenon, and Piecewise Methods
Interpolation Error · Chebyshev Nodes · Runge's Phenomenon · Piecewise Linear Interpolation
Section 4.7

Interpolation Error

Constructing an interpolating polynomial is only part of the problem. The other part is understanding how good the interpolant is. When the data comes from an underlying function \(f\), the interpolation error is the difference between the true function value and the polynomial's estimate.

The Interpolation Error Formula

Suppose \(f\) is a function with \(n+1\) continuous derivatives on an interval \([a, b]\) containing all the nodes. The error in the interpolating polynomial \(p_n\) at any point \(x \in [a, b]\) is:

\[f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \cdot (x - x_0)(x - x_1)\cdots(x - x_n)\]

where \(\xi\) is some point in the open interval containing \(x\) and all the nodes. The point \(\xi\) depends on \(x\) and is generally not known. Three features of this formula are essential:

  • The error involves \(f^{(n+1)}\), the \((n+1)\)-th derivative of the true function. Large higher derivatives mean large possible errors even with many interpolation points.
  • The error involves the product \(\omega(x) = (x - x_0)(x - x_1)\cdots(x - x_n)\), which depends on how far \(x\) is from the nodes and how the nodes are distributed.
  • The error is zero at each node \(x_i\), since \(\omega(x_i) = 0\). The interpolant passes exactly through the data.

Using the error formula in practice. Since \(\xi\) is unknown, the formula produces an upper bound:

\[|f(x) - p_n(x)| \leq \frac{\max_{\xi \in [a,b]} |f^{(n+1)}(\xi)|}{(n+1)!} \cdot \max_{x \in [a,b]} |\omega(x)|\]
Example 4.4
Bounding the Interpolation Error for sin x
  • Problem Suppose \(f(x) = \sin x\) is interpolated by a polynomial at four equally spaced nodes over \([0, \pi]\). Bound the maximum interpolation error over \([0, \pi]\).
  • Think Four nodes yield degree at most 3. The error formula involves the fourth derivative: \(f^{(4)}(x) = \sin x\). The maximum of \(|\sin x|\) over \([0, \pi]\) is 1.
  • Compute For four equally spaced nodes on \([0,\pi]\) with step \(h = \pi/3\), a standard bound for the error product gives \(\max|\omega(x)| \leq \tfrac{3!}{4}\left(\tfrac{\pi}{3}\right)^4 \approx 1.80\). The error bound is: \[\left|\sin x - p_3(x)\right| \leq \frac{1}{4!} \cdot 1.80 = \frac{1.80}{24} \approx 0.075\]
  • Check The actual maximum error is approximately 0.05, which is below the bound of 0.075. The bound is valid but not tight — typical of theoretical error bounds.
  • Interpret Over \([0, \pi]\), the cubic interpolating polynomial for \(\sin x\) with four equally spaced nodes has an error of at most about 0.075. More nodes or better-placed nodes reduce this bound further.
When the Function Is Unknown

The interpolation error formula requires knowledge of \(f^{(n+1)}\). When the underlying function \(f\) is unknown — as is typically the case with real measurement data — this bound cannot be computed directly. Practitioners must then rely on other strategies: comparing interpolants of different degrees, checking whether adding more nodes changes the result significantly, or using known physical constraints on the rate of variation.

Section 4.8

Choosing Interpolation Points

The placement of interpolation nodes has a profound effect on the accuracy of the interpolant. More nodes do not always mean greater accuracy; where those nodes are placed matters just as much as how many there are.

Node TypeDistributionAdvantageRisk
Equally spaced Uniform spacing: \(x_i = a + i \cdot \frac{b-a}{n}\) Simple to compute; convenient for tables Runge's phenomenon for large \(n\)
Chebyshev nodes Clustered near endpoints: \(x_i = \cos\!\left(\frac{(2i+1)\pi}{2(n+1)}\right)\) on \([-1,1]\) Minimizes worst-case \(|\omega(x)|\); convergence guaranteed for smooth functions Less natural spacing; requires mapping to \([a,b]\)

Chebyshev nodes are more densely clustered near the endpoints than near the center of the interval. This clustering counteracts the tendency of high-degree polynomials to oscillate at the edges — the very effect that produces Runge's phenomenon.

General principle. When students have the freedom to choose where to evaluate a function, they should prefer Chebyshev nodes over equally spaced nodes. When the nodes are determined by external factors — measurement locations, sensor positions, table spacing — students have no choice and should be alert to the risk of oscillatory behavior near the edges of the data range.

Section 4.9

Runge's Phenomenon

Runge's phenomenon is one of the most instructive surprises in numerical analysis. It demonstrates that using a higher-degree interpolating polynomial does not always mean greater accuracy — and in some cases, more nodes actively make things worse.

Runge's 1901 Result

In 1901, Carl Runge studied polynomial interpolation of the function \(f(x) = 1/(1 + 25x^2)\) over \([-1, 1]\) using equally spaced nodes. He found that as the number of nodes increased, the interpolating polynomial became increasingly accurate near the center but oscillated violently near the endpoints \(x = \pm 1\), with errors growing rather than decreasing.

The maximum error over \([-1,1]\) actually increases as \(n \to \infty\), even though the underlying function is smooth and analytic on \([-1,1]\).

Why it happens. The error formula involves the product \(\omega(x) = (x - x_0)(x - x_1)\cdots(x - x_n)\). For equally spaced nodes, this product grows very large near the endpoints, amplifying any errors in the interpolant there. The derivatives \(f^{(n+1)}(x)\) also grow rapidly for Runge's function, compounding the effect.

Diagram description. Imagine two graphs of \(f(x) = 1/(1+25x^2)\) over \([-1,1]\). In the first graph, the interpolating polynomial using 5 equally spaced nodes fits reasonably well everywhere. In the second graph, the polynomial using 11 equally spaced nodes matches near the center but shows pronounced oscillations near \(x = \pm 1\), reaching far above and below the true function. The oscillations are Runge's phenomenon.

The remedy. Using Chebyshev nodes instead of equally spaced nodes controls the growth of \(|\omega(x)|\) near the endpoints. With Chebyshev nodes, the interpolating polynomial for Runge's function converges uniformly to the true function as \(n \to \infty\). Alternatively, piecewise interpolation (Section 4.10) avoids the problem entirely by never using high-degree global polynomials.

Practical Significance

Runge's phenomenon is not a pathological curiosity affecting only one unusual function. It is a real risk in any application that uses high-degree polynomial interpolation over equally spaced nodes on a large interval. Engineers, scientists, and analysts who use interpolation routinely must be aware of it. When in doubt, use piecewise interpolation or Chebyshev-spaced nodes rather than a high-degree global polynomial over equally spaced nodes.

Section 4.10

Piecewise Interpolation

The most widely used remedy for Runge's phenomenon is piecewise interpolation: instead of fitting one high-degree polynomial to all the data, fit a sequence of low-degree polynomials, each defined on a small subinterval between consecutive nodes.

Piecewise Linear Interpolation

The simplest piecewise interpolant connects each pair of consecutive data points with a straight line. On the subinterval \([x_i, x_{i+1}]\), the interpolant is:

\[p(x) = y_i + \frac{y_{i+1} - y_i}{x_{i+1} - x_i}(x - x_i), \quad x_i \leq x \leq x_{i+1}\]

This produces a continuous function that is generally not smooth: the piecewise linear interpolant has corners at each interior node where two line segments meet. The first derivative is typically discontinuous at the nodes.

Advantage
No Runge's Phenomenon
Each piece uses only local data, so there is no tendency to oscillate far from the data. Reliable for any smooth function.
Advantage
Easy to Update
Adding a new data point affects only the pieces adjacent to the new node — not the entire interpolant.
Advantage
Reliable Convergence
The error decreases as \(h^2\) on each subinterval. Halving the subinterval width reduces the maximum error by a factor of 4.
Tradeoff
Not Smooth at Joints
The first derivative is typically discontinuous at interior nodes. Applications needing smooth derivatives require cubic splines (Chapter 5).

Error in Piecewise Linear Interpolation

On each subinterval \([x_i, x_{i+1}]\) of width \(h = x_{i+1} - x_i\), the error is bounded by:

\[|f(x) - p(x)| \leq \frac{h^2}{8} \max_{x_i \leq t \leq x_{i+1}} |f''(t)|\]
Example 4.5
Piecewise Linear Interpolation for cos x
  • Problem Data (approximately \(\cos x\)):
    \(x\)\(f(x)\)
    0.01.000
    0.50.878
    1.00.540
    1.50.071
    2.0−0.416
    Estimate \(f(0.75)\) and \(f(1.25)\).
  • Think For \(x = 0.75\): use subinterval \([0.5, 1.0]\). For \(x = 1.25\): use subinterval \([1.0, 1.5]\).
  • Compute f(0.75) \[p(0.75) = 0.878 + \frac{0.540 - 0.878}{1.0 - 0.5}(0.75 - 0.5) = 0.878 + \frac{-0.338}{0.5}(0.25) = 0.878 - 0.169 = \mathbf{0.709}\]
  • Compute f(1.25) \[p(1.25) = 0.540 + \frac{0.071 - 0.540}{1.5 - 1.0}(1.25 - 1.0) = 0.540 + \frac{-0.469}{0.5}(0.25) = 0.540 - 0.2345 = \mathbf{0.306}\]
  • Check \(\cos(0.75) \approx 0.7317\) and \(\cos(1.25) \approx 0.3153\). Errors are approximately 0.023 and 0.010 respectively — small given the step size of 0.5.
  • Interpret Piecewise linear interpolation gives \(f(0.75) \approx 0.709\) and \(f(1.25) \approx 0.306\), accurate to about 2 decimal places with node spacing 0.5.
Sections 4.11 – 4.14
Applications, Limitations, Mistakes, and What Comes Next
Real Applications · Unsafe Situations · Common Mistakes · Bridge to Splines and Least Squares
Section 4.11

Interpolation in Tables, Sensors, and Engineering Data

The abstract theory of this chapter connects directly to practical applications across many fields. Polynomial and piecewise interpolation are not academic exercises — they underlie tools used every day in science, engineering, and technology.

Mathematical Tables
Accessing Discrete Function Tables
Before electronic computation, books of sine, logarithm, and exponential tables listed values at discrete arguments. To find a value between entries, the reader applied linear or higher-order interpolation. Engineering handbooks and thermodynamic property tables still use this structure today.
Sensor Data
Reconstructing Continuous Signals
Engineering systems record temperature, pressure, flow rate, or voltage at discrete sample times. Between samples, the continuous quantity must be estimated. Piecewise linear interpolation provides the simplest reconstruction; cubic splines (Chapter 5) provide smoother versions.
Geographic Information
Elevation and Climate Maps
Elevation models, climate charts, and oceanographic maps represent continuously varying quantities at discrete measurement points. Interpolation fills in values between stations, creating the smooth spatial fields shown in maps and visualizations.
Computer Graphics
Motion Paths and Animation
Animated camera paths, character motions, and object deformations are defined at key frames. Interpolation — typically cubic spline interpolation — constructs smooth continuous motion between the key frames.
Signal Reconstruction
Digital Audio and Video
Digital audio and video store signals as discrete samples. Playback requires reconstructing a continuous signal from those samples. The choice of interpolation method significantly affects output quality.
Scientific Computing
Post-processing Solver Output
Finite element and finite difference solvers compute solutions at mesh points. Post-processing and visualization require interpolating those solutions to denser grids or to arbitrary evaluation points.
Section 4.12

When Interpolation Is Unsafe

Despite its broad applicability, polynomial interpolation can produce dangerously misleading results in several situations. Students should develop the habit of checking whether interpolation is appropriate before trusting an interpolated value.

SituationWhy Interpolation Is UnreliableBetter Approach
Extrapolation The polynomial may diverge rapidly outside the range of the nodes. The further from the nodes, the less reliable the estimate. Avoid extrapolation, or state explicit uncertainty. Never report extrapolated values as if they were interpolated.
Oscillatory or discontinuous functions Rapidly varying functions may be completely missed between nodes. Jump discontinuities force the polynomial to bridge them, creating large errors nearby. Use smaller subintervals, or a different basis (Fourier series, wavelets) suited to the function's structure.
Widely spaced nodes If the function varies significantly but nodes are sparse, the interpolant may miss that variation entirely. Increase sampling density in regions of rapid change.
High-degree polynomial over equally spaced nodes Runge's phenomenon: oscillation near the endpoints can make errors grow even as more nodes are added. Use Chebyshev nodes, or switch to piecewise interpolation.
Noisy data An interpolant that passes exactly through all data points fits the noise as well as the signal, amplifying measurement error. Use least-squares approximation (Chapter 5) rather than exact interpolation.
Chapter 4 — Back Matter

Common Interpolation Mistakes

Mistake 1
"Estimation between known data and estimation beyond it are both interpolation."
Interpolation estimates values between nodes. Extrapolation estimates beyond them. Polynomial interpolants may diverge rapidly outside the range of the nodes, making extrapolation unreliable. Students should always check that the evaluation point lies inside the range of the nodes before reporting a result without qualification.
Mistake 2
"More interpolation nodes always means more accuracy."
This is the lesson of Runge's phenomenon. For global polynomial interpolation over equally spaced nodes, adding more nodes can make the interpolant worse, not better, near the endpoints. Accuracy improves reliably only when the function is smooth, the nodes are well-placed (such as Chebyshev nodes), and the degree is not excessive. When in doubt, use piecewise interpolation.
Mistake 3
"The interpolant passes through points between the nodes exactly."
The interpolating polynomial passes exactly through the given data points. It does not pass through the true function values at other points. Between the nodes, the interpolant is an approximation, not an exact reconstruction. The interpolation error formula quantifies how far the approximation may stray.
Mistake 4
"Error analysis is optional once the polynomial is constructed."
Error analysis is part of responsible numerical practice. Students sometimes construct an interpolating polynomial and report an interpolated value without considering the error. The interpolation error formula provides an essential check. When the underlying function is known, students should compute or bound the error. When it is unknown, they should at least compare interpolants of different degrees to check stability.
Mistake 5
"The Lagrange form and Newton's form produce different polynomials for the same data."
The Lagrange formula and Newton's divided difference formula produce the same polynomial — only in different algebraic representations. There is exactly one interpolating polynomial for a given dataset. If the two constructions give different numerical results, a computational error has been made. They should be treated as two representations of one object, not two different approximations.
Mistake 6
"Interpolation is the right method for noisy measurement data."
Exact interpolation through noisy data fits the noise, not the signal. When data values contain measurement error, the interpolating polynomial passes exactly through the erroneous values, amplifying rather than filtering the noise. Least-squares approximation (Chapter 5) is the correct tool in this situation.

Chapter Summary

Key Terms

interpolation
Constructing a function that passes through known data points and using it to estimate values at unmeasured locations between those points.
interpolation node
One of the input values \(x_i\) at which the function value is known. Nodes must be distinct.
linear interpolation
Interpolation using a straight line through two data points. The simplest form of interpolation.
interpolating polynomial
The unique polynomial of degree at most \(n\) passing through \(n+1\) given data points.
Lagrange basis polynomial
A polynomial \(L_i(x)\) satisfying the cardinal condition: equal to 1 at node \(x_i\) and 0 at all other nodes.
Lagrange interpolation
The interpolating polynomial expressed as \(p_n(x) = \sum_i y_i L_i(x)\), using Lagrange basis polynomials as building blocks.
divided difference
A recursive measure of the rate of change of a function over a set of nodes, used as the coefficients in Newton's interpolating polynomial.
divided difference table
A triangular table organizing divided differences of increasing order, used to construct Newton's interpolating polynomial systematically.
Newton's interpolating polynomial
The interpolating polynomial expressed using divided differences in a form efficient for computation and updating.
interpolation error
The difference between the true function value and the interpolated polynomial value at an unmeasured point.
cardinal condition
The property of Lagrange basis polynomials: \(L_i(x_j) = 1\) if \(j = i\) and \(0\) if \(j \neq i\).
Runge's phenomenon
The tendency of high-degree polynomial interpolants over equally spaced nodes to oscillate violently near the endpoints of the interval, causing errors to grow rather than decrease as \(n\) increases.
equally spaced nodes
Interpolation nodes placed at uniform distances across an interval. Convenient but susceptible to Runge's phenomenon at high degree.
Chebyshev nodes
Interpolation nodes clustered near the endpoints of an interval, designed to minimize the worst-case interpolation error and avoid Runge's phenomenon.
piecewise interpolation
Interpolation using a different low-degree polynomial on each subinterval between consecutive nodes, avoiding the oscillation that can plague high-degree global polynomials.
piecewise linear interpolant
A piecewise interpolant using straight line segments on each subinterval. Continuous but not differentiable at interior nodes.
extrapolation
Estimation of function values outside the range of the interpolation nodes. Generally unreliable; polynomials may diverge rapidly beyond the data range.
node product
The product \(\omega(x) = (x - x_0)(x - x_1)\cdots(x - x_n)\) appearing in the interpolation error formula. Its size controls how the error varies across the interval.
ReviewConcept Review Questions
  1. What is the difference between interpolation and extrapolation? Why is extrapolation less reliable?
  2. State the existence and uniqueness result for polynomial interpolation. What conditions are required on the nodes?
  3. Explain in words what the Lagrange basis polynomial \(L_i(x)\) does. What is its value at node \(x_i\)? What is its value at any other node?
  4. What is a divided difference? How is a second-order divided difference computed from first-order divided differences?
  5. What does the interpolation error formula tell a student? What information is needed to apply it as a bound?
  6. Explain Runge's phenomenon in your own words. What causes it, and what are the two main ways to avoid it?
  7. What is the advantage of using Chebyshev nodes instead of equally spaced nodes for polynomial interpolation?
  8. Compare global polynomial interpolation with piecewise linear interpolation. What does piecewise interpolation gain? What does it sacrifice?
  9. In what situations is polynomial interpolation unsafe or unreliable?
  10. Why is interpolation inappropriate for noisy data? What method should be used instead?
PracticeSkill Practice
  1. 4.1. Two data points are given: \((2, 5)\) and \((6, 13)\). Use linear interpolation to estimate the function value at \(x = 4\).
  2. 4.2. Three data points are \((0, 1)\), \((1, 2)\), \((3, 10)\). Construct the Lagrange interpolating polynomial \(p_2(x)\) and evaluate it at \(x = 2\).
  3. 4.3. Four data points are \((0, 1)\), \((1, e)\), \((2, e^2)\), \((3, e^3)\) with \(e \approx 2.718\). Construct the divided difference table.
  4. 4.4. Using the divided difference table from Problem 4.3, write Newton's interpolating polynomial and evaluate it at \(x = 1.5\).
  5. 4.5. Verify that the Lagrange basis polynomials for nodes \(x_0 = 1\), \(x_1 = 3\), \(x_2 = 5\) satisfy \(L_0(1) = 1\), \(L_0(3) = 0\), \(L_0(5) = 0\).
  6. 4.6. Suppose a function is interpolated at four equally spaced nodes on \([0, 1]\). If \(|f^{(4)}(x)| \leq 5\) on \([0, 1]\), bound the interpolation error.
  7. 4.7. Apply piecewise linear interpolation using the data: \((0, 0)\), \((1, 1)\), \((4, 2)\), \((9, 3)\). Estimate \(f(2)\) and \(f(6)\).
  8. 4.8. Four nodes are equally spaced on \([-1, 1]\). Describe qualitatively how the interpolating polynomial for \(f(x) = 1/(1+25x^2)\) would behave near \(x = \pm 1\) compared to near \(x = 0\). What is this phenomenon called?
PracticeAlgorithm Practice
  1. 4.9. Apply the Lagrange interpolation algorithm by hand to estimate \(f(2.5)\) using the data \((1, 0)\), \((2, 0.693)\), \((3, 1.099)\). Show all intermediate values of the basis polynomials \(L_0, L_1, L_2\) at \(x = 2.5\).
  2. 4.10. Build the divided difference table for the data \((0, 0)\), \((1, 1)\), \((2, 8)\), \((3, 27)\). What pattern do the entries in the third-order column suggest about the underlying function?
  3. 4.11. Write out the steps of Newton's interpolation algorithm in full for the data \((1, 2)\), \((2, 3)\), \((4, 5)\). Evaluate the resulting polynomial at \(x = 3\).
  4. 4.12. Verify that Newton's interpolating polynomial and the Lagrange interpolating polynomial produce the same result at \(x = 2.5\) for the data \((1, 1)\), \((2, 4)\), \((3, 9)\).
PracticeComputational Interpretation
  1. 4.13. A student constructs a degree-5 interpolating polynomial through six data points and finds that the polynomial oscillates between values of \(-50\) and \(+60\) near the right endpoint, while the data values are all between 0 and 10. What is likely happening? What should the student do?
  2. 4.14. A table of values of \(\sqrt{x}\) is given at \(x = 1, 4, 9, 16, 25\). Explain why the spacing of these nodes is not uniform. Does this affect the validity of polynomial interpolation? Does it affect the divided difference construction?
  3. 4.15. Two engineers use the same 9 data points to build interpolants: Engineer A uses a single degree-8 polynomial with equally spaced nodes; Engineer B uses piecewise linear interpolation. In what situations would Engineer A's approach be more accurate? In what situations would Engineer B's approach be safer?
  4. 4.16. A student evaluates an interpolating polynomial at a point 20% beyond the range of the nodes and reports the result confidently. What is the mathematical term for this estimation, and what caution should the student express about the reliability of the result?
ApplicationsApplications
  1. 4.17 (Engineering). A structural engineer records the displacement of a beam at five points along its length:
    Position (m)Displacement (mm)
    0.00.00
    0.52.34
    1.04.12
    1.53.87
    2.00.00
    Use piecewise linear interpolation to estimate the displacement at \(x = 0.75\) m and \(x = 1.25\) m.
  2. 4.18 (Physics). A physics experiment records the pressure of a gas at several temperatures:
    Temperature (K)Pressure (kPa)
    200120
    250150
    300180
    350210
    Apply Newton's divided differences to estimate the pressure at 275 K. What degree polynomial does the divided difference table suggest the data follows?
  3. 4.19 (Finance). The closing price of a stock is recorded on five trading days: Day 1: $102.50, Day 3: $104.20, Day 5: $101.80, Day 7: $106.50, Day 9: $108.00. Use linear interpolation to estimate the price on Day 4. Explain why polynomial interpolation of stock prices carries significant uncertainty regardless of the method used.
  4. 4.20 (Computer Graphics). An animation studio defines a camera path by five key-frame positions at times \(t = 0, 1, 2, 3, 4\) seconds. The horizontal coordinate values are 10, 14, 20, 18, 22. Apply Lagrange interpolation to estimate the camera position at \(t = 2.5\) seconds. What concern about interpolation should the technical team keep in mind?
Error AnalysisError Analysis
  1. 4.21. Suppose \(f(x) = e^x\) is interpolated using two nodes \(x_0 = 0\) and \(x_1 = 1\). Write the interpolation error formula for this linear interpolant. Bound the maximum error on \([0, 1]\).
  2. 4.22. For the data in Example 4.3, the estimate at \(x = 1.8\) was 0.5888, while the true value is \(\ln(1.8) \approx 0.5878\). Calculate the absolute and relative errors.
  3. 4.23. A student uses a degree-3 polynomial to interpolate a function on \([0, 4]\) with four equally spaced nodes. If \(|f^{(4)}(x)| \leq 24\) on \([0, 4]\), bound the maximum interpolation error on \([0, 4]\).
  4. 4.24. Piecewise linear interpolation is applied to a function on \([0, 1]\) with ten equally spaced subintervals. If \(|f''(x)| \leq 4\) on \([0, 1]\), bound the maximum error in the piecewise linear interpolant. If twenty subintervals are used instead, how does the error bound change, and by what factor?
Chapter 4 Checkpoint
Confirm your understanding before moving to Chapter 5
Core Concepts
  • I can explain what interpolation is and distinguish it from extrapolation.
  • I can state the existence and uniqueness theorem for the interpolating polynomial.
  • I understand that the Lagrange and Newton forms represent the same unique polynomial.
  • I can explain Runge's phenomenon and why it occurs with equally spaced nodes.
  • I can describe two strategies for avoiding Runge's phenomenon.
  • I can explain why piecewise interpolation does not suffer from Runge's phenomenon.
  • I can identify situations where polynomial interpolation is unsafe or unreliable.
Construction and Computation
  • I can apply the linear interpolation formula to two data points.
  • I can construct the Lagrange interpolating polynomial for three or four data points.
  • I can build a divided difference table and write Newton's interpolating polynomial.
  • I can evaluate Newton's polynomial at a given point using the computed coefficients.
  • I can apply piecewise linear interpolation on each relevant subinterval.
Error and Reliability
  • I can state the interpolation error formula and identify what each factor represents.
  • I can use the error formula to produce an upper bound when the function is known.
  • I can state the piecewise linear error bound and explain how it depends on subinterval width.
  • I know why error analysis cannot be skipped in responsible numerical work.
Integrated Problems
  • I can work a checkpoint problem that combines divided difference construction, Newton polynomial evaluation, and error estimation.
  • I can write a clear paragraph explanation of Runge's phenomenon for a classmate.
  • I can advise a practitioner on whether polynomial or piecewise interpolation is more appropriate for a described situation.
Methods Reference — Chapter 4
Linear Interpolation
\[p_1(x) = y_0 + \frac{y_1 - y_0}{x_1 - x_0}(x - x_0)\]
Lagrange Basis Polynomial
\[L_i(x) = \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}, \quad L_i(x_j) = \begin{cases} 1 & j = i \\ 0 & j \neq i \end{cases}\]
Lagrange Interpolating Polynomial
\[p_n(x) = \sum_{i=0}^{n} y_i L_i(x)\]
Divided Difference (recursive)
\[f[x_i, \ldots, x_{i+k}] = \frac{f[x_{i+1}, \ldots, x_{i+k}] - f[x_i, \ldots, x_{i+k-1}]}{x_{i+k} - x_i}\]
Newton's Interpolating Polynomial
\[p_n(x) = f[x_0] + f[x_0,x_1](x-x_0) + f[x_0,x_1,x_2](x-x_0)(x-x_1) + \cdots\]
Interpolation Error Formula
\[f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}(x-x_0)(x-x_1)\cdots(x-x_n)\]
Piecewise Linear Error Bound (per subinterval of width h)
\[\left|f(x) - p(x)\right| \leq \frac{h^2}{8}\max\left|f''\right|\]
Chebyshev Nodes on [−1, 1]
\[x_i = \cos\!\left(\frac{(2i+1)\pi}{2(n+1)}\right), \quad i = 0, 1, \ldots, n\]
Bridge Note — Chapter 5
Splines, Curve Fitting, and Least Squares

Chapter 4 developed exact polynomial interpolation: given data points, construct a polynomial passing exactly through all of them. Chapter 5 extends these ideas in two directions. The first direction is piecewise polynomial interpolation with smooth joints — cubic spline interpolation. A piecewise linear interpolant is continuous but has corners at interior nodes. A cubic spline goes further: piecewise cubic with continuous first and second derivatives everywhere, including at the joints. Cubic splines produce smooth curves that behave well for numerical differentiation and integration and are among the most widely used interpolants in practice. The second direction is least-squares curve fitting. When data contains noise or measurement error, exact interpolation is counterproductive — the polynomial passes through the noise rather than the signal. Least-squares fitting minimizes total squared error between the approximating function and the data. Together, splines and least squares address the two most common reasons exact polynomial interpolation is insufficient: sharp corners at the nodes, and noisy data.

MGU Library Connection
  • Numerical Methods — Appendix H: Interpolation Formula Reference
  • Numerical Methods — Appendix J: Numerical Differentiation Formula Sheet (derived from interpolating polynomials)
  • Numerical Methods — Appendix K: Numerical Integration Formula Sheet (trapezoidal and Simpson's rules derived from interpolants)
  • Companion: MGU Algorithm Reference — Lagrange Interpolation and Newton Divided Differences
  • Companion: MGU Linear Algebra — Vandermonde Systems and Interpolation as a Linear Algebra Problem
  • See Chapter 5 for cubic splines and least-squares fitting
  • See Chapter 6 for numerical differentiation formulas derived from interpolating polynomials
  • See Chapter 7 for numerical integration rules derived from interpolants