układy równań metodą Gaussa- zadania z Rutkowskiego

Przestrzenie wektorowe, bazy, liniowa niezależność, macierze.... Formy kwadratowe, twierdzenia o klasyfikacji...
july04
Użytkownik
Użytkownik
Posty: 94
Rejestracja: 18 cze 2018, o 21:12
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 12 razy
Pomógł: 1 raz

układy równań metodą Gaussa- zadania z Rutkowskiego

Post autor: july04 »

Zadanie jest z podręcznika Rutkowskiego- uczę się samodzielnie i nie umiem znaleźć sposobu rozwiązania niektórych układów równań (innych zadań), np:

Rozwiązać układ równań z ciała \(\displaystyle{ \mathbb{Z}_{5}}\)
\(\displaystyle{ \begin{cases} x_{1}+2x_{2}+3x_{3}=1\\2x_{1}+x_{2}+x_{3}=0\\4x_{1}+3x_{2}+x_{3}=3 \end{cases} }\)

Nie rozumiem zapisu ciało \(\displaystyle{ \mathbb{Z}_{5}}\) Tzn. wiem, że chodzi o zbór 5 elementowy od zera do \(\displaystyle{ n-5}\), mimo to nie potrafię tego rozwiązać.

Ponadto mam pytanie dla osób z tym podręcznikiem zaznajomionych.

Długie minuty spędziłem nad rozwiązaniem poniższego układu. Dałem za wygraną i dopiero kalkulator w internecie pokazuje trudne dla mnie do dostrzeżenia postępowanie.

\(\displaystyle{ \begin{cases} 4x_{1}-9x_{2}+6x_{3}=5\\3x_{1}-4x_{2}+2x_{3}=2\\7x_{1}-2x_{2}-2x_{3}=1 \end{cases} }\)

Wg kalkulatora powinienem od równania 2 odjąć równanie pierwsze pomnożone przez \(\displaystyle{ 3/4}\)
I tak wtedy faktycznie wszystko wychodzi.
Czy większość zadań jest tak skonstruowana w tym podręczniku, że pojawiają się mnożenia przez ułamki, bo utknąłem na dużej ilości zadań.

Pozdrawiam
Łukasz
Ostatnio zmieniony 28 lut 2020, o 20:54 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: układy równań metodą Gaussa- zadania z Rutkowskiego

Post autor: Premislav »

Jest taki szkodnik (szybko się mnoży, szczególnie należy nań uważać, jeśli ma się w domu wylot szybu wentylacyjnego), który nazywa się Gauss i urodził się w 1777 roku. W celu jego zwalczania powstała słynna metoda eliminacji Gaussa. Zazwyczaj pomaga ona rozwiązać takie zadania.
\(\displaystyle{ \ZZ_{5}}\) to \(\displaystyle{ \left\{0,1,2,3,4\right\}}\) z działaniami dodawania modulo \(\displaystyle{ 4}\) i mnożenia modulo \(\displaystyle{ 4}\) (czyli normalnie dodajesz/mnożysz te liczby jak rzeczywiste, a potem bierzesz resztę z dzielenia przez \(\displaystyle{ 4}\) otrzymanej liczby).

