Foundations of numerical computing · Lecture 5

Conditioning and Stability

Some problems magnify every tiny error, and no algorithm can save them. Some algorithms ruin perfectly good problems. Telling the two apart is the most important diagnostic skill in numerical computing.

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Today's goals

Define conditioning (a property of the problem) and stability (a property of the algorithm)
Compute the condition number of a function and of a matrix
Predict how many digits are lost: about $\log_{10}\kappa$
Recognise unstable algorithms and replace them with stable ones
Explain forward and backward error

Last time

Errors propagate through arithmetic; cancellation can destroy relative accuracy.

Today

Two questions behind every inaccurate answer: Is the problem sensitive? Is my method careless?

Foundations of numerical computing · you are here

L1 · Why Numerical Methods?→L2 · Floating-Point Numbers→L3 · Taylor Series and Order of Accuracy→L4 · Errors and Their Propagation→L5 · Conditioning and Stability

Builds on: L3, L4

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

2 / 17

Start here

The idea in one picture

Solving two equations = finding where two lines cross.Change one line a tiny bit (a small data error).Lines at a wide angle: the answer hardly changes.Nearly parallel lines: the same tiny change moves the answer a long way.

In plain words

Some problems are touchy: a tiny change in the data changes the answer a lot
That is a property of the problem, not of the program
A good method (stable) adds no extra trouble of its own

New words today

well-conditioned: small data change → small answer change
ill-conditioned: small data change → large answer change
condition number κ: how much errors are magnified
stable algorithm: one that keeps its own rounding errors small

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

3 / 17

Problem vs algorithm

Conditioning (the problem)

How much does the exact answer change when the input changes a little?
Measured by the condition number $\kappa$
Well-conditioned: $\kappa$ small (≈ 1–100)
Ill-conditioned: $\kappa$ huge; data errors are amplified
No algorithm can fix it; only better data, more precision or a reformulated problem

≠

Stability (the algorithm)

Does the algorithm keep its own rounding errors small?
Stable: the answer is as good as the conditioning allows
Unstable: errors grow inside the algorithm (e.g. by $n!$ or by $10^{8}$ )
Fixable: choose a different algorithm for the same problem
Examples: pivoting, rewriting formulas, backward recurrence

Accurate result ⇐ well-conditioned problem + stable algorithm. You need both.

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

4 / 17

Condition number of evaluating $f(x)$

Relative change out ÷ relative change in

\kappa_f(x) = \left|\frac{\Delta f / f}{\Delta x / x}\right| \approx \left|\frac{x\,f'(x)}{f(x)}\right|

Derivation: $\Delta f \approx f'(x)\,\Delta x$ , so $\dfrac{\Delta f}{f} \approx \dfrac{x f'(x)}{f(x)}\cdot\dfrac{\Delta x}{x}$
A relative input error $\delta$ becomes about $\kappa\,\delta$ in the output
Since every stored input has $\delta \approx 10^{-16}$ , expect to lose about $\log_{10}\kappa$ digits

$f(x)$	$\kappa_f(x)$	verdict
$\sqrt{x}$	$\tfrac12$	always well
$e^{x}$	$\|x\|$	well unless $x$ huge
$x - 1$ at $x = 1.001$	$\left\|\tfrac{x}{x-1}\right\| = 1001$	ill (cancellation)
$\tan x$ at $x = 1.57$	≈ 1972	ill (near $\pi/2$ )
$\ln x$ near $x = 1$	$\left\|\tfrac{1}{\ln x}\right\|$ → ∞	ill

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

5 / 17

Explore: nearly parallel lines

Two lines cross at the solution of a 2×2 system
When the lines are nearly parallel, a tiny shift moves the crossing a long way
Move the slider: $b_2$ changes in the 5th decimal
Switch to the well-conditioned system: the crossing barely moves

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

6 / 17

Problem 1: an ill-conditioned system

Problem 1Solve

x + y = 2

,

\;x + 1.0001y = 2.0001

. Then change the second right-hand side to

2.0002

.

1

Subtract the equations:

0.0001\,y = 0.0001 \Rightarrow y = 1,\; x = 1

2

With

2.0002

:

0.0001\,y = 0.0002 \Rightarrow y = 2,\; x = 0

3

Input changed by

0.0001/2.0001 = 0.005\%

; output changed by

100\%

: amplification about

20{,}000

4

A^{-1} = \dfrac{1}{0.0001}\begin{pmatrix}1.0001 & -1\\ -1 & 1\end{pmatrix}

,

