You are currently browsing the tag archive for the ‘ułamki łańcuchowe’ tag.

Let [ a0 , a1, \ldots ,a_{k}] represent continued fraction. In previous posts I represent it by the following formula:

\displaystyle  M = S \prod_{i=0}^{k} S(ST)^{a_{i}}

where {S,T} are matrices defined as below:

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

In formulas below I will use {\textbf{I}} for {2 \times 2} unity matrix.

Formula above I will call matrix representation of continued fraction – or SST representation in short to distinguish it from usual representation by elements of {SL_{2}(Z)} group given by continued fraction tree – which I will call RL representation ( R for right, L for left. In this representation continued fraction is pointed by path – the sequence of the right-left moves on the Stern-Brocot tree). If You like to know more about SST representation You will find information in my previous posts on this blog.

For holomorphic function {f(z)} in a disk bounded by the circle {\Gamma}, it is true that for every point {a} within the disk:

\displaystyle  f(a) = \frac{1}{2\pi i} \oint_\Gamma \frac{f(z)}{z-a}\, dz

It is well known Cauchy integral representation of the holomorphic function.

Today one of articles I have read (Nick Higham „The f(A)b Problem”(2011) ), reminds me that this formula has also matrix form.

If {f(\textbf{A})} is regular enough function of the matrix, for example {exp(A)} or {A^{1/2}} there is true that:

\displaystyle  f(\textbf{A}) = \frac{1}{2\pi i} \oint_\Gamma f(z)(z\textbf{I}-\textbf{A})^{(-1)}\, dz

where {\Gamma} is integral contour on the complex plane containing every eigenvalues of {\textbf{A}} matrix inside. What is interesting this formal looking formula has very practical use, and gives numerically accurate results ( N. Hale, N. J. Higham and L. N. Trefethen
„Computing A^{\alpha}, log(A), and related matrix functions by contour integrals”
SIAM J. Numer. Anal., Vol. 46, No. 5, 2505-2523. 2008 ) in certain computations. I know matrix formula earlier, but information that it may be efficient in numerical context was new, and surprising for me.

I want to use Cauchy formula in matrix form in order to rewrite matrix continued fraction representation. It is not complicated, nor revolutionary, but is worth to mention, that because representation I use here is algebraically more „homogeneous” than well known „RL” representation by matrices from {SL_{2}(Z)}, results is nice looking, and probably may be useful.

At first we consider simple function {f(\textbf{A})} looking like one element of the product of in the SST representation ( given by the first formula in this post). I will write it in the form {f(\textbf{ST}) = (\textbf{ST})^a}. Using formula above we obtain:

\displaystyle  \textbf{S}f(\textbf{ST}) = \textbf{S}(\textbf{ST})^a = \textbf{S}\frac{1}{2\pi i} \oint_\Gamma z^{a}(z\textbf{I}-\textbf{ST})^{(-1)}\, dz \ \ \ \ \ (4)

We have to use contour of the integral above such that eigenvalues of {\textbf{ST}} matrix will be inside. So we have to compute it – it is straightforward ( I have used Sage for that, but it may be computed without any problems on the paper with a pen and a brain) that spectrum of {\textbf{ST}} consist of one degenerated eigenvalue {\lambda = 1}.

So w are ready tu use last integral to put it into SST representation matrix formula. We obtain what follows:

\textbf{M} = \textbf{S} \prod_{i=0}^{k} \textbf{S}(\textbf{ST})^{a_{i}} =

\textbf{S} \frac{1}{(2\pi i)^{k}} \oint_{\Gamma_{0}} \ldots \oint_{\Gamma_{k}} z_{0}^{a_{0}} \ldots z_{k}^{a_{k}} \prod_{i=0}^{k} \textbf{S}(z_{i}\textbf{I}-\textbf{ST})^{(-1)}\, dz_{0} \ldots dz_{k}

For me – it looks interesting:

  1. term {\textbf{S} ( z_{i} \textbf{I}-\textbf{ST})^{(-1)}} may be easily computed in closed form. I put it in Sage and obtained the following result:

    \textbf{S} ( z_{i} \textbf{I}-\textbf{ST})^{(-1)} =  \left( \begin{array}{cc} 0 & \frac{1}{z_{i} - 1} \\ \frac{1}{z_{i} - 1} & \frac{1}{(z_{i} - 1)^{2}} \\ \end{array} \right)

  2. the whole dependency on {a_{i}} coefficients now is not related to any matrix operations which means we may for example compute derivatives etc.
  3. contour \Gamma_{i} may be shaped at will with great freedom, because all integrals above has poles on eigenvalues of {\textbf{ST}} matrix, which is {\lambda = 1}. It means that we have additional freedom to use for example nice rectangle shaped contour.
  4. term {\textbf{S}(z_{i}\textbf{I}-\textbf{ST})^{(-1)}} is matrix {2 \times 2} so it may be decomposed in {I,S,T,L} base defined in earlier posts. It gives interesting possibilities. One is specially interesting – {z_{i}} here is a integration complex variable. In posts before, base {I,S,T,L} was used to construct a ring over rational numbers {Q[{I,S,T,L}]}. In that space {SL_{2}(Z)} matrices lays on quadric defined in one of the posts before. Maybe it is interesting to generalise description to complex variables, and connect it with choice of contour of integration. It may gives us a integral formula for continuants as well…

It will be worth to check if everything is ok with formulas above – analytically ( in simple cases) and especially numerically. I have further ideas so stay tuned ;-)

On the margin of continued fraction blogging I would like to present simple result as regards to continuant polynomials. Continued fraction {[a_0,a_1,...,a_n]} may be expressed as quotient of two polynomials of {(a_0,a_1,...,a_n)}, named continuant (see continuants on Wikipedia)

{[a_0,a_1,...,a_n]} = K(a_0,a_1,...,a_n)/K(a_1,...,a_n)

For example {K(a_0,a_1,a_2,a_3) = a_{0} a_{1} a_{2} a_{3} + a_{0} a_{1} + a_{0} a_{3} + a_{2} a_{3} + 1}

Continuants has many interesting recurrence relations some of which You may find in Graham, Knuth, Patashnik book „Concrete mathematics”. The most important of this recurrences is as follows:

\displaystyle  K(a_0,a_1,...,a_n,x) = xK(a_0,a_1,...,a_n)+K(a_0,a_1,...,a_n) \ \ \ \ \

During my plays with matrix representation of continued fractions I found interesting relation:

\displaystyle  K( a_0,a_1,\ldots ,a_k,a_{(k+1)},\ldots ,a_n ) = \ \ \ \ \

\displaystyle  K(a_0,a_1,\ldots ,a_k,1,1,a_{(k+1)}, \ldots ,a_n) - K(a_0,a_1,\ldots ,a_k,1,a_{(k+1)}, \ldots ,a_n) \ \ \ \ \

that is – between variables {a_k} and {a_{(k+1)}} You put two of „1″ in the first and one „1″ in the second term. You may consider this as generalisation of Fibonacci recurrence – because if You put all {a_i =1} You obtain Fibonacci numbers.

For example:

\displaystyle  K(a_0,a_1,a_2) = (a_0 a_ 1+1)a_2+a_0 \ \ \ \ \

\displaystyle  K(a_0,a_1,1,1,a_2) = (2 a_0 a_1+ a_0+2)a_2+a_0 a_1+a_0+1 \ \ \ \ \

\displaystyle  K(a_0,a_1,1,a_2) = (a_2+1)(a_0 a_1+1)+a_0 a_2 \ \ \ \ \

And it is true that:

\displaystyle  K(a_0,a_1,a_2) = K(a_0,a_1,1,1,a_2) - K(a_0,a_1,1,a_2) \ \ \ \ \

How to prove it? W have:

{ x = [a_{0},a_{1},a_{2},...a_{n}] =\frac{K(a_0,a_1,\ldots ,a_n)}{K(a_1,\ldots ,a_n)}= - \frac{1}{2} \frac{Tr \left( M(S- L) \right) }{Tr \left( M(S-T) \right) }}

where {tr} is trace of a matrix, and maybe You know that I define M as follows (see here ):

\displaystyle  M = S \prod_{i=0}^{n} S(ST)^{a_{i}} \ \ \ \ \

So we have the following formulas true:

\displaystyle  K(a_{0},a_{1},a_{2} \ldots a_{n}) =\frac{1}{2} Tr \left( M(S- L) \right) \ \ \ \ \

\displaystyle  K(a_{1},a_{2} \ldots a_{n}) = - Tr \left( M(S-T) \right) \ \ \ \ \

Please note that upper formula has different arguments than the lower so they agree.

