Het benaderen van irrationale getallen door rationale. Vakantiecursus Wiskunde 2012

Het benaderen van irrationale getallen door ‘rationale.’ Vakantiecursus Wiskunde 2012 Cor Kraaikamp

August 24, 2012

Cor Kraaikamp ()

Het benaderen van irrationale getallen door ‘rationale.’ Vakantiecursus Wiskunde August 201224, 2012

1 / 64

Decimale ontwikkelingen

Iedereen weet dat

1 = 0.33333 · · · 333333333 . . . , 3 maar wat wil dit ook al weer zeggen? . . . en wat bedoelen we ook al weer met 1 = 0.25, 4

1 = 0.125, 8

1 = 0.142857142 · · · 7

en wat gebeurt er met deze laatste ontwikkeling? Is deze eindig, oneindig? . . . en als zij oneindig is, op wat voor manier?

Cor Kraaikamp ()


2 / 64


Iedereen weet dat


1 = 0.125, 8

1 = 0.142857142 · · · 7


Cor Kraaikamp ()


2 / 64


Iedereen weet dat


1 = 0.125, 8

1 = 0.142857142 · · · 7


Cor Kraaikamp ()


2 / 64


Iedereen weet dat


1 = 0.125, 8

1 = 0.142857142 · · · 7


Cor Kraaikamp ()


2 / 64


Iedereen weet dat


1 = 0.125, 8

1 = 0.142857142 · · · 7


Cor Kraaikamp ()


2 / 64


Iedereen weet dat


1 = 0.125, 8

1 = 0.142857142 · · · 7


Cor Kraaikamp ()


2 / 64


Iedereen weet dat


1 = 0.125, 8

1 = 0.142857142 · · · 7


Cor Kraaikamp ()


2 / 64


Iedereen weet dat


1 = 0.125, 8

1 = 0.142857142 · · · 7


Cor Kraaikamp ()


2 / 64


In het algemeen bedoelen we dat als de decimale ontwikkeling van een getal x ∈ R gelijk is aan x = a0 .a1 a2 a3 . . . met a0 ∈ Z en an ∈ {0, 1, 2, . . . , 9}, dat: x = a0 +

Cor Kraaikamp ()

∞ X an . n 10 n=1


3 / 64



Cor Kraaikamp ()

∞ X an . n 10 n=1


3 / 64



Cor Kraaikamp ()

∞ X an . n 10 n=1


3 / 64


Hoe komen we aan zoiets? En hoe kunnen we zien dat de decimale ontwikkeling van rationale getallen x ∈ Q eindig of eventueel periodiek (maar wel oneindig) is?

Cor Kraaikamp ()


4 / 64


Hoe komen we aan zoiets? En hoe kunnen we zien dat de decimale ontwikkeling van rationale getallen x ∈ Q eindig of eventueel periodiek (maar wel oneindig) is?

Cor Kraaikamp ()


4 / 64


Om met de laatste vraag te beginnen: door te delen!! Als we een gewone staartdeling doen (zoals ik – als “oude man” – vroeger op school kreeg), dan krijgen we in de deling “vanzelf” twee keer dezelfde rest (er zijn maar eindig veel mogelijkheden, nietwaar ...). Voor de eerste vraag gebruiken we de volgende afbeelding T10 : [0, 1) → [0, 1), gedefinieerd door: T10 (x) = 10x − b10xc.

Cor Kraaikamp ()


5 / 64



Cor Kraaikamp ()


5 / 64



Cor Kraaikamp ()


5 / 64


Als x ∈ [0, 1), zet dan n−1 an = an (x) = b10T10 (x)c,

dan zijn de ‘digits’ an ∈ {0, 1, 2 . . . , 9}, en geldt er: T10 (x) = 10x − a1 en dus zien we dat x=

Cor Kraaikamp ()

⇔

10x = a1 + T10 (x)

a1 1 + T10 (x) 10 10


6 / 64




Cor Kraaikamp ()

⇔

10x = a1 + T10 (x)

a1 1 + T10 (x) 10 10


6 / 64




Cor Kraaikamp ()

⇔

10x = a1 + T10 (x)

a1 1 + T10 (x) 10 10


6 / 64




Cor Kraaikamp ()

⇔

10x = a1 + T10 (x)

a1 1 + T10 (x) 10 10


6 / 64

Decimale ontwikkelingen Omdat 2 T10 (x) = T10 (T10 (x)) = 10T10 (x) − a2

volgt er T10 (x) =

a2 1 2 + T10 (x). 10 10

Simpelweg invullen geeft dan x=

1 a1 a2 1 2 a1 + T10 (x) = + + 2 T10 (x) 10 10 10 102 10

Zo doorgaand vinden we dus: x=

Cor Kraaikamp ()

a1 a2 an 1 n + 2 + · · · + n + n T10 (x). 10 10 10 10


7 / 64


volgt er T10 (x) =

a2 1 2 + T10 (x). 10 10


a1 1 a1 a2 1 2 + T10 (x) = + + 2 T10 (x) 10 10 10 102 10


Cor Kraaikamp ()

a1 a2 an 1 n + 2 + · · · + n + n T10 (x). 10 10 10 10


7 / 64


volgt er T10 (x) =

a2 1 2 + T10 (x). 10 10


a1 1 a1 a2 1 2 + T10 (x) = + + 2 T10 (x) 10 10 10 102 10


Cor Kraaikamp ()

a1 a2 an 1 n + 2 + · · · + n + n T10 (x). 10 10 10 10


7 / 64


volgt er T10 (x) =

a2 1 2 + T10 (x). 10 10


a1 1 a1 a2 1 2 + T10 (x) = + + 2 T10 (x) 10 10 10 102 10


Cor Kraaikamp ()

a1 a2 an 1 n + 2 + · · · + n + n T10 (x). 10 10 10 10


7 / 64


volgt er T10 (x) =

a2 1 2 + T10 (x). 10 10


a1 1 a1 a2 1 2 + T10 (x) = + + 2 T10 (x) 10 10 10 102 10


Cor Kraaikamp ()

a1 a2 an 1 n + 2 + · · · + n + n T10 (x). 10 10 10 10


7 / 64


volgt er T10 (x) =

a2 1 2 + T10 (x). 10 10


a1 1 a1 a2 1 2 + T10 (x) = + + 2 T10 (x) 10 10 10 102 10


Cor Kraaikamp ()

a1 a2 an 1 n + 2 + · · · + n + n T10 (x). 10 10 10 10


7 / 64


Omdat 0≤

1 1 n T (x) < n 10n 10 10

volgt er: x = lim

n→∞

