Jenkins–Traub algorithm: Difference between revisions

Revision as of 00:15, 17 December 2011

Revision as of 18:41, 4 October 2012

Line 16:

=== Root-finding procedure ===

Starting with the current polynomial ''P''(''X'') of degree ''n'', the smallest root of ''P(x)'' is computed. To that end, a sequence of so -called ''H'' polynomials is constructed. These polynomials are all of degree ''n''&nbsp;&minus;&nbsp;1 and are supposed to converge to the factor of ''P''(''X'') containing 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> depends on a sequence of complex numbers <math>(s_\lambda)_{\lambda=0,1,2,\dots}</math> called shifts. These shifts themselves depend, at least in the third stage, on the previous ''H'' polynomials. The ''H'' polynomials are defined as the solution to the implicit recursion

Line 117:

=== 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,

:<math>P_m(X)=\frac{P(X)-P(\alpha_m)}{X-\alpha_m}.</math>

If all roots are different, then the Lagrange factors form a basis of the space of polynomials of degree at most ''n''&nbsp;&minus;&nbsp;1. By analysis of the recursion procedure one finds that the ''H'' polynomials have the coordinate representation

Line 238:

*[http://www.netlib.org/toms/493 RPOLY] Algorithm 493 from ACM TOMS) on Netlib. In Fortran.

*[http://www.novanumeric.com/samples.php?CalcName=Roots Online Calculator] Online Polynomial Calculator using the Jenkins Traub procedure

{{DEFAULTSORT:Jenkins-Traub Algorithm}}

[[Category:Numerical analysis]]