And there is true that {S^2 =I} and {T^2 = I+T} which we may use to produce „unity decomposition” as below:

\displaystyle  I = T^2 -T = S(ST)S(ST) - S(ST) \ \ \ \ \

Then You may insert it in any place between {S(ST)^{a_{i}}S(ST)^{a_{i+1}}} which gives expression above and many more if You consider {T^p} for {p \in Z} etc.

Remark 1: proved here formula should be possible also to prove from recursion relation directly – so if You would like to try this way – please let me know.

Remark 2: I post this on mathoverflow, and someone provide the sketch of proof by induction – but it seems to be only a sketch – and rather incomplete.

W 1855 zmarł Carl Friedrich Gauss. Trzy lata później w roku 1858 Moritz Abraham Stern został mianowany Ordinarius Na Uniwersytecie w Getyndze, zajmując tym samym katedrę Gaussa. Stern był pierwszym pełno-miarowym profesorem matematyki żydowskiego pochodzenia w Niemczech. W roku w którym obejmował stanowisko Gaussa Stern opisał ciekawą konstrukcję na liczbach wymiernych. Był to rodzaj listy ułamków ułożonych w pewnym porządku, tak, że dało się je narysować w postaci drzewa binarnego. Każdy wierzchołek w drzewie – rodzic, miał dwie wychodzące z niego gałęzie – dzieci. Związek pomiędzy wartościami rodziców i dzieci byl prosty ale intrygujący – napiszemy o tym niżej. Stern opisał ciekawe własności tej konstrukcji – jako zawodowy matematyk zajmował się teorią liczb zaś konstrukcja przypominała i uogólniała opisane wcześniej w 1818 roku ciągi Fareya – co zapewne było samo w sobie interesujące. Zupełnie niezależnie konstrukcję tą, z powodów praktycznych, w kilka lat później powtórzył francuski zegarmistrz Achille Brocot -było to w 1861 roku. Konstrukcja ta przeszła do historii pod nazwą drzewa Sterna-Brocota. Co takiego praktycznego zainteresowało Achille Brocota – zegarmistrza, którego ojciec także był zegarmistrzem – w uporządkowaniu ułamków w drzewo?
Problemem blisko związanym z zegarmistrzostwem jest konstrukcja przekładni zębatych. Mechanizm zegarowy musi transmitować napęd dając precyzyjną i z góry zadaną liczbę obrotów – często kilka zadanych liczb obrotów. Na przykład wskazówka godzinowa musi obracać się 2 razy podczas gdy minutowa 1440 razy na dobę. Ponieważ obie napędzane są z jednej sprężyny – trzeba skonstruować przekładnię zębatą która zapewni stosowne przełożenia – 1/720. W dawnych czasach koła zębate wykonywano ręcznie – precyzyjne wykonanie koła o dużej liczbie zębów jest nie lada wyzwaniem i bardzo czasochłonną pracą. Luksusowe produkty zegarowe – nie tylko zegary liczące czas, ale i inne służące rozrywce, wskazujące fazy księżyca i może datę Wielkanocy, różne pozytywki wymagały sporej wiedzy już na etapie projektu – należało wyliczać ilości zębów w kołach by uzyskać właściwe stosunki. Jeśli chcemy wykonać przekładnię realizującą stosunek 34/55 możemy dokonać rozkładu licznika i mianownika: 17/5* 2/11 i uzyskać szukane przełożeni używając 4-rech kół zębatych – łącząc dwie przekładnie o stosunkach jak tym iloczynie. Metoda zdaje się działać, przynajmniej dla prostych stosunków. Znanym problemem zegarmistrzowskim było zadanie postawione przez Charlesa E. Camus – chodziło o projekt zegara realizującego stosunek 720 / 525,949 . Problem z tym ułamkiem jest taki, że mianownik jest liczbą pierwszą, a więc nie damy rady go rozłożyć na czynniki. Tym samym, nawet starając się wykonać przekładnie złożoną z wielu kół nie unikniemy wykonania koła o olbrzymiej ilości zębów! Powinniśmy się zatem raczej odwołać do przybliżeń. Jak znaleźć najlepsze – takie w którym ułamki mają możliwie najmniejszą liczbę zębów ale ich stosunki dobrze przybliżają poszukiwaną wartość? Odpowiedź na to pytanie była wynikiem pracy Brocota, jego metodę można znaleźć tu: http://www.ams.org/samplings/feature-column/fcarc-stern-brocot dodajmy jedynie, że

720 / 525,949 ~ 196 / 143,175 = 2/3 * 2/25 * 7/23 * 7/83

było jednym z możliwych rozwiązań. Drzewo Sterna Brocota umożliwia systematyczne wyliczanie takich przybliżeń, co więcej gwarantuje optymalność – mogę przypuszczać, że jego implementacja to także współczesne narzędzie służące do projektowania przekładni zębatych – ciekawe lu ludzi zdaje sobie współcześnie z tego sprawę ( czy jest inżynier na sali? czy wspomniano o tym?)…

Przejdźmy zatem do opisu konstrukcji Sterna-Brocota. Klasyczna szkolna konstrukcja drzewa zakłada użycie tzw. mediantów. Dla danych ułamków A = a/b i B=c/d ich mediantem nazywamy ułamek M = (a+c)/(b+d) co przypomina nieco sposób dodawania ułamków jaki błędnie wypracowują sobie dzieci. Drzewo Sterna-Brocota to drzewo ułamków, a więc liczb wymiernych. Każda liczba wymierna daje się przedstawić jako iloraz liczb naturalnych p/q gdzie q=/= 0. Jednak drzewo o którym mówimy jest konstruowane wychodząc od dwu stosunków w postaci 0/1 i 1/0 z których jeden jak widać nie jest ułamkiem. Może dać to pretekst do rozważań na temat roli punktu w nieskończoności w tej konstrukcji i a z estetycznego punktu widzenia nieco psuje konstrukcję klasyczną. Wydaje się jednak że jest ona nadal prostsza pojęciowo, zwłaszcza gdy mowa o praktycznych zastosowaniach. Poniżej wprowadzimy znacznie ładniejszą w mojej ocenie konstrukcje algebraiczną. Ale nie uprzedzajmy faktów.

Z każdego wierzchołka drzewa spuśćmy w dól linię. Drzewo SB wisi rozpięte między dwoma stosunkami 0/1 i 1/0 i linie spuszczone z tych elementów są granicami drzewa. Każdy element drzewa leży pomiędzy dwoma liniami – i jest mediantem stosunków od których te linie wychodzą. Tak więc pierwsze dwa elementy ( które nie są uważane za części drzewa i stanowią tylko jego „techniczne zawieszenie” ) to 0/1 i 1/0. Następny -pojedynczy element – to ich mediant czyli:

(-1 – zawieszenie) – 0/1 1/0

(0-wiersz ) (0+1)/(1+0) = 1/1 = 1

Liczba 1 jest wierzchołkiem drzewa – spuszczamy z niej linię w dól – wraz z granicami – liniami opuszczonymi z 0/1 i 1/0 mamy podział „przestrzeni drzewa” dwa sektory. Po lewej stronie mamy linię wychodzącą z 0/1, po środku 1/1 a po prawej 1/0. Wyliczając medianty dostajemy kolejny rząd elementów drzewa:

(1-wiersz) (0+1)/(1+1) = 1/2 ; (1+1)/(1+0) = 2

Spuścimy kolejne linie, wyliczymy kolejne medianty:

(2-wiersz) (0+1)/(1+2) = 1/3 ; (1+1)/(2+1) = 2/3 ; (1+2)/(1+1) = 3/2 ; (2+1)/(1+0) = 3

Myślę, że konstrukcja za pomocą mediantów stanie się jaśniejsza jeśli spojrzy się na rysunek ( z wikipedii):

Drzewo Sterna-Brockot

Powstaje w ten sposób drzewo SB o bardzo ciekawych własnościach. Po pierwsze ułamki sa w nim ułożone według pewnego porządku – ułamki o mniejszych liczbach w mianowniku są wyżej niż ułamki o większych mianownikach – drzewo jest wyposażone w porządek pionowy.. Po drugie wszystkie ułamki są nieskracalne. Trzecią ciekawą własnością jest to, że w drzewie SB każda liczba występuje w unikalny sposób – tylko raz. Czwarta własność -każda liczba ma tu swoją reprezentację. Drzewo SB jest więc to tablica wszystkich liczb wymiernych w określonym porządku.

