TITLE: Iterations with matrices over simple fields approximating solutions for more complicated fields.
QUESTION [1 upvotes]: Inspired by this question I started wondering if there exist some systematic way to construct approximation to any number one can find using matrices over a preferrably simpler field. In the question matrices with elements $\in \mathbb{Z}$ are used to find approximations to numbers $\in \mathbb{R}$ ( irrationals, to be specific ).
Say we have the equation $$\sum_{k=0}^Nc_kx^k=0$$
If we rewrite it and set our $x^N$ term: $$x^N = \frac{a_{n+1}}{b_{n+1}}\left(\frac{a_n}{b_n}\right)^{N-1}$$
and then all other terms
$$x^k = \left(\frac{a_n}{b_n}\right)^k, k\neq N$$
Put everything on the same quotient and solve for $a_{n+1},b_{n+1}$ in terms of $a_n,b_n$.
For example $x^2-2=0$:
$$\frac{a_{n+1}}{b_{n+1}}\frac{a_n}{b_n} = \frac{2}{1}$$
giving $M = \left[\begin{array}{cc}0&2\\1&0\end{array}\right]$ for $M\left[\begin{array}{c}a_n\\b_n\end{array}\right] = \left[\begin{array}{c}a_{n+1}\\b_{n+1}\end{array}\right]$
But this doesn't work, so somewhere my reasoning is wrong. Can you help me find where?

For no reason I can put into words I tried $(M+I)$ and now it works. I also tried for some different $l$ : $x^2-l = 0, l\in \mathbb{Z}$ and seems to work for those, for $3,5$ giving better approximations to $\sqrt{3}, \sqrt{5}$.
Can one show that this can always be done? Find $M$ with the procedure above and then iterating with $M+I$ multiplications, or is this specific for this equation?
If this is correct, then how to use it to extend to arbitrary polynomials? 
Could maybe this Horner method construction be useful?

REPLY [2 votes]: Given a monic polynomial $P(z) = z^n + a_{n-1} z^{n-1} + \ldots a_0$, the companion matrix 
$$ M = \pmatrix{0 & 0 & 0 & \ldots &  0 & -a_0\cr
                1 & 0 & 0 & \ldots & 0  & -a_1\cr
                0 & 1 & 0 & \ldots & 0 & -a_2 \cr
                  &   &   & \ldots &   &     \cr
                0 & 0 & 0 & \ldots & 1 & -a_{n-1}\cr} $$
has characteristic polynomial $P$.  For any root $r$ of $P$, it has an eigenvector $v$, with $v_n = - r v_1/a_0$.  If this root $r$ is simple and has
greater absolute value than any of the others, then for almost any initial vector $u$ the iterates $M^k u$, appropriately scaled, will be approximations of the eigenvector; thus $- a_0 (M^k u)_n/(M^k u)_1$ will be an approximation 
of $r$, with an error that decreases exponentially.
For example, suppose we want to approximate the real root $r$ of ${z}^{5}+4\,{z}^{4}-4\,{z}^{3}+5\,{z}^{2}-2\,z+1$, which happens to be the largest in absolute value.  We take
$$ M = \pmatrix{0&0&0&0&-1\cr 1&0&0&0&2\cr 0&1&0&0&-5\cr 0&0&1&0&4\cr 
0&0&0&1&-4\cr},\ u = \pmatrix{1\cr 1 \cr 1\cr 1\cr 1\cr}$$
and we get the following approximations to $r$:
$$\eqalign{-(M^1 u)_5/(M^1 u)_1 & = -\frac{3}{1} = -3.0000000000\cr-(M^2 u)_5/(M^2 u)_1 & = -\frac{17}{3} = -5.6666666667\cr-(M^3 u)_5/(M^3 u)_1 & = -\frac{84}{17} = -4.9411764706\cr-(M^4 u)_5/(M^4 u)_1 & = -\frac{211}{42} = -5.0238095238\cr-(M^5 u)_5/(M^5 u)_1 & = -\frac{1058}{211} = -5.0142180095\cr-(M^6 u)_5/(M^6 u)_1 & = -\frac{10609}{2116} = -5.0137051040\cr-(M^7 u)_5/(M^7 u)_1 & = -\frac{53195}{10609} = -5.0141389386\cr-(M^8 u)_5/(M^8 u)_1 & = -\frac{266724}{53195} = -5.0140802707\cr-(M^9 u)_5/(M^9 u)_1 & = -\frac{1337375}{266724} = -5.0140782232\cr-(M^{10} u)_5/(M^{10} u)_1 & = -\frac{1341141}{267475} = -5.0140798205\cr
}$$
{"set_name": "stack_exchange", "score": 1, "question_id": 1818321}