Pokażę na przykładzie pierwszego zadania, jak stosować tę metodę:
\(\displaystyle{ \begin{cases}x_{1}+2x_{2}+3x_{3}=1\\2x_{1}+x_{2}+x_{3}=0\\4x_{1}+3x_{2}+x_{3}=3 \end{cases}}\)
W lewym górnym rogu mamy jedynkę przy \(\displaystyle{ x_{1}}\), więc wygodnie będzie użyć krotności pierwszego wiersza w celu wyrugowania \(\displaystyle{ x_{1}}\) z dwóch pozostałych równań.
Od drugiego równania, w którym występuje \(\displaystyle{ 2x_{1}}\), odejmujemy stronami pierwsze równanie pomnożone przez \(\displaystyle{ 2}\). Od trzeciego równania, w którym występuje \(\displaystyle{ 4x_{1}}\), odejmujemy stronami pierwsze równanie pomnożone przez \(\displaystyle{ 4}\). To daje nam:
\(\displaystyle{ \begin{cases}x_{1}+2x_{2}+3x_{3}=1\\-3x_{2}-5x_{3}=-2\\-5x_{2}-11x_{3}=-1 \end{cases}}\)
Jednakowoż jesteśmy w \(\displaystyle{ \ZZ_{5}}\), więc zastępujemy te współczynniki (dotąd eliminację wykonałem normalnie jak w rzeczywistych) ich resztami z dzielenia przez \(\displaystyle{ 5}\). W ten sposób otrzymujemy:
\(\displaystyle{ \begin{cases}x_{1}+2x_{2}+3x_{3}=1\\2x_{2}=3\\4x_{3}=4 \end{cases}}\)
Jest całkiem elegancko, chcielibyśmy jednak mieć też w drugim równaniu jako wiodący współczynnik jedynkę, mnożymy więc stronami przez takie \(\displaystyle{ x\in\left\{0,1,2,3,4\right\}}\), że \(\displaystyle{ 2x\equiv 1\pmod{5}}\), czyli przez element odwrotny do \(\displaystyle{ 2}\) w \(\displaystyle{ \ZZ_{5}}\). To zawsze można znaleźć z rozszerzonego algorytmu Euklidesa (

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Algorytm_Euklidesa#Rozszerzony_algorytm_Euklidesa
), ale tutaj prościej podstawić na pałę wszystkie możliwości, bo jest ich tylko \(\displaystyle{ 4}\) (zero nie ma elementu odwrotnego), co da nam \(\displaystyle{ x=3}\).
Czyli mnożymy drugie równanie układu
\(\displaystyle{ \begin{cases}x_{1}+2x_{2}+3x_{3}=1\\2x_{2}=3\\4x_{3}=4 \end{cases}}\)
stronami przez \(\displaystyle{ 3}\) i znów redukujemy modulo \(\displaystyle{ 5}\), otrzymując
\(\displaystyle{ \begin{cases}x_{1}+2x_{2}+3x_{3}=1\\x_{2}=4\\4x_{3}=4 \end{cases}}\)
Znajdujemy teraz element odwrotny do \(\displaystyle{ 4}\) w \(\displaystyle{ \ZZ_{5}}\), znów można podstawiać na pałę, tym elementem jest \(\displaystyle{ 4}\), gdyż \(\displaystyle{ 4\cdot 4\equiv 1\pmod{5}}\), mnożymy ostatnie równanie stronami przez \(\displaystyle{ 4}\), redukujemy modulo \(\displaystyle{ 5}\) i mamy
\(\displaystyle{ \begin{cases}x_{1}+2x_{2}+3x_{3}=1\\x_{2}=4\\x_{3}=1 \end{cases}}\)
Podstawiamy teraz do pierwszego równania z drugiego i trzeciego \(\displaystyle{ x_{2}=4, \ x_{3}=1}\), co daje nam
\(\displaystyle{ \begin{cases}x_{1}+11=1\\x_{2}=4\\x_{3}=4 \end{cases}}\)
ale \(\displaystyle{ 11\equiv 1\pmod{5}}\), więc nad \(\displaystyle{ \ZZ_{5}}\) to się redukuje do
\(\displaystyle{ \begin{cases}x_{1}=0\\x_{2}=4\\x_{3}=1\end{cases}}\)
Ostatnio zmieniony 28 lut 2020, o 21:48 przez Premislav, łącznie zmieniany 1 raz.
Jan Kraszewski
Administrator
Administrator
Posty: 34129
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: układy równań metodą Gaussa- zadania z Rutkowskiego

Post autor: Jan Kraszewski »

Premislav pisze: 28 lut 2020, o 21:40\(\displaystyle{ \ZZ_{5}}\) to \(\displaystyle{ \left\{0,1,2,3,4\right\}}\) z działaniami dodawania modulo \(\displaystyle{ 4}\) i mnożenia modulo \(\displaystyle{ 4}\) (czyli normalnie dodajesz/mnożysz te liczby jak rzeczywiste, a potem bierzesz resztę z dzielenia przez \(\displaystyle{ 4}\) otrzymanej liczby).
Zawsze byłem przekonany, że w \(\displaystyle{ \ZZ_{5}}\) to modulo \(\displaystyle{ 5}\)...

JK
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: układy równań metodą Gaussa- zadania z Rutkowskiego

Post autor: Premislav »

Cóż, chęci miałem dobre, ale to nie jest mój dzień, już drugi raz idiotyczny błąd, jeszcze głupszy niż z \(\displaystyle{ \cos 0}\)
Miałem też istotniejszy błąd, obliczeniowy, ale do tego Pan się nie odniósł, więc raczej poprawa nie stanowiła naruszenia regulaminu.
Jan Kraszewski
Administrator
Administrator
Posty: 34129
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: układy równań metodą Gaussa- zadania z Rutkowskiego

Post autor: Jan Kraszewski »

Premislav pisze: 28 lut 2020, o 21:50Miałem też istotniejszy błąd, obliczeniowy, ale do tego Pan się nie odniósł,
Bo nie czytałem rachunków, a to rzucało się w oczy.
Premislav pisze: 28 lut 2020, o 21:50więc raczej poprawa nie stanowiła naruszenia regulaminu.
Nie stanowiła, choć dobrym zwyczajem jest dodanie krótkiej notki na temat tego, co się edytowało.

JK
july04
Użytkownik
Użytkownik
Posty: 94
Rejestracja: 18 cze 2018, o 21:12
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 12 razy
Pomógł: 1 raz

Re: układy równań metodą Gaussa- zadania z Rutkowskiego

Post autor: july04 »

Dziękuje bardzo za pomoc.
a4karo
Użytkownik
Użytkownik
Posty: 22174
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: układy równań metodą Gaussa- zadania z Rutkowskiego

Post autor: a4karo »

Inna rzecz to zapis. W `\ZZ_5` nie ma 9,6,7...
ODPOWIEDZ