Jenkins–Traub algorithm: Difference between revisions

Revision as of 23:38, 21 July 2024

Latest revision as of 22:14, 16 August 2025

(3 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Root-finding algorithm for polynomials}}

The '''Jenkins–Traub algorithm for polynomial zeros''' is a fast globally convergent iterative [[Root-finding algorithms#Roots of polynomials|polynomial root-finding]] method published in 1970 by [[Michael A. Jenkins]] and [[Joseph F. Traub]]. They gave two variants, one for general polynomials with complex coefficients, commonly known as the "CPOLY" algorithm, and a more complicated variant for the special case of polynomials with real coefficients, commonly known as the "RPOLY" algorithm. The latter is "practically a standard in black-box polynomial root-finders".<ref>Press, W. H., Teukolsky, S. A., Vetterling, W. T. and Flannery, B. P. (2007), Numerical Recipes: The Art of Scientific Computing, 3rd ed., Cambridge University Press, page 470.</ref>

Line 183 ⟶ 184:

\frac{|\alpha_1-s_\lambda|^2}{|\alpha_2-s_\lambda|}

\right)

</math> giving rise to a higher than quadratic convergence order of <math>\phi^2=1+\phi\approx 2.61618</math>, where <math>\phi=\tfrac12(1+\sqrt5)</math> is the [[golden ratio]].

=== Interpretation as inverse power iteration ===

Line 192 ⟶ 193:

This maps polynomials of degree at most ''n''&nbsp;&minus;&nbsp;1 to polynomials of degree at most ''n''&nbsp;&minus;&nbsp;1. The eigenvalues of this map are the roots of ''P''(''X''), since the eigenvector equation reads

<math display="block">0 = (M_X-\alpha\cdot id)(H)=((X-\alpha)\cdot H) \bmod P\,,</math>

which implies that <math>(X-\alpha)\cdot H)=C\cdot P(X)</math>, that is, <math>(X-\alpha)</math> is a linear factor of ''P''(''X''). In the monomial basis the linear map <math>M_X</math> is represented by a [[companion matrix]] of the polynomial ''P'', as

<math display="block"> M_X(H) = \sum_{m=0}^{n-1}H_mX^{m+1}-H_{n-1}\left(X^n+\sum_{m=0}^{n-1}a_mX^m\right) = \sum_{m=1}^{n-1}(H_{m-1}-a_{m}H_{n-1})X^m-a_0H_{n-1}\,,</math>

the resulting transformation matrix is

Line 228 ⟶ 229:

{{DEFAULTSORT:Jenkins-Traub Algorithm}}

[[Category:Numerical analysis]]

[[Category:PolynomialsPolynomial factorization algorithms]]