Periodická pokračující část - Periodic continued fraction

V matematiky , nekonečná periodické řetězový zlomek je řetězový zlomek , které mohou být umístěny ve formě

${\ displaystyle x = a_ {0} + {\ cfrac {1} {a_ {1} + {\ cfrac {1} {a_ {2} + {\ cfrac {\ ddots} {\ quad \ ddots \ quad a_ { k} + {\ cfrac {1} {a_ {k + 1} + {\ cfrac {\ ddots} {\ quad \ ddots \ quad a_ {k + m-1} + {\ cfrac {1} {a_ {k + m} + {\ cfrac {1} {a_ {k + 1} + {\ cfrac {1} {a_ {k + 2} + {\ ddots}}}}}}}}}}}}}}} }}}$

kde po počátečním bloku dílčích jmenovatelů k + 1 následuje blok [ a _{k +1} ,  a _{k +2} , ... a _{k + m} ] dílčích jmenovatelů, který se opakuje pořád dokola, ad infinitum . Například lze rozšířit na periodický zlomek, a to jako [1,2,2,2, ...]. ${\ displaystyle {\ sqrt {2}}}$

Dílčími jmenovateli { a _i } mohou být obecně libovolná reálná nebo komplexní čísla. Tento obecný případ je zpracován v článku konvergenční problém . Zbývající část tohoto článku je věnována tématu jednoduchých pokračujících zlomků, které jsou také periodické. Jinými slovy, zbytek tohoto článku předpokládá, že všechny dílčí jmenovatele a _i ( i  ≥ 1) jsou kladná celá čísla.

Čistě periodické a periodické zlomky

Vzhledem k tomu, že všechny dílčí čitatele v pravidelném zlomku pokračování jsou rovny jednotce, můžeme přijmout zkratkovou notaci, ve které je výše zobrazený zlomek zapsán

${\ displaystyle {\ begin {aligned} x & = [a_ {0}; a_ {1}, a_ {2}, \ dots, a_ {k}, a_ {k + 1}, a_ {k + 2}, \ tečky, a_ {k + m}, a_ {k + 1}, a_ {k + 2}, \ dots, a_ {k + m}, \ dots] \\ & = [a_ {0}; a_ {1} , a_ {2}, \ dots, a_ {k}, {\ overline {a_ {k + 1}, a_ {k + 2}, \ dots, a_ {k + m}}}]] \ end {zarovnáno}} }$

kde na druhém řádku označí vinculum opakující se blok. Některé učebnice používají notaci

${\ displaystyle {\ begin {aligned} x & = [a_ {0}; a_ {1}, a_ {2}, \ dots, a_ {k}, {\ dot {a}} _ {k + 1}, a_ {k + 2}, \ dots, {\ dot {a}} _ {k + m}] \ end {zarovnáno}}}$

kde je opakující se blok označen tečkami nad jeho prvním a posledním termínem.

Pokud počáteční neopakující se blok není přítomen - tj. Pokud k = -1, a ₀ = a _m a

${\ displaystyle x = [{\ overline {a_ {0}; a_ {1}, a_ {2}, \ dots, a_ {m-1}}}],}$

regulární pokračující zlomek x je považován za čistě periodický . Například pravidelný pokračující zlomek pro zlatý poměr φ - daný [1; 1, 1, 1, ...] - je čistě periodický, zatímco pravidelný zlomek pro druhou odmocninu ze dvou - [1; 2, 2, 2, ...] - je periodický, ale nikoli čistě periodický.

Jako unimodulární matice

Takové periodické zlomky jsou v korespondenci jedna ku jedné se skutečnými kvadratickými iracionály . Korespondence je výslovně poskytována funkcí Minkowského otazníku . Tento článek také přezkoumává nástroje, které usnadňují práci s takovými pokračujícími zlomky. Zvažte nejprve čistě periodickou část

${\ displaystyle x = [{\ overline {0; a_ {1}, a_ {2}, \ dots, a_ {m}}}],}$

To lze ve skutečnosti psát jako