Dokładniejsza analiza pokazuje dalsze własności: na lewo są zawsze liczby mniejsze a na prawo większe – mamy zatem porządek w wierszach a więc poziomy. Przyglądając się obrazkowi z wikipedii przedstawiającemu drzewo SB można zauważyć kolejną ciekawa własność. Przepiszmy liczniki ułamków z 3-ciego rzędu drzewa wypisanego wyżej – od lewej – dostaniemy wówczas ciąg 1,2,3,3. Przepiszmy teraz ciąg mianowników od lewej 3,3,2,1 (gdzie uznaliśmy że 3=3/1) Widzimy że jest to ten sam ciąg ale w odwrotnym kierunku! nie jest to przypadek – jest to cecha która występuje w każdym wierszu drzewa SB. Przypuszczam, że podobnego rodzaju własności można wskazać cale mnóstwo, dla nas jednak następuje tu czas aby odnieść drzewo SB do ułamków łańcuchowych.

Popatrzmy na ułamki znajdujące się w n-tym rzędzie drzewa. Przedstawię tutaj ciekawe podejście opisane przez Alexandra Bogomolny na jego fantastycznej stronie Cut-The-Knot ( sekcja o ułamkach łańcuchowych zaczyna się tu: http://www.cut-the-knot.org/blue/Euclid.shtml i przynależy do artykułów o algorytmie Euklidesa – polecam!).

Po pierwsze, skoro każdy rodzić ma tu dwoje potomków, zachowując notację w której wierzchołek drzewa, zawierający tylko jeden wyraz równy 1, ma numer 0, otrzymamy wniosek (ogólnie prawdziwy dla wszystkich drzew binarnych):

( T3 ) Jeśli piętra drzewa Sterna-Brockota liczymy od zera to na n-tym poziomie drzewa mamy 2^n liczb.

Warto zauważyć, że drzewo dzieli się na dwie gałęzie, prawa i lewą, oraz, że wyrazy po lewej są odwrotnościami tych po prawej stronie – gałęzie sa swoim lustrzanym odbiciem z inwersją. Biorąc pod uwagę opisany w poprzednim eseju fakt, iż dla ułamków łańcuchowych zachodzi zależność (wzór (10) w poprzednim wpisie) :

[a_0,a_1,...] = \frac{1}{[0,a_0,a_1,...]}

należy się spodziewać że i w drzewie SB znajdzie ona swoje wykorzystanie – np. możemy ograniczyć się do analizy połowy drzewa – druga połowa to lustrzane odbicie.

Zajmijmy się teraz bezpośrednim wyliczeniem ułamków łańcuchowych i ich związkiem z przedstawionym drzewem. Rozpoczniemy niewinnie od ponownego napisania wzoru na pierwszy krok w rozkładzie ułamka p/q na ułamki łańcuchowe:

(12) \frac{p}{q} = a_0 + \frac{r_1}{q}

Idąc za pomysłem przedstawionym na stronach Bogomolnego wprowadzimy tu nieco algebry linowej. Pomysł jest taki: niech ułamek p/q będzie reprezentowany przez wektor [p,q] i niech będzie to kolumna. Spróbujmy równanie (12) przedstawić za pomocą takich wektorów, w postaci macierzowej:

(13) \left| \begin{array}{c}  p \\  q \\  \end{array} \right| =    \left| \begin{array}{c}  a_0q + r_1 \\  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|

Jak na razie – fajnie. Co dalej. W następnym kroku rozkładu na ułamki powinniśmy wziąć odwrotność r_1/q czyli q/r_1 i powtórzyć nasze rachunki:

(14) \frac{q}{r_1} = a_1 + \frac{r_2}{r_1}

Szczęśliwie w języku macierzy nie musimy martwić się o odwrotność, po prostu zapiszemy nasze równanie za pomocą odpowiednio dobranych macierzy:

(15) \left| \begin{array}{c}  r_1 \\  q \\  \end{array} \right| =    \left| \begin{array}{c}  r_1 \\  a_1r_1 + r_2 \\  \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|

Sprytnie, prawda? Następnych kroków łatwo się domyśleć: za każdym razem dokonujemy rozkładu tej ze współrzędnych wektora która jest większa ( za pierwszym razem było to p, za drugim q). Konstrukcja – nasz algorytm – sprawia, że raz jest to współrzędna górna a raz dolna. Jak widać pojawiają się tu ciekawe macierze w postaci:

(16) \left| \begin{array}{cc}  1 & 0 \\  s & 1 \\  \end{array} \right| =    \left| \begin{array}{cc}  1 & 0 \\  1 & 1 \\  \end{array} \right|^s = L^s

oraz:

(17) \left| \begin{array}{cc}  1 & t \\  0 & 1 \\  \end{array} \right| =    \left| \begin{array}{cc}  1 & 1 \\  0 & 1 \\  \end{array} \right|^t = R^t

Zdefiniowaliśmy tym samym operatory macierzowe L i R. Zauważmy, że możemy (dzięki trickowi który pozwolił nam nie dokonywać operacji odwrotności) zestawić równania (13) i (15) w jedno:

(18) \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|

jesteśmy już bardzo niedalecy od drzewa Sterna-Brocota. W poprzednim odcinku uzasadniliśmy, że rozkład jak powyżej musi się zakończyć na pewnym, skończonym etapie dla liczb wymiernych. nastąpi to oczywiście gr\dy jedna ze współrzędnych wektora [r_i,r_{i+1}] będzie zerowa. Uważny i podejrzliwy czytelnik z pewnością zechce rozpoznać w literach L i R angielskie skróty od słów Right i Left i będzie miał słuszność!

Dla otarcia się o prawdziwe obliczenia, podajmy tutaj jakiś konkretny przykład – a jego waga nie sprowadza się jedynie do rachunków. Wskaże on nam pewną cechę, która z jednej strony może być nieco rozczarowująca, ale z drugiej jest nieunikniona. nie uprzedzajmy faktów. Oto przykład:

(19) \left| \begin{array}{c}  4 \\  7 \\  \end{array} \right| =    R^0 \left| \begin{array}{c}  4 \\  7 \\  \end{array} \right| =    R^0L^1\left| \begin{array}{c}  4 \\  3 \\  \end{array} \right| =    R^0L^1R^1 \left| \begin{array}{c}  1 \\  3 \\  \end{array} \right| =  R^0L^1R^1L^3 \left| \begin{array}{c}  1 \\  0 \\  \end{array} \right| =  R^0L^1R^1L^2 L \left| \begin{array}{c}  1 \\  0 \\  \end{array} \right|

Po pierwsze zwróćmy uwagę, że otrzymaliśmy prawidłowy rozkład ułamka 4/7 = [0,1,1,3] co zresztą można odczytać z przedostatniej równości. Proszę teraz sprawdzić, gdzie mieści się 4/7 na drzewie Sterna-Brocota – stosownie duże drzewo jest tu: http://www.cut-the-knot.org/blue/stern.gif

Jak widać, chcąc dotrzeć do liczby 4/7 z wierzchołka reprezentowanego tu przez 1/1 należy wybrać się w Lewo, potem w Prawo, a potem 2-razy w Lewo – daje to zygzak postaci LRLL . A mogło być tak ładnie! Niestety w naszym rozkładzie na ostatnim miejscu jest liczba 3 a nie 2.

Okazuje się, ze na ostatnim miejscu ułamka łańcuchowego zawsze pojawia się cyfra o 1 większa niż stosowny zapis „zygzaka” od liczby 1/1 do liczby która przechodząc zygzak osiągamy. Taka własność drzewa – ot co.

Aby jednak całość rozjaśnić, to jest zagmatwać, zapisałem jeszcze jedną równość w równaniu (19). Teraz mamy poprawną ścieżkę, oraz jeden dodatkowy krok w lewo jeśli startujemy od „absolutnego zakotwiczenia drzewa” w postaci „ułamka „1/0″. Popatrzmy może na inny przykład:

(20) \left| \begin{array}{c}  2 \\  3 \\  \end{array} \right| =    R^0 \left| \begin{array}{c}  2 \\  3 \\  \end{array} \right| =    R^0L^1\left| \begin{array}{c}  2 \\  1 \\  \end{array} \right| =    R^0L^1R^2 \left| \begin{array}{c}  0 \\  1 \\  \end{array} \right| =    R^0L^1R^1 R \left| \begin{array}{c}  0 \\  1 \\  \end{array} \right|

I rzeczywiście, co nie powinno dziwić 2/3 = [0,1,2] ale tym razem mamy dodatkowy ruch w zygzaku ( dla 2/3 zygzak ma kształt LR) tym razem w prawo ale od 0/1. Najwyraźniej jakaś siła nie chce nam pozwolić operować na „gołych okropieństwach w postaci 1/0 i 0/1″ i wstawia stosowne R lub L w ostatnie miejsce – łamiąc miłą dla oka symetrię i cenzorując horrendum wyrażeń postaci 1/0.. Co ciekawe i oczywiste R[0,1] =L[1,0] = [1,1] = 1… Rozkład jest poprawny – a nieoczekiwane pojawienie się liczby o jeden większej nie jest przypadkiem – można się tu dopatrywać jakiejś ingerencji wielkiego cenzora, albo metafizyki, a może po prostu rzeczy są nieco złośliwe. Drzewo pamięta jak jest zawieszone ale uwzględnia to w niemiłym dla nas miejscu. Ot, taka własność.

Czas na podsumowanie naszych wyprowadzeń. Niech ciąg liter R i L reprezentuje pewną ścieżkę w drzewie SB – L oznacza wybór lewej gałęzi, R prawej oraz jeśli w takim ciągu występuje po sobie kilka jednakowych liter, np. p liter R to taki fragment ciągu zapisujemy jako R^p ( podobnie dla liter L następujących po sobie). Rozpatrujemy tylko ciągi zaczynające się od litery R , z tym że dopuszczamy możliwość że występuje ona „0″ razy. Niech CF oznacza funkcję która dla zadanego ciągu R i L zwraca ułamek łańcuchowy leżący w stosownym miejscu drzewa Sterna-Brocota. Możemy zapisać wzór na CF:

( 21 ) CF(R^{a_0} X_1^{a_1}X_2^{a_2}... X_k^{a_k}) = [a_0;a_1,a_2,...,a_k+1]

gdzie X^{a_p} oznacza R lub L a_p razy po sobie, zaś a_0 może być równe 0 lub nie. Czytelnik podobne wyprowadzenie może znaleźć u Bogomolnego, tam jednak użyte sa mnożenia macierzowe od lewej strony i wektory jako wiersze. Proszę pamiętać o tej różnicy w notacji porównując rachunki. Należy dla porządku także nadmienić, ze zapis procedury rozkładu ułamków łańcuchowych w postaci macierzy jest pochodną macierzowej postaci algorytmu Euklidesa – czy uczą tego na informatyce? Jak ktoś dociekliwy – proszę samemu spróbować zapisać algorytm na gcd(a,b) w postaci macierzowej – podobnie jak powyżej.

Skoro w ciągu liter RLRRLL…. zawarta jest informacja o miejscu ułamka łańcuchowego w drzewie SB, a zarazem o jego czynnikach, uzyskujemy w naturalny sposób ciekawy wniosek. Aby dojść do dowolnej liczby w 3-cim rzędzie musimy wykonać 3 ruchy licząc od 0 (powiedzmy RLL dla liczby 4/3 = CF(RLL) = [1,3] ) . Stosownie w n-tym rzędzie znajdują się liczby reprezentowane przez ciągi n-literowe. Prawdziwe jest zatem następujące twierdzenie:

( T4 ) Niech [a_0,a_1,...a_k] ułamkiem łańcuchowym pojawiającym się w n-tym rzędzie drzewa Sterna-Brocota. Wówczas:

\sum^{k}_{i=0} a_i = n + 1

Rozkład liczby na sumę czynników, kiedy bierzemy pod uwagę kolejność składników nosi nazwę kompozycji Twierdzenie T4 można zatem wypowiedzieć inaczej:

Na n-tym piętrze drzewa SB mamy wszystkie takie ułamki łańcuchowe że ich czynniki są kompozycjami liczby n przy czym należy pamiętać, że dopuszczamy możliwość iż zero może występować tylko na pierwszym miejscu.

Jako proste ćwiczenie kombinatoryczne proponuję dowieść że wynik ten jest zgodny z T3 w którym napisaliśmy, ze na n-tym wierszu drzewa Sb jest 2^n liczb ( zakładając, że wiersze liczymy od zera). Podpowiem że wystarczy zmodyfikować rozumowanie opisane w artykule o kompozycjach z wikipedii aby uwzględnić występowanie liczby 0 oraz fakt, że dla ułamków łańcuchowych zachodzi zależność [a_0,a_1...,a_k,1] = [a_0,a_1,...,a_k +1] ( należy konsekwentnie wybrać tylko jedną reprezentację ułamków, np. zawierająca zawsze 1-dynkę na końcu).

Uznałem że w tym miejscu zrobimy przerwę. Miałem napisać o funkcji ?(x) ale to chyba byłoby za wiele na raz. Jak zwykle proszę o uwagi i ewentualne poprawki co do rachunków.

W kolejnych odcinkach jeśli autor poradzi sobie z rachunkami (co mu na razie nie idzie) powiemy coś o pasjonującej funkcji ?(x) Minkowskiego oraz o drzewie Calkina–Wilfa – co będzie niejako rozważaniami na boku tego co chciałbym opisać, ale pozwoli zadać ciekawe, w opinii autora, 2 pytania. Głównym celem cyklu jest jednak przedstawienie nieco innego podejścia do tego co opisano tutaj, w tym wpisie. I temu poświęcę następny wpis.

    

    Chciałbym napisać tu coś o ułamkach łańcuchowych. Wpis ten ukazał się wczesnej na Google Buzz. Jak widać z fragmentów dyskusji przytoczonych poniżej nie jestem zbyt kompetentną osobą by pisać na ten temat, jednak mimo to napiszę, bez wielkich zmian. Być może w przyszłości, za słuszną sugestią profesora Włodzimierza Holsztyńskiego, zdobędę się na poprawienie swoich potknięć, rewizję poglądów, i uzupełnienie wpisu. Byłoby to ze wszech miar wskazane, jako, że Włodzimierz ma zdecydowanie rację tam gdzie podkreśla że nie posiadam dostatecznej wiedzy i praktyki co do ferowania ogólnych ocen na temat matematyki i matematyków. Z drugiej strony w pewnych kwestiach, jak by to śmieszne się miało nie wydawać, mam własne zdanie na przedstawianą treść. Tak więc by rzecz dobrze wyjaśnić, a czytelnika nie znudzić, chciałbym wyrazić tu pewną prośbę: czytajcie to co poniżej z dystansem, i darujcie mi niekompetencję. Jestem człowiekiem niecierpliwym, a bardzo chcę pokazać coś więcej niż to co mieści się w typowym traktowaniu poniższej tematyki. by jednak było to możliwe, konieczne jest danie kontekstu. Pokazanie pewnego wprowadzenia by rozmowa nie sprowadzała się do napisania kilku wzorów których nikt nie zrozumie. Namawiam zatem do przeczytania, przemyślenia, skomentowania, ale i do poczekania aż uda mi się dojść do bardziej intrygujących, na amatorski sposób, ciekawych, tematów….

    Ułamki łańcuchowe to ciekawa i niezbyt pamiętana współcześnie konstrukcja. Gdyby spytać o nie ucznia szkoły średniej to pewnie jedynie pasjonaci matematyki znaleźliby jakieś wiadomości o tego typu obiektach, na ogół nie potrafiliby jednak podać pewnie żadnych faktów poza definicją. Przypuszczam, ze nawet studenci matematyki nie posiadają jakiejś szczególnej wiedzy na temat ułamków łańcuchowych gdyż nie są one związane w sposób szczególny z żadnym działem współcześnie wykładanej matematyki uniwersyteckiej. Oczywiście znajomość definicji i podstawowych własności jest elementem ogólnej kultury matematycznej, jednak chyba ułamki łańcuchowe są współczesne raczej kuriozum niż szczególnie ważną konstrukcją w matematyce. Współczesna matematyka zdaje się umieszcza je w obrębie tak zwanej matematyki konkretnej, lezą na pograniczu matematyki stosowanej, informatyki i technik numerycznych.

    Warto wiedzieć, że jeszcze kilkadziesiąt lat temu, i na przełomie stuleci XIX i XX, a zwłaszcza w czasach jeszcze wcześniejszych, ułamki łańcuchowe były ważną konstrukcją matematyczną. Ich analiza zaprzątywała umysły tego formatu co Euler który dowiódł za ich pomocą niewymierności liczby e. Lambert używając ułamków łańcuchowych dowiódł niewymierności liczby pi. Uczeni tej miary co Lagrange, Gauss który wprowadził ułamki łańcuchowe zespolone, oraz wyrażał ich wartości a pomocą funkcji hipergeometrycznych prowadzili aktywne badania na ich polu. ważne konstrukcję wprowadził Pade – twórca tzw. aproksymant Pade, ciekawe i charakterystyczne dla niego są wyniki Ramanujana. Wreszcie Chiniczyn – autor monografii na ich temat. Wówczas było to pole ciekawych badań. Ułamki łańcuchowe mają bliski związek z aproksymacją diofantyczną czyli przybliżaniem liczb rzeczywistych niewymiernych liczbami wymiernymi z dobra, najchętniej optymalną dokładnością. Badania związane z ułamkami łańcuchowymi doprowadziły Chniniczyna do odkrycia tak zwanej Stałej Chiniczyna, która w wikipedii wymieniana jest jako jedna z 10 najważniejszych stałych matematycznych obok liczby pi i liczby e.

    Zajmijmy się na początek podstawowymi definicjami. Przez ułamek łańcuchowy, zapisywany jako [a_{1};a_{1},a_{2},a_{3} \ldots a_{k}] będziemy rozumieli liczbę postaci:

[ a_0;a_1,a_2,a_3...a_k ] = a_0 + \frac{1}{ a_1 + \frac{1}{ a_2 + \ldots \frac{1}{ a_k}}}

gdzie liczba a_0 jest liczbą całkowitą ( a więc może być ujemna, zero lub dodatnia) zaś a_{i} są liczbami naturalnymi. Jest to tak zwany ułamek łańcuchowy w postaci kanonicznej lub regularnej lub prostej . Jest to postać wyróżniona – w takim piętrowym ułamku, wszystkie liczniki zawierają wyłącznie cyfrę 1. Oczywiście w sensie ogólnym tak być nie musi – mamy wówczas do czynienia z ułamkiem niekanonicznym lub złożonym. Teoria ułamków niekanonicznych jest co najmniej tak samo, jeśli nie bardziej ciekawa jak ułamków kanonicznych. Jednak w naszych rozważaniach nie będziemy o nich wspominać.

    Skoro mamy definicję, spróbujmy zapisać w tej postaci jakąś liczbę. wiele przykładów jest bardzo prostych, inne wymagają pewnego nakładu pracy:

\frac{3}{2} = [1;2] = 1 + \frac{1}{2}

3 10/71 = [4;2,1,2,1,2,2] = 4 + \frac{1}{2 + \frac{1}{1+\frac{1}{2+\ldots }}}

    Jak szybko wyliczać ułamki łańcuchowe znając daną liczbę?

    Najszybsze jest użycie programu komputerowego. Wiele dostępnych pakietów bardzo sprawnie wylicza rozkład zadanej liczby na ułamki łańcuchowe, polecam jednak dwa z nich: Sage  które jest wspaniałym narzędziem do zabawy matematyka, jednak jego pobranie to około 400 Mb a instalacja zajmuje około 4 Gb! Monstrum. Dla poszukujących czegoś lżejszego – polecam Pari/GP. Wspaniałe narządzie dla wszystkich zabawiających się teorią liczb, kiedy żona i dzieci śpią. A przy tym nadal jedno z najbardziej wydajnych, wśród darmowych programów – z pewnością rekordzista szybkości.

   Uruchamiamy więc Pari/GP i piszemy: contfrac(52163/16604) i naciskamy enter. Magia! Wynik to: %11 = [3, 7, 15, 1, 146] . Jak oni to zrobili?

    Kiedy mamy zadaną liczbę powiedzmy A, to aby przedstawić ją w postaci ułamka łańcuchowego musimy ją zapisać jako:

A = a_0 + 1/x_0

    Och to proste: a_0 to po prostu część całkowita z liczby A! x_0 też znajdziemy w prosty sposób – x_0   jest odwrotnością części ułamkowej liczby A. A dalej? Dalej to samo! Liczbę x_0 przedstawimy w postaci:

x_0= a_1 +1/x_1

    A z x_1 zrobimy to samo i tak dalej, aż cały proces na którymś kroku się zatrzyma – nie będzie już części ułamkowej. Po wstawieniu wszystkich pośrednich rachunków do jednego wzoru dostaniemy formułę z definicji (1). Pojawia się więc ważne pytanie: Dla jakich liczb ten proces ma szansę się zatrzymać?

    Po pierwsze zauważmy, że jeśli mamy ułamek łańcuchowy [a_0;a_1,a_2,a_3...a_k] to w wyniku wyliczenia jego wartości z definicji (1) otrzymamy liczbę wymierną ( jako stosowny wynik operacji dodawania i dzielenia na liczbach wymiernych, a te są przecież ciałem – a więc te operacje nie wyprowadza nas poza zbiór liczb wymiernych). Możemy wypowiedzieć zatem wniosek:

( T1 ) Skończony ułamek łańcuchowy to pewna liczba wymierna.

    Czy każda liczba wymierna ma zatem postać skończonego ułamka łańcuchowego? Rozważmy liczbę wymierną p/q . Nie ma dla nas znaczenia czy jest to ułamek właściwy czy nie, ważne wszakże, że q \neq 0 . Postępując zgodnie z pomysłem na rozkład na ułamki łańcuchowe opisany wyżej możemy zapisać:

\frac{p}{q} = a_0 + \frac{r_0}{q} = a_1 + \frac{1}{\frac{q}{r_0}} = a_0 + \frac{1}{x_0}

    po pierwsze zauważmy, że

r_0 < q

    gdyż a_0 jest częścią całkowita jaką da się tu wyciągnąć, więc r_0/q jest ułamkiem właściwym. Jeśli mamy r_0 = 0 cały proces się kończy i mamy ułamek łańcuchowy w skończonej postaci. Załóżmy że tak nie jest. Co dalej? Wówczas musi być r_0/q <1 a więc q/r_0 >1 Wykonajmy następny krok rozkładu:

x_0 = \frac{q}{r_0} = a_1 + \frac{r_1}{r_0} = a_1 + \frac{1}{\frac{r_0}{r_1}} = a_1 + \frac{1}{x_1}

    I tu ważne spostrzeżenie:

r_1 < r_0

    z tych samych powodów jak wyżej w równaniu (7). Widzimy zatem, że w procesie iteracji uzyskujemy ciąg czynników r_0 > r_1 > ...> r_k > \ldots które są malejące! W wyniku takiego procesu musimy osiągnąć 0, co zakończy działanie całego algorytmu, bo liczby r_i sa liczbami naturalnymi. Dowiedliśmy zatem następującego stwierdzenia;

( T2 ) Każda liczba wymierna może zostać przedstawiona jako skończony ułamek łańcuchowy prosty.

    Analizując rzecz nieco bardziej szczegółowo można spostrzec, że przedstawiony powyżej algorytm jest bardzo podobny do algorytmu Euklidesa znajdowania największego wspólnego podzielnika dwu liczb. To prawda! Algorytm Euklidesa jako wynik uboczny daje także informacje o rozkładzie liczby na ułamek łańcuchowy. Jednak samo dokonanie rozkładu na ułamki łańcuchowe, przedstawione powyżej, wydaje się być nieco prostsze i łatwiejsze.

    A co z liczbami niewymiernymi? Otóż liczby niewymierne nie mają skończonego rozkładu na ułamki łańcuchowe. W zasadzie nie powinno to dziwić, nie tylko dlatego że przyzwyczailiśmy się do ich „patologii” czy wyjątkowości ( co przecież jest ledwie opinią bardziej estetyczną niż obiektywną). Każda liczba niewymierna może być przybliżana przez liczby wymierne. Lepsze przybliżenia- to na ogół bardziej skomplikowane ułamki – o większych liczbach w liczniku i mianowniku – a zatem dłuższe rozwinięcia w ułamki łańcuchowe… Najbardziej znanym przykładem może być tu liczba pi. Popatrzmy na je kolejne przybliżenia i ich rozkłady na ułamki łańcuchowe (przybliżenia za wikipedią, rozkłady za pomocą PARI/GP):

\pi \approx 3, \frac{22}{7}, \frac{333}{106}, \frac{355}{113}, \frac{52163}{16604}, \ldots

3 = [3]
22/7 = [3,7]
333/106 = [3,7,15]
355/113 = [3,7,16]
52163/16604 = [3,7,15,1,146]

    I tak dalej. Początek dokładnego liczby pi na ułamki łańcuchowe wygląda zaś tak (http://oeis.org/A001203 ):

\pi = [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, ... ]

    Warto zwrócić uwagę, ze znana liczba 22/7 to wynik znany już Archimedesowi, oraz, że szczególnie dobre aproksymacje wymierne to te, które urywają się tam gdzie w ułamku łańcuchowym występuje duży czynnik. W takim wypadku następna poprawka a_j jest bowiem szczególnie mała…

    W ten oto sposób doszliśmy do ważnego zastosowania ułamków łańcuchowych: aproksymacji liczb niewymiernych. Jeśli ułamek łańcuchowy dla pewnej liczby niewymiernej, podobnie jak dla liczby pi, ma jakiś duży czynnik na j-tym miejscu, wówczas jego obcięcie na j-tym miejscu, nazywane j-tym konwergentem lub po polsku j-tym reduktem liczby, daje szczególnie dobre przybliżenie owej liczby. Na przykład 333/106 = [3,7,15] = 3.141509434 to drugi redukt liczby pi, i jak widać daje dobrą dokładność do 4-tego miejsca po przecinku.

    Czy każdy ułamek łańcuchowy, skończony lub nieskończony [a_0;a_1,a_2,a_3...a_k, \ldots ] dla całkowitego a_0 i dowolnych naturalnych a_i różnych od zera reprezentuje jakąś liczbę? Okazuje się, i jest to bardzo ważny fakt – że tak! Co więcej można by nawet nieco zliberalizować założenia i dopuścić by liczby ia_i były całkowite ( różne od zera) byle szereg będący ich sumą był rozbieżny. Przy takich założeniach ułamek łańcuchowy jest zbieżny do jakiejś liczby. Co istotne, jeśli jest nieskończony – liczba ta jest niewymierna, a jeśli skończony – wymierna – co dowiedliśmy powyżej ( liczby rzeczywiste są albo wymierne albo nie, jest to podział dychotomiczny i nie ma innych rodzajów liczb).

    Zauważmy, ze jeśli mamy niezerową liczbę A, to jej odwrotność 1/A w zasadzie przypomina fragment zależności (4) jeśli założymy, że a_0 = 0 . I rzeczywiście, prawdziwa jest zależność:

[a_0,a_1,...] = \frac{1}{[0,a_0,a_1,...]}

    Na koniec tego popularnego wprowadzenia uwaga o równaniach kwadratowych. Przypatrzmy się równaniu postaci:

x^2 -x -1 =0

jak wiadomo rozwiązaniem tego równania jest liczba \varphi stosunek złotego podziału. Jako ludzie leniwi, zamiast rozwiązywać równanie przepiszemy je w postaci:

x= 1 + \frac{1}{x}

a następnie za x podstawimy … wyliczony x:

x= 1 + \frac{1}{ 1 + \frac{1}{x} }

    Ponieważ proces ten możemy kontynuować w nieskończoność, aż x „zniknie” po lewej stronie równości ( a przynajmniej będzie już tak małe że go nie będzie widać – proszę samemu spróbować! ), skoro rozwiązanie oznaczyliśmy symbolem \varphi możemy napisać:

\varphi = [1,1,1,1,1, \ldots]

    Ciekawe prawda? Okazuje się, że całkiem podobnie zachowują się wszystkie pierwiastki równań kwadratowych! Jeśli liczba A jest pierwiastkiem równania kwadratowego i jest zarazem liczba niewymierną, to jej rozwinięcie na ułamek łańcuchowy jest okresowe. I odwrotnie – okresowe ułamki łańcuchowe reprezentują liczby niewymierne będące pierwiastkami równań kwadratowych!

    Czy istnieją inne podobne zależności? Oczywiście. Kilka przykładów można znaleźć tutaj. Co ciekawe, nadal nie wiadomo na przykład czy istnieją jakieś szczególne wzory związane z pierwiastkami innych równań wielomianowych – stopnia trzeciego czy dziesiątego. Intrygujące własności i problemy nie mające odpowiedzi kryją się także za pytaniami o długość rozwinięcia w ułamki łańcuchowe liczb wymiernych, pytaniem o długość okresu ułamków łańcuchowych okresowych i tak dalej.

Literatura: „Continued Fractions” A.Ya.Chiniczyn

   W następnym wpisie napiszę o drzewie Sterna-Brockota.
—————————————————
Poniżej dyskusja jaka odbyła się po mojej prośbie o „recenzję” powyższego wpisu.

Włodzimierz Holsztyński Miło, Kazimierzu, gdy piszesz konkretnie. Gorzej, gdy nakreślasz panoramy i ferujesz wyroki. Poza tym, gdy piszesz o otwartych problemach, to należy zaznaczyć, że matematycy stawiali je w przeszłości, pisali o nich wiele prac. Niedobrze jest robić wrażenie, że się te pytania samemu wymyślilo, jakby przez dziesiątki lat innym nie wpadały do głowy. Szczególnie razi to w przypadku narzucających się, naturalnych pytań, które często należą do domeny publicznej, bo na ogół matematycy nie chcą się podpisywać pod czymś, co każdy może naturalnie pomyśleć. Owszem, czasem wielkim matematykom przypisuje się wręcz banalne, choć ważne, rzeczy, by ich w ten sposob uczcić i nagrodzić za ich dzieło. A te drobiazgi slużą za pretekst do wykazania szacunku. Aug 24, 2011
Włodzimierz Holsztyński Pierwszy paragraf (w obecnej postaci) jest mylący. Matematyka nie jest popularna, więc niematematycy nie mogą mieć jasnego obrazu stanu rzeczy (nawet nie ma takiej potrzeby, matematyka jest skromna). Mógłbyś ten swój pierwszy paragraf równie dobrze napisać o zwykłych ułamkach k/m, i byłby równie (nie)prawdziwy.
Chociaż wszędzie w matematyce można stawiać nowe, dzikie, więc często trudne pytania, to jednak pewne działy/narzędzia dojrzały, wiadomo ile z ich pomocą można uzyskać w ich naturalnych ramach (bez przedefiniowywania i zmieniania zakresu dziedziny). One dalej są standardowe dla specjalistów. Tak jest właśnie z ułamkami łańcuchowymi. Wiele szanujących się podręczników teorii liczb zawiera między innymi elegancki i systematyczny wykład z ułamków łańcuchowych. Oprócz najslawniejszych matematyków również wielu mniej znanych, ale budzących swoimi wynikami szacunek, stosowało ułamki łancuchowe z wielkim mistrzostwem.
Twój artykuł jest na tyle niepełny (to nie jest krytyka, jeszcze nie :-), że naturalnego zakresu stosowalności ułamków łańcuchowych z niego nie widać. Zaznaczę ten zakres trochę w następnym komentarzu. Ograniczenie metody klasycznych ułamków łańcuchowych stymulowało pewne ich uogólnienia, by jednak pójść dalej. Aug 24, 2011

Kazimierz Kurz @Wlodzimierz Holsztyński – hm, a mógłbyś bardziej konkretnie o tych poruszanych/zadawanych już pytaniach? Bo właściwie to takich uwag oczekiwałem. Jak wiesz nie jestem zawodowym matematykiem i w większości wypadków zapewne nawet nie jestem świadom, że temat był już poruszany. Prawdę mówiąc zanim zabrałem się do pisania wykonałem pewną internetową kwerendę, ale też nie miałem ambicji pisać monografii a piszę „amatorsko” dla „amatorów” – w żadnym razie nie są to prace naukowe…
Jako, że jest to esej, uważam że mam prawo do własnej opinii, i z wielkim zainteresowaniem zapoznam sie z Twoją, a im bardziej będzie niezgodna z moją, tym więcej ciekawych rzeczy się nauczę ;-) Zgoda – Artur Popławski na G+ wspomniał, że ułamki łańcuchowe są w większości monografii, w tym w Narkiewiczu i Sierpińskim. Oczywiście to prawda – zarazem zwykle jest to samo sedno, poświęcone podstawowej konstrukcji i własnościom, nie wspomina się zwykle o drzewie SB, reprezentacji binarnej i związkach z SL(2,N). Rozumiem że to niszowe sprawy, akurat dla mnie ważne bo przygotowuję sobie grunt by opisać na końcu coś co sam (?) wymyśliłem. Aug 24, 2011

Włodzimierz Holsztyński Napisałeś Kazimierzu „Skoro mamy definicję [skończonego ułamka łancuchowego]„, ale definicji nigdzie nie podaleś. Być może w tego typu artykule nie ma potrzeby. Jednak frazy „mamy definicję” nie należy wtedy używać, bo szkodzi się mało doświadczonym. (Z drugiej strony dodam na zapas, że żadnych usprawiedliwień, zwłaszcza długich, też nie należy dawać). Aug 24, 2011

Kazimierz Kurz Alez definicja jest: „Zajmijmy się na początek podstawowymi definicjami. Przez ułamek łańcuchowy, zapisywany jako [a_0;a_1,a_2,a_3 ... a_k] będziemy rozumieli liczbę postaci:

(1) [ a_0;a_1,a_2,a_3...a_k ] = a_0 + \frac{1}{ a_1 + \frac{1}{ a_2 + \ldots \frac{1}{ a_k}}}

gdzie liczba a_0 jest liczbą całkowitą ( a więc może być ujemna, zero lub dodatnia) zaś a_i sa liczbami naturalnymi. Jest to tak zwany ułamek łańcuchowy w postaci kanonicznej lub regularnej lub prostej .
[...]
Skoro mamy definicję, spróbujmy zapisać w tej postaci jakąś liczbę. wiele przykładów jest bardzo prostych, inne wymagają pewnego nakładu pracy: ” Może nie działa Ci renderowanie wzorów? Aug 24, 2011

Włodzimierz Holsztyński Dowód twierdzenia (T2) jest ładny, a jego metoda cenna dla czytelników. Sformułowanie (T2) jest niepełne. Pelne twierdzenie mówi, że dla każdej liczby wymiernej istnieją dokładnie dwa różne skończone ułamki łancuchowe, reprezentujące daną liczbę. Informacja o dwóch rozkładach jest ważna w kontekście reprezentowania wszystkich liczb rzeczywistych. Jest to ważna część obrazu. Przypomina ułamki dziesiętne: każda liczba wymierna postaci k/10^n dopuszcza dokładnie dwa różne nieskończone rozwinięcia dziesiętne; na przykład (w układzie dziesiętnym):

1/10^0 = 1.0000… = 0.99999…

Wszystkie pozostałe liczby rzeczywiste są reprezentowane przez dokładnie jedno nieskończone rozwinięcie dziesiętne.

Chodzi w obu sytuacjach o reprezentowanie (rozrywanie i sklejanie) ciągłego zbioru liczb rzeczywistych poprzez dyskretne obiekty jak liczby calkowite lub cyfry dziesiętne. Aug 24, 2011

Włodzimierz Holsztyński Powszechnie mówi się o tym, że Archimedes udowodnił podwójną nierówność:
3 + 10/71 < pi < 3 + 1/7
W tej chwili nie jestem pewny, co wiadomo o jego znajomności dalszych przybliżeń. Być może już wtedy znał(?) późniejsze chińskie przybliżenie 355/113 (znane też poza Chinami), ale z pewnością nie więcej. Warto to porządnie sprawdzić. Aug 24, 2011

Włodzimierz Holsztyński Warto zauważyć, że kolejne redukty przybliżają wartość ułamka łancuchowego na przemian: od dołu, od góry, od dołu, od … Jest to prosta obserwacja.
Dobrze wiadomo, że kolejne redukty są (w mojej terminologii) sąsiadami, t.zn.
|k/m – s/t| = 1/(m*t)
Jest to jedna z ich podstawowych własności. Aug 24, 2011

Kazimierz Kurz O reduktach będę wspominał w późniejszym toku, chociaż z innych powodów.
Z Archimedesem – chyba masz rację – i chyba nieco przekoloryzowałem – znał tylko przybliżenie o którym piszesz na podstawie aproksymacji wielokątami. Aug 24, 2011

Włodzimierz Holsztyński Przy okazji niewymierności kwadratowych można podać informację o problemie ułamków łańcuchowych czysto okresowych, rozwiązanym i opublikowanym(!) przez E.Galois. Więc jeszcze jeden wielki matematyk zajmował się ułamkami łańcuchowymi.
Z grubsza mówiąc, teorioliczbowe problemy algebraiczne stopnia 2 oraz niewymierności stopnia 2 stanowią naturalny zakres stosowalności ułamków łancuchowych. Dla problemów stopnia 3 kilku matematyków badało pewne uogólnienia ułamków łancuchowych. Uzyskali pewne ciekawe wyniki, ale nie udało się rozwinąć równie pełnej i harmonijnej teorii, co w przypadku standardowych ulamków okresowych lub ich wariacji. Wygląda na to, że pełna ogólniejsza teoria, pożyteczna dla stopnia 3, nie istnieje. Aug 24, 2011

Włodzimierz Holsztyński Nie mogę się zdecydować, Kazimierzu, czy Twój artykuł jest krótki, czy długi. Mimo to w każdym wypadku zdumiewającym jest, że nie podałeś zasadniczego powodu dla wprowadzenia ułamków łańcuchowych. To, że czasem fuksem przybliżają niewymierności ekstra dokładnie, jest ledwo marginesową uwagą, a nie powodem. Czyli (gdy brak motywacji) mamy do czynienia ze sztuczną, ciężką konstrukcją, która w końcu nic nie daje. Poza odwrotnością liczb dodatnich, to nawet nie widać na oko żadnych na nich pożytecznych operacji arytmetycznych. Prawdziwy powód jest następujący: redukty i tylko ułamki równe reduktom, są tak zwanymi „najlepszymi przybliżeniami wymiernymi” liczby reprezentowanej przez ułamek łańcuchowy.
Przy tym „najlepszymi” w pewnym nie byle jakim silnym sensie – trzeba tu uważać, bo czasem nawet doświadczony matematyk może się w momencie słabości zmylić (czego byłem świadkiem na seminarium z teorii liczb na jednym z czołowych wydziałów matematycznych :-). Aug 24, 2011

Kazimierz Kurz @Włodzimierz – rozpatrujesz ten esej jako samodzielną całość – a tak nie jest – o bardzo praktycznej aproksymacji wspominam już w 2-giej części – przy czym wprowadziłem ją nieco historycznie – za pomocą drzewa SB które zostało użyte do wynajdywania takich przybliżeń. Moim celem jest jednak na koniec przedstawienie własnych wyników – dlatego cykl esejów ma do nich przybliżać. Ponieważ wyniki te (choć dla mnie ciekawe) nie są szczególnie przełomowe czy ważkie, uznałem że podążając w pewnym kierunku, będę jednak pisał nieco popularnie, by osoby niezwiązane uczuciowo z tematem coś z tego wyniosły. Gdybym napisał od razu co wymyśliłem – nikt by się tym nie zainteresował, a tym bardziej żądnej korzyści by z tego nie odniósł ;-) Aug 24, 2011

