Disclaimer:
Permission to use, copy, and distribute this software, and It’s documentation for any non-commercial purpose is hereby granted without fee, provided: THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL Henrik Vestermark, BE LIABLE FOR ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

# Polynomial Root finder

(Hit count: 241723)

This Polynomial solver finds the real or complex roots (or zeros) of a polynomial of any degree with either real or complex coefficients. The method was original based on a modified Newton iteration method developed by Kaj Madsen back in the seventies, see: [K.Madsen: "A root finding algorithm based on Newton Method" Bit 13 1973 page 71-75]. However I have recently added other methods: Ostrowski, Halley's, Householder 3rd order, Jenkins-Traub, Laguerre's, Eigenvalue, Durand-Kerner, Aberth-Ehrlich, Chebyshev, Ostrowski Square root method, Arithmetic Mean Newton & Steffensen method. See the Authors paper on the subject Read more ... Notice that all methods are so called modified method's, which maintain there convergence rate even for multiple roots.

Polynomial Root Finder vs 1.63

Options

• Results
• Graph: Roots
• Graph: P(x) Values
• Graph: Convergence
• 3D Surface Plot
• 2D Contour Plot
• Help
• Method used

#### Polynomial root finder

This Polynomial solver finds the real or complex roots of a polynomial of any degree with either real or complex coefficients. The polynomial is general written on the form anxn+an-1xn-1....a1x+a0 where a is a real or complex number and n is an integer.
To enter a polynomial you just type 'naturally' E.g. x3-3x+4 and hit the Solve Equation button to find all the roots. x^3 stands for x3. The coefficients can be in any order. E.g. -1.2+3.5x3+4.5x-1.2E-1x is just as valid.
Floating point in standard notation IEEE754 format with e or E as exponent is OK. e.g. 120 1.20e2 12E+1 1200E-1 all represent the same number 120. Complex coefficients can be entered with surrounding () where needed e.g. (3-i4)x3-2x2-i4x-3
Checkmark the Verbose print out details about the each iteration steps.
Checkmark the Display Iteration trail print out and show graphical the iterations towards the root.
There should be no limitation of the polynomial degree it can solve.
For the more advance user you can type in any polynomial expression. E.g. (x-1)(x-2)(x-3) or 1+2*3x4-5x2x or (1+2*3x4-5x2)3. The operator +,-,*,/,^ is all supported together with using () to group polynomial expression
The Test button setup a default polynomial as an example of how to enter a polynomial.
The 3 tabs (Roots, Function Values & Convergence) show graphical the roots in the complex plan. The Function value for each iteration step as it converged towards the root and Convergence power for each iterations step. When this Newton methode converged toward a root the convergence power is a factor of 2 meaning that for each iteration step the number of significant digits in the root double for each iteration. For Halleys method the number of significants digits triples per iteration and finally for both Ostrowski & Householder 3rd order methods the number of significant digits increase by a factor 4 for each iteration.
Email: hve@hvks.com if you have any questions.
This version has been tested with both IE9, Chrome 10, Firefox 3 & Safari 5 browser.

#### Finding all roots for a polynomial with either real or complex coefficients.

Let the polynomial be given by: f(x)=anxn+an-1xn-1....a1x+a0
Where an is either a real or complex number. We try to find all roots to this polynomial by solving the equation for x.

anxn+an-1xn-1....a1x+a0=0

There exist many methods available to solve this problem. Among them are Newton's, Bairstow's, Halley's, Laguerre's, Graeffe's, Alberth's, Durand-Kerner, Jenkins-Traub, eigenvalue methods etc. If you are interested in seeing all these methods in actions go to http://hvks.com/Numerical/websolver.phpor stay here since you can watch them all in action. For this Polynomial root finder we default to one of the Newton's variants original developed by Kaj Madsen in the early seventies [K.Madsen: "A root finding algorithm based on Newton Method" Bit 13 1973 page 71-75]. The reason is that it is fast, reliable and can also handle the traditional problems a Newton method can ran into when searching for roots.
Newton has quadratic convergence meaning that for each iteration the numbers of significant digits in the root doubles. What is remarkable by Madsen implementation is that it maintains the quadratic convergence even for multiple roots which otherwise will converge to a root on a much slower pace.
The method works by finding one root at a time, then divide the root up into the polynomial. The resulting polynomial is one degree lower than the original polynomial and you then repeat the process until all roots have been found. For quadratic polynomial or lesser degree we however solve the polynomial directly. To start a search for a root we go though the following steps.
• The initial start value for the root search. Instead of using a fixed start guess we start with a guess that is less than the modulus of any root of f and as a general strategy try to find the roots in increasing order of modulus to ensure a stable deflation process. [J.H.Wilkinson: "Rounding erros in algebraic processes" Prentice-Hall 1963]
• The iterations phase. Madsen divide the iteration up into two stages. Stage 1 is the phase where we need to get into a position where we know the Newton will converge to a root. This is the most complicate stage and we would need to safeguard the search by being able to successful handle ?saddle point? or handle unreasonable steps side etc. Stage 2 is entered when we are sufficient close to the root that we can rely on the standard Newton step to do the job.
• Termination of the iterations. This is another important part if our stopping criteria is too aggressive we will never get there on the other hand if we are to relax the root will not be as accurate as we could possible obtain. For polynomial with real coefficients we use the stopping criteria proposed by D. Adams [D.Adams "A Stopping criterion for polynomial Root finding" Comm ACM 10 1967 pp 655-658]. For complex coefficients polynomial we use the stopping criteria from Grant & Hitchins [Grant, J A & Hitchins, G D. Two algorithms for the solution of polynomial equations to limiting machine precision. The computer Journal volume 18 Number 3, page 258-264] polynominal solver for complex coefficients.
By checking the verbose mode you can get a taste of how this method is working.