Math Is Fun Forum / Quadratic Equation Solver

MathsIsFun · 2011-05-07 16:19:41

I have updated the Quadratic Equation Solver

Could you guys give it a bit of a workout and let me know how it goes?

bobbym · 2011-05-07 18:05:09

Hi MathsIsFun;

Worked on all test examples. Worked well.

For a quadratic of this type, known to be numerically unstable

The solver gets ( -0.0000017547864, -712345.12) the actual answer is: (-0.00000175476742..., -712345.119998245...)

The answer given by the solver implies an error of ±
5 * 10^-14, the true error is closer to 10^-10 for the smaller root. When I say smaller I mean in magnitude.

By producing other quadratics with the property that:

It is possible to lose more digits, thus drowning out the solution.

This is not due to any error on your part. The high condition number of this polynomial is causing subtractive cancellation in the quadratic formula ( or whatever other method the solver is using ).

It is for this not well known reason that the quadratic formula is not used in numerical analysis! In short it may be taught everywhere but it is not reliable.

If you are passed the debugging stage and want to add more bells and whistles to this solver, then I could show you a simple modification that will increase the accuracy of the smaller root. A way that makes the quadratic formula somewhat stable.

MathsIsFun · 2011-05-07 20:04:19

Thank you very much for the testing.

bobbym wrote:
If you are passed the debugging stage and want to add more bells and whistles to this solver, than I could show you a simple modification that will increase the accuracy of the smaller root. A way that makes the quadratic formula somewhat stable.

Yes, please!

(PS: Your current Yoda avatar very much I like.)

ganesh · 2011-05-07 21:31:48

Hi MathsIsFun,

The Quadratic Equation Solver is well presented. The solver works well.

I feel the page may include mentioning how to form equation given the roots. Also, the sum of the roots and their product.

bobbym · 2011-05-07 23:21:57

Hi;

(PS: Your current Yoda avatar very much I like.)

Yoda? Me that be.

Real Roots Only.

It is known that the product of the roots are equal to c / a . If you have divided through by a to create a monic polynomial then the product of the roots is just c.

When

Or more clearly when b is much larger than 4ac then it is much more numerically stable to get the smaller root by dividing c by the larger root. Provided the larger root > c. When I say larger I mean the absolute value of the two roots.

In the previous example the solvers answer of -712345.12 is used to get the smaller root to high precision:

Notice it agrees with the high precision answer of -0.00000175476742795... much better than before.

In order to understand why this works you only need the knowledge that any time you have a floating point number in a computer that number n is actually represented as:

Where epsilon represents the error in the representation. Any time you divide a smaller number by a larger one the error portion of the numerator is divided, made smaller. So division is an error minimizer while multiplication is an error magnifier. Dividing by 712345 picks up 2 or 3 correct digits for us.

There is a general rule that covers all the real roots:

Forman S. Acton wrote:
In order to preserve significant digits one should always get the larger root ( in absolute value ) by using the sign that avoids a subtraction. That is, use - if b is positive and + if it is negative. Then use x1 * x2 = c for the smaller root.

He means in the quadratic formula and a monic polynomial. This also saves some time because you only need to use the formula once, instead of twice.

MathsIsFun · 2011-05-08 14:26:37

Excellent. Now I just need to translate that to an algorithm. Something like:

(divide through by a)
(make sure root1 is bigger in magnitude than root2, else swap)
if root1 (much bigger than) root2 {
root2 = root1/c;
}

Yes?

ganesh wrote:
I feel the page may include mentioning how to form equation given the roots. Also, the sum of the roots and their product.

Good ideas ... I can show them at the bottom.

bobbym · 2011-05-08 16:42:49

Hi MIF;

Since you need the discriminant anyway, compute it first. When the roots are real use this routine, else use the one you already have.

1) Divide through by a to turn it into a monic polynomial.

2) Is b negative then use:

3) Is b positive then use:

4) Is root1 bigger than c?

5a) Yes: root2 = c / root1 ; goto 6:

5b) No: Get root2 in the ordinary way. By using the other form of the quadratic.