Włodzimierz Holsztyński @Kazimierz – jest trzykropkowa sugestia, ale definicji nie ma.
Rozpisanie się o ułamkach łańcuchowych bez podania ich zasadniczej własności, po prostu jest bez sensu, niepotrzebnie czytelnikowi zaśmieca się głowę. To, że w następnym artykule masz jakieś obserwacje dotyczące aproksymacji, niczego tu nie zmienia. Nawet nie odważyłeś się napisać, że równoważne. Prawdopodobnie nie wiedziałeś przy pisaniu. Prawdopodobnie słabsze.
Masz prawo do swoich opinii. Masz prawo głosić je publicznie. Co nie zmienia faktu, że aż za często jest to w złym guście. (Mniejsza o wartość merytoryczną, zaciemnioną niejasnym pisaniem).
Co do odnośników, to nie jestem specjalistą, ani nie mam zdolności kolekcjonowania ich. Na dodatek wciąż mi przetrzebiało moją osobistą bibliotekę, taki los. Wskażę na kilka problemów, do których stosowano ułamki łancuchowe. Jednak takich prac były tuziny, jeżeli nie setki. Prawdziwe poznanie ułamków łańcuchowych oznacza przeskoczenie pewnej bariery, Ci, którzy to uczynili, stosowali ułamki łańcuchowe jako swoje regularne narzędzie naukowe. Zaabsorbowanie wiedzy czyli nabycie techniki ułamków łancuchowych wcale nie jest czymś prostym – jest solidnym osiągnieciem (możliwym dla niewielu), które procentowało w twórczości szeregu laikom nieznanych, ale bardzo dobrych, utalentowanych ekspertów.
W każdym razie, skoro nie poszedłeś do biblioteki, nie przeszukałeś starannie literatury, to moralnie nie miałeś prawa podawać swojej opinii o stanie tej teorii. Jako minimum, choć to byłoby bez sensu, mógłbyś napisać, że podajesz opinię ignorancką, nie opartą na znajomości literatury. Internet wciąż, w przypadku matematyki, nie jest głównym źródłem matematycznej wiedzy historycznej lub bieżącej. Z czasem będzie lepiej, mam nadzieję, ale to jeszcze potrwa.
Ułamki łańcuchowe stosowano do dowodu twierdzenia Fermata o reprezentowaniu liczb pierwszych, dających 1 z dzielenia przez 4, jako sumy dwóch kwadratów (np. 5=2^2+1^2, 13 = 3^2 + 2^2, itd); stosowano do rozwiązania równania Pella; w tematyce Stormera; przy wyznaczeniu kolejnych, najgorzej wymiernie przybliżalnych liczb … J.Browkin i J.Brzeziński w publikacji z 1994 zastosowali ułamki łancuchowe heurystycznie do uzyskiwania przykładów, związanych z hipotezą abc.
Twoja uwaga, @Kazimierzu, na samym końcu artykułu o ułamkach łancuchowych, jest niestosowna. (Sam się nad tym zastanów, bo nie będę wywalał kawy na ławę). Aug 25, 2011

