Kettingbreuk

In de wiskunde is een kettingbreuk een uitdrukking van de vorm:

${\displaystyle a_{0}+{\cfrac {b_{1}}{a_{1}+{\cfrac {b_{2}}{a_{2}+{\cfrac {b_{3}}{a_{3}+\,\cdots }}}}}}}$,

waarin ${\displaystyle a_{0}}$ een willekeurig geheel getal is en alle overige getallen ${\displaystyle a_{i}}$ en ${\displaystyle b_{j}}$ positieve gehele getallen zijn.

Een enkelvoudige of reguliere kettingbreuk is een uitdrukking van de vorm

${\displaystyle a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots \,}}}}}}}}}$,

dus een kettingbreuk waarin alle ${\displaystyle b_{j}=1}$ zijn.

De reguliere kettingbreuken vormen een eenduidige voorstelling van de reële getallen. Daarbij tellen de eindige reguliere kettingbreuken niet eindigend met een noemer 1, dat wil zeggen kettingbreuken in kanonieke vorm, mee.

Voorbeelden

Het eenvoudigste voorbeeld van een oneindige kettingbreuk is die voor het gulden getal ${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}618}$:

${\displaystyle \varphi =1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+\,\cdots }}}}}}}$

Een ander voorbeeld is de uitdrukking voor de boogtangensfunctie:

${\displaystyle \arctan(z)={\cfrac {z}{1+{\cfrac {z^{2}}{3+{\cfrac {4z^{2}}{5+{\cfrac {9z^{2}}{7+{\cfrac {16z^{2}}{9+{\cfrac {25z^{2}}{\ddots \,}}}}}}}}}}}}}$

Notatie

Een kettingbreuk in kanonieke vorm is geheel bepaald door de getallen ${\displaystyle a_{0},a_{1},a_{2},a_{3},\dots }$ Er zijn verscheidene notaties bedacht om kettingbreuken eenvoudiger te noteren dan op de omslachtige manier als een echte breuk. Oskar Perron introduceerde in zijn boek Die Lehre von den Kettenbrüchen de volgende veel gebruikte notatie:

${\displaystyle [a_{0};a_{1},a_{2},a_{3},\ldots ]}$

In deze notatie wordt de gulden snede ${\displaystyle \varphi =[1;1,1,1,\dots ]}$.

Een andere notatie, van de hand van Pringsheim, is:

${\displaystyle a_{0}+{\frac {1\mid }{\mid a_{1}}}+{\frac {1\mid }{\mid a_{2}}}+{\frac {1\mid }{\mid a_{3}}}+\dots }$

Verwant daarmee is:

${\displaystyle a_{0}+{1 \over a_{1}+}{1 \over a_{2}+}{1 \over a_{3}+}\dots }$

Theorie

Reële getallen kunnen eenduidig geschreven worden als kettingbreuken in kanonieke vorm, gegeven door een al dan niet eindige rij gehele getallen ${\displaystyle a_{0},a_{1},a_{2},a_{3},\dots }$, waarvan alle termen, behalve eventueel ${\displaystyle a_{0}}$, groter dan of gelijk aan 1 zijn. Rationale getallen hebben een eindige voorstelling: ${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ,a_{n}]}$ met ${\displaystyle a_{n}\geq 2}$ en irrationale getallen een oneindige: ${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ]}$.

De indeling in getallen met oneindige en eindige representatie is daarmee fundamenteler dan bij een schrijfwijze met een geheel getal, een komma en cijfers achter de komma, waar die indeling van het grondtal afhangt. Bij een kettingbreuk zijn ook de getallen in de representatie, los van hun eigen schrijfwijze, onafhankelijk van een grondtal.

De gedachte achter de kettingbreuk is dat een reëel getal de som is van een geheel getal en een reëel getal van 0 of meer, maar kleiner dan 1. Als dit deel niet 0 is kan het geschreven worden als 1 gedeeld door een reëel getal groter dan 1. Voor dit laatste getal geldt weer hetzelfde. Enzovoort. Zo ontstaat een kettingbreuk. Er geldt dus

