{ Numerical Methods}

Home
Polynomial Zeros
Arbitrary Precision
Numerical Ports
Papers
Related Sites
Contact us
Feedback?

Web Tools
Polynomial Roots
Splines or Polynomial Interpolation
Numerical Integration
Differential Equations
Complex Expression Calculator
Financial Calculator
Car Lease Calulator
 
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 OR NOT 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: 135392

Polynomial Root Finder vs 1.44
P(x)=  
  Display Iteration trail Verbose Mode  

         

  • Results
  • Graph: Roots
  • Graph: P(x) Values
  • Graph: Convergence
  • Help
  • Method used
Your browser does not support canvas which is part of HTML 5. Please upgrade your browser.
Your browser does not support canvas which is part of HTML 5. Please upgrade your browser.
Your browser does not support canvas which is part of HTML 5. Please upgrade your browser.

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. x^3-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.5x^3+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)x^3-2x^2-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*3x^4-5^2x or (1+2*3x^4-5^2x)^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.
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, Durand-Kerner, Jenkins-Traub methods. If you are interested in seeing all these methods in actions go to http:www.hvks.com/Numerical/winsolve.html For this Polynomial root finder we use 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 an upper bound of the errors in calculating f(x) for the polynomial.
By checking the verbose mode you can get a taste of how this method is working.
Rate this page
Click on the stars to rate this page
Low    High
Missing anything? or comment your rating. If reporting a bug please add you email address.

 

 
Note:
If you are reporting a bug:
1)Add an Email address. (in case I have questions)
2)And the polynomial your are trying to solve. If I can't get a detailed bug report I can't improve anything! (Please help me out here)
Corrections:
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)