Jenkins–Traub algorithm: Difference between revisions

Revision as of 20:51, 6 July 2007

Revision as of 20:53, 6 July 2007

Line 29:

The algorithm converges for any distribution of zeros. Furthermore, the convergence is faster than the quadratic convergence of Newton-Raphson iteration.

==What Givesgives the Algorithmalgorithm its Powerpower?==

WhatCompare giveswith the Jenkins-Traub algorithm its power? Lets compare with [[Newton-Raphson iteration]]

::::<math>z_{i+1}=z_i - \frac{P(z_i)}{P^{\prime}(z_i)}.</math>

Note theThe iteration useduses the given <math>P</math> and <math>P^{\prime}</math>. In contrast the third-stage of Jenkins-Traub

::::<math>s_{\lambda+1}=s_\lambda- \frac{P(s_\lambda)}{\bar H^{(\lambda+1)}(s_\lambda)}</math>

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>P(z)/H^{(\lambda)}</math>.

For <math>\lambda</math> sufficiently large,

:<math>P(z)/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.

:<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.

==Real Coefficients==