Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 37 ยท Root Finding

Fixed-Point Iteration and Root Finding with SciPy

Learn fixed-point iteration and the contraction condition, then use SciPy's brentq, newton, root_scalar and root to solve single equations and nonlinear systems.

You met fixed-point iteration in the very first lesson, when repeatedly applying cos homed in on the solution of cos(x) = x. This lesson explains why that worked, shows when it fails, and then moves to the professional tools: SciPy's root finders for single equations and for systems of equations.

A fixed point of a function g is a number p with g(p) = p. Finding a root of f(x) = 0 is the same as finding a fixed point of g(x) = x - f(x) (or of any rearrangement like g(x) = x + c f(x)). The iteration is as simple as it gets:

x_(k+1) = g(x_k)

When does it converge?

Let p be a fixed point and e_k = x_k - p. By the mean value theorem, e_(k+1) = g(x_k) - g(p) = g'(ฮพ) e_k for some ฮพ between them. So the error is multiplied by about |g'(p)| at each step. This gives the key rule:

  • If |g'(p)| < 1, the iteration converges (for a starting guess close enough). It is linear with ratio |g'(p)|.
  • If |g'(p)| > 1, it diverges.
  • If g'(p) = 0, it converges faster than linear. Newton's method is exactly this case: its g(x) = x - f/f' has g'(r) = 0 at a simple root.

A function with |g'| โ‰ค L < 1 on an interval, mapping the interval into itself, is a contraction, and the Banach fixed-point theorem guarantees a unique fixed point and convergence from any start in the interval.

Different rearrangements, different outcomes

Any equation can be rearranged into x = g(x) in many ways. Take xยณ + x - 1 = 0. Different rearrangements give different behaviours:

Python Two rearrangements of one equation

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 first rearrangement has |g'(p)| = 3pยฒ โ‰ˆ 1.4 > 1: it never settles (it bounces between values near 0 and 1). The second and third have |g'(p)| of about 0.7 and 0.6 at the root, so they converge, but only linearly and slowly (50 to 60 steps for ten digits). Same equation, same root, completely different behaviour. Always check |g'| near the expected root (or just try it and watch).

flowchart TD
    A["f(x) = 0"] --> B["Rewrite as x = g(x)"]
    B --> C{"|g'(p)| < 1 ?"}
    C -->|"yes"| D["Converges linearly"]
    C -->|"no"| E["Try another<br/>rearrangement or use Newton"]

The rewriting step decides the fate of fixed-point iteration.

Speeding it up: Aitken's delta-squared

A linearly converging sequence can be accelerated. Given three consecutive iterates, Aitken's extrapolation estimates the limit:

xฬ‚ = x_k - (x_(k+1) - x_k)ยฒ / (x_(k+2) - 2 x_(k+1) + x_k)

Applying this every three steps is Steffensen's method, which reaches quadratic convergence without any derivative.

Python Steffensen's method

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.

Four or five rounds replace 58 plain steps. Each round costs two evaluations of g.

Root finding with SciPy: single equations

In practice you rarely write the loops yourself. scipy.optimize offers well-tested routines.

Function Needs Notes
brentq(f, a, b) bracket Best general choice: guaranteed and fast
bisect(f, a, b) bracket Plain bisection
newton(f, x0, fprime=...) start (and optionally f') Newton if fprime given, else secant
root_scalar(f, ...) method name Unified interface with a result object
Python Single-variable root finders in SciPy

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.

brentq needs far fewer iterations than bisect yet keeps the bracket guarantee. Remember that newton in SciPy silently becomes the secant method without fprime, and that it raises RuntimeError if it does not converge, so catch that when scanning many problems.

Systems of nonlinear equations

Many problems have several unknowns: find (x, y) such that xยฒ + yยฒ = 4 and x y = 1. Newton's method generalises: replace f' by the Jacobian matrix J of partial derivatives, and solve a linear system at each step: J(x_k) ฮ” = -F(x_k), then x_(k+1) = x_k + ฮ”. You will solve linear systems in the next chapter; here we reuse NumPy.

Python Newton for a 2D system, then SciPy's root()

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 residual norm drops quadratically, just as in the one-dimensional case. Without the Jacobian, root estimates it by finite differences (omit jac), which is convenient but costs extra function calls.

Pick the tool by what you know: a bracket means brentq; a smooth f and a good guess means newton; several unknowns means root. For all of them, plot or tabulate the function first so you know how many roots to expect and where.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. When does the fixed-point iteration x_(k+1) = g(x_k) converge to a fixed point p?

    The error is multiplied by about |g'(p)| each step, so it shrinks only if that factor is below 1.
  2. 2. Why does Newton's method converge faster than a generic fixed-point iteration?

    For g(x) = x - f/f', the derivative at the root vanishes, giving quadratic convergence.
  3. 3. Which SciPy function is the usual first choice when you can bracket a root?

    Brent's method is guaranteed (bracket) and fast (interpolation).
  4. 4. What does scipy.optimize.newton do when you do not pass fprime?

    Without a derivative it falls back to the secant method.
  5. 5. What replaces f'(x) when Newton's method is applied to a system F(x) = 0?

    At each step solve J(x_k) delta = -F(x_k), then update x.

Summary

  • Root finding f(x) = 0 can be rewritten as fixed-point iteration x = g(x); it converges if |g'(p)| < 1, with linear rate.
  • The rewriting matters: different g for the same equation can converge or diverge.
  • Aitken and Steffensen acceleration turn linear convergence into quadratic.
  • SciPy: brentq for brackets, newton for smooth problems, root_scalar for a unified interface, root for systems.
  • Newton for systems needs the Jacobian and one linear solve per iteration.

Next: Gaussian Elimination