approximating algebraic numbers with linear recurrences
Linear recurrences can be used to obtain rational approximations for real algebraic numbers. Suppose that is the root of a polynomial with rational coefficients and further assume that the roots of are distinct and that all the other roots of are strictly smaller in absolute value than .
Consider the recursion
As discussed in the parent entry, the solution of this recurrence is
where are the roots of — let us agree that — and the ’s are determined by the initial conditions of the recurrence. If , we have
Because when , we have , and hence
To illustrate this method, we will compute the square root of two. Now, we cannot use the equation because it has two roots, and , which are equal in absolute value. So what we shall do instead is to use the equation , or , whose roots are and . Since , we can use our method to approximate the larger of these roots, namely ; to approximate , we subtract from our answer. The recursion we should use is
or, moving terms around,
If we choose , then we have
Starting with these values, we obtain the following sequence:
Therefore, as our approximations to , we have
By making suitable transformations, one can compute all the roots of a polynomial using this technique. A way to do this is to start with a rational number which is closer to the desired root than to the other roots, then make a change of variable .
As an example, we shall examine the roots of . Approximating the polynomial by leaving off the constant term, we guess that the roots are close to , , and . Since the two complex roots are conjugates, it suffices to find one of them.
To look for the root near , we make the change of variable to obtain , which gives the recursion . Picking some initial values, this recursion gives us the sequence
whence we obtain the approximations
To look for the root near , we make the change of variable to obtain , which gives the recursion
Picking some initial values, this recursion gives us the sequence
|Title||approximating algebraic numbers with linear recurrences|
|Date of creation||2013-03-22 16:53:03|
|Last modified on||2013-03-22 16:53:03|
|Last modified by||rspuzio (6075)|