Computational Methods: Finding single operation in algorithm that causes larger error

Question

I have been struggling with Computational Methods and am having a hard time finding good examples/resources online to follow through with.

So Previously, we used MATLAB to calculate the errors of a given algorithm. We obtained errors much larger than machine epsilon. Now we want to find which single operation in the algorithm caused the large error.

First Example:

$y= 3 - \sqrt{9-x^2}$ for $x = \frac{1}{3} * 10^{-5}$

I broke it up into:

$y_1 = x^2$

$y_2 = 9 - y_1$

$y_3 = \sqrt{y_2}$

$y_4 = 3 - y_3$

I then am using: $ c_f = \frac{f^1(x)x}{f(x)}$ to determine the condition number

Respectively, I got:

$c_{f1} = \frac{x(2x)}{x^2} = 2$

$c_{f2} = \frac{y_{1}(-1)}{9-y_1} = 1.234 * 10^{-12} $

$c_{f3} = \frac{y_2}{2y_2} = \frac{1}{2}$

$c_{f4} = ~ 0 $

Would I then conclude that the $x^2$ operation causes the largest error in the algorithm?

Could someone please explain if this is correct or point me in the right direction? Thank You

Answer 1

When subtracting numbers that differ only by few decimal places results in a catastrophic cancellation, this is a loss of significance. Ways to avoid this are covered in numerical stability, like using algebraic properties, taylor polynomial approximation, polynomial simplification etc

By the way I made some calculations with Mathematica to test the conditioning of your function:

$c_{f_1} = 2$

$c_{f_2} = -\frac{2}{9-x^2} = -2.469135802\cdot 10^{-12}$

$c_{f_3} = -\frac{x^2}{9-x^2} = -1.23456790\cdot 10^{-12}$

$c_{f_4} = \frac{x^2}{\sqrt{9-x^2}(3-\sqrt{9-x^2})} = 1.99999983$

---

EDIT: As you asked me to clarify where I got the conditioning results, then this is where they came from:

$c_{f_1} = \frac{x\cdot y_1'}{y_1} = \frac{x\cdot 2x}{x^2} = 2$

$c_{f_2} = \frac{x\cdot y_2'}{y_2} = \frac{x\cdot -2x}{9-x^2} = -\frac{2x^2}{9-x^2}$

$c_{f_3} = \frac{x\cdot y_3'}{y_3} = \frac{x\cdot -\frac{x}{\sqrt{9-x^2}}}{\sqrt{9-x^2}} = -\frac{x^2}{9-x^2}$

and $c_{f_4} = \frac{x\cdot f(x)'}{f(x)}$

where $x=\frac{1}{3}\cdot10^{-5}$

Then the instability appears in $c_{f_2}$ with the subtraction of $9-x^2$. Hope it helps.

Answer 2

By using floating point arithmetics, you represent every value by $1.abc(...)\cdot 2^{qwer}$ (I use letters as placeholders for single bits here)

If you subtract similar numbers (like $1.abcdef \cdot 2^q$ and $1.abcdeg\cdot 2^q$) you loose a lot of precision. You can assume, that both inputs have a relative error of $2^{-6}$ which is the best you can get with that mantissa. But if you subtract these numbers, you get to a result of $0.(f-g)\cdot ^{q-5}$ This has a relative error of $2^{-1}$, which is horrifying large. Try to avoid subtracting numbers of similar size!

In your example I think, there is not that much of a problem but let me give you a suggestion, since you already work with MatLab. There ist IntLab from my professor, that automatically calculates upper and lower bounds for the result of every single arithmetic expression. The cost is really high, but you could use some of the Papers metioned on that page.