Ułamek łańcuchowy

Ułamek łańcuchowy (skończony) jest to wyrażenie postaci:

$a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\stackrel{\ddots}{{{\ \ \ \ \ a_{k-2}+\cfrac{1}{a_{k-1}+\cfrac{1}{a_k}}}}}}}}$

gdzie a₀ jest liczbą całkowitą, a wszystkie pozostałe liczby 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:

$[a_0; a_1, a_2, a_3, \dots, a_k]\;$.

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

$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):

$[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 $[a_0;a_1,a_2,a_3,\dots]\;$ (skończonego lub nie), to $[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:

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

gdzie $\lfloor x \rfloor$ oznacza część całkowitą liczby x. Innymi słowy: $a_0 = \lfloor x \rfloor$, a dalej postępuj podobnie z $1/(x-\lfloor x\rfloor)$. W nieco bardziej sformalizowanej postaci:

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

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

• $r=2,35=\frac{47}{20}$
• $a_0=\lfloor r\rfloor = 2$
• $r=\frac{1}{\frac{47}{20}-2}=\frac{20}{7}$
• $a_1= \lfloor r\rfloor = 2$
• $r=\frac{1}{\frac{20}{7}-2}=\frac{7}{6}$
• $a_2= \lfloor r\rfloor = 1$
• $r=\frac{1}{\frac{7}{6}-1}=6$
• $a_3= \lfloor r\rfloor = 6$

Zatem:

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

Dla $p_n, q_n$ zdefiniowanych rekurencyjnie wzorami:

$p_{-1}=1, \, q_{-1}=0, \, p_0 = a_0, \, q_0=1$

$p_{k+1}=a_{k+1}p_k+p_{k-1}$

$q_{k+1}=a_{k+1}q_k+q_{k-1}$

zachodzi $[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 $[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 $[a_0;a_1,a_2,\dots,a_k]$ gdzie a₀ jest liczbą całkowitą, $a_1,\dots,a_k$ są liczbami naturalnymi, $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 $\frac{p}{q}, q\in\mathbb{N}, q\neq 0$ jest lepszym przybliżeniem liczby $x\;$ niż redukt liczby $x\;$ przedstawiony w postaci ułamka nieskracalnego, to mianownik $q\;$ tej liczby jest większy od mianownika tego reduktu. Ponadto redukty parzyste szacują liczbę od dołu, a nieparzyste od góry.

Bibliografia

• Władysław Narkiewicz: Teoria liczb. Warszawa: PWN, 1977, s. 271-285.

Zobacz też

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