Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 37 ยท Getting Started

Iteration, Convergence and Stopping Rules

Understand iterative methods, linear and quadratic convergence, how to measure the order of convergence in code, and how to choose safe stopping criteria.

Almost every numerical method is an iteration: start with a guess x0, apply a rule to get x1, apply it again to get x2, and keep going. If the guesses approach the true answer, the method converges. Two questions decide whether a method is any good. How fast does it converge? And when do you stop?

This lesson gives you the vocabulary (order of convergence, tolerance, residual) and the code to measure it. You will use it in every later chapter, from root finding to linear systems to differential equations.

The shape of an iterative method

An iterative method has three parts: an initial guess, an update rule and a stopping rule. In code that is a loop with a safety limit.

Python
def iterate(update, x0, tol=1e-10, max_iter=100):
    x = x0
    for k in range(1, max_iter + 1):
        x_new = update(x)
        if abs(x_new - x) < tol:
            return x_new, k
        x = x_new
    raise RuntimeError("did not converge")

Always include max_iter. A method that diverges or cycles would otherwise run forever.

Python A reusable iteration loop

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.

Both loops use the same code, yet the second needed far fewer steps. The reason is the order of convergence.

Error and order of convergence

Let x* be the true answer and e_k = |x_k - x*| the error after k steps. If the errors satisfy

e_(k+1) โ‰ˆ C * e_k^p

then p is the order and C the asymptotic constant.

Order p Name What it means
1 (and C < 1) Linear The error is multiplied by a constant C each step: you gain a fixed number of digits per step
between 1 and 2 Superlinear Faster than linear (the secant method has p โ‰ˆ 1.618)
2 Quadratic The number of correct digits roughly doubles each step (Newton's method)

A linear method with C = 0.1 gains one digit per step. A quadratic method that has 3 correct digits has about 6 after the next step and 12 after that. This is why order matters far more than a few percent of speed.

flowchart LR
    A["Error 1e-1"] --> B["Linear: 1e-2, 1e-3, 1e-4"]
    A --> C["Quadratic: 1e-2, 1e-4, 1e-8"]

Starting from the same error, quadratic convergence finishes in far fewer steps.

Measuring the order from data

You can estimate p without any theory. If you know the true value, take the logs of consecutive errors:

p โ‰ˆ log(e_(k+1) / e_k) / log(e_k / e_(k-1))

Python Estimate the order of convergence

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 list climbs towards 2 (quadratic), the second hovers around 1 (linear). Rounding noise can disturb the last estimate once the error reaches 1e-16, so ignore estimates from errors close to machine precision.

Stopping rules

When the exact answer is unknown (the usual case) you need something you can compute. Three tests are common.

Test Formula Warning
Step size abs(x_new - x) < tol Can stop early on a slowly moving iteration
Relative step abs(x_new - x) < tol * abs(x_new) Fails when the answer is near zero
Residual abs(f(x_new)) < tol A small residual does not guarantee a small error when f is flat

A robust choice combines absolute and relative tolerance, the way NumPy's isclose does:

Python
def close_enough(x_new, x, atol=1e-12, rtol=1e-10):
    return abs(x_new - x) <= atol + rtol * abs(x_new)

Also stop on max_iter and report that the method failed, rather than returning a poor answer silently.

Python Why the residual can mislead

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.

At x = 1.1 the residual is only 1e-6 although the answer is off by 0.1. If you stopped when abs(f(x)) < 1e-5 you would accept a poor result. Flat functions need a stricter residual tolerance or a check on the step as well.

Never use tol = 0 or a tolerance below machine precision (about 2.2e-16 relative). Rounding errors then keep the test false forever and the loop runs to max_iter.

Divergence and cycling

An iteration need not converge. The rule x <- 2 * x runs away to infinity, and x <- -x bounces between two values forever. Always watch for:

  • growth without bound (the step keeps getting larger),
  • oscillation (the same two or three values repeat),
  • nan or inf appearing.

In later lessons you will see conditions that guarantee convergence, such as bracketing in bisection and the contraction condition in fixed-point iteration.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A method has quadratic convergence and currently has 4 correct digits. Roughly how many after the next step?

    Quadratic convergence roughly doubles the number of correct digits each step, so 4 becomes about 8.
  2. 2. What is wrong with stopping only when abs(f(x)) < tol?

    A flat function has tiny values over a wide interval, so a small residual does not guarantee a small error.
  3. 3. Why should every iterative loop have a max_iter limit?

    Not every iteration converges, so a cap turns an endless loop into a clear failure.
  4. 4. Errors in successive steps are 1e-2, 1e-3, 1e-4. What is the convergence?

    Each error is one tenth of the previous: linear convergence with C = 0.1.
  5. 5. Why combine an absolute and a relative tolerance?

    atol + rtol * abs(x) behaves sensibly for both tiny and huge answers.

Summary

  • An iterative method needs a start, an update rule, a stopping rule and a max_iter limit.
  • Order p and constant C describe e_(k+1) โ‰ˆ C e_k^p; linear gains a fixed number of digits per step, quadratic doubles them.
  • Estimate p from logs of successive errors.
  • Stop on a combined absolute and relative step test, and consider the residual too.
  • Watch for divergence, cycling and nan.

Next: Your First Method: Square Roots