Ułamek łańcuchowy

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

$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 $a_{0}$ jest liczbą całkowitą, a wszystkie pozostałe liczby $a_{n}$ są naturalne i dodatnie. Liczby $a_{1},a_{2},\dots ,a_{k}$ nazywamy mianownikami częściowymi ułamka łańcuchowego. W niektórych źródłach zezwala się, by liczby $a_{n}$ były rzeczywiste, a ułamki, w których $a_{0}\in \mathbb {Z}$ i $a_{1},\dots ,a_{k}\in \mathbb {N} _{+}$, nazywa się dodatkowo arytmetycznymi.

Zamiast powyższej „piętrowej” notacji ułamki łańcuchowe najczęściej zapisuje się w postaci ciągu $[a_{0};a_{1},a_{2},a_{3},\dots ,a_{k}].$ Spotykane są również inne notacje, między innymi notacja wprowadzona przez Pringsheima:

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

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}].$

Każdą liczbę rzeczywistą można zapisać w postaci ułamka łańcuchowego. Liczbom wymiernym odpowiadają ułamki skończone, natomiast liczbom niewymiernym – ułamki nieskończone. Dla ułamków łańcuchowych 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 ich rozwinięcie w ułamek łańcuchowy nie jest jednoznaczne. Staje się ono 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_{0}$ jest liczbą całkowitą, $a_{1},\dots ,a_{k}$ są liczbami naturalnymi, a $a_{k}>1.$ Rozwinięcie liczby niewymiernej w (nieskończony) ułamek łańcuchowy zawsze jest jednoznaczne.

Każdy okresowy ułamek łańcuchowy przedstawia pewną niewymierność kwadratową, tzn. niewymierny pierwiastek równania kwadratowego o współczynnikach całkowitych. Każda niewymierność kwadratowa rozwija się w okresowy arytmetyczny ułamek łańcuchowy.

Znajdowanie ułamków łańcuchowych

Algorytm znajdowania reprezentacji liczby $x$ w postaci ułamka łańcuchowego można opisać następująco:

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]$

Redukty, najlepsze wymierne przybliżenia

Niech $[a_{0};a_{1},a_{2},a_{3},\dots ]$ będzie ułamkiem łańcuchowym (skończonym lub nieskończonym), wówczas liczbę $[a_{0};a_{1},a_{2},\dots ,a_{n}]$ nazywamy $n$-tym reduktem tego ułamka łańcuchowego.

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.

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 ułamek ${\frac {p_{n}}{q_{n}}}$ jest $n$-tym reduktem rozwinięcia liczby $a\in \mathbb {R}$ w ułamek łańcuchowy, to dla każdej liczby wymiernej ${\frac {p}{q}}$ spełniającej warunek $0<q<q_{n}$ zachodzi nierówność

$\left\vert a-{\frac {p_{n}}{q_{n}}}\right\vert <\left\vert a-{\frac {p}{q}}\right\vert$.

Ponadto redukty parzyste przybliżają liczbę od dołu (z niedomiarem), a nieparzyste od góry (z nadmiarem).

Zobacz też

• stała Chinczyna
• Równanie Pella

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, Wolfram Research [dostęp 2020-12-12]  (ang.).
• Ułamki łańcuchowe – inny sposób zapisu liczb, blog beta-iks.pl, 19 sierpnia 2021 [dostęp 2023-07-08].