Rozwiązujemy układ równań


[Komentarz LeMUra]
[Komentarz Kaczusia]


Sądzę, że jak napisać program obliczający układ dwu równań liniowych z dwiema niewiadomymi to przynajmniej dla większości z was jest wiadomym, przedstawić to w sposób zrozumiały dla osób potrafiących rozwiązywać układy równań jedynie metodami: podstawiania i przeciwnych współczynników. Dlatego wybrałem do opisania w powyższym artykule metodę Gausa.

Metoda ta opisana jest prawie w każdej książce do metod numerycznych [Metoda eliminacji Gaussa użyta do przy rozwiązywaniu układów równań wykożystywana jest dość często w obliczeniach numerycznych], lecz mimo, iż jest to naprawdę metoda bardzo prosta, spotkałem się już z programami obliczającymi tą metodą, lecz ze smutkiem muszę stwierdzić, że większość z nich nie działała poprawnie.

Ale nie pora o tym mówić. Przedstawię więc metodę.
Mamy układ równań typu:


a11x1+a12x2+a13x3+...=b1
a21x1+a22x2+a23x3+...=b2
       ...
an1x1+an2x2+an3x3+...=bn

gdzie aij oznaczają współczynniki stojące przy j-tej niewiadomej w i-tym równaniu, natomiast bi oznacza tzw "wyraz wolny" i-tego równania, czyli liczba, przy której nie stoi żadna niewiadoma.

Czy przypominacie sobie metodę przeciwnych współczynników? Mam nadzieję, że tak. Lecz tak czy inaczej przypomnijmy sobie na czym ona polegała:
jedno z równań mnożyliśmy obustronnie przez pewną stałą różną od zera, tak oby po dodaniu stronami obu równań otrzymać równanie z jedną niewiadomą, z rozwiązaniem którego zazwyczaj nie mieliśmy kłopotów. Otóż mimo, że omawiamy teraz układ większej ilości równań z większą ilością niewiadomych to możemy sprowadzić ją do podobnego przypadku (po prostu człowiek - szczególnie matematyk lubi sprowadzać wszystko do poznanych wcześniej przypadków, a następnie stara się zautomatyzować tą operację). Żeby dodatkowo zautomatyzować tą operację to postaramy się robić to według pewnego klucza. Będzie to jak mi się wydaje najprostrzy z możliwych kluczy: weźmy pod uwagę najpierw pierwsze równanie mnożąc je przez pewną liczbę (o której za chwilę) doprowadźmy je do takiej postaci, że po dodaniu do następnego równania zredukuje nam się pierwsza ze zmiennych, mnożymy to pierwsze z równań przez kolejne liczby i redukujemy pierwszy wyraz w kolejnych równaniach. Uzyskujemy wtedy układ równań o stopień mniejszy - trochę zawiłe co? Lecz zaraz postaram się to wytłumaczyć na przykładzie:


Weźmy pod uwagę układ równań:
 
         x +  y + z = 6
         x + 2y + z = 8
        2x +  y - z = 1
 
Postępując jak wspomniałem wcześniej mnożymy pierwsze równanie raz przez -1,a następnie dodajemy stronami raz do pierwszego, potem mnożymy przez -2 i dodaemy do drugiego z równań. Dzięki takim działaniom otrzymujemy układ :
 
         x + y +  z = 6  
             y      = 2  
            -y - 3z = -11  
   
Oczywiście my moglibyśmy już powiedzieć, że y=2, lecz maszyna jest na tyle mało inteligentna, że raczej na to nie wpadnie. Więc łatwo zauważyć, że jeżeli na razie pominiemy pierwsze z równań, otrzymamy układ 2 równań z dwiema niewiadomymi, i tu postępujemy analogicznie, jak wcześniej do układu trzech równań, czyli próbujemy pozbyć się kolejnego z równań, otrzymujemy wtedy układ:
 
         x +  y +  z = 6
              y      = 2
                 -3z = -9
 
Łatwo zauważyć, że przekształcając powyższe równania do postaci:
 
         x = 6 - y - z
         y = 2
       -3z = -9
  
możemy już bez problemów wyliczyć najpierw z, znając z wyliczamy y, a następnie x.

Dobrze, ale zapytacie teraz jak to się ma do komputera? Otóż na komputerze bez większych przeszkód możemy wykonać identyczne operacje. Po prostu najpierw musimy pobrać dane, czyli współczynniki przy kolejnych zmiennych powiedzmy, że wprowadzimy je do tablicy A (ponieważ podobnież nie wskazane jest używanie w C tablic dwuwymiarowych, to użyjmy tablicy jednowymiarowej o wielkości n*n, gdzie n - to ilość równań [w C++ obecnie często używa sie obiektu vector, bądź też można stworzyć własną klasę typu macierz]). Żeby nie było problemów ze zrozumieniem to

A[i*n+j] = A[i][j] = A [i,j]

oznacza to j-ty element i-tego wiersza tablicy A. "Wyrazy wolne", czyli to co stoi bez niewiadomej po drugiej stronie każdego z równań, zapiszemy w tablicy B (tablica B jest n-wymiarowa), gdzie B[i] oznacza wyraz wolny i-tego równania. Teraz rozpatrując po kolei równania -bieżemy element A[i,i] dzieląc przez ten wyraz. Troszkę namieszałem co? ale sprawdźcie na przykładzie analizując ten algorytm...


Dobrze, a teraz weźcie taki przykład:

           z = 0
           x = 1
           y = 2
  
co? Wydawało by się, iż rozwiązanie mamy podane na tacy, ale komputer -głupia maszyna i tak będzie się starała rozwiązać ten problem według starego algorytmu, i co? -dzielenie przez zero? Zgadza się! Pierwszy pomysł jaki nam się nasuwa, to przewidzenie takiego zagrania i wypisanie informacji "czemu wpisujesz gamoniu rozwiązany już układ", lecz jednak takie postępowanie wykluczy tylko powyższy przypadek, a co z takim:

            y + z = 2
        x + y     = 3
        x +     z = 1
 
Taki układ napewno ma rozwiązanie, a tu też jest dzielenie przez zero. Część programistów obchodzi ten problem w ten sposób, iż piszą, że układ taki nie ma rozwiązań (aczkolwiek jest on dopiero podejrzany o ich brak!), a nie zawsze jest to prawda. Co w takim wypadku zrobić? Są dwa rozwiązania:
  1. zamienić kolejnością kolumny (tzn niech pierwszy będzie np. y)
    
            y +     z = 2
            y + x     = 3
                x + z = 1
     
  2. zamienić rzędy
    
            x + y     = 3
                y + z = 2
            x +     z = 1
     

Oba te rozwiązania są tak samo dobre (trudniejszy do zakodowania jest ten pierwszy, dlatego też przykładowy program jest zakodowany wg. tego algorytmu).Jak wybrać odpowiednią kolumnę do zamiany? -szukamy pierwszego niezerowego znaku danego wiersza i z nim zamieniamy [W praktyce stosuje się metodę szukania wyrazu o największej wartości bezwzględnej]. Jeżeli takowego nie znajdziemy (wyzerują nam się wszystkie współczynniki stojące przy zmiennych), oznacza to, iż układ ten ma albo nieskończenie wiele rozwiązań, lub nie posiada ich wcale[W praktyce, jeśli korzystamy z liczb typu double, tudzież float, należy wziąść poprawkę, na to iż za wyraz zerowy powinniśmy przyjąć liczbę o bardzo małej wartości bezwzględnej].Do artykułu dołączony jest mały program przykładowy.

Na tym kończe, życząc przyjemnej zabawy

Kaczuś


Powrót do Menu