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 415/93, 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 43/93 hvis invers er 93/43 = 2 + 7/43. Da den inverse av 7/43 har en verdi som er tilnærmet lik 6, har man dermed kommet frem til en tilnærmet verdi 4 + 1/ 2 + 1/6 = 0.4615 for den opprinnelige brøken. Fortsetter man ett skritt til og setter 43/7 = 6 + 1/7, stopper prosessen. Resultatet av beregningen kan da skrives som den endelige kjedebrøken

  
    
      
        
          
            415
            93
          
        
        =
        4
        +
        
          
            
              
                
              
              
                
                  1
                
              
            
            
              
                
              
              
                
                  2
                  +
                  
                    
                      
                        
                          
                        
                        
                          
                            1
                          
                        
                      
                      
                        
                          
                        
                        
                          
                            6
                            +
                            
                              
                                
                                  
                                    
                                  
                                  
                                    
                                      1
                                    
                                  
                                
                                
                                  
                                    
                                  
                                  
                                    
                                      7
                                    
                                  
                                
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
    {\displaystyle {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  standarformen

  
    
      
        x
        =
        
          a
          
            0
          
        
        +
        
          
            
              
                
              
              
                
                  1
                
              
            
            
              
                
              
              
                
                  
                    a
                    
                      1
                    
                  
                  +
                  
                    
                      
                        
                          
                        
                        
                          
                            1
                          
                        
                      
                      
                        
                          
                        
                        
                          
                            
                              a
                              
                                2
                              
                            
                            +
                            
                              
                                
                                  
                                    
                                  
                                  
                                    
                                      1
                                    
                                  
                                
                                
                                  
                                    
                                  
                                  
                                    
                                      
                                        a
                                        
                                          3
                                        
                                      
                                      +
                                      
                                        
                                          
                                          
                                            ⋱
                                          
                                        
                                      
                                    
                                  
                                
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
    {\displaystyle 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
          
        
        ,
        ⋯
        ]
      
    
    {\displaystyle x=[a_{0},a_{1},a_{2},a_{3},\cdots ]}
  . Alternativt kan man også benytte formen

  
    
      
        x
        =
        
          a
          
            0
          
        
        +
        
          
            1
            
              
                a
                
                  1
                
              
              +
            
          
        
        
          
            1
            
              
                a
                
                  2
                
              
              +
            
          
        
        
          
            1
            
              
                a
                
                  3
                
              
              +
            
          
        
        ⋯
      
    
    {\displaystyle 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

  
    
      
        
          
            
              
                17
              
              
                
                =
                
                  1
                
                ⋅
                10
                +
                7
              
            
            
              
                10
              
              
                
                =
                
                  1
                
                ⋅
                7
                +
                3
              
            
            
              
                7
              
              
                
                =
                
                  2
                
                ⋅
                3
                +
                1
              
            
            
              
                3
              
              
                
                =
                
                  3
                
                ⋅
                1
                +
                0
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}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{aligned}}}
  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

  
    
      
        
          
            17
            10
          
        
        =
        1
        +
        
          
            
              7
              10
            
          
        
        =
        1
        +
        
          
            
              
                 
                 
                1
                 
                 
              
              
                
                  10
                  7
                
              
            
          
        
        =
        1
        +
        
          
            
              1
              
                1
                +
                
                  
                    
                      3
                      7
                    
                  
                
              
            
          
        
        =
        1
        +
        
          
            
              1
              
                1
                +
                
                  
                    
                      1
                      
                        
                          7
                          3
                        
                      
                    
                  
                
              
            
          
        
        =
        1
        +
        
          
            
              1
              
                1
                +
                
                  
                    
                      1
                      
                        2
                        +
                        
                          
                            
                              1
                              3
                            
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
    {\displaystyle {\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×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×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
        +
        
          
            
              
                
              
              
                
                  1
                
              
            
            
              
                
              
              
                
                  7
                  +
                  
                    
                      
                        
                          
                        
                        
                          
                            1
                          
                        
                      
                      
                        
                          
                        
                        
                          
                            15
                          
                        
                      
                    
                  
                
              
            
          
        
        =
        3
        +
        
          
            
              
                
              
              
                
                  1
                
              
            
            
              
                
              
              
                
                  
                    
                      
                        
                      
                      
                        
                          106
                        
                      
                    
                    
                      
                        
                      
                      
                        
                          15
                        
                      
                    
                  
                
              
            
          
        
        =
        3
        +
        
          
            
              
                
              
              
                
                  15
                
              
            
            
              
                
              
              
                
                  106
                
              
            
          
        
        =
        
          
            
              
                
              
              
                
                  333
                
              
            
            
              
                
              
              
                
                  106
                
              
            
          
        
        =
        3.141509...
      
    
    {\displaystyle [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
        ]
        =
        
          
            
              
                
              
              
                
                  355
                
              
            
            
              
                
              
              
                
                  113
                
              
            
          
        
        =
        3.1415929...
      
    
    {\displaystyle [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 kjederøker med et periodisk mønster.Kvadratrøtter oppstår ved løsningen av andregradsligningen. Deres løsning kan kan uttrykkes ved kjedebrøker. Et enkelt enksempel er ligningen

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

  
    
      
        
          
            
              
                x
              
              
                
                =
                a
                +
                
                  
                    
                      
                        
                      
                      
                        
                          1
                        
                      
                    
                    
                      
                        
                      
                      
                        
                          a
                          +
                          
                            
                              
                                
                                  
                                
                                
                                  
                                    1
                                  
                                
                              
                              
                                
                                  
                                
                                
                                  
                                    x
                                  
                                
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}x&=a+{\cfrac {1}{a+{\cfrac {1}{x}}}}\\\end{aligned}}}
  og gir dermed den uendelige kjedebrøken 
  
    
      
        x
        =
        [
        a
        ;
        a
        ,
        a
        ,
        a
        ,
        ⋯
        ]
      
    
    {\displaystyle x=[a;a,a,a,\cdots ]}
  . Når a = 1, gir dette det gyldne snitt φ = [1; 1, 1, 1, ... ] eller

  
    
      
        
          
            
              1
              2
            
          
        
        (
        1
        +
        
          
            5
          
        
        )
        =
        1
        +
        
          
            
              
                
              
              
                
                  1
                
              
            
            
              
                
              
              
                
                  1
                  +
                  
                    
                      
                        
                          
                        
                        
                          
                            1
                          
                        
                      
                      
                        
                          
                        
                        
                          
                            1
                            +
                            
                              
                                
                                  
                                    
                                  
                                  
                                    
                                      1
                                    
                                  
                                
                                
                                  
                                    
                                  
                                  
                                    
                                      1
                                      +
                                      
                                        
                                          
                                          
                                            ⋱
                                          
                                        
                                      
                                    
                                  
                                
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
    {\displaystyle {\tfrac {1}{2}}(1+{\sqrt {5}})=1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+{_{\ddots }}}}}}}}}
  Herfra kan man så utlede √5 = [2; 4, 4, 4, ...]. Den samme beregningen kan også benyttes til å omforme √2. Ved å sette y = x - 1 i ligningen  y 2 = 2, fremkommer den samme andregradsligningen for x med a = 2. Derfor er x = [2; 2, 2, 2, ...] og dermed √2 = [1; 2, 2, 2, ...].