${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ]=a_{0}+1/[a_{1};a_{2},a_{3},\dots ]}$

${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ,a_{n}]=a_{0}+1/[a_{1};a_{2},a_{3},\dots ,a_{n}],\ n\geq 1}$

${\displaystyle [a_{0};]=a_{0}}$

Schrijf als voorbeeld 0,345 als een kettingbreuk:

${\displaystyle 0{,}345=0+{\frac {345}{1000}}}$

${\displaystyle {\frac {1000}{345}}=2+{\frac {310}{345}}}$

${\displaystyle {\frac {345}{310}}=1+{\frac {35}{310}}}$

${\displaystyle {\frac {310}{35}}=8+{\frac {30}{35}}}$

${\displaystyle {\frac {35}{30}}=1+{\frac {5}{30}}}$

${\displaystyle {\frac {30}{5}}=6}$

Dus 0,345 = [0;2,1,8,1,6]

De berekening heeft een overeenkomst met het algoritme van Euclides voor het bepalen van de grootste gemene deler en kan als volgt worden weergegeven:

1000  0
 345  2
 310  1
  35  8
  30  1
   5  6
   0

De getallen in de linkerkolom worden het langzaamst kleiner en de kettingbreuk het langst als in de rechterkolom steeds lage getallen, en vooral enen, staan. Dit is het geval bij breuken in de buurt van ${\displaystyle \varphi }$, dus ook bijvoorbeeld bij ${\displaystyle \varphi -1.}$ De getallen in de linkerkolom worden dan steeds door ongeveer ${\displaystyle \varphi }$ gedeeld. Het kan dan dat er voor iedere factor 10 in de orde van grootte van de noemer vijf extra niveaus nodig zijn. De kettingbreuk voor het getal 0,62 heeft bijvoorbeeld 8 niveaus en is [0; 1, 1, 1, 1, 1, 2, 2].

Een algemeen rekenschema voor willekeurige reële getallen is analoog aan het algoritme van Euclides:

getal 1/fractie				geheel deel		fractie
0,345				0		0,345
1/0,345	=	2,898550725		2		0,898550725
1/0,898550725	=	1,112903226		1		0,112903226
1/0,112903226	=	8,857142857		8		0,857142857
1/0,857142857	=	1,166666667		1		0,166666667
1/0,166666667	=	6		6		0

Ordening

De lexicografische volgorde van getallen en van hun weergave als kettingbreuk komen overeen. Daarbij moet in de weergave als kettingbreuk op de oneven posities de volgorde worden omgekeerd en met een blanco positie na een even kolom worden gerekend alsof daar oneindig staat. Het is op die manier mogelijk getallen geschreven als kettingbreuken te sorteren zonder ze uit te schrijven.

Voorbeelden tussen 0 en 1, waaronder alle breuken met noemer tot en met 10, in stijgende volgorde:

