Skip to content
Tutorials Center
My learning

Topics

Lesson 50 of 68 ยท Linear Algebra and Numerical Methods

Root Finding and Interpolation

Solve f(x) = 0 with bisection, secant and Newton methods, then fill gaps between data points with polynomial and spline interpolation in Python.

Two jobs come up constantly in engineering computation. The first is root finding: find the x where f(x) = 0. A pipe-flow friction factor, the operating point of a circuit with a diode, the time at which a rocket hits the ground: all of them are equations that no algebra will solve in closed form. The second is interpolation: you have measurements at a few points and need a smooth value in between. A lookup table of material properties and a sampled sensor trace are typical examples.

Both are numerical methods built on ideas you already know. Root finding reuses the intermediate value theorem from Continuity and the tangent line from Linearization and Newton's Method. Interpolation uses polynomials, which you met in Taylor and Maclaurin Series.

Three ways to find a root

We will solve x**3 - 2x - 5 = 0, which has a single real root near 2.0946.

Bisection needs a bracket [a, b] where f(a) and f(b) have opposite signs. Cut the interval in half, keep the half that still has a sign change, repeat. It always works for continuous functions, but it gains only one binary digit per step.

Newton's method uses the tangent line at the current guess: x_new = x - f(x)/f'(x). It needs the derivative and a decent starting point, but it converges extremely fast near a simple root.

The secant method is Newton with the derivative replaced by the slope through the last two points. It needs no derivative and is almost as fast.

flowchart TD
    A["Need a root of f"] --> B{"Is there a bracket<br/>with a sign change?"}
    B -- yes --> C{"Is f' available<br/>and cheap?"}
    B -- no --> D["Find a bracket first<br/>or start Newton near the root"]
    C -- yes --> E["Newton, protected by<br/>a bracket as a fallback"]
    C -- no --> F["Secant or Brent's method"]

A practical way to choose a root finder.

Python Bisection, secant and Newton compared

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Bisection needs 40 iterations to shrink an interval of width 1 to about 1e-12, since 2**-40 is roughly 1e-12. The secant method takes 7 and Newton 6. That gap is the difference between linear convergence (a fixed factor per step) and superlinear or quadratic convergence (the number of correct digits roughly doubles per Newton step).

Newton's speed and its failures

Near a simple root, Newton's error roughly squares each step: 0.09, then 0.005, then 1.7e-5, then 1.6e-10. But the method has no safety net. It fails when f'(x) is zero or tiny, when the starting point lies in the wrong basin, or when the function is not smooth enough at the root. The classic example is the real cube root: its tangent lines send you twice as far from the root every time.

Python Quadratic convergence and a divergent case

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the cube root, each step doubles the distance and flips the sign: -2, 4, -8, 16, -32. A bracketing method would have found the root at 0 without trouble. This is why production code, such as scipy.optimize.brentq, combines the guaranteed progress of bisection with the speed of secant and interpolation steps. When you do use Newton, add a maximum iteration count and a check that |f(x)| actually decreases.

Stop on both criteria: the step size is small and the residual |f(x)| is small. A tiny step alone can mean the method is crawling; a tiny residual alone can mean the function is flat near the root.

Interpolation: filling the gaps

Given points (x0, y0), ..., (xn, yn), an interpolating function passes exactly through every point. The simplest choice is linear interpolation: connect neighbouring points with straight lines. It is robust but has corners, so its slope jumps at every data point.

A polynomial of degree n can pass through n + 1 points exactly, and it is unique. The Lagrange and Newton forms are two ways to write it, and np.polyfit or scipy.interpolate.BarycentricInterpolator compute it. High degree has a dark side, as the next section shows.

A cubic spline glues together a separate cubic on each interval, requiring that the pieces agree in value, slope and curvature at every data point. This gives a smooth curve with no wild swings, and it is the standard tool for tabulated data.

Python Linear, polynomial and spline interpolation of sensor data

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The three methods agree to within a degree or two between the samples, but they differ in character. The spline also gives you a derivative for free: its slope at t = 5 is about 3.05 degrees per second, a smooth estimate of the heating rate. On the sine test with seven points, the spline's worst error is about 1e-3, thirty times smaller than the linear interpolant's 3e-2.

Newton's divided differences and Lagrange form

The interpolating polynomial through n + 1 points is unique, but it can be written in two useful ways.

Lagrange form. Build one basis polynomial per node, L_i(x) = product over j != i of (x - xj) / (xi - xj). It equals 1 at node xi and 0 at every other node, so p(x) = sum of yi L_i(x) passes through all the points. It is easy to explain and to code, but if you add a new data point you must recompute everything.

Newton form. Write the polynomial as a nested sum that grows one term at a time:

p(x) = c0 + c1 (x - x0) + c2 (x - x0)(x - x1) + ... + cn (x - x0)...(x - x(n-1))

