1
$\begingroup$

For the floating point system $(B, t, L, U) = (10,8,-50,50)$ and for the quadratic equation:

$ax^2 + bx + c$, I need to show error that arises in various cases and how to fix those.

$$a=10^{-30}$$ $$b= -10^{30}$$ $$c=10^{30}$$

I think there is cancellation error when plugging into quadratic formula. Can anyone help me verify that if multiply quadratic formula by conjugate, then I'll get $\frac{2c}{-b \pm \sqrt{b^2-4ac}}$ which will take away the error for the case that is subject to error?

Thanks!

2 Answers 2

2

The basic idea is that if |$4ac| \ll b^2$, the square root is very close to $|b|$. Depending on the sign of $b$, one combination or the other will involve subtracting two nearly equal quantities.

To be specific, let us assume $b \gt 0$. Then one root is $\frac {-b+\sqrt{b^2-4ac}}{2a}$ and is the one subject to cancellation. If we multiply by the congugate:$$\frac {-b+\sqrt{b^2-4ac}}{2a}\frac {b+\sqrt{b^2-4ac}}{b+\sqrt{b^2-4ac}}=\frac{b^2-4ac-b^2}{2ab+2a\sqrt{b^2-4ac}}=\frac{-2c}{b+\sqrt{b^2-4ac}}$$ and the cancellation has disappeared. The case $b \lt 0$ is similar except you worry about the one with the minus sign.

  • 0
    Sweet! Thank you for verifying!2012-08-26
  • 0
    When you multiply by conjugate shouldnt it be -b?2012-08-26
  • 0
    Also, I feel like there will still be error in how big the exponents will be since they can only go up to -50 and 50 by the problem statement2012-08-26
  • 0
    @SamuelGregory: re the conjugate, you want to change the sign of one term or the other. I chose the $b$, not the square root. re the problem with exponents, you are right in that $b^2$ overflows before $b$ does. This approach does not solve that, and I don't know of one that does. You can certainly use a numeric technique that avoids squaring $b$.2012-08-26
  • 0
    To avoid squaring $b$, use the Binomial Theorem: $(b^2-4ac)^{1/2}=\sum_{n=0}^\infty{1/2\choose n}(-4ac)^n(b^2)^{1/2-n}=-b\sum_{n=0}^\infty\frac{(2n-3)!!}{2^nn!}(4ac/b^2)^n$ (valid if $b^2>|4ac|$). Then write $h$ for $4ac/b^2$ (which you can compute as $4ac/b/b$) and rewrite as $-b\sum_{n=0}^\infty\frac{(2n-3)!!}{2^nn!}h^n=b-bh/4-bh^2/8-bh^3/16-\cdots$. Instead of $b^2$ overflowing, the danger is that $h^n$ will eventually underflow, but when that happens, you should be able to just truncate the sum. (In your case, $h$ will underflow immediately, but that's fine; $\sqrt{b^2-4ac}\approx b$.)2017-11-01
2

OK, just for fun, let's try a different method: $$ ax^2 + bx + c = 0 $$ $$ a + b\frac 1 x + c\frac{1}{x^2} = 0 $$ $$ a + bu + cu^2 = 0 $$ So $u=1/x$, and now we have a quadratic equation in $u$. Solve that by the usual formula (but we've interchanged the customary roles of $a$ and $c$, so do that in the formula as well): $$ u = \frac{-b\pm\sqrt{b^2 - 4ca}}{2c}. $$ $$ x = \frac{2c}{-b\pm\sqrt{b^2-4ca}}. $$