User geekgirl - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T03:59:40Z http://mathoverflow.net/feeds/user/23915 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97807/error-in-polynomial-root-finding-algorithm-with-synthetic-division Error in Polynomial Root Finding Algorithm with Synthetic Division Geekgirl 2012-05-24T01:27:43Z 2012-05-25T04:15:04Z <p>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))</p> <p>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?</p> http://mathoverflow.net/questions/97807/error-in-polynomial-root-finding-algorithm-with-synthetic-division/97812#97812 Answer by Geekgirl for Error in Polynomial Root Finding Algorithm with Synthetic Division Geekgirl 2012-05-24T03:36:10Z 2012-05-24T03:36:10Z <p>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).</p> <p>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.</p> <p>This ensures that the values will be at least as precise as required.</p>