Ukończony projekt sprzed lat

Na początku mogę pozdrowić kumatych, którzy przyjrzeli się zdjęciu moich wypocin. Dla tych nieco mniej kumatych – tak, te bazgroły dotyczą wyznacznika macierzy. Kto nie wie, co to macierz, nie wie też na pewno, czym jest jej wyznacznik. A takim należy tylko współczuć.

Nie no, żartuję. Na współczucie jest już za późno.

 

Żarty na bok, bo wpis będzie w sumie o tym, jak to się prawie popłakałem. Prawie, chociaż kilka łezek pociekło mi z prawego oka. Ale może to wynik zbyt długiego siedzenia przy komputerze.

Dawno, dawno temu…

studiowałem sobie matematykę. Był na którymś tam semestrze przedmiot pod nazwą >>PROGRAMOWANIE<<, czy jakoś tak, może podstawy, a może nie. No i to była moja pierwsza (poza gównianymi zajęciami w liceum) styczność z programowaniem, a konkretnie z językiem C++.

Dzisiaj trochę się z tego śmieję, bo używaliśmy wówczas „środowiska” DevC++, który jest odradzany ze względu na… chyba wszystko. No, ale nie mając pojęcia o istnieniu takiego cuda jak Visual Studio, kodziliśmy sobie w Devie.

Szło mi nawet-nawet. Prowadzący w pewnym momencie zaproponował, a wręcz zasugerował, bym przepisał się do drugiej grupy projektowej, ponieważ w tej „macierzystej” podobno zawyżałem poziom. Ale nie było tak różowo do końca semestru. Dostałem do zrobienia zadanie, które miało mi gwarantować najwyższą ocenę.

Nemezis moja ty, po nocach mi się śnisz

Polecenie brzmiało niezbyt interesująco:

Napisz program obliczający wyznacznik macierzy stopnia n

Pomyślicie – co za problem? Jak się umie liczyć n=2 i n=3, to można metodą indukcji matematycznej przenieść to na wyższe stopnie.

Otóż, kurwa, nie.

Wypada wiedzieć, że najogólniejszą metodą liczenia wyznacznika macierzy jest rozwinięcie Laplace’a, które to tylko w przypadku właśnie n=3 i n=2 przybiera taką, a nie inną, prostą skądinąd formę.

Jak to wygląda w praktyce, zaraz pokażę.

uwaga!!! osobom nieobeznanym z podstawami rachunku macierzowego moje pieprzenie poniżej może tylko namieszać w głowach,
gdyż stosuję w nim dużo uproszczeń, skrótów myślowych
i (zapewne) odstępstw od konwencji!!!
w żadnym wypadku nie odpowiadam za pały na klasówkach czy rachunki za powtarzanie przedmiotów!!!
do chuja pana!!!!!!!!!!!!!

Trochę pisania piórem po kratkach…

Poniżej ogólne rozwinięcie Laplace’a dla wyznacznika (det – determinant, czyli wyznacznik) stopnia 4, rozwinąłem względem pierwszego wiersza. Oczywiście mogłem to rozwinąć względem dowolnego wiersza czy kolumny, ale na ogólnym przykładzie jest to obojętne. Warto pamiętać, by rozwijać tam, gdzie jest najwięcej zer, a jeśli zer nie ma, dobrze jest doprowadzić do ich pojawienia się.

Duże literki „M” to minory – wyznaczniki macierzy powstałych przez wykreślenie z macierzy głównej wierszy i kolumn podanych w indeksie dolnym minora. Rozpiszmy sobie M00:

Na tej samej zasadzie rozpiszę minora z minora, a potem minora z minora z minora:


Napisałem „bo tak jest”, bo tak jest. Wyznacznik macierzy jednoelementowej jest równy temu elementowi. Zresztą, jak chcielibyście to rozwijać? Chyba się zgodzicie. A dla macierzy o wymiarach 2×2 będzie tak:

Widzimy, że ostatecznie rozwinięcie wyznacznika 2×2 można skrócić do mnożenia wyrazów macierzy „na krzyż”. Proste?

Co się zaś będzie działo dla wyznacznika o wymiarach 3×3?

Dotarliśmy do momentu, gdy pojawiły się minory stopnia drugiego. A przecież wiemy, że można je pomnożyć na krzyż. Dostaniemy więc takie coś:

Teraz wystarczy uporządkować wyrażenia względem znaku:

żeby zobaczyć coś cholernie ciekawego:

Mianowicie, jeśli dopiszemy sobie pod wyznacznikiem dwa pierwsze wiersze (albo obok odpowiednie dwie kolumny) wyjdzie na to, że tu też mnożymy na krzyż! Proste? No ba, i to o ile prostsze, niż pieprzenie się z ogólną formą rozwinięcia Laplace’a.

Nic nie może jednak wiecznie trwać

W związku z tym, że już późno, a ja jestem leniwy, nie rozpiszę wyznacznika stopnia czwartego. Musicie mi uwierzyć na słowo, że od czwartego wzwyż nie da się już wymnażać na krzyż (hehe, poeta, tylko głowa nie ta). Co za tym idzie, trzeba się bawić w rozwinięcie Laplace’a aż do uzyskania minorów o wymiarach 3×3 – wówczas można mnożyć. Przy czwartym stopniu daje to cztery wyznaczniki trzeciego stopnia do wymnożenia. Niezbyt wiele? No to…

…pobawcie się w wyznacznik stopnia szóstego. To jest sześć wyrazów, każdy przemnożyć przez minor 5×5. Każdy z tych minorów trzeba rozwinąć, więc mamy pięć minorów czwartego stopnia. Te też trzeba rozwinąć, więc ile na koniec dostajemy minorków 3×3 do wymnożenia?

