Editing ContinuedFraction
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
If you want a password, email topicsinmaths@solipsys.co.uk
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Sat Apr 20 10:10:33 2024.
Press
to finish editing.
Who can edit this page?
World editing disabled
Members
Council
Admin
Take any positive real number. By rounding down we can see that it consists of an integer plus a bit left over. That extra bit might be zero, in which case we're done, but it might not be. If you subtract off the integer, the bit left over is between 0 and 1. It might be 0, but it can't be 1. Call the extra /x./ Now we can take EQN:\frac{1}{x}. That too is an integer plus a bit left over. Again, that extra bit might be zero, in which case we're done, but it might not be. Again, subtract off the integer, and repeat. * Note: This process will terminate if and only if the starting number is rational. ** Not hard to prove, and an interesting exercise. Let's do this with EQN:\pi. | EQN:\pi | = | 3 | + | 0.1415926... | | 1/0.1415926... | = | 7 | + | 0.0625133... | | 1/0.0625133... | = | 15 | + | 0.9965944... | | 1/0.9965944... | = | 1 | + | 0.0034172... | | 1/0.0034172... | = | 292 | + | 0.6345908... | _ _ EQN:\Large{\pi=3+\frac{1}{7+\frac{1}{15+\frac{1}{1+\frac{1}{292+...}}}}} We can write this as EQN:\pi=[3;7,15,1,292,...] Cutting this off at different stages gives us rational approximations. * EQN:[3]=3=3.0000... * EQN:[3;7]=22/7\approx3.142857 * EQN:[3;7,15]=333/106\approx3.14151 * EQN:[3;7,15,1]=355/113\approx3.141593 * EQN:[3;7,15,1,292]=103993/33102\approx3.1415926530 Compare these with the "correct" value of 3.1415926535897931... As you can see, the large number in the expansion causes a sudden jump in the terms used in the rational approximation. However, a large number in the continued fraction implies a small error in the previous step. That means that cutting off the continued fraction just before a large number will give an unreasonably good approximation. Hence EQN:\pi\approx\frac{355}{113} Using this technique gives an approximation with an error that is "best" given a limit on the size of the denominator. ---- We can also use continued fractions to give another proof that root two is irrational. ---- Given a continued fraction, we can compute the successive truncations as follows. Taking EQN:\sqrt{2}=[1;2,2,2,2,2,...] as an example, write a table with three rows. Put the CF terms across the top, and start with a sort of "identity matrix", but the wrong way around. Here: COLUMN_START | | | 1 | 2 | 2 | 2 | 2 | 2 | ... | | 0 | 1 | 1 | 3 | 7 | 17 | 41 | 99 | ... | | 1 | 0 | 1 | 2 | 5 | 12 | 29 | 70 | ... | COLUMN_SPLIT So we have EQN:\frac{41}{29} and EQN:\frac{99}{70} as approximations to EQN:\sqrt{2}. COLUMN_END _ Each term is the product of the quotient above it and the term on its left, plus the term two to the left. Here it is for EQN:\pi COLUMN_START | | | 3 | 7 | 15 | 1 | 292 | ... | | 0 | 1 | 3 | 22 | 333 | 355 | 103933 | ... | | 1 | 0 | 1 | 7 | 106 | 113 | 33102 | ... | COLUMN_SPLIT So /333=15*22+3/ and /113=1*106+7,/ and we get EQN:\frac{355}{113} as an approximation of EQN:\pi. COLUMN_END