6) Done:

Example:

b is negative so use:

Notice you did not need a compare, this method always produces the largest root first.

xlarger is bigger than c so,

If xlarger was not greater than c then you would use the other form of the quadratic to get root2.

Have I explained it well enough? If not what do you require?

MathsIsFun · 2011-05-09 09:37:13

Thanks "Yoda", will get on to it soon.

bobbym · 2011-05-09 15:40:47

Hi MIF;

Sorry, I am sick so I was unable to answer. Look at the claws on that creature!

MathsIsFun · 2011-05-09 22:21:47

Oh no ... a virus of some sort?

bobbym · 2011-05-10 04:45:19

Yes, and back problems resurfacing. Soon they will just put me to sleep and toss me out into the dumpster.

MathsIsFun · 2011-05-10 07:34:10

Virus will clear up. Do exercises for back.

Keep the evil dumpster at bay!

bobbym · 2011-05-10 09:17:34

Luckily, I do not have to shop for food. It frightens the kiddies when I am seen lurching down the street. My only hope is the the townspeople do not mistake me for Frankenstein's monster and put me to the torch.

Have you been able to implement the idea? Is the pseudocode clear enough?

MathsIsFun · 2011-05-10 13:52:34

So, does someone else shop for you, or do you run on nuclear energy?

Anyhoo ... new version posted (0.72) ... does it pass the tests?

bobbym · 2011-05-10 17:32:15

Hi MIF;

So, does someone else shop for you, or do you run on nuclear energy?

No, I just have a big supply of food in the house. When I was a kid my grandfather used to say that I ran on atomic energy.

Worked on all my examples, accuracy good.

amit28it · 2011-10-19 18:32:47

Quadratic Equation Solver :
You have done good work and it will be better for us if you will work will on homogenous equation.
As for all Discriminant should be
D=sqrt(b^2-4ac)
and
c=b/a;

bobbym · 2011-10-19 20:50:33

Hi;

The discriminant is not the point of this calculation. Anyway, who said it was anything else ( leave out the square root )?

The discriminant is only used to show when the quadratic formula is unstable for numerical calculation.

The idea is to increase the numerical stability of the quadratic formula. To make it more amenable to computer calculation.

MathsIsFun · 2011-10-20 14:34:18

Also, amit28it, your formula is not quite right. The discriminant does not include the square root, it is simply b^2-4ac

bobbym · 2011-10-20 20:34:32

Hi;

Yes, leave out the square root. Sorry, I missed that.

Login

Ads

Menu

#1 2011-05-07 16:19:41

Quadratic Equation Solver

#2 2011-05-07 18:05:09

Re: Quadratic Equation Solver

#3 2011-05-07 20:04:19

Re: Quadratic Equation Solver

bobbym wrote:

#4 2011-05-07 21:31:48

Re: Quadratic Equation Solver

#5 2011-05-07 23:21:57

Re: Quadratic Equation Solver

Forman S. Acton wrote:

#6 2011-05-08 14:26:37

Re: Quadratic Equation Solver

ganesh wrote:

#7 2011-05-08 16:42:49

Re: Quadratic Equation Solver

#8 2011-05-09 09:37:13

Re: Quadratic Equation Solver

#9 2011-05-09 15:40:47

Re: Quadratic Equation Solver

#10 2011-05-09 22:21:47

Re: Quadratic Equation Solver

#11 2011-05-10 04:45:19

Re: Quadratic Equation Solver

#12 2011-05-10 07:34:10

Re: Quadratic Equation Solver

#13 2011-05-10 09:17:34

Re: Quadratic Equation Solver

#14 2011-05-10 13:52:34

Re: Quadratic Equation Solver

#15 2011-05-10 17:32:15

Re: Quadratic Equation Solver

#16 2011-10-19 18:32:47

Re: Quadratic Equation Solver

#17 2011-10-19 20:50:33

Re: Quadratic Equation Solver

#18 2011-10-20 14:34:18

Re: Quadratic Equation Solver

#19 2011-10-20 20:34:32

Re: Quadratic Equation Solver

Board footer