Let us go back to Figure 1, and give another meaning to the involved matricial products. Since
as 
(together
with 
) and 
as the homographic
mapping 
. We therefore obtain 
.
In our example 
.
By recurrence, we have 
where 
.
In other words,
But the composition of homographies obeys to the same rules as matricial
products, and the 
can be obtained by multiplying, from left
to right, the matrices 
,
namely:
the integer coefficients of these homographies,
i.e. 
.
The fractions 
are usually called the
convergents of 
(expansion of into
continued fractions). The last one (here 
) is nothing
but the irreducible expression of , and the preceeding one
(here 
) carries the Bezout's coefficient of the pair
that defines as 
.
From the very definition, we have formula
 |
 |
 |
|
 |
|
 |
, so that 
except perhaps from
and 
. Thus
the are positive (for 
).
and 
are coprimes since 
.
is monotonic over 
therefore
.
written in lowest terms 
since
is really a strong one, since for a randomly chosen denominator, 
only implies that 
.
If we compare Figure 1 with Figure 2,
we can do the following remarks. On the former, the algorithm goes
through fractions 
, 
, 
,
, and (the ``convergents''
of 
). On the later, the algorithm goes only
through , , and ,
skipping and . This remark can be generalized
as follows.
Theorem 1. A convergent is skipped by the centered algorithm
if and only if the next quotient is 
, except for the ``killing
convergents'' that are not killed themselves.
Proof. Let us define (for 
) 
as 
together with 
. The lemma:
,
obtained from the ordinary algorithm, can be rewritten as follows
: reading from the left, the first occurrence of 
is replaced
according to Eq. 4. And so on recursively. It is
to be noticed that a sequence 
will be replaced by 
: the second
will never been the center of a replacement (``killer
not killed''). When all the have been removed, the 
can be pushed to the right according to Eq. 5 or
canceled by encountering another since 
and we obtain 
.
This sequence of homographies 
acts with decreasing 
, i.e. from right to left, over the 
defined by 
and 
.
But this sequence acts with increasing over the matrices conveying
the remainders and the convergents, according to
, 
,
, Eq. 6 leads
to 
(where 
is a centered remainder) and to 
.
With these transformations, the quotient sequence 
, 
,
is shorten to 
while the remainder sequence
is replaced by 
and one convergent is skipped. If 
, i.e. if 
is a centered remainder, every things are ready to continue the algorithm,
with one sign reversal until another is encountered. On
the other hand, if 
, the remainder is not a
centered one and another reduction step must be engaged, involving
the new quotient 
, this and the next quotient
.
In our example, we start from 
,
rewritten as 
then 
and obtain 
.
In other words, convergent 
is killed since 
; 
remains regardless to 
: ``killer
is not killed'' ; 
is killed since 
; 
remains (killer) ; 
remains
since 
and 
remains too since
.
Let us give another example of that process, by describing the expansion
of 
into convergents. Figure 4
gives the convergents of that number and the quotients 
and
respectively involved in the ordinary and centered
algorithm. A 
in the last line stands for ``killed'' and the
corresponding fraction isn't a centered convergent.
The sequence 
is converted into 
and thereafter into 
.
This result can be compared with theorem 183 & 184 in [9],
stating that 
holds
for at least one of any two consecutive (ordinary) convergents, and
conversely implies that 
is a convergent of 
. It
is easy to see that any convergent appearing during the centered algorithm
obeys to that rule, except from those related to a sequence ending
by 
where 
or by 
where 
: it suffices to remember that convergents are obtained
under the action of the 
, thus by reading from left to right
the sequence of the 
. And we have :
Theorem 2. For any two consecutive centered convergents,
while
To prove that these bounds are as good as possible, let us consider
a number whose (ordinary) quotient sequence is an odd number,
say 
, of followed by a last one, 
. The (ordinary)
convergents except for the last one, are the Fibonnaci convergents
, and we have 
for 
. Going to the centered sequence, all odd indexed convergents
but the last one are skipped. The quotient of denominators of centered
convergents 
and 
are exactly equal to ,
and 
when 
increases.
On the other hand, 
.
A simple inspection gives 
.
Given 
, we can choose such that 
and thereafter choose the last quotient 
as great as requested
to enforce 
.
Let us now have another sight over properties 1 and 2 of paragraph
4.1. We can use them to define an algorithm that
applies to 
rather than to ,
since quotients and convergents remains the same when starting from
instead of starting from .
Something have changed, however: computations are done now in 
instead of 
. And you have nothing to change to your code, thanks
to Maple's syntax flexibility.
If you want to start from any 
, you have a little change
to do : the ending test cannot remains ``
''.
You have to choose and specify some approximation level, and something
like ``
''
is convenient since, as previously stated, the convergents
of verify 
. Starting
from 
, we obtain Figure 5.
Therefore the first 14 convergents of are :
It appears from Figure 5 that the sequence
of quotients is periodic. That property is a characteristic of quadratics
numbers (a proof can be found in [9]). To obtain an ad
hoc justification for the present case, put 
and define 
. We have 
. The periodicity follows, and also an explanation for the ``surprising
value'' 
: from 
,
the last four digits cannot be trusted since any small rounding error
can be magnified up to that factor.
Expansion into continued fractions can be used to guess if a real
number, known as belonging to a small real interval is in fact a rational
or not. To exemplify this algorithm, due to Lehmer, let us consider
the number 
.
It is well-known that 
holds for the general case, and we want to guess 
.
Since 
is decreasing, we have 
and therefore 
where 
,
the 
being chosen for convenience. On the other hand, we have
where 
and 
(cf Figure 6).
The auxiliary function 
has been chosen for it's decomposition
into partial fractions. From 
,
relation 
is plain and both 
and 
are easy to evaluate. Let
us take 
and put 
and 
.
The confrac algorithm will be slightly modified to start with matrix
instead of 
, allowing a simultaneous expansion of both 
and 
into continued fractions until the two expansions diverge from each
other.
Common convergents to and are convergents of
any such that 
. Here 
is an even convergent of (majorant) and an odd convergent
of (minorant) : it separates the two values. The unexpectedly
high value of the next quotient (2586520) is a strong suggestion for
to be a rational (the effective value of that quotient being
). Further details are given in [6].
.
