--- numbering: enumerator: 1.4.%s --- (section-intro-stability)= # Stability ```{index} ! stability ``` If we solve a problem using a computer algorithm and see a large error in the result, we might suspect poor conditioning in the original mathematical problem. But algorithms can also be sources of errors. When error in the result of an algorithm exceeds what conditioning can explain, we call the algorithm **unstable**. ## Case study In {numref}`Example %s ` we showed that finding the roots of a quadratic polynomial $ax^2 + b x+c$ is poorly conditioned if and only if the roots are close to each other relative to their size. Hence, for the polynomial ```{math} :label: quadunstable p(x) = (x-10^6)(x-10^{-6}) = x^2 - (10^6+10^{-6})x + 1, ``` finding roots is a well-conditioned problem. An obvious algorithm for finding those roots is to directly apply the familiar quadratic formula, ```{math} :label: quadform x_1 = \frac{-b + \sqrt{b^2-4ac}}{2a}, \qquad x_2 = \frac{-b - \sqrt{b^2-4ac}}{2a}. ``` ``````{prf:example} Instability of the quadratic formula :label: demo-stability-quadbad `````{tab-set} ````{tab-item} Julia :sync: julia :::{embed} #demo-stability-quadbad-julia ::: ```` ````{tab-item} MATLAB :sync: matlab :::{embed} #demo-stability-quadbad-matlab ::: ```` ````{tab-item} Python :sync: python :::{embed} #demo-stability-quadbad-python ::: ```` ````` `````` ::::{aside} `````{tab-set} ````{tab-item} Julia :sync: julia :::{div} :width: 100% ```{iframe} https://cdnapisec.kaltura.com/p/2358381/embedPlaykitJs/uiconf_id/57659783?iframeembed=true&entry_id=1_4ug49ukm&config%5Bprovider%5D=%7B%22widgetId%22%3A%221_y3pcfiws%22%7D&config%5Bplayback%5D=%7B%22startTime%22%3A0%7D ``` ::: ```` ````{tab-item} MATLAB :sync: matlab ```` ````{tab-item} Python :sync: python ```` ````` :::: ```{index} subtractive cancellation ``` @demo-stability-quadbad suggests that the venerable quadratic formula is an *unstable* means of computing roots in finite precision. The roots themselves were not sensitive to the data or arithmetic—it's the specific computational path we chose that caused the huge growth in errors. We can confirm this conclusion by finding a different path that avoids subtractive cancellation. A little algebra using {eq}`quadform` confirms the additional formula $x_1x_2=c/a$. So given one root $r$, we compute the other root using $c/ar$, which has only multiplication and division and therefore creates no numerical trouble. ``````{prf:example} Stable alternative to the quadratic formula :label: demo-stability-quadgood `````{tab-set} ````{tab-item} Julia :sync: julia :::{embed} #demo-stability-quadgood-julia ::: ```` ````{tab-item} MATLAB :sync: matlab :::{embed} #demo-stability-quadgood-matlab ::: ```` ````{tab-item} Python :sync: python :::{embed} #demo-stability-quadgood-python ::: ```` ````` `````` ::::{aside} `````{tab-set} ````{tab-item} Julia :sync: julia :::{div} :width: 100% ```{iframe} https://cdnapisec.kaltura.com/p/2358381/embedPlaykitJs/uiconf_id/57659783?iframeembed=true&entry_id=1_bnng2ukz&config%5Bprovider%5D=%7B%22widgetId%22%3A%221_fgo2o818%22%7D&config%5Bplayback%5D=%7B%22startTime%22%3A0%7D ``` ::: ```` ````{tab-item} MATLAB :sync: matlab ```` ````{tab-item} Python :sync: python ```` ````` :::: The algorithms in @demo-stability-quadbad and @demo-stability-quadgood are equivalent when using real numbers and exact arithmetic. When results are perturbed by machine representation at each step, though, the effects may depend dramatically on the specific sequence of operations, thanks to the chain rule {eq}`condition-chain`. ::::{prf:observation} The sensitivity of a problem $f(x)$ is governed only by $\kappa_f$, but the sensitivity of an algorithm depends on the condition numbers of all of its individual steps. :::: This situation may seem hopelessly complicated. But the elementary operations we take for granted, such as those in {numref}`table-condition-functions`, are well-conditioned in most circumstances. Exceptions usually occur when $|f(x)|$ is much smaller than $|x|$, although not every such case signifies trouble. The most common culprit is simple subtractive cancellation. A practical characterization of instability is that results are much less accurate than the conditioning of the problem can explain. Typically, one should apply an algorithm to test problems whose answers are well-known, or for which other programs are known to work well, in order to spot possible instabilities. In the rest of this book we will see some specific ways in which instability is manifested for different types of problems. ## Backward error In the presence of poor conditioning for a problem $f(x)$, even just the act of rounding the data to floating point may introduce a large change in the result. It's not realistic, then, to expect any algorithm $\tilde{f}$ to have a small error in the sense $\tilde{f}(x)\approx f(x)$. There is another way to characterize the error, though, that can be a useful alternative measurement. Instead of asking, "Did you get nearly the right answer?", we ask, "Did you answer nearly the right question?" ```{index} ! backward error ``` :::{prf:definition} Backward error :label: definition-backward-error Let $\tilde{f}$ be an algorithm for the problem $f$. Let $y=f(x)$ be an exact result and $\tilde{y}=\tilde{f}(x)$ be its approximation by the algorithm. If there is a value $\tilde{x}$ such that $f(\tilde{x}) = \tilde{y}$, then the relative **backward error** in $\tilde{y}$ is ```{math} :label: backwarderror \frac{ |\tilde{x}-x| } { |x| }. ``` The absolute backward error is $|\tilde{x}-x|$. ::: Backward error measures the change to the original data that reproduces the result that was found by the algorithm. The situation is illustrated in {numref}`fig-backwarderror`. ```{figure} figures/backwarderror.svg :name: fig-backwarderror Backward error is the difference between the original data and the data that exactly produces the computed value. ``` ``````{prf:example} Backward error :label: demo-stability-roots `````{tab-set} ````{tab-item} Julia :sync: julia :::{embed} #demo-stability-roots-julia ::: ```` ````{tab-item} MATLAB :sync: matlab :::{embed} #demo-stability-roots-matlab ::: ```` ````{tab-item} Python :sync: python :::{embed} #demo-stability-roots-python ::: ```` ````` `````` ::::{aside} `````{tab-set} ````{tab-item} Julia :sync: julia :::{div} :width: 100% ```{iframe} https://cdnapisec.kaltura.com/p/2358381/embedPlaykitJs/uiconf_id/57659783?iframeembed=true&entry_id=1_y6dxnlam&config%5Bprovider%5D=%7B%22widgetId%22%3A%221_2xcm0icy%22%7D&config%5Bplayback%5D=%7B%22startTime%22%3A0%7D ``` ::: ```` ````{tab-item} MATLAB :sync: matlab ```` ````{tab-item} Python :sync: python ```` ````` :::: Small backward error is the best we can hope for in a poorly conditioned problem. Without getting into the formal details, know that if an algorithm always produces small backward errors, then it is stable. But the converse is not always true: some stable algorithms may produce a large backward error. ::::{prf:example} :label: example-stability-notbs One stable algorithm that is not backward stable is floating-point evaluation for our old friend, $f(x)=x+1$. If $|x|<\macheps/2$, then the computed result is $\tilde{f}(x)=1$, since there are no floating-point numbers between $1$ and $1+\macheps$. Hence, the only possible choice for a real number $\tilde{x}$ satisfying {eq}`backwarderror` is $\tilde{x}=0$. But then $|\tilde{x}-x|/|x|=1$, which indicates 100% backward error! :::: ## Exercises ``````{exercise} :label: problem-stability-trig The formulas ```{math} :numbered: false f(x)=\frac{1-\cos(x)}{\sin(x)}, \quad g(x) = \frac{2\sin^2(x/2)}{\sin(x)}, ``` are mathematically equivalent, but they suggest evaluation algorithms that can behave quite differently in floating point. **(a)** ✍ Using {eq}`conditionderiv`, find the relative condition number of $f$. (Because $f$ and $g$ are equivalent, the condition number of $g$ is the same.) Show that it approaches 1 as $x\to 0$. (Hence it should be possible to compute the function accurately near zero.) **(b)** ⌨ Compute $f(10^{-6})$ using a sequence of four elementary operations. Using {numref}`Table {number} `, make a table like the one in @demo-stability-quadbad that shows the result of each elementary result and the numerical value of the condition number of that step. **(c)** ⌨ Repeat part (b) for $g(10^{-6})$, which has six elementary steps. **(d)** ✍ Based on parts (b) and (c), is the numerical value of $f(10^{-6})$ more accurate, or is $g(10^{-6})$ more accurate? `````` ``````{exercise} :label: problem-stability-expm1 Let $f(x) = \frac{e^x-1}{x}$. **(a)** ✍ Find the condition number $\kappa_f(x)$. What is the maximum of $\kappa_f(x)$ over $-1\le x \le 1$? **(b)** ⌨ Use the "obvious" algorithm ``` julia (exp(x) - 1) / x ``` to compute $f(x)$ at $x=10^{-2},10^{-3},10^{-4},\ldots,10^{-11}$. **(c)** ⌨ Create a second algorithm from the first 8 terms of the Maclaurin series, i.e., ```{math} :numbered: false f(x) \approx p(x) = 1 + \frac{1}{2!}x + \frac{1}{3!}x^2 + \cdots + \frac{1}{8!}x^7. ``` Evaluate it at the same values of $x$ as in part (b). **(d)** ⌨ Make a table of the relative difference between the two algorithms as a function of $x$. Which algorithm is more accurate, and why? `````` ``````{exercise} :label: problem-stability-acosh ⌨ The function ```{math} :numbered: false x = \cosh(y) = \frac{e^y + e^{-y}}{2} ``` can be inverted to yield a formula for $\operatorname{acosh}(x)$: ```{math} :label: acosh y = \operatorname{acosh}(x) = -\log\bigl(x-\sqrt{x^2-1}\bigr). ``` For the steps below, define $y_i=4i$ and $x_i=\cosh(y_i)$ for $i=1,\dots,4$. Hence $y_i=\operatorname{acosh}(x_i)$. **(a)** Find the relative condition number of evaluating $f(x) = \operatorname{acosh}(x)$. (You can use {eq}`acosh` or look up a formula for $f'$ in a calculus book.) Evaluate $\kappa_f$ at all the $x_i$. (You will find that $\kappa$ is less than 20 at these inputs, so the conditioning is fine.) **(b)** Use {eq}`acosh` to approximate $f(x_i)$ for all $i$. Compute the relative accuracy of the results. Why are some of the results so inaccurate? **(c)** An alternative formula is ```{math} :label: acosh2 y = 2\log\left(\sqrt{\frac{x+1}{2}} + \sqrt{\frac{x-1}{2}}\right). ``` Apply {eq}`acosh2` to approximate $f(x_i)$ for all $i$, again computing the relative accuracy of the results. `````` ``````{exercise} :label: problem-stability-samplevar ⌨ (Continuation of @problem-algorithms-samplevar. Adapted from {cite}`highamAccuracyStability2002`.) One drawback of the formula {eq}`samplevar` for sample variance is that you must compute a sum for $\overline{x}$ before beginning another sum to find $s^2$, implying two loops taken over the data. Some statistics textbooks quote a formula that can be computed with a single loop: ```{math} :numbered: false \begin{split} s^2 &= \frac{1}{n-1} \left( u - \tfrac{1}{n}v^2 \right),\\ u & = \sum_{i=1}^n x_i^2, \\ v &= \sum_{i=1}^n x_i. \end{split} ``` Try this formula for these three sets as `x`, each having a variance exactly equal to 1: ```{math} :numbered: false \{ 10^6, 1 + 10^6, 2 + 10^6 \}, \quad \{ 10^7, 1 + 10^7, 2 + 10^7 \}, \quad \{ 10^8, 1 + 10^8, 2 + 10^8 \}. ``` Explain the results. (Remember to use scientific notation in code, such as `1e6` for $10^6$.) ``````