Content deleted Content added
→Overview: Reorganized contents, added the preprocessing stage and some details |
|||
Line 105:
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.
=== 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-1''. By analysis of the recursion procedure one finds that the H polynomials have the coordinate representation
:<math>
H^{(\lambda)}(X)
=\sum_{m=1}^n
\left[
\prod_{\kappa=0}^{\lambda-1}(\alpha_m-s_\kappa)
\right]^{-1}\,P_m(X)\ .
</math>
Each Lagrange factor has leading coefficient 1, so that the leading coefficient of the H polynomials is the sum of the coefficients. The normalized H polynomials are thus
:<math>
\bar H^{(\lambda)}(X)
=\frac{\sum_{m=1}^n
\left[
\prod_{\kappa=0}^{\lambda-1}(\alpha_m-s_\kappa)
\right]^{-1}\,P_m(X)
}{
\sum_{m=1}^n
\left[
\prod_{\kappa=0}^{\lambda-1}(\alpha_m-s_\kappa)
\right]^{-1}
}
=\frac{P_1(X)+\sum_{m=2}^n
\left[
\prod_{\kappa=0}^{\lambda-1}\frac{\alpha_1-s_\kappa}{\alpha_m-s_\kappa}
\right]\,P_m(X)
}{
1+\sum_{m=1}^n
\left[
\prod_{\kappa=0}^{\lambda-1}\frac{\alpha_1-s_\kappa}{\alpha_m-s_\kappa}
\right]^{-1}
}\ .
</math>
If teh condition <math>|\alpha_1-s_\kappa|<\min{}_{m=2,3,\dots,n}|\alpha_m-s_\kappa|</math> holds for almost all iterates, the normalized H polynomials will converge at least geometrically towards <math>P_1(X)</math>
=== As inverse power iteration ===
| |||