W szkole poznajemy różne sposoby zapisu liczb takie jak np. zapis dziesiętny czy, w przypadku liczb wymiernych, ułamki zwykłe. Prawie nigdy nie wspomina się jednak o ułamkach łańcuchowych. A szkoda! Bo ułamki te są bardzo ciekawe. Mają nawet zastosowania i to nie tylko w matematyce!
Jednym z ich najbardziej znanych zastosowań jest to, że pozwalają znajdować, w pewnym sensie najlepsze, przybliżenia wymierne liczb rzeczywistych. Oprócz wszelkiego rodzaju obliczeń praktycznych fakt ten może mieć także inne zastosowania, o których jeszcze wspomnimy. Ciekawszym zastosowaniem jest ich wykorzystywanie w krypotoanalizie do prób efektywnego łamania szyfrów opartych na algorytmie RSA np. tzw. atak Wienera.
Celem tego wpisu jest wprowadzenie w tematykę ułamków łańcuchowych oraz pokazanie, że są nie tylko innym sposobem zapisywania liczb (jak i funkcji), lecz również interesującym, narzędziem matematycznym mającym zastosowania nie tylko w matematyce.
Liczby wymierne to te, które możemy przedstawiać w postaci ułamków zwykłych tj. ilorazu dwu liczb całkowitych. Innym sposobem przedstawienia liczb rzeczywistych jest rozwinięcie dziesiętne, które w przypadku liczb wymiernych jest skończone lub nieskończone okresowe. Przykładowo \[\dfrac 15=0,2\textrm{ oraz }\dfrac 13=0,(3).\] Liczb niewymiernych nie da się zapisać w postaci ilorazu dwóch liczb całkowitych. Możemy się jednak posłużyć zapisem dziesiętnym. Liczba \[0,12345678910111213…,\] mimo iż bez trudu jesteśmy w stanie odgadnąć zasadę którą podążają dalsze cyfry jej rozwinięcia, jest niewymierna. Jej rozwinięcie dziesiętne nie jest ani skończone ani okresowe.
Z kolei w rozwinięciu, znanej chyba wszystkim, liczby \[\pi=3,1415926535897932384626433832795028…\] ciężko znaleźć jakąkolwiek zasadę pozwalającą wypisywać kolejne cyfry po przecinku. Nie tylko w systemie dziesiętnym lecz również w innych. Np. początkowe cyfry rozwinięcia \(\pi\) w systemie o podstawie 7 prezentują się następująco: \[\pi_{(7)}=3,066365143203613411026340224465\ldots\] Możemy jedynie, stosując mniej lub bardziej wyszukane metody, wyznaczać kolejne cyfry. Co jakiś czas zresztą można usłyszeć doniesienia o nowym rekordzie w wyznaczaniu ilości cyfr po przecinku liczby \(\pi\). W czasie pisania tego wpisu, tj. w sierpniu 2021, szwajcarscy uczeni z uniwersytetu mieszczącego się w kantonie o dźwięcznej nazwie Gryzonia ogłosili iż udało im się wyznaczyć rozwinięcie \(\pi\) do \(62,8\) biliona miejsc po przecinku. Co, o ile jest to prawdą, stanowi nowy rekord. Link do oświadczenia.
Jednym ze sposobów coraz dokładniejszego przybliżania wartości liczb jest użycie szeregów. Liczbę \(\pi\) z ich wykorzystaniem można np. przedstawić następująco \[\pi=4-\dfrac 43+\dfrac 45-\dfrac 47+\dfrac 49-…=\sum_{n=0}^\infty\dfrac{4\cdot (-1)^n}{2n+1}.\]
Wzór ten jest, w zasadzie, szczególnym przypadkiem ogólniejszej równości \[\textrm{arctg }{x}=x-\dfrac{x^3}{3}+\dfrac{x^5}{5}-\dfrac{x^7}{7}+\cdots.\] Wystarczy przyjąć \(x=1\) i otrzymaną równość dla \(\textrm{arctg }1=\frac{\pi}{4}\) pomnożyć przez 4. Dzięki powyższemu szeregowi dostajemy narzędzie pozwalające wyznaczyć \(\pi\) z dowolną dokładnością. Jego efektywność, czyli to ile wyrazów należy zsumować by otrzymać zadaną dokładność, jest już innym zagadnieniem.
Liczbę \(\pi\) można przedstawić na wiele sposobów jako sumę nieskończonego szeregu. Jak widać są wśród nich takie, które pozwalają to zrobić tak, aby kolejne sumowane liczby spełniały prostą zależność.
Można także zamiast sum wykorzystywać iloczyny nieskończone jak np. w słynnym wzorze Wallisa \[\dfrac{\pi}{2}=\dfrac{2}{1}\cdot\dfrac{2}{3}\cdot\dfrac{4}{3}\cdot\dfrac{4}{5}\cdot\dfrac{6}{5}\cdot\dfrac{6}{7}\cdot\cdots=\prod_{n=1}^\infty\dfrac{2n\cdot 2n}{(2n-1)(2n+1)}\]
Innym sposobem przedstawiania liczb, przy pomocy działań niekoniecznie skończonych, są ułamki łańcuchowe. Być może będzie to dla niektórych zaskakujące, ale \[\pi=3+\dfrac{1^2}{6+\dfrac{3^2}{6+\dfrac{5^2}{6+\dfrac{7^2}{6+\cdots}}}}\]
Właśnie wyrażenia postaci \[a_0+\dfrac{b_1}{a_1+\dfrac{b_2}{a_2+\dfrac{b_3}{a_3+\dfrac{b_4}{a_4+\cdots}}}}\] nazywamy ułamkami łańcuchowymi. Nas najbardziej interesować będą tzw. proste ułamki łańcuchowe, tj. takie, w których wszystkie \(b_i=1\) oraz \(a_i\) są liczbami naturalnymi dodatnimi dla \(i\geqslant 1\). O liczbie \(a_0\) zakładamy, że jest całkowita. Może być ujemna. Ułamki proste mają więc postać \[a_0+\dfrac{1}{a_1+\dfrac{1}{a_2+\dfrac{1}{a_3+\dfrac{1}{a_4+\cdots}}}}\] Możemy je zapisywać stosując wygodniejszą notację \([a_0;a_1, a_2, \ldots]\). Ułamki częściowe \([a_0;a_1,a_2,a_3,\ldots, a_n]\) nazywamy reduktami. Ponieważ \(a_i\gt 0\) dla \(i\geqslant 1\), to każdy redukt jest liczbą poprawnie określoną.
Jeżeli taki ułamek jest skończony (tzn. ciąg \((a_n)\) jest skończony), to nietrudno zauważyć, że przedstawia pewną liczbę wymierną. Wystarczy zwinąć go od końca. Przykładowo \[2+\dfrac{1}{3+\dfrac{1}{2}}=2+\dfrac{1}{\dfrac{7}{2}}=2+\dfrac{2}{7}=\dfrac{16}{7}\]
Gdy ciąg \((a_n)\) jest nieskończony, to pojawia się naturalne pytanie jaki jest sens liczbowy wyrażenia \[[a_0;a_1,a_2,a_3,\ldots]?\] Odpowiedź jest bardzo prosta. Możemy z nim stowarzyszyć ciąg reduktów \[r_1=[a_0;a_1], r_2=[a_0;a_1,a_2], \ldots ,r_n=[a_0;a_1,a_2,\ldots, a_n], \ldots\] Są one liczbami wymiernymi i za wartość \([a_0;a_1,a_2,a_3,\ldots]\) przyjąć granicę tego ciągu. Nie jest jednak takie oczywiste, że ta granica istnieje. Okazuje się, że istnieje dla każdego ułamka prostego i nie tylko. Jeżeli rozważymy ułamki, w których liczby \(a_i\) są, być może poza \(a_0\), dowolnymi liczbami dodatnimi (niekoniecznie całkowitymi), to proste kryterium zbieżności daje twierdzenie Seidela-Sterna
Twierdzenie (Seidel – Stern)
Jeżeli \(a_n\gt 0\) dla \(n\geqslant 1\), to ciąg \(([a_0;a_1,\ldots,a_n])\) ma granicę wtedy i tylko wtedy, gdy szereg \[\sum_{n=0}^\infty a_n\] jest rozbieżny.
Teraz pokażemy jak przedstawić dowolną liczbę rzeczywistą \(x\) w postaci ułamka łańcuchowego. W tym celu przypomnimy najpierw pojęcie części całkowitej. Jeżeli \(x\) jest liczbą rzeczywistą, to jej częścią całkowitą jest największa liczba całkowita \(\lfloor x\rfloor\) nie większa od \(x\). Np. \(\lfloor 5\rfloor=5, \lfloor 2,6\rfloor=2\) oraz \(\lfloor -3,3\rfloor=-4\).
Na początek zajmiemy się liczbami wymiernymi pokazując algorytm na przykładzie liczby \(x=\dfrac{87}{38}\).
Żeby wyznaczyć \(a_0\) dzielimy 87 przez 38 otrzymując 2 (czyli \(\lfloor x\rfloor\)) oraz resztę 11, tzn.
\[\dfrac{87}{38}=2+\dfrac{11}{38}\] Otrzymaliśmy \(a_0\) oraz ułamek mający 11 w liczniku. My jednak chcemy mieć 1. Można to osiągnąć \[2+\dfrac{11}{38}=2+\dfrac{1}{\frac{38}{11}}\] Powtarzamy teraz proces dla ułamka \(\dfrac{38}{11}\) co prowadzi nas do równości \[\dfrac{87}{38}=2+\dfrac{11}{38}=2+\dfrac{1}{3+\frac{5}{11}}\] Znowu robimy to samo tym razem dla ułamka \[\dfrac{1}{\dfrac{5}{11}}=\dfrac{11}{5}=2+\dfrac{1}{5}\] co prowadzi nas do ostatecznego wyniku \[\dfrac{87}{38}=2+\dfrac{1}{3+\dfrac{1}{2+\dfrac{1}{5}}}\] tzn. \(\dfrac{87}{38}=[2;3,2,5]\). W kolejnych krokach wykonywaliśmy następujące dzielenia z resztą\[\dfrac{87}{38}, \dfrac{38}{11}, \dfrac{11}{5}, \dfrac{5}{1}.\] Uprzednie mianowniki stawały się licznikami, a reszty mianownikami. Ci co znają algorytm Euklidesa bez trudu dostrzegli głębokie podobieństwo.
Zwróćmy uwagę, że \[\dfrac{87}{38}=2+\dfrac{1}{3+\dfrac{1}{2+\dfrac{1}{5}}}= \dfrac{87}{38}=2+\dfrac{1}{3+\dfrac{1}{2+\dfrac{1}{4+\dfrac{1}{1}}}}\] czyli możemy liczby wymierne przedstawiać w postaci ułamka na dwa sposoby. Prawdziwe jest przy tym następujące twierdzenie:
Twierdzenie
Każdy skończony prosty ułamek łańcuchowy przedstawia pewną liczbę wymierną. Każdą liczbę wymierną można przedstawić w postaci skończonego prostego ułamka łańcuchowego \([a_0;a_1,\ldots,a_n]\). Przedstawienie to jest jednoznaczne z wyjątkiem, że \([a_0;a_1,\ldots,a_n]=[a_0;a_1,\ldots,a_n-1,1]\).
Algorytm Euklidesa, a tym samym znajdowanie rozwinięcia liczby wymiernej w prosty ułamek łańcuchowy, mają ciekawą interpretację geometryczną. Pokażemy ją na przykładzie ułamka \(\dfrac{87}{38}\). Ułamki łańcuchowe mają jeszcze inną interpretację geometryczną. O niej powiemy sobie później. Zacznijmy od prostokąta, którego boki mają długość 87 oraz 38 pewnych jednostek.
Prostokąt ten wypełniamy kwadratami o boku 38 (czyli krótszy bok prostokąta) tak jak na rysunku poniżej. Mieszczą się dwa a reszta jest prostokątem o bokach 38 oraz 11.
Proces powtarzamy. Tym razem prostokąt o bokach 11 oraz 38 wypełniamy tyloma kwadratami o boku 11 ile się zmieści.
Dopóki proces się nie zakończy, to w każdym kolejnym kroku otrzymamy prostokąt, który wypełniamy kwadratami o boku nie dłuższym od drugiego. Wykorzystaliśmy prostokąt o bokach 87 oraz 38. Jednakże mogliśmy użyć każdego prostokąta, którego stosunek boków byłby równy \(\dfrac{87}{38}\).
Znajdywanie rozwinięć liczb niewymiernych w proste ułamki łańcuchowe jest niemal identyczne. Niewymierność sprawia jednak, że proces ten się nigdy nie kończy. Pokażemy go na przykładzie liczby \(\pi\).
Jak wcześniej, \(a_0=\lfloor\pi\rfloor=3\). Z tego mamy, że \[\pi=3+s_0\] gdzie \(x_0=\pi-\lfloor\pi\rfloor=0,1415192…\). Stosujemy ten sam trik co wcześniej, tzn. bierzemy odwrotność \(x_0\) zapisując w równoważnej formie \[\pi=3+\dfrac{1}{\dfrac{1}{x_0}}\] Ponieważ \(0\lt x_0\lt 1\), to \(\dfrac{1}{x_0}\gt 1\). Dokładniej \(\dfrac{1}{x_0}=7,062513…\) Wobec tego \(a_1=7\). Proces powtarzamy dla liczby \[\dfrac{1}{x_0}-\left\lfloor\dfrac{1}{x_0}\right\rfloor=0,062513…\] oraz kolejnych tak otrzymanych. Okaże się, że \[\pi=[3;7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, \ldots]\]
W ogólności, dla liczby niewymiernej \(x\) mamy \(a_k=\lfloor x_k\rfloor\), gdzie \(x_0=x\) oraz \[x_{k+1}=\dfrac{1}{x_k-a_k}\] dla \(k\geqslant 0\). Ponieważ \(x\) jest niewymierna, to \(x_k-a_k\neq 0\).
Pojawia się pewien problem. O ile w przypadku liczb wymiernych było jasne z konstrukcji algorytmu, że otrzymany ułamek jest równy wyjściowej liczbie \(x\), o tyle w przypadku liczb wymiernych aż takie oczywiste to nie jest. Ponadto czy daną liczbę niewymierną można przedstawić w postaci ułamka prostego jednoznacznie?
Twierdzenie
Każdą liczbę niewymierną \(x\) można przedstawić w sposób jednoznaczny w postaci nieskończonego prostego ułamka łańcuchowego \([a_0;a_1,a_2,a_3,\ldots]\), gdzie liczby \(a_i\) otrzymujemy przy pomocy algorytmu opisanego powyżej. Każdy nieskończony prosty ułamek łańcuchowy przedstawia pewną liczbę niewymierną.
Podobnie jak w przypadku rozwinięcia dziesiętnego ciężko znaleźć, o ile jakaś istnieje, regułę według której pojawiają się kolejne liczby w rozwinięciu \(\pi\) w ułamek prosty. W przypadku niektórych innych, dobrze nam znanych, liczb niewymiernych takie reguły można łatwo dostrzec. Może to być zaskakujące, ale \[e=[2;1,2,1,1,4,1,1,6,1,1,8,1,1,10,\ldots]\] Z kolei bez trudu można zweryfikować, że \[\sqrt{2}=[1;2,2,2,2,\ldots]=[1;\overline{2}],\] gdzie kreska oznacza, że dana część powtarza się w nieskończoność. Podobnie, \[\sqrt{7}=[2;\overline{1,1,1,4}], \dfrac{24-\sqrt{15}}{17}=[1;5,\overline{2,3}]\] zaś słynna złota proporcja ma przedstawienie \[[1;1,1,1,1,\ldots]=[1;\overline{1}]\] Ogólnie prawdziwe jest następujące twierdzenie.
Twierdzenie
Rozwinięcie liczby niewymiernej w prosty ułamek łańcuchowy jest od pewnego miejsca okresowe wtedy i tylko wtedy, gdy jest niewymiernym rozwiązaniem równania kwadratowego o współczynnikach całkowitych.
Innymi słowy liczba ma rozwinięcie (od pewnego miejsca) okresowe w ułamek prosty wtedy i tylko wtedy, gdy jest postaci \[\dfrac{B+\sqrt{D}}{A},\] gdzie wszystkie liczby są całkowite, \(A\neq 0, D\gt 0\) oraz \(D\) nie jest kwadratem liczby naturalnej. Dowód w jedną stronę, tj. że każde niewymierne rozwiązanie równania kwadratowego o współczynnikach wymiernych ma okresowe przedstawienie w postaci ułamka prostego, zawdzięczamy Lagrange’owi.
Zwróćmy uwagę na pewną rzecz. Rozwinięcie dziesiętne pozwala nam stowarzyszyć z każdą liczbą rzeczywistą ciąg liczb całkowitych. W przypadku \(\pi\) będzie to ciąg \(3, 1, 4, 1, 5, 9,\ldots\). Jeżeli zapiszemy \(\pi\) w innym systemie, to otrzymamy ciąg, w którym na pierwszym miejscu nadal będzie 3 (być może zapisane inaczej, np. jako 11 w systemie dwójkowym) a pozostałe liczby będą inne.
Z kolei przedstawienie liczby rzeczywistej w postaci prostego ułamka łańcuchowego zawsze będzie prowadzić do ciągu tych samych liczb bez względu na to w jakim systemie liczbowym zapisujemy liczby. Mogą one jedynie zostać zapisane przy pomocy innych symboli. Z tego względu możemy powiedzieć, że postać ułamka prostego jest bardziej naturalna niż postać dziesiętna. Choć ta druga ma istotną zaletę, znacznie bardziej nadaje się do wszelkiego rodzaju obliczeń. W przypadku ułamków łańcuchowych nawet obliczanie kolejnych reduktów, mimo znajomości rozwinięcia liczby w ułamek prosty może wydawać się zadaniem żmudnym.
Na szczęście kolejne redukty spełniają prostą zależność rekurencyjną. Niech \(r_n=\dfrac{p_n}{q_n}\) będzie, w postaci nieskracalnej, n-tym reduktem ułamka \([a_0;a_1,a_2,\ldots]\). Przyjmijmy \[p_{-2}=0,\ q_{-2}=1,\ p_{-1}=1,\ q_{-1}=0\] okazuje się, że wówczas (co łatwo pokazać indukcyjnie) dla \(k\geqslant 0\) mamy \[\begin{array}{lllll}p_k & = & p_{k-1}a_k & + & p_{k-2},\\ q_k & = & q_{k-1}a_k & + & q_{k-2} \end{array}\] Powyższe zależności pozwalają z łatwością wyznaczać kolejne redukty, o ile znamy kolejne \(a_i\) występujące w rozwinięciu danej liczby w ułamek prosty.
Z algorytmu przedstawiania liczby \(x\) w postaci ułamka prostego łatwo się domyślić, że kolejne redukty są pewnymi, zapewne coraz lepszymi, przybliżeniami \(x\). Spójrzmy na liczbę \(\pi\). Jej kolejne redukty to \[3, \dfrac{22}{7}, \dfrac{333}{106}, \dfrac{355}{113}, \dfrac{103993}{33102},\ldots\] Już Archimedes potrafił oszacować, że \(\dfrac{223}{71}\lt\pi\lt\dfrac{22}{7}\). Natomiast chińscy matematycy już w V wieku wiedzieli, że \(\dfrac{355}{113}\) jest bardzo dobrym przybliżeniem \(\pi\). Fakt ten będzie jeszcze bardziej widoczny, gdy poznamy drugą interpretację geometryczną przedstawiania liczb w postaci ułamka prostego.
Dla prostoty punkt płaszczyzny \((p,q)\) utożsamiamy z wektorem \([p,q]\).
Niech \(\alpha\) będzie liczbą rzeczywistą dodatnią. Dla liczb ujemnych proces wygląda podobnie. Narysujmy półprostą \(l: y=\alpha x\) dla \(x\geqslant 0\). Zaczynamy od wektorów/punktów \[R_{-2}=[1,0]\textrm{ oraz } R_{-1}=[0,1]\] Punkt \(R_{-2}\) znajduje się poniżej półprostej \(l\) zaś \(R_{-1}\) powyżej.
Teraz do wektora \(R_{-2}\) dodajemy tyle razy \(R_{-1}=[1,0]\), otrzymując nowy wektor \(R_0=R_{-2}+a_0R_{-1}\), aż dodanie kolejnego \(R_{-1}\) sprawi, że znajdziemy się nad półprostą \(l\).
W naszym przypadku możemy jedynie raz dodać \(R_{-1}\) do \(R_{-2}\) aby znajdować się pod lub na półprostej. Dodanie dwukrotności \(R_{-1}\) sprawi, że znajdziemy się nad półprostą. Wobec tego \(a_0=1\). Zauważmy, że proces ten odpowiada po prostu braniu części całkowitej. Tzn. \(a_0=\lfloor \alpha\rfloor\). Otrzymaliśmy punkt \(R_0=(1,a_0)\) o współrzędnych całkowitych, który znajduje się nie dalej od półprostej \(l\) niż \(R_{-2}\) oraz \(R_{-1}\).
Punkt \(R_{-1}\) znajduje się nad półprostą. Dodajemy do niego tyle razy wektor \(R_0\) aż kolejne jego dodanie sprawi, że znajdziemy się pod półprostą. W naszym przypadku możemy dodać dwukrotności \(R_0\), tzn. \(a_1=2\).
Otrzymaliśmy kolejny punkt \(R_1\) o współrzędnych całkowitych znajdujący się bliżej półprostej \(l\) niż punkty poprzednie.
W ogólności otrzymujemy \(R_{k}=R_{k-2}+a_kR_{k-1}\). Jeżeli \(R_k\) znajduje się na półprostej \(l\), to w tym momencie kończymy proces. Analogia do wzorów rekurencyjnych opisujących liczniki i mianowniki kolejnych reduktów ułamków łańcuchowych jest oczywista i jak się łatwo domyślić współrzędne \(R_k\), to licznik oraz mianownik k-tego reduktu ułamka \(\alpha=[a_0;a_1,a_2,\ldots]\) w postaci ułamka nieskracalnego. Choć nie jest to takie oczywiste na pierwszy rzut oka.
Znając tę interpretację geometryczną możemy zauważyć, że kolejne redukty mają wartości naprzemienne raz mniejszą, raz większą od \(\alpha\). W ogólności \[r_0\lt r_2\lt r_4\lt\ldots\lt\alpha\lt\ldots\lt r_{2n-1}\lt r_{2n-3}\lt\ldots\lt r_3\lt r_1\]
Jeżeli wektor/punkt \(R_n\) znajduje się pod półprostą \(l\), to ,,rośnie” wolniej niż \(l\). Dodając go do znajdującego się nad \(l\) wektora \(R_{n-1}\) zbliżamy się do \(l\). Ogólnie \[d_n\gt d_{n+1},\] gdzie \(d_n\), to odległość \(R_n\) od \(l\).
Korzystając ze wzoru na odległość punktu od prostej, nietrudno pokazać, że \[d_n=d_{n-2}+a_nd_{n-1}\] tzn. \[0\leqslant d_{n-2}-a_nd_{n-1}\lt d_{n-1}\] dzieląc przez \(d_{n-1}\) otrzymujemy \[a_n\leqslant\dfrac{d_{n-2}}{d_{n-1}}\lt a_n+1\] czyli \[a_n=\left\lfloor\dfrac{d_{n-2}}{d_{n-1}}\right\rfloor \] Ponadto \[\dfrac{d_{n-2}}{d_{n-1}}=a_n+\dfrac{d_n}{d_{n-1}}\] Czyli otrzymaliśmy znaną zależność! Przyjmując \(x_n=\dfrac{d_{n-2}}{d_{n-1}}\) otrzymujemy \[x_{n+1}=\dfrac{1}{x_n-a_n}\textrm{ oraz }a_n=\lfloor x_n\rfloor\] Łatwo też zweryfikować, że \(\alpha=\dfrac{d_{-2}}{d_{-1}}\) co pokazuje, że istotnie współrzędne punktów \(R_n\) to liczniki i mianowniki kolejnych reduktów ułamka \(\alpha=[a_0;a_1,a_2,\ldots]\).
Wspomnieliśmy, że kolejne redukty ułamka prostego \(x=[a_0;a_1,a_2,\ldots]\) stanowią coraz lepsze przybliżenia liczby \(x\). Pojawia się pytanie jak dobre?
Twierdzenie
Jeżeli \(x=[a_0;a_1,a_2,\ldots]\) oraz \(\dfrac{p_n}{q_n}=[a_0;a_1,\ldots,a_n]\) jest ułamkiem nieskracalnym, to \[\left|x-\dfrac{p_n}{q_n}\right|\lt\dfrac{1}{q^2_n}\]
Z tego twierdzenia wynika np., że \[\left|\pi-\dfrac{22}{7}\right|\lt\dfrac{1}{49}\textrm{ oraz } \left|\pi-\dfrac{355}{113}\right|\lt\dfrac{1}{113^2}=\dfrac{1}{12769}\] co tylko potwierdza, jak dobrym przybliżeniem \(\pi\) jest \(\dfrac{355}{113}\) oraz, że kolejne redukty są coraz lepszymi przybliżeniami liczby \(x=[a_0;a_1,a_2,\ldots]\). W pewnym sensie najlepszymi. Co dokładnie oznacza sformułowanie najlepsze przybliżenie?
Ponieważ w każdym przedziale liczbowym znajduje się nieskończenie wiele liczb wymiernych, to dla każdej liczby rzeczywistej \(\alpha\) istnieje liczba wymierna znajdująca się dowolnie blisko \(\alpha\). Jeżeli jednak ograniczymy się do ułamków zwykłych mających w mianowniku liczby \(1, 2, \ldots, q\), to wśród nich będzie ten położony najbliżej \(\alpha\). Dlatego będziemy porównywać przybliżenia wymierne liczb biorąc pod uwagę ich mianowniki. Dla prostoty zakładamy, że \(\alpha\gt 0\) oraz zawsze zakładamy, że ułamki są w postaci nieskracalnej.
Powiemy więc, że liczba wymierna \(\dfrac pq\) jest najlepszym przybliżeniem (I rodzaju) liczby \(\alpha\), o ile dla dowolnej innej liczby wymiernej \(\dfrac ab\), gdzie \(0\lt b\leqslant q\) zachodzi \[\left|\alpha-\dfrac{p}{q}\right|\lt \left|\alpha-\dfrac{a}{b}\right|\]
Jeżeli przy tych samych założeniach zastąpimy nierówność \[\left|\alpha-\dfrac{p}{q}\right|\lt \left|\alpha-\dfrac{a}{b}\right|\] przez \[|q\alpha-p|\lt |b\alpha-a|,\] to otrzymamy definicję najlepszego przybliżenia II rodzaju. Każda liczba będąca przybliżeniem II rodzaju jest również tym I rodzaju, ale nie na odwrót.
Twierdzenie
Każde najlepsze przybliżenie II rodzaju jest reduktem.
Najlepsze przybliżenia II rodzaju nazywamy po prostu najlepszym przybliżeniem. Ma ono prostą interpretację geometryczną. Liczba \(d=|q\alpha – p|\) jest równa odległości od punktu \((q,p)\) do \((q,q\alpha)\). Jeżeli narysujemy prostą \(l:y=\alpha x\), to możemy powiedzieć, że \(d\) jest odległością od punktu \((q,p)\) do prostej \(l\) w kierunku wektora \([0,1]\). Z tego wynika (choć nie jest to takie oczywiste na pierwszy rzut oka), że spośród wszystkich punktów \((b,a)\) o współrzędnych całkowitych punkt \((q,p)\) jest tym najbliższym prostej \(l\), o ile \(0\lt b\leqslant q\).
Umiejętność znajdowania dobrych przybliżeń wymiernych może mieć zastosowania praktyczne, inne od czysto rachunkowych. Przykładowo załóżmy, że mamy mechanizm wprawiany w ruch przy pomocy dwóch kół zębatych i chcemy aby stosunek czasu w jakim pierwsze koło wykona pełny obrót do czasu w jakim drugie koło wykona obrót był równy \(x\). Gdy \(x=\dfrac pq\) jest liczbą wymierną, to wystarczy aby jedno koło miało p zębów, a drugie q. Jeżeli natomiast \(\alpha\) jest liczbą niewymierną, to nie da się tego zrobić dokładnie. Musimy się posłużyć wymiernym przybliżeniem, a najlepszymi są kolejne redukty. Podobnie w przypadku wymiernym, gdy co najmniej jedna z liczb p lub q jest duża i z jakichś powodów może nie być możliwe zastosowanie koła o tak dużej liczbie zębów.
Ułamki łańcuchowe są również źródłem ciekawych i wciąż nierozwiązanych problemów matematycznych. Jednym z nich jest problem związany z tzw. stałą Chinczyna. Jeżeli \(x=[a_0;a_1,a_2,\ldots]\) jest liczbą rzeczywistą, to ciąg średnich geometrycznych \[s_n^x=\sqrt[n]{a_1\cdot a_2\cdot a_3\cdot\ldots\cdot a_n}\] jest dla prawie wszystkich liczb zbieżny do liczby \[K\approx 2,68545\ldots\] zwanej właśnie stałą Chinczyna. Do teraz (tj. sierpień 2021) nie wiadomo czy \(K\) jest liczbą wymierną czy nie.
Mimo iż wiadomo, że dla prawie wszystkich wszystkich liczb ciąg \((s_n^x)\) dąży do \(K\), to niezwykle trudno udowodnić, że jest to prawda dla konkretnej liczby. Wiadomo, że własności tej nie mają liczby wymierne, liczby niewymierne będące pierwiastkami wielomianów kwadratowych o współczynnikach całkowitych oraz także liczba \(e\). Nie wiadomo m. in. czy ciąg \((s_n^{\pi})\) dąży do \(K\). Wykres poniżej przedstawia wartości \(s_n^{\pi}\) dla \(n\in\{10,11,\ldots,500\}\).
Na koniec literatura, która była pomocna przy tworzeniu tego wpisu oraz pozycje warte uwagi dla chcących pogłębić swoją wiedzę dotyczącą ułamków łańcuchowych.
Literatura
A.J. Chinczyn, Continued Fractions, Dover Publ. Inc. (1992)
M.C. Irwin, Geometry of Continued Fractions, Amer. Math. Monthly 96 (1989), 696-703
W. Narkiewicz, Teoria Liczb, PWN (1977)
C.D. Olds, Continued Fractions, Random House Inc. (1963)
W. Sierpiński, Teoria Liczb, PWN (1959)
H.M. Stark, An Introduction to Number Theory, MIT Press (1998)