Kazimierz Kurz @Wlodzimierz – ja jednak jestem prostak i wolałbym abyś dał kawę na ławę. Nie wiem o czym mówisz, a obawiam się, że liczenie na moją domyślność jest kompletnie bez sensu. Artykuł jest pomyślany jako dosyć swobodna wymiana myśli, broń boże ani podręcznik ani wprowadzenie nie bardzo więc widzę powód dla którego miałbym formalnie pisać: Definicja: …
Krytykę przyjmuję, częściowo się z nią zgadzam, choć nie znalazłem w niej nic ( w mojej opinii) co miałoby spowodować konieczność zmian w tekście (np. napisanie: „J.Browkin i J.Brzeziński w publikacji z 1994 zastosowali ułamki łancuchowe heurystycznie do uzyskiwania przykładów, związanych z hipotezą abc.” – jest szalenie ciekawe i ważne, ale co to wnosi do wiedzy adresata tego wpisu który ułamków łańcuchowych w założeniu wcale nie zna a jeśli już to tylko od strony elementarnej definicji? Zaś przedstawienie hipotezy abc to jednak co najmniej osobny artykuł w którym wytknąłbyś mi – całkiem słusznie – kolejne tysiące błędów ;-) Bardzo chętnie natomiast przeglądnąłbym jakieś wprowadzenie w prace Galois o których wspomniałeś – masz może jakieś namiary?) . Uzupełnienie wiadomości historycznych jest jak najbardziej sensowną sugestia ale do treści niewiele wnosi – większość z tych tematów jest całkiem nieźle opracowana lub zasygnalizowana np. w wikipedii na temat ułamków łańcuchowych – a nie widzę powodu dla którego miałbym dublować tamtejsze wpisy. Dodanie rzetelnego wpisu historycznego wymagałoby po pierwsze bardzo wiele pracy ( sprawdzenie źródeł) a po drugie rozwlekłoby artykuł – musiałbym zrobić część „0″ tylko o tym. W mieście ( a raczej miasteczku ) w którym mieszkam nie ma biblioteki naukowej – sam nie jestem afiliowany przy żadnej instytucji edukacyjnej – nie mam dostępu do JSTOR itp. – o szukaniu prac Galois nie mam więc co marzyć ;-) chyba że są na arxiv. Na Buzz czy G+ ( a nawet na blogu) nie ma miejsca na takie wpisy – w sumie szkoda. Ten i tak został nazwany „dłuuugaśnym”.
Ale może kiedyś wykonam jakąś część pracy która mi zalecasz – wówczas pewnie zbiorę to w formę nieco bardziej obszerną – ebook?. W zasadzie pchasz mnie w tym kierunku swoimi uwagami – i to jest intrygująca myśl… Aug 25, 2011