\;\|A\|_\infty = 2.0001

,

\;\|A^{-1}\|_\infty = 20001

,

\;\kappa_\infty(A) \approx 40{,}004

\kappa \approx 4\times10^{4}

: expect to lose about 4–5 significant digits, whatever method we use.

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

7 / 17

Condition number of a matrix

Definition

\kappa(A) = \|A\|\,\|A^{-1}\| \;\ge 1

What it guarantees

\frac{\|\Delta \mathbf{x}\|}{\|\mathbf{x}\|} \le \kappa(A)\,\frac{\|\Delta \mathbf{b}\|}{\|\mathbf{b}\|}

$\|A\|_\infty$ = largest absolute row sum (easy by hand)
$\kappa = 1$ : perfect (e.g. identity, rotations)
Rule of thumb: digits lost ≈ $\log_{10}\kappa(A)$
Singular matrix: $\kappa = \infty$ . A small determinant alone does not mean ill-conditioned: $10^{-10}I$ has $\kappa = 1$
Full treatment of norms: Lecture 11

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

8 / 17

The famous Hilbert matrix

$H_{ij} = \dfrac{1}{i + j - 1}$ ; we solve $H\mathbf{x} = \mathbf{b}$ where the true $\mathbf{x}$ is all ones
The algorithm (Gaussian elimination with pivoting, Lecture 12) is stable
Yet the error grows from $10^{-14}$ to $10^{-3}$ as $n$ goes 3 → 12
Because $\kappa(H_{12}) \approx 10^{16}$ : all 16 digits are lost

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

9 / 17

An unstable algorithm for a well-conditioned problem

$I_n = \int_0^1 x^n e^{x-1}\,dx$ ; integration by parts gives $I_n = 1 - n\,I_{n-1}$
Start from $I_0 = 1 - e^{-1}$ (rounded) and go forward: the error is multiplied by $n$ each step
By $n = 20$ it is multiplied by $20! \approx 2.4\times10^{18}$ : $I_{20} = -30.19$ , impossible
Run the same formula backwards from a rough guess: errors are divided by $n$ : stable

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

10 / 17

Unstable algorithms and their stable replacements

Gaussian elimination without pivoting

A tiny pivot like 0.001 creates huge multipliers (Lecture 12). Fix: partial pivoting.

$(1-\cos x)/x^2$ for small $x$

Cancellation inside the algorithm. Fix: $2\sin^2(x/2)/x^2$ .

One-pass variance $\overline{x^2} - \bar{x}^2$

Cancellation for large means. Fix: subtract the mean first (two passes).

Forward recurrence $I_n = 1 - nI_{n-1}$

Error × $n$ per step. Fix: run it backwards.

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

11 / 17

Forward error and backward error

Forward error: how wrong is the answer?

|\tilde{x} - x|

Backward error: for which nearby problem is the answer exact?

\min\{\,|\Delta| : \tilde{x} \text{ solves the problem with data } d + \Delta\,\}

Link

\text{forward error} \;\lesssim\; \kappa \times \text{backward error}

Example: root of $x^2 - 2 = 0$ computed as $\tilde{x} = 1.4142$
Forward error: $|1.4142 - \sqrt2| = 1.36\times10^{-5}$
Backward: $1.4142^2 = 1.99996164$ , so $\tilde{x}$ is the exact root of $x^2 - 1.99996164 = 0$ : data changed by $3.8\times10^{-5}$
A backward stable algorithm always gives the exact answer to a slightly perturbed problem

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

12 / 17

Diagnosing an inaccurate answer

well-conditioned + stable

Accurate ✓

$\sqrt{x}$ , Gaussian elimination with pivoting on a good matrix, $2\sin^2(x/2)$ .

well-conditioned + unstable

Inaccurate, but fixable

Change the algorithm: pivot, rewrite, reverse the recurrence.

ill-conditioned + stable

Inaccurate, algorithm is innocent

Change the problem: better data, more precision, rescale, regularise. Hilbert matrix, nearly parallel lines.

ill-conditioned + unstable

Hopeless

Fix the algorithm first, then deal with the conditioning.

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

13 / 17

Practice

Practice problem

Problem 2"Distinguish between an ill-conditioned problem and an unstable algorithm. A well-conditioned problem can still yield an inaccurate computed result. Using one example each, illustrate (i) a well-conditioned problem ruined by an unstable algorithm, and (ii) an ill-conditioned problem for which no algorithm, however stable, can guarantee an accurate result."

How to write a complete answer

