Math 2.0

Numerical analysis Nonlinear equations Theorem

Jenkins–Traub algorithm

Builds on Root of a polynomialMonic polynomialNewton's methodComplex numbers

Statement

Let pp be a monic polynomial of degree n≥2n \ge 2 with complex coefficients and p(0)≠0p(0) \ne 0. Given complex shifts s0,s1,…s_0, s_1, \dots with p(sλ)≠0p(s_\lambda) \ne 0, define polynomials H(λ)H^{(\lambda)} of degree at most n−1n - 1 by H(0)=p′H^{(0)} = p' and H(λ+1)(z)=1z−sλ(H(λ)(z)−H(λ)(sλ)p(sλ) p(z)).H^{(\lambda + 1)}(z) = \frac{1}{z - s_\lambda} \left( H^{(\lambda)}(z) - \frac{H^{(\lambda)}(s_\lambda)}{p(s_\lambda)} \, p(z) \right). Write Hˉ(λ)\bar H^{(\lambda)} for H(λ)H^{(\lambda)} divided by its leading coefficient, when this is defined. The Jenkins–Traub algorithm runs three stages:

  1. no shift: sλ=0s_\lambda = 0 for 0≤λ<M0 \le \lambda < M;
  2. fixed shift: sλ=ss_\lambda = s for M≤λ<LM \le \lambda < L, where ss is a fixed complex number;
  3. variable shift: sL=s−p(s)/Hˉ(L)(s)s_L = s - p(s) / \bar H^{(L)}(s) and sλ+1=sλ−p(sλ)/Hˉ(λ+1)(sλ)s_{\lambda + 1} = s_\lambda - p(s_\lambda) / \bar H^{(\lambda + 1)}(s_\lambda) for λ≥L\lambda \ge L.

Suppose pp has a root α1\alpha_1 with ∣s−α1∣<∣s−α∣\abs{s - \alpha_1} < \abs{s - \alpha} for every other root α\alpha of pp. Then Hˉ(L)(z)→p(z)/(z−α1)\bar H^{(L)}(z) \to p(z)/(z - \alpha_1) as L→∞L \to \infty, coefficient by coefficient, and for LL large enough the variable shifts sλs_\lambda of stage 3 converge to α1\alpha_1.

Remarks

Write p(z)=∏j(z−αj)p(z) = \prod_j (z - \alpha_j) over the roots, so that H(0)=p′=∑jp(z)/(z−αj)H^{(0)} = p' = \sum_j p(z)/(z - \alpha_j). One checks by induction that H(λ)H^{(\lambda)} stays a combination of the polynomials p(z)/(z−αj)p(z)/(z - \alpha_j), and that each shift multiplies the coefficient of the jj-th one by 1/(αj−sλ)1/(\alpha_j - s_\lambda). With a fixed shift ss, the term of the root nearest to ss grows fastest, so the normalized Hˉ(λ)\bar H^{(\lambda)} tends to p(z)/(z−α1)p(z)/(z - \alpha_1). Then p(z)/Hˉ(λ)(z)p(z)/\bar H^{(\lambda)}(z) is close to z−α1z - \alpha_1, and the stage 3 step behaves like Newton's method with an ever better model; its convergence is very fast. In practice ss is taken at a random angle on a circle whose radius is a lower bound for the moduli of the roots. Stage 2 is ended by a test on the shifts. After a root is found, it is divided out and the algorithm runs again on the quotient. A variant for real polynomials works with quadratic factors and real arithmetic.

Going deeper

For a student

It was for a long time the standard black-box polynomial root finder in numerical libraries, under the name CPOLY for the complex version. The stages give a global convergence guarantee that Newton's method alone lacks. Finding the small roots first makes the deflation steps numerically stable.

Reading path

To understand this page from the ground up, read these 14 pages in order. The foundations come first.

Show the path as a graph
Complex numbers, object, no evidence levelComplex numbersobjectGroup, concept, no evidence levelGroupconceptLimit point of a set, definition, no evidence levelLimit point of a setdefinitionRoot of a polynomial, concept, no evidence levelRoot of a polynomialconceptRing, definition, no evidence levelRingdefinitionLimit of a function, definition, no evidence levelLimit of a functiondefinitionPolynomial ring, definition, no evidence levelPolynomial ringdefinitionDerivative, definition, no evidence levelDerivativedefinitionDegree of a polynomial, definition, no evidence levelDegree of a polynomialdefinitionTangent line, concept, no evidence levelTangent lineconceptLeading coefficient, definition, no evidence levelLeading coefficientdefinitionNewton's method, concept, no evidence levelNewton's methodconceptMonic polynomial, definition, no evidence levelMonic polynomialdefinitionJenkins–Traub algorithm, statement, no evidence levelJenkins–Traub algorit…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Complex numbers object
  2. Group concept
  3. Limit point of a set definition
  4. Root of a polynomial concept
  5. Ring definition
  6. Limit of a function definition
  7. Polynomial ring definition
  8. Derivative definition
  9. Degree of a polynomial definition
  10. Tangent line concept
  11. Leading coefficient definition
  12. Newton's method concept
  13. Monic polynomial definition
  14. Jenkins–Traub algorithm statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Jenkins–Traub_algorithm
About this page
TagHTWCTA2MTJ
URIm2://HTWCTA2MTJ
Kindstatement, theorem
WritingW0 stub
MSC65H04
StatusThis copy of the site has no build data. Run m2 status HTWCTA2MTJ.
AboutRoot of a polynomial
UsesRoot of a polynomial, Monic polynomial, Newton's method, Complex numbers
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.