Conditioning of a Problem

Inputs are never exact: they are measured, or rounded to doubles. So we must ask how much a small change in the input can change the answer. That is a property of the problem, before any method enters. The tool is the Linear Approximation and Differentials, and the bad case is the one you met in Round-Off and Cancellation.

For a function $f$ of one variable, the condition number at $x$ is $$\kappa(x) = \left|\frac{xf'(x)}{f(x)}\right|.$$ A problem is well-conditioned when $\kappa$ is modest and ill-conditioned when $\kappa$ is large.

Idea clave

A relative change $\delta$ in the input changes the output by a relative amount of about $\kappa\delta$. With input errors near $10^{-16}$, an answer can only be trusted to about $16 - \log_{10}\kappa$ digits, whatever method computes it.

Por qué funciona

Change $x$ by a relative amount $\delta$, to $x(1 + \delta)$. By linear approximation, $f(x + x\delta) \approx f(x) + f'(x)x\delta$. So the relative change in the output is $$\frac{f(x + x\delta) - f(x)}{f(x)} \approx \frac{xf'(x)}{f(x)}\delta.$$ The factor in front of $\delta$ is the condition number (up to sign). It compares relative changes, so it does not depend on units or on the size of $x$.

Ejemplo resuelto: A well-conditioned problem

Find $\kappa$ for $f(x) = \sqrt{x}$.

$f'(x) = \frac{1}{2\sqrt{x}}$, so $\frac{xf'(x)}{f(x)} = \frac{x}{2\sqrt{x}\sqrt{x}} = \frac{1}{2}$.
$\kappa = \frac{1}{2}$ everywhere: a square root halves relative errors.

Respuesta: $\kappa = \frac{1}{2}$

Ejemplo resuelto: Subtraction is ill-conditioned

Find $\kappa$ for $f(x) = x - 1$ at $x = 1.001$, and the effect of an input error of $10^{-16}$.

$f'(x) = 1$, so $\kappa = \left|\frac{x}{x - 1}\right| = \frac{1.001}{0.001} = 1001$.
A relative input error of $10^{-16}$ becomes about $1001 \times 10^{-16} \approx 10^{-13}$ in the output: about 3 digits lost.
This is cancellation seen as a property of the problem: no formula for $x - 1$ can avoid it once $x$ itself is uncertain.

Respuesta: $\kappa \approx 1001$

Ejemplo resuelto: A logarithm near 1

Find $\kappa$ for $f(x) = \ln x$ at $x = 1.01$.

$f'(x) = \frac{1}{x}$, so $\kappa = \left|\frac{x \cdot \frac{1}{x}}{\ln x}\right| = \frac{1}{|\ln x|}$.
At $x = 1.01$: $\ln 1.01 \approx 0.00995$, so $\kappa \approx 100.5$.

Respuesta: $\kappa \approx 100$

The condition number 1/|ln x| of the logarithm. It blows up near x = 1, where ln x is near 0.

Condition numbers of common functions.
$f(x)$	$\kappa(x)$	ill-conditioned where
$x^{n}$	$\|n\|$	never
$e^{x}$	$\|x\|$	$\|x\|$ large
$\ln x$	$\frac{1}{\|\ln x\|}$	$x$ near 1
$x - a$	$\left\|\frac{x}{x - a}\right\|$	$x$ near $a$
$\sin x$	$\|x\cot x\|$	$x$ near $k\pi$, $k \ne 0$

The same idea works for any problem: compare the relative change in the answer with the relative change in the data that caused it. For a linear system $A\mathbf{x} = \mathbf{b}$ that ratio is bounded by the condition number of the matrix, which plays exactly this role later in the course.

Error común

Blaming the method when the problem itself is ill-conditioned. If $\kappa = 10^{10}$ and the input is known to 16 digits, only about 6 digits of the answer are meaningful, however carefully you compute. Check: compute $\kappa$ before hunting for a better algorithm.

Práctica

Se apoya en

Lleva a

Fuentes y lecturas