Content deleted Content added
No edit summary |
No edit summary |
||
Line 10:
==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>
The three-stages of the Jenkins-traub algorith follow:
Line 18:
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 40:
==Real Coefficients==
The Jenkins-Traub algorithm described in the previous Section 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 the 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 Connection with the Shifted QR Algorithm==
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 Testing==
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>
The software has been extensively tested by many people and shown to be very robust in fixed precision floating point arithmetic. It has been described as ''practically a standard in black-box polynomial root finders''; see Press, et al.
The polynomial has all its zeros lying on two half-circles of different radii. Wilkinson recommends that it is desirable for ???? deflation that smaller zeros be computed first. The second-stage shifts are closer so that the zeros on the smaller half circle are found first. After deflation the polynomial with the zeros on on the half circle is known to be ill-conditioned if the degree is large. See Wilkinson<ref>Wilkinson, J. H. (1963), Rounding Errors in Algebraic Processes, Prentice Hall,
==References==
{{reflist}}
▲*Ralston, A. and Rabinowitz, P. (1978), A First Course in Numerical Analysis, 2nd Ed., McGraw-Hill, New York.
==External links==
| |||