[0;]                                   = 0
[0; 10]                                = 0,1
[0; 9, 11]                             = 0,11
[0; 9]                                 ${\displaystyle \approx }$ 0,1111
[0; 8, 3]                              = 0,12
[0; 8]                                 = 0,125
[0; 7, 1, 2, 4]                        = 0,13
[0; 7, 7]                              = 0,14
[0; 7, 15, 1, 292, 1, ..]              ${\displaystyle \approx }$ 0,1416 (π-3)
[0; 7]                                 ${\displaystyle \approx }$ 0,1429
[0; 6, 1, 2]                           = 0,15
[0; 6, 4]                              = 0,16
[0; 6]                                 ${\displaystyle \approx }$ 0,1667
[0; 5, 1, 7, 2]                        = 0,17
[0; 5, 1, 1, 4]                        = 0,18
[0; 5, 3, 1, 4]                        = 0,19
[0; 5]                                 = 0,2
[0; 4, 2]                              ${\displaystyle \approx }$ 0,2222
[0; 4]                                 = 0,25
[0; 3, 2]                              ${\displaystyle \approx }$ 0,2857
[0; 3, 3]                              = 0,3
[0; 3]                                 ${\displaystyle \approx }$ 0,3333
[0; 2, 1, 8,  1, 6]                    = 0,345
[0; 2, 1, 2]                           = 0,375
[0; 2, 2]                              = 0,4
[0; 2, 2, 3, 1, 1, 2]                  = 0,41
[0; 2, 3]                              ${\displaystyle \approx }$ 0,4286
[0; 2, 3, 14]                          = 0,43
[0; 2, 4]                              ${\displaystyle \approx }$ 0,4444
[0; 2]                                 = 0,5
[0; 1, 1, 4]                           ${\displaystyle \approx }$ 0,5556
[0; 1, 1, 3]                           ${\displaystyle \approx }$ 0,5714
[0; 1, 1, 2]                           = 0,6
[0; 1, 1, 1, 1, 3, 2, 2]               = 0,61
[0; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5]   = 0,618
[0; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,.] ${\displaystyle \approx }$ 0,6180 (φ-1)
[0; 1, 1, 1, 1, 1, 2, 2]               = 0,62
[0; 1, 1, 1, 2]                        = 0,625
[0; 1, 2]                              ${\displaystyle \approx }$ 0,6667
[0; 1, 2, 3]                           = 0,7
[0; 1, 2, 2]                           ${\displaystyle \approx }$ 0,7143
[0; 1, 2, 1, 1, 4,..]                  ${\displaystyle \approx }$ 0,7183 (e-2)
[0; 1, 3]                              = 0,75
[0; 1, 3, 2]                           ${\displaystyle \approx }$ 0,7778
[0; 1, 4]                              = 0,8
[0; 1, 5]                              ${\displaystyle \approx }$ 0,8333
[0; 1, 6]                              ${\displaystyle \approx }$ 0,8571
[0; 1, 7]                              = 0,875
[0; 1, 8]                              ${\displaystyle \approx }$ 0,8889
[0; 1, 9]                              = 0,9
[1;]                                   = 1

Convergenten

Als we een eindige kettingbreuk voor het einde afbreken of een oneindige kettingbreuk afbreken vormt de zo ontstane kettingbreuk een benadering van de gehele kettingbreuk. Men noemt zo'n eindig deel een convergent. De ${\displaystyle n}$-de convergent is de kettingbreuk:

${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{n}]}$.

Een convergent is een rationaal getal, omdat het een eindige kettingbreuk is.

De successievelijke convergenten vormen een rij breuken die steeds beter de kettingbreuk benaderen. De convergenten, op de eventuele laatste na, met even rangnummer zijn kleiner dan de kettingbreuk en die met oneven rangnummer groter. Wanneer kettingbreuken die eindigen met een noemer 1 worden herschreven in kanonieke vorm, dus een niveau korter worden, is aan een eindresultaat niet te zien of het rangnummer van de convergent even of oneven is.

Voor het gulden getal:

${\displaystyle \varphi =[1;1,1,1,\dots ]}$,

zijn de eerste convergenten:

${\displaystyle [1]=1}$

${\displaystyle [1;1]=2}$

${\displaystyle [1;1,1]={\frac {3}{2}}=1{,}5}$

${\displaystyle [1;1,1,1]={\frac {5}{3}}\approx 1{,}67}$

${\displaystyle [1;1,1,1,1]={\frac {8}{5}}=1{,}6}$

De opeenvolgende tellers en noemers vormen de rij van Fibonacci.

Een convergent is een breuk, en wel is voor ${\displaystyle n=0,1,2,\ldots }$ de ${\displaystyle n}$-de convergent van de vorm:

${\displaystyle {\frac {p_{n}}{q_{n}}}}$

die kan worden berekend met de recurrente betrekkingen:

${\displaystyle p_{n}=a_{n}\cdot p_{n-1}+p_{n-2}}$

${\displaystyle q_{n}=a_{n}\cdot q_{n-1}+q_{n-2}}$

Daarbij gelden als startwaarden:

${\displaystyle p_{-2}=0,\ p_{-1}=1,\ q_{-2}=1,\ q_{-1}=0}$.

Beste benaderingen van de eerste en tweede soort

