Content deleted Content added
LucasBrown (talk | contribs) Adding short description: "Root-finding algorithm for polynomials" |
The Golden Ratio is about 1.618033… so if you round it to three decimals, it would be ≈1.62 and not ≈1.61. A better fix is to say ≈1.618 since that is an excellent approximation, correctly rounded. |
||
| (One intermediate revision by one other user not shown) | |||
Line 184:
\frac{|\alpha_1-s_\lambda|^2}{|\alpha_2-s_\lambda|}
\right)
</math> giving rise to a higher than quadratic convergence order of <math>\phi^2=1+\phi\approx 2.
=== Interpretation as inverse power iteration ===
Line 193:
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
<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}-a_{m}H_{n-1})X^m-a_0H_{n-1}\,,</math>
the resulting transformation matrix is
| |||