Kjedebrøk

**Kjedebrøk** er en iterativ måte å beskrive et vilkårlig tall. Den er et alternativ til den vanlige fremstillingen ved desimaltall eller andre tallsystem. Tallet skrives som et heltall pluss den inverse av et annet tall. Dette andre tallet skrives så på samme måte som et heltall pluss en invers av et nytt tall. Denne prosessen kan så fortsettes til man oppnår den nødvendige presisjon.

Kjennskapen til kjedebrøker kan føres tilbake til antikkens Hellas hvor de var en implisitt del av Euklids algoritme for bestemmelse av største felles divisor av heltall. Men det var først på midten av 1600-tallet de fikk sin moderne utforming gjennom arbeidene til Lord Brouncker. Siden ble deres egenskaper videre utarbeidet av Euler og Lagrange. I dag har kjedebrøker en visss betydning i deler av tallteori og har også  mange anvendelser i mer praktiske sammenhenger.

## Definisjon

Hvis man for eksempel betrakter brøken , så er den ganske nøyaktig 4.4624. Som en første approksimasjon, kan man derfor si at den har verdien 4. For å få en mer nøyaktig verdi, beregner man  differansen mellom  brøken og denne approksimative verdien. Det gir nye brøken  hvis invers er  = 2 + . Da den inverse av  har en verdi som er tilnærmet lik 6, har man dermed kommet frem til en tilnærmet verdi 4 +  = 0.4615 for den opprinnelige brøken. Fortsetter man ett skritt til og setter  = 6 + , stopper prosessen. Resultatet av beregningen kan da skrives som den endelige kjedebrøken

:  {415\over 93} =  4 + \cfrac{1}{2 + \cfrac{1}{6 + \cfrac{1}{7}}} 

Alle brøker eller rasjonale tall kan skrives som en kjedebrøk med et endelig antall nevnere.

På samme måte kan et irrasjonalt tall *x* skrives som en uendelig kjedebrøk med standardformen

: x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + {_\ddots}}}}

hvor alle tallene i nevnerne er positive heltall. Desto flere nevnere man beholder, desto nøyaktigere verdi finner man for det irrasjonale tallet.

Denne kjedebrøken skrives i en mer kompakt notasjon som  x = [a_0, a_1, a_2, a_3, \cdots] . Alternativt kan man også benytte formen

: x = a_0  + \frac{1}{a_1+}\frac{1}{a_2+}\frac{1}{a_3+}\cdots 

selv om denne er mindre brukt.

### Euklids algoritme

En gitt rasjonalt tall kan omskrives til en endelig kjedebrøk ved bruk av Euklids algoritme. Som et eksempel kan man benytte denne fremgangsmåten til å splitte opp brøken 17/10. Det gir

: \begin{align}
17 &= \mathbf{1} \cdot 10 + 7 \\
10 &= \mathbf{1} \cdot  7 + 3 \\
 7 &= \mathbf{2} \cdot  3 + 1 \\
 3 &= \mathbf{3} \cdot  1 + 0
\end{align}

Multiplikandene som her er uthevet med fet skrift, er nevnerne i den resulterende kjedebrøken. Man har dermed at 17/10 = [1; 1, 2, 3]. Innholdet av algoritmen tilsvarer omskrivningen

: \frac{17}{10}=1+\dfrac{7}{10}=1+\dfrac{\ \ 1\ \ }{\dfrac{10}{7}}=1+\dfrac{1}{1+\dfrac{3}{7}}=1+\dfrac{1}{1+\dfrac{1}{\dfrac{7}{3}}}=1+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{3}}}

Algoritmen er den samme som benyttes ved beregning av største felles faktor av to heltall og kan illustreres på en tilsvarende måte. I dette eksempelet tenker man seg et rektangel som er 10&times;17 stort. I det plasserer man så mange kvadrater som mulig med sidelengde lik med den korteste siden i rektangelet, det vil si 10 i dette eksempelet. Dermed blir det en rest igjen med størrelse 10&times;7 i det opprinnelige rektangelet. I dette mindre rektangelet gjentar man så utfyllingen med mindre kvadrater helt til det gitte rektangelet er dekket med kvadrater av forskjellige størrelser. Den resulterende kjedebrøken har nevnere som angir antall kvadrat med avtagende sidekanter som benyttes i denne oppdelingen.

### Eksempel

Hvis man benytter Euklids algoritme på et irrasjonalt tall, vil den fortsette i det uendelige. Det tilsvarer at det har uendelig mange siffer etter desimaltegnet. Men ved å fremstille tallet som en kjedebrøk, vil man ved å bare ta med noen få nevnere få en like gode approksimasjon til tallet som ville ha krevet et større antall desimaler.

