Jenkins–Traub algorithm: Difference between revisions

Revision as of 11:42, 4 August 2009

Revision as of 09:01, 5 August 2009

Line 65:

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_Ms=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_Ms</math>. TypicallyDuring onethis usesiteration, ''L=M+9''the current approximation for polynomialsthe ofroot moderate degree.

:<math>t_\lambda=s-\frac{P(s)}{\bar H^{(\lambda)}(s)}</math>

is traced. The second stage is finished successfully if the conditions

:<math>

|t_{\lambda+1}-t_\lambda|<\tfrac12\,|t_\lambda|

</math> and <math>

|t_\lambda-t_{\lambda-1}|<\tfrac12\,|t_{\lambda-1}|

</math>

are simultaneously met. 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 ====