Content deleted Content added
The Golden Ratio is about 1.618033… so if you round it to three decimals, it would be ≈1.62 and not ≈1.61. A better fix is to say ≈1.618 since that is an excellent approximation, correctly rounded. |
|||
| (22 intermediate revisions by 21 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>
This article describes the complex variant. Given a polynomial ''P'',
▲:<math>P(z)=\sum_{i=0}^na_iz^{n-i}, \quad a_0=1,\quad a_n\ne 0</math>
with complex coefficients it computes approximations to the ''n'' zeros <math>\alpha_1,\alpha_2,\dots,\alpha_n</math> of ''P''(''z''), one at a time in roughly increasing order of magnitude. After each root is computed, its linear factor is removed from the polynomial. Using this ''deflation'' guarantees that each root is computed only once and that all roots are found.
Line 10 ⟶ 9:
==Overview==
The Jenkins–Traub algorithm calculates all of the roots of a [[polynomial]] with complex coefficients. The algorithm starts by checking the polynomial for the occurrence of very large or very small roots. If necessary, the coefficients are rescaled by a rescaling of the variable. In the algorithm, proper
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), [
=== Root-finding procedure ===
Starting with the current polynomial ''P''(''X'') of degree ''n'', the aim is to compute the smallest root <math>\alpha</math> of ''P(x)''
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 <math>\bar H(X)</math> of ''P''(''X'') containing (the linear factors of) 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.
The construction of the ''H'' polynomials <math>\left(H^{(\lambda)}(z)\right)_{\lambda=0,1,2,\dots}</math>
<math display="block">
H^{(0)}(z)=P^\prime(z)
</math> and <math display="block">
(X-s_\lambda)\cdot H^{(\lambda+1)}(X)\equiv H^{(\lambda)}(X)\pmod{P(X)}\ .
</math>
A direct solution to this implicit equation is
H^{(\lambda+1)}(X)
=\frac1{X-s_\lambda}\cdot
Line 35:
where the polynomial division is exact.
Algorithmically, one would use
\left.\begin{align}
P(X)&=p(X)\cdot(X-s_\lambda)+P(s_\lambda)\\
Line 44:
</math>
Since the highest degree coefficient is obtained from ''P(X)'', the leading coefficient of <math>H^{(\lambda+1)}(X)</math> is <math>-\tfrac{H^{(\lambda)}(s_\lambda)}{P(s_\lambda)}</math>. If this is divided out the normalized ''H'' polynomial is
\bar H^{(\lambda+1)}(X)
&=\frac1{X-s_\lambda}\cdot
Line 57:
==== Stage one: no-shift process ====
For <math>\lambda = 0,1,\dots, M-1</math> set <math>s_\lambda=0</math>. Usually ''M=5'' is chosen for polynomials of moderate degrees up to ''n'' = 50. This stage is not necessary from theoretical considerations alone, but is useful in practice. It emphasizes in the ''H'' polynomials the cofactor(s) (of the linear factor) of the smallest root(s).
==== Stage two: fixed-shift process ====
The shift for this stage is determined as some point close to the smallest root of the polynomial. It is quasi-randomly located on the circle with the inner root radius, which in turn is estimated as the positive solution of the equation
R^n+|a_{n-1}|\,R^{n-1}+\dots+|a_{1}|\,R=|a_0|\,.
</math>
Since the left side is a convex function and increases monotonically from zero to infinity, this equation is easy to solve, for instance by [[Newton's method]].
Now choose <math>s=R\cdot \exp(i\,\phi_\text{random})</math> on the circle of this radius. The sequence of polynomials <math>H^{(\lambda+1)}(z)</math>, <math>\lambda=M,M+1,\dots,L-1</math>, is generated with the fixed shift value <math>s_\lambda = s</math>. This creates an asymmetry relative to the previous stage which increases the chance that the ''H'' polynomial moves towards the cofactor of a single root.
During this iteration, the current approximation for the root is traced. The second stage is
<math display="block">
|t_{\lambda+1}-t_\lambda|<\tfrac12\,|t_\lambda|
</math> and <math display="block">
|t_\lambda-t_{\lambda-1}|<\tfrac12\,|t_{\lambda-1}|
</math>
are simultaneously met. This limits the relative step size of the iteration, ensuring that the approximation sequence stays in the range of the smaller roots. If there was no success after some number of iterations, a different random point on the circle is tried. Typically one uses a number of 9 iterations for polynomials of moderate degree, with a doubling strategy for the case of multiple failures.
==== Stage three: variable-shift process ====
The <math>H^{(\lambda+1)}(X)</math> polynomials are now generated using the variable shifts <math>s_{\lambda},\quad\lambda=L,L+1,\dots</math> which are generated by
being the last root estimate of the second stage and
If the step size in stage three does not fall fast enough to zero, then stage two is restarted using a different random point. If this does not succeed after a small number of restarts, the number of steps in stage two is doubled.
Line 88 ⟶ 92:
It can be shown that, provided ''L'' is chosen sufficiently large, ''s''<sub>λ</sub> always converges to a root of ''P''.
The algorithm converges for any distribution of roots, but may fail to find all roots of the polynomial. Furthermore, the convergence is slightly faster than the [[Rate of convergence|quadratic convergence]] of the Newton–Raphson
==What gives the algorithm its power?==
Compare with the [[Newton–Raphson iteration]]
▲:<math>z_{i+1}=z_i - \frac{P(z_i)}{P^{\prime}(z_i)}.</math>
The iteration uses the given ''P'' and <math>\scriptstyle P^{\prime}</math>. In contrast the third-stage of Jenkins–Traub
<math display="block">
s_{\lambda+1}
=s_\lambda- \frac{P(s_\lambda)}{\bar H^{\lambda+1}(s_\lambda)}
Line 106:
is precisely a Newton–Raphson iteration performed on certain [[rational functions]]. More precisely, Newton–Raphson is being performed on a sequence of rational functions
▲:<math>W^\lambda(z)=\frac{P(z)}{H^\lambda(z)}.</math>
For <math>\lambda</math> sufficiently large,
▲:<math>\frac{P(z)}{\bar H^{\lambda}(z)}=W^\lambda(z)\,LC(H^{\lambda})</math>
is as close as desired to a first degree polynomial
▲:<math>z-\alpha_1, \,</math>
where <math>\alpha_1</math> is one of the zeros of <math>P</math>. Even though Stage 3 is precisely a Newton–Raphson iteration, differentiation is not performed.
=== Analysis of the ''H'' polynomials ===
Let <math>\alpha_1,\dots,\alpha_n</math> be the roots of ''P''(''X''). The so-called Lagrange factors of ''P(X)'' are the cofactors of these roots,
If all roots are different, then the Lagrange factors form a basis of the space of polynomials of degree at most ''n'' − 1. By analysis of the recursion procedure one finds that the ''H'' polynomials have the coordinate representation
H^{(\lambda)}(X)
=\sum_{m=1}^n
Line 131 ⟶ 126:
</math>
Each Lagrange factor has leading coefficient 1, so that the leading coefficient of the H polynomials is the sum of the coefficients. The normalized H polynomials are thus
\bar H^{(\lambda)}(X)
=\frac{\sum_{m=1}^n
Line 143 ⟶ 138:
\right]^{-1}
}
= \frac{P_1(X)+\sum_{m=2}^n
\left[
\prod_{\kappa=0}^{\lambda-1}\frac{\alpha_1-s_\kappa}{\alpha_m-s_\kappa}
Line 159 ⟶ 154:
Under the condition that
one gets the
*stage 1: <math display="block">
H^{(\lambda)}(X)
=P_1(X)+O\left(\left|\frac{\alpha_1}{\alpha_2}\right|^\lambda\right).
</math>
*for stage 2, if ''s'' is close enough to <math>\alpha_1</math>: <math display="block">
H^{(\lambda)}(X)
= P_1(X)
+O\left(
\left|\frac{\alpha_1}{\alpha_2}\right|^M
\cdot
\left|\frac{\alpha_1-s}{\alpha_2-s}\right|^{\lambda-M}\right)
</math> and <math display="block">
s-\frac{P(s)}{\bar H^{(\lambda)}(s)}
= \alpha_1+O\left(\ldots\cdot|\alpha_1-s|\right).</math>
*and for stage 3: <math display="block">
H^{(\lambda)}(X)
=P_1(X)
Line 186 ⟶ 176:
\left|\frac{\alpha_1-s_\kappa}{\alpha_2-s_\kappa}\right|
\right)
</math> and <math display="block">
s_{\lambda+1}=
s_\lambda-\frac{P(s)}{\bar H^{(\lambda+1)}(s_\lambda)}
Line 196 ⟶ 184:
\frac{|\alpha_1-s_\lambda|^2}{|\alpha_2-s_\lambda|}
\right)
▲:giving rise to a higher than quadratic convergence order of <math>\phi^2=1+\phi\approx 2.61</math>, where <math>\phi=\tfrac12(1+\sqrt5)</math> is the [[golden ratio]].
=== Interpretation as inverse power iteration ===
All stages of the Jenkins–Traub complex algorithm may be represented as the linear algebra problem of determining the eigenvalues of a special matrix. This matrix is the coordinate representation of a linear map in the ''n''-dimensional space of polynomials of degree ''n'' − 1 or less. The principal idea of this map is to interpret the factorization
with a root <math>\alpha_1\in\C</math> and <math>P_1(X) = P(X) / (X-\alpha_1)</math> the remaining factor of degree ''n'' − 1 as the eigenvector equation for the multiplication with the variable ''X'', followed by remainder computation with divisor ''P''(''X''),
This maps polynomials of degree at most ''n'' − 1 to polynomials of degree at most ''n'' − 1. The eigenvalues of this map are the roots of ''P''(''X''), since the eigenvector equation reads
which implies that <math>(X-\alpha)\cdot H
the resulting
0 & 0 & \dots & 0 & -
1 & 0 & \dots & 0 & -
0 & 1 & \dots & 0 & -
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \dots & 1 & -
\end{pmatrix}\,.</math>
To this matrix the [[inverse power iteration]] is applied in the three variants of no shift, constant shift and generalized Rayleigh shift in the three stages of the algorithm. It is more efficient to perform the linear algebra operations in polynomial arithmetic and not by matrix operations, however, the properties of the inverse power iteration remain the same.
==Real coefficients==
The Jenkins–Traub algorithm described earlier works for polynomials with complex coefficients. The same authors also created a three-stage algorithm for polynomials with real coefficients. See Jenkins and Traub [
==A connection with the shifted QR algorithm==
Line 227 ⟶ 214:
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 methods have been extensively tested by many people.{{Who|date=December 2021}} As predicted they enjoy faster than quadratic convergence for all distributions of zeros.
However, there are polynomials which can cause loss of precision<ref>{{Cite web|date=8 August 2005|title=William Kahan Oral history interview by Thomas Haigh|url=http://history.siam.org/oralhistories/kahan.htm|access-date=2021-12-03|website=The History of Numerical Analysis and Scientific Computing|publication-place=Philadelphia, PA}}</ref> as illustrated by the following example. The polynomial has all its zeros lying on two half-circles of different radii. [[James H. Wilkinson|Wilkinson]] recommends that it is desirable for stable deflation that smaller zeros be computed first. The second-stage shifts are chosen so that the zeros on the smaller half circle are found first. After deflation the polynomial with the zeros 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, Englewood Cliffs, N.J.</ref> p. 64. The original polynomial was of degree 60 and suffered severe deflation instability.
==References==
Line 235 ⟶ 222:
==External links==
*[http://www.hvks.com/Numerical/winsolve.html A free downloadable Windows application using the Jenkins–Traub Method for polynomials with real and complex coefficients]
*[https://github.com/sweeneychris/RpolyPlusPlus RPoly++] An SSE-Optimized C++ implementation of the RPOLY algorithm.
{{Root-finding algorithms}}
Line 246 ⟶ 229:
{{DEFAULTSORT:Jenkins-Traub Algorithm}}
[[Category:Numerical analysis]]
[[Category:
| |||