approximating algebraic numbers with linear recurrences

Linear recurrences can be used to obtain rational approximations for real algebraic numbersMathworldPlanetmath. Suppose that ρ is the root of a polynomialPlanetmathPlanetmath p(x)=k=0nckxk with rational coefficients ck and further assume that the roots of p are distinct and that all the other roots of p are strictly smaller in absolute valueMathworldPlanetmathPlanetmathPlanetmath than ρ.

Consider the recursion


As discussed in the parent entry, the solution of this recurrence is


where r1,,rn are the roots of p — let us agree that r1=ρ — and the bk’s are determined by the initial conditions of the recurrence. If b10, we have


Because |rkρ|<1 when k>1, we have limm(rk/ρ)m=0, and hence


To illustrate this method, we will compute the square root of two. Now, we cannot use the equation x2-2=0 because it has two roots, +2 and -2, which are equal in absolute value. So what we shall do instead is to use the equation (x-1)2=2, or x2-2x-3=0, whose roots are 1-2 and 1+2. Since |1+2|>|1-2|, we can use our method to approximate the larger of these roots, namely 1+2; to approximate 2, we subtract 1 from our answer. The recursion we should use is


or, moving terms around,


If we choose b1=-b2=1/(22), then we have

a0 =b1(1+2)0+b2(1-2)0=b1+b2=0
a1 =b1(1+2)1+b2(1-2)1=b1+b2+(b1-b2)2=1.

Starting with these values, we obtain the following sequence:

a0 =0
a1 =1
a2 =2
a3 =5
a4 =12
a5 =29
a6 =70
a7 =169
a8 =408
a9 =985
a10 =2738
a11 =5741
a12 =13860

Therefore, as our approximations to 2, 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 h which is closer to the desired root than to the other roots, then make a change of variable x=1/(y+h).

As an example, we shall examine the roots of x3+9x+1. Approximating the polynomial by leaving off the constant term, we guess that the roots are close to 0, +3i, and -3i. Since the two complex roots are conjugatesPlanetmathPlanetmath, it suffices to find one of them.

To look for the root near 0, we make the change of variable x=1/y to obtain y3+9y2+1=0, which gives the recursion ak+3+9ak+2+ak=0. Picking some initial values, this recursion gives us the sequence


whence we obtain the approximations


To look for the root near 3i, we make the change of variable x=1/(y+3i) to obtain y3+(9+9i)y2+(-27+54i)y+82-27i=0, which gives the recursion


Picking some initial values, this recursion gives us the sequence

0, 0, 1,-9-9i, 27+108i,-82-945i,-225+11196i, 44415-127953i,,
Title approximating algebraic numbers with linear recurrences
Canonical name ApproximatingAlgebraicNumbersWithLinearRecurrences
Date of creation 2013-03-22 16:53:03
Last modified on 2013-03-22 16:53:03
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 16
Author rspuzio (6075)
Entry type Definition
Classification msc 11B37