a2 a3 an 1 n a1 a2 a3 a1 + + + · · · + n + n T10 (x) = + + +· · · 10 100 1000 10 10 10 100 1000

oftewel, x=

Cor Kraaikamp ()

∞ X an . 10n n=1


8 / 64


Omdat 0≤

1 1 n T (x) < n 10n 10 10

volgt er: x = lim

n→∞

a1 a2 a3 an 1 n a3 a1 a2 + + + · · · + n + n T10 (x) = + + +· · · 10 100 1000 10 10 10 100 1000

oftewel, x=

Cor Kraaikamp ()

∞ X an . 10n n=1


8 / 64


Omdat 0≤

1 1 n T (x) < n 10n 10 10

volgt er: x = lim

n→∞

a1 a2 a3 an 1 n a3 a1 a2 + + + · · · + n + n T10 (x) = + + +· · · 10 100 1000 10 10 10 100 1000

oftewel, x=

Cor Kraaikamp ()

∞ X an . 10n n=1


8 / 64


Omdat 0≤

1 1 n T (x) < n 10n 10 10

volgt er: x = lim

n→∞

a1 a2 a3 an 1 n a3 a1 a2 + + + · · · + n + n T10 (x) = + + +· · · 10 100 1000 10 10 10 100 1000

oftewel, x=

Cor Kraaikamp ()

∞ X an . 10n n=1


8 / 64

Binaire ontwikkelingen

Merk op, dat dit ook werkt als de base niet gelijk is aan 10, maar aan 2, of 3, of 12, . . . Dit werkt eigenlijk altijd zo voor gehele bases ≥ 2. Een bekend voorbeeld is de keuze van base 2 (dan krijgen we dus binaire ontwikkelingen). In het laatste geval hebben we dus alleen maar digits 0 en 1, en kunnen we elk getal x ∈ [0, 1) schrijven als: ∞ X bn , met bn ∈ {0, 1} voor n ≥ 1. x= 2n n=1

Cor Kraaikamp ()


9 / 64



Cor Kraaikamp ()


9 / 64



Cor Kraaikamp ()


9 / 64


Merk op, dat dit ook werkt als de base niet gelijk is aan 10, maar aan 2, of 3, of 12, . . . Dit werkt eigenlijk altijd zo voor gehele bases ≥ 2. Een bekend voorbeeld is de keuze van base 2 (dan krijgen we dus binaire ontwikkelingen). In het laatste geval hebben we dus alleen maar digits 0 en 1, en kunnen we elk getal x ∈ [0, 1) schrijven als: ∞ X bn x= , met bn ∈ {0, 1} voor n ≥ 1. 2n n=1

Cor Kraaikamp ()


9 / 64


Merk op, dat dit ook werkt als de base niet gelijk is aan 10, maar aan 2, of 3, of 12, . . . Dit werkt eigenlijk altijd zo voor gehele bases ≥ 2. Een bekend voorbeeld is de keuze van base 2 (dan krijgen we dus binaire ontwikkelingen). In het laatste geval hebben we dus alleen maar digits 0 en 1, en kunnen we elk getal x ∈ [0, 1) schrijven als: ∞ X bn x= , met bn ∈ {0, 1} voor n ≥ 1. 2n n=1

Cor Kraaikamp ()


9 / 64

Het maken van (binaire) rijtjes Je kunt het ook zo zien: Op ieder tijdstip moet aan een waarde een rijtje 0-en en 1-en gekoppeld worden. Dit doen we voor getallen tussen 0 en 1 door het interval steeds in 2 stukken te delen en dan te kijken of het punt links of rechts ligt.

Neem

1 2

√

3 ≈ 0.8660.

0

0 1 2

√

1

1 2

rijtjes

1

3 = 0.1 . . .

Cor Kraaikamp ()

Het benaderen van irrationale getallen door ‘rationale.’ Vakantiecursus Wiskunde August 2012 24, 2012

10 / 64


Neem

1 2

√

3 ≈ 0.8660.

0

0 1 2

√

1

1 2

rijtjes

1

3 = 0.1 . . .

Cor Kraaikamp ()


10 / 64


Neem

1 2

√

3 ≈ 0.8660.

0

0 1 2

√

1

1 2

rijtjes

1

3 = 0.1 . . .

Cor Kraaikamp ()


10 / 64


Neem

1 2

√

3 ≈ 0.8660.

0

0 1 2

√

1

1 2

rijtjes

1

3 = 0.1 . . .

Cor Kraaikamp ()


10 / 64

Het maken van (binaire) rijtjes Op ieder tijdstip moet aan een waarde een rijtje 0-en en 1-en gekoppeld worden. Dit doen we voor getallen tussen 0 en 1 door het interval steeds in 2 stukken te delen en dan te kijken of het punt links of rechts ligt. √ Neem 12 3 ≈ 0.8660.

0

0 1 2

√

10

1 2

11

3 4

rijtjes

1

3 = 0.11 . . .

Cor Kraaikamp ()


11 / 64

Het maken van (binaire) rijtjes Op ieder tijdstip moet aan een waarde een rijtje 0-en en 1-en gekoppeld worden. Dit doen we voor getallen tussen 0 en 1 door het interval steeds in 2 stukken te delen en dan te kijken of het punt links of rechts ligt. √ Neem 12 3 ≈ 0.8660.

0

0 1 2

√

10

1 2

110111 rijtjes

3 4

7 8

1

3 = 0.110 . . .

Cor Kraaikamp ()


12 / 64

Een functie die hetzelfde doet De functie T2 doet hetzelfde als het algoritme. 2x, als x tussen 0 en 1/2 ligt, T2 (x) = 2x − 1, als x tussen 1/2 en 1 ligt. 1

2x

2x-1

0

Cor Kraaikamp ()

1 2

1


13 / 64

Het maken van rijtjes 0-en en 1-en Neem bijvoorbeeld x =

1 2

√

3. We maken een rijtje 0-en en 1-en. Schrijf b1 (x) = 1.

1

0 1 2

√

0

1

1 2

1

3 = 0.1 . . .

Cor Kraaikamp ()


14 / 64


1 2

√


1

0 1 2

√

0

1

1 2

1

3 = 0.11 . . .

Cor Kraaikamp ()


15 / 64


1 2

√


1

0 1 2

√

0

1

1 2

1

3 = 0.110 . . .

Cor Kraaikamp ()


16 / 64


1 2

√


1

0 1 2

√

0

1

1 2

1

3 = 0.1101 . . .

Cor Kraaikamp ()


17 / 64

Benadering van

1 2

√

3 in 4 stappen

