Content deleted Content added
→External links: Add links to Netlib's copies of the programs by Jenkins and Traub. |
add 2 wikilinks, spacing |
||
Line 87:
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 sligthly faster than the [[Rate of convergence|quadratic convergence]] of Newton-Raphson iteration, however, it uses at least twice as many operations per step.
==What gives the algorithm its power?==
Line 197:
=== 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
:<math>P(X)=(X-\alpha_1)\cdot P_1(X)</math>
Line 227 ⟶ 226:
The methods have been extensively tested by many people. As predicted they enjoy faster than quadratic convergence for all distributions of zeros.
However there are polynomials which can cause loss of precision 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==
{{reflist}}
| |||