Wiele już razy pisałem o ułamkach łańcuchowych i rzeczach z nimi związanych. Obsesja ta zaowocowała wpisami dotyczącymi tworzenia własnych reprezentacji algebraicznych ułamków łańcuchowych, zapisywania skomplikowanych zależności jeszcze bardziej skomplikowanymi calkami oraz oryginalnym wyprowadzeniem w zasadzie nieciekawej zależności rekurencyjnej miedzy kontynuantami. BA, nie posiadając po temu żadnych kwalifikacji i wiedzy rzuciłem sie do programowania by stworzyć arkusz w Sage pozwalający na własne eksperymenty z strukturami o których wspomniałem ( z wszystkich linków w tym wpisie działa już tylko odwołanie do google docs – trzeba arkusz ściągnąć  i załadować do własnego Sage. Postaram sie to naprawić). Nieźle jak na amatora. Jestem z siebie dumny. Tym razem jednak przedstawię fakt tak oczywisty, a mimo to będzie zaskakujący i nowy. Nowy i nieznany nauce fakt** Wow! No przynajmniej ja nie widziałem by ktoś to tak analizował…

Z definicji przytaczanej przez wikipedie a takze z bardzo ciekawej książki, a fakt ów pochodzi z jej II tomu, zaś sama książka wydana została w roku 1900 i zawiera co najmniej jeszcze jeden piękny fakt dotyczący kontynuantów do którego powrócimy w przyszłości, postanowiłem połechtać tu waszą ciekawość – szukajcie, szukajcie… ekhem.. z książki G.Chrystal pod tytułem „Algebra: An elementary text-Book” , dostępnej online, wynika, ze dla kontynuantów, jeśli zdefiniujemy macierz G jak następuje:

G = \left| \begin{array}{ccccccc}  a_{0} & 1 & 0 & 0 & 0 & \ldots & 0 \\  -1 & a_{1} & 1 & 0 & \ldots & 0 & 0 \\  0 &-1 & a_{2} & 1 & \ldots & 0 & 0 \\  \vdots & \ddots & \ddots & \ddots & \ddots & \vdots & \vdots \\  0 & 0 & 0 & 0 & \ldots & -1 & a_{n}  \end{array}\right|

(1) det(G) = K(a_{0}, a_{1}, \ldots , a_{n})

zachodzi następujący związek

(1) det(G) = K(a_{0}, a_{1}, \ldots , a_{n})

Gdzie M jest macierzą zdefiniowana powyżej zaś $latex K(a0, a1, \ldots , a_n) $ jest kontynuantem. Tymczasem z poprzednich wpisów wiemy ze zachodzi następujący związek:

(2) \displaystyle K(a_0, a_1, \ldots , a_n) = \frac{1}{2} Tr \left( M(S- L) \right) = \ldots
\ldots = \frac{1}{2} Tr \left( S \prod_{i=0}^{n} S(ST)^{a_{i}} (S - L) \right)

Macierze S, T, M występujące w powyższym wzorze maja rozmiar 2×2 i zdefiniowane sa w tutaj. Co to oznacza? Łącząc (1) z (2) uzyskujemy przedstawienie wyznacznika macierzy G o rozmiarze (n+1)x(n+1) reprezentującej kontnuant, jako śladu z iloczynu mniej więcej (n+1) macierzy 2×2. Bo przecież potęgowanie macierzy, które występuje we wzorze (2) ładnie wygląda, ale wcale nie jest konieczne. Bardzo interesujące, prawda?

