Jenkins–Traub algorithm: Difference between revisions

Revision as of 20:49, 6 July 2007

Revision as of 20:51, 6 July 2007

Line 9:

==Overview==

The Jenkins-Traub algorithm is a three-stage process for calculating the zeros of a polynomial with complex coefficents. See Jenkins and Traub<ref>[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].Jenkins, M. A. and Traub, J. F. (1970), [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.> .

A description can also be found 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 algorithm is similar in spirit to the two-stage algorithm studied by Traub<ref> [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]. 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>.

The three-stages of the Jenkins-Traub algorithm followare these:

The three-stages of the Jenkins-Traub algorithm follow:

*Stage One: No-Shift Process.

This stage is not necessary from theoretical considerations alone, but is useful in practice.

*Stage Two: Fixed-Shift Process.

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