Content deleted Content added
→Root-finding procedure: introduce the aim of obtaining an approximate factorization and the place of the H factor in it. Add and clarify motivations for the stages |
^m→Interpretation as inverse power iteration: The coefficients of P were introduced as a_i, use them in the companion matrix |
||
Line 189:
<math display="block">P(X)=(X-\alpha_1)\cdot P_1(X)</math>
with a root <math>\alpha_1\in\C</math> and <math>P_1(X) = P(X) / (X-\alpha_1)</math> the remaining factor of degree ''n'' − 1 as the eigenvector equation for the multiplication with the variable ''X'', followed by remainder computation with divisor ''P''(''X''),
<math display="block">M_X(H) = (X\cdot H(X)) \bmod P(X)\,.</math>
This maps polynomials of degree at most ''n'' − 1 to polynomials of degree at most ''n'' − 1. The eigenvalues of this map are the roots of ''P''(''X''), since the eigenvector equation reads
<math display="block">0 = (M_X-\alpha\cdot id)(H)=((X-\alpha)\cdot H) \bmod P\,,</math>
which implies that <math>(X-\alpha)\cdot H)=C\cdot P(X)</math>, that is, <math>(X-\alpha)</math> is a linear factor of ''P''(''X''). In the monomial basis the linear map <math>M_X</math> is represented by a [[companion matrix]] of the polynomial ''P'', as
<math display="block"> M_X(H) = \sum_{m=0}^{n-1}H_mX^{m+1}-H_{n-1}\left(X^n+\sum_{m=0}^{n-1}a_mX^m\right) = \sum_{m=1}^{n-1}(H_{m-1}-
the resulting
<math display="block">A=\begin{pmatrix}
0 & 0 & \dots & 0 & -
1 & 0 & \dots & 0 & -
0 & 1 & \dots & 0 & -
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \dots & 1 & -
\end{pmatrix}\,.</math>
To this matrix the [[inverse power iteration]] is applied in the three variants of no shift, constant shift and generalized Rayleigh shift in the three stages of the algorithm. It is more efficient to perform the linear algebra operations in polynomial arithmetic and not by matrix operations, however, the properties of the inverse power iteration remain the same.
| |||