Partial Convergents
Fix a finite continued fraction
. We do not assume
at this point that the
are integers.
Definition 5.1 (Partial convergents)
For
![$ 0\leq n\leq m$](img1592.png)
, the
![$ n$](img7.png)
th
convergent of the
continued fraction
![$ [a_0,\ldots,a_m]$](img1591.png)
is
![$ [a_0,\ldots, a_n]$](img1593.png)
. These convergents for
![$ n<m$](img1594.png)
are
also called
partial convergents.
For each
with
,
define real numbers
and
as follows:
Proof.
We use induction. The assertion is obvious when
![$ n=0,1$](img1598.png)
. Suppose the
proposition is true for all continued fractions of length
![$ n-1$](img488.png)
. Then
SAGE Example 5.1
If c is a continued fraction
in SAGE, use c.convergents()
to compute a list of the partial
convergents of c.
sage: c = continued_fraction(pi,bits=33); c
[3, 7, 15, 1, 292, 2]
sage: c.convergents()
[3, 22/7, 333/106, 355/113, 103993/33102, 208341/66317]
As we will see, the convergents of a continued fraction
are the best rational approximations to the value of
the continued fraction. In the example above, the
listed convergents are the best rational approximations
of
![$ \pi$](img1560.png)
with given denominator size.
Proof.
The case for
![$ n=0$](img1610.png)
is obvious from the definitions.
Now suppose
![$ n>0$](img1300.png)
and the statement is true for
![$ n-1$](img488.png)
. Then
This completes the proof of (
5.1.2). For
(
5.1.3), we have
Remark 5.1
Expressed in terms of matrices, the proposition asserts that the determinant
of
![$ \left(\begin{smallmatrix}p_n&p_{n-1} q_n&q_{n-1}\end{smallmatrix}\right)$](img1575.png)
is
![$ (-1)^{n-1}$](img1620.png)
, and of
![$ \left(\begin{smallmatrix}p_n&p_{n-2} q_n&q_{n-2}\end{smallmatrix}\right)$](img1576.png)
is
![$ (-1)^{n}a_n$](img1621.png)
.
SAGE Example 5.1
We use SAGE to verify Proposition
5.1.7
for the first few terms of the continued
fraction of
![$ \pi$](img1560.png)
.
sage: c = continued_fraction(pi); c
[3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 3]
sage: for n in range(-1, len(c)):
... print c.pn(n)*c.qn(n-1) - c.qn(n)*c.pn(n-1),
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1
sage: for n in range(len(c)):
... print c.pn(n)*c.qn(n-2) - c.qn(n)*c.pn(n-2),
3 -7 15 -1 292 -1 1 -1 2 -1 3 -1 14 -3
Proof.
It is clear that the
![$ p_n$](img1570.png)
and
![$ q_n$](img1571.png)
are integers, from the formula
that defines them. If
![$ d$](img16.png)
is a positive divisor of both
![$ p_n$](img1570.png)
and
![$ q_n$](img1571.png)
, then
![$ d\mid (-1)^{n-1}$](img1623.png)
, so
![$ d=1$](img1624.png)
.
SAGE Example 5.1
We illustrate Corollary
5.1.10 using SAGE.
sage: c = continued_fraction([1,2,3,4,5])
sage: c.convergents()
[1, 3/2, 10/7, 43/30, 225/157]
sage: [c.pn(n) for n in range(len(c))]
[1, 3, 10, 43, 225]
sage: [c.qn(n) for n in range(len(c))]
[1, 2, 7, 30, 157]
William
2007-06-01