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?
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.)
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.
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.
