Jenkins–Traub algorithm: Difference between revisions

Revision as of 09:07, 5 August 2009

Revision as of 23:39, 13 August 2009

Line 9:

==Overview==

The Jenkins-Traub algorithm calculates all of the roots of a [[polynomial]] with complex coefficentscoefficients. The algorithm starts by checking the polynomial for the occurence 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 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 prodedureprocedure. The root -finding procedure has three stages that correspond to different variants of the [[inverse power iteration]]. See Jenkins and [[Joseph F Traub|Traub]]<ref>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 [[Philip Rabinowitz (mathematician)|

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>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>.

=== Root -finding procedure ===

Starting with the current polynomial ''P(X)'' of degree ''n'', the smallest root of ''P(x)'' is computed. To that end, a sequence of so called ''H'' polynomials is constructed. These polynomials are all of degree ''n-1'' and are supposed to converge to the factor of ''P(X)'' containing all the remaining roots. The sequence of ''H'' polynomials occurs in two variants, an unnormalized variant that allows easy theoretical insights and a normalized variant of <math>\bar H</math> polynomials that keeps the coefficients in a numerically sensible range.