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?



Error in Polynomial Root Finding Algorithm with Synthetic Division
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](http://en.wikipedia.org/wiki/Wilkinson%27s_polynomial) 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.)