Po pierwsze pomyślmy chwilkę ile zachodu kosztuje obliczanie wyznacznika. Aby policzyć wyznacznik macierzy NxN metoda naiwna potrzeba N! mnożeń. Dla dużych macierzy – to ogromny koszt obliczeniowy. Oczywiście algorytm naiwny nie jest szczególnie efektywny – istnieją lepsze. O ile wiem najlepsze obecne algorytmy liczenia wyznacznika dowolnej macierzy NxN ma efektywność rzędu n^4 . Wyliczanie wyznacznika nie jest szczególnie ważną procedurą numeryczną – z tego co czytałem wynika, ze wbrew pozorom całkiem sporo algebry da się wykonać wcale go nie obliczając, na przykład wyliczenie rozwiązań równań liniowych obywa się bez niego. Po części wynika to także i z tego ze procedury mnożenia macierzy udało sie zrealizować w złożoności obliczeniowej rzędu n^{3.3} i gdzie tylko można raczej dokonuje sie ich użycia, łącząc je z sprytnymi rozkładami macierzy na iloczyny macierzy specjalnych, jak na przykład w rozkładzie LU.  Innymi słowy wyznaczniki się wylicza ale nie dla macierzy w ogólnej postaci, a dla postaci szczególnych, kiedy jest to łatwe i dogodne. Oczywiście wyliczanie wyznacznika pewnych typów macierzy, jak macierze diagonalne, rzadkie czy trójkątne wymaga mniej zachodu. Macierz G powyżej jest przykładem takiej macierzy. Dla szczególnie dużych liczb N, to co dzieje sie w rogach nie jest istotne, a wyliczenie jej wyznacznika wymaga w wypadku metody naiwnej „jedynie” 3 \times 3 \times 3 \ldots 3 = 3^n mnożen ( z których każde 2 sa prostymi mnożeniami przez 1 lub -1 ). Gdyby przyjąć za dobra monetę szacowanie nienaiwne oparte o algorytmy o złożoności N^4 z pewnością wyznacznik ów da sie wyliczyć znacznie bardziej efektywnie i szybko, z pewnością ze złożonością wielomianową. Niestety nie posiadam wiedzy o numeryce dostatecznie głębokiej by móc takiego oszacowania dokonać – nie wiem jak działają owe algorytmy $N^4$ Może Ty – czytelniku – potrafisz w komentarzu kompetentnie rozwiać budowane tutaj miraże – zapraszam.

Mnożenie macierzy z wzoru (2) wymaga powiedzmy n 2^3 czyli około n mnożeń macierzy! Oczywiście dla małych n czynnik 2^3 jest kłopotliwy i istotny, jednak dla dużych n, jeśli moje szacowania nie są całkowicie błędne – mamy linowe lub prawie linowe skalowanie z liczba n. Macierze S i T są bardzo proste i posiadają szereg własności bardzo ułatwiających ich mnożenie. Przykładowa implementacja funkcji wyliczającej kontynuant bazującej na wzorze (2), dokonana w Sage, znajduje sie tu. Co więcej – w konkretnych przypadkach wyliczania wartości ( a wiec przy obliczeniach numerycznych, kiedy nie mamy symboli a wartości liczbowe), wiele języków programowania implementuje macierze 2×2 jako typy proste, wbudowane, a tym samym bardzo efektywne obliczeniowo. W sytuacji obliczeń symbolicznych zysk wydaje sie być jeszcze większy – na przykład własnoręczna implementacja iloczynu macierzy jest znacznie prostsza niż implementacja wyznacznika, na dodatek dla macierzy o zmiennej ilości wierszy / kolumn. Zaznaczę ze nie „efektywność” jest tu cecha wazka czy ciekawa, ale związek miedzy wyznacznikiem macierzy NxN a śladem iloczynu N macierzy 2×2

Na zakończenie pozwolę sobie odwołać do poprzedniego wpisu, który uczyniłem tylko jako cover do tego opus magnum które czytasz szlachetny czytelniku. Czy szokujące fakty przedstawione powyżej sa przypadkiem? Nie ulega najmniejszej wątpliwości ze zależność (1) = (2) wynika z specyficznej konstrukcji macierzy G – jest to tak zwana macierz tridiagonalna. Zgodnie z wpisem z wikipedii o kontynuantach, można rozważać ogólniejsze postaci takich macierzy, ogólniejsze pojecie kontynuantu i ogólniejsze pojecie ułamka łańcuchowego. Wiadomo ze są one równoważne, a każdy ułamek/kontynuant ma swoje jednoznaczne przedstawienie „kanoniczne” czyli takie jakim wyłącznie zajmuje się w swoich wpisach. Co najmniej do tego poziomu możliwe jest utrzymanie takiej czy innej relacji podobne do (1) = (2). Czy relacja ta ma jakieś uogólnienia na mniej dogodne postacie macierzy G? Czy droga badania zależności – wyznacznik macierzy NxN jako ślad iloczynu macierzy 2×2 ( lub innych ale stałych rozmiarów) jest otwarta i obiecująca czy bezsensowna? Przypadek czy coś intrygującego? Jeśli ktokolwiek słyszał, ktokolwiek wie…

**piękne w matematyce jest także i to że każdy – także i ty czytelniku, możesz wynajdywać własne, nieznane nauce fakty. Wystarczy starać sie nie oszukiwać i próbować sobie uczciwie dowieść, ze to co sie jedynie przypuszcza musi być prawdziwe. To gra dla jednego uczestnika, ale bardzo wciągająca. Pobaw sie wnikliwie dowolnymi czterema cyframi – a po 15 minutach znajdziesz nowe, oryginalne twierdzenie… Zachecam1G