Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have written a program which finds the roots of polynomial using Newton's Method. After finding the first root to within a tolerance (note that this also finds complex roots), I use synthetic division to remove that root from the original polynomial (f = f/(x-root))

My question is, how does this affect the error? I can tell I get some shift as I look at my 20th root, but exactly how would I quantify this, and how would I ensure that the max error is still less than my tolerance?

share|improve this question
add comment

3 Answers

up vote 4 down vote accepted

It is a terrible idea to divide out roots as they are found. There will be examples where the later roots are lost almost completely. See this wikipedia article for a famous and remarkably simple example of a polynomial whose zeros are very sensitive to the coefficients. As soon as you divide out one zero approximately, you perturb the coefficients and the other zeros may have moved a lot. At the very least, all the roots should be refined using the original polynomial. Textbooks usually advise trying to find a way to solve your problem that does not involve root finding in a polynomial. (For example, getting the eigenvalues of a matrix by finding its characteristic polynomial first is nearly always a bad idea.)

share|improve this answer
    
@Brendan, your link seems to be broken... –  Igor Rivin May 24 '12 at 3:38
    
I think the link was meant to be to the article on Wilkinson's polynomial. –  Johan Wästlund May 24 '12 at 6:30
    
As an alternative to an eigenvalue solver, there is a "simultaneous Newton" that finds all the roots at the same time and works well in many examples: en.wikipedia.org/wiki/Aberth_method. There is a public "semi-free" implementation: en.wikipedia.org/wiki/MPSolve. –  Federico Poloni May 24 '12 at 6:49
    
@Igor: thanks, fixed link –  Brendan McKay May 25 '12 at 4:15
add comment

Books have been written about this. The primitive implementation of this is going to be terrible, but some tweaks (see this wikipedea article, and references therein) work ok.

share|improve this answer
add comment

The answer that I chose to implement was to find initial versions of all of my roots, then add an additional polishing function at the end (as suggested by both answerers). This function simply performed Newton's method on the values again, only using the initial function (without any synthetic division).

While this could hypothetically take twice as long (since re-doing Newton for each root), it shouldn't in practice- values very close to perfect and should terminated quickly by being within precision. Also should be in the basins of attraction for each fixed pt- and have a max # iterations to prevent getting out of control.

This ensures that the values will be at least as precise as required.

share|improve this answer
    
I would do the polishing as each root is found, so that the synthetic division is more precise. –  Brendan McKay May 25 '12 at 4:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.