Well-conditioned and ill-conditioned problems

3 Well-conditioned and ill-conditioned problems

Suppose we have a mathematical problem that depends on some input data. Now imagine altering the input data by a tiny amount. If the corresponding solution always varies by a correspondingly tiny amount then we say that the problem is well-conditioned . If a tiny change in the input results in a large change in the output we say that the problem is ill-conditioned . The following Example should help.

Example 4

Show that the evaluation of the function $f (x) = x^{2} - x - 1500$ near $x = 39$ is an ill-conditioned problem.

Solution

Consider $f (39) = - 18$ and $f (39.1) = - 10.29$ . In changing $x$ from 39 to 39.1 we have altered it by about 0.25%. But the percentage change in $f$ is greater than 40%. The demonstrates the ill-conditioned nature of the problem.

Task!

Work out the derivative $\frac{d f}{d x}$ for the function used in Example 4 and so explain why the numerical results show the calculation of $f$ to be ill-conditioned near $x = 39$ .

We have $f = x^{2} - x - 1500$ and $\frac{d f}{d x} = 2 x - 1$ . At $x = 39$ the value of $f$ is $- 18$ and, using calculus, the value of $\frac{d f}{d x}$ is $77$ . Thus $x = 39$ is very close to a zero of $f$ (i.e. a root of the quadratic equation $f (x) = 0$ ). The fractional change in $f$ is thus very large even for a small change in $x$ . The given values of $f (38.6)$ and $f (39.4)$ lead us to an estimate of

$\frac{12.96 - (- 48.64)}{39.4 - 38.6}$

for $\frac{d f}{d x}$ . This ratio gives the value $77.0$ , which agrees exactly with our result from the calculus. Note, however, that an exact result of this kind is not usually obtained; it is due to the simple quadratic form of $f$ for this example.

One reason that this matters is because of rounding error. Suppose that, in the Example above, we know is that $x$ is equal to 39 to 2 significant figures. Then we have no chance at all of evaluating $f$ with confidence, for consider these values

\begin{array}{rcl} f (38.6) & = & - 48.64 \\ f (39) & = & - 18 \\ f (39.4) & = & 12.96 . \end{array}

All of the arguments on the left-hand sides are equal to 39 to 2 significant figures so all the values on the right-hand sides are contenders for $f (x)$ . The ill-conditioned nature of the problem leaves us with some serious doubts concerning the value of $f$ .

It is enough for the time being to be aware that ill-conditioned problems exist. We will discuss this sort of thing again, and how to combat it in a particular case, in a later Section of this Workbook.

Exercises

Round each of these numbers to the number of places or figures indicated
1. $23.56712$ (to 2 decimal places).
2. $- 15432.1$ (to 3 significant figures).
Suppose we wish to calculate
$\sqrt{x + 1} - \sqrt{x},$

for relatively large values of $x$ . The following table gives values of $y$ for a range of $x$ -values

$\begin{matrix} x & \sqrt{x + 1} - \sqrt{x} \\ ̲ & ̲ \\ 100 & 0.04987562112089 \\ 1000 & 0.01580743742896 \\ 10000 & 0.00499987500625 \\ 100000 & 0.00158113487726 \end{matrix}$
1. For each $x$ shown in the table, and working to 6 significant figures evaluate $\sqrt{x + 1}$ and then $\sqrt{x}$ . Find $\sqrt{x + 1} - \sqrt{x}$ by taking the difference of your two rounded numbers. Are your answers accurate to 6 significant figures?
2. For each $x$ shown in the table, and working to 4 significant figures evaluate $\sqrt{x + 1}$ and then $\sqrt{x}$ . Find $\sqrt{x + 1} - \sqrt{x}$ by taking the difference of your two rounded numbers. Are your answers accurate to 4 significant figures?
The larger solution of the quadratic equation
$x^{2} + 168 x + 1 = 0$

is $- 84 + \sqrt{7055}$ which is equal to $- 0.0059525919$ to 10 decimal places. Round the value $\sqrt{7055}$ to 4 significant figures and then use this rounded value to calculate the larger solution of the quadratic equation. How many accurate significant figures does your answer have?
Consider the function
$f (x) = x^{2} + x - 1975$

and suppose we want to evaluate it for some $x$ .
1. Let $x = 20$ . Evaluate $f (x)$ and then evaluate $f$ again having altered $x$ by just 1%. What is the percentage change in $f$ ? Is the problem of evaluating $f (x)$ , for $x = 20$ , a well-conditioned one?
2. Let $x = 44$ . Evaluate $f (x)$ and then evaluate $f$ again having altered $x$ by just 1%. What is the percentage change in $f$ ? Is the problem of evaluating $f (x)$ , for $x = 44$ , a well-conditioned one?
(Answer: the problem in part (a) is well-conditioned, the problem in part (b) is ill-conditioned.)

$23.57, - 15400.$
The answers are tabulated below. The $2^{n d}$ and $3^{r d}$ columns give values for $\sqrt{x + 1}$ and $\sqrt{x}$ respectively, rounded to 10 decimal places. The $4^{t h}$ column shows the values of $\sqrt{x + 1} - \sqrt{x}$ also to 10 decimal places. Column (a) deals with part (a) of the question and finds the difference after rounding the numbers in the $2^{n d}$ and $3^{r d}$ columns to 6 significant figures. Column (b) deals with part (b) of the question and finds the difference after rounding the numbers in the $2^{n d}$ and $3^{r d}$ columns to 4 significant figures.
$\begin{matrix} x & \sqrt{x + 1} & \sqrt{x} & (a) & (b) \\ ̲ & ̲ & ̲ & ̲ & ̲ & ̲ \\ 100 & 10.0498756211 & 10.0000000000 & 0.0498756211 & 0.0499 & 0.0500 \\ 1000 & 31.6385840391 & 31.6227766017 & 0.0158074374 & 0.0158 & 0.0200 \\ 10000 & 100.0049998750 & 100.0000000000 & 0.0049998750 & 0.0050 & 0.0000 \\ 100000 & 316.2293471517 & 316.2277660168 & 0.0015811349 & 0.0010 & 0.0000 \end{matrix}$

Clearly the answers in columns (a) and (b) are not accurate to 6 and 4 figures respectively. Indeed the last two figures in column (b) are accurate to no figures at all!
$\sqrt{7055} = 83.99$ to 4 significant figures. Using this value to find the larger solution of the quadratic equation gives
$- 84 + 83.99 = - 0.01$ .

The number of accurate significant figures is 0 because the accurate answer is $0.006$ and $‘ 1^{'}$ is not the leading digit (it is $‘ 6^{'}$ ).
1. $f (20) = - 1555$ and $f (20.2) = - 1546.76$ so the percentage change in $f$ on changing $x = 20$ by $1 %$ is
  $\frac{- 1555 - (- 1546.76)}{- 1555} \times 100 % = 0.53 %$
  
  to 2 decimal places.
2. $f (44) = 5$ and $f (44.44) = 44.3536$ so the percentage change in $f$ on changing $x = 44$ by $1 %$ is
  $\frac{5 - 44.3536}{5} \times 100 % = - 787.07 %$
  
  to 2 decimal places.
Clearly then, the evaluation of $f (20)$ is well-conditioned and that of $f (44)$ is ill-conditioned.