√ Voor 21 3 ≈ 0.8660 hadden we het rijtje 1101 gekregen. De benadering die dit geeft is 1 1 0 1 + + + = 0.8125. 2 4 8 16 Hoe meer stappen we nemen in de benadering, hoe nauwkeuriger de benadering wordt. We kunnen hier oneindig lang mee doorgaan en krijgen dan een oneindig √ lang rijtje met 0-len en 1-nen. We kunnen 21 3 dan schrijven als een oneindige som: 1√ 1 1 1 0 1 1 0 + + + + ... 3= + + + 2 2 4 8 16 32 64 128

Cor Kraaikamp ()


18 / 64

Benadering van

1 2

√

3 in 4 stappen


Cor Kraaikamp ()


18 / 64

Benadering van

1 2

√

3 in 4 stappen


Cor Kraaikamp ()


18 / 64

Benadering van

1 2

√

3 in 4 stappen


Cor Kraaikamp ()


18 / 64

Benadering van

1 2

√

3 in 4 stappen


Cor Kraaikamp ()


18 / 64

Eigenschappen van de benaderingen

Bij iedere x tussen 0 en 1 kunnen we een oneindig rijtje 0-en en 1-en geven. Met dit rijtje kunnen we x schrijven als oneindige som. x=

b2 b3 b4 b1 + + + + ... 2 4 8 16

Deze som heet de ontwikkeling in basis 2 van x. Bijna alle getallen tussen 0 en 1 hebben een unieke ontwikkeling. Getallen die geen unieke ontwikkeling hebben, hebben precies 2 ontwikkelingen.

Cor Kraaikamp ()


19 / 64



b2 b3 b4 b1 + + + + ... 2 4 8 16


Cor Kraaikamp ()


19 / 64



b2 b3 b4 b1 + + + + ... 2 4 8 16


Cor Kraaikamp ()


19 / 64

Meerdere ontwikkelingen Getallen die twee ontwikkelingen hebben, zijn alle getallen die een keer op 9 terecht komen. Voorbeelden: 14 , 34 , 58 , 16 . 1 4

= =

1 2

0 1 0 0 0 + + + + + ... 2 4 8 16 32 0 0 1 1 1 + + + + + ... 2 4 8 16 32 1

2x

2x-1

0

Cor Kraaikamp ()

1 2

1


20 / 64

De gulden snede We zagen dat – afgezien van een deelverzameling van de rationale getallen tussen 0 en 1 alle getallen een unieke ontwikkeling hebben in elke basis β ∈ Z, β ≥ 2. Als we de eis laten vallen dat de basis geheel moet zijn gebeuren er opeens spectaculaire dingen. We beperken ons tot het meest eenvoudige geval, waarin de base β gelijk is aan de gulden snede. √

De gulden snede is g = 1+2 5 ≈ 1.6181. – Het is een van de oplossingen van de vergelijking x2 − x − 1 = 0. – Het is te schrijven als een kettingwortel met alleen maar 1-nen, want g 2 = g + 1: s r q √ g = 1 + 1 + 1 + 1 + · · ·. – Het is te schrijven als een kettingbreuk met alleen maar 1-nen, want g = 1 + g1 : 1 g =1+ . 1 1+ . 1 + .. Cor Kraaikamp () Het benaderen van irrationale getallen door ‘rationale.’ Vakantiecursus Wiskunde August 2012 24, 2012

21 / 64



21 / 64



21 / 64



21 / 64



21 / 64



21 / 64

De gulden snede in kunst De gulden snede wordt wellicht gebruikt in kunst, zoals in de Vetruviaanse man van Leonardo da Vinci . . . maar anderen denken dat dat onzin is.

De verhouding tussen de afstand van voeten tot navel en de afstand van hoofd tot navel is de gulden snede, evenals de verhouding tussen de afstand van voeten tot navel en de totale lichaamslengte. Cor Kraaikamp ()


22 / 64




22 / 64




22 / 64

De bijbehorende functie? Als we kijken naar de lijnen gx en gx − 1 voor x-en tussen 0 en g, dan ziet dat er zo uit. g

gx-1

gx

0

Cor Kraaikamp ()

1 g

1

g


23 / 64

Benaderingen maken in basis de gulden snede We kunnen weer 0-len en 1-nen gebruiken om benaderingen te maken van alle getallen tussen 0 en g. Alleen nu is er een gebied waar we zowel de 0 als de 1 kunnen gebruiken. g

0

1

gx-1

gx

0

Cor Kraaikamp ()

1 g

1

g


24 / 64


0

1

gx-1

gx

0

Cor Kraaikamp ()

1 g

1

g


24 / 64


0

01

1

gx-1

gx

0

Cor Kraaikamp ()

1 g

1

g


25 / 64


0

01

1

gx-1

gx

0

Cor Kraaikamp ()

1 g

1

g


26 / 64


0

01

1

gx-1

gx

0

Cor Kraaikamp ()

1 g

1

g


27 / 64


0

01

1

gx-1

gx

0

Cor Kraaikamp ()

1 g

1

g


28 / 64

Benaderingen maken in basis de gulden snede We kunnen weer 0-len en 1-en gebruiken om benaderingen te maken van alle getallen tussen 0 en g. Alleen nu is er een gebied waar we zowel de 0 als de 1 kunnen gebruiken. g

0

01

1

gx-1

gx

0

Cor Kraaikamp ()

1 g

1

g


29 / 64


0

01

1

gx-1

gx

0

Cor Kraaikamp ()

1 g

1

g


30 / 64


0

01

1

gx-1

gx

0

Cor Kraaikamp ()

1 g

1

g


31 / 64

Oneindig veel rijtjes Neem bijvoorbeeld weer g

1 2

√

0

3.

01

1

gx-1

gx

0

1√ 3 = 0.1 . . . 2

Cor Kraaikamp ()

g

1 g

1

0

01

1

gx-1

gx

g0

1 g

1

g

1√ 3 = 0.0 . . . 2


32 / 64


1 2

√

0

3.

01

1

gx-1

gx

0

1√ 3 = 0.10 . . . 2

Cor Kraaikamp ()

g

1 g

1

0

01

1

gx-1

gx

g0

1 g

1

g

1√ 3 = 0.01 . . . 2


33 / 64


1 2

√

0

3.

01

1

gx-1

gx

0

1√ 3 = 0.100 . . . 2 1√ 3 = 0.101 . . . 2 Cor Kraaikamp ()

g

1 g

1

0

01

1

gx-1

gx

g0

1 g

1

g

1√ 3 = 0.011 . . . 2


34 / 64


1 2

√

0

3.

01

gx-1

gx

0

1√ 3 = 0.1001 . . . 2 1√ 3 = 0.1010 . . . 2 Cor Kraaikamp ()