The coefficients are the divided differences, built from a triangular table. The first column holds the values f[xi] = yi, and each later column divides the difference of two neighbours by the span of x values they cover:

f[xi, ..., x(i+k)] = (f[x(i+1), ..., x(i+k)] - f[xi, ..., x(i+k-1)]) / (x(i+k) - xi)

The top row of the table, c_k = f[x0, ..., xk], gives the coefficients. Adding a new data point appends one new row to the table and one new term to p; nothing already computed changes. That is the practical advantage of the Newton form. Divided differences also work for unequally spaced x, and they are symmetric in their arguments.

Python Divided-difference table, Newton form and Lagrange form

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The top row 1, 2, -1.5, 0.5833 means p(x) = 1 + 2x - 1.5 x(x - 1) + 0.5833 x(x - 1)(x - 2). All three evaluations agree at every test point (for instance 2.59375 at x = 0.5), as they must: they are the same unique polynomial in different clothes. After adding the point (5, 4), the first four coefficients are unchanged and only a fifth one, -0.2, is appended.

Equally spaced nodes: forward differences

When the nodes are equally spaced by h, the divisions become trivial and the table reduces to repeated subtraction. The forward differences are Delta y_i = y(i+1) - y_i, Delta**2 y_i = Delta y(i+1) - Delta y_i, and so on. With s = (x - x0) / h, Newton's forward formula is

p(x) = y0 + s Delta y0 + s(s - 1)/2! Delta**2 y0 + s(s - 1)(s - 2)/3! Delta**3 y0 + ...

Use it for points near the start of a table. Backward differences (nabla y_i = y_i - y(i-1)) give an analogous formula that is centred on the last entry, suited to points near the end of the table.

The error

If f has n + 1 continuous derivatives, the error of the degree-n interpolant is

f(x) - p(x) = f^(n+1)(xi) / (n + 1)! * (x - x0)(x - x1)...(x - xn)

for some xi in the interval. Two practical messages follow: the error is small near the middle of the nodes and larger near the ends (the product term is biggest there), and it is controlled by the high derivative of f, which for unlucky functions grows quickly. That is the root of the Runge phenomenon in the next section.

Python Forward differences and the error bound

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The difference table shrinks and smooths out as the order rises, and the degree-4 formula gives sin(0.8) to about 2e-4 (0.717541 against 0.717356), inside the bound of 3.4e-4 computed from the error formula.

The Runge phenomenon

More points should mean a better fit, right? Not with equally spaced points and a single high-degree polynomial. Carl Runge showed that for f(x) = 1/(1 + 25 x**2) on [-1, 1], the interpolating polynomial through equally spaced points oscillates wildly near the ends, and the error grows as the degree rises.

Two cures work well. One is to place the points more densely near the ends, using Chebyshev nodes cos((2k + 1) pi / (2n)). The other is to stop using one big polynomial and use a piecewise low-degree interpolant such as a spline.

Python Runge's example: equispaced, Chebyshev and spline

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The table tells the story. With equally spaced points the maximum error climbs from about 0.44 (5 points) to 59.8 (21 points), so adding data made the fit worse. With Chebyshev nodes it falls steadily to about 0.015, and the spline error falls to about 0.003. In the plot, the equispaced curve shoots far outside the picture near the ends.

Practical guidance

  • To solve one equation, use scipy.optimize.brentq with a bracket, or newton with a derivative. For systems, see scipy.optimize.root.
  • Never extrapolate far outside your data: both polynomials and splines can go badly wrong.
  • Use a spline (or PchipInterpolator, which never overshoots monotone data) rather than a high-degree polynomial on tabulated data.
  • If your data are noisy, do not interpolate; fit a model instead. That is the subject of Statistics, Curve Fitting and Uncertainty.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What must be true of the starting interval for the bisection method?

    A sign change plus continuity guarantees a root inside, by the intermediate value theorem. Bisection keeps the half that still has a sign change.
  2. 2. Newton's method applied to the cube root of x starting at x = 1 does what?

    The update works out to x_new = -2x, so the distance from the root doubles and the sign flips every iteration.
  3. 3. What does a cubic spline require at the data points?

    Each interval has its own cubic, and the pieces are joined so the curve and its first two derivatives are continuous.
  4. 4. How can the Runge phenomenon be reduced?

    Clustering nodes near the ends, or switching to splines, avoids the large end oscillations of equispaced high-degree polynomials.

Summary

  • Bisection is slow but certain; Newton is fast but needs a derivative and a good start; the secant method is a derivative-free compromise; brentq combines safety and speed.
  • Newton's error roughly squares each step near a simple root, but it can diverge, so cap iterations and check the residual.
  • Interpolation passes exactly through the data: linear is robust, cubic splines are smooth, high-degree polynomials can oscillate.
  • The Runge phenomenon shows that more equispaced points can make a polynomial fit worse; use Chebyshev nodes or splines.
  • Do not interpolate noisy data and do not extrapolate far.

Next: Floating-Point Error and Conditioning.