Ułamek łańcuchowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 a0 jest liczbą całkowitą, a wszystkie pozostałe liczby annaturalne 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 a0 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[1]. Ponadto redukty parzyste szacują liczbę od dołu, a nieparzyste od góry.

Przypisy

  1. Wacław Sierpiński: Arytmetyka teoretyczna. Warszawa: PWN, 1959, s. 249-250.

Bibliografia[edytuj | edytuj kod]

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

Zobacz też[edytuj | edytuj kod]