${\ displaystyle x = {\ frac {\ alfa x + \ beta} {\ gamma x + \ delta}}}$

s bytím celých čísel a splnění Explicitní hodnoty lze získat zápisem ${\ displaystyle \ alpha, \ beta, \ gamma, \ delta}$${\ displaystyle \ alpha \ delta - \ beta \ gamma = 1.}$

${\ displaystyle S = {\ begin {pmatrix} 1 & 0 \\ 1 & 1 \ end {pmatrix}}}$

který se nazývá „posun“, takže

${\ displaystyle S ^ {n} = {\ begin {pmatrix} 1 & 0 \\ n & 1 \ end {pmatrix}}}$

a podobně odraz, daný

${\ displaystyle T \ mapsto {\ začátek {pmatrix} -1 & 1 \\ 0 & 1 \ konec {pmatrix}}}$

tak to . Obě tyto matice jsou unimodulární , libovolné produkty zůstávají unimodulární. Poté, jak je uvedeno výše, má odpovídající matice tvar ${\ displaystyle T ^ {2} = I}$${\ displaystyle x}$

${\ displaystyle S ^ {a_ {1}} TS ^ {a_ {2}} T \ cdots TS ^ {a_ {m}} = {\ begin {pmatrix} \ alpha & \ beta \\\ gama & \ delta \ konec {pmatrix}}}$

a jeden má

${\ displaystyle x = [{\ overline {0; a_ {1}, a_ {2}, \ dots, a_ {m}}}] = {\ frac {\ alpha x + \ beta} {\ gamma x + \ delta} }}$

jako explicitní forma. Protože všechny položky matice jsou celá čísla, patří tato matice do modulární skupiny ${\ displaystyle SL (2, \ mathbb {Z}).}$

Vztah ke kvadratickým iracionálnostem

Kvadratický iracionální číslo je nerozumný skutečný kořen kvadratické rovnice

${\ displaystyle ax ^ {2} + bx + c = 0}$

kde koeficienty a , b a c jsou celá čísla a diskriminátor , b ² - 4 ac , je větší než nula. Které kvadratickou rovnicí každý kvadratický nerozumný lze zapsat ve tvaru

${\ displaystyle \ zeta = {\ frac {P + {\ sqrt {D}}} {Q}}}$

kde P , D a Q jsou celá čísla, D > 0 není dokonalý čtverec (ale nemusí být nutně bez čtverce) a Q rozdělí množství P ²  -  D (například (6+ √ 8 ) / 4). Takový kvadratický iracionál lze také zapsat v jiné formě se druhou odmocninou čísla bez čtverce (například (3+ √ 2 ) / 2), jak je vysvětleno pro kvadratické iracionály .

Uvažováním o úplných kvocientech periodických pokračujících zlomků dokázal Euler dokázat, že pokud x je pravidelný periodický zlomek, pak x je kvadratické iracionální číslo. Důkaz je přímý. Ze samotného zlomku lze sestrojit kvadratickou rovnici s integrálními koeficienty, které x musí splňovat.

Lagrange dokázal obrácenou Eulerovu větu: je-li x kvadratické iracionální, pak je pravidelné pokračování expanze zlomků x periodické. Vzhledem k kvadratickému iracionálnímu x lze sestrojit m různých kvadratických rovnic, z nichž každá má stejnou diskriminaci, které souvisejí s po sobě jdoucími úplnými kvocienty pravidelného pokračování expanze zlomků x k sobě navzájem. Protože těchto rovnic je pouze konečně mnoho (koeficienty jsou ohraničené), musí se nakonec opakovat úplné kvocienty (a také částečné jmenovatele) v pravidelném pokračujícím zlomku, který představuje x .

Snížené částky

