Finding true roots of $x^2 + 10^9x +1$ using the Quadratic Formula

Question

I've been given a hint to rearrange the quadratic formula to:

$$b\sqrt{1-\frac{4ac}{b^2}}$$

but am still dealing with a numerical error at $4/10^{18}$

Can I solve this numerically with the Taylor Series?

Answer 1

The problem is that the quadratic formula $\frac 1{2a}(-b \pm \sqrt {b^2-4ac})$ suffers from roundoff if $4ac \ll b$. In that case the square root is very close to $b$ and when you take the plus sign you get cancellation. Rewriting the parentheses as $b(-1+\sqrt{1-\frac {4ac}{b^2}})$ is a step. Then you can use the binomial theorem to say $\sqrt {1-\frac {4ac}{b^2}}\approx 1-\frac {2ac}{b^2}$. Now you can cancel the $1$'s analytically and be left with$ -\frac {2ac}{b^2}$. This will not overflow your floats and you have avoided the subtraction error.

Answer 2

Taylor is an option. Another option is to note that if $r_1$ and $r_2$ denotes the two roots then $(x-r_1)(x-r_2)=x^2 - (r_1+r_2) x +r_1 r_2 = x^2 + A x + 1$, where $A=10^9$ is large and positive.

This shows that $r_2=1/r_1$. So calculate one root from $r_1=-(A+\sqrt{A^2-4})/2$ and then $r_2=1/r_1=-2/(A+\sqrt{A^2-4})$.

If you want further precision you may factor out $A$, respectively $1/A$, and use Taylor on the remaining part. Another way is to calculate $x$ as a fixed point of a map. For the small solution you write $x(x+A)+1=0 \Leftrightarrow x= -\frac{1}{A+x}$. Initialize by $x_0=0$ and calculate $x_1=-\frac{1}{A+x_0}=-\frac{1}{A}$ and for more precision, $x_2=-\frac{1}{A+x_1}=\frac{1}{A-1/A}$, which may be expanded as $\frac{1}{A}(1-\frac{1}{A^2})^{-1}=-\frac1A-\frac{1}{A^3}...=-10^{-9}-10^{-27}...$, correct to 30 digits (or more).

The large solution may be found by iterating $x\mapsto -A-1/x$ starting with $x_0=-A$.

Answer 3

$$-b+\sqrt{b^2-4ac} = -10^9 + \sqrt{10^{18} - 4} \approx -10^9 + 10^9$$ The difference is so tiny compared to the quantities being subtracted that the difference gets lost.

Take $0$ to be a first approximation to the solution.

Plug the approximation into the equation in the quadratic term $x^2$ but not in the linear term. Solve the resulting linear equation. Take the solution to be the next approximation.

Iterate until yummy.

Answer 4

Almost as H. H. Rugh answered, consider the case of $$x^2+a x+1=0$$ where $a$ is a huge number.

The roots are given by $$x_{1,2}=-\frac{1}{2} \left(a\pm\sqrt{a^2-4}\right)=-\frac{a}{2} \left(1\pm\sqrt{1-\frac 4{a^2}}\right)$$ Now, using Taylor series for small $y$ (or the generalized binomial expansion)$$\sqrt{1-y}=1-\frac{y}{2}-\frac{y^2}{8}-\frac{y^3}{16}-\frac{5 y^4}{128}+O\left(y^5\right)$$ replace $y$ by $\frac 4{a^2}$ to get $$x_1=-a+\frac{1}{a}+\frac{1}{a^3}+\frac{2}{a^5}+O\left(\frac{1}{a^6}\right)$$ $$x_2=-\frac{1}{a}-\frac{1}{a^3}-\frac{2}{a^5}+O\left(\frac{1}{a^6}\right)$$