1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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 }$$

$\endgroup$
  • $\begingroup$ Yes companion matrices, of course! Good one. $\endgroup$ – mathreadler Jun 8 '16 at 18:26
  • $\begingroup$ Seems to fail for $z^2-2=0$, but I suppose that is because for the roots $|\sqrt{2}| = |-\sqrt{2}|$. Same happens for the whole set $z^2-k=0, k \in \mathbb{Z}$. Still haven't figured out why it seems to work to add $I$ to $M$ in that case. But it also works for your 5th degree polynomial (although maybe slightly worse convergence). $\endgroup$ – mathreadler Jun 8 '16 at 19:56
  • 1
    $\begingroup$ Adding $I$ to the matrix shifts the eigenvalues by $1$, so instead of $\pm \sqrt{2}$ you get $1 + \sqrt{2}$ and $1-\sqrt{2}$, with $|1 + \sqrt{2}| > |1 - \sqrt{2}|$. $\endgroup$ – Robert Israel Jun 8 '16 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.