g

1

1 g

1

0

01

1

gx-1

gx

g0

1 g

1

g

1√ 3 = 0.0111 . . . 2


35 / 64

Ontwikkelingen in basis de gulden snede

We kunnen de rijtjes weer omzetten in benaderingen van het √ originele getal. Zo vinden we ontwikkelingen in basis de gulden snede. Voor 12 3 ≈ 0.8660 kregen we na een paar stappen het rijtje 1010. Dit geeft de benadering 0 1 1 0 + + 3 + 4 ≈ 0.8541. g g2 g g We hebben de ontwikkeling 1√ 1 0 1 0 0 0 0 0 0 1 3 = + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + · · · 2 g g g g g g g g g g

Cor Kraaikamp ()


36 / 64



Cor Kraaikamp ()


36 / 64



Cor Kraaikamp ()


36 / 64

Veel ontwikkelingen

Bij het maken van een rijtje 0-len en 1-nen met een algoritme moeten we een keuze maken in het gekleurde gebied. Als we altijd kiezen voor de 1 krijgen we de zogenaamde greedy expansion. Als we altijd kiezen voor digit 0 dan krijgen we de lazy expansion. . . . maar we kunnen onze keuze natuurlijk afwisselen!

Cor Kraaikamp ()


37 / 64

Veel ontwikkelingen


Cor Kraaikamp ()


37 / 64

Veel ontwikkelingen


Cor Kraaikamp ()


37 / 64

Veel ontwikkelingen


Cor Kraaikamp ()


37 / 64

Veel ontwikkelingen Voor vaste keuze van de digit geeft dat de volgende afbeeldingen. Eerst de afbeelding voor de greedy afbeelding:

1

g

. ... ... ... .. . . .. ... ... ... .. . . ... ... ... ... .. ... . ... ... ... ... ... .. ... . . . . .. .. ... ... ... ... .. ... .. ... . . . . .. .. ... ... ... ... .. ... .. ... . . . . .. .. ... ... ... ... ... ... .. .. . . . . . . ... ... .. ..

0

g

1

Figure: De afbeelding Tβ met β gelijk aan de gulden snede g Cor Kraaikamp ()


38 / 64

Veel ontwikkelingen Voor vaste keuze van de digit geeft dat de volgende afbeeldingen. Eerst de afbeelding voor de greedy afbeelding:

1

g

. ... ... ... .. . . .. ... ... ... .. . . ... ... ... ... .. ... . ... ... ... ... ... .. ... . . . . .. .. ... ... ... ... .. ... .. ... . . . . .. .. ... ... ... ... .. ... .. ... . . . . .. .. ... ... ... ... ... ... .. .. . . . . . . ... ... .. ..

0

g

1

Figure: De afbeelding Tβ met β gelijk aan de gulden snede g Cor Kraaikamp ()


38 / 64

Veel ontwikkelingen . . . en voor de lazy afbeelding: g

. ... ... ... ... . . ... ... ... ... . . . ... ... ... ... . . . ... ... .. .. ... ... ... . . . . .. .. ... ... ... ... .. ... .. ... . . . . .. .. ... ... ... ... .. ... .. ... . . . . .. .. ... ... ... ... .. ... .. ... . . . . .. .. ... ... ... ... ... ... .. .. . . . . ... ... ... ... ... ... ... ...

1

1/g

0

1/g

1

g

Figure: De afbeelding Tβ voor β = G op het grotere gebied [0, G] Cor Kraaikamp ()


39 / 64

Veel ontwikkelingen . . . en voor de lazy afbeelding: g

. ... ... ... ... . . ... ... ... ... . . . ... ... ... ... . . . ... ... .. .. ... ... ... . . . . .. .. ... ... ... ... .. ... .. ... . . . . .. .. ... ... ... ... .. ... .. ... . . . . .. .. ... ... ... ... .. ... .. ... . . . . .. .. ... ... ... ... ... ... .. .. . . . . ... ... ... ... ... ... ... ...

1

1/g

0

1/g

1

g

Figure: De afbeelding Tβ voor β = G op het grotere gebied [0, G] Cor Kraaikamp ()


39 / 64

Oneindig veel ontwikkelingen We kunnen bij alle x-en dus veel verschillende ontwikkelingen opschrijven in basis de gulden snede. We hebben zelfs de volgende stelling.

Stelling (Erdös, Joo en Komornik) Alle getallen tussen 0 en g hebben oneindig veel verschillende ontwikkelingen in basis de gulden snede.

Bewijs: Iedere keer als een x in het gekleurde gebied komt, verdubbelt het aantal ontwikkelingen van x in basis de gulden snede. Als een x oneindig vaak in het gekleurde gebied komt, dan heeft het ook oneindig veel verschillende ontwikkelingen. Stel dat we laten zien dat een x in het 0-gebied of het 1-gebied altijd na een eindig aantal stappen in het 0/1-gebied komt, dan laat dat zien dat alle x-en oneindig vaak in het 0/1-gebied komen. Cor Kraaikamp ()


40 / 64





40 / 64





40 / 64





40 / 64





40 / 64

Oneindig veel ontwikkelingen Bewijs, vervolg: g

0

01

1

gx-1

gx

0

1 g

1

g

