Back to the on-screen lesson ·
How far the exact answer moves when the data does: $\kappa = |xf'(x)/f(x)|$, why it belongs to the problem rather than to any method, and the reciprocal form that conditions a root.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to derive and compute the relative condition number of a problem, read it as a magnification factor for relative error, say why it is local and why no algorithm can change it, and condition a root as well as an evaluation.
You have seen relative error, and you have seen a subtraction of nearly equal numbers destroy a computation that looked fine. This lesson turns that observation into a number — one that can be worked out in advance, before any method is chosen and before anything is run.
The data is what goes into a problem and the answer is what comes out. A perturbation is a small change in the data, usually the one that storing it caused. The relative condition number of $f$ at $x$ is the factor by which the problem magnifies a relative perturbation, and a problem is called well conditioned when that factor is modest and ill conditioned when it is large. How large is too large is answered by the precision available, which is a later lesson.
Perturb the data and ask how far the exact answer moves. Write the perturbed input as $x(1 + \delta)$; a first-order expansion gives $f(x + x\delta) \approx f(x) + x\delta f'(x)$, so the relative change in the answer is about $\dfrac{xf'(x)}{f(x)}\delta$. The factor in front is the relative condition number $\kappa = \left|\dfrac{xf'(x)}{f(x)}\right|$. Three things follow, and all three matter. First, $\kappa$ is built from $f$ and $x$ and nothing else, so it is a property of the problem: two algorithms for the same problem face the same $\kappa$, and choosing a better one cannot reduce it. Second, it is local — the same function can be beautifully conditioned at one point and hopeless at another, and $f(x) = x - a$ near $x = a$ is the standard example, with $\kappa = |x/(x - a)|$ unbounded as the gap closes. Third, it bounds what is achievable: data carrying relative error $\eta$ cannot produce an answer with relative error much below $\kappa\eta$, however the answer is computed. The same idea runs backwards for an inverse problem. For a root $r$ of $f$ the data is the function and the answer is the crossing point, and the condition number comes out as $1/|f'(r)|$ — the derivative in the denominator, so a flat crossing is the bad case rather than the good one.
Another way: steps
Another way: picture
Draw the graph of $f$ and a short interval of width $2x\delta$ around $x$ on the horizontal axis. Its image on the vertical axis is an interval of width about $2x\delta|f'(x)|$. The condition number is how much wider that second interval is as a share of its own height than the first was as a share of its own — a steep graph over a small value of $f$ stretches it enormously, and a flat graph over a large value squashes it.
An ill-conditioned problem is routinely reported as a bug in the code, and weeks go into rewriting a method that was never at fault. Conditioning belongs to the problem and stability to the algorithm. A stable method on an ill-conditioned problem returns a wrong answer and is not at fault; a good answer from an unstable method on a well-conditioned problem is luck. Only the two together say anything about the digits. The test that separates them costs nothing: perturb the data in the last digit, recompute, and see how far the answer moves. If it moves a long way, the problem is sensitive and a different formulation — not a different algorithm — is the only cure.
$f(x) = x^{4}$: $\kappa = |x \cdot 4x^{3}/x^{4}| = 4$, everywhere.
The exponent, and no dependence on the point.
$f(x) = x - 100$ at $x = 101$: $\kappa = |101/1| = 101$.
Two digits already gone.
The same $f$ at $x = 100.01$: $\kappa = 10001$.
Four digits gone, from moving the point closer.
$f(x) = x^{2} - 2$ has $f'(\sqrt2) \approx 2.83$, so the root's condition number is about $0.35$.
A steep crossing.
$f(x) = (x - 1)^{2} - 10^{-8}$ has roots either side of $1$ with $|f'| = 2 \times 10^{-4}$, so the condition number is $5000$.
A nearly flat crossing.
$f'(x) = -1/x^{2}$, so $xf'(x) = -1/x$.
Divide by $f(x) = 1/x$: the quotient is $-1$.
So $\kappa = 1$ at every non-zero point: taking a reciprocal is perfectly conditioned, and the enormous change in size it can cause is not the same thing as a change in relative error.
What is the relative condition number of $f(x) = x^{2}$ at any non-zero $x$?
Answer:
For $f(x) = x - 34$ the relative condition number at $x$ is $\left|\dfrac{x}{x - 34}\right|$. Give it at the three points named, as a fraction where it is not a whole number.
| The point | Condition number | |
|---|---|---|
| Four away from the zero | 38 | |
| Two away from the zero | 36 | |
| One away from the zero | 35 |
Match each function to its relative condition number at a point $x$ where it is defined and non-zero.
| $3$, at every non-zero point | $\tfrac12$, at every positive point | $|x|$, so bad far from the origin | $1/|\ln x|$, so bad near $x = 1$ | |
|---|---|---|---|---|
| $f(x) = x^{3}$ | ||||
| $f(x) = \sqrt{x}$ | ||||
| $f(x) = e^{x}$ | ||||
| $f(x) = \ln x$ |
Put the five steps of deriving the relative condition number into the order they depend on each other.
Number the steps in order (write the number in the box):
A function $f$ has a simple root at $r$ with $f'(r) = \dfrac{1}{7}$. The function itself is known only to within $\varepsilon$. About how many times $\varepsilon$ can the root move?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Select every statement a relative condition number supports.
This task has no paper form; do it on a device.
You can compute a condition number, say what it bounds and what it does not, and condition a root. Say in your own words why a better algorithm cannot rescue an ill-conditioned problem.
8. Your turn: the condition number of $f(x) = 1/x$, step 3