Rozwiązywanie układów równań metodą eliminacji Gaussa

Stronę tą wyświetlono już: 2067 razy

Rozwiązywanie układów równań liniowych możliwe jest poprzez zastosowanie metody eliminacji Gaussa. Metoda ta sprowadza macierz danego układu równań do macierzy jednostkowej lub macierzy trójkątnej z jednoczesnym wyznaczeniem wartości niewiadomych x1, x2, ... , xn.

Z współczynników stojących przy niewiadomych oraz wyrazów wolnych należy utworzyć macierz:

gdzie:

  • a1,1, ... , an,n - odpowiadają współczynnikom stojącym przy niewiadomych x1, x2, ... , xn;
  • a1, n+1, a2, n+1, ... , an,n+1 - odpowiadają wyrazom wolnym z układu równań [1].

Przekształcenie powyższej macierzy do macierzy trójkątnej górnej odbywa się etapowo w dwóch krokach, które realizowane są dla wartości i zmieniającej się od 1 do n:

  1. Podzielić i-ty wiersz macierzy przez odwrotność jej argumentu ai,i w następujący sposób:

    Przykład dla i=1:

  2. Dla każdego wiersza o indeksie k takim że i<kn odjąć otrzymany wiersz Wi' przemnożony przez argument ai,k:

    Przykład dla k= 2, ... , n:

    Aby zredukować do zera argumenty macierzy znajdujące się nad przekątną główną należy operację odejmowania przeprowadzić dla k∈{1, 2, ..., n}{i}.

Macierz powstała w wyniku jednokrotnego wykonania kroków 1, 2 stanowi dane wejściowe dla następnego cyklu. W początkowej fazie, dla i=1 dane wejściowe stanowi macierz [2].

Po przeprowadzeniu wszystkich etapów dla i=1, 2, ... , n otrzymana zostanie następująca macierz trójkątna górna:

gdzie:

  • bi,j - argumenty macierzy otrzymane po przeprowadzeniu metody eliminacji Gaussa na macierzy [2]

Wartość niewiadomej xn układu równań [1] po przeprowadzeniu metody eliminacji Gaussa jest równa:

natomiast kolejne niewiadome o indeksach i=n-1, n-2, ... , 1 obliczyć można za pomocą następującego wzoru:

Przykład

Rozwiązać metodą eliminacji Gaussa do postaci macierzy trójkątnej górnej następujący układ równań:

Zacząć należy od utworzenia macierzy:

Etap pierwszy dla i = 1

Krok pierwszy - podzielenie pierwszego wiersza przez a1,1

Krok drugi - odjęcie od wierszy 2, 3, 4 wiersza pierwszego pomnożonego odpowiednio przez współczynniki a2,1, a3,1, a4,1.

Ponieważ argument a2,2 uzyskanej macierzy jest równy 0, konieczna jest zamiana miejscami wiersza drugiego z trzecim w następujący sposób:

Etap drugi dla i=2

Krok pierwszy - podzielenie drugiego wiersza przez a2,2

Krok drugi - odjęcie od wierszy 3, 4 wiersza drugiego pomnożonego odpowiednio przez współczynniki a3,2, a4,2, jednakże wiersz trzeci można pominąć, ponieważ argument a3,2=0.

Etap trzeci dla i=3

Krok pierwszy - podzielenie wiersza trzeciego przez argument a3,3

Krok drugi - odjęcie od wiesza czwartego wiersza trzeciego pomnożonego przez współczynnik a4,3.

Etap czwarty dla i=4

Krok pierwszy - podzielenie wiersza czwartego przez argument a4,4

Kroku drugiego nie ma i nie będzie, ponieważ brak jest wierszy do przeliczenia.

Według wzoru [6] niewiadoma x4 jest równa:

Pozostałe niewiadome można obliczyć według wzoru [7].

Można zredukować do zera argumenty macierzy znajdujące nad przekątną główną macierzy uzyskanej w kroku czwartym za pomocą trzech etapów otrzymując w ten sposób w ostatniej kolumnie wartości niewiadomych x1, x2, x3, x4.

Etat pierwszy - od wierszy 1, 2, 3 odjąć wiersz czwarty pomnożony odpowiednio przez współczynniki a1,4, a2,4, a3,4.

Etap drugi - od wierszy 1, 2 odjąć wiersz trzeci pomnożony odpowiednio przez współczynniki a1,3, a2,3.

Etap trzeci - od wiersza pierwszego odjąć wiersz drugi pomnożony przez współczynnik a1,2.

Ponieważ swego czasu zrobiłem program, który w przebiegły sposób wykorzystuje metodą eliminacji Gausa do rozwiązywania liniowych układów równań, więc użyję go tutaj do rozwiązania tego samego układu równań podając mu na wejście następujące dane:

Listing 1
  1. 4
  2. 2 4 8 2 10
  3. 1 2 12 56 30
  4. 22 26 4 40 160
  5. 28 32 26 6 10

by program po chwili wypluł na powierzchnię ekranu następujący wynik:

Listing 2
  1. Przeliczanie macierzy do postaci macierzy jednostkowej:
  2. 2 4 8 2 10
  3. 1 2 12 56 30
  4. 22 26 4 40 160
  5. 28 32 26 6 10
  6. Etap 1:
  7. 1 2 4 1 5
  8. 1 2 12 56 30
  9. 22 26 4 40 160
  10. 28 32 26 6 10
  11. 1 2 4 1 5
  12. 0 0 8 55 25
  13. 0 -18 -84 18 50
  14. 0 -24 -86 -22 -130
  15. Etap 2:
  16. a(2, 2)=0 i dlatego muszę posortowac:
  17. 1 2 4 1 5
  18. 0 -24 -86 -22 -130
  19. 0 0 8 55 25
  20. 0 -18 -84 18 50
  21. 1 2 4 1 5
  22. -0 1 3.583333333 0.9166666667 5.416666667
  23. 0 0 8 55 25
  24. 0 -18 -84 18 50
  25. 1 0 -3.166666667 -0.8333333333 -5.833333333
  26. -0 1 3.583333333 0.9166666667 5.416666667
  27. 0 0 8 55 25
  28. 0 0 -19.5 34.5 147.5
  29. Etap 3:
  30. 1 0 -3.166666667 -0.8333333333 -5.833333333
  31. -0 1 3.583333333 0.9166666667 5.416666667
  32. 0 0 1 6.875 3.125
  33. 0 0 -19.5 34.5 147.5
  34. 1 0 0 20.9375 4.0625
  35. -0 1 0 -23.71875 -5.78125
  36. 0 0 1 6.875 3.125
  37. 0 0 0 168.5625 208.4375
  38. Etap 4:
  39. 1 0 0 20.9375 4.0625
  40. -0 1 0 -23.71875 -5.78125
  41. 0 0 1 6.875 3.125
  42. 0 0 0 1 1.23655914
  43. 1 0 0 0 -21.82795699
  44. 0 1 0 0 23.5483871
  45. 0 0 1 0 -5.376344086
  46. 0 0 0 1 1.23655914

Jak widać powyżej, program nie tylko rozwiązuje ale i rozpisuje kolejne etapy.

Przykład do samodzielnego rozwiązania:

Odpowiedź:

Załączniki:

Napisany przeze mnie program RownaniaLiniowe

Komentarze