Neem een x tussen 0 en 1/g. Dan is x in het 0 gebied, en wordt x òf in het 0-gebied o`f in het gekleurde gebied afgebeeld. Aangezien de x-en in het 0-gebied met g worden vermenigvuldigd, worden ze alleen maar groter, zodat ze uiteindelijk allemaal een keer in het gekleurde gebied worden afgebeeld.

Cor Kraaikamp ()


41 / 64


0

01

1

gx-1

gx

0

1 g

1

g


Cor Kraaikamp ()


41 / 64


0

01

1

gx-1

gx

0

1 g

1

g


Cor Kraaikamp ()


41 / 64


0

01

1

gx-1

gx

0

1 g

1

g

Neem een x tussen 1 en g. Dan wordt de x of in het 1-gebied afgebeeld of in het gekleurde gebied. Aangezien de x-en in het 1-gebied alleen maar kleiner worden, worden ze uiteindelijk allemaal een keer in het gekleurde gebied afgebeeld.

Cor Kraaikamp ()


42 / 64


0

01

1

gx-1

gx

0

1 g

1

g


Cor Kraaikamp ()


42 / 64


0

01

1

gx-1

gx

0

1 g

1

g


Cor Kraaikamp ()


42 / 64

Kettingbreuken

We zagen eerder voor het gulden snede getal dat er naast de decimale en bianaire-ontwikkeling andere getal-ontwikkelingen bestaan. Eén van deze getal-ontwikkelingen is sterk gerelateerd aan een zeer oud algoritme: het algoritme van Euclides om de grootste gemende deler van twee gehele getallen te vinden. Laat a, b ∈ Z en veronderstel gemakshalve dat a > b > 0. Zet r0 = a,

r1 = b ,

en kies gehele getallen a1 ≥ 1, r2 ≥ 0, zo dat r0 = a1 r1 + r2 , waarbij 0 ≤ r2 < r1 . In het geval dat r2 6= 0 kunnen we deze procedure herhalen.

Cor Kraaikamp ()


43 / 64

Kettingbreuken


r1 = b ,


Cor Kraaikamp ()


43 / 64

Kettingbreuken


r1 = b ,


Cor Kraaikamp ()


43 / 64

Kettingbreuken


r1 = b ,


Cor Kraaikamp ()


43 / 64

Kettingbreuken


r1 = b ,


Cor Kraaikamp ()


43 / 64

Kettingbreuken


r1 = b ,


Cor Kraaikamp ()


43 / 64

Kettingbreuken


r1 = b ,


Cor Kraaikamp ()


43 / 64

Kettingbreuken

Het is duidelijk dat we na ten hoogste r1 stappen ‘tot stilstand’ komen. Er bestaat een positief geheel getal n met rn 6= 0, rk = ak+1 rk+1 + rk+2

voor

k ≤n−1

en 0 = rn+1 < rn < · · · < r1 . Er geldt dan dat de grootste gehele deler ggd(a, b) van a en b gelijk is aan rn .

Cor Kraaikamp ()


44 / 64

Kettingbreuken


voor

k ≤n−1


Cor Kraaikamp ()


44 / 64

Kettingbreuken


voor

k ≤n−1


Cor Kraaikamp ()


44 / 64

Kettingbreuken

Als we het bovenstaande ‘op z’n kop zetten’ krijgen we kettingbreuken. We hebben dan, dat r1 rn−1 r0 , a2 = , . . . , an = . a1 = r1 r2 rn Definieer nu t1 , t2 , . . . , tn−1 door x=

b r1 r2 r3 rn = , t1 = , t2 = , . . . , tn−1 = , a r0 r1 r2 rn−1

dan geldt er dat:

Cor Kraaikamp ()


45 / 64

Kettingbreuken



dan geldt er dat:

Cor Kraaikamp ()


45 / 64

Kettingbreuken



dan geldt er dat:

Cor Kraaikamp ()


45 / 64

Kettingbreuken 1 x

=

a1

+

t1

1 t1

=

a2

+

t2

.. .

1 tn−2 1 tn−1

= an−1

+ tn−1

=

+

an

0.

We vinden dat x=

1 = a 1 + t1

1 1 a1 + a 2 + t2

1

= ··· = a1 +

1

.

. 1 a2 + . . + an

Een dergelijke uitdrukking noemen we een eindige reguliere kettingbreuk. Cor Kraaikamp ()


46 / 64

Kettingbreuken 1 x

=

a1

+

t1

1 t1

=

a2

+

t2

.. .

1 tn−2 1 tn−1

= an−1

+ tn−1

=

+

an

0.

We vinden dat x=

1 = a 1 + t1

1 1 a1 + a 2 + t2

1

= ··· = a1 +

1

.

. 1 a2 + . . + an



46 / 64

Kettingbreuken 1 x

=

a1

+

t1

1 t1

=

a2

+

t2

.. .

1 tn−2 1 tn−1

= an−1

+ tn−1

=

+

an

0.

We vinden dat x=

1 = a 1 + t1

1 1 a1 + a 2 + t2

1

= ··· = a1 +

1

.

. 1 a2 + . . + an



46 / 64

Kettingbreuken Dus elke x = p/q ∈ Q geschreven kan worden als een eindige reguliere kettingbreuk 1 , x = a0 + 1 a1 + . 1 a2 + . . + an met a0 ∈ Z zodat x − a0 ∈ [0, 1). We korten bovenstaande kettingbeuk af door [ a0 ; a1 , a2 , . . . , an−1 , an ] . Uit het algoritme van Euclides volgt bovendien dat an ≥ 2. Maar dan heeft elk rationaal getal x dus twee eindige kettingbreuk-ontwikkelingen: [ a0 ; a1 , a2 , . . . , an−1 , an ] = [ a0 ; a1 , a2 , . . . , an−1 , an − 1, 1 ].

Cor Kraaikamp ()


47 / 64


Cor Kraaikamp ()


47 / 64


Cor Kraaikamp ()


47 / 64

Kettingbreuken Om de (reguliere) kettinbreuk van een irrationaal getal x ∈ [0, 1) te vinden gebruiken we het bovenstande idee. Beschouw de afbeelding T : [0, 1) → [0, 1), gedefinieerd door T (0) = 0 en 1 1 , x ∈ (0, 1). T (x) = − x x Hierbij is bxc het grootste gehele getal kleiner dan, of gelijk aan x. 1

... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... ... ... .. .. . . ... ... ... .. .. ... ... .. ... ... ... ... ... .. ... ... ... .... ... ... ... ... ... .. .... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... ... ... ... ... ... ... ... . ... ... ... ... ... . ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..... .. ... ... ... ..... ... ... ... ... ..... . . ... ... ... .. ...

•••

0

11 1 1 65 4 3

1 2

1

Figure: De (reguliere) kettingbreuk afbeelding T Cor Kraaikamp ()


48 / 64

Kettingbreuken Om de (reguliere) kettinbreuk van een irrationaal getal x ∈ [0, 1) te vinden gebruiken we het bovenstande idee. Beschouw de afbeelding T : [0, 1) → [0, 1), gedefinieerd door T (0) = 0 en 1 1 T (x) = − , x ∈ (0, 1). x x Hierbij is bxc het grootste gehele getal kleiner dan, of gelijk aan x. 1

... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... ... ... .. .. . . ... ... ... .. .. ... ... .. ... ... ... ... ... .. ... ... ... .... ... ... ... ... ... .. .... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... ... ... ... ... ... ... ... . ... ... ... ... ... . ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..... .. ... ... ... ..... ... ... ... ... ..... . . ... ... ... .. ...

•••

0

11 1 1 65 4 3

1 2

1



48 / 64


... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... ... ... .. .. . . ... ... ... .. .. ... ... .. ... ... ... ... ... .. ... ... ... .... ... ... ... ... ... .. .... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... ... ... ... ... ... ... ... . ... ... ... ... ... . ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..... .. ... ... ... ..... ... ... ... ... ..... . . ... ... ... .. ...

•••

0

11 1 1 65 4 3

1 2

1



48 / 64


... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... ... ... .. .. . . ... ... ... .. .. ... ... .. ... ... ... ... ... .. ... ... ... .... ... ... ... ... ... .. .... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... ... ... ... ... ... ... ... . ... ... ... ... ... . ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..... .. ... ... ... ..... ... ... ... ... ..... . . ... ... ... .. ...

•••

0

11 1 1 65 4 3

1 2

1



48 / 64

Kettingbreuken

Definieer voor n ≥ 1 de wijzergetallen an door: 1 an = an (x) = , als T n−1 (x) 6= 0. T n−1 (x) Dus als we T n (x) afkorten tot tn , dan vinden we t1 =

1 − a1 , x

1 , a1 + t1

oftewel

x=

oftewel

tn−1 =

en meer in het algemeen dat tn =

Cor Kraaikamp ()

1 tn−1

− an ,

1 . an + tn


49 / 64

Kettingbreuken


1 − a1 , x

1 , a1 + t1

oftewel

x=

oftewel

tn−1 =


Cor Kraaikamp ()

1 tn−1

− an ,

1 . an + tn


49 / 64

Kettingbreuken


1 − a1 , x

1 , a1 + t1

oftewel

x=

oftewel

tn−1 =


Cor Kraaikamp ()

1 tn−1

− an ,

1 . an + tn


49 / 64

Kettingbreuken


1 − a1 , x

1 , a1 + t1

oftewel

x=

oftewel

tn−1 =


Cor Kraaikamp ()

1 tn−1

− an ,

1 . an + tn


49 / 64

Kettingbreuken


1 − a1 , x

1 , a1 + t1

oftewel

x=

oftewel

tn−1 =


Cor Kraaikamp ()

1 tn−1

− an ,

1 . an + tn


49 / 64

Kettingbreuken


1 − a1 , x

1 , a1 + t1

oftewel

x=

oftewel

tn−1 =


Cor Kraaikamp ()

1 tn−1

− an ,

1 . an + tn


49 / 64

Kettingbreuken


1 − a1 , x

1 , a1 + t1

oftewel

x=

oftewel

tn−1 =


Cor Kraaikamp ()

1 tn−1

− an ,

1 . an + tn


49 / 64

Kettingbreuken Zolang tn = T n (x) 6= 0 geeft domweg herhaald invullen dat: 1

x =

1

a1 + a2 + =

..

.+

1 an + T n (x)

[ 0; a1 , a2 , . . . , an−1 , an + T n (x) ] ,

n ≥ 1.

Als we de ‘restterm’ tn = T n (x) weglaten vinden we een rationale benadering van x: pn = [ 0; a1 , a2 , . . . , an−1 , an ]. qn Zeg de n-de orde decimale benadering van x is rn /sn . We zagen eerder dat x=

Cor Kraaikamp ()

rn T n (x) + 10 n . sn 10


50 / 64

Kettingbreuken Zolang tn = T n (x) 6= 0 geeft domweg herhaald invullen dat: x

1

=

1

a1 + a2 + =

..

.+

1 an + T n (x)

[ 0; a1 , a2 , . . . , an−1 , an + T n (x) ] ,

n ≥ 1.


Cor Kraaikamp ()

rn T n (x) + 10 n . sn 10


50 / 64


1

=

1

a1 + a2 + =

..

.+

1 an + T n (x)

[ 0; a1 , a2 , . . . , an−1 , an + T n (x) ] ,

n ≥ 1.


Cor Kraaikamp ()

rn T n (x) + 10 n . sn 10


50 / 64


1

=

1

a1 + a2 + =

..

.+

1 an + T n (x)

[ 0; a1 , a2 , . . . , an−1 , an + T n (x) ] ,

n ≥ 1.


Cor Kraaikamp ()

rn T n (x) + 10 n . sn 10


50 / 64


1

=

1

a1 + a2 + =

..

.+

1 an + T n (x)

[ 0; a1 , a2 , . . . , an−1 , an + T n (x) ] ,

n ≥ 1.


Cor Kraaikamp ()

rn T n (x) + 10 n . sn 10


50 / 64

Kettingbreuken

Merk op dat sn ≤ 10n . We vinden dat rn n 10 x − ≤ 1. sn De reden om naar kettingbreuken te kijken is dat de ‘kwaliteit van de benadering” op twee manieren superieur is aan die van de decimale benadering. Dit zullen we nu laten zien. Hiervoor zijn de zogenaamde Möbius transformaties heel erg handig.

Cor Kraaikamp ()


51 / 64

Kettingbreuken

Merk op dat sn ≤ 10n . We vinden dat rn n ≤ 1. 10 x − sn De reden om naar kettingbreuken te kijken is dat de ‘kwaliteit van de benadering” op twee manieren superieur is aan die van de decimale benadering. Dit zullen we nu laten zien. Hiervoor zijn de zogenaamde Möbius transformaties heel erg handig.

Cor Kraaikamp ()


51 / 64

Kettingbreuken


Cor Kraaikamp ()


51 / 64

Kettingbreuken


Cor Kraaikamp ()


51 / 64

Kettingbreuken


Cor Kraaikamp ()


51 / 64

Kettingbreuken Laat a, b, c, d ∈ Z, met ad − bc = ±1, en definieer de afbeelding A : R ∪ {∞} → R ∪ {∞} door A(x) =

ax + b , cx + d

x ∈ R ∪ {∞} .

Als we A nu met de matrix

a c

b d

∈ SL2 (Z)

identificeren, dan beschrijven we de afbeelding A (op een beetje illegale wijze) door ax + b a b (x) = , x ∈ R ∪ {∞} . c d cx + d

Cor Kraaikamp ()


52 / 64


ax + b , cx + d

x ∈ R ∪ {∞} .


a c

b d

∈ SL2 (Z)


Cor Kraaikamp ()


52 / 64


ax + b , cx + d

x ∈ R ∪ {∞} .


a c

b d

∈ SL2 (Z)


Cor Kraaikamp ()


52 / 64


ax + b , cx + d

x ∈ R ∪ {∞} .


a c

b d

∈ SL2 (Z)


Cor Kraaikamp ()


52 / 64

Kettingbreuken

Verschillende eenvoudige eigenschappen van M¨ obius transformaties kunnen nu worden afgeleid. Bijvoorbeeld, voor matrices A, B ∈ SL2 (Z), geldt er dat (AB)(x) = A(B(x)) , waarbij AB het gebruikelijke matrix product van A en B is. Laat nu x ∈ R \ Q een irrationaal getal zijn, met wijzergetallen a0 ∈ Z (met x − a0 ∈ [0, 1)) en an ∈ N voor n ≥ 1. Definieer voor n ≥ 0 de matrices An en Mn door: 1 a0 0 1 A0 := , An := , Mn := A0 A1 · · · An , n ≥ 1. 0 1 1 an

Cor Kraaikamp ()


53 / 64

Kettingbreuken


Cor Kraaikamp ()


53 / 64

Kettingbreuken


Cor Kraaikamp ()


53 / 64

Kettingbreuken

Dan geldt er dat: Mn (0) = [ a0 ; a1 , . . . , an ] . Als we nu zetten dat

Mn =

rn sn

pn qn

, n ≥ 0,

dan volgt er uit het uitschrijven van Mn = Mn−1 An dat: pn−1 pn Mn = , n ≥ 0. qn−1 qn

Cor Kraaikamp ()


54 / 64

Kettingbreuken


Mn =

rn sn

pn qn

, n ≥ 0,


Cor Kraaikamp ()


54 / 64

Kettingbreuken


Mn =

rn sn

pn qn

, n ≥ 0,


Cor Kraaikamp ()


54 / 64

Kettingbreuken


Mn =

rn sn

pn qn

, n ≥ 0,


Cor Kraaikamp ()


54 / 64

Kettingbreuken


Mn =

rn sn

pn qn

, n ≥ 0,


Cor Kraaikamp ()


54 / 64

Kettingbreuken Uit Mn = Mn−1 An volgt dat: pn−1 qn − pn qn−1 pn qn

=

det(Mn ) = (−1)n ,

n ≥ 1,

en

= Mn (0) = [ a0 ; a1 , . . . , an ], n ≥ 1.

Bovendien volgen de beroemde recurrente relaties voor kettingbreuken ook direct uit Mn = Mn−1 An : pn−1 pn pn−2 pn−1 0 1 = . qn−1 qn qn−2 qn−1 1 an Namelijk p−1 = 1,

p0 = a0 ,

pn = an pn−1 + pn−2

als n ≥ 1,

q−1 = 0,

q0 = a1 ,

qn = an qn−1 + qn−2

als n ≥ 1.

en

Cor Kraaikamp ()


55 / 64


=

det(Mn ) = (−1)n ,

n ≥ 1,

en

= Mn (0) = [ a0 ; a1 , . . . , an ], n ≥ 1.


p0 = a0 ,


als n ≥ 1,

q−1 = 0,

q0 = a1 ,


als n ≥ 1.

en

Cor Kraaikamp ()


55 / 64


=

det(Mn ) = (−1)n ,

n ≥ 1,

en

= Mn (0) = [ a0 ; a1 , . . . , an ], n ≥ 1.


p0 = a0 ,


als n ≥ 1,

q−1 = 0,

q0 = a1 ,


als n ≥ 1.

en

Cor Kraaikamp ()


55 / 64


=

det(Mn ) = (−1)n ,

n ≥ 1,

en

= Mn (0) = [ a0 ; a1 , . . . , an ], n ≥ 1.


p0 = a0 ,


als n ≥ 1,

q−1 = 0,

q0 = a1 ,


als n ≥ 1.

en

Cor Kraaikamp ()


55 / 64


=

det(Mn ) = (−1)n ,

n ≥ 1,

en

= Mn (0) = [ a0 ; a1 , . . . , an ], n ≥ 1.


p0 = a0 ,


als n ≥ 1,

q−1 = 0,

q0 = a1 ,


als n ≥ 1.

en

Cor Kraaikamp ()


55 / 64


=

det(Mn ) = (−1)n ,

n ≥ 1,

en

= Mn (0) = [ a0 ; a1 , . . . , an ], n ≥ 1.


p0 = a0 ,


als n ≥ 1,

q−1 = 0,

q0 = a1 ,


als n ≥ 1.

en

Cor Kraaikamp ()


55 / 64

Kettingbreuken

∗ Definieer tenslotte de matrix MN door pn−2 pn−1 0 Mn∗ = qn−2 qn−1 1

1 an + T n (x)

.

Dan geldt er dat: 1

Mn∗ (0) = a1 +

Cor Kraaikamp ()

1 . a2 + . . +

= x.

1 an + T n (x)


56 / 64

Kettingbreuken


1 an + T n (x)

.

Dan geldt er dat: 1

Mn∗ (0) = a1 +

Cor Kraaikamp ()

1 . a2 + . . +

= x.

1 an + T n (x)


56 / 64

Kettingbreuken


1 an + T n (x)

.

Dan geldt er dat: 1

Mn∗ (0) = a1 +

Cor Kraaikamp ()

1 . a2 + . . +

= x.

1 an + T n (x)


56 / 64

Kettingbreuken


1 an + T n (x)

.

Dan geldt er dat: 1

Mn∗ (0) = a1 +

Cor Kraaikamp ()

1 . a2 + . . +

= x.

1 an + T n (x)


56 / 64

Kettingbreuken

Als we het matrix-product uitschrijven en de recurrente relaties gebruiken vinden we dat: pn−1 pn + pn−1 T n (x) ∗ Mn = . qn−1 qn + qn−1 T n (x) Maar dan zien we dus, dat x = Mn∗ (0) =

Cor Kraaikamp ()

pn + pn−1 T n (x) , qn + qn−1 T n (x)

n ≥ 1,


57 / 64

Kettingbreuken


Cor Kraaikamp ()

pn + pn−1 T n (x) , qn + qn−1 T n (x)

n ≥ 1,


57 / 64

Kettingbreuken


Cor Kraaikamp ()

pn + pn−1 T n (x) , qn + qn−1 T n (x)

n ≥ 1,


57 / 64

Kettingbreuken

We vinden nu direct voor n ≥ 1 dat x−

pn + pn−1 T n (x) pn (−1)n T n (x) pn = − = , n qn qn + qn−1 T (x) qn qn (qn + qn−1 T n (x))

waaruit direct volgt dat: pn T n (x) 2 qn x − = ≤ 1, n ≥ 1. qn 1 + T n (x)Vn In feite was dit één van de startpunten van de moderne theorie van de metrische eigenschappen van kettingbreuken, die in het begin van de tachtiger jaren van de vorige eeuw begon.

Cor Kraaikamp ()


58 / 64

Kettingbreuken




Cor Kraaikamp ()


58 / 64

Kettingbreuken




Cor Kraaikamp ()


58 / 64

Kettingbreuken

Met het voorafgaande kunnen makkelijk allerlei benaderings eigenschappen van kettingbeuk convergenten gevonden worden. Zet pn 2 Θn = Θn (x) = qn x − , n ≥ 1, qn dan geldt er voor elk irrational getal x dat: min{Θn−1 , Θn } <

min{Θn−1 , Θn , Θn+1 } < p

Cor Kraaikamp ()

1 2

1 1 ≤√ 5 a2n + 4

Vahlen (1905),

Bagemihl & McLaughlin (1966).


59 / 64

Kettingbreuken


min{Θn−1 , Θn , Θn+1 } < p

Cor Kraaikamp ()

1 2

1 1 ≤√ 5 a2n + 4

Vahlen (1905),



59 / 64

Kettingbreuken


min{Θn−1 , Θn , Θn+1 } < p

Cor Kraaikamp ()

1 2

1 1 ≤√ 5 a2n + 4

Vahlen (1905),



59 / 64

Kettingbreuken


min{Θn−1 , Θn , Θn+1 } < p

Cor Kraaikamp ()

1 2

1 1 ≤√ 5 a2n + 4

Vahlen (1905),



59 / 64

Kettingbreuken


min{Θn−1 , Θn , Θn+1 } < p

Cor Kraaikamp ()

1 2

1 1 ≤√ 5 a2n + 4

Vahlen (1905),



59 / 64

Kettingbreuken

Kettingbreuk convergenten zijn de beste benaderingsbreuken. Een rationaal getal a/b is een beste benaderingsbreuk van x ∈ R \ Q, als b > 0 en als voor alle rationale getallen c/d 6= a/b met 0 < d ≤ b er geldt dat |dx − c| > |bx − a|. Merk eerst op, dat de convergenten pn /qn van x ‘om-en-om’ x springen: a0 =

Cor Kraaikamp ()

p0 p2 p4 p5 p3 p1 < < < ··· < x < ··· < < < . q0 q2 q4 q5 q3 q1


60 / 64

Kettingbreuken


Cor Kraaikamp ()

p0 p2 p4 p5 p3 p1 < < < ··· < x < ··· < < < . q0 q2 q4 q5 q3 q1


60 / 64

Kettingbreuken


Cor Kraaikamp ()

p0 p2 p4 p5 p3 p1 < < < ··· < x < ··· < < < . q0 q2 q4 q5 q3 q1


60 / 64

Kettingbreuken


Cor Kraaikamp ()

p0 p2 p4 p5 p3 p1 < < < ··· < x < ··· < < < . q0 q2 q4 q5 q3 q1


60 / 64

Kettingbreuken

Veronderstel eerst, dat a/b (met b > 0) een beste benaderingsbreuk is. We willen dus aantonen dat a/b een convergent is. Dan moet er wel gelden dat a/b ≥ a0 , want als a/b < a0 vinden we dat: a a 1 · x − a0 < x − ≤ b x − = bx − a , b b en we krijgen een tegenspraak, omdat a/b dan geen beste benaderingsbreuk is. Stel nu, dat a/b geen convergent is. Dan is wegens het “heen-en-weer springen” van de convergenten dat ` of a/b > p1 /q1 ` of bestaat er een n ≥ 1 zo dat a/b tussen pn−1 /qn−1 en pn+1 /qn+1 ligt.

Cor Kraaikamp ()


61 / 64

Kettingbreuken


Cor Kraaikamp ()


61 / 64

Kettingbreuken


Cor Kraaikamp ()


61 / 64

Kettingbreuken


Cor Kraaikamp ()


61 / 64

Kettingbreuken


Cor Kraaikamp ()


61 / 64

Kettingbreuken In het eerste geval (a/b > p1 /q1 ) geldt er dat: a |bp1 − aq1 | 1 a p1 ≥ , x − > − = b q1 b bq1 bq1 (hierbij gebruiken we dat bp1 − aq1 een geheel getal verschillend van 0 is), en dus dat 1 1 = . |bx − a| > q1 a1 Omdat |1 · x − a0 | <

1 a1

volgt er direct dat |bx − a| > |1 · x − a0 |, en we hebben opnieuw een tegenspraak.

Cor Kraaikamp ()


62 / 64

Kettingbreuken In het eerste geval (a/b > p1 /q1 ) geldt er dat: a |bp1 − aq1 | 1 a p1 ≥ , x − > − = b q1 b bq1 bq1 (hierbij gebruiken we dat bp1 − aq1 een geheel getal verschillend van 0 is), en dus dat 1 1 |bx − a| > = . q1 a1 Omdat |1 · x − a0 | <

1 a1


Cor Kraaikamp ()


62 / 64


1 a1


Cor Kraaikamp ()


62 / 64


1 a1


Cor Kraaikamp ()


62 / 64

Kettingbreuken In het tweede geval (a/b ligt tussen pn−1 /qn−1 en pn+1 /qn+1 voor een n ≥ 1) volgt er ook een tegenspraak. Immers, a pn−1 |aqn−1 − bpn−1 | 1 − = ≥ b qn−1 bqn−1 bqn−1 en

a pn−1 pn pn−1 1 − < − , = b qn−1 qn qn−1 qk qn−1

zodat we vinden dat b > qn . Verder geldt er, dat: a pn+1 a 1 − ≥ . x − > b qn+1 b bqn+1 Maar dan geldt er dat: |bx − a| >

Cor Kraaikamp ()

1 qn+1

.


63 / 64




Cor Kraaikamp ()

1 qn+1

.


63 / 64




Cor Kraaikamp ()

1 qn+1

.


63 / 64




Cor Kraaikamp ()

1 qn+1

.


63 / 64




Cor Kraaikamp ()

1 qn+1

.


63 / 64




Cor Kraaikamp ()

1 qn+1

.


63 / 64




Cor Kraaikamp ()

1 qn+1

.


63 / 64

Kettingbreuken Uit het heen-en-weer springen van de convergenten volgt dat: |qn x − pn | ≤

1 qn+1

,

zodat we dus vinden dat: |qn x − pn | ≤ |bx − a|. Maar dan volgt uit dit en b > qn een tegenspraak; a/b is geen beste benaderingsbreuk. We zien dus dat elke beste benaderingsbreuk een convergent is. Voor het bewijs dat elke convergent een beste benaderingsbreuk is verwijs ik de lezer naar Stelling 17 in Khintchine’s beroemde boek over kettingbreuken . . . het is wel mooi geweest!

Cor Kraaikamp ()


64 / 64


1 qn+1

,


Cor Kraaikamp ()


64 / 64


1 qn+1

,


Cor Kraaikamp ()


64 / 64


1 qn+1

,


Cor Kraaikamp ()


64 / 64


1 qn+1

,


Cor Kraaikamp ()


64 / 64


1 qn+1

,


Cor Kraaikamp ()


64 / 64

Het benaderen van irrationale getallen door rationale. Vakantiecursus Wiskunde 2012

Recommend Documents