Section 2.3 Error and conditioning
Every problem in numerical analysis can be described as follows: there is a map \(F\) depending on some parameters \((x_1,x_2,\dots,x_n)\) (that we call the input) and we want to evaluate numerically \(F\) at a given input. The solution of the problem is an algorithm that will return some other number of parameters \((y_1,y_2,\dots,y_m)\) (that we call the output). To keep things simple, we assume in this section that \(F\) takes in input a single value \(x\) and returns in output a single value \(y\text{.}\) The fundamental observation that motivates the concept of conditioning is that the input data of a problem are often known only approximatively. Moreover, even when they are known exactly, in general their values cannot be represented exactly in a binary floating point system, such as single or double precision. It is therefore very important to ascertain how sensitive is the problem with respect to small perturbations of the input data, namely: if \(x\) changes by a small amount \(\delta x\text{,}\) how much does change the value of \(F\text{?}\) Problems where the output of \(F\) changes a lot for a small change \(\delta x\) of \(x\) are called ill-conditioned. We use the following dictionary:| \(|\delta x|\) | input absolute error |
|---|---|
| \(|\delta x|/|x|\) | input relative error |
| \(|F(x)-F(x+\delta x)|\) | output absolute error |
| \(|F(x)-F(x+\delta x)|/|F(x)|\) | output relative error |
\begin{equation*}
\frac{|F(x)-F(x+\delta x)|}{|\delta x|}
\end{equation*}
for \(\delta x\to 0\text{,}\) while its relative condition number is the limit value of the ratio
\begin{equation*}
\frac{|F(x)-F(x+\delta x)|/|F(x)|}{|\delta x|/|x|}
\end{equation*}
for \(\delta x\to 0\text{.}\) Roughly speaking, if a problem has condition number of the order of \(10^k\) then, on top of all errors coming from the floating point arithmetic, it is to be expected the loss of about \(k\) decimal digits of accuracy. Below we examine the conditioning of the two case studies of this section.
Case study 1: Evaluating the value of a function. Consider the problem discussed in Section 2.1, namely we want to evaluate a smooth function \(f\) at a point \(x_0\text{.}\) In concrete, due to input errors, we will end up evaluating \(f+\varepsilon\delta f\) at a point \(x_0+\delta x\text{.}\) By Taylor's Theorem truncated at the second order,
\begin{equation*}
f(x_0+\delta x) + \varepsilon\delta f(x_0+\delta x) = f(x_0) + \varepsilon\delta f(x_0) + f'(x_0)\delta x + \text{terms of order 2 in }\delta x,\varepsilon
\end{equation*}
so that the absolute conditioning number \(K_a(x,f)\) is given by
\begin{equation*}
K_a(x_0,f) = |f'(x_0)|,
\end{equation*}
while the relative conditioning number \(K_r(x,f)\) is given by
\begin{equation*}
K_r(x_0,f) = \frac{|x_0 f'(x_0)|}{|f(x_0)|}.
\end{equation*}
Well-conditioned problems are characterized by having either "small enough" absolute conditioning number or a relative conditioning number (enough) smaller than 1. For instance, the expression of \(K_r(x,f)\) shows that roots \(r\) of \(f\) such that \(r\neq0\) and \(f'(r)\neq0\) are ill-conditioned. The reason is that arbitrarily small changes of \(r\) would make \(f\) pass from zero to non-zero, and every number is "infinitely larger" than zero. The fact that \(K_a(x_0,f) = |f'(x_0)|\) is obvious by looking at the Taylor series \(f(x_0+h)\simeq f(x_0)+f'(x_0)h\text{:}\) a small change in \(x_0\) produces a change in \(f\) that is amplified by a factor \(|f'(x_0)|\text{.}\) The assumption that the change in \(x_0\) is "small" is essential to make sure that the contribution of the second-order error term is small enough not to interfere with the first order term.
Example 2.3.2.
\begin{equation*}
K_f(x) = \left|\frac{x\cdot 1}{x-a}\right| = \left|\frac{x}{x-a}\right|.
\end{equation*}
The meaning of this is that subtracting two numbers close to each other causes a large loss in accuracy: by canceling several digits in common between the two numbers, fewer significant sigits are left (see Fact 1.2.3 in Section 1.2). This phenomenon is called catastrophic cancellation.
\begin{equation*}
K_g(x) = \left|\frac{x\cdot a}{ax}\right|=1.
\end{equation*}
In particular, multiplication is not subject to catastrophic cancellations.
\begin{equation*}
K_a(x_0,f) = |f''(x_0)|,
\end{equation*}
while the relative conditioning number \(K_r(x,f)\) is given by
\begin{equation*}
K_r(x_0,f) = \frac{|x_0 f''(x_0)|}{|f'(x_0)|}.
\end{equation*}
Summarizing, evaluating numerically a derivative at \(x_0\) is subject to a large loss of accuracy, independently on the algorithm used, when \(|f''(x_0)|\) is large compared to \(|f'(x_0)|\text{.}\)