Kvadratický surd se říká, že se sníží, jestliže a jeho konjugát uspokojí nerovnosti . Zlatý řez je například snížený surd, protože je větší než jedna a jeho konjugát je větší než -1 a menší než nula. Na druhou stranu druhá odmocnina dvou je větší než jedna, ale není redukovaným množstvím, protože její konjugát je menší než -1. ${\ displaystyle \ zeta = {\ frac {P + {\ sqrt {D}}} {Q}}}$${\ displaystyle \ zeta> 1}$ ${\ displaystyle \ eta = {\ frac {P - {\ sqrt {D}}} {Q}}}$${\ displaystyle -1 <\ eta <0}$${\ displaystyle \ phi = (1 + {\ sqrt {5}}) / 2 = 1,618033 ...}$${\ displaystyle (1 - {\ sqrt {5}}) / 2 = -0,618033 ...}$${\ displaystyle {\ sqrt {2}} = (0 + {\ sqrt {8}}) ​​/ 2}$${\ displaystyle - {\ sqrt {2}} = (0 - {\ sqrt {8}}) ​​/ 2}$

Galois dokázal, že pravidelný zlomek, který představuje kvadratický surd ζ, je čistě periodický právě tehdy, když ζ je redukovaný surd. Galois ve skutečnosti ukázal víc než tohle. Dokázal také, že pokud ζ je redukovaný kvadratický surd a η je jeho konjugát, pak pokračující zlomky pro ζ a pro (−1 / η) jsou čistě periodické a opakující se blok v jedné z těchto pokračujících zlomků je zrcadlovým obrazem opakujícího se bloku v druhém. V symbolech máme

${\ displaystyle {\ begin {aligned} \ zeta & = [{\ overline {a_ {0}; a_ {1}, a_ {2}, \ dots, a_ {m-1}}}]] \\ [3pt] {\ frac {-1} {\ eta}} & = [{\ overline {a_ {m-1}; a_ {m-2}, a_ {m-3}, \ dots, a_ {0}}}] \, \ end {zarovnáno}}}$

kde ζ je jakýkoli redukovaný kvadratický surd a η je jeho konjugát.

Z těchto dvou Galoisových vět lze odvodit výsledek, který Lagrange již zná. Pokud r  > 1 je racionální číslo, které není dokonalým čtvercem, pak

${\ displaystyle {\ sqrt {r}} = [a_ {0}; {\ overline {a_ {1}, a_ {2}, \ dots, a_ {2}, a_ {1}, 2a_ {0}}} ].}$

Zejména, pokud n je jakékoli jiné než čtvercové kladné celé číslo, pravidelné pokračující rozšiřování zlomků √ n obsahuje opakující se blok délky m , ve kterém první  dílčí jmenovatelé m - 1 tvoří palindromický řetězec.

Délka opakujícího se bloku

Analýzou sledu kombinací

${\ displaystyle {\ frac {P_ {n} + {\ sqrt {D}}} {Q_ {n}}}}$

které mohou vzniknout, když je ζ = ( P + √ D ) / Q rozšířeno jako běžný pokračující zlomek, Lagrange ukázal, že největší dílčí jmenovatel a _i v expanzi je menší než 2 √ D a že délka opakujícího se bloku je menší než 2, D .

V poslední době ostřejší argumenty založené na funkci dělitele ukázaly, že L ( D ), délka opakujícího se bloku kvadratického množství diskriminačního D , je dána vztahem

${\ displaystyle L (D) = {\ mathcal {O}} ({\ sqrt {D}} \ ln {D})}$

kde velké O znamená „řádově“ nebo „asymptoticky úměrné“ (viz velký O zápis ).

Kanonická forma a opakování

Následující iterační algoritmus lze použít k získání pokračujícího rozšiřování zlomků v kanonické formě ( S je jakékoli přirozené číslo, které není dokonalým čtvercem ):

${\ displaystyle m_ {0} = 0 \, \!}$

${\ displaystyle d_ {0} = 1 \, \!}$

${\ displaystyle a_ {0} = \ vlevo \ lfloor {\ sqrt {S}} \ vpravo \ rfloor \, \!}$

${\ displaystyle m_ {n + 1} = d_ {n} a_ {n} -m_ {n} \, \!}$

${\ displaystyle d_ {n + 1} = {\ frac {S-m_ {n + 1} ^ {2}} {d_ {n}}} \, \!}$

