[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:
x + y + z = 6 x + 2y + z = 8 2x + y - z = 1Postę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 = -11Oczywiś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 = -9moż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
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...
z = 0 x = 1 y = 2co? 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 = 1Taki 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:
y + z = 2 y + x = 3 x + z = 1
x + y = 3 y + z = 2 x + z = 1
Kaczuś