In dit verband wordt een niet te vereenvoudigen breuk met positieve noemer als benadering van een reëel getal een beste benadering van de eerste soort genoemd als de absolute waarde van de afwijking kleiner is dan bij elke andere breuk met een kleinere of gelijke positieve noemer en een beste benadering van de tweede soort als zelfs de absolute waarde van de afwijking vermenigvuldigd met de noemer kleiner is dan bij elke andere breuk met een kleinere of gelijke, positieve noemer. Dit laatste is een sterkere eigenschap.

De convergenten van een reëel getal die geen geheel getal zijn vormen de beste benaderingen van de tweede soort die geen geheel getal zijn.^[1]

Er kunnen behalve de convergenten wel meer beste benaderingen van de eerste soort zijn. Dit geldt in ieder geval als de laatste noemer van de kettingbreuk van een convergent wordt verlaagd tot een waarde die meer dan de helft van de oorspronkelijke is. Dit geeft bijvoorbeeld 2/3 = [0;1,2] als benadering voor 3/4 = [0;1,3]), en soms ook als deze wordt gehalveerd (bijvoorbeeld 1/2 = [0;2] = [0;1,1] als benadering voor 7/10 = [0;1,2,3]).

Wortel 2 kan op deze manier worden benaderd.

Eindige kettingbreuken

De uitgeschreven notatie van de kanonieke vorm een eindige kettingbreuk is van de vorm:

${\displaystyle a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+_{\ddots {\cfrac {1}{a_{n}}}}}}}}}$,

waarin ${\displaystyle a_{n}\neq 1}$.

Een eindige kettingbreuk is vanzelfsprekend een rationaal getal, maar omgekeerd laat ook elk rationaal getal zich als eindige kettingbreuk schrijven. Dat kan men inzien door de breuk ${\displaystyle a/b}$ met ${\displaystyle a<b}$ te bekijken en daarbij voor het gemak ${\displaystyle a_{0}=0}$ te kiezen. Door delen vinden we:

${\displaystyle b=qa+r}$

met ${\displaystyle r<a}$. Dus is:

${\displaystyle {\frac {a}{b}}={\frac {1}{\frac {b}{a}}}={\frac {1}{q+{\frac {r}{a}}}}}$

Daarin komt de breuk ${\displaystyle r/a}$ voor, waarvoor we hetzelfde doen als voor ${\displaystyle a/b}$. Dit gaat in een eindig aantal stappen, omdat steeds de volgende noemers kleiner zijn dan de vorige. Als voorbeeld:

${\displaystyle {\frac {3}{8}}={\frac {1}{\tfrac {8}{3}}}={\cfrac {1}{2+{\tfrac {2}{3}}}}={\cfrac {1}{2+{\cfrac {1}{\tfrac {3}{2}}}}}={\cfrac {1}{2+{\cfrac {1}{1+{\tfrac {1}{2}}}}}}}$

We kunnen dus schrijven: ${\displaystyle {\frac {3}{8}}=[0;2,1,2]}$

Er geldt:

${\displaystyle [a_{0};a_{1}]=a_{0}+{\frac {1}{a_{1}}}}$

${\displaystyle [a_{0};a_{1},a_{2}]=a_{0}+{\frac {a_{2}}{a_{1}a_{2}+1}}}$

${\displaystyle [a_{0};a_{1},a_{2},a_{3}]=a_{0}+{\frac {a_{2}a_{3}+1}{a_{1}a_{2}a_{3}+a_{1}+a_{3}}}}$

Oneindige kettingbreuken

Een oneindige kettingbreuk is gezien het bovenstaande een irrationaal getal. Omgekeerd laat ook elk irrationaal getal zich schrijven als oneindige kettingbreuk. De oneindige kettingbreuken laten zich nog opdelen in periodieke en aperiodieke kettingbreuken.