Definitions: conditioning = sensitivity of the exact solution to input changes ( $\kappa$ ); stability = whether the algorithm keeps its own rounding errors from growing
(i) $I_n = 1 - nI_{n-1}$ forward: well-conditioned integral, error × $n!$ ⇒ $I_{20} = -30$ ; or GE without pivoting on $0.001x + y = 1, x + y = 2$
(ii) $x + y = 2$ , $x + 1.0001y = 2.0001$ : changing 2.0001 → 2.0002 moves $(1,1)$ to $(0,2)$ ; $\kappa \approx 4\times10^4$ , true for any algorithm
Close with: accuracy needs both, forward error ≲ κ × backward error

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

14 / 17

Beyond the classroom

Where this shows up in CSE and machine learning

📐

Feature scaling

Features in metres and in millimetres make the normal-equations matrix ill-conditioned. Standardising features (mean 0, std 1) reduces $\kappa$ and speeds up training.

🛡️

Ridge regularisation

Solving $(X^TX + \lambda I)\mathbf{w} = X^T\mathbf{y}$ instead of $X^TX\mathbf{w} = X^T\mathbf{y}$ caps the condition number: a cure for ill-conditioning (Lecture 23).

⛰️

Ill-conditioned loss surfaces

When the Hessian's eigenvalues differ a lot (ratio = $\kappa$ ), gradient descent zig-zags: exactly the situation studied in Lecture 25.

🔢

Adam's epsilon

Optimisers divide by $\sqrt{v} + \epsilon$ with $\epsilon = 10^{-8}$ so that a tiny denominator cannot amplify noise: a stability safeguard.

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

15 / 17

Checkpoint

Checkpoint · think, then discuss with your neighbourA linear system has

\kappa(A) = 10^{10}

and is solved in double precision with a stable algorithm. About how many correct significant digits can we expect?

A16

B10

C6

D0

C. Double gives about 16 digits;

\log_{10}\kappa = 10

digits are lost: about

16 - 10 = 6

remain.

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

16 / 17

Summary

Key points

Conditioning belongs to the problem; stability to the algorithm
$\kappa_f = |xf'(x)/f(x)|$ ; $\kappa(A) = \|A\|\|A^{-1}\|$ ; digits lost ≈ $\log_{10}\kappa$
Ill-conditioned: change the data or the problem. Unstable: change the algorithm
Forward error ≲ κ × backward error; a backward-stable algorithm solves a nearby problem exactly

Homework

Find $\kappa_f(x)$ for $f(x) = x^{10}$ and for $f(x) = \ln x$ . Where is each ill-conditioned?
For $A = \begin{pmatrix} 1 & 2 \\ 2 & 4.001\end{pmatrix}$ compute $\kappa_\infty(A)$ . How many digits would you lose?
Run the recurrence widget to $n = 25$ . At which $n$ does the forward value first leave $[0, 1]$ ?
Write a model answer to Problem 2 in your own words (half a page).

Next lecture

Root finding and the bisection method. The safest way to solve $f(x) = 0$ : trap the root in an interval and halve it, with a guaranteed error bound.

Md Mahbub E Noor

Lecture 5: Conditioning and Stability

University of Barishal

17 / 17

Conditioning and Stability

Today's goals

The idea in one picture

Problem vs algorithm

Conditioning (the problem)

Stability (the algorithm)

Condition number of evaluating f(x)f(x)f(x)

Explore: nearly parallel lines

Problem 1: an ill-conditioned system

Condition number of a matrix

The famous Hilbert matrix

An unstable algorithm for a well-conditioned problem

Unstable algorithms and their stable replacements

Gaussian elimination without pivoting

(1−cos⁡x)/x2(1-\cos x)/x^2(1−cosx)/x2 for small xxx

One-pass variance x2‾−xˉ2\overline{x^2} - \bar{x}^2x2−xˉ2

Forward recurrence In=1−nIn−1I_n = 1 - nI_{n-1}In​=1−nIn−1​

Forward error and backward error

Diagnosing an inaccurate answer

Accurate ✓

Inaccurate, but fixable

Inaccurate, algorithm is innocent

Hopeless

Practice problem

Where this shows up in CSE and machine learning

Feature scaling

Ridge regularisation

Ill-conditioned loss surfaces

Adam's epsilon

Checkpoint

Summary

Condition number of evaluating $f(x)$

$(1-\cos x)/x^2$ for small $x$

One-pass variance $\overline{x^2} - \bar{x}^2$

Forward recurrence $I_n = 1 - nI_{n-1}$