Et godt eksempel gir tallet π = 3.1415926... Mens laveste approksimasjon er  π = 3, finner man i neste omgang kjedebrøken [3; 7] = 3 + 1/7 = 22/7 med verdien π = 3.14. Neste stepp i algoritmen gir [3; 7, 15] som utregnet blir

:  [3;7,15] = 3 + \cfrac{1}{7 + \cfrac{1}{15}} = 3 + \cfrac{1}{\cfrac{106}{15}}=3 + \cfrac{15}{106} = \cfrac{333}{106} = 3.141509... 

En mer korrekt kjedebrøk er π = [3; 7, 15, 1, 292, 1, 1, 3, ...]. Ved å ta med en nevner til, finner man 

:  [3;7,15, 1] = [3;7,16]  = \cfrac{355}{113} = 3.1415929... 

som en approksimativ verdi for π som er omtrent hundre ganger mer nøyaktig enn 3.1416.

## Kvadratrøtter

Når et  rasjonalt tall skrives som desimaltall, får det genenerelt uendelig mange desimaler. Men de opptrer i et periodisk mønster. Derimot vil desimalene til et irrasjonalt tall ikke ha noe tydelig mønster. Med bruk av kjedebrøker kan rasjonale tall fremstilles som endelige kjedebrøker, mens kvadratrøtter kan skrives som uendelige kjedebrøker med et periodisk mønster.

Kvadratrøtter oppstår ved løsningen av andregradsligningen. Deres løsning kan uttrykkes ved kjedebrøker. Et enkelt eksempel er ligningen

:  x^2 - ax - 1 = 0 

som har løsningen  x = \tfrac{1}{2}(a + \sqrt{a^2 + 4}) . Men den kan også finnes ved å skrive ligningen som  x = a + 1/x . Dette uttrykket kan itereres,

: \begin{align} x &= a + \cfrac{1}{a + \cfrac{1}{x}} \\ \end{align} 

og gir dermed den uendelige kjedebrøken  x = [a; a, a, a, \cdots] . Når *a* = 1, gir dette det gyldne snitt *&phi;* = [1; 1, 1, 1, ... ] eller

:   \tfrac{1}{2}(1 + \sqrt{5}) =  1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + {_\ddots}}}} 

Herfra kan man så utlede &radic;5 = [2; 4, 4, 4, ...]. Den samme beregningen kan også benyttes til å omforme &radic;2. Ved å sette  i ligningen  , fremkommer den samme andregradsligningen for *x* med *a* = 2. Derfor er *x* = [2; 2, 2, 2, ...] og dermed &radic;2 = [1; 2, 2, 2, ...].

### Periodiske kjedebrøker

Hvis man for eksempel betrakter kjedebrøken &radic;19 = [4;2,1,3,1,2,8,2,1,3,1,2,8,...], ser man at nevnerne etter *a*0 opptrer på en periodisk måte. Dette gjelder for alle irrasjonale kvadratrøtter.

Generelt kan en slik kjedebrøk skrives som [*a*0;&thinsp;] hvor linjen over perioden *P* betyr at den gjentas i det uendelige.  For &radic;19 er da *P* = (2,1,3,1,2,8). Med denne notasjonen kan man da skrive &radic;2 = [1;], mens &radic;3 = [1;] og &radic;7 = [2;].

Periodene har også en spesiell symmetri da de har formen *P* = (*a*1,*a*2,...,*a*2,*a*1,2*a*0). Bortsett fra det siste leddet, er de derfor palindromiske.

## Generaliserte kjedebrøker

En generell kjedebrøk er definert å ha formen

:  x = a_0+\cfrac{b_1}{a_1+\cfrac{b_2}{a_2+\cfrac{b_3}{a_3+\cfrac{b_4}{\;\,\ddots}}}}\quad 

og kan mer kompakt skrives som

:  x = a_0 + \frac{b_1}{a_1 +}\frac{b_2}{a_2 +}\frac{b_3}{a_3 +}\cdots 

hvor tellere og nevnere er positive heltall.

På denne formen kan nye symmetrier bli synlige i fremstillingen av reelle tall. Et av de første eksemplene ble vist av Lord Brouncker som tok utgangspunkt i formelen til John Wallis for det transcendente tallet π som et uendelig produkt. Han kom frem til at

:  {4\over\pi} = 1 + \frac{1^2}{3 +}\frac{2^2}{5 +}\frac{3^2}{7 +}\cdots 

Det var John Wallis som ga navnet *continued fractions* til disse uendelige kjedebrøkene.

## Referanser


## Eksterne lenker

* Youtube, ''Continued Fractions'', John Barrow forelesning ved Gresham College
* E.W. Weisstein, ''Periodic Continued Fraction'', Wolfram MathWorld