Włodzimierz Holsztyński @Kazimierz – wcale nie sugerowałem, że należy zamieścić odnośniki na które wskazywałem (choć może ze 2-3 przydałoby się, chyba tak, to nic o tym nie pisałem). Aug 26, 2011

Włodzimierz Holsztyński @Kazimierz – nie chodzi o słowo „DEFINICJA”. Chodzi o to, że nie podaleś definicji (nie ważne, czy wodrębnionej formatem, czy nie), a piszesz, że podałes. Nie musiśz podawać, ale wtedy należy jasno napisać, że się podało tylko sugestię ułamka łańcuchowego, a nie definicję. Podanie „wzoru” z trzema kropkami nie jest definicją. W najprostszych wypadkach można sobie na taki luksus pozwolić. W danym wypadku tak nie jest. Dałeś jakąś ideę o co chodzi, ale nie definicję.
Dla przykładu:
()\quad\quad\quad\sum_{k=1}^n\ a_k\ \ :=\ \ a_1 + ... + a_n
nie jest definicją sigmy (sumy od 1 po n). Podobnie dla funkcji rzeczywistej f nie jest definicją jej sumy wyrażenie typu:
(*)\quad\quad\quad\sum, f\ := ... + f(x) + ...
po wszystkich elementach x\in X , gdzie X jest domeną funkcji f,.
=================
Mam nadzieję, że TeX ( [;\TeX;] ) skompiluje się. (U siebie widzę go skompilowanego). Aug 26, 2011