De meeste irrationale getallen hebben geen periodieke of anderszins regelmatige kettingbreukontwikkeling. Alexander Khinchin bewees echter dat voor bijna alle reële getallen, voor alle reële getallen behalve een verzameling met maat nul, het meetkundige gemiddelde van de eerste ${\displaystyle n}$ ${\displaystyle a}$'s uit de kettingbreuk voor ${\displaystyle n}$ naar oneindig één bepaalde limiet heeft, nu bekend als de constante van Khinchin, ${\displaystyle K\approx 2{,}6854520010\ldots }$. Paul Lévy toonde aan dat de ${\displaystyle n}$-de-machtswortels uit de noemers van de ${\displaystyle n}$-de convergenten van bijna alle reële getallen convergeren naar dezelfde limiet, die daarom ook de constante van Lévy wordt genoemd.

Periodieke oneindige kettingbreuken

Een periodieke oneindige kettingbreuk stelt een irrationaal algebraïsch getal voor, dat een oplossing is van een vierkantsvergelijking met gehele coëfficiënten. Omgekeerd kan elke zodanige oplossing als periodieke oneindige kettingbreuk worden voorgesteld.

Patronen in aperiodieke oneindige kettingbreuken

Het is fascinerend dat sommige aperiodieke oneindige kettingbreuken toch regelmatige patronen vertonen.

Zo is de kettingbreukontwikkeling voor ${\displaystyle e}$

${\displaystyle e=[2;1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,\dots ]}$

En voor elk natuurlijk getal ${\displaystyle n>1}$ is:

${\displaystyle \exp({\tfrac {1}{n}})=[1;n-1,1,1,3n-1,1,1,5n-1,1,1,7n-1,\dots ]}$

De ontwikkeling voor het gulden getal ${\displaystyle \varphi }$ is als volgt:

${\displaystyle \varphi =[1;1,1,1,1,\dots ]}$

Voor de tangens geldt:

${\displaystyle \tan(1)=[1;1,1,3,1,5,1,7,1,9,1,11,1,13,1,15,\dots ]}$

Voor elk natuurlijk getal ${\displaystyle n>1}$:

${\displaystyle \tan({\tfrac {1}{n}})=[0;n-1,1,3n-2,1,5n-2,1,7n-2,\dots ]}$

en ook:

${\displaystyle \tanh({\tfrac {1}{n}})=[0;n,3n,5n,7n,9n,11n,13n,17n,19n,\dots ]}$

Aparte vermelding verdient de kettingbreuk:

${\displaystyle S=[1;2,3,4,5,6,7,\dots ]}$,

de voorstelling van

${\displaystyle S={\frac {I_{0}(2)}{I_{1}(2)}}}$,

waarin ${\displaystyle I_{n}}$ de gemodificeerde Besselfunctie van de eerste soort is.

Het getal pi

Het begin van de kettingbreuk voor ${\displaystyle \pi }$ is [3; 7, 15, 1, 292, 1, 1, ...]. De successieve benaderingen zijn: 3, 22/7, 333/106, 355/113. Van deze laatste, [3; 7, 15, 1] = 355/113 = 3,14159292035..., zijn de eerste zes decimalen correct.

Deze reguliere kettingbreukontwikkeling voor ${\displaystyle \pi }$ vertoont geen enkel regelmatig patroon. De beide volgende ontwikkelingen met algemene kettingbreuken daarentegen zijn wel regelmatig:

${\displaystyle \pi ={\cfrac {4}{1+{\cfrac {1}{3+{\cfrac {4}{5+{\cfrac {9}{7+{\cfrac {16}{9+{\cfrac {25}{11+{\cfrac {36}{13+{\cfrac {49}{\ddots }}}}}}}}}}}}}}}}}$

en:

${\displaystyle \pi =3+{\cfrac {1}{6+{\cfrac {9}{6+{\cfrac {25}{6+{\cfrac {49}{6+{\cfrac {81}{6+{\cfrac {121}{\ddots }}}}}}}}}}}}}$

voetnoten

1. De beste benaderingen van de tweede soort in het geval van een geheel getal (deze komen dan trouwens overeen met de beste benaderingen van de eerste soort), zijn één getal dat de enige gehele convergent is (de "nulde") of een van de twee gehele convergenten (de "nulde" en de "eerste"), of twee getallen waarvan een de enige gehele convergent is (de "nulde").

websites

• MathWorld. Continued Fraction.