[kde-edu]: [KDE-EDU] KMathTool, Finding roots of Cubic polynomial

[Maurizio Paolini]

On Mon, Jan 17, 2005 at 09:01:23AM -0800, Trenton Carr wrote:
> Hello all
> 
> I'm trying to implement a class that takes the (math)function of a  
> hyperbola and parabola, solves them simultaneously by finding the roots of  
> a cubic polynomial. This gives the intercepts between the two.
> 
> ie:	hyperbola y = k/x
> 	parabola  y = ax^2+bx+c
> 
> solve simultaneously:	ax^3+bx^2+cx-k
> 
> this can be solved by factorizing the cubic by factor theorem, like so,
> 
> 		(x+?)(ax^2+bx+c)	where ? = Int. 	? can be found by inspection and  
> algebraic long division.

If I understand, you need to solve the cubic equation numerically and find only
the real roots (it seems to me that you are not interested in the complex ones).  
This can be
done using the exact formula ('http://mathworld.wolfram.com/CubicFormula.html')
or (better) by constructing the Sturm Sequence
('http://mathworld.wolfram.com/SturmFunction.html') which in this case consists
of four polynomial of degree 0, 1, 2 and 3 (the latter is the original
polynomial), call them p0, p1, p2, p3.
A Sturm sequence has the property that computing the number of changes in
sign sigma(x) in the sequence p0(x), p1(x), p2(x), p3(x) allows to compute
exactly how many roots are contained in some interval [a,b] by evaluating
sigma(b) - sigma(a). This, combined with a technique that gives you a big
interval that contains *all* the real roots allows you
1. to know how many real roots are there (1 or 3 in this case)
2. to isolate the roots, using bisection for example.

I actually used this method to compute the intersections of a cubic and a line
and the intersections between two conics in kdeedu/kig; you can also have a
look at the code in "kdeedu/kig/misc/kignumerics.cpp".

Cheers,
Maurizio Paolini