Kazimierz Kurz @Wlodzimierz – co do definicji to zasadniczo nie bardzo rozumiem, a na swoje usprawiedliwienie mam następujące przykład:
http://books.google.com/books?id=R7Fp8vytgeAC&lpg=PP1&dq=continued%20fractions&pg=PA1#v=onepage&q&f=false – tu natomiast jest książka Chiniczyna – w zasadzie da mnie podstawowy materiał źródłowy ( obok wikipedii i strony Bogomolnego)
Czy mógłbyś zatem napisać jak Twoim zdaniem miałaby wyglądać ta definicja?
W moim mniemaniu definicja to „nazwa” na znany obiekt. Po lewej stronie – coś definiowanego – po prawej wyrażenie które znamy ( np. umiemy wyliczyć jego wartość). Oczywiście stosując sztuczne języki jak Coq, matematykę w języku aksjomatyzacji Peano arytmetyki itp. należy definicję także zapisywać formalnie. Nie widzę jednak powodu by w popularnej pogadance o ułamkach łańcuchowych pisanej swobodnym językiem i adresowanej do amatorów wyrażenie które napisałem nie miało być przyjęte za definicje. Coś czego nie zdefiniowałem – to ułamek łańcuchowy nieskończony – ale o tym będę jeszcze pisał a na tym etapie w zasadzie nie było potrzebne – operowałem w zasadzie wyłącznie na skończonych obiektach poza przykładem (!) dla równania kwadratowego co było wtrętem i nie miało związku z treścią. Aug 26, 2011

