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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sweet! Thank you for verifying! $\endgroup$ – Samuel Gregory Aug 26 '12 at 21:58
  • $\begingroup$ When you multiply by conjugate shouldnt it be -b? $\endgroup$ – Samuel Gregory Aug 26 '12 at 22:19
  • $\begingroup$ 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 statement $\endgroup$ – Samuel Gregory Aug 26 '12 at 22:31
  • $\begingroup$ @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$. $\endgroup$ – Ross Millikan Aug 26 '12 at 23:22
  • $\begingroup$ 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$.) $\endgroup$ – Toby Bartels Nov 1 '17 at 23:20
2
$\begingroup$

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}}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.