Ułamek łańcuchowy

Ułamek łańcuchowy, ułamek ciągły^[1] (skończony) jest to wyrażenie postaci:

${\displaystyle a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\stackrel {\ddots }{\qquad a_{k-2}+{\cfrac {1}{a_{k-1}+{\cfrac {1}{a_{k}}}}}}}}}}}}}$

gdzie ${\displaystyle a_{0}}$ jest liczbą całkowitą, a wszystkie pozostałe liczby ${\displaystyle a_{n}}$ są naturalne i większe od 0.

Zamiast notacji „piętrowej” najczęściej korzysta się z notacji „poziomej”, zapisując odpowiedni ułamek jako:

${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ,a_{k}].}$

Często wykorzystywana jest również notacja wprowadzona przez Pringsheima:

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

Ułamek łańcuchowy nieskończony definiujemy jako granicę ciągu ułamków skończonych (granica ta zawsze istnieje):

${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ]=\lim _{k\to \infty }[a_{0};a_{1},a_{2},a_{3},\dots ,a_{k}].}$

Jeżeli x jest wartością ułamka ${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ]}$ (skończonego lub nie), to ${\displaystyle [a_{0};a_{1},a_{2},\dots ,a_{n}]}$ nazywamy n-tym reduktem liczby x.

Okazuje się, że każdą liczbę rzeczywistą można zapisać w postaci ułamka łańcuchowego, przy czym liczbom wymiernym odpowiadają ułamki skończone, natomiast liczbom niewymiernym – ułamki nieskończone. Algorytm przedstawiania liczby x w postaci ułamka łańcuchowego można schematycznie zapisać następująco:

${\displaystyle x=[\lfloor x\rfloor ;1/(x-\lfloor x\rfloor )],}$

gdzie ${\displaystyle \lfloor x\rfloor }$ oznacza część całkowitą liczby x. Innymi słowy: ${\displaystyle a_{0}=\lfloor x\rfloor ,}$ a dalej postępuj podobnie z ${\displaystyle {\frac {1}{x-\lfloor x\rfloor }}.}$ W nieco bardziej sformalizowanej postaci:

1. ${\displaystyle r=x,\,n=0}$
2. ${\displaystyle a_{n}=\lfloor r\rfloor }$
3. JEŚLI ${\displaystyle r-a_{n}=0}$ – STOP
4. ${\displaystyle r=1/(r-a_{n}),\,n=n+1}$
5. PRZEJDŹ DO 2

Dla x = 2,35, otrzymujemy na przykład:

• ${\displaystyle r=2{,}35={\frac {47}{20}}}$
• ${\displaystyle a_{0}=\lfloor r\rfloor =2}$
• ${\displaystyle r={\frac {1}{{\frac {47}{20}}-2}}={\frac {20}{7}}}$
• ${\displaystyle a_{1}=\lfloor r\rfloor =2}$
• ${\displaystyle r={\frac {1}{{\frac {20}{7}}-2}}={\frac {7}{6}}}$
• ${\displaystyle a_{2}=\lfloor r\rfloor =1}$
• ${\displaystyle r={\frac {1}{{\frac {7}{6}}-1}}=6}$
• ${\displaystyle a_{3}=\lfloor r\rfloor =6}$

Zatem:

${\displaystyle 2{,}35=2+{\cfrac {1}{2+{\cfrac {1}{1+{\cfrac {1}{6}}}}}}=[2;2,1,6]}$

Dla ${\displaystyle p_{n},q_{n}}$ zdefiniowanych rekurencyjnie wzorami:

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

${\displaystyle p_{k+1}=a_{k+1}p_{k}+p_{k-1}}$

${\displaystyle q_{k+1}=a_{k+1}q_{k}+q_{k-1}}$

zachodzi ${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ,a_{n}]={\frac {p_{n}}{q_{n}}}.}$ Ponadto jest to postać nieskracalna tego ułamka.

Dla ułamków skończonych reprezentujących liczby wymierne zachodzi

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

czyli rozwinięcie nie jest jednoznaczne. Staje się jednoznaczne przy założeniu że ta ostatnia liczba jest większa od 1, tzn. każdą liczbę wymierną można jednoznacznie przedstawić w postaci ${\displaystyle [a_{0};a_{1},a_{2},\dots ,a_{k}]}$ gdzie a₀ jest liczbą całkowitą, ${\displaystyle a_{1},\dots ,a_{k}}$ są liczbami naturalnymi, ${\displaystyle a_{k}>1.}$

Rozwinięcie liczby niewymiernej w ułamek łańcuchowy zawsze jest jednoznaczne.

Kolejne redukty rozwinięcia danej liczby w ułamek łańcuchowy są najlepszymi przybliżeniami wymiernymi tej liczby o możliwie małych mianownikach. Dokładniej, jeżeli liczba wymierna ${\displaystyle {\frac {p}{q}},q\in \mathbb {N} ,q\neq 0}$ jest lepszym przybliżeniem liczby ${\displaystyle x}$ niż redukt liczby ${\displaystyle x}$ przedstawiony w postaci ułamka nieskracalnego, to mianownik ${\displaystyle q}$ tej liczby jest większy od mianownika tego reduktu^[2]. Ponadto redukty parzyste szacują liczbę od dołu, a nieparzyste od góry.

Zobacz też

• ułamek dziesiętny
• ułamek dziesiętny nieskończony

Przypisy

Bibliografia

• Władysław Narkiewicz: Teoria liczb. Warszawa: Państwowe Wydawnictwo Naukowe, 1977, s. 271–285.

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Continued Fraction, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-12]  (ang.).