Włodzimierz Holsztyński @Kazimierz – pisz tak jak piszesz, tylko unikaj mówienia, że podałeś definicję. Możesz napisać, że Twoje dwa czy trzy paragrafy pozwalają dostatecznie jasno czuć czym są ułamki łańcuchowe. Ewentualnie możesz nawet napisać, że nie podałeś formalnej definicji, ale nie ma już wątpliwości czym są ułamki łańcuchowe. Przy tym w żadnym wypadku ani nie usprawiedliwiaj się z niepodania definicji formalnej, ani przede wszystkim nie pisz, że nie podałeś, bo piszesz dla niematematyków, itp. (trudno byłoby o coś gorszego w popularyzatorskim lub podręcznikowym tekście–w słabych jest to nagminne). Co najwyżej, i jak najbardziej, można czytelników po dalszą wiedzę odesłać do dalszych pozycji w literaturze, jak na przykład niewielki klasyczny podręcznik teorii liczb autorstwa Winogradowa (ostro napisany, ale świetny). Aug 26, 2011

Marek Wojcik Kazik, pisz nie przejmuj się. Z matematycznymi purystami zawsze są problemy, co nie zmienia faktu, że są szalenie pożyteczni, wręcz niezbędni na późniejszych etapach pogłębiania wiedzy. Aug 26, 2011

Kazimierz Kurz Heh, dziękuję Marku. Osobiście prosiłem Wlodzimierza o przejrzenie i krytyczną opinię – i jestem mu za nią wdzięczny. Biorę sobie do serca uwagi Wlodzimierza bo wie co mówi, choć zapewne patrzy na to co napisałem z innego kompletnie punktu widzenia niż ja – stąd spore różnice w zdaniach. Mam swoją wizję propagowania matematyki, jakkolwiek zabawnie by to nie brzmiało, drażni mnie maniera wypisywania twierdzenia popieranego następnie dowodem ( co przecież jest chwalebną tradycją ;-). Wolę formułowanie twierdzeń po przedstawieniu rozumowania po którym stają się oczywistymi wnioskami. Ale moim celem nie jest popularyzacja ułamków łańcuchowych tylko napisanie coś o własnym pomyśle którego z powodu braku wiedzy i czasu nie umiem rozwijać dalej. Ponieważ jestem jednak świadom że to co wymyśliłem to taki drobiazg, a żeby o tym napisać i tak trzeba kupę rzeczy objaśnić, pomyślałem, ze zrobię to właśnie w taki, amatorski i popularny sposób. Pomyślałem, ze jeśli będę umiał rzecz wytłumaczyć komuś kto nie wie o ułamkach nic zgoła – sam to lepiej zrozumiem ;-)
Na koniec się pewnie okaże że góra mysz urodziła, wiec niech chociaż ta popularyzacja ma jakąś wartość… Aug 26, 2011

Follow

Otrzymuj każdy nowy wpis na swoją skrzynkę e-mail.

Join 898 other followers

%d bloggers like this: