Thursday, April 9, 2009

Continued fractions

Any whole number or simple fraction can be written as a continued fraction. Continued fractions appear a little strange and look like this:

        1
a0 + ----------------------
            1
     a1 + ---------------
               1
          a2 + --------
               a3 + ...
To make it easier to write down, the above fraction is written as:

[a0 ; a1, a2, a3 ...]

For example, the continued fraction for 40/33 is:

        1
 1 + ----------------------
            1
      4 + ---------------
                1
          1 + ---------
                   1
              2 + ---
                   2
= [1; 4, 1, 2, 2]

You can check this on a calculator by starting at the bottom of the fraction and working upwards. First calculate 1/2, then add 2, then do 1/x , then add 1, then do 1/x again, then add 4, do 1/x again and finally add one to get 1.21212... = 40/33.

To work out the numbers that go in a continued fraction you go in the opposite direction. Start with 40/33. = 1.21212.

1.2121212

Subtract the whole number part, in this case 1

value remainingcontinued fraction so far
0.2121212 1 + ...

Take 1/x

value remainingcontinued fraction so far
4.7142857 1 + 1/ ...

Subtract the whole number part, in this case 4

value remainingcontinued fraction so far
0.7142857 1 + 1/( 4 + ...)

Take 1/x

value remainingcontinued fraction so far
1.4000000 1 + 1/( 4 + 1/ ...)

Subtract the whole number part, in this case 1

value remainingcontinued fraction so far
0.4000000 1 + 1/( 4 + 1/ (1 +...))

Take 1/x

value remainingcontinued fraction so far
2.5000000 1 + 1/( 4 + 1/ (1 + 1/ ...))

Subtract the whole number part, in this case 2

value remainingcontinued fraction so far
0.5000000 1 + 1/( 4 + 1/ (1 + 1/ (2 + ...))

Take 1/x

value remainingcontinued fraction so far
2.0000000 1 + 1/( 4 + 1/ (1 + 1/ (2 + 1/...))

We are left with a whole number so put this number in our continued fraction and we have reached the end.

40/33 = 1 + 1/( 4 + 1/ (1 + 1/ (2 + 1/2))

You can use the same method to work out continued fractions for square roots. Then the continued fraction goes on forever (unless the square root is a whole number eg √4 = 2):

           1
√2 = 1 + ---------------------
               1
         2 + --------------
                  1
             2 + --------
                  2 + ...
= [1; 2, 2, 2, 2, ...]

For square roots, the continued fraction soon forms a repeating pattern.

√2 = [1; 2, 2, ...]
√3 = [1; 1, 2, 1, 2, ...]
√5 = [2; 4, 4, ...]
√6 = [2; 2, 4, 2, 4, ...]
√7 = [2; 1, 1, 1, 4, 1, 1, 1, 4, ...]

For other numbers, such as π, the continued fraction does not form a pattern:

π = [3; 7, 15, 1, 292, 1, 1, 1, 2. ...]

By using the start of a continued fraction we can determine a fraction that is close to the irrational number. For the case of π:

[3;] = 3/1 = 3 = π - 0.14
[3; 7] = 22/7 = 3.1428 = π + 0.0012
[3; 7, 15] = 333/106 = 3.141509 = π - 0.000083
[3; 7, 15, 1] = 355/113 = 3.14159292 = π + 0.00000027
[3; 7, 15, 1, 292] = 103993/33102 = 3.14159265301 = π - 0.00000000058

The 292 in the continued fraction for π is quite large. This indicates that we will have to use much larger numbers in the faction to estimate π, before we find a better approximation than 355/113. So 355/113 will be quite a good approximation for π.

No comments:

Post a Comment