${\ displaystyle a_ {n + 1} = \ left \ lfloor {\ frac {{\ sqrt {S}} + m_ {n + 1}} {d_ {n + 1}}} \ right \ rfloor = \ left \ lfloor {\ frac {a_ {0} + m_ {n + 1}} {d_ {n + 1}}} \ right \ rfloor \ !.}$

Všimněte si, že m _n , d _n a a _n jsou vždy celá čísla. Algoritmus končí, když je tento triplet stejný jako ten, který se setkal dříve. Algoritmus lze také ukončit na _i, když _i = 2 a ₀ , což je snazší implementovat.

Expanze se od té doby bude opakovat. Posloupnost [ a ₀ ; a ₁ , a ₂ , a ₃ , ...] je pokračující expanze zlomků:

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

Příklad

Chcete-li získat √ 114 jako pokračující zlomek, začněte s m ₀  = 0; d ₀  = 1; a ₀  = 10 (10 ²  = 100 a 11 ²  = 121> 114 tak 10 výběru).

${\ displaystyle {\ begin {aligned} {\ sqrt {114}} & = {\ frac {{\ sqrt {114}} + 0} {1}} = 10 + {\ frac {{\ sqrt {114}} -10} {1}} = 10 + {\ frac {({\ sqrt {114}} - 10) ({\ sqrt {114}} + 10)} {{\ sqrt {114}} + 10}} \ \ & = 10 + {\ frac {114-100} {{\ sqrt {114}} + 10}} = 10 + {\ frac {1} {\ frac {{\ sqrt {114}} + 10} {14 }}}. \ end {zarovnáno}}}$

${\ displaystyle m_ {1} = d_ {0} \ cdot a_ {0} -m_ {0} = 1 \ cdot 10-0 = 10 \ ,.}$

${\ displaystyle d_ {1} = {\ frac {S-m_ {1} ^ {2}} {d_ {0}}} = {\ frac {114-10 ^ {2}} {1}} = 14 \ ,.}$

${\ displaystyle a_ {1} = \ vlevo \ lfloor {\ frac {a_ {0} + m_ {1}} {d_ {1}}} \ vpravo \ rfloor = \ vlevo \ lfloor {\ frac {10 + 10} {14}} \ right \ rfloor = \ left \ lfloor {\ frac {20} {14}} \ right \ rfloor = 1 \ ,.}$

Takže, m ₁  = 10; d ₁  = 14; a ₁  = 1.

${\ displaystyle {\ frac {{\ sqrt {114}} + 10} {14}} = 1 + {\ frac {{\ sqrt {114}} - 4} {14}} = 1 + {\ frac {114 -16} {14 ({\ sqrt {114}} + 4)}} = 1 + {\ frac {1} {\ frac {{\ sqrt {114}} + 4} {7}}}.}$

Dále m ₂  = 4; d ₂  = 7; a ₂  = 2.

${\ displaystyle {\ frac {{\ sqrt {114}} + 4} {7}} = 2 + {\ frac {{\ sqrt {114}} - 10} {7}} = 2 + {\ frac {14 } {7 ({\ sqrt {114}} + 10)}} = 2 + {\ frac {1} {\ frac {{\ sqrt {114}} + 10} {2}}}.}$

${\ displaystyle {\ frac {{\ sqrt {114}} + 10} {2}} = 10 + {\ frac {{\ sqrt {114}} - 10} {2}} = 10 + {\ frac {14 } {2 ({\ sqrt {114}} + 10)}} = 10 + {\ frac {1} {\ frac {{\ sqrt {114}} + 10} {7}}}.}$

${\ displaystyle {\ frac {{\ sqrt {114}} + 10} {7}} = 2 + {\ frac {{\ sqrt {114}} - 4} {7}} = 2 + {\ frac {98 } {7 ({\ sqrt {114}} + 4)}} = 2 + {\ frac {1} {\ frac {{\ sqrt {114}} + 4} {14}}}.}$

