Content deleted Content added
→Overview: Detailed a possible construction of the H sequence |
→What gives the algorithm its power?: as multidimensional Newton map for the 1x(n-1) factorization |
||
Line 66:
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.
=== As a multidimensional Newton's method ===
The sequence of the normed polynomials <math>\bar H^{(\lambda)}</math> is also obtained by considering variants of the Newton-Kantorovich method for the map
:<math>F:\Pi_1\times\Pi_{n-1}\to\Pi_n, F(G,H)=G\cdot H-P</math>
where <math>\Pi_d\subset \C[X]</math> is the set of polynomials of degree ''k+1'' with leading coefficient ''1''.
For the inverse of the derivative of this map one calculates, using <math>G(X)=X-s</math>
:<math>
(\nabla F(G,H))^{-1}(Y)
=\left(
\frac{Y(s)}{H(s)},
\frac1{X-s}\left(Y-\tfrac{Y(s)}{H(s)}H\right)
\right)
</math>.
In the third stage, the full Newton update is applied, that is
:<math>\begin{align}
(G^{k+1}, H^{k+1})
&=(G^k, H^k)-(\nabla F(G,H))^{-1}(G^k\cdot H^k-P)\\
&=\left(
X-s_k+\frac{P(s)}{H^k(s)},
\frac1{X-s_k}\left(P-\tfrac{P(s)}{H^k(s)}H^k\right)
\right)
\end{align}</math>.
From this formula one recovers <math>s_{k+1}=s_k-\tfrac{P(s)}{H^k(s)}</math> and
that <math>H^{k+1}</math> is again a normed polynomial, since ''P'' has leading coefficient ''1'' and <math>H^k</math> has one degree less.
In the first and second stage, the shifts <math>s_k</math> and consequently the first polynomial <math>G^k</math> are left constant, that is without update. The ensuing method is best understood as an inverse power iteration.
==Real coefficients==
| |||