W poprzednim wpisie przedstawiłem zapis macierzowy algorytmu Euklidesa. W zapisie tym ułamek { \frac{p}{q}} reprezentowany jest przez wektor o dwóch składowych {[p,q]} zaś rozkład na ułamek łańcuchowy polega na wykonaniu opisanych w algorytmie kroków jak w równaniu poniżej:

\left| \begin{array}{c}  p \\  q \\  \end{array} \right| =  \left| \begin{array}{cc}  1 & a_0 \\  0 & 1 \\  \end{array} \right|  \left| \begin{array}{c}  r_1 \\  q \\  \end{array} \right| =  \left| \begin{array}{cc}  1 & a_0 \\  0 & 1 \\  \end{array} \right|  \left| \begin{array}{cc}  1 & 0 \\  a_1 & 1 \\  \end{array} \right|  \left| \begin{array}{c}  r_1 \\  r_2 \\  \end{array} \right|  =R^{a_0}L^{a_1} \left| \begin{array}{c}  r_1 \\  r_2 \\  \end{array} \right|

Rozkład prowadzimy tak długo aż „wektor reszt” {[r_{1},r_{2}]} będzie jednym z wektorów „bazowych” o postaci {[1,0]} lub {[0,1]}.

Opisana metoda pozwoliła nam na powiązanie algorytmu Euklidesa i drzewa Sterna-Brocota ( po szczegóły odsyłam czytelnika do wcześniejszego wpisu – oraz polecam niedawny wpis na blogu Terrence Tao – w którym przedstawiono w abstrakcyjnej profesjonalnej notacji wyniki opublikowane – chyba nawet po raz pierwszy – na stronie Bogomolnego ( można by to nazwać „nowoczesnym sformowaniem teorii ułamków łańcuchowych”).

Obecny wpis będzie innym przedstawieniem tych samych zagadnień. Wprowadzimy ważne pojęcie konwergentu oraz postaram się przedstawić inne niż to „współczesne”, moje własne (?) macierzowe przedstawienie ułamków łańcuchowych.

Kowergent ułamka łańcuchowego to ułamek będący jego przybliżeniem. Tak więc jeśli {[a_{0},a_{1}, \ldots a_{n}]} to ułamek łańcuchowy, to odpowiadający mu ciąg konwergentów ma postać: {q_{0} = a_{0} = [a_{0}]}, {q_{1} = [a_{0},a_{1}]}, {q_{2} = [a_{0},a_{1},a_{2}]} i tak dalej. Oczywiście konwergenty są liczbami wymiernymi – co więcej sa to ułamki wymierne nieskracalne. Dla skończonego ułamka łańcuchowego ostatni kowergent jest równy temu ułamkowi, zaś dla ułamków nieskończonych konwergenty dają ciąg coraz lepszych przybliżeń wymiernych wartości ułamka nieskończonego. Temat jakości tych przybliżeń jest fascynujący, odsyłam czytelnika np. do książki Chiniczyna, lub dobrego wykładu z teorii liczb – okazuje się że przybliżenie wymierne kolejnymi kowergentami jest najlepsze z możliwych w ciele liczb wymiernych. W naszych rozważaniach zagadnienie to, bardzo interesujące z praktycznego punktu widzenia, gra znikomą rolę dlatego poprzestanę na tej uwadze…

Spróbujmy nieco sformalizować zagadnienie obliczania konwergentów ułamka łańcuchowego. Zastanówmy się jak wyliczamy wartość ułamka łańcuchowego {[a_{0},a_{1}, \ldots a_{n} \ldots ]} skończonego lub nieskończonego. Oczywiście wychodzimy od definicji i wyliczamy kolejne przybliżenia. O ile dla ułamka skończonego możemy zacząć „od ostatniego elementu” i jest to z pewnością metoda najłatwiejsza rachunkowo, o tyle w wypadku ułamków nieskończonych musimy postępować inaczej. Kolejne przybliżenia, uzyskujemy obcinając ułamek {[a_{0},a_{1}, \ldots a_{n} \ldots ]} na k-tym miejscu jak nadmieniłem powyżej i wyliczając stosowny kowergent. Ułamek {[a_{0},a_{1}, \ldots a_{n} \ldots ]} przedstawiamy w postaci:

[a_0,a_1, \ldots a_n \ldots ] = [a_0,a_1, \ldots a_n, x] \approx [a_0,a_1, \ldots a_n ] =\frac{h_n}{k_n}

gdzie {x} jest „resztą” i ową resztę, jeśli szukamy przybliżenia, lub wyliczamy kolejny kowergent, pomijamy. Nadmieńmy że dla ułamków skończonych reszta ta jest liczbą wymierną, zaś dla ułamków nieskończonych – niewymierną co w oczywisty sposób wynika z definicji ułamka łańcuchowego i rozważań które można znaleźć w pierwszym wpisie tego cyklu. Jako, że po pominięciu reszty uzyskujemy skończony ułamek łańcuchowy, wynik jest zwykłym ułamkiem wymiernym co zaznaczyliśmy wypisując ostatnią równość, gdzie {h_{n}} i {k_{n}} sa liczbami całkowitymi – jest to oczywiście n-ty kowergent ułamka oznaczony wyżej symbolem {q_n}. Dla każdego {n} prawdziwa jest następująca zależność:

(1) \left[a_0; a_1, \,\dots, a_{n-1}, x \right]= \frac{x h_{n-1}+h_{n-2}}{x k_{n-1}+k_{n-2}} =\frac{h_{n}(x)}{k_{n}(x)}

Proszę zwrócić uwagę, że dla niewymiernych liczb h_{n}(x) i k_{n}(x) sa wyrażeniami niewymiernymi (a jako funkcje x są wielomianami, a właściwie funkcjami liniowymi! Co za fascynująca sytuacja – mamy tu do czynienia z homografia co pozwala nam mieć nadzieję na związek pomiędzy teorią ułamków łańcuchowych a teorią homografii czy wręcz form modularnych. Czytelnik nie będzie pewnie zaskoczony kiedy wspomnimy że taki związek istnieje).

Ostatnie równanie pozwala na skonstruowanie relacji rekurencyjnej pozwalającej na wyliczanie współczynników h_{n} i k_{n} dla zadanego ułamka łańcuchowego {[a_{0},a_{1}, \ldots a_{n},x]}:

\begin{array}{ccc}  h_{n}(x)=xh_{n-1}+h_{n-2};& h_{-2}=0 & h_{-1}=1 \\  k_{n}(x)=xk_{n-1}+k_{n-2};& k_{-2}=1 & k_{-1}=0 \\  \end{array}

Ostatnie równanie można zapisać w postaci macierzowej (dokonałem przejścia {n\rightarrow n+1} i ominąłem zaznaczenie że h i k są zależne od x):

(2) \left| \begin{array}{cc}  h_{n-1}&h_{n}\\  k_{n-1}&k_{n}\\  \end{array} \right|  \left| \begin{array}{cc}  0 & 1 \\  1 & x \\  \end{array} \right|=  \left| \begin{array}{cc}  h_{n}& h_{n}x +h_{n-1}\\  k_{n}& k_{n}x +k_{n-1}\\  \end{array} \right|

Powyższe równanie jest zapisane w dosyć niezwyczajnej formie, mamy bowiem w nim reprezentację zarówno n-tego jak i n-1-szego konwergentu – czyli mamy pewien nadmiar. Co ciekawe takie przedstawienie konwergentów można otrzymać dzięki programowi Pari/Gp gdzie bardzo podobne macierze zwraca funkcja contfracpnqn. Zapis ten kieruje nas do interesujących spostrzeżeń.

Zdefiniujmy stałe macierze T oraz S w następujący sposób:

(3) T= \left| \begin{array}{cc}  0& 1\\  1& 1\\  \end{array} \right|;  S = \left| \begin{array}{cc}  0& 1\\  1& 0\\  \end{array} \right|

Dla x ze zbioru liczb naturalnych zachodzi następująca relacja ( łatwa do sprawdzenia bezpośrednim rachunkiem):

(4) S(ST)^{x} = \left| \begin{array}{cc}  0& 1\\  1& x\\  \end{array} \right|

Wprowadźmy jeszcze jedno oznaczenie – niech M oznacza macierz konwergentów w następującej postaci:

(5) M(q_{n}) =M([a_{0};a_{1},...a_{n}]) =  \left| \begin{array}{cc}  h_{n-1}&h_{n}\\  k_{n-1}&k_{n}\\  \end{array} \right|

Stosując wprowadzone definicje macierzy S i T i M możemy rozwiązanie rekurencji z macierzami zawierającymi konwergenty zapisać w następującej postaci:

(6) \boxed{M = S S (ST)^{a_{0}} S (ST)^{a_{1}} \ldots S(ST)^{a_{n}} = S \prod_{i=0}^{N} S (ST)^{a_{i}}}

Uzyskaliśmy zapis konwergentów za pomocą raczej skomplikowanego iloczynu macierzowego.

Na koniec tego wpisu podam przykład wyliczenia macierzy M dla ułamka { \frac{43}{30}}. Zachęcam czytelnika do wykonania ten jeden raz rachunków na macierzach własnoręcznie lub przy użyciu oprogramowania jak Octave czy Sage.

1+ \frac{1}{2+\frac{1}{3+\frac{1}{4}}} = SS(ST)^1 S(ST)^2 S(ST)^3 S(ST)^4 =  \left(\begin{array}{rr}  10 & 43 \\  7 & 30  \end{array}\right)

Czytelnicy którzy znają poprzedni wpis, być może pamiętają, że przedstawiłem reprezentacją macierzową, dobrze znaną i opisaną na przykład na stronach Bogomolnego, w której użyto macierzy L i R. Ich kolejne potęgi dostarczały zapisu ścieżki od korzenia drzewa Sterna-Brocota do miejsca gdzie znajduje się obliczany ułamek. Macierze te miały prostą interpretację – „idź w lewo a_{0} razy, następnie idź w prawo a_{1} razy” i tak dalej. Proponuję aby czytelnik w tym, miejscu przerwał na chwilę lekturę i zastanowił się jak sprawy się mają w przypadku reprezentacji za pomocą macierzy S i T opisanych w tym wpisie. Jaką inną metodą można opisać jednoznacznie ruch po drzewie binarnym?
Oczywiście istnieje podobna interpretacja! Tym razem jest ona taka:„idź a_{0} razy przed siebie, zmień kierunek, idź a_{1} razy przed siebie, zmień kierunek…” Macierz która zmienia kierunek to S, zaś macierz ST to krok naprzód. Ładne – prawda?

Wydaje się że na drzewie binarnym nie ma żadnego innego sposobu określania ruchów po drzewie niż za pomocą reprezentacji LR lub S(ST). co ciekawe reprezentacji S(ST) nie widziałem dotychczas nigdzie… Oczywiście przedstawiony zapis wydaje się nieco sztuczny. Prościej byłoby iloczyn ST nazwać jakimś ładnym symbolem. Można. Ale wydaje się – że nie warto… W dalszej części postaram pokazać że macierze S, T mają ciekawe własności, oraz że związane sa z pewną ciekawą struktura algebraiczną.

Dla osób posiadających Sage – w następnym odcinku udostępnię workbook pozwalający samodzielnie sprawdzić opisane powyżej zależności i kilka innych o których wspomnimy w przyszłości… CDN…