${\ displaystyle {\ frac {{\ sqrt {114}} + 4} {14}} = 1 + {\ frac {{\ sqrt {114}} - 10} {14}} = 1 + {\ frac {14 } {14 ({\ sqrt {114}} + 10)}} = 1 + {\ frac {1} {\ frac {{\ sqrt {114}} + 10} {1}}}.}$

${\ displaystyle {\ frac {{\ sqrt {114}} + 10} {1}} = 20 + {\ frac {{\ sqrt {114}} - 10} {1}} = 20 + {\ frac {14 } {{\ sqrt {114}} + 10}} = 20 + {\ frac {1} {\ frac {{\ sqrt {114}} + 10} {14}}}.}$

Nyní se vraťte zpět k druhé rovnici výše.

V důsledku toho je jednoduchá pokračující část pro druhou odmocninu 114

${\ displaystyle {\ sqrt {114}} = [10; {\ overline {1,2,10,2,1,20}}]. \,}$ (sekvence A010179 v OEIS )

√ 114 je přibližně 10,67707 82520. Po jednom rozšíření opakování získá pokračující zlomek racionální zlomek, jehož desetinná hodnota je přibližně. 10,67707 80856, relativní chyba 0,0000016% nebo 1,6 dílů na 100 000 000. ${\ displaystyle {\ frac {21194} {1985}}}$

Zobecněná pokračující frakce

Rychlejší metodou je vyhodnotit její zobecněný pokračující zlomek . Z vzorce odvozeného tam :

${\ displaystyle {\ sqrt {z}} = {\ sqrt {x ^ {2} + y}} = x + {\ cfrac {y} {2x + {\ cfrac {y} {2x + {\ cfrac {y} {2x + \ ddots}}}}}} = x + {\ cfrac {2x \ cdot y} {2 (2z-y) -y - {\ cfrac {y ^ {2}} {2 (2z-y) - {\ cfrac {y ^ {2}} {2 (2z-y) - \ ddots}}}}}}$

a skutečnost, že 114 je 2/3 cesty mezi 10 ² = 100 a 11 ² = 121, má za následek

${\ displaystyle {\ sqrt {114}} = {\ cfrac {\ sqrt {1026}} {3}} = {\ cfrac {\ sqrt {32 ^ {2} +2}} {3}} = {\ cfrac {32} {3}} + {\ cfrac {2/3} {64 + {\ cfrac {2} {64 + {\ cfrac {2} {64 + {\ cfrac {2} {64+ \ ddots}} }}}}}} = = {\ cfrac {32} {3}} + {\ cfrac {2} {192 + {\ cfrac {18} {192 + {\ cfrac {18} {192+ \ ddots}}} }}},}$

což je jednoduše výše uvedené [10; 1,2, 10,2,1, 20,1,2] hodnocené při každém třetím semestru. Spojením párů frakcí vznikne

${\ displaystyle {\ sqrt {114}} = {\ cfrac {\ sqrt {32 ^ {2} +2}} {3}} = {\ cfrac {32} {3}} + {\ cfrac {64/3 } {2050-1 - {\ cfrac {1} {2050 - {\ cfrac {1} {2050- \ ddots}}}}}} = {\ cfrac {32} {3}} + {\ cfrac {64} {6150-3 - {\ cfrac {9} {6150 - {\ cfrac {9} {6150- \ ddots}}}}}}}$

který je nyní hodnocen na třetím semestru a poté každých šest semestrů. ${\ displaystyle [10; 1,2, {\ overline {10,2,1,20,1,2}}}}$

Viz také

• Hermitin problém
• Metoda pokračování zlomku výpočtu druhé odmocniny
• Omezené částečné kvocienty
• Pokračující zlomková faktorizace

Poznámky

Reference

• Long, Calvin T. (1972), Elementární úvod do teorie čísel (2. vydání), Lexington: DC Heath and Company , LCCN   77-171950
• Pettofrezzo, Anthony J .; Byrkit, Donald R. (1970), Elements of Number Theory , Englewood Cliffs: Prentice Hall , LCCN   77-81766
• Rockett, Andrew M .; Szüsz, Peter (1992). Pokračující zlomky . World Scientific. ISBN   981-02-1052-3 .