Jenkins–Traub algorithm: Difference between revisions

Revision as of 14:15, 6 July 2007

Revision as of 16:38, 6 July 2007

Line 1:

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

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

Line 5:

::::<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 considerably research on theory and software for methods of this type.

==Overview==

The Jenkins-traub algorithm is a three-stage process for calculating the zeros of a polynomial with complexi coefficents. See Jenkins and Traub [http://www.springerlink.com/content/q6w17w30035r2152/?p=ae17d723839045be82d270b45363625f&pi=1 A Three-Stage Variable-Shift Iteration for Polynomial Zeros and Its Relation to Generalized Rayleigh Iteration].<ref>Jenkins, M. A. and Traub, J. F. (1968), [http://www.springerlink.com/content/q6w17w30035r2152/?p=ae17d723839045be82d270b45363625f&pi=1 A Three-Stage Variables-Shift Iteration for Polynomial Zeros and Its Relation to Generalized Rayleigh Iteration], Numer. Math. 14, 252-263.</ref> The algorithm is similar in spirit to the two-stage algorithm studied by Traub; [http://links.jstor.org/sici?sici=0025-5718(196601)20%3A93%3C113%3AACOGCI%3E2.0.CO%3B2-3 A class of Globally Convergent Iteration Functions for the Solution of Polynomial Equations].<ref>Traub, J. F. (1966), [http://links.jstor.org/sici?sici=0025-5718(196601)20%3A93%3C113%3AACOGCI%3E2.0.CO%3B2-3 A Class of Globally Convergent Iteration Functions for the Solution of Polynomial Equations], Math. Comp., 20(93), 113-138.</ref> A description may be bound in Ralston and Rabinowitz<ref>Ralston, A. and Rabinowitz, P. (1978), A First Course in Numerical Analysis, 2nd ed., McGraw-Hill, New York.</ref> p. 383.

The three-stages of the Jenkins-traubTraub algorithalgorithm follow:

*Stage One: No-Shift Process.

This stage is not necessaynecessary from theoretical considerations but is useful in practice.

*Stage Two: Fixed-ShisftShift Process.

A sequence of polynomials <math>H^{(\lambda+1)}(z)</math> is generated, <math>\lambda=0,1,\dots,L-1</math>.

*Stage Three: Variable-Shift Process.

The <math>H^{(\lambda)}(z)</math> are now generated using the variable shift <math>s_{\lambda}</math> which are generated by

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

Line 24:

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> chosen sufficiently large <math>s_{\lambda}</math> always converges to a zero of <math>P</math> and that the rate of convergence is faster than quadratic. 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-RaphonRaphson iteration.

==What Gives the Algorithm its Power?==

Line 33:

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

Note the iteration used the given <math>P</math> and <math>P^{\prime}</math>. In contrast the thirgthird-stage of Jenkins-Traub

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

is precisely a Newton-Raphson iteration performed on certain rational functions. More precisely, Newton-Raphon is being performed on a sequence of rational functions <math>P(z)/H^{(\lambda)}</math>. For <math>\lambda</math> sufficiently large, <math>P(z)/H^{(\lambda)}</math> is as close as desired to a first degree polynomial <math>z-\alphaalpha_1</math>, where <math>\alphaalpha_1</math> is one of the zeros of <math>P</math>. Even though Stage 3 is precisely a Newton-raphonsRaphson iteration differentiation is not performed.

==Real Coefficients==

Line 53:

==References==

Ralston, A. and Rabinowitz, P. (1978), A First Course in Numerical Analysis, 2nd ed., McGraw-Hill, New York.

{{reflist}}