|
WinSolve finds all zeros of a polynomial of any degree with
either real or complex coefficients using Bairstow's, Newton's, Halley's,
Graeffe's or Laguerre's method.
Last update on:
05/25/2007
Visitors:
 |
|
WinSolve:
Finds all zeros of a polynomial of any degree with either real or complex
coefficients using Bairstow's, Newton's, Halley's,
Graeffe's or Laguerre's method.
Furthermore Newton's methods is represented using 3 different approaches:
The Method by Madsen, The Method by Grant-Hitchins and the probably the most
famous the method by Jenkins-Traub. All 3 Newton variants existing in both a
real coefficients and a complex coefficients version. Bairstow method can
only handle real coefficients while Halley's, Graeffe's and Laguerre's works on complex
coefficients. Newton's method has quadratic convergence meaning that the
number of significant digits double for each iterations while Halley's and
Laguerre's has a cubic convergence meaning the number of significant digits
tripe for each iterations. All methods shows weakness when dealing with multiple
roots and the precision suffer considerably.
A more detail analysis of each method is found
in the user guide that can be downloaded directly from the link:
Winsolve User Guide.
WinSolve version 1.7
now:
Or try a web based solver:
|
Examples:
This is a 14 degree polynomials with the root -7,-6,-5,...,5,6,7
Polynomial:
x^14-140x^12+7462x^10-191620x^8+2475473x^6-15291640x^4+38402064x^2-25401600=0
Method: Real Newton (Jenkins-Traub)
Solution is:
Root Iter. REAL IMAG
1: 14 - 9.999999999999999e-001
2: 0 + 9.999999999999998e-001
3: 15 - 2.000000000000001e+000
4: 11 + 2.000000000000000e+000
5: 12 + 3.000000000000434e+000
6: 13 - 3.000000000000435e+000
7: 11 - 3.999999999999062e+000
8: 14 + 3.999999999999061e+000
9: 10 + 5.000000000000664e+000
10:12 - 5.000000000000655e+000
11:12 - 6.999999999999963e+000
12:17 + 5.999999999884272e+000
13: 0 - 5.999999999999906e+000
14: 0 + 7.000000000115590e+000
Compute time: 0 msec. Iterations 141
Jenkins-Traub finds
pretty good root estimate, but after root refinement we are dead on!
Solution after root refinement is:
Root Iter. REAL IMAG
1: 17 - 1.000000000000000e+000
2: 3 + 1.000000000000000e+000
3: 18 - 2.000000000000000e+000
4: 14 + 2.000000000000000e+000
5: 15 + 3.000000000000000e+000
6: 16 - 3.000000000000000e+000
7: 14 - 4.000000000000000e+000
8: 17 + 4.000000000000000e+000
9: 13 + 5.000000000000000e+000
10:15 - 5.000000000000000e+000
11:15 - 7.000000000000000e+000
12:24 + 6.000000000000000e+000
13: 3 - 6.000000000000000e+000
14: 7 + 7.000000000000000e+000
Compute time: 1412 msec. Iterations 191
For multiple root the root refinement works really impressive. The roots
are:(x-1)^4(x-2)^3(x-1)^2=0
Polynomial:
x^9-16x^8+111x^7-438x^6+1083x^5-1740x^4+1817x^3-1190x^2+444x-72=0
Method: Real Newton (Jenkins-Traub)
Solution is:
Root Iter. REAL IMAG
1: 6 + 1.000765930710291e+000
2: 10 + 9.992354246716848e-001
3: 35 + 9.999993223132694e-001 + i7.652508771728135e-004
4: 0 + 9.999993223132694e-001 - i7.652508771728135e-004
5: 8 + 2.000001502125681e+000
6: 10 + 2.000001568510758e+000
7: 10 + 1.999996929358801e+000
8: 0 + 2.999999000397843e+000
9: 0 + 3.000000999598405e+000
Compute time: 0 msec. Iterations 79
Very typical result for standard root finders like the Jenkins-Traub with
only 2-6 significant digits. After root refinement we have perfect roots!
Solution after root refinement is:
Root Iter. REAL IMAG
1: 7 + 1.000000000000000e+000
2: 11 + 1.000000000000000e+000
3: 36 + 1.000000000000000e+000
4: 33 + 1.000000000000000e+000
5: 9 + 2.000000000000000e+000
6: 11 + 2.000000000000000e+000
7: 19 + 2.000000000000000e+000
8: 6 + 3.000000000000000e+000
9: 57 + 3.000000000000000e+000
Compute time: 3054 msec. Iterations 189
|
|
