Centre de Recherche et d'Expérimentation pour l'Enseignement des Mathématiques
Deux
ponts entre le discret et le continu: - différences
finies, Euclide et fractions
continuées;
- Suite de Stern-Brocot et fractions continuées.
Il existe trois variantes d'un même algorithme
géométrique, que les Grecs désignaient par anthyphérèse, qui consiste à découper un rectangle en pièces carrées
aussi grandes que possible. Ces variantes sont communément désignées
par algorithme des "différences finies", algorithme
"d'Euclide" et algorithme des "fractions continuées"
(ou "fractions continues").
1 - L'algorithme des différences
finies:
Cet algorithme est enseigné en classe de troisième pour
déterminer le plus grand diviseur commun de deux nombres entiers a et b.
Il est entièrement construit sur le
simple lemme: si
d divise a et b, alors il divise a-b. Par exemple, si a=3471 et b=1239, on peut présenter sous
forme de tableau les calculs à réaliser:
on initialise les suites (ai)
et (bi) avec les deux nombres
fournis, puis on pose :
di=
ai-bi
, ai+1= max(ai,ai-bi)
et bi+1= min(ai,ai-bi)
On arrête le processus lorsque di
=0; le plus grand commun diviseur de a et b est la dernière différence
non nulle.
i
ai
bi
di
test
d'arrêt: di
= 0 ?
0
3471
1239
2232
d0
>0, on continue
1
2232
1239
993
d1>0, on continue
2
1239
993
246
d2>0, on continue
3
993
246
747
d3>0, on continue
4
747
246
501
d4
>0, on continue
5
501
246
255
d5
>0, on continue
6
255
246
9
d6
>0, on continue
7
246
9
237
d7
>0, on continue
8
237
9
228
d8
>0, on continue
...
...
...
...
...
on continue...
32
12
9
3
d32
>0, on continue
33
9
3
6
d33
>0, on continue
34
6
3
3
d34
>0, on continue
35
3
3
0
d35
= 0 : STOP, et PGCD(3471,1239) = d34
= 3.
Figure 1 pour illustrer de manière dynamique
l'algorithme des différences finies :
Pour choisir les dimensions
entières du rectangle: saisissez à la souris le point M ;
pour dessiner la pièce carrée suivante: touche G ; pour
sortir du mode trace: touche Echap
2 - L'algorithme d'Euclide,
variante accélérée de l'algorithme des différences
finies :
L'algorithme d'Euclide, qui est lui aussi programme du collège, permet
d'accélérer la procédure précédente de recherche du PGCD de
deux nombres. L'idée est d'éviter les répétitions de différence par
une division euclidienne.
Cet algorithme est entièrement construit sur un
corollaire du
lemme précédent : si
d divise a et b, alors il divise a-b, et par récurrence a-nb pour tout entier
n,
en particulier il divise a-qb=r où q est le quotient et r le reste
de la division euclidienne de a par b.
Géométriquement, le nombre d'itérations économisées est directement
liée au nombre de répétitions de pièces carrées de même
taille. Le tableau ci-dessous présente la mise en œuvre
de l'algorithme d'Euclide pour
la recherche de PGCD(3471,1239).
Il s'agit cette fois de faire des divisions euclidiennes ai
= bi
qi
+ ri
partant de a0=3471 et de b0=1239
, et de poser ensuite a1= b0
et b1= r0
, et par la suite ai+1= bi
et bi+1= ri
tant que ri
n'est pas nul. Le PGCD est le dernier reste non nul.
i
ai
bi
qi
ri
test
d'arrêt: ri
= 0 ?
0
3471
1239
2
993
r0
= 993>0, on continue
1
1239
993
1
246
r1
= 246>0, on continue
2
993
246
4
9
r2
= 9>0, on continue
3
246
9
27
3
r3
= 3>0, on continue
4
9
3
3
0
r4
= 0: STOP, et PGCD(3471,1239) = r3
= 3
On peut de plus remarquer que la traduction algébrique du puzzle
de forme rectangulaire et à pièces carrées est :
a0 b0=Si
qi ci²,
ce qui donne dans
notre exemple: 3471´1239 = 2´1239²+1´993²+4´246²+27´9²+3´3²
On en déduit que l'entier a0´b0
est un nombre entier décomposable en
somme de carrés. Le thème de la décomposition de nombres entiers en somme
de carrés a suscité des développements arithmétiques parfois ardus ayant
un lien très étroit avec la théorie des formes quadratiques.
3
- Les fractions continuées,
généralisation aux irrationnels des deux algorithmes précédents:
Soit x un irrationnel.
L'algorithme des fractions continuées permet de construire une suite de rationnels,
dite suite des réduites:
- qui
converge vers l'irrationnel x plus rapidement que la suite des décimaux
obtenus par troncature du développement décimal de x après la nième
décimale de x, et, comme chacun sait, les approximations les plus
courtes sont les meilleures;
- qui présente, entre autres intérêts théoriques,
celui de ne pas dépendre de la base dans laquelle on travaille.
Le procédé nécessite la construction de deux suites annexes et entremêlées:
l'une q, prend ses valeurs dans N*
, l'autre, e, prend ses valeurs dans {x}U
] 0 1]
- Q.
On pose e(0)= x , puis q(0)=E(x)=partie entière de x, puis on cherche
à approcher l'erreur e(1)=x-E(x)=e(0)-q(0).
Cette erreur e(1) est irrationnelle, est strictement supérieure à 0 et
est inférieure strictement à l'unité, donc son inverse 1/e(1) est un
irrationnel supérieur strictement à l'unité. On pose q(1)= E(1/e(1)),
qui est bien dans N*
, et la nouvelle erreur irrationnelle à estimer est : e(2)=
1/e(1)-q(1), et ainsi de suite.
La suite des réduites, dont
les premiers termes sont
,
,
,
, et dont le terme général est
converge vers x.
La suite q devient plus intelligible lorsque on la
relie à (et la relit comme une nouvelle application de) notre algorithme
géométrique de partition en carrés d'un rectangle dont
la proportion Longueur/largeur est égale à x. Seule la
proportion du rectangle est importante: tout rectangle semblable pourrait aussi-bien
faire l'affaire, même si dans la pratique on ne prendra que des
rectangles homothétiques au rectangle dont les côtés sont parallèles
aux axes du repère orthonormé. L'idée des fractions continuées est donc
strictement la même que pour l'algorithme des différences finies: découper un rectangle en des pièces carrées en se contraignant à
chaque nouveau découpage à obtenir une nouvelle pièce carrée aussi
grande que possible, et en évitant de gâcher de la surface en
"chutes". Le nombre de grandes pièces carrées est q(1), le
nombre de pièces carrées de deuxième grandeur est q(2), etc...On
comprend dès lors à quoi correspond les n inversions algébriques de
la définition de x(n): ce sont les n "basculements" des
rectangles successifs qu'il reste à découper, ou encore les n tailles
différentes des pièces carrées utilisées jusqu'à ce point.
Nous avons découvert cette représentation des fractions
continuées avec Mathématique,
informatique et enseignement de Jacqueline Zizi. Une belle caractérisation géométrique du nombre d'or
est démontrée par
Jean Barbé et Renaud Palisse (bulletin n°408 de l'APMEP, pp. 38 à 42)
dans un article intitulé "la quadrature du rectangle": il y a
basculement à chaque étape, c'est-à-dire un exemplaire unique de
chaque pièce carrée. Autrement dit, le nombre d'or limite
l'accélération de l'algorithme des fractions continuées.
Des résultats plus généraux peuvent être établis sur les suites q qui
sont périodiques ou périodiques à partir d'un certain rang: Théorème
(Lagrange, 1768). Le développement en fraction continuée d'un
irrationnel x est périodique à partir d'un certain rang si et
seulement si x est un irrationnel racine d'un polynôme de degré 2 à
coefficients entiers (ou rationnel, ce qui revient au même, quitte à
multiplier par le PGCD des dénominateurs des coefficients).
On dit qu'un tel x
est irrationnel quadratique. Et : Théorème
: Les réels admettant un développement périodique dont la période
commence dès le premier rang sont exactement les
irrationnels quadratiques x > 1 dont le conjugué radical est élément
de ]-1,0[.
On dit qu'un tel x est irrationnel
quadratique réduit.
Figure 2 pour illustrer de manière dynamique
l'algorithme des fractions continuées:
Vous pouvez redimensionner le rectangle en pilotant à la souris le
point I, puis en appuyant sur la touche I.
Appuyez sur la touche G pour obtenir une nouvelle
pièce carrée. Pour sortir du mode trace: toucheEchap.
Appuyez sur la touche P pour obtenir un rectangle d'or puis G
plusieurs fois pour comprendre que la suite q est constante égale à 1
pour le nombre d'or; touche
Echap pour sortir du mode trace.
Pour faire apparaître ou disparaître des instructions relatives au
théorème de Lagrange, appuyez sur la touche T;
pour
régler la période, appuyez sur la touche Q ou R,
puis les flèches du clavier, puis de nouveau Q ou R.
Remarque théorique importante: en pilotant le point I à la
souris, on ne fait que des affectations décimales; pour forcer une
affectation irrationnelle, double-cliquez sur la figure, pour utiliser
l'item Piloter/placer un point par coordonnées: vous saisirez
alors les coordonnées souhaitées pour le point I.
Pour se familiariser avec
le théorème de Lagrange:
- période de longueur 1 : si pour x irrationnel q(n) = q(0) pour
tout n, alors x=q(0)+1/x, donc x²-q(0)x-1=0; on retrouve au
passage le polynôme associé au nombre d'or si q(0)=1, qui est le plus
simple des irrationnels quadratiques réduits.
- période de longueur 2: voir texte de la figure ci-dessus. Au
passage, le polynôme est x²-q(1) x -q(1)/q(0)=0, et ce polynôme coïncide
avec le précédent lorsque q(1)=q(0).
C'est un bon exercice préparatoire à la compréhension de ces théorèmes
que de rechercher le polynôme de degré 2, dont les coefficients sont
fonctions de trois paramètres q(0),q(1),et q(2), qui s'annule pour x
tel que q(3n)=q(0), q(3n+1)=q(1) et q(3n+2)=q(2) pour tout entier n.
La démonstration des deux théorèmes ci-dessus est présentable à une
leçon d'agrégation (cf.par exemple http://www.infty08.net/dudeFraCont.pdf.)
L'interprétation géométrique de l'algorithme des fractions continuées
permet de montrer que
:
- la suite xn
converge effectivement vers x; plus précisément,
la suite x2n croît vers x et la suite x2n+1 décroît
vers x;
- pour x=b/a rationnel, c'est-à-dire
si a et b sont commensurables, l'algorithme s'arrête au bout d'un
nombre fini d'itérations: il existe un rang n pour lequel l'erreur
e(n)=0.
La preuve de ces deux résultats est laissée en exercice au
lecteur; indication: construire à rebours le puzzle dont on néglige les pièces carrées
au delà du n+1ième terme, et en prenant
par exemple 1 pour le côté du carré du nième ordre de
grandeur : xn n'est autre que la proportion rationnelle du
rectangle obtenu, ou son inverse - nous n'avons pas encore clairement défini
si une proportion est le rapport longueur/largeur, mais il y a un lien
très simple entre le développement en fractions continuées d'un
nombre et de son inverse... On laisse également au lecteur retrouver
comment exprimer la nième réduite xn ; indication:
aller fouiller dans le texte de la figure ci-dessous.
Figure
3 pour obtenir la suite des réduites d'un nombre x
Ci-dessous, vous pouvez obtenir les premiers éléments de la suite
des réduites pour x =
(touche P),
pour x= π (touche 2), pour x= 3471/1239 (touche 3),
pour x quelconque (touche X, puis flèches du clavier).
Pour piloter le rang N de la réduite affichée: touche N
; au delà d'un certain rang, les affichages disparaissent, ou
deviennent négatifs;
le nombre de chiffres exacts d'un entier que gère Géoplan n'est pas
illimité ! Pour voir apparaître le rang limite, au-delà
duquel les valeurs de la suite q ne sont plus fiables, appuyez
sur la touche T : un tableau de valeurs de la suite Q
apparaît; la première valeur dont l'affichage nécessite un
exposant marque le rang en deçà duquel les résultats sont
fiables. Remarque théorique
importante: en pilotant le nombre x à la souris, on ne fait
que des affectations décimales; pour forcer une affectation
irrationnelle, double-cliquez sur la figure, pour utiliser
l'item Piloter/Affecter une variable numérique libre:
vous saisirez alors la valeur souhaitée pour le réel x.
Remarques :
- Si a et b ne sont pas
commensurables, la traduction du puzzle (infini, voir figure 2) n'est plus
arithmétique, mais analytique: ab = Si
qi ci²
(sommation infinie).
- L'outil matriciel (avec des matrices (2,2)) permet
également d'évaluer la suite des réduites; ce même outil matriciel
peut également être utile pour comprendre la fin du paragraphe suivant.
Voyons de quoi il s'agit.
4 - Fractions continuées et suite de
Stern-BrocotL'algorithme des
fractions continuées est étroitement lié à une suite de rationnels (xn),
dite suite de Stern -Brocot
,
construite suivant un procédé très simple et astucieux, qui utilise, entre
autres choses, le fait que si on se donne deux fractions réduites
positives
rangées
<
, alors on a l'encadrement <
<
, et la fraction intercalée est aussi sous forme réduite.
Cette suite (xn)
construit directement
une bijection entre Q* et N*
: Stern, un mathématicien allemand, et Brocot, un horloger français,
ont semble-t-il indépendamment publié respectivement en 1858 et 1860
l'algorithme suivant, présentable sous forme d'arbre ou ici de "tableau
générationnel".
La "génération 0" contient les deux bornes
de Q*, à
savoir 0 et +∞ sous "forme réduite".
génération G0
G1
x1
G2
x2
x3
G3
x4
x5
x6
x7
G4
x8
x9
x10
x11
x12
x13
x14
x15
etc...
Chacun des 2i-1
nouveaux arrivants xj ( 2i-1 j<2i ) de la génération Gi
a pour numérateur la somme des numérateurs de ses deux voisins
et pour dénominateur la somme de leurs dénominateurs.
Par exemple, x22=(2+3)/(3+4)=5/7
Ce procédé produit un
tableau (ou arbre) de rationnels compris entre 0 et 1 dans la partie gauche et de
leurs inverses, compris entre 1 et l'infini, dans la partie droite.
L'algorithme donne sans équivoque un sens au concept de "rationnel
suivant", ce qui déjà n'est pas une mince affaire, mais fait
encore beaucoup mieux, puisque l'on a les trois propriétés
1- Toutes les fractions sont
sous forme réduite ; 2-
La suite (xn)
ainsi définie ne passe pas deux fois par le même rationnel.
3-
La suite (xn)
ainsi définie recouvre entièrement Q*.
Ces résultats sont démontrés dans Concrete
Mathematics,
de Graham, Knuth et Patashnik (en anglais).
Ils établissent donc de manière constructive la dénombrabilité de
l'ensemble des rationnels.
Il y a un lien très étroit entre la suite de
Stern-Brocot et l'algorithme des fractions continuées. En effet, si, partant de x1 , et descendant vers xN,
on doit dans l'ordre faire a0
saut(s) vers la droite, puis a1
saut(s) vers la gauche, puis a2
saut(s) vers la droite, et ainsi de suite jusqu'à a2n+1
saut(s) vers la gauche, alors le développement en fractions continuées
de xN est: (a0,a1,a2,...,a2n+1, 1);
autrement dit,
démonstration là encore dans Concrete Mathematics.
Par exemple, pour descendre de x1 sur x22
=5/7, on passe par x2 puis x5 puis x11,
autrement dit on doit dans l'ordre
faire a0=0 saut vers la
droite, puis a1 = 1 saut
vers la gauche, puis a2
= 2 sauts vers la droite, puis a3
= 1 saut vers la gauche, et on peut vérifier que
.
Une curiosité : Euler a prouvé que le nombre e était la limite du
cheminement suivant dans l'arbre de Stern-Brocot: D1G0D1G1D1G2D1G3D1G4D1G5D1
....etc où D1 symbolise un
saut vers la droite et Gk
k sauts vers la gauche; en fait, G et D peuvent être comprise comme
deux matrices (2,2), cf. Concrete Mathematics.