5
$\begingroup$

Homework disclaimer...

The task:

We are using the following algorithm to solve the quadratic equation $x^2+2px+q=0$:

$x_1=|p|+\sqrt{p^2-q}\mathtt{;}$

$\mathtt{if}\,p>0\,\mathtt{then}\,x_1=-x_1\mathtt{;}$

$x_2=q/x_1\mathtt{;}$

Point out two places where running this algorithm can meet significant problems. How to mitigate these problems?

That's my guess: The first place is this: $p^2-q$, we're risking catastrophic cancellation here; and the second place is this: $q/x_1$, we're getting a NaN if $x_1$ is $0$.

The second one seems kind of easy: the only way for the absolutey larger root to be $0$ is when both roots are $0$, which entails so $p=q=0$; we can test for this case.

I don't know how to mitigate the first problem, though. I can't think of a way to solve a quadratic equation without computing its discriminant, and computing its discriminant does require subtraction. Which, of course, risks catastrophic cancellation.

Is there any way to avoid catastrophic cancellation when computing the discriminant of a quadratic function?

EDIT: As per request from comments, moving additional info from answer to question:

Hah. Regarding $x_1=|p|+\sqrt{p^2-q}$. Another student was arguing today that this cannot be an issue: According to him, catastrophic cancellation can only occur if $p^2\approx q$; but then $\sqrt{p^2-q}\approx 0$ and moreover $|p|\gg\sqrt{p^2-q}$; so the discriminant itself and any errors introduced by computing it loose significance when computing $x_1$. The Professor said he would have to think about it; I'll post an update here if/when he's done thinking.

However, there is one more problem I failed to notice. Namely, if $p$ is large, then $p^2$ may overflow; but then $\sqrt{p^2-q}$ will also overflow even if its accurate value would fit in the range of the number format; so $x_1$ will be spuriously set to $\infty$. To avoid this, the Professor said, $p$ needs to be rescaled if its large enough.

$\endgroup$
  • 4
    $\begingroup$ This answer on Stackoverflow may be helpful. $\endgroup$ – njuffa Dec 13 '18 at 17:22
  • $\begingroup$ or Math @njuffa $\endgroup$ – simon Dec 13 '18 at 17:30
  • $\begingroup$ @GoHokies As per your request, added this to question. Not sure why, though? That "nothing needs to be done wrt catastrophic cancellation" seems to me to be an answer; also the overflow problem is, as well, an answer to the homework task. $\endgroup$ – gaazkam Dec 14 '18 at 21:48
  • $\begingroup$ The statement that $\sqrt{p^2-q}\approx0$ is sufficient to ensure that the formula is fine seems true in the real case, but is wrong when $p^2-q<0$, which should trigger your code to output two complex numbers. I think a counterexample is any quadratic with $p^2-q\approx0$ where your evaluation of $p^2-q$ produces the wrong sign. But you seem to assume only real roots. (Also: it is quite alright to answer your own questions on Stack Exchange, and your answer looks okay to me.) $\endgroup$ – Kirill Dec 15 '18 at 0:51

Your Answer

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

Browse other questions tagged or ask your own question.