Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 37 ยท Errors and Floating Point

Conditioning and Stability

Learn the difference between ill-conditioned problems and unstable algorithms, compute the condition number of a function, and see Wilkinson's polynomial in action.

When a computed answer is wrong, there are two possible culprits. Either the problem is so sensitive that small changes in the input change the answer a lot (it is ill-conditioned), or the algorithm you chose adds avoidable error (it is unstable). Telling these apart is one of the most useful skills in numerical analysis, because the cures are different: a better algorithm can fix instability, but nothing can fix an ill-conditioned problem except more precise data or a reformulation.

You have already seen both ideas indirectly. Cancellation in 1 - cos(x) was a stability problem, fixed by a better formula. This lesson focuses on the other half.

The condition number of a function

Imagine evaluating y = f(x) when x is slightly wrong, say xฬ‚ = x(1 + ฮด). How big is the resulting relative change in y? To first order,

|f(xฬ‚) - f(x)| / |f(x)| โ‰ˆ ฮบ ร— |xฬ‚ - x| / |x|, with ฮบ(x) = |x f'(x) / f(x)|

The number ฮบ is the relative condition number. It is the amplification factor between relative input error and relative output error. A rule of thumb: you lose about log10(ฮบ) decimal digits just because of the problem.

ฮบ Meaning
near 1 well-conditioned: errors stay about the same size
1e3 lose about 3 digits
1e16 no digits survive in double precision
Python Condition numbers of some functions

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.

Notice that sqrt always has ฮบ = 1/2 (errors are halved: very safe), x^10 has ฮบ = 10, and exp(x) has ฮบ = |x|. The subtraction x - 1 near x = 1 has an enormous ฮบ of about ten million: subtracting nearly equal numbers is an ill-conditioned problem, which is exactly the cancellation of the last lesson, now explained as a property of the operation itself.

Seeing ill-conditioning: Wilkinson's polynomial

James Wilkinson's famous example is the polynomial with roots 1, 2, ..., 20:

P(x) = (x - 1)(x - 2) ... (x - 20)

Expanded, the coefficient of x^19 is -210. Wilkinson changed that single coefficient by 2^-23 โ‰ˆ 1.2e-7 (a relative change of about 6e-10) and found that several roots moved by large amounts and even became complex. The roots of high-degree polynomials are extremely sensitive to the coefficients.

Python Wilkinson's polynomial

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.

A relative change of one part in a billion in one coefficient pushes some roots by amounts of order 1 and turns them complex. The roots are perfectly well-defined mathematically; the problem "find the roots from the coefficients" is just very ill-conditioned. Moral: do not represent polynomials by their expanded coefficients if you can avoid it.

Stability of algorithms

An algorithm is stable if it does not add error beyond what the problem's conditioning allows. An unstable algorithm magnifies rounding errors even on a well-conditioned problem.

A classic example: compute the integrals E_n = โˆซโ‚€ยน x^n e^(x-1) dx. Integration by parts gives E_n = 1 - n E_(n-1) with E_0 = 1 - 1/e. The problem is well-conditioned (the true E_n are small and decrease), but the recurrence multiplies the previous error by n at each step, so a rounding error 1e-16 at the start grows like n!.

Python An unstable recurrence versus a stable one

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 forward results lose their digits by n = 15 and are garbage by n = 18: at n = 20 the recurrence gives about -30, which is impossible for an integral of a positive function that is at most 1/(n+1). Running the recurrence backwards divides the error by n at each step, so even a terrible starting guess is forgotten. Same equation, same data, completely different stability.

flowchart TD
    A["Bad result"] --> B{"Change the input<br/>slightly. Does the<br/>answer jump?"}
    B -->|"yes, for every algorithm"| C["Ill-conditioned problem<br/>reformulate or get better data"]
    B -->|"no, the problem is fine"| D["Unstable algorithm<br/>choose another method"]

A quick diagnostic: conditioning belongs to the problem, stability to the algorithm.

How to tell in practice

You can run two cheap experiments before trusting a result:

  1. Perturb the input by a relative 1e-8. If the output changes by much more than 1e-8, the problem is sensitive (large ฮบ).
  2. Change the algorithm or precision: recompute in float32 versus float64, or with an algebraically equivalent formula. If results disagree, the first one is suspect.
Python Perturbation experiment

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 output is an estimate of ฮบ. Near a zero of the function, such as sin near ฯ€ or the parabola near its double root, ฮบ explodes. That is why finding roots (especially multiple roots) is delicate, a theme that returns in Chapter 3.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a large condition number tell you?

    Conditioning is a property of the problem, independent of the algorithm.
  2. 2. The relative condition number of f(x) = sqrt(x) is

    kappa = |x f'(x)/f(x)| = |x * (1/(2 sqrt x)) / sqrt x| = 1/2.
  3. 3. Why is the forward recurrence E_n = 1 - n E_(n-1) unstable?

    The problem is well-conditioned, but this algorithm amplifies earlier rounding errors.
  4. 4. A relative condition number of 1e10 means that in double precision you lose roughly how many digits to the problem?

    You lose about log10(kappa) = 10 decimal digits, leaving around 6.
  5. 5. What does Wilkinson's polynomial illustrate?

    A change of about 1e-7 in one coefficient moves some roots enormously.

Summary

  • The condition number ฮบ = |x f'(x) / f(x)| measures the problem's amplification of relative input errors; expect to lose about log10 ฮบ digits.
  • Subtracting nearly equal numbers and finding roots near multiple roots are ill-conditioned problems.
  • An algorithm is stable if it adds no more error than the conditioning forces; unstable algorithms can fail on easy problems.
  • Backward recurrences, stable rewrites and avoiding expanded polynomial coefficients are typical cures.
  • Diagnose by perturbing inputs and by comparing alternative algorithms or precisions.

Next: The Bisection Method