Prove that the rounding error can contaminate half the digits of computed root

Question

I am trying to resolve the following problem:

If $b^2 \approx 4ac $ the rounding error can contaminate half the digits of the root computed with the formula: $\dfrac {-b \pm \sqrt {b^2 - 4ac}} {2c} (\beta =2) $

I've tried to multiply with the conjugate for each numerator and I think the discussion is around the sign of $b$ However, I don't know how to continue forward.

Thanks.

Answer 1

Assume that $Δ=b^2−4ac≈0$ means that the actual value is $Δ=k^2·\mu$ where $μ=2^{-52}\sim 10^{-15}$ is the machine constant for the double type.

Then the floating point error for the computation of $fl(Δ)=fl(fl(b⋅b)−4⋅fl(a⋅c))$ and assuming "normal" values for $a,b,c$, for instance $a,b,c≈1,\pm2,1$, is of size $fl(Δ)-Δ=m·μ$ where $|m|<2$. Since all elementary operations are required to have an error smaller $μ/2$ one could argue that $|m|\le1$ is also true.

By Taylor or Newton, the transmitted error of the square root results from $$ \sqrt{k^2·μ+m·μ}=k·\sqrt{μ}·\left(1+\frac{m}{2k^2}+...\right) $$ so the actual error of the square root is of size $\frac{m}{2k}·\sqrt{μ}$, which can, depending on the actual size of the first ratio, contaminate about half the mantissa of the denominator.

Answer 2

I suppose that you solve for the roots of $a+bx+cx^2=0$ in which $\Delta=b^2-4ac$ is small. The roots are given by $$x_{\pm}=\dfrac {-b \pm \sqrt {b^2 - 4ac}} {2c}$$

Let us consider the case where $b>0$; so, by absolute value, the largest root is $$x_{-}=-\dfrac {b + \sqrt {b^2 - 4ac}} {2c}$$ and this should not make problem. Now, remember that $x_{-}\times x_{+}=\frac ac$ and $x_{-}+ x_{+}=-\frac bc$ and get $ x_{+}$ from one of these relations.

Just do the reverse if $b<0$.