Factoring: program doesn't take into account when a 'crossover' is at repeating or...

[TheOAP]

Hi,
I've written a program (Polynomials) that attempts to factor equations.
It works OK. After the basic techniques I use Synthetic Division (SD).
The literature says that the factors +/-(of Constant / Highest exponents coefficient) are the ONLY possible factors.
But this doesn't take into account when a 'crossover' is at a re[eating or irrational value, so I built an extension to SD.
It works OK. by a "brute force" method :

[1] Find a start and end value of 'x' to search for.
[2] Set X1 & X2 to the start value (-ive) and X2 to X1 +1
[3] Generate f(FX1) & f(FX2) for the values of X1 & X2
[4] Look for a 'crossover' on the X axis. If found store them.
[5] When all have been found narrow the 'steps' to 0.0000001 and repeat above
for the stred values.
But suppose there is more than 1 crossover between X1 & X2 ?
Can you think of a way I can get round this ?
Pete

 

[Steven G]

The literature says that the factors +/-(of Constant / Highest exponents coefficient) are the ONLY possible ROOTS.

This statement is not true at all. Consider x²-2. You are clearly saying that the only possible roots are +/- 1 and +/- 2. None of these work but +/-sqrt(2) surely works. I guess you have to start all over (I hope not).

 

[Dr.Peterson]

Hi,
I've written a program (Polynomials) that attempts to factor equations.
It works OK. After the basic techniques I use Synthetic Division (SD).
The literature says that the factors +/-(of Constant / Highest exponents coefficient) are the ONLY possible factors.
But this doesn't take into account when a 'crossover' is at a repeating or irrational value, so I built an extension to SD.
It works OK. by a "brute force" method :

[1] Find a start and end value of 'x' to search for.
[2] Set X1 & X2 to the start value (-ive) and X2 to X1 +1
[3] Generate f(FX1) & f(FX2) for the values of X1 & X2
[4] Look for a 'crossover' on the X axis. If found store them.
[5] When all have been found narrow the 'steps' to 0.0000001 and repeat above
for the stred values.
But suppose there is more than 1 crossover between X1 & X2 ?
Can you think of a way I can get round this ?
Pete

Presumably the literature you read says that these are the only possible rational zeros of the polynomial. That is a very different thing. You seem to be aware that this will miss irrational zeros; but it will not miss "repeating" zeros, which are rational.

I suppose you are using "crossover" to refer to a zero of the polynomial where its value changes sign. Note that it will not change sign at every zero; at some, it will just "touch and turn". But even ignoring that, your method will be very inefficient, and can easily miss zeros. One way to identify when there are multiple crossings would be to find where the derivative is zero (since the curve has to change directions between them). But that requires you to do the same thing you are doing, with a polynomial whose degree is one less.

There is a great deal of theory about polynomial equations, much of which I have not seen. Have you tried searching for more of it than the wrong theorem you found? How much else have you learned about polynomials? You might start here.

 

[JeffM]

As has been pointed out, the theorem that you think you are using finds a rational root of a polynomial with integer coefficients if there is such a rational root. The theorem does not say that such a root exists, and it does not apply at all to polynomials with even one coefficient that is not an integer.

I want to point out another problem. If you are dealing with irrational roots, a numerical method will not directly give you the factorization you seek because you will only get an approximate value for the root.
That is, there is a simple factoring of

\(\displaystyle x^2 - 37 = (x - \sqrt{37})(x + \sqrt{37})\)

but no purely numerical method of approximating roots will give you that result.

If you want to factor in order to find roots, it is probably easier to just use a root finding algorithm. A book on numerical methods will have fast algorithms for finding a good approximation for a root.

EDIT: You have not said what degree of polynomial you want to factor. There are formulas for quadratics, cubics, and quartics.

 

[TheOAP]

As has been pointed out, the theorem that you think you are using finds a rational root of a polynomial with integer coefficients if there is such a rational root. The theorem does not say that such a root exists, and it does not apply at all to polynomials with even one coefficient that is not an integer.

I want to point out another problem. If you are dealing with irrational roots, a numerical method will not directly give you the factorization you seek because you will only get an approximate value for the root.
That is, there is a simple factoring of

\(\displaystyle x^2 - 37 = (x - \sqrt{37})(x + \sqrt{37})\)

but no purely numerical method of approximating roots will give you that result.

If you want to factor in order to find roots, it is probably easier to just use a root finding algorithm. A book on numerical methods will have fast algorithms for finding a good approximation for a root.

EDIT: You have not said what degree of polynomial you want to factor. There are formulas for quadratics, cubics, and quartics.

Hi JeffM
Thanks for your comments.
The final result to an irrational value is 2 numbers serarated by 0.000001
All the trial data I use (taken from textbooks or self generated) was
calculated manually and also graphically.
The extension to Synthetic Division IS inefficient but its a last 'gasp' when SD
doesn't provide the possible number of solutions (n, n-2 etc .. or none.)

Extended Synthetic Division for 4x4 - 10x2 + 1 :
| * No Rational roots found *
| Irrational/repeating root(s):
| between
| -1.547787 and -1.547786 y
| -0.323042 and -0.323041 y
| 0.323041 and 0.323042 y
| 1.547786 and 1.547787

I'd still like to know how to determine an efficicient "range"
in which to search!

Pete

 

[JeffM]

Pete

I am really not qualified to answer. I took just one course on numerical methods back in 1968, which is a very long time ago, but I do seem to remember that there were several methods for finding good initial values for an iterative process such as Newton-Raphson. Dr. Peterson gave you a reference indicating that this is not a topic on which memories from five decades ago will be much help even if they are correct. You need an up-to-date text on numerical methods.