Autor Wątek: Algorytm Gaussa-Jordana i zerowe elementy macierzy  (Przeczytany 1947 razy)

Offline hashedone

  • Użytkownik

# Wrzesień 03, 2010, 07:51:31
Witam, mam niewielki problem z implementacją algorytmu Gaussa-Jordana do odwracania macierzy, konkretnie z ustawieniem wierszy macierzy przed zastosowaniem algorytmu. Weźmy sobie na przykład macierz:
1 4 6
2 0 7
3 5 8
Aby w tym przypadku zastosować algorytm G-J, muszę na początek zamienić wiersz drugi z pierwszym lub trzecim (i odpowiednio te same wiersze w "doklejanej" macierzy jednostkowej). Przypadek dość trywialny, ale wystarczy spojrzeć na macierz:
0 0 2
1 0 0
0 3 0
Widać, że wiersze tej macierzy trzeba ułożyć już tylko na jeden konkretny sposób. No i właśnie chodzi o to, jak szybko pozamieniać wiersze tak, żeby elementy na głównej przekątnej były niezerowe (oczywiście jeśli to możliwe - muszę także wyłapać sytuacje kiedy się nie da i zgłosić błąd). W macierzach 3x3 sobie poradziłem dość łatwo - sprawdzam wszystkie 6 permutacji wierszy, aż któraś będzie poprawna. Tyle że dla macierzy 4x4 tych permutacji będzie już 24, a może się zdarzyć że tylko jedna będzie poprawna... Czy macie pomysł, jak szybko przystosować macierz do algorytmu G-J?

Pozdrawiam.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Avaj

  • Użytkownik

# Wrzesień 03, 2010, 08:50:33
a nie możesz tak?
1 4 6
2 0 7
3 5 8
W2 = W2 / 2*W1
W3 = W3 / 3*W1

1 4      6
0 0      7/12
0 5/12  8/18

teraz mamy 0 na przekątnej, to zamieniamy wiersz z niższymi niezerowymi w tej kolumnie, zamieniamy W2 i W3

1 4      6
0 5/12 8/18
0 0      7/12

teraz dzielimy W1 przez tyle ile trzeba i potem trzecia kolumna bez problemu

Offline hashedone

  • Użytkownik

# Wrzesień 03, 2010, 12:05:54
Wiesz no, na kartce bez problemu:P Jak się na kartce ma skilla, to można w ogóle nie pamiętać G-J, a sprowadzenie do macierzy jednostkowej jest na prawdę szybkie. Problem w tym, że ja to chcę zaimplementować w C++ i tu nie jest tak łatwo wszystko dedukować (w każdym razie nie mam pomysłu jak to zrobić:P).

Offline albireo

  • Użytkownik

# Wrzesień 03, 2010, 12:28:05
Ale dlaczego chcesz przestawiać wiersze przed, a nie w trakcie, powinno wystarczyć przestawianie wierszy dopiero w momencie jak natrafisz na zero w pozycji którą rozpatrujesz, poza tym przestawianie przed nie gwarantuje ci że po drodze nie trafisz i tak na zero.

Offline hashedone

  • Użytkownik

# Wrzesień 03, 2010, 14:15:38
Bo może się okazać, że będę musiał zamienić z którymś z wcześniejszych wierszy, który ma już jedynkę na swojej pozycji... Poza tym właśnie chodzi o to, że jeśli nie mogę przestawić tak wierszy, żeby sobie zagwarantować brak zera na przekątnej, to znaczy że macierz ma wyznacznik zerowy, nie ma więc macierzy odwrotnej... w tej sytuacji zgłaszam błąd.

Pozdrawiam

Offline albireo

  • Użytkownik

# Wrzesień 03, 2010, 14:35:40
Nie będziesz musiał (a właściwie nie będziesz mógł), bo przy tej metodzie nie będziesz miał niżej wierszy z niezerowymi wartościami we wcześniejszych kolumnach.
Tak dla pewności, to domyślam się, że chodzi ci o http://pl.wikipedia.org/wiki/Metoda_Gaussa

Offline DoomsdayNow

  • Użytkownik

# Wrzesień 03, 2010, 14:50:09
hashedone: sprawa jest prosta - ponieważ wyznacznik macierzy górnotrójkątnej jest równy iloczynowi wartości z głównej przekątnej, jeśli macierz jest odwracalna, to tak czy owak będziesz w stanie ustawić wiersze w odpowiedni sposób (w locie). Gdybyś nie mógł tego uczynić, oznaczałoby to po prostu, że wyznacznik jest równy zero i macierz nie jest odwracalna. Operacje elementarne, jak pewnie wiesz, nie wpływają na rząd macierzy.

Offline Knopi

  • Użytkownik

# Wrzesień 03, 2010, 15:32:21
Ale to czy rząd macierzy jest równy liczbie wierszy wyjdzie w praniu podczas tego algorytmu.
Ja nie wiem o czym jest ta dyskusja. Wiele przykładów w sieci, na googlach i w książkach . Chyba, że znowu trzeba próbować to zrobić bez dzielenia ; o


Znajdujesz pierwszy wiersz , który jest niezerowy w danej kolumnie ( albo na odwrót wedle uznania :) ) wykonujesz odpowiednie operacje elementarne i przechodzisz do kolejnej kolumny( wiersza).

Das ist alles.

Ewentualnie nie przedstawiłeś tego co jest problemem dość jasno albo ja tego nie zrozumiałem.

Offline hashedone

  • Użytkownik

# Wrzesień 03, 2010, 22:00:39
hmmm.... Właśnie szukając kontrprzykładu udowodniłem sobie (i to wprost!) że moje pytanie jest bez sensu, bo postulowany przeze mnie przypadek nie może mieć miejsca:) Jaki to człowiek potrafi być naiwny... W każdym razie dzięki za pomoc w uświadomieniu sobie błędu:)

Pozdrawiam