Mamy macierz wstęgową \(\displaystyle{ B_{nxn}}\) o szerokości wstęgi \(\displaystyle{ w}\). Ile operacji musimy na niej wykonać w drodze eliminacji? Jaka jedną operację rozumiemy tu mnożenie współczynników i odjęcie od wiersza.
Odpowiedź, jaką znalazłem to \(\displaystyle{ nw^2}\) operacji, wytłumaczenie jest następujące:
Wyzerowanie współczynników poniżej pierwszego piwota to \(\displaystyle{ w^2}\) operacji (\(\displaystyle{ w}\) wierszy poniżej i mnożymy przez rzędy o długości \(\displaystyle{ w}\)). Powtarzając dla każdej kolumny dostajemy \(\displaystyle{ nw^2}\) operacji.
Jednak sprawdzając dla \(\displaystyle{ n=4}\) i \(\displaystyle{ w=2}\), żeby wyzerować pierwszą kolumnę poniżej piwota potrzebujemy 6 operacji (zerujemy 2 wiersze poniżej, a pierwszy wiersz ma 3 elementy - a nie 2, jak wskazywałoby wyjaśnienie, które znalazłem). To samo mamy przy zerowaniu kolumny drugiej, a dla kolumny trzeciej mamy 2 operacje. To razem daje 14 operacji, co różni się od przewidywanego \(\displaystyle{ nw^2=16}\). W dodatku dla \(\displaystyle{ n>5}\) uzyskuję liczby operacji większe od \(\displaystyle{ nw^2}\).
Liczbę \(\displaystyle{ nw^2}\) znalazłem w kilku źródłach, więc skąd wystepują takie rozbieżności?-- 14 gru 2015, o 10:21 --Aktualizacja o to, jak definiujemy w tym problemie macierz wstęgową.
W problemie, który rozpatruję, nieformalna definicja macierzy wstęgowej to:
Macierz, która ma \(\displaystyle{ w}\) niezerowych diagonalnych poniżej, jak również powyżej głównej diagonalnej.
W zapisie formalnym taka macierz to \(\displaystyle{ B _{nxn} =( b_{ij} )}\), gdzie \(\displaystyle{ b _{ij} =0}\) dla \(\displaystyle{ \left| i-j \right| > w}\).