transpozycja Mariusz: Czy macierzy A^TA jest symetryczna i dodatnio określona Czy mnożąc równanie macierzowe Ax=B lewostronnie przez macierz transponowaną unikniemy częściowego wyboru elementu podstawowego

g: A^TA = A^TA x^T(A^TA)x = (Ax)^T(Ax) ≥ 0 więc A^TA jest symetryczna i dodatnio określona.

g: poprawka: (A^TA)^T = A^TA

Mariusz: Oczywiście zakładamy że A jest kwadratowa i nieosobliwa (wyznacznik różny od zera) A czy to prawda że dla takiej macierzy nie jest konieczny wybór elementu podstawowego ? (Wybór elementu podstawowego następuje wtedy gdy w eliminacji szukamy w kolumnie elementu największego co do wartości bezwzględnej i zamieniamy wiersze) Przypuśćmy że mamy układ równań w postaci macierzowej Ax=B W jaki sposób przekształcić ten układ równań aby mieć układ równań z macierzą silnie diagonalnie dominującą

Pytający: Zgaduję, że czytałeś: http://wazniak.mimuw.edu.pl/index.php?title=MN05 "Dla niektórych ważnych klas macierzy wiadomo, że rozkład LU jest wykonalny bez wyznaczania elementu głównego, co istotnie może zmniejszyć całkowity czas działania algorytmu. Jest tak m.in. dla macierzy: • symetrycznych, dodatnio określonych • silnie diagonalnie dominujących" Zatem, jeśli A jest nieosobliwa, dla równania: A^TAx=A^Tb, rozkład LU wykonasz bez konieczności wyboru elementu głównego.

Mariusz: Z grubsza to przeczytałem i kiedyś nawet napisałem kod Pascalowy na podstawie ich pseudokodu No tak ale jak to pokazać (to że nie trzeba dokonywać wyboru elementu głównego) W sumie mnożenie przez macierz transponowaną zwiększy nam złożoność pamięciową co nie gra roli przy odwracaniu macierzy Mnożenie przez macierz transponowaną zwiększy nam złożoność czasową ale jest łatwiejsze do zapisania w języku programowania Przy odwracaniu macierzy metodą eliminacji Gaussa na wejściu mamy daną macierz blokową A | I i chcemy uzyskać macierz blokową I I A⁻¹ Można by na wejściu podać macierz A^TA | A^T i jeśli udałoby się pokazać że to co na ważniaku piszą jest prawdą to można byłoby uniknąć wyboru elementu głównego

Mariusz: Przydałaby się edycja wpisów Pomnożenie lewostronne przez transpozycję macierzy spowoduje że rozkład Choleskiego będzie wykonalny jednak rozkład LU jest preferowany bo nie używa pierwiastków

Mariusz: @ Pytający czytałeś ten artykuł na ważniaku do którego dałeś odnośnik ? Jeśli czytałeś to powinieneś zauważyć że mają tam kilka drobnych błędów w pseudokodzie Poza tym według mnie ich artykuł jest niedokończony Pomijając te kilka drobnych błędów ich pseudokod jest czytelny i łatwo napisać na jego podstawie kod w ulubionym języku programowania

Pytający: Czytałem. Aha. Aha. Aha.

Mariusz: I co nie znalazłeś błędów lub braków w ich pseudokodzie ? Wg mnie jest ich kilka Pewnie czytałeś tak samo jak kod kulek który jakiś czas temu umieściłem do dokończenia

Mariusz: 1. Czy aby na pewno dobrze obliczają elementy macierzy L ? 2. Czy na pewno dobrze zapamiętują pozycje jedynek w macierzy permutacji ? 3. Co z permutacją wektora wyrazów wolnych Nie brakuje ci jej u nich ? https://www.geeksforgeeks.org/reorder-a-array-according-to-given-indexes/ Jeśli chodzi o pierwszy sposób to wolałbym nie używać dodatkowej tablicy zresztą na ten pomysł już sam wpadłem Jeśli chodzi o drugi sposób to wolałbym nie modyfikować tablicy indeksów bo później może być potrzebna W Pascalu ten ich drugi pomysł może jakoś by przeszedł bo parametry w nagłówku funkcji bądź procedury mogą być poprzedzone słówkiem var , const albo mogą występować bez żadnego z nich W twoim ulubionym C tablica jest wskaźnikiem i te ich pomysły nie przejdą Jeżeli chodzi o permutację wektora wyrazów wolnych to bez dodatkowej pamięci nie może trwać dłużej niż O(n²)

Pytający: 1. Tak. 2. Tak. 3. Nie brakuje, przecież ten pseudokod znajduje rozkład PA=LU. Jedynie trzeba wciąż pod uwagę, że w pseudokodzie P oznacza wektor (bo wystarczy zapamiętać permutację jako wektor), a nie macierz, ale jest to wspomniane. Wtedy rozwiązując już równanie Ly=Pb, w pseudokodzie w stylu C (ponoć moim ulubionym) wartość (Pb)_k możesz uzyskać w ten sposób: b[ P[k] ]; Toteż wektora wyrazów wolnych b w ogóle nie musisz permutować, bo do odpowiednich wartości wektora Pb masz dostęp w czasie stałym. Tymczasem milknę, gdyż wystarczy mi tych insynuacji.

Mariusz: Insynuacji ... to mnie rozbawiłeś Co nie jest twoim ulubionym A kto szczekał na Pascala ? Odpowiadając na postawione przeze mnie pytania pokazałeś że nie czytasz treści do których dajesz odnośniki Przekręcasz też zdania z moich wpisów Zatem gdzie masz te insynuacje ? Próbowałem napisać procedurę rozwiązującą te układy z macierzami trójkątnymi bez permutowania wyrazów wolnych odwołując się do elementów w wyżej pokazany sposób ale otrzymywałem błędne wyniki Ciekawe po co dali adres do marudzenia skoro nie reagują na to marudzenie Gdyby przepisać dosłownie ten ich pseudokod na kod w języku programowania to mielibyśmy błędy , np dzielenie przez zero itp a jeśli nawet program by się zatrzymał to zwróciłby błędny wynik Skoro nie czytałeś tego co na tym ważniaku napisali to tym bardziej nie przepisałeś ich pseudokodu na język programowania Jakiś czas temu działający kod rozkładu LU=PA można było ściągnąć razem z książką po angelsku (dali go w niej jako przykład czyli po waszemu gotowiec)