=== Periodiske kjedebrøker ===
Hvis man for eksempel betrakter kjedebrøken √19 = [4;2,1,3,1,2,8,2,1,3,1,2,8,...], ser man at nevnerne etter a0 opptrer på en periodisk måte. Dette gjelder for alle irrasjonale kvadratrøtter.Generelt kan en slik kjedebrøk skrives som [a0;P ] hvor linjen over perioden P betyr at den gjentas i det uendelige.  For √19 er da P = (2,1,3,1,2,8). Med denne notasjonen kan man da skrive √2 = [1;2], mens √3 = [1;1,2] og √7 = [2;1,1,1,4].
Periodene har også en spesiell symmetri da de har formen P = (a1,a2,...,a2,a1,2a0). Bortsett fra det siste leddet, er de derfor palindromiske.


== Generaliserte kjedebrøker ==
En generell kjedebrøk er definert å ha formen

  
    
      
        x
        =
        
          a
          
            0
          
        
        +
        
          
            
              
                
              
              
                
                  
                    b
                    
                      1
                    
                  
                
              
            
            
              
                
              
              
                
                  
                    a
                    
                      1
                    
                  
                  +
                  
                    
                      
                        
                          
                        
                        
                          
                            
                              b
                              
                                2
                              
                            
                          
                        
                      
                      
                        
                          
                        
                        
                          
                            
                              a
                              
                                2
                              
                            
                            +
                            
                              
                                
                                  
                                    
                                  
                                  
                                    
                                      
                                        b
                                        
                                          3
                                        
                                      
                                    
                                  
                                
                                
                                  
                                    
                                  
                                  
                                    
                                      
                                        a
                                        
                                          3
                                        
                                      
                                      +
                                      
                                        
                                          
                                            
                                              
                                            
                                            
                                              
                                                
                                                  b
                                                  
                                                    4
                                                  
                                                
                                              
                                            
                                          
                                          
                                            
                                              
                                            
                                            
                                              
                                                
                                                
                                                ⋱
                                              
                                            
                                          
                                        
                                      
                                    
                                  
                                
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
        
        
      
    
    {\displaystyle 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
          
        
        +
        
          
            
              b
              
                1
              
            
            
              
                a
                
                  1
                
              
              +
            
          
        
        
          
            
              b
              
                2
              
            
            
              
                a
                
                  2
                
              
              +
            
          
        
        
          
            
              b
              
                3
              
            
            
              
                a
                
                  3
                
              
              +
            
          
        
        ⋯
      
    
    {\displaystyle 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
            π
          
        
        =
        1
        +
        
          
            
              1
              
                2
              
            
            
              3
              +
            
          
        
        
          
            
              2
              
                2
              
            
            
              5
              +
            
          
        
        
          
            
              3
              
                2
              
            
            
              7
              +
            
          
        
        ⋯
      
    
    {\displaystyle {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