Numerical Methods at work

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: 243686)

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.

Rate this page

Click on the stars below to rate this page

Low
High


Corrections:
5-Mar-2024 Introduce Autoscaling, no autoscaling in plotting of graph and 2D contour
20-Dec-2023 Added 2D Contour plot
23-Nov-2023 Added 3D Surface plot
30-Oct-2023 Improve the termination criterion for the Durand-Kerner and the Anerth method
22-Oct-2023 Switched to the Plotly librariy for the graphic. The issue with the Plot function has been fixed
12-Jul-2021 Fixed a bug in parsing Polynomial involving non-integer number to the ^ operator
24-Jun-2020 Added Steffensen & Arithmetic Mean Newton root method
6-Jun-2020 Added Chebyshev & Ostrowski Square root method
26-Apr-2020 Added Durand-Kerner and Aberth-Ehrlich method
22-Apr-2020 Fix a bug in the Halley method for multiplicity greater than 1
17-Apr-2020 Fix a bug in the Ostrowski method
16-Mar-2020 Added the Laguerre's and the Eigenvalue methods for finding zeros of Polynomials with either real or complex coefficients
31-Jan-2020 Added the fameous Jenkins-Traub methods for finding zeros of Polynomials with either real or complex coefficients
29-Jan-2020 Fixed an issue where the test for newton convergence produce a wrong result making Newton, Halley & Householder failed for large polynomials
17-Jan-2020 Added 3 extra methods, Halley, Householder 3rd and Ostrowski
1-Nov-2019 GUI redesigned
25-Oct-2018 Fix a bug where the wrong Complex arithmetic libraries was uploaded to the web site.
24-Mar-2014 Fixed several parsing issues involving cascade power e.g. i^2, i^3^2 and cascade power for x e.g. x^2^3 etc. Fixed also an overflow issue when dealing with polynominal with a degree exceeding 174. e.g. x^175+1. Thanks to Kaspii Kaspars & Wei Xu for reporting this.
21-Apr-2011 Email button added, for Emailing the result.
17-Apr-2011 Layout changes and switching to using canvas object for HTML graphic. Now Print also print the Graphic of the Roots, Function Values and Convergence Power
16-Nov-2009 A parsing error was corrected -x^2 was incorrectly parsed as x^2 while -1x^2 was handle correctly
28-Oct-2009 A parsing error was corrected involving proper treatment of the exponent E or e in the expression like1.31E-06
20-Jun-2009 Works now with the Safari Browser
14-Apr-2009 Fixed a bug that allowed overflow in calculation caused by unreasonable step size for large polynomials greater than x^27 resulting in some incorrect roots.
24-Feb-2009 Parsing bug corrected that incorrectly did not recognized an implicit multiplication in complex expression.
01-Jan-2009 Parsing bug corrected that left out the constant term in some situations
23-Oct-2008 Detect a constant as a non polynomial and report an error
05-Sep-2008 Works with Google Chrome
18-Jul-2008 Works with IE7, Firefox 2 & 3 and add polynomial expression as input
30-Oct-2007 Complex coefficients with an implicit value e.g (i) was interpreted as i0 instead of i1
29-July-2007 Now roots point in the graphic display will also be printable
12-July-2007 A bug has been fixed for polynomial with roots of zeros.
07-Dec-2006: A small FireFox 2.0 bug was corrected on Dec 8, 2006. The  problem was that separation of sign and arguments was not done correctly due to a differences in the Regular expression split function. (Thanks to Brian Phelan for making me aware of the problem and providing the fix)