Condition Numbers

Why Condition Numbers Matter¶

Before we discuss algorithms and their errors, we need to understand: some problems are inherently harder than others.

Consider computing $f(x) = \tan(x)$ near $x = \pi/2$ . Even with infinite precision arithmetic and a perfect algorithm, tiny uncertainties in $x$ cause huge changes in $\tan(x)$ . This isn’t a flaw in our algorithm—it’s the nature of the tangent function near its pole.

The condition number quantifies this sensitivity. It answers: if my input is slightly wrong, how wrong might my output be?

Absolute and Relative Error¶

Before measuring problem sensitivity, we need precise definitions of error.

Why Relative Error Matters¶

Example 1 (Same Absolute Error, Different Quality)

	$x = 1$ , $x^* = 2$	$x = 10^6$ , $x^* = 10^6 + 1$
Absolute error	1	1
Relative error	$100\%$	$0.0001\%$
Quality	Terrible	Excellent

Both have the same absolute error, but the first is off by 100% while the second is nearly perfect. Relative error captures what matters.

Condition of $f$ at $x$ ¶

When we want to evaluate $f(x)$ , even if $x^*$ is close to $x$ , the value $f(x^*)$ may be far from $f(x)$ . The condition number quantifies this sensitivity.

Simplified Formula via Taylor’s Theorem¶

Proof 1

Since $x^*$ is close to $x$ , we can write $x^* = x + h$ and apply Taylor’s theorem:

f(x^*) = f(x + h) \approx f(x) + f'(x)(x - x^*)

(5)

This gives us:

f(x) - f(x^*) \approx f'(x)(x - x^*)

(6)

Substituting into the condition number definition:

\kappa = \sup_x \left| \frac{x f'(x)}{f(x)} \right|

(7)

Examples¶

Example 2 (Square Root (Well-Conditioned))

Consider $f(x) = \sqrt{x}$ with $f'(x) = \frac{1}{2\sqrt{x}}$ .

Near $\bar{x} = 1$ , we have $\bar{y} = f(\bar{x}) = 1$ . Using a Taylor approximation:

y - \bar{y} = \sqrt{x} - 1 \approx \frac{1}{2}(x - 1) = \frac{1}{2}(x - \bar{x})

(8)

Variations in $y$ are always smaller than variations in $x$ . Computing the condition number:

\kappa = \left| \frac{x f'(x)}{f(x)} \right| = \left| \frac{x \cdot \frac{1}{2\sqrt{x}}}{\sqrt{x}} \right| = \frac{1}{2}

(9)

Result: $\kappa = 1/2$ — evaluating $\sqrt{x}$ is well-conditioned.

Example 3 (Tangent Near π/2 (Ill-Conditioned))

Consider $f(x) = \tan(x)$ near $x = \frac{\pi}{2}$ .

Take two points:

x_1 = \frac{\pi}{2} - 0.001, \quad x_2 = \frac{\pi}{2} - 0.002

(10)

Then $|x_1 - x_2| = 0.001$ , but $|f(x_1) - f(x_2)| \approx 500$ . A tiny input change causes a huge output change!

Computing the condition number:

\kappa = \left| \frac{x f'(x)}{f(x)} \right| = \left| \frac{x}{\cos(x)\sin(x)} \right| = |2x \csc(2x)| \to \infty \text{ as } x \to \pi/2

(11)

Result: $\kappa \to \infty$ — evaluating $\tan(x)$ near $\frac{\pi}{2}$ is ill-conditioned.

Example 4 (Logarithm Near 1 (Ill-Conditioned))

Consider $f(x) = \ln(x)$ near $x = 1$ .

\kappa = \left| \frac{x f'(x)}{f(x)} \right| = \left| \frac{x \cdot (1/x)}{\ln(x)} \right| = \frac{1}{|\ln(x)|}

(12)

As $x \to 1$ , we have $\ln(x) \to 0$ , so $\kappa \to \infty$ .

Result: $\kappa \to \infty$ — evaluating $\ln(x)$ near $x = 1$ is ill-conditioned.

Summary¶

Problem	Condition Number	Well/Ill-Conditioned
$f(x) = \sqrt{x}$	$\kappa = 1/2$	Well-conditioned
$f(x) = x^2$	$\kappa = 2$	Well-conditioned
$f(x) = \tan(x)$ near $\pi/2$	$\kappa \to \infty$	Ill-conditioned
$f(x) = \ln(x)$ near 1	$\kappa \to \infty$	Ill-conditioned

The condition number is a property of the mathematical problem—it tells us the best possible accuracy any algorithm could achieve. But even well-conditioned problems can give bad results if we use a bad algorithm. That’s the subject of the next section.