STO PIEPRZONE DWADZIEŚCIA WYZNACZNIKÓW 3×3!!!!

Ale matematyka jest piękna nie od parady. Powiedzieliśmy wcześniej, że najlepiej rozwijać względem tych kolumn czy wierszy, gdzie jest najwięcej zer, a jeśli ich nie ma, to sobie dorobić. Nie będę się tu rozwodził nad operacjami, które można wykonywać wewnątrz wyznacznika. Dość powiedzieć, że można tych zer narobić tyle, żeby pod główną przekątną nie było nic oprócz nich. Wówczas wyznacznik może wyglądać np. tak:

O jejku, a kuku, a co to?

Rozwijając względem pierwszej kolumny, mamy JEDEN minor stopnia czwartego do wyliczenia, który również rozwiniemy względem pierwszej kolumny, co da nam JEDEN minor stopnia trzy. Tutaj możemy już sobie powymnażać na krzyż, ale dla obrazowego spojrzenia lepiej dalej rozwijać względem pierwszych kolumn. I tak na jedno wyjdzie. Z racji tego, że zawsze jedziemy względem pierwszej kolumny, potęga minus jedynki zawsze będzie parzysta, a więc wyliczenie wyznacznika sprowadzi się do wymnożenia tylko i wyłącznie wyrazów na głównej przekątnej tej wielkiej macierzy. Najpierw jednak trzeba się narobić, żeby te zera uzyskać.

wracamy do wątku głównego

Dość już przynudzania. Mnie zabawa z macierzami jara, ale Was nie musi. Wracając do projektu na zaliczenie, jako początkujący progr… tfu! student siedziałem po nocach i kombinowałem algorytm. Nie chciałem patrzeć do internetu, jestem z natury frajerem, to znaczy uczciwym człowiekiem, więc piątka za rozwiązanie zerżnięte z sieci nie sprawiłaby mi satysfakcji.

No i poległem. Nie dałem rady tego zrobić.

Byłem na siebie wściekły, czułem się do bani, zniechęciłem się do programowania. Pomocne nie były rady kolegi: „Użyj tablic dynamicznych”. Bo w czym mi to miało pomóc, skoro mój program czasami po prostu nie chciał liczyć wyznacznika. Zwaliłem to wówczas na gówniane środowisko, o sprawie zapomniałem.

do czasu

Studia. Informatyka. Przedmiot: Techniki programowania. Projekt na zaliczenie – dowolny. Oczywiście do konsultacji z prowadzącym, nikt przecież nie da nawet trójki za program wywalający „Hello world!”. Więc ja sobie wybrałem: Kalkulator macierzowy! Taki z wyznacznikiem! To będzie motywacja, by dokończyć niedokończone!

Zrobiłem prawie cały program w dwie godziny. Trochę więcej czasu zajęła mi obsługa plików (wczytywanie i zapisywanie), ale w końcu się udało. Wyznacznik zostawiłem sobie na sam koniec. Nad tym jednym algorytmem siedziałem niemal cały dzień. I w końcu, nareszcie…

…wkurwiłem się na siebie, tego sprzed siedmiu lat. Bo o czym wówczas zapomniałem? Spójrzmy jeszcze raz na to, jak należy sprowadzić pieprzoną macierz do pieprzonego trójkąta:

Ano trzeba w pewnym momencie sprawdzić, czy nie dzieli się przez zero, i w razie przysłowiowego Szweda zamienić miejscami wiersze, co, wbrew pozorom, może znacznie przyśpieszyć liczenie. Siedem lat temu nie pomyślałem o tym. Do łba mi to nawet nie zastukało. Cóż…

Tak więc, udało się, dziękuję, kurtyna. Popłakałem się (prawie), ale poczułem w sobie… moc? siłę? Górnolotnie to trochę brzmi, ale coś takiego w sobie poczułem. Zrobiłem to sam, bez posiłkowania się przykładami z internetu. Miałem co prawda chwile zwątpienia, i chciałem zrobić to rekurencyjnie poprzez ogólne rozwinięcie Laplace’a, ale tak się zamotałem przy pisaniu funkcji, że postanowiłem nie zarzynać procesora zapętlonym wywoływaniem funkcji.

Zrobiło mi się zimno na myśl, że wyznacznik stopnia 50 mógłby spalić mój komputer. Dosłownie!

Postanowiłem podzielić się z Wami moim osiągnięciem. Zdaję sobie sprawę z tego, że kod może nie być zbyt dobrej jakości, komentarzy też jakoś na lekarstwo (nie wiem jak skomentować coś, co wydaje się oczywiste), ale na dobry początek chyba może być.

Może dzięki temu znajdę pracę, może nawiążę nowe kontakty, a może ktoś napisze do mnie z informacją „Ej, stary, zjebałeś tu, tu i tu”. Krytyka, jeśli jest konstruktywna, na pewno prowadzi do rozwoju.

Z tej okazji utworzyłem nową stronę w nawigacji bloga: GITHUB: JULIUSZ MARETZKY

A tutaj bezpośredni link do mojego konta na GitHubie: OTO I ON.

Jestem świadom swego człowieczeństwa, więc jeśli popełniłem gdzieś jakieś poważne merytoryczne błędy,
lub, co gorsza, obliczeniowo-przekształceniowe, dawajcie znać. Trzeba to będzie jak najszybciej poprawić.

Share This:

No Comments

Leave a Comment