Jenkins–Traub algorithm: Difference between revisions

Revision as of 22:45, 6 July 2007

Revision as of 15:36, 7 July 2007

Line 1:

The '''Jenkins-Traub algorithm for polynomial zeros''' is a fast globally convergent iterative method. It has been described as ''practically a standard in black-box polynomial root-finders''.

Given a polynomial <math>''P</math>'',

::::<math>P(z)=\sum_{i=0}^na_iz^{n-i}, \quad a_0=1,\quad a_n\ne 0</math>

with complex coefficients compute approximations to the <math> ''n</math>'' zeros <math>\alpha_1,\alpha_1,\dots,\alpha_n</math> of <math>''P''(''z'')</math>.

There is a variation of the Jenkins-Traub algorithm which is faster if the coefficients are real. The Jenkins-Traub algorithm has stimulated considerable research on theory and software for methods of this type.

Line 25:

where <math>\bar H^{(\lambda+1)}(z)</math> is <math>H^{(\lambda)}(z)</math> divided by its leading coefficient.

It can be shown that provided <math>''L</math>'' is chosen sufficiently large ''s''<mathsub>s_{\&lambda};</mathsub> always converges to a zero of <math>''P</math>''. After an approximate zero has been found the degree of <math>''P</math>'' is reduced by one by deflation and the algorithm is performed on the new polynomial until all the zeros have been computed.

The algorithm converges for any distribution of zeros. Furthermore, the convergence is faster than the quadratic convergence of Newton-Raphson iteration.

Line 34:

:<math>z_{i+1}=z_i - \frac{P(z_i)}{P^{\prime}(z_i)}.</math>

The iteration uses the given <math>''P</math>'' and <math>\scriptstyle P^{\prime}</math>. In contrast the third-stage of Jenkins-Traub

:<math>s_{\lambda+1}=s_\lambda- \frac{P(s_\lambda)}{\bar H^{(\lambda+1)}(s_\lambda)}</math>

Line 52:

where <math>\alpha_1</math> is one of the zeros of <math>P</math>. Even though Stage 3 is precisely a Newton-Raphson iteration, differentiation is not performed.

==Real Coefficientscoefficients==

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 [http://links.jstor.org/sici?sici=0036-1429%28197012%297%3A4%3C545%3AATAFRP%3E2.0.CO%3B2-J A Three-Stage Algorithm for Real Polynomials Using Quadratic Iteration].<ref>Jenkins, M. A. and Traub, J. F. (1970), [http://links.jstor.org/sici?sici=0036-1429%28197012%297%3A4%3C545%3AATAFRP%3E2.0.CO%3B2-J A Three-Stage Algorithm for Real Polynomials Using Quadratic Iteration], SIAM J. Numer. Anal., 7(4), 545-566.</ref> 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.

==A Connectionconnection with the Shiftedshifted QR Algorithmalgorithm==

There is a surprising connection with the shifted QR algorithm for computing matrix eigenvalues. See Dekker and Traub [http://www.sciencedirect.com/science?_ob=ArticleListURL&_method=list&_ArticleListID=596538089&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=6062eb1bdb37e355f732a580c6faee1a The shifted QR algorithm for Hermitian matrices].<ref>Dekker, T. J. and Traub, J. F. (1971), [http://www.sciencedirect.com/science?_ob=ArticleListURL&_method=list&_ArticleListID=596538089&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=6062eb1bdb37e355f732a580c6faee1a The shifted QR algorithm for Hermitian matrices], Lin. Algebra Appl., 4(2), 137-154.</ref> Again the shifts may be viewed as Newton-Raphson iteration on a sequence of rational functions converging to a first degree polynomial.

==Software and Testingtesting==

The software for the Jenkins-traub algorithm was published as Jenkins and Traub [http://portal.acm.org/citation.cfm?id=361262&coll=portal&dl=ACM Algorithm 419: Zeros of a Complex Polynomial].<ref> Jenkins, M. A. and Traub, J. F. (1972), [http://portal.acm.org/citation.cfm?id=361262&coll=portal&dl=ACM Algorithm 419: Zeros of a Complex Polynomial], Comm. ACM, 15, 97-99.</ref> The software for the real algorithm was published as Jenkins [http://portal.acm.org/citation.cfm?id=355643&coll=ACM&dl=ACM Algorithm 493: Zeros of a Real Polynomial].<ref>Jenkins, M. A. (1975), [http://portal.acm.org/citation.cfm?id=355643&coll=ACM&dl=ACM Algorithm 493: Zeros of a Real Polynomial], ACM TOMS, 1, 178-189.</ref>