Expand/Contract All

Continued Fractions

Page Contents

Continued Fractions

A #~{continued fraction} has the form

cfrac{,1,cfrac{~a_1 + ,~b_1,cfrac{~a_2 + ,~b_2,cfrac{~a_3 + ,~b_3, ^#.#._#. }}}}

Write

~F _ = _ 1 ./ (~a_1 + ~b_1 ./ (~a_2 + ~b_2 ./ (~a_3 + ~b_3 ./ ... ./ (~a_~i + ~b_~i ./ (~a_{~i+1} + ~b_{~i+1} ... )))))

The ~n^{th} #~{convergent} is defined as the truncation of the continued fraction after the ~n^{th} line

~F_~n _ = _ 1 ./ (~a_1 + ~b_1 ./ (~a_2 + ~b_2 ./ (~a_3 + ~b_3 ./ ... ./ (~a_{~n-1} + ~b_{~n-1} ./ (~a_~n + ~b_~n)).)))

Put _ ~X_{~n - 1} _ = _ ~b_{~n - 1} , _ _ ~Y_{~n - 1} _ = _ ~a_~n + ~b_~n

~F_~n _ = _ 1 ./ (~a_1 + ~b_1 ./ (~a_2 + ~b_2 ./ (~a_3 + ~b_3 ./ ... ~b_{~n - 2} ./ (~a_{~n - 1} + ~X_{~n - 1} ./ ~Y_{~n - 1}).)))

_ _ _ = _ 1 ./ (~a_1 + ~b_1 ./ (~a_2 + ~b_2 ./ (~a_3 + ~b_3 ./ ... ~b_{~n - 2}~Y_{~n - 1} ./ (~a_{~n - 1}~Y_{~n - 1} + ~X_{~n - 1} ).)))

Suppose we have reduced _ ~F_~n _ to the form

~F_~n _ = _ 1 ./ (~a_1 + ~b_1 ./ (~a_2 + ~b_2 ./ (~a_3 + ~b_3 ./ ... ~b_{~i} ./ (~a_{~i + 1} + ~X_{~i + 1} ./ ~Y_{~i + 1}).)))

then

~F_~n _ = _ 1 ./ (~a_1 + ~b_1 ./ (~a_2 + ~b_2 ./ (~a_3 + ~b_3 ./ ... ~b_{~i}~Y_{~i + 1} ./ (~a_{~i + 1}~Y_{~i + 1} + ~X_{~i + 1} ).)))

~F_~n _ = _ 1 ./ (~a_1 + ~b_1 ./ (~a_2 + ~b_2 ./ (~a_3 + ~b_3 ./ ... ~b_{~i - 1} ./ (~a_{~i} + ~X_{~i} ./ ~Y_{~i} ).)))

where _ ~X_{~i} _ = _ ~b_{~i}~Y_{~i + 1} , _ _ ~Y_{~i} _ = _ ~a_{~i + 1}~Y_{~i + 1} + ~X_{~i + 1} _ ... _ (1).

Continuing recursively, we get

~F_~n _ = _ 1 ./ (~a_1 + ~X_1 ./ ~Y_1) _ = _ ~Y_1 ./ (~a_1~Y_1 + ~X_1)

Using the relation (1) to expand:

~F_~n _ = _ fract{ ~Y_1 , (~a_1~Y_1 + ~X_1)} _ = _ fract{ ~a_2~Y_2 + ~X_2 , (~a_1(~a_2~Y_2 + ~X_2) + ~b_1~Y_2)}

_ _ _ = _ fract{ ~a_2~Y_2 + ~X_2 , ((~a_1~a_2 + ~b_1)~Y_2 + ~a_1~X_2)}

Note that numerator and denominator are linear equations in ~Y_2 and ~X_2. This process can be continued, so put

~F_~n _ = _ fract{ ~r_{~j - 1}~Y_{~j - 1} + ~t_{~j - 1}~X_{~j - 1}, ~u_{~j - 1}~Y_{~j - 1} + ~v_{~j - 1}~X_{~j - 1}}

_ _ _ = _ fract{ ~r_{~j - 1}(~a_~j~Y_~j + ~X_~j) + ~t_{~j - 1}~b_{~j - 1}~Y_~j, ~u_{~j - 1}(~a_~j~Y_~j + ~X_~j) + ~v_{~j - 1}~b_{~j - 1}~Y_~j}

_ _ _ = _ fract{ (~r_{~j - 1}~a_~j + ~t_{~j - 1}~b_{~j - 1})~Y_~j + ~r_{~j - 1}~X_~j , (~u_{~j - 1}~a_~j + ~v_{~j - 1}~b_{~j - 1})~Y_~j + ~u_{~j - 1}~X_~j)}

_ _ _ = _ fract{ ~r_~j ~Y_~j + ~t_~j ~X_~j, ~u_~j ~Y_~j + ~v_~j ~X_~j}

where

~r_~j _ = _ ~r_{~j - 1}~a_~j + ~t_{~j - 1}~b_{~j - 1} , _ _ _ ~t_~j _ = _ ~r_{~j - 1}

~u_~j _ = _ ~u_{~j - 1}~a_~j + ~v_{~j - 1}~b_{~j - 1} , _ _ _ ~v_~j _ = _ ~u_{~j - 1} _ ... _ (2)

The expansion eventually stopping at _ ~j _ = _ ~n - 1 , _ where _ _ ~X_{~n - 1} _ = _ ~b_{~n - 1} , _ _ ~Y_{~n - 1} _ = _ ~a_~n + ~b_~n:

~F_~n _ = _ fract{ ~r_{~n - 1} (~a_~n + ~b_~n ) + ~t_{~n - 1} ~b_{~n - 1}, ~u_{~n - 1} (~a_~n + ~b_~n ) + ~v_{~n - 1} ~b_{~n - 1}}

Note that the ~r_~j, ~t_~j, ~u_~j, and ~v_~j are not dependent on the stopping point (~n), and for ~i < ~n these will have the same value in the expansion of ~F_{~n + 1} as in the expansion of ~F_~n , _ so we can evaluate the ~F_~n progressively until some stopping criterion is met.

We saw that

~F_~n _ = _ fract{ ~Y_1 , (~a_1~Y_1 + ~X_1)}

So _ ~r_1 = 1 , _ ~t_1 = 0 , _ ~u_1 = ~a_1 , _ ~v_1 = 1. _ The subsequent values can be calculated providing we can calculate the ~a_~i and ~b_~i.

Programming Example

The following, incomplete, piece of code is only meant to illustrate the general principles involved. It can be adapted to specific problems, and should be fairly easy to implement in any of the C family of computer languages ( C, C++, Java, JavaScript, ...).

   wA = ??? ; // set to value of a_1
   wB = ??? ; // set to value of b_1 
   wR = 1;
   wT = 0;
   wU = wA;
   wV = 1;
  
   for( var wJ = 2 ; wJ < ??? ; wJ++) // stopping criterion
   {
      prevB = wB;
      prevA = wA;
      prevR = wR;
      prevT = wT; 
      prevU = wU;
      prevV = wV;
   
      wA = ??? ; // set or calculate value of a_2, a_3, etc.
      wB = ??? ; // set or calculate value of b_2, b_3, etc.
      wR = prevR * wA + prevT * prevB;
      wT = prevR;
      wU = prevU * wA + prevV * prevB;
      wV = prevU;
      // calculate S_n (if needed)
      wSum = prevR * ( wA + wB ) + prevT * prevB /
            prevU * ( wA + wB ) + prevV * prevB; 
    }

Here is a rather trivial example to calculate _ 1/(3 + 1/(3 + 1/(3 + 1/ ... , _ for n from 2 to 9 (view source for coding details):

Note that this quickly seems to settle down to a number around 0.30277. This leads us to the question of convergence.

Convergence and Limits