1942:
6009:
1569:
1427:
7206:
5696:
1086:
1937:{\displaystyle {\begin{aligned}{\bar {H}}^{(\lambda +1)}(X)&={\frac {1}{X-s_{\lambda }}}\cdot \left(P(X)-{\frac {P(s_{\lambda })}{H^{(\lambda )}(s_{\lambda })}}H^{(\lambda )}(X)\right)\\&={\frac {1}{X-s_{\lambda }}}\cdot \left(P(X)-{\frac {P(s_{\lambda })}{{\bar {H}}^{(\lambda )}(s_{\lambda })}}{\bar {H}}^{(\lambda )}(X)\right)\,.\end{aligned}}}
6991:
261:
each root is found, the polynomial is deflated by dividing off the corresponding linear factor. Indeed, the factorization of the polynomial into the linear factor and the remaining deflated polynomial is already a result of the root-finding procedure. The root-finding procedure has three stages that correspond to different variants of the
3538:
4752:
43:. They gave two variants, one for general polynomials with complex coefficients, commonly known as the "CPOLY" algorithm, and a more complicated variant for the special case of polynomials with real coefficients, commonly known as the "RPOLY" algorithm. The latter is "practically a standard in black-box polynomial root-finders".
5379:
7226:. The algorithm finds either a linear or quadratic factor working completely in real arithmetic. If the complex and real algorithms are applied to the same real polynomial, the real algorithm is about four times as fast. The real algorithm always converges and the rate of convergence is greater than second order.
6986:
1023:
7212:
is applied in the three variants of no shift, constant shift and generalized
Rayleigh shift in the three stages of the algorithm. It is more efficient to perform the linear algebra operations in polynomial arithmetic and not by matrix operations, however, the properties of the inverse power iteration
6004:{\displaystyle s_{\lambda +1}=s_{\lambda }-{\frac {P(s)}{{\bar {H}}^{(\lambda +1)}(s_{\lambda })}}=\alpha _{1}+O\left(\prod _{\kappa =0}^{\lambda -1}\left|{\frac {\alpha _{1}-s_{\kappa }}{\alpha _{2}-s_{\kappa }}}\right|\cdot {\frac {|\alpha _{1}-s_{\lambda }|^{2}}{|\alpha _{2}-s_{\lambda }|}}\right)}
5691:
7264:
recommends that it is desirable for stable deflation that smaller zeros be computed first. The second-stage shifts are chosen so that the zeros on the smaller half circle are found first. After deflation the polynomial with the zeros on the half circle is known to be ill-conditioned if the degree is
247:
The real variant follows the same pattern, but computes two roots at a time, either two real roots or a pair of conjugate complex roots. By avoiding complex arithmetic, the real variant can be faster (by a factor of 4) than the complex variant. The
Jenkins–Traub algorithm has stimulated considerable
2673:
are simultaneously met. This limits the relative step size of the iteration, ensuring that the approximation sequence stays in the range of the smaller roots. If there was no success after some number of iterations, a different random point on the circle is tried. Typically one uses a number of 9
260:
with complex coefficients. The algorithm starts by checking the polynomial for the occurrence of very large or very small roots. If necessary, the coefficients are rescaled by a rescaling of the variable. In the algorithm, proper roots are found one by one and generally in increasing size. After
1422:{\displaystyle \left.{\begin{aligned}P(X)&=p(X)\cdot (X-s_{\lambda })+P(s_{\lambda })\\H^{(\lambda )}(X)&=h(X)\cdot (X-s_{\lambda })+H^{(\lambda )}(s_{\lambda })\\\end{aligned}}\right\}\implies H^{(\lambda +1)}(z)=h(z)-{\frac {H^{(\lambda )}(s_{\lambda })}{P(s_{\lambda })}}p(z).}
3046:
4192:
3339:
5201:
5520:
5163:
7201:{\displaystyle A={\begin{pmatrix}0&0&\dots &0&-a_{0}\\1&0&\dots &0&-a_{1}\\0&1&\dots &0&-a_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\dots &1&-a_{n-1}\end{pmatrix}}\,.}
6686:
836:
5527:
831:
2054:
The shift for this stage is determined as some point close to the smallest root of the polynomial. It is quasi-randomly located on the circle with the inner root radius, which in turn is estimated as the positive solution of the equation
4881:
3757:
3154:
If the step size in stage three does not fall fast enough to zero, then stage two is restarted using a different random point. If this does not succeed after a small number of restarts, the number of steps in stage two is doubled.
5039:
2894:
2671:
2573:
167:
6544:
6123:
All stages of the
Jenkins–Traub complex algorithm may be represented as the linear algebra problem of determining the eigenvalues of a special matrix. This matrix is the coordinate representation of a linear map in the
2481:
1560:
4187:
4011:
560:
3299:
2186:
7221:
The
Jenkins–Traub algorithm described earlier works for polynomials with complex coefficients. The same authors also created a three-stage algorithm for polynomials with real coefficients. See Jenkins and Traub
2889:
3625:
5384:
5048:
1574:
230:
2786:
6421:
2248:
627:
6108:
1094:
6206:
4747:{\displaystyle {\bar {H}}^{(\lambda )}(X)={\frac {\sum _{m=1}^{n}\left^{-1}\,P_{m}(X)}{\sum _{m=1}^{n}\left^{-1}}}={\frac {P_{1}(X)+\sum _{m=2}^{n}\left\,P_{m}(X)}{1+\sum _{m=1}^{n}\left}}\ .}
6606:
3899:
3533:{\displaystyle s_{\lambda +1}=s_{\lambda }-{\frac {P(s_{\lambda })}{{\bar {H}}^{\lambda +1}(s_{\lambda })}}=s_{\lambda }-{\frac {W^{\lambda }(s_{\lambda })}{(W^{\lambda })'(s_{\lambda })}}}
6319:
6054:
383:
3103:
6241:
7260:
However, there are polynomials which can cause loss of precision as illustrated by the following example. The polynomial has all its zeros lying on two half-circles of different radii.
2352:
704:
699:
3334:
1999:
3185:
of the Newton–Raphson method, however, it uses one-and-half as many operations per step, two polynomial evaluations for Newton vs. three polynomial evaluations in the third stage.
385:
Other root-finding methods strive primarily to improve the root and thus the first factor. The main idea of the
Jenkins-Traub method is to incrementally improve the second factor.
5374:{\displaystyle H^{(\lambda )}(X)=P_{1}(X)+O\left(\left|{\frac {\alpha _{1}}{\alpha _{2}}}\right|^{M}\cdot \left|{\frac {\alpha _{1}-s}{\alpha _{2}-s}}\right|^{\lambda -M}\right)}
2728:
2296:
1479:
7281:
Press, W. H., Teukolsky, S. A., Vetterling, W. T. and
Flannery, B. P. (2007), Numerical Recipes: The Art of Scientific Computing, 3rd ed., Cambridge University Press, page 470.
3652:
3149:
3794:
2385:
2032:
432:
4189:
Each
Lagrange factor has leading coefficient 1, so that the leading coefficient of the H polynomials is the sum of the coefficients. The normalized H polynomials are thus
1061:
6638:
5196:
4925:
3821:
7448:
7291:
6981:{\displaystyle M_{X}(H)=\sum _{m=0}^{n-1}H_{m}X^{m+1}-H_{n-1}\left(X^{n}+\sum _{m=0}^{n-1}a_{m}X^{m}\right)=\sum _{m=1}^{n-1}(H_{m-1}-a_{m}H_{n-1})X^{m}-a_{0}H_{n-1}\,,}
473:
2578:
4917:
3647:
2486:
311:
53:
6442:
6673:
4764:
3181:
The algorithm converges for any distribution of roots, but may fail to find all roots of the polynomial. Furthermore, the convergence is slightly faster than the
1018:{\displaystyle H^{(\lambda +1)}(X)={\frac {1}{X-s_{\lambda }}}\cdot \left(H^{(\lambda )}(X)-{\frac {H^{(\lambda )}(s_{\lambda })}{P(s_{\lambda })}}P(X)\right)\,,}
3841:
5686:{\displaystyle H^{(\lambda )}(X)=P_{1}(X)+O\left(\prod _{\kappa =0}^{\lambda -1}\left|{\frac {\alpha _{1}-s_{\kappa }}{\alpha _{2}-s_{\kappa }}}\right|\right)}
2396:
4024:
7672:
3916:
3199:
2058:
2791:
3549:
240:), one at a time in roughly increasing order of magnitude. After each root is computed, its linear factor is removed from the polynomial. Using this
7257:
The methods have been extensively tested by many people. As predicted they enjoy faster than quadratic convergence for all distributions of zeros.
1484:
7441:
6340:
2188:
Since the left side is a convex function and increases monotonically from zero to infinity, this equation is easy to solve, for instance by
482:
3041:{\displaystyle s_{\lambda +1}=s_{\lambda }-{\frac {P(s_{\lambda })}{{\bar {H}}^{(\lambda +1)}(s_{\lambda })}},\quad \lambda =L,L+1,\dots ,}
7238:. Again the shifts may be viewed as Newton-Raphson iteration on a sequence of rational functions converging to a first degree polynomial.
7646:
6135:
7572:
2042: = 50. This stage is not necessary from theoretical considerations alone, but is useful in practice. It emphasizes in the
270:
320:
7434:
176:
7636:
640:
2733:
446:
polynomials occurs in two variants, an unnormalized variant that allows easy theoretical insights and a normalized variant of
2198:
568:
6059:
7416:
A free downloadable
Windows application using the Jenkins–Traub Method for polynomials with real and complex coefficients
3194:
2391:
polynomial moves towards the cofactor of a single root. During this iteration, the current approximation for the root
7667:
7265:
large; see
Wilkinson, p. 64. The original polynomial was of degree 60 and suffered severe deflation instability.
7234:
There is a surprising connection with the shifted QR algorithm for computing matrix eigenvalues. See Dekker and Traub
3762:
7605:
6549:
5515:{\displaystyle s-{\frac {P(s)}{{\bar {H}}^{(\lambda )}(s)}}=\alpha _{1}+O\left(\ldots \cdot |\alpha _{1}-s|\right).}
5158:{\displaystyle H^{(\lambda )}(X)=P_{1}(X)+O\left(\left|{\frac {\alpha _{1}}{\alpha _{2}}}\right|^{\lambda }\right).}
3858:
6246:
6014:
3051:
6211:
4013:
If all roots are different, then the
Lagrange factors form a basis of the space of polynomials of degree at most
7590:
7534:
7292:
A Three-Stage Variables-Shift Iteration for Polynomial Zeros and Its Relation to Generalized Rayleigh Iteration
2301:
3310:
1954:
7615:
7549:
7493:
7465:
7457:
7303:
Ralston, A. and Rabinowitz, P. (1978), A First Course in Numerical Analysis, 2nd ed., McGraw-Hill, New York.
7209:
262:
32:
2674:
iterations for polynomials of moderate degree, with a doubling strategy for the case of multiple failures.
7539:
7352:
7247:
4883:
holds for almost all iterates, the normalized H polynomials will converge at least geometrically towards
2685:
2253:
1436:
7631:
36:
7365:
7251:
3112:
7402:
Wilkinson, J. H. (1963), Rounding Errors in Algebraic Processes, Prentice Hall, Englewood Cliffs, N.J.
7610:
7585:
2357:
2004:
7595:
7524:
7516:
3182:
399:
1039:
826:{\displaystyle (X-s_{\lambda })\cdot H^{(\lambda +1)}(X)\equiv H^{(\lambda )}(X){\pmod {P(X)}}\ .}
7261:
6611:
5174:
3843:. Even though Stage 3 is precisely a Newton–Raphson iteration, differentiation is not performed.
3799:
3543:
475:
polynomials that keeps the coefficients in a numerically sensible range. The construction of the
7641:
7562:
7506:
7501:
2189:
449:
7339:
7235:
6132: − 1 or less. The principal idea of this map is to interpret the factorization
2387:. This creates an asymmetry relative to the previous stage which increases the chance that the
7557:
4886:
4876:{\displaystyle |\alpha _{1}-s_{\kappa }|<\min {}_{m=2,3,\dots ,n}|\alpha _{m}-s_{\kappa }|}
3632:
296:
273:
p. 383. The algorithm is similar in spirit to the two-stage algorithm studied by Traub.
7473:
6676:
629:
called shifts. These shifts themselves depend, at least in the third stage, on the previous
317:. The polynomial can then be split into a linear factor and the remaining polynomial factor
7314:
A Class of Globally Convergent Iteration Functions for the Solution of Polynomial Equations
6651:
6325: − 1 as the eigenvector equation for the multiplication with the variable
3752:{\displaystyle {\frac {P(z)}{{\bar {H}}^{\lambda }(z)}}=W^{\lambda }(z)\,LC(H^{\lambda })}
40:
3546:. More precisely, Newton–Raphson is being performed on a sequence of rational functions
3826:
563:
266:
7661:
7580:
7529:
1029:
5034:{\displaystyle |\alpha _{1}|<|\alpha _{2}|=\min {}_{m=2,3,\dots ,n}|\alpha _{m}|}
17:
7478:
6111:
1033:
7378:
2666:{\displaystyle |t_{\lambda }-t_{\lambda -1}|<{\tfrac {1}{2}}\,|t_{\lambda -1}|}
7420:
7246:
The software for the Jenkins–Traub algorithm was published as Jenkins and Traub
4017: − 1. By analysis of the recursion procedure one finds that the
2568:{\displaystyle |t_{\lambda +1}-t_{\lambda }|<{\tfrac {1}{2}}\,|t_{\lambda }|}
162:{\displaystyle P(z)=\sum _{i=0}^{n}a_{i}z^{n-i},\quad a_{0}=1,\quad a_{n}\neq 0}
6539:{\displaystyle 0=(M_{X}-\alpha \cdot id)(H)=((X-\alpha )\cdot H){\bmod {P}}\,,}
7483:
7415:
442:) containing (the linear factors of) all the remaining roots. The sequence of
257:
244:
guarantees that each root is computed only once and that all roots are found.
2046:
polynomials the cofactor(s) (of the linear factor) of the smallest root(s).
1028:
Algorithmically, one would use long division by the linear factor as in the
2483:
is traced. The second stage is terminated as successful if the conditions
7426:
2476:{\displaystyle t_{\lambda }=s-{\frac {P(s)}{{\bar {H}}^{(\lambda )}(s)}}}
1555:{\displaystyle -{\tfrac {H^{(\lambda )}(s_{\lambda })}{P(s_{\lambda })}}}
4182:{\displaystyle H^{(\lambda )}(X)=\sum _{m=1}^{n}\left^{-1}\,P_{m}(X)\ .}
1063:
and obtain the quotients at the same time. With the resulting quotients
7326:
7313:
7223:
7327:
A Three-Stage Algorithm for Real Polynomials Using Quadratic Iteration
7224:
A Three-Stage Algorithm for Real Polynomials Using Quadratic Iteration
4006:{\displaystyle P_{m}(X)={\frac {P(X)-P(\alpha _{m})}{X-\alpha _{m}}}.}
555:{\displaystyle \left(H^{(\lambda )}(z)\right)_{\lambda =0,1,2,\dots }}
3294:{\displaystyle z_{i+1}=z_{i}-{\frac {P(z_{i})}{P^{\prime }(z_{i})}}.}
2181:{\displaystyle R^{n}+|a_{n-1}|\,R^{n-1}+\dots +|a_{1}|\,R=|a_{0}|\,.}
6431: − 1. The eigenvalues of this map are the roots of
637:
polynomials are defined as the solution to the implicit recursion
2884:{\displaystyle s_{L}=t_{L}=s-{\frac {P(s)}{{\bar {H}}^{(L)}(s)}}}
3620:{\displaystyle W^{\lambda }(z)={\frac {P(z)}{H^{\lambda }(z)}}.}
396: − 1 and are supposed to converge to the factor
392:
polynomials is constructed. These polynomials are all of degree
7430:
7250:. The software for the real algorithm was published as Jenkins
46:
This article describes the complex variant. Given a polynomial
6523:
6391:
3542:
is precisely a Newton–Raphson iteration performed on certain
256:
The Jenkins–Traub algorithm calculates all of the roots of a
6011:
giving rise to a higher than quadratic convergence order of
3320:
3264:
677:
169:
with complex coefficients it computes approximations to the
7423:
An SSE-Optimized C++ implementation of the RPOLY algorithm.
1091:
7383:
The History of Numerical Analysis and Scientific Computing
2250:
on the circle of this radius. The sequence of polynomials
248:
research on theory and software for methods of this type.
225:{\displaystyle \alpha _{1},\alpha _{2},\dots ,\alpha _{n}}
2781:{\displaystyle s_{\lambda },\quad \lambda =L,L+1,\dots }
2730:
polynomials are now generated using the variable shifts
6416:{\displaystyle M_{X}(H)=(X\cdot H(X)){\bmod {P}}(X)\,.}
2243:{\displaystyle s=R\cdot \exp(i\,\phi _{\text{random}})}
7379:"William Kahan Oral history interview by Thomas Haigh"
7006:
6427: − 1 to polynomials of degree at most
6070:
3314:
2625:
2533:
1492:
1429:
Since the highest degree coefficient is obtained from
622:{\displaystyle (s_{\lambda })_{\lambda =0,1,2,\dots }}
6994:
6689:
6654:
6614:
6552:
6445:
6343:
6249:
6214:
6138:
6062:
6017:
5699:
5530:
5387:
5204:
5177:
5051:
4928:
4889:
4767:
4195:
4027:
3919:
3861:
3829:
3802:
3765:
3655:
3635:
3552:
3342:
3313:
3202:
3115:
3054:
2897:
2891:
being the last root estimate of the second stage and
2794:
2736:
2688:
2581:
2489:
2399:
2360:
2304:
2256:
2201:
2061:
2007:
1957:
1572:
1487:
1439:
1089:
1042:
839:
707:
643:
571:
485:
452:
402:
323:
299:
179:
56:
6103:{\displaystyle \phi ={\tfrac {1}{2}}(1+{\sqrt {5}})}
3759:
is as close as desired to a first degree polynomial
2038:
is chosen for polynomials of moderate degrees up to
7624:
7571:
7548:
7515:
7492:
7464:
7200:
6980:
6667:
6632:
6600:
6538:
6415:
6313:
6235:
6201:{\displaystyle P(X)=(X-\alpha _{1})\cdot P_{1}(X)}
6200:
6102:
6048:
6003:
5685:
5514:
5373:
5190:
5157:
5033:
4911:
4875:
4746:
4181:
4005:
3893:
3835:
3815:
3788:
3751:
3641:
3619:
3532:
3328:
3293:
3143:
3097:
3040:
2883:
2780:
2722:
2665:
2567:
2475:
2379:
2346:
2290:
2242:
2180:
2026:
1993:
1936:
1554:
1473:
1421:
1055:
1017:
825:
693:
621:
554:
467:
426:
377:
305:
224:
161:
6329:, followed by remainder computation with divisor
269:. A description can also be found in Ralston and
4975:
4804:
7340:The shifted QR algorithm for Hermitian matrices
7236:The shifted QR algorithm for Hermitian matrices
6601:{\displaystyle (X-\alpha )\cdot H)=C\cdot P(X)}
4021:polynomials have the coordinate representation
3336:. In contrast the third-stage of Jenkins–Traub
833:A direct solution to this implicit equation is
3894:{\displaystyle \alpha _{1},\dots ,\alpha _{n}}
7442:
6314:{\displaystyle P_{1}(X)=P(X)/(X-\alpha _{1})}
6049:{\displaystyle \phi ^{2}=1+\phi \approx 2.61}
378:{\displaystyle P(X)=(X-\alpha ){\bar {H}}(X)}
8:
7353:Algorithm 419: Zeros of a Complex Polynomial
7248:Algorithm 419: Zeros of a Complex Polynomial
6128:-dimensional space of polynomials of degree
3098:{\displaystyle {\bar {H}}^{(\lambda +1)}(z)}
29:Jenkins–Traub algorithm for polynomial zeros
6236:{\displaystyle \alpha _{1}\in \mathbb {C} }
7449:
7435:
7427:
7230:A connection with the shifted QR algorithm
2354:, is generated with the fixed shift value
1295:
1291:
293:, the aim is to compute the smallest root
7366:Algorithm 493: Zeros of a Real Polynomial
7252:Algorithm 493: Zeros of a Real Polynomial
7194:
7174:
7110:
7073:
7036:
7001:
6993:
6974:
6962:
6952:
6939:
6920:
6910:
6891:
6872:
6861:
6843:
6833:
6817:
6806:
6793:
6772:
6753:
6743:
6727:
6716:
6694:
6688:
6659:
6653:
6613:
6551:
6532:
6526:
6522:
6459:
6444:
6409:
6394:
6390:
6348:
6342:
6302:
6284:
6254:
6248:
6229:
6228:
6219:
6213:
6183:
6167:
6137:
6119:Interpretation as inverse power iteration
6090:
6069:
6061:
6022:
6016:
5988:
5982:
5969:
5960:
5952:
5947:
5940:
5927:
5918:
5915:
5899:
5886:
5874:
5861:
5854:
5838:
5827:
5806:
5787:
5762:
5751:
5750:
5732:
5723:
5704:
5698:
5665:
5652:
5640:
5627:
5620:
5604:
5593:
5563:
5535:
5529:
5499:
5487:
5478:
5455:
5424:
5413:
5412:
5394:
5386:
5354:
5335:
5317:
5310:
5296:
5284:
5274:
5268:
5237:
5209:
5203:
5182:
5176:
5142:
5130:
5120:
5114:
5084:
5056:
5050:
5026:
5020:
5011:
4981:
4979:
4967:
4961:
4952:
4944:
4938:
4929:
4927:
4894:
4888:
4868:
4862:
4849:
4840:
4810:
4808:
4796:
4790:
4777:
4768:
4766:
4721:
4708:
4696:
4683:
4676:
4664:
4653:
4638:
4627:
4600:
4595:
4581:
4568:
4556:
4543:
4536:
4524:
4513:
4498:
4487:
4465:
4458:
4443:
4429:
4416:
4397:
4386:
4370:
4359:
4338:
4333:
4324:
4310:
4297:
4278:
4267:
4251:
4240:
4233:
4209:
4198:
4197:
4194:
4158:
4153:
4144:
4130:
4117:
4098:
4087:
4071:
4060:
4032:
4026:
3991:
3970:
3942:
3924:
3918:
3885:
3866:
3860:
3828:
3807:
3801:
3785:
3776:
3764:
3740:
3726:
3711:
3686:
3675:
3674:
3656:
3654:
3634:
3596:
3575:
3557:
3551:
3518:
3497:
3479:
3466:
3459:
3450:
3431:
3412:
3401:
3400:
3388:
3375:
3366:
3347:
3341:
3319:
3312:
3276:
3263:
3248:
3235:
3226:
3207:
3201:
3120:
3114:
3068:
3057:
3056:
3053:
2992:
2967:
2956:
2955:
2943:
2930:
2921:
2902:
2896:
2857:
2846:
2845:
2827:
2812:
2799:
2793:
2741:
2735:
2693:
2687:
2658:
2646:
2637:
2636:
2624:
2616:
2604:
2591:
2582:
2580:
2560:
2554:
2545:
2544:
2532:
2524:
2518:
2499:
2490:
2488:
2449:
2438:
2437:
2419:
2404:
2398:
2365:
2359:
2347:{\displaystyle \lambda =M,M+1,\dots ,L-1}
2303:
2261:
2255:
2231:
2226:
2200:
2174:
2169:
2163:
2154:
2147:
2142:
2136:
2127:
2106:
2101:
2096:
2084:
2075:
2066:
2060:
2012:
2006:
1956:
1926:
1900:
1889:
1888:
1875:
1856:
1845:
1844:
1832:
1819:
1787:
1771:
1735:
1719:
1700:
1685:
1672:
1640:
1624:
1590:
1579:
1578:
1573:
1571:
1539:
1518:
1499:
1491:
1486:
1444:
1438:
1392:
1371:
1352:
1345:
1300:
1274:
1255:
1239:
1183:
1166:
1144:
1093:
1088:
1047:
1041:
1011:
982:
961:
942:
935:
911:
890:
874:
844:
838:
792:
771:
737:
721:
706:
694:{\displaystyle H^{(0)}(z)=P^{\prime }(z)}
676:
648:
642:
589:
579:
570:
522:
496:
484:
454:
453:
451:
404:
403:
401:
355:
354:
322:
298:
216:
197:
184:
178:
147:
127:
107:
97:
87:
76:
55:
7351:Jenkins, M. A. and Traub, J. F. (1972),
7325:Jenkins, M. A. and Traub, J. F. (1970),
7290:Jenkins, M. A. and Traub, J. F. (1970),
6648:). In the monomial basis the linear map
6439:), since the eigenvector equation reads
6423:This maps polynomials of degree at most
3329:{\displaystyle \scriptstyle P^{\prime }}
1562:. If this is divided out the normalized
1025:where the polynomial division is exact.
31:is a fast globally convergent iterative
7338:Dekker, T. J. and Traub, J. F. (1971),
7274:
6988:the resulting transformation matrix is
5041:one gets the asymptotic estimates for
1994:{\displaystyle \lambda =0,1,\dots ,M-1}
7329:, SIAM J. Numer. Anal., 7(4), 545–566.
3909:). The so-called Lagrange factors of
388:To that end, a sequence of so-called
281:Starting with the current polynomial
7:
7342:, Lin. Algebra Appl., 4(2), 137–154.
3151:divided by its leading coefficient.
7673:Polynomial factorization algorithms
3189:What gives the algorithm its power?
2723:{\displaystyle H^{(\lambda +1)}(X)}
2678:Stage three: variable-shift process
2291:{\displaystyle H^{(\lambda +1)}(z)}
1474:{\displaystyle H^{(\lambda +1)}(X)}
1079:) as intermediate results the next
800:
3913:are the cofactors of these roots,
25:
7385:. Philadelphia, PA. 8 August 2005
3144:{\displaystyle H^{(\lambda )}(z)}
7647:Sidi's generalized secant method
3789:{\displaystyle z-\alpha _{1},\,}
7637:Inverse quadratic interpolation
7316:, Math. Comp., 20(93), 113–138.
6321:the remaining factor of degree
3163:It can be shown that, provided
3007:
2750:
1036:to evaluate the polynomials at
793:
142:
122:
6932:
6884:
6706:
6700:
6627:
6615:
6595:
6589:
6574:
6565:
6553:
6519:
6510:
6498:
6495:
6489:
6483:
6480:
6452:
6406:
6400:
6387:
6384:
6378:
6366:
6360:
6354:
6308:
6289:
6281:
6275:
6266:
6260:
6195:
6189:
6173:
6154:
6148:
6142:
6097:
6081:
5989:
5961:
5948:
5919:
5793:
5780:
5775:
5763:
5756:
5744:
5738:
5575:
5569:
5553:
5547:
5542:
5536:
5500:
5479:
5442:
5436:
5431:
5425:
5418:
5406:
5400:
5249:
5243:
5227:
5221:
5216:
5210:
5096:
5090:
5074:
5068:
5063:
5057:
5027:
5012:
4968:
4953:
4945:
4930:
4906:
4900:
4869:
4841:
4797:
4769:
4612:
4606:
4477:
4471:
4435:
4409:
4350:
4344:
4316:
4290:
4227:
4221:
4216:
4210:
4203:
4170:
4164:
4136:
4110:
4050:
4044:
4039:
4033:
3976:
3963:
3954:
3948:
3936:
3930:
3746:
3733:
3723:
3717:
3698:
3692:
3680:
3668:
3662:
3608:
3602:
3587:
3581:
3569:
3563:
3524:
3511:
3504:
3490:
3485:
3472:
3437:
3424:
3406:
3394:
3381:
3282:
3269:
3254:
3241:
3174:always converges to a root of
3167:is chosen sufficiently large,
3138:
3132:
3127:
3121:
3092:
3086:
3081:
3069:
3062:
2998:
2985:
2980:
2968:
2961:
2949:
2936:
2875:
2869:
2864:
2858:
2851:
2839:
2833:
2717:
2711:
2706:
2694:
2659:
2638:
2617:
2583:
2561:
2546:
2525:
2491:
2467:
2461:
2456:
2450:
2443:
2431:
2425:
2380:{\displaystyle s_{\lambda }=s}
2285:
2279:
2274:
2262:
2237:
2220:
2170:
2155:
2143:
2128:
2097:
2076:
2050:Stage two: fixed-shift process
2027:{\displaystyle s_{\lambda }=0}
1918:
1912:
1907:
1901:
1894:
1881:
1868:
1863:
1857:
1850:
1838:
1825:
1813:
1807:
1753:
1747:
1742:
1736:
1725:
1712:
1707:
1701:
1691:
1678:
1666:
1660:
1614:
1608:
1603:
1591:
1584:
1545:
1532:
1524:
1511:
1506:
1500:
1468:
1462:
1457:
1445:
1413:
1407:
1398:
1385:
1377:
1364:
1359:
1353:
1339:
1333:
1324:
1318:
1313:
1301:
1292:
1280:
1267:
1262:
1256:
1245:
1226:
1220:
1214:
1201:
1195:
1190:
1184:
1172:
1159:
1150:
1131:
1125:
1119:
1106:
1100:
1003:
997:
988:
975:
967:
954:
949:
943:
929:
923:
918:
912:
868:
862:
857:
845:
813:
810:
804:
794:
789:
783:
778:
772:
761:
755:
750:
738:
727:
708:
688:
682:
666:
660:
655:
649:
586:
572:
514:
508:
503:
497:
459:
421:
415:
409:
372:
366:
360:
351:
339:
333:
327:
66:
60:
1:
3303:The iteration uses the given
1433:, the leading coefficient of
427:{\displaystyle {\bar {H}}(X)}
1056:{\displaystyle s_{\lambda }}
35:method published in 1970 by
7294:, Numer. Math. 14, 252–263.
6633:{\displaystyle (X-\alpha )}
5191:{\displaystyle \alpha _{1}}
3816:{\displaystyle \alpha _{1}}
1947:Stage one: no-shift process
562:is guided by a sequence of
7689:
7466:Bracketing (no derivative)
4922:Under the condition that
1083:polynomial is obtained as
468:{\displaystyle {\bar {H}}}
4912:{\displaystyle P_{1}(X)}
3642:{\displaystyle \lambda }
3195:Newton–Raphson iteration
2788:which are generated by
7616:Splitting circle method
7601:Jenkins–Traub algorithm
7458:Root-finding algorithms
7368:, ACM TOMS, 1, 178–189.
7364:Jenkins, M. A. (1975),
7355:, Comm. ACM, 15, 97–99.
7210:inverse power iteration
3823:is one of the zeros of
306:{\displaystyle \alpha }
263:inverse power iteration
33:polynomial root-finding
7606:Lehmer–Schur algorithm
7202:
6982:
6883:
6828:
6738:
6669:
6640:is a linear factor of
6634:
6602:
6540:
6417:
6315:
6237:
6202:
6104:
6050:
6005:
5849:
5687:
5615:
5516:
5375:
5192:
5159:
5035:
4913:
4877:
4748:
4675:
4643:
4535:
4503:
4408:
4375:
4289:
4256:
4183:
4109:
4076:
4007:
3895:
3837:
3817:
3790:
3753:
3643:
3621:
3534:
3330:
3295:
3145:
3099:
3042:
2885:
2782:
2724:
2667:
2569:
2477:
2381:
2348:
2292:
2244:
2182:
2028:
1995:
1938:
1556:
1475:
1423:
1057:
1019:
827:
695:
623:
556:
469:
428:
379:
307:
277:Root-finding procedure
226:
163:
92:
7632:Fixed-point iteration
7312:Traub, J. F. (1966),
7203:
6983:
6857:
6802:
6712:
6670:
6668:{\displaystyle M_{X}}
6635:
6603:
6541:
6418:
6316:
6238:
6203:
6105:
6051:
6006:
5823:
5688:
5589:
5517:
5376:
5193:
5160:
5036:
4914:
4878:
4749:
4649:
4623:
4509:
4483:
4382:
4355:
4263:
4236:
4184:
4083:
4056:
4008:
3896:
3838:
3818:
3791:
3754:
3644:
3622:
3535:
3331:
3296:
3183:quadratic convergence
3146:
3100:
3043:
2886:
2783:
2725:
2668:
2570:
2478:
2382:
2349:
2293:
2245:
2183:
2029:
1996:
1939:
1557:
1476:
1424:
1058:
1020:
828:
696:
624:
557:
470:
429:
380:
308:
227:
164:
72:
7591:Durand–Kerner method
7535:Newton–Krylov method
7242:Software and testing
6992:
6687:
6675:is represented by a
6652:
6612:
6550:
6443:
6341:
6247:
6212:
6136:
6060:
6015:
5697:
5528:
5385:
5202:
5175:
5049:
4926:
4887:
4765:
4193:
4025:
3917:
3859:
3827:
3800:
3763:
3653:
3649:sufficiently large,
3633:
3550:
3340:
3311:
3200:
3113:
3109:polynomial, that is
3052:
2895:
2792:
2734:
2686:
2579:
2487:
2397:
2358:
2302:
2254:
2199:
2059:
2005:
1955:
1570:
1485:
1437:
1087:
1040:
837:
705:
641:
569:
483:
450:
400:
321:
297:
177:
54:
18:Jenkins-Traub method
7540:Steffensen's method
7208:To this matrix the
6546:which implies that
5171:is close enough to
7668:Numerical analysis
7573:Polynomial methods
7198:
7188:
6978:
6679:of the polynomial
6665:
6630:
6598:
6536:
6413:
6311:
6233:
6198:
6100:
6079:
6046:
6001:
5683:
5512:
5371:
5188:
5155:
5031:
4909:
4873:
4757:Convergence orders
4744:
4179:
4003:
3891:
3833:
3813:
3786:
3749:
3639:
3617:
3544:rational functions
3530:
3326:
3325:
3291:
3141:
3105:is the normalized
3095:
3038:
2881:
2778:
2720:
2663:
2634:
2565:
2542:
2473:
2377:
2344:
2288:
2240:
2178:
2024:
1991:
1934:
1932:
1552:
1550:
1471:
1419:
1285:
1053:
1015:
823:
691:
619:
552:
465:
424:
375:
303:
265:. See Jenkins and
222:
159:
37:Michael A. Jenkins
7655:
7654:
7611:Laguerre's method
7586:Bairstow's method
7217:Real coefficients
7213:remain the same.
6095:
6078:
5994:
5906:
5797:
5759:
5672:
5524:and for stage 3:
5446:
5421:
5348:
5290:
5136:
4761:If the condition
4740:
4736:
4728:
4588:
4453:
4206:
4175:
3998:
3836:{\displaystyle P}
3702:
3683:
3612:
3528:
3441:
3409:
3286:
3193:Compare with the
3065:
3002:
2964:
2879:
2854:
2633:
2541:
2471:
2446:
2234:
1897:
1885:
1853:
1794:
1729:
1647:
1587:
1549:
1402:
992:
897:
819:
633:polynomials. The
462:
412:
363:
16:(Redirected from
7680:
7596:Graeffe's method
7525:Broyden's method
7474:Bisection method
7451:
7444:
7437:
7428:
7403:
7400:
7394:
7393:
7391:
7390:
7375:
7369:
7362:
7356:
7349:
7343:
7336:
7330:
7323:
7317:
7310:
7304:
7301:
7295:
7288:
7282:
7279:
7207:
7205:
7204:
7199:
7193:
7192:
7185:
7184:
7115:
7114:
7078:
7077:
7041:
7040:
6987:
6985:
6984:
6979:
6973:
6972:
6957:
6956:
6944:
6943:
6931:
6930:
6915:
6914:
6902:
6901:
6882:
6871:
6853:
6849:
6848:
6847:
6838:
6837:
6827:
6816:
6798:
6797:
6783:
6782:
6764:
6763:
6748:
6747:
6737:
6726:
6699:
6698:
6677:companion matrix
6674:
6672:
6671:
6666:
6664:
6663:
6639:
6637:
6636:
6631:
6607:
6605:
6604:
6599:
6545:
6543:
6542:
6537:
6531:
6530:
6464:
6463:
6422:
6420:
6419:
6414:
6399:
6398:
6353:
6352:
6320:
6318:
6317:
6312:
6307:
6306:
6288:
6259:
6258:
6242:
6240:
6239:
6234:
6232:
6224:
6223:
6207:
6205:
6204:
6199:
6188:
6187:
6172:
6171:
6109:
6107:
6106:
6101:
6096:
6091:
6080:
6071:
6055:
6053:
6052:
6047:
6027:
6026:
6010:
6008:
6007:
6002:
6000:
5996:
5995:
5993:
5992:
5987:
5986:
5974:
5973:
5964:
5958:
5957:
5956:
5951:
5945:
5944:
5932:
5931:
5922:
5916:
5911:
5907:
5905:
5904:
5903:
5891:
5890:
5880:
5879:
5878:
5866:
5865:
5855:
5848:
5837:
5811:
5810:
5798:
5796:
5792:
5791:
5779:
5778:
5761:
5760:
5752:
5747:
5733:
5728:
5727:
5715:
5714:
5692:
5690:
5689:
5684:
5682:
5678:
5677:
5673:
5671:
5670:
5669:
5657:
5656:
5646:
5645:
5644:
5632:
5631:
5621:
5614:
5603:
5568:
5567:
5546:
5545:
5521:
5519:
5518:
5513:
5508:
5504:
5503:
5492:
5491:
5482:
5460:
5459:
5447:
5445:
5435:
5434:
5423:
5422:
5414:
5409:
5395:
5380:
5378:
5377:
5372:
5370:
5366:
5365:
5364:
5353:
5349:
5347:
5340:
5339:
5329:
5322:
5321:
5311:
5301:
5300:
5295:
5291:
5289:
5288:
5279:
5278:
5269:
5242:
5241:
5220:
5219:
5197:
5195:
5194:
5189:
5187:
5186:
5167:for stage 2, if
5164:
5162:
5161:
5156:
5151:
5147:
5146:
5141:
5137:
5135:
5134:
5125:
5124:
5115:
5089:
5088:
5067:
5066:
5040:
5038:
5037:
5032:
5030:
5025:
5024:
5015:
5010:
5009:
4980:
4971:
4966:
4965:
4956:
4948:
4943:
4942:
4933:
4918:
4916:
4915:
4910:
4899:
4898:
4882:
4880:
4879:
4874:
4872:
4867:
4866:
4854:
4853:
4844:
4839:
4838:
4809:
4800:
4795:
4794:
4782:
4781:
4772:
4753:
4751:
4750:
4745:
4738:
4737:
4735:
4734:
4730:
4729:
4727:
4726:
4725:
4713:
4712:
4702:
4701:
4700:
4688:
4687:
4677:
4674:
4663:
4642:
4637:
4615:
4605:
4604:
4594:
4590:
4589:
4587:
4586:
4585:
4573:
4572:
4562:
4561:
4560:
4548:
4547:
4537:
4534:
4523:
4502:
4497:
4470:
4469:
4459:
4454:
4452:
4451:
4450:
4442:
4438:
4434:
4433:
4421:
4420:
4407:
4396:
4374:
4369:
4353:
4343:
4342:
4332:
4331:
4323:
4319:
4315:
4314:
4302:
4301:
4288:
4277:
4255:
4250:
4234:
4220:
4219:
4208:
4207:
4199:
4188:
4186:
4185:
4180:
4173:
4163:
4162:
4152:
4151:
4143:
4139:
4135:
4134:
4122:
4121:
4108:
4097:
4075:
4070:
4043:
4042:
4012:
4010:
4009:
4004:
3999:
3997:
3996:
3995:
3979:
3975:
3974:
3943:
3929:
3928:
3901:be the roots of
3900:
3898:
3897:
3892:
3890:
3889:
3871:
3870:
3847:Analysis of the
3842:
3840:
3839:
3834:
3822:
3820:
3819:
3814:
3812:
3811:
3795:
3793:
3792:
3787:
3781:
3780:
3758:
3756:
3755:
3750:
3745:
3744:
3716:
3715:
3703:
3701:
3691:
3690:
3685:
3684:
3676:
3671:
3657:
3648:
3646:
3645:
3640:
3626:
3624:
3623:
3618:
3613:
3611:
3601:
3600:
3590:
3576:
3562:
3561:
3539:
3537:
3536:
3531:
3529:
3527:
3523:
3522:
3510:
3502:
3501:
3488:
3484:
3483:
3471:
3470:
3460:
3455:
3454:
3442:
3440:
3436:
3435:
3423:
3422:
3411:
3410:
3402:
3397:
3393:
3392:
3376:
3371:
3370:
3358:
3357:
3335:
3333:
3332:
3327:
3324:
3323:
3300:
3298:
3297:
3292:
3287:
3285:
3281:
3280:
3268:
3267:
3257:
3253:
3252:
3236:
3231:
3230:
3218:
3217:
3150:
3148:
3147:
3142:
3131:
3130:
3104:
3102:
3101:
3096:
3085:
3084:
3067:
3066:
3058:
3047:
3045:
3044:
3039:
3003:
3001:
2997:
2996:
2984:
2983:
2966:
2965:
2957:
2952:
2948:
2947:
2931:
2926:
2925:
2913:
2912:
2890:
2888:
2887:
2882:
2880:
2878:
2868:
2867:
2856:
2855:
2847:
2842:
2828:
2817:
2816:
2804:
2803:
2787:
2785:
2784:
2779:
2746:
2745:
2729:
2727:
2726:
2721:
2710:
2709:
2672:
2670:
2669:
2664:
2662:
2657:
2656:
2641:
2635:
2626:
2620:
2615:
2614:
2596:
2595:
2586:
2574:
2572:
2571:
2566:
2564:
2559:
2558:
2549:
2543:
2534:
2528:
2523:
2522:
2510:
2509:
2494:
2482:
2480:
2479:
2474:
2472:
2470:
2460:
2459:
2448:
2447:
2439:
2434:
2420:
2409:
2408:
2386:
2384:
2383:
2378:
2370:
2369:
2353:
2351:
2350:
2345:
2297:
2295:
2294:
2289:
2278:
2277:
2249:
2247:
2246:
2241:
2236:
2235:
2232:
2187:
2185:
2184:
2179:
2173:
2168:
2167:
2158:
2146:
2141:
2140:
2131:
2117:
2116:
2100:
2095:
2094:
2079:
2071:
2070:
2033:
2031:
2030:
2025:
2017:
2016:
2000:
1998:
1997:
1992:
1943:
1941:
1940:
1935:
1933:
1925:
1921:
1911:
1910:
1899:
1898:
1890:
1886:
1884:
1880:
1879:
1867:
1866:
1855:
1854:
1846:
1841:
1837:
1836:
1820:
1795:
1793:
1792:
1791:
1772:
1764:
1760:
1756:
1746:
1745:
1730:
1728:
1724:
1723:
1711:
1710:
1694:
1690:
1689:
1673:
1648:
1646:
1645:
1644:
1625:
1607:
1606:
1589:
1588:
1580:
1561:
1559:
1558:
1553:
1551:
1548:
1544:
1543:
1527:
1523:
1522:
1510:
1509:
1493:
1480:
1478:
1477:
1472:
1461:
1460:
1428:
1426:
1425:
1420:
1403:
1401:
1397:
1396:
1380:
1376:
1375:
1363:
1362:
1346:
1317:
1316:
1290:
1286:
1279:
1278:
1266:
1265:
1244:
1243:
1194:
1193:
1171:
1170:
1149:
1148:
1062:
1060:
1059:
1054:
1052:
1051:
1024:
1022:
1021:
1016:
1010:
1006:
993:
991:
987:
986:
970:
966:
965:
953:
952:
936:
922:
921:
898:
896:
895:
894:
875:
861:
860:
832:
830:
829:
824:
817:
816:
782:
781:
754:
753:
726:
725:
700:
698:
697:
692:
681:
680:
659:
658:
628:
626:
625:
620:
618:
617:
584:
583:
561:
559:
558:
553:
551:
550:
521:
517:
507:
506:
474:
472:
471:
466:
464:
463:
455:
433:
431:
430:
425:
414:
413:
405:
384:
382:
381:
376:
365:
364:
356:
312:
310:
309:
304:
231:
229:
228:
223:
221:
220:
202:
201:
189:
188:
168:
166:
165:
160:
152:
151:
132:
131:
118:
117:
102:
101:
91:
86:
21:
7688:
7687:
7683:
7682:
7681:
7679:
7678:
7677:
7658:
7657:
7656:
7651:
7642:Muller's method
7620:
7567:
7563:Ridders' method
7544:
7511:
7507:Halley's method
7502:Newton's method
7488:
7460:
7455:
7412:
7407:
7406:
7401:
7397:
7388:
7386:
7377:
7376:
7372:
7363:
7359:
7350:
7346:
7337:
7333:
7324:
7320:
7311:
7307:
7302:
7298:
7289:
7285:
7280:
7276:
7271:
7244:
7232:
7219:
7187:
7186:
7170:
7165:
7160:
7155:
7150:
7144:
7143:
7138:
7133:
7128:
7123:
7117:
7116:
7106:
7101:
7096:
7091:
7086:
7080:
7079:
7069:
7064:
7059:
7054:
7049:
7043:
7042:
7032:
7027:
7022:
7017:
7012:
7002:
6990:
6989:
6958:
6948:
6935:
6916:
6906:
6887:
6839:
6829:
6789:
6788:
6784:
6768:
6749:
6739:
6690:
6685:
6684:
6655:
6650:
6649:
6610:
6609:
6548:
6547:
6455:
6441:
6440:
6344:
6339:
6338:
6298:
6250:
6245:
6244:
6215:
6210:
6209:
6179:
6163:
6134:
6133:
6121:
6058:
6057:
6018:
6013:
6012:
5978:
5965:
5959:
5946:
5936:
5923:
5917:
5895:
5882:
5881:
5870:
5857:
5856:
5850:
5822:
5818:
5802:
5783:
5749:
5748:
5734:
5719:
5700:
5695:
5694:
5661:
5648:
5647:
5636:
5623:
5622:
5616:
5588:
5584:
5559:
5531:
5526:
5525:
5483:
5471:
5467:
5451:
5411:
5410:
5396:
5383:
5382:
5331:
5330:
5313:
5312:
5306:
5305:
5280:
5270:
5264:
5263:
5262:
5258:
5233:
5205:
5200:
5199:
5178:
5173:
5172:
5126:
5116:
5110:
5109:
5105:
5080:
5052:
5047:
5046:
5016:
4978:
4957:
4934:
4924:
4923:
4890:
4885:
4884:
4858:
4845:
4807:
4786:
4773:
4763:
4762:
4759:
4717:
4704:
4703:
4692:
4679:
4678:
4648:
4644:
4616:
4596:
4577:
4564:
4563:
4552:
4539:
4538:
4508:
4504:
4461:
4460:
4425:
4412:
4381:
4377:
4376:
4354:
4334:
4306:
4293:
4262:
4258:
4257:
4235:
4196:
4191:
4190:
4154:
4126:
4113:
4082:
4078:
4077:
4028:
4023:
4022:
3987:
3980:
3966:
3944:
3920:
3915:
3914:
3881:
3862:
3857:
3856:
3853:
3825:
3824:
3803:
3798:
3797:
3772:
3761:
3760:
3736:
3707:
3673:
3672:
3658:
3651:
3650:
3631:
3630:
3592:
3591:
3577:
3553:
3548:
3547:
3514:
3503:
3493:
3489:
3475:
3462:
3461:
3446:
3427:
3399:
3398:
3384:
3377:
3362:
3343:
3338:
3337:
3315:
3309:
3308:
3272:
3259:
3258:
3244:
3237:
3222:
3203:
3198:
3197:
3191:
3173:
3161:
3116:
3111:
3110:
3055:
3050:
3049:
2988:
2954:
2953:
2939:
2932:
2917:
2898:
2893:
2892:
2844:
2843:
2829:
2808:
2795:
2790:
2789:
2737:
2732:
2731:
2689:
2684:
2683:
2680:
2642:
2600:
2587:
2577:
2576:
2550:
2514:
2495:
2485:
2484:
2436:
2435:
2421:
2400:
2395:
2394:
2361:
2356:
2355:
2300:
2299:
2257:
2252:
2251:
2227:
2197:
2196:
2190:Newton's method
2159:
2132:
2102:
2080:
2062:
2057:
2056:
2052:
2008:
2003:
2002:
1953:
1952:
1949:
1931:
1930:
1887:
1871:
1843:
1842:
1828:
1821:
1803:
1799:
1783:
1776:
1762:
1761:
1731:
1715:
1696:
1695:
1681:
1674:
1656:
1652:
1636:
1629:
1617:
1577:
1568:
1567:
1535:
1528:
1514:
1495:
1494:
1483:
1482:
1440:
1435:
1434:
1388:
1381:
1367:
1348:
1347:
1296:
1284:
1283:
1270:
1251:
1235:
1204:
1179:
1176:
1175:
1162:
1140:
1109:
1090:
1085:
1084:
1043:
1038:
1037:
978:
971:
957:
938:
937:
907:
906:
902:
886:
879:
840:
835:
834:
767:
733:
717:
703:
702:
672:
644:
639:
638:
585:
575:
567:
566:
564:complex numbers
492:
491:
487:
486:
481:
480:
448:
447:
398:
397:
319:
318:
295:
294:
279:
254:
212:
193:
180:
175:
174:
143:
123:
103:
93:
52:
51:
41:Joseph F. Traub
23:
22:
15:
12:
11:
5:
7686:
7684:
7676:
7675:
7670:
7660:
7659:
7653:
7652:
7650:
7649:
7644:
7639:
7634:
7628:
7626:
7622:
7621:
7619:
7618:
7613:
7608:
7603:
7598:
7593:
7588:
7583:
7577:
7575:
7569:
7568:
7566:
7565:
7560:
7558:Brent's method
7554:
7552:
7550:Hybrid methods
7546:
7545:
7543:
7542:
7537:
7532:
7527:
7521:
7519:
7513:
7512:
7510:
7509:
7504:
7498:
7496:
7490:
7489:
7487:
7486:
7481:
7476:
7470:
7468:
7462:
7461:
7456:
7454:
7453:
7446:
7439:
7431:
7425:
7424:
7418:
7411:
7410:External links
7408:
7405:
7404:
7395:
7370:
7357:
7344:
7331:
7318:
7305:
7296:
7283:
7273:
7272:
7270:
7267:
7243:
7240:
7231:
7228:
7218:
7215:
7197:
7191:
7183:
7180:
7177:
7173:
7169:
7166:
7164:
7161:
7159:
7156:
7154:
7151:
7149:
7146:
7145:
7142:
7139:
7137:
7134:
7132:
7129:
7127:
7124:
7122:
7119:
7118:
7113:
7109:
7105:
7102:
7100:
7097:
7095:
7092:
7090:
7087:
7085:
7082:
7081:
7076:
7072:
7068:
7065:
7063:
7060:
7058:
7055:
7053:
7050:
7048:
7045:
7044:
7039:
7035:
7031:
7028:
7026:
7023:
7021:
7018:
7016:
7013:
7011:
7008:
7007:
7005:
7000:
6997:
6977:
6971:
6968:
6965:
6961:
6955:
6951:
6947:
6942:
6938:
6934:
6929:
6926:
6923:
6919:
6913:
6909:
6905:
6900:
6897:
6894:
6890:
6886:
6881:
6878:
6875:
6870:
6867:
6864:
6860:
6856:
6852:
6846:
6842:
6836:
6832:
6826:
6823:
6820:
6815:
6812:
6809:
6805:
6801:
6796:
6792:
6787:
6781:
6778:
6775:
6771:
6767:
6762:
6759:
6756:
6752:
6746:
6742:
6736:
6733:
6730:
6725:
6722:
6719:
6715:
6711:
6708:
6705:
6702:
6697:
6693:
6662:
6658:
6629:
6626:
6623:
6620:
6617:
6597:
6594:
6591:
6588:
6585:
6582:
6579:
6576:
6573:
6570:
6567:
6564:
6561:
6558:
6555:
6535:
6529:
6525:
6521:
6518:
6515:
6512:
6509:
6506:
6503:
6500:
6497:
6494:
6491:
6488:
6485:
6482:
6479:
6476:
6473:
6470:
6467:
6462:
6458:
6454:
6451:
6448:
6412:
6408:
6405:
6402:
6397:
6393:
6389:
6386:
6383:
6380:
6377:
6374:
6371:
6368:
6365:
6362:
6359:
6356:
6351:
6347:
6310:
6305:
6301:
6297:
6294:
6291:
6287:
6283:
6280:
6277:
6274:
6271:
6268:
6265:
6262:
6257:
6253:
6231:
6227:
6222:
6218:
6197:
6194:
6191:
6186:
6182:
6178:
6175:
6170:
6166:
6162:
6159:
6156:
6153:
6150:
6147:
6144:
6141:
6120:
6117:
6116:
6115:
6099:
6094:
6089:
6086:
6083:
6077:
6074:
6068:
6065:
6045:
6042:
6039:
6036:
6033:
6030:
6025:
6021:
5999:
5991:
5985:
5981:
5977:
5972:
5968:
5963:
5955:
5950:
5943:
5939:
5935:
5930:
5926:
5921:
5914:
5910:
5902:
5898:
5894:
5889:
5885:
5877:
5873:
5869:
5864:
5860:
5853:
5847:
5844:
5841:
5836:
5833:
5830:
5826:
5821:
5817:
5814:
5809:
5805:
5801:
5795:
5790:
5786:
5782:
5777:
5774:
5771:
5768:
5765:
5758:
5755:
5746:
5743:
5740:
5737:
5731:
5726:
5722:
5718:
5713:
5710:
5707:
5703:
5681:
5676:
5668:
5664:
5660:
5655:
5651:
5643:
5639:
5635:
5630:
5626:
5619:
5613:
5610:
5607:
5602:
5599:
5596:
5592:
5587:
5583:
5580:
5577:
5574:
5571:
5566:
5562:
5558:
5555:
5552:
5549:
5544:
5541:
5538:
5534:
5522:
5511:
5507:
5502:
5498:
5495:
5490:
5486:
5481:
5477:
5474:
5470:
5466:
5463:
5458:
5454:
5450:
5444:
5441:
5438:
5433:
5430:
5427:
5420:
5417:
5408:
5405:
5402:
5399:
5393:
5390:
5369:
5363:
5360:
5357:
5352:
5346:
5343:
5338:
5334:
5328:
5325:
5320:
5316:
5309:
5304:
5299:
5294:
5287:
5283:
5277:
5273:
5267:
5261:
5257:
5254:
5251:
5248:
5245:
5240:
5236:
5232:
5229:
5226:
5223:
5218:
5215:
5212:
5208:
5185:
5181:
5165:
5154:
5150:
5145:
5140:
5133:
5129:
5123:
5119:
5113:
5108:
5104:
5101:
5098:
5095:
5092:
5087:
5083:
5079:
5076:
5073:
5070:
5065:
5062:
5059:
5055:
5029:
5023:
5019:
5014:
5008:
5005:
5002:
4999:
4996:
4993:
4990:
4987:
4984:
4977:
4974:
4970:
4964:
4960:
4955:
4951:
4947:
4941:
4937:
4932:
4908:
4905:
4902:
4897:
4893:
4871:
4865:
4861:
4857:
4852:
4848:
4843:
4837:
4834:
4831:
4828:
4825:
4822:
4819:
4816:
4813:
4806:
4803:
4799:
4793:
4789:
4785:
4780:
4776:
4771:
4758:
4755:
4743:
4733:
4724:
4720:
4716:
4711:
4707:
4699:
4695:
4691:
4686:
4682:
4673:
4670:
4667:
4662:
4659:
4656:
4652:
4647:
4641:
4636:
4633:
4630:
4626:
4622:
4619:
4614:
4611:
4608:
4603:
4599:
4593:
4584:
4580:
4576:
4571:
4567:
4559:
4555:
4551:
4546:
4542:
4533:
4530:
4527:
4522:
4519:
4516:
4512:
4507:
4501:
4496:
4493:
4490:
4486:
4482:
4479:
4476:
4473:
4468:
4464:
4457:
4449:
4446:
4441:
4437:
4432:
4428:
4424:
4419:
4415:
4411:
4406:
4403:
4400:
4395:
4392:
4389:
4385:
4380:
4373:
4368:
4365:
4362:
4358:
4352:
4349:
4346:
4341:
4337:
4330:
4327:
4322:
4318:
4313:
4309:
4305:
4300:
4296:
4292:
4287:
4284:
4281:
4276:
4273:
4270:
4266:
4261:
4254:
4249:
4246:
4243:
4239:
4232:
4229:
4226:
4223:
4218:
4215:
4212:
4205:
4202:
4178:
4172:
4169:
4166:
4161:
4157:
4150:
4147:
4142:
4138:
4133:
4129:
4125:
4120:
4116:
4112:
4107:
4104:
4101:
4096:
4093:
4090:
4086:
4081:
4074:
4069:
4066:
4063:
4059:
4055:
4052:
4049:
4046:
4041:
4038:
4035:
4031:
4002:
3994:
3990:
3986:
3983:
3978:
3973:
3969:
3965:
3962:
3959:
3956:
3953:
3950:
3947:
3941:
3938:
3935:
3932:
3927:
3923:
3888:
3884:
3880:
3877:
3874:
3869:
3865:
3852:
3845:
3832:
3810:
3806:
3784:
3779:
3775:
3771:
3768:
3748:
3743:
3739:
3735:
3732:
3729:
3725:
3722:
3719:
3714:
3710:
3706:
3700:
3697:
3694:
3689:
3682:
3679:
3670:
3667:
3664:
3661:
3638:
3616:
3610:
3607:
3604:
3599:
3595:
3589:
3586:
3583:
3580:
3574:
3571:
3568:
3565:
3560:
3556:
3526:
3521:
3517:
3513:
3509:
3506:
3500:
3496:
3492:
3487:
3482:
3478:
3474:
3469:
3465:
3458:
3453:
3449:
3445:
3439:
3434:
3430:
3426:
3421:
3418:
3415:
3408:
3405:
3396:
3391:
3387:
3383:
3380:
3374:
3369:
3365:
3361:
3356:
3353:
3350:
3346:
3322:
3318:
3290:
3284:
3279:
3275:
3271:
3266:
3262:
3256:
3251:
3247:
3243:
3240:
3234:
3229:
3225:
3221:
3216:
3213:
3210:
3206:
3190:
3187:
3171:
3160:
3157:
3140:
3137:
3134:
3129:
3126:
3123:
3119:
3094:
3091:
3088:
3083:
3080:
3077:
3074:
3071:
3064:
3061:
3037:
3034:
3031:
3028:
3025:
3022:
3019:
3016:
3013:
3010:
3006:
3000:
2995:
2991:
2987:
2982:
2979:
2976:
2973:
2970:
2963:
2960:
2951:
2946:
2942:
2938:
2935:
2929:
2924:
2920:
2916:
2911:
2908:
2905:
2901:
2877:
2874:
2871:
2866:
2863:
2860:
2853:
2850:
2841:
2838:
2835:
2832:
2826:
2823:
2820:
2815:
2811:
2807:
2802:
2798:
2777:
2774:
2771:
2768:
2765:
2762:
2759:
2756:
2753:
2749:
2744:
2740:
2719:
2716:
2713:
2708:
2705:
2702:
2699:
2696:
2692:
2679:
2676:
2661:
2655:
2652:
2649:
2645:
2640:
2632:
2629:
2623:
2619:
2613:
2610:
2607:
2603:
2599:
2594:
2590:
2585:
2563:
2557:
2553:
2548:
2540:
2537:
2531:
2527:
2521:
2517:
2513:
2508:
2505:
2502:
2498:
2493:
2469:
2466:
2463:
2458:
2455:
2452:
2445:
2442:
2433:
2430:
2427:
2424:
2418:
2415:
2412:
2407:
2403:
2376:
2373:
2368:
2364:
2343:
2340:
2337:
2334:
2331:
2328:
2325:
2322:
2319:
2316:
2313:
2310:
2307:
2287:
2284:
2281:
2276:
2273:
2270:
2267:
2264:
2260:
2239:
2230:
2225:
2222:
2219:
2216:
2213:
2210:
2207:
2204:
2177:
2172:
2166:
2162:
2157:
2153:
2150:
2145:
2139:
2135:
2130:
2126:
2123:
2120:
2115:
2112:
2109:
2105:
2099:
2093:
2090:
2087:
2083:
2078:
2074:
2069:
2065:
2051:
2048:
2023:
2020:
2015:
2011:
1990:
1987:
1984:
1981:
1978:
1975:
1972:
1969:
1966:
1963:
1960:
1948:
1945:
1929:
1924:
1920:
1917:
1914:
1909:
1906:
1903:
1896:
1893:
1883:
1878:
1874:
1870:
1865:
1862:
1859:
1852:
1849:
1840:
1835:
1831:
1827:
1824:
1818:
1815:
1812:
1809:
1806:
1802:
1798:
1790:
1786:
1782:
1779:
1775:
1770:
1767:
1765:
1763:
1759:
1755:
1752:
1749:
1744:
1741:
1738:
1734:
1727:
1722:
1718:
1714:
1709:
1706:
1703:
1699:
1693:
1688:
1684:
1680:
1677:
1671:
1668:
1665:
1662:
1659:
1655:
1651:
1643:
1639:
1635:
1632:
1628:
1623:
1620:
1618:
1616:
1613:
1610:
1605:
1602:
1599:
1596:
1593:
1586:
1583:
1576:
1575:
1566:polynomial is
1547:
1542:
1538:
1534:
1531:
1526:
1521:
1517:
1513:
1508:
1505:
1502:
1498:
1490:
1470:
1467:
1464:
1459:
1456:
1453:
1450:
1447:
1443:
1418:
1415:
1412:
1409:
1406:
1400:
1395:
1391:
1387:
1384:
1379:
1374:
1370:
1366:
1361:
1358:
1355:
1351:
1344:
1341:
1338:
1335:
1332:
1329:
1326:
1323:
1320:
1315:
1312:
1309:
1306:
1303:
1299:
1294:
1289:
1282:
1277:
1273:
1269:
1264:
1261:
1258:
1254:
1250:
1247:
1242:
1238:
1234:
1231:
1228:
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1205:
1203:
1200:
1197:
1192:
1189:
1186:
1182:
1178:
1177:
1174:
1169:
1165:
1161:
1158:
1155:
1152:
1147:
1143:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1118:
1115:
1112:
1110:
1108:
1105:
1102:
1099:
1096:
1095:
1092:
1050:
1046:
1014:
1009:
1005:
1002:
999:
996:
990:
985:
981:
977:
974:
969:
964:
960:
956:
951:
948:
945:
941:
934:
931:
928:
925:
920:
917:
914:
910:
905:
901:
893:
889:
885:
882:
878:
873:
870:
867:
864:
859:
856:
853:
850:
847:
843:
822:
815:
812:
809:
806:
803:
799:
796:
791:
788:
785:
780:
777:
774:
770:
766:
763:
760:
757:
752:
749:
746:
743:
740:
736:
732:
729:
724:
720:
716:
713:
710:
690:
687:
684:
679:
675:
671:
668:
665:
662:
657:
654:
651:
647:
616:
613:
610:
607:
604:
601:
598:
595:
592:
588:
582:
578:
574:
549:
546:
543:
540:
537:
534:
531:
528:
525:
520:
516:
513:
510:
505:
502:
499:
495:
490:
461:
458:
423:
420:
417:
411:
408:
374:
371:
368:
362:
359:
353:
350:
347:
344:
341:
338:
335:
332:
329:
326:
302:
278:
275:
253:
250:
219:
215:
211:
208:
205:
200:
196:
192:
187:
183:
158:
155:
150:
146:
141:
138:
135:
130:
126:
121:
116:
113:
110:
106:
100:
96:
90:
85:
82:
79:
75:
71:
68:
65:
62:
59:
24:
14:
13:
10:
9:
6:
4:
3:
2:
7685:
7674:
7671:
7669:
7666:
7665:
7663:
7648:
7645:
7643:
7640:
7638:
7635:
7633:
7630:
7629:
7627:
7625:Other methods
7623:
7617:
7614:
7612:
7609:
7607:
7604:
7602:
7599:
7597:
7594:
7592:
7589:
7587:
7584:
7582:
7581:Aberth method
7579:
7578:
7576:
7574:
7570:
7564:
7561:
7559:
7556:
7555:
7553:
7551:
7547:
7541:
7538:
7536:
7533:
7531:
7530:Secant method
7528:
7526:
7523:
7522:
7520:
7518:
7514:
7508:
7505:
7503:
7500:
7499:
7497:
7495:
7491:
7485:
7482:
7480:
7477:
7475:
7472:
7471:
7469:
7467:
7463:
7459:
7452:
7447:
7445:
7440:
7438:
7433:
7432:
7429:
7422:
7419:
7417:
7414:
7413:
7409:
7399:
7396:
7384:
7380:
7374:
7371:
7367:
7361:
7358:
7354:
7348:
7345:
7341:
7335:
7332:
7328:
7322:
7319:
7315:
7309:
7306:
7300:
7297:
7293:
7287:
7284:
7278:
7275:
7268:
7266:
7263:
7258:
7255:
7253:
7249:
7241:
7239:
7237:
7229:
7227:
7225:
7216:
7214:
7211:
7195:
7189:
7181:
7178:
7175:
7171:
7167:
7162:
7157:
7152:
7147:
7140:
7135:
7130:
7125:
7120:
7111:
7107:
7103:
7098:
7093:
7088:
7083:
7074:
7070:
7066:
7061:
7056:
7051:
7046:
7037:
7033:
7029:
7024:
7019:
7014:
7009:
7003:
6998:
6995:
6975:
6969:
6966:
6963:
6959:
6953:
6949:
6945:
6940:
6936:
6927:
6924:
6921:
6917:
6911:
6907:
6903:
6898:
6895:
6892:
6888:
6879:
6876:
6873:
6868:
6865:
6862:
6858:
6854:
6850:
6844:
6840:
6834:
6830:
6824:
6821:
6818:
6813:
6810:
6807:
6803:
6799:
6794:
6790:
6785:
6779:
6776:
6773:
6769:
6765:
6760:
6757:
6754:
6750:
6744:
6740:
6734:
6731:
6728:
6723:
6720:
6717:
6713:
6709:
6703:
6695:
6691:
6682:
6678:
6660:
6656:
6647:
6643:
6624:
6621:
6618:
6592:
6586:
6583:
6580:
6577:
6571:
6568:
6562:
6559:
6556:
6533:
6527:
6516:
6513:
6507:
6504:
6501:
6492:
6486:
6477:
6474:
6471:
6468:
6465:
6460:
6456:
6449:
6446:
6438:
6434:
6430:
6426:
6410:
6403:
6395:
6381:
6375:
6372:
6369:
6363:
6357:
6349:
6345:
6336:
6332:
6328:
6324:
6303:
6299:
6295:
6292:
6285:
6278:
6272:
6269:
6263:
6255:
6251:
6225:
6220:
6216:
6192:
6184:
6180:
6176:
6168:
6164:
6160:
6157:
6151:
6145:
6139:
6131:
6127:
6118:
6113:
6092:
6087:
6084:
6075:
6072:
6066:
6063:
6043:
6040:
6037:
6034:
6031:
6028:
6023:
6019:
5997:
5983:
5979:
5975:
5970:
5966:
5953:
5941:
5937:
5933:
5928:
5924:
5912:
5908:
5900:
5896:
5892:
5887:
5883:
5875:
5871:
5867:
5862:
5858:
5851:
5845:
5842:
5839:
5834:
5831:
5828:
5824:
5819:
5815:
5812:
5807:
5803:
5799:
5788:
5784:
5772:
5769:
5766:
5753:
5741:
5735:
5729:
5724:
5720:
5716:
5711:
5708:
5705:
5701:
5679:
5674:
5666:
5662:
5658:
5653:
5649:
5641:
5637:
5633:
5628:
5624:
5617:
5611:
5608:
5605:
5600:
5597:
5594:
5590:
5585:
5581:
5578:
5572:
5564:
5560:
5556:
5550:
5539:
5532:
5523:
5509:
5505:
5496:
5493:
5488:
5484:
5475:
5472:
5468:
5464:
5461:
5456:
5452:
5448:
5439:
5428:
5415:
5403:
5397:
5391:
5388:
5367:
5361:
5358:
5355:
5350:
5344:
5341:
5336:
5332:
5326:
5323:
5318:
5314:
5307:
5302:
5297:
5292:
5285:
5281:
5275:
5271:
5265:
5259:
5255:
5252:
5246:
5238:
5234:
5230:
5224:
5213:
5206:
5183:
5179:
5170:
5166:
5152:
5148:
5143:
5138:
5131:
5127:
5121:
5117:
5111:
5106:
5102:
5099:
5093:
5085:
5081:
5077:
5071:
5060:
5053:
5044:
5043:
5042:
5021:
5017:
5006:
5003:
5000:
4997:
4994:
4991:
4988:
4985:
4982:
4972:
4962:
4958:
4949:
4939:
4935:
4920:
4903:
4895:
4891:
4863:
4859:
4855:
4850:
4846:
4835:
4832:
4829:
4826:
4823:
4820:
4817:
4814:
4811:
4801:
4791:
4787:
4783:
4778:
4774:
4756:
4754:
4741:
4731:
4722:
4718:
4714:
4709:
4705:
4697:
4693:
4689:
4684:
4680:
4671:
4668:
4665:
4660:
4657:
4654:
4650:
4645:
4639:
4634:
4631:
4628:
4624:
4620:
4617:
4609:
4601:
4597:
4591:
4582:
4578:
4574:
4569:
4565:
4557:
4553:
4549:
4544:
4540:
4531:
4528:
4525:
4520:
4517:
4514:
4510:
4505:
4499:
4494:
4491:
4488:
4484:
4480:
4474:
4466:
4462:
4455:
4447:
4444:
4439:
4430:
4426:
4422:
4417:
4413:
4404:
4401:
4398:
4393:
4390:
4387:
4383:
4378:
4371:
4366:
4363:
4360:
4356:
4347:
4339:
4335:
4328:
4325:
4320:
4311:
4307:
4303:
4298:
4294:
4285:
4282:
4279:
4274:
4271:
4268:
4264:
4259:
4252:
4247:
4244:
4241:
4237:
4230:
4224:
4213:
4200:
4176:
4167:
4159:
4155:
4148:
4145:
4140:
4131:
4127:
4123:
4118:
4114:
4105:
4102:
4099:
4094:
4091:
4088:
4084:
4079:
4072:
4067:
4064:
4061:
4057:
4053:
4047:
4036:
4029:
4020:
4016:
4000:
3992:
3988:
3984:
3981:
3971:
3967:
3960:
3957:
3951:
3945:
3939:
3933:
3925:
3921:
3912:
3908:
3904:
3886:
3882:
3878:
3875:
3872:
3867:
3863:
3850:
3846:
3844:
3830:
3808:
3804:
3782:
3777:
3773:
3769:
3766:
3741:
3737:
3730:
3727:
3720:
3712:
3708:
3704:
3695:
3687:
3677:
3665:
3659:
3636:
3627:
3614:
3605:
3597:
3593:
3584:
3578:
3572:
3566:
3558:
3554:
3545:
3540:
3519:
3515:
3507:
3498:
3494:
3480:
3476:
3467:
3463:
3456:
3451:
3447:
3443:
3432:
3428:
3419:
3416:
3413:
3403:
3389:
3385:
3378:
3372:
3367:
3363:
3359:
3354:
3351:
3348:
3344:
3316:
3306:
3301:
3288:
3277:
3273:
3260:
3249:
3245:
3238:
3232:
3227:
3223:
3219:
3214:
3211:
3208:
3204:
3196:
3188:
3186:
3184:
3179:
3177:
3170:
3166:
3158:
3156:
3152:
3135:
3124:
3117:
3108:
3089:
3078:
3075:
3072:
3059:
3035:
3032:
3029:
3026:
3023:
3020:
3017:
3014:
3011:
3008:
3004:
2993:
2989:
2977:
2974:
2971:
2958:
2944:
2940:
2933:
2927:
2922:
2918:
2914:
2909:
2906:
2903:
2899:
2872:
2861:
2848:
2836:
2830:
2824:
2821:
2818:
2813:
2809:
2805:
2800:
2796:
2775:
2772:
2769:
2766:
2763:
2760:
2757:
2754:
2751:
2747:
2742:
2738:
2714:
2703:
2700:
2697:
2690:
2677:
2675:
2653:
2650:
2647:
2643:
2630:
2627:
2621:
2611:
2608:
2605:
2601:
2597:
2592:
2588:
2555:
2551:
2538:
2535:
2529:
2519:
2515:
2511:
2506:
2503:
2500:
2496:
2464:
2453:
2440:
2428:
2422:
2416:
2413:
2410:
2405:
2401:
2392:
2390:
2374:
2371:
2366:
2362:
2341:
2338:
2335:
2332:
2329:
2326:
2323:
2320:
2317:
2314:
2311:
2308:
2305:
2282:
2271:
2268:
2265:
2258:
2228:
2223:
2217:
2214:
2211:
2208:
2205:
2202:
2193:
2191:
2175:
2164:
2160:
2151:
2148:
2137:
2133:
2124:
2121:
2118:
2113:
2110:
2107:
2103:
2091:
2088:
2085:
2081:
2072:
2067:
2063:
2049:
2047:
2045:
2041:
2037:
2021:
2018:
2013:
2009:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1946:
1944:
1927:
1922:
1915:
1904:
1891:
1876:
1872:
1860:
1847:
1833:
1829:
1822:
1816:
1810:
1804:
1800:
1796:
1788:
1784:
1780:
1777:
1773:
1768:
1766:
1757:
1750:
1739:
1732:
1720:
1716:
1704:
1697:
1686:
1682:
1675:
1669:
1663:
1657:
1653:
1649:
1641:
1637:
1633:
1630:
1626:
1621:
1619:
1611:
1600:
1597:
1594:
1581:
1565:
1540:
1536:
1529:
1519:
1515:
1503:
1496:
1488:
1465:
1454:
1451:
1448:
1441:
1432:
1416:
1410:
1404:
1393:
1389:
1382:
1372:
1368:
1356:
1349:
1342:
1336:
1330:
1327:
1321:
1310:
1307:
1304:
1297:
1287:
1275:
1271:
1259:
1252:
1248:
1240:
1236:
1232:
1229:
1223:
1217:
1211:
1208:
1206:
1198:
1187:
1180:
1167:
1163:
1156:
1153:
1145:
1141:
1137:
1134:
1128:
1122:
1116:
1113:
1111:
1103:
1097:
1082:
1078:
1074:
1070:
1066:
1048:
1044:
1035:
1031:
1030:Horner scheme
1026:
1012:
1007:
1000:
994:
983:
979:
972:
962:
958:
946:
939:
932:
926:
915:
908:
903:
899:
891:
887:
883:
880:
876:
871:
865:
854:
851:
848:
841:
820:
807:
801:
797:
786:
775:
768:
764:
758:
747:
744:
741:
734:
730:
722:
718:
714:
711:
685:
673:
669:
663:
652:
645:
636:
632:
614:
611:
608:
605:
602:
599:
596:
593:
590:
580:
576:
565:
547:
544:
541:
538:
535:
532:
529:
526:
523:
518:
511:
500:
493:
488:
478:
456:
445:
441:
437:
418:
406:
395:
391:
386:
369:
357:
348:
345:
342:
336:
330:
324:
316:
300:
292:
288:
284:
276:
274:
272:
268:
264:
259:
251:
249:
245:
243:
239:
235:
217:
213:
209:
206:
203:
198:
194:
190:
185:
181:
172:
156:
153:
148:
144:
139:
136:
133:
128:
124:
119:
114:
111:
108:
104:
98:
94:
88:
83:
80:
77:
73:
69:
63:
57:
49:
44:
42:
38:
34:
30:
19:
7600:
7517:Quasi-Newton
7479:Regula falsi
7398:
7387:. Retrieved
7382:
7373:
7360:
7347:
7334:
7321:
7308:
7299:
7286:
7277:
7259:
7256:
7245:
7233:
7220:
6680:
6645:
6641:
6436:
6432:
6428:
6424:
6334:
6330:
6326:
6322:
6208:with a root
6129:
6125:
6122:
6112:golden ratio
5168:
4921:
4760:
4018:
4014:
3910:
3906:
3902:
3854:
3848:
3628:
3541:
3304:
3302:
3192:
3180:
3175:
3168:
3164:
3162:
3153:
3106:
2681:
2393:
2388:
2194:
2053:
2043:
2039:
2035:
1950:
1563:
1430:
1080:
1076:
1072:
1068:
1064:
1034:Ruffini rule
1027:
634:
630:
479:polynomials
476:
443:
439:
435:
393:
389:
387:
314:
290:
289:) of degree
286:
282:
280:
255:
246:
241:
237:
233:
170:
47:
45:
28:
26:
7494:Householder
6608:, that is,
3851:polynomials
3159:Convergence
2195:Now choose
7662:Categories
7484:ITP method
7389:2021-12-03
7269:References
2034:. Usually
271:Rabinowitz
258:polynomial
7262:Wilkinson
7179:−
7168:−
7158:…
7141:⋮
7136:⋮
7131:⋱
7126:⋮
7121:⋮
7104:−
7094:…
7067:−
7057:…
7030:−
7020:…
6967:−
6946:−
6925:−
6904:−
6896:−
6877:−
6859:∑
6822:−
6804:∑
6777:−
6766:−
6732:−
6714:∑
6625:α
6622:−
6584:⋅
6569:⋅
6563:α
6560:−
6514:⋅
6508:α
6505:−
6472:⋅
6469:α
6466:−
6373:⋅
6300:α
6296:−
6226:∈
6217:α
6177:⋅
6165:α
6161:−
6064:ϕ
6041:≈
6038:ϕ
6020:ϕ
5984:λ
5976:−
5967:α
5942:λ
5934:−
5925:α
5913:⋅
5901:κ
5893:−
5884:α
5876:κ
5868:−
5859:α
5843:−
5840:λ
5829:κ
5825:∏
5804:α
5789:λ
5767:λ
5757:¯
5730:−
5725:λ
5706:λ
5667:κ
5659:−
5650:α
5642:κ
5634:−
5625:α
5609:−
5606:λ
5595:κ
5591:∏
5540:λ
5494:−
5485:α
5476:⋅
5473:…
5453:α
5429:λ
5419:¯
5392:−
5359:−
5356:λ
5342:−
5333:α
5324:−
5315:α
5303:⋅
5282:α
5272:α
5214:λ
5180:α
5144:λ
5128:α
5118:α
5061:λ
5045:stage 1:
5018:α
5001:…
4959:α
4936:α
4864:κ
4856:−
4847:α
4830:…
4792:κ
4784:−
4775:α
4723:κ
4715:−
4706:α
4698:κ
4690:−
4681:α
4669:−
4666:λ
4655:κ
4651:∏
4625:∑
4583:κ
4575:−
4566:α
4558:κ
4550:−
4541:α
4529:−
4526:λ
4515:κ
4511:∏
4485:∑
4445:−
4431:κ
4423:−
4414:α
4402:−
4399:λ
4388:κ
4384:∏
4357:∑
4326:−
4312:κ
4304:−
4295:α
4283:−
4280:λ
4269:κ
4265:∏
4238:∑
4214:λ
4204:¯
4146:−
4132:κ
4124:−
4115:α
4103:−
4100:λ
4089:κ
4085:∏
4058:∑
4037:λ
3989:α
3985:−
3968:α
3958:−
3883:α
3876:…
3864:α
3805:α
3774:α
3770:−
3742:λ
3713:λ
3688:λ
3681:¯
3637:λ
3598:λ
3559:λ
3520:λ
3499:λ
3481:λ
3468:λ
3457:−
3452:λ
3433:λ
3414:λ
3407:¯
3390:λ
3373:−
3368:λ
3349:λ
3321:′
3265:′
3233:−
3125:λ
3073:λ
3063:¯
3033:…
3009:λ
2994:λ
2972:λ
2962:¯
2945:λ
2928:−
2923:λ
2904:λ
2852:¯
2825:−
2776:…
2752:λ
2743:λ
2698:λ
2651:−
2648:λ
2609:−
2606:λ
2598:−
2593:λ
2556:λ
2520:λ
2512:−
2501:λ
2454:λ
2444:¯
2417:−
2406:λ
2367:λ
2339:−
2330:…
2306:λ
2266:λ
2229:ϕ
2218:
2212:⋅
2122:⋯
2111:−
2089:−
2014:λ
1986:−
1977:…
1959:λ
1905:λ
1895:¯
1877:λ
1861:λ
1851:¯
1834:λ
1817:−
1797:⋅
1789:λ
1781:−
1740:λ
1721:λ
1705:λ
1687:λ
1670:−
1650:⋅
1642:λ
1634:−
1595:λ
1585:¯
1541:λ
1520:λ
1504:λ
1489:−
1449:λ
1394:λ
1373:λ
1357:λ
1343:−
1305:λ
1293:⟹
1276:λ
1260:λ
1241:λ
1233:−
1224:⋅
1188:λ
1168:λ
1146:λ
1138:−
1129:⋅
1049:λ
984:λ
963:λ
947:λ
933:−
916:λ
900:⋅
892:λ
884:−
849:λ
776:λ
765:≡
742:λ
731:⋅
723:λ
715:−
678:′
615:…
591:λ
581:λ
548:…
524:λ
501:λ
460:¯
410:¯
361:¯
349:α
346:−
301:α
242:deflation
214:α
207:…
195:α
182:α
154:≠
112:−
74:∑
6056:, where
3508:′
252:Overview
7421:RPoly++
6110:is the
4739:
4174:
3796:where
3048:where
2233:random
1071:) and
818:
173:zeros
6683:, as
267:Traub
6337:),
6243:and
6044:2.61
5693:and
5381:and
4950:<
4802:<
3911:P(X)
3855:Let
3629:For
3307:and
2682:The
2622:<
2575:and
2530:<
2001:set
1951:For
1431:P(X)
701:and
315:P(x)
39:and
27:The
6524:mod
6392:mod
4976:min
4805:min
2215:exp
2036:M=5
1481:is
1032:or
798:mod
434:of
313:of
232:of
7664::
7381:.
7254:.
5198::
4919:.
3178:.
2298:,
2192:.
50:,
7450:e
7443:t
7436:v
7392:.
7196:.
7190:)
7182:1
7176:n
7172:a
7163:1
7153:0
7148:0
7112:2
7108:a
7099:0
7089:1
7084:0
7075:1
7071:a
7062:0
7052:0
7047:1
7038:0
7034:a
7025:0
7015:0
7010:0
7004:(
6999:=
6996:A
6976:,
6970:1
6964:n
6960:H
6954:0
6950:a
6941:m
6937:X
6933:)
6928:1
6922:n
6918:H
6912:m
6908:a
6899:1
6893:m
6889:H
6885:(
6880:1
6874:n
6869:1
6866:=
6863:m
6855:=
6851:)
6845:m
6841:X
6835:m
6831:a
6825:1
6819:n
6814:0
6811:=
6808:m
6800:+
6795:n
6791:X
6786:(
6780:1
6774:n
6770:H
6761:1
6758:+
6755:m
6751:X
6745:m
6741:H
6735:1
6729:n
6724:0
6721:=
6718:m
6710:=
6707:)
6704:H
6701:(
6696:X
6692:M
6681:P
6661:X
6657:M
6646:X
6644:(
6642:P
6628:)
6619:X
6616:(
6596:)
6593:X
6590:(
6587:P
6581:C
6578:=
6575:)
6572:H
6566:)
6557:X
6554:(
6534:,
6528:P
6520:)
6517:H
6511:)
6502:X
6499:(
6496:(
6493:=
6490:)
6487:H
6484:(
6481:)
6478:d
6475:i
6461:X
6457:M
6453:(
6450:=
6447:0
6437:X
6435:(
6433:P
6429:n
6425:n
6411:.
6407:)
6404:X
6401:(
6396:P
6388:)
6385:)
6382:X
6379:(
6376:H
6370:X
6367:(
6364:=
6361:)
6358:H
6355:(
6350:X
6346:M
6335:X
6333:(
6331:P
6327:X
6323:n
6309:)
6304:1
6293:X
6290:(
6286:/
6282:)
6279:X
6276:(
6273:P
6270:=
6267:)
6264:X
6261:(
6256:1
6252:P
6230:C
6221:1
6196:)
6193:X
6190:(
6185:1
6181:P
6174:)
6169:1
6158:X
6155:(
6152:=
6149:)
6146:X
6143:(
6140:P
6130:n
6126:n
6114:.
6098:)
6093:5
6088:+
6085:1
6082:(
6076:2
6073:1
6067:=
6035:+
6032:1
6029:=
6024:2
5998:)
5990:|
5980:s
5971:2
5962:|
5954:2
5949:|
5938:s
5929:1
5920:|
5909:|
5897:s
5888:2
5872:s
5863:1
5852:|
5846:1
5835:0
5832:=
5820:(
5816:O
5813:+
5808:1
5800:=
5794:)
5785:s
5781:(
5776:)
5773:1
5770:+
5764:(
5754:H
5745:)
5742:s
5739:(
5736:P
5721:s
5717:=
5712:1
5709:+
5702:s
5680:)
5675:|
5663:s
5654:2
5638:s
5629:1
5618:|
5612:1
5601:0
5598:=
5586:(
5582:O
5579:+
5576:)
5573:X
5570:(
5565:1
5561:P
5557:=
5554:)
5551:X
5548:(
5543:)
5537:(
5533:H
5510:.
5506:)
5501:|
5497:s
5489:1
5480:|
5469:(
5465:O
5462:+
5457:1
5449:=
5443:)
5440:s
5437:(
5432:)
5426:(
5416:H
5407:)
5404:s
5401:(
5398:P
5389:s
5368:)
5362:M
5351:|
5345:s
5337:2
5327:s
5319:1
5308:|
5298:M
5293:|
5286:2
5276:1
5266:|
5260:(
5256:O
5253:+
5250:)
5247:X
5244:(
5239:1
5235:P
5231:=
5228:)
5225:X
5222:(
5217:)
5211:(
5207:H
5184:1
5169:s
5153:.
5149:)
5139:|
5132:2
5122:1
5112:|
5107:(
5103:O
5100:+
5097:)
5094:X
5091:(
5086:1
5082:P
5078:=
5075:)
5072:X
5069:(
5064:)
5058:(
5054:H
5028:|
5022:m
5013:|
5007:n
5004:,
4998:,
4995:3
4992:,
4989:2
4986:=
4983:m
4973:=
4969:|
4963:2
4954:|
4946:|
4940:1
4931:|
4907:)
4904:X
4901:(
4896:1
4892:P
4870:|
4860:s
4851:m
4842:|
4836:n
4833:,
4827:,
4824:3
4821:,
4818:2
4815:=
4812:m
4798:|
4788:s
4779:1
4770:|
4742:.
4732:]
4719:s
4710:m
4694:s
4685:1
4672:1
4661:0
4658:=
4646:[
4640:n
4635:1
4632:=
4629:m
4621:+
4618:1
4613:)
4610:X
4607:(
4602:m
4598:P
4592:]
4579:s
4570:m
4554:s
4545:1
4532:1
4521:0
4518:=
4506:[
4500:n
4495:2
4492:=
4489:m
4481:+
4478:)
4475:X
4472:(
4467:1
4463:P
4456:=
4448:1
4440:]
4436:)
4427:s
4418:m
4410:(
4405:1
4394:0
4391:=
4379:[
4372:n
4367:1
4364:=
4361:m
4351:)
4348:X
4345:(
4340:m
4336:P
4329:1
4321:]
4317:)
4308:s
4299:m
4291:(
4286:1
4275:0
4272:=
4260:[
4253:n
4248:1
4245:=
4242:m
4231:=
4228:)
4225:X
4222:(
4217:)
4211:(
4201:H
4177:.
4171:)
4168:X
4165:(
4160:m
4156:P
4149:1
4141:]
4137:)
4128:s
4119:m
4111:(
4106:1
4095:0
4092:=
4080:[
4073:n
4068:1
4065:=
4062:m
4054:=
4051:)
4048:X
4045:(
4040:)
4034:(
4030:H
4019:H
4015:n
4001:.
3993:m
3982:X
3977:)
3972:m
3964:(
3961:P
3955:)
3952:X
3949:(
3946:P
3940:=
3937:)
3934:X
3931:(
3926:m
3922:P
3907:X
3905:(
3903:P
3887:n
3879:,
3873:,
3868:1
3849:H
3831:P
3809:1
3783:,
3778:1
3767:z
3747:)
3738:H
3734:(
3731:C
3728:L
3724:)
3721:z
3718:(
3709:W
3705:=
3699:)
3696:z
3693:(
3678:H
3669:)
3666:z
3663:(
3660:P
3615:.
3609:)
3606:z
3603:(
3594:H
3588:)
3585:z
3582:(
3579:P
3573:=
3570:)
3567:z
3564:(
3555:W
3525:)
3516:s
3512:(
3505:)
3495:W
3491:(
3486:)
3477:s
3473:(
3464:W
3448:s
3444:=
3438:)
3429:s
3425:(
3420:1
3417:+
3404:H
3395:)
3386:s
3382:(
3379:P
3364:s
3360:=
3355:1
3352:+
3345:s
3317:P
3305:P
3289:.
3283:)
3278:i
3274:z
3270:(
3261:P
3255:)
3250:i
3246:z
3242:(
3239:P
3228:i
3224:z
3220:=
3215:1
3212:+
3209:i
3205:z
3176:P
3172:λ
3169:s
3165:L
3139:)
3136:z
3133:(
3128:)
3122:(
3118:H
3107:H
3093:)
3090:z
3087:(
3082:)
3079:1
3076:+
3070:(
3060:H
3036:,
3030:,
3027:1
3024:+
3021:L
3018:,
3015:L
3012:=
3005:,
2999:)
2990:s
2986:(
2981:)
2978:1
2975:+
2969:(
2959:H
2950:)
2941:s
2937:(
2934:P
2919:s
2915:=
2910:1
2907:+
2900:s
2876:)
2873:s
2870:(
2865:)
2862:L
2859:(
2849:H
2840:)
2837:s
2834:(
2831:P
2822:s
2819:=
2814:L
2810:t
2806:=
2801:L
2797:s
2773:,
2770:1
2767:+
2764:L
2761:,
2758:L
2755:=
2748:,
2739:s
2718:)
2715:X
2712:(
2707:)
2704:1
2701:+
2695:(
2691:H
2660:|
2654:1
2644:t
2639:|
2631:2
2628:1
2618:|
2612:1
2602:t
2589:t
2584:|
2562:|
2552:t
2547:|
2539:2
2536:1
2526:|
2516:t
2507:1
2504:+
2497:t
2492:|
2468:)
2465:s
2462:(
2457:)
2451:(
2441:H
2432:)
2429:s
2426:(
2423:P
2414:s
2411:=
2402:t
2389:H
2375:s
2372:=
2363:s
2342:1
2336:L
2333:,
2327:,
2324:1
2321:+
2318:M
2315:,
2312:M
2309:=
2286:)
2283:z
2280:(
2275:)
2272:1
2269:+
2263:(
2259:H
2238:)
2224:i
2221:(
2209:R
2206:=
2203:s
2176:.
2171:|
2165:0
2161:a
2156:|
2152:=
2149:R
2144:|
2138:1
2134:a
2129:|
2125:+
2119:+
2114:1
2108:n
2104:R
2098:|
2092:1
2086:n
2082:a
2077:|
2073:+
2068:n
2064:R
2044:H
2040:n
2022:0
2019:=
2010:s
1989:1
1983:M
1980:,
1974:,
1971:1
1968:,
1965:0
1962:=
1928:.
1923:)
1919:)
1916:X
1913:(
1908:)
1902:(
1892:H
1882:)
1873:s
1869:(
1864:)
1858:(
1848:H
1839:)
1830:s
1826:(
1823:P
1814:)
1811:X
1808:(
1805:P
1801:(
1785:s
1778:X
1774:1
1769:=
1758:)
1754:)
1751:X
1748:(
1743:)
1737:(
1733:H
1726:)
1717:s
1713:(
1708:)
1702:(
1698:H
1692:)
1683:s
1679:(
1676:P
1667:)
1664:X
1661:(
1658:P
1654:(
1638:s
1631:X
1627:1
1622:=
1615:)
1612:X
1609:(
1604:)
1601:1
1598:+
1592:(
1582:H
1564:H
1546:)
1537:s
1533:(
1530:P
1525:)
1516:s
1512:(
1507:)
1501:(
1497:H
1469:)
1466:X
1463:(
1458:)
1455:1
1452:+
1446:(
1442:H
1417:.
1414:)
1411:z
1408:(
1405:p
1399:)
1390:s
1386:(
1383:P
1378:)
1369:s
1365:(
1360:)
1354:(
1350:H
1340:)
1337:z
1334:(
1331:h
1328:=
1325:)
1322:z
1319:(
1314:)
1311:1
1308:+
1302:(
1298:H
1288:}
1281:)
1272:s
1268:(
1263:)
1257:(
1253:H
1249:+
1246:)
1237:s
1230:X
1227:(
1221:)
1218:X
1215:(
1212:h
1209:=
1202:)
1199:X
1196:(
1191:)
1185:(
1181:H
1173:)
1164:s
1160:(
1157:P
1154:+
1151:)
1142:s
1135:X
1132:(
1126:)
1123:X
1120:(
1117:p
1114:=
1107:)
1104:X
1101:(
1098:P
1081:H
1077:X
1075:(
1073:h
1069:X
1067:(
1065:p
1045:s
1013:,
1008:)
1004:)
1001:X
998:(
995:P
989:)
980:s
976:(
973:P
968:)
959:s
955:(
950:)
944:(
940:H
930:)
927:X
924:(
919:)
913:(
909:H
904:(
888:s
881:X
877:1
872:=
869:)
866:X
863:(
858:)
855:1
852:+
846:(
842:H
821:.
814:)
811:)
808:X
805:(
802:P
795:(
790:)
787:X
784:(
779:)
773:(
769:H
762:)
759:X
756:(
751:)
748:1
745:+
739:(
735:H
728:)
719:s
712:X
709:(
689:)
686:z
683:(
674:P
670:=
667:)
664:z
661:(
656:)
653:0
650:(
646:H
635:H
631:H
612:,
609:2
606:,
603:1
600:,
597:0
594:=
587:)
577:s
573:(
545:,
542:2
539:,
536:1
533:,
530:0
527:=
519:)
515:)
512:z
509:(
504:)
498:(
494:H
489:(
477:H
457:H
444:H
440:X
438:(
436:P
422:)
419:X
416:(
407:H
394:n
390:H
373:)
370:X
367:(
358:H
352:)
343:X
340:(
337:=
334:)
331:X
328:(
325:P
291:n
287:X
285:(
283:P
238:z
236:(
234:P
218:n
210:,
204:,
199:2
191:,
186:1
171:n
157:0
149:n
145:a
140:,
137:1
134:=
129:0
125:a
120:,
115:i
109:n
105:z
99:i
95:a
89:n
84:0
81:=
78:i
70:=
67:)
64:z
61:(
58:P
48:P
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.