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

Stronę tą wyświetlono już: 510 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:

    egin{bmatrix}
1 & cfrac{a_{1,2}}{a_{1,1}} & cdots & cfrac{a_{1,n}}{a_{1,1}} & cfrac{a_{1,n+1}}{a_{1,1}} 
a_{2,1} & a_{2,2} & cdots & a_{2,n} & a_{2,n+1} 
vdots & vdots & ddots & vdots & vdots  
a_{n,1} & a_{n,2} & cdots & a_{n,n} & a_{n,n+1}
end{bmatrix}

  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:

    egin{bmatrix}
1 & cfrac{a_{1,2}}{a_{1,1}} & cdots & cfrac{a_{1,n}}{a_{1,1}} & cfrac{a_{1,n+1}}{a_{1,1}} 
0 & a_{2,2}-cfrac{a_{1,2}}{a_{1,1}}cdot a_{2,1} & cdots & a_{2,n}-cfrac{a_{1,n}}{a_{1,1}}cdot a_{2,n} & a_{2,n+1}-cfrac{a_{1,n+1}}{a_{1,1}}cdot a_{2,n+1} 
vdots & vdots & ddots & vdots & vdots  
0 & a_{n,2}-cfrac{a_{1,2}}{a_{1,1}}cdot a_{n,1} & cdots & a_{n,n}-cfrac{a_{1,2}}{a_{1,1}}cdot a_{n,n} & a_{n,n+1}-cfrac{a_{1,2}}{a_{1,1}}cdot a_{n,n+1}
end{bmatrix}

    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ń:

egin{cases}
 2cdot x_1+4cdot x_2 +8cdot x_3+2cdot x_4=10  
 x_1+2cdot x_2 +12cdot x_3+56cdot x_4=30  
 22cdot x_1+26cdot x_2 +4cdot x_3+40cdot x_4=160  
 28cdot x_1+32cdot x_2 +26cdot x_3+6cdot x_4=10
end{cases}

Zacząć należy od utworzenia macierzy:

egin{bmatrix}
 2 & 4 & 8 & 2 & 10  
 1 & 2 & 12 & 56 & 30  
 22 & 26 & 4 & 40 & 160  
 28 & 32 & 26 & 6 & 10
end{bmatrix}

Etap pierwszy dla i = 1

Krok pierwszy - podzielenie pierwszego wiersza przez a1,1


egin{bmatrix}
 cfrac{2}{2} & cfrac{4}{2} & cfrac{8}{2} & cfrac{2}{2} & cfrac{10}{2}  
 1 & 2 & 12 & 56 & 30  
 22 & 26 & 4 & 40 & 160  
 28 & 32 & 26 & 6 & 10
end{bmatrix}=egin{bmatrix}
 1 & 2 & 4 & 1 & 5  
 1 & 2 & 12 & 56 & 30  
 22 & 26 & 4 & 40 & 160  
 28 & 32 & 26 & 6 & 10
end{bmatrix}

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


egin{bmatrix}
 1 & 2 & 4 & 1 & 5  
 1-1cdot 1 & 2-2cdot 1 & 12-4cdot 1 & 56 - 1cdot 1 & 30-5cdot 1  
 22-1cdot 22 & 26-2cdot 22 & 4-4cdot 22 & 40-1cdot 22 & 160-5cdot 22  
 28-1cdot 28 & 32-2cdot 28 & 26-4cdot 28 & 6-1cdot 28 & 10-5cdot 28
end{bmatrix}=egin{bmatrix}
1 & 2 & 4 & 1 & 5 
0 & 0 & 8 & 55 & 25 
0 & -18 & -84 & 18 & 50 
0 & -24 & -86 & -22 & -130
end{bmatrix}

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

egin{bmatrix}
1 & 2 & 4 & 1 & 5 
0 & -18 & -84 & 18 & 50 
0 & 0 & 8 & 55 & 25 
0 & -24 & -86 & -22 & -130
end{bmatrix}

Etap drugi dla i=2

Krok pierwszy - podzielenie drugiego wiersza przez a2,2

egin{bmatrix}
1 & 2 & 4 & 1 & 5 
cfrac{0}{-18} & cfrac{-18}{-18} & cfrac{-84}{-18} & cfrac{18}{-18} & cfrac{50}{-18} 
0 & 0 & 8 & 55 & 25 
0 & -24 & -86 & -22 & -130
end{bmatrix}=egin{bmatrix}
1 & 2 & 4 & 1 & 5 
0 & 1 & 4cfrac{2}{3} & -1 & -2 cfrac{7}{9} 
0 & 0 & 8 & 55 & 25 
0 & -24 & -86 & -22 & -130
end{bmatrix}

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.

egin{bmatrix}
1 & 2 & 4 & 1 & 5 
0 & 1 & 4cfrac{2}{3} & -1 & -2 cfrac{7}{9} 
0 & 0 & 8 & 55 & 25 
0 & -24-1cdot -24 & -86-4cfrac{2}{3}cdot -24 & -22+1cdot -24 & -130+2cfrac{7}{9}cdot -24
end{bmatrix}=egin{bmatrix}
1 & 2 & 4 & 1 & 5 
0 & 1 & 4cfrac{2}{3} & -1 & -2 cfrac{7}{9} 
0 & 0 & 8 & 55 & 25 
0 & 0 & 26 & -46 & -196cfrac{2}{3}
end{bmatrix}

Etap trzeci dla i=3

Krok pierwszy - podzielenie wiersza trzeciego przez argument a3,3

egin{bmatrix}
1 & 2 & 4 & 1 & 5 
0 & 1 & 4cfrac{2}{3} & -1 & -2 cfrac{7}{9} 
cfrac{0}{8} & cfrac{0}{8} & cfrac{8}{8} & cfrac{55}{8} & cfrac{25}{8} 
0 & 0 & 26 & -46 & -196cfrac{2}{3}
end{bmatrix}=egin{bmatrix}
1 & 2 & 4 & 1 & 5 
0 & 1 & 4cfrac{2}{3} & -1 & -2 cfrac{7}{9} 
0 & 0 & 1 & 6cfrac{7}{8} & 3cfrac{1}{8} 
0 & 0 & 26 & -46 & -196cfrac{2}{3}
end{bmatrix}

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

egin{bmatrix}
1 & 2 & 4 & 1 & 5 
0 & 1 & 4cfrac{2}{3} & -1 & -2 cfrac{7}{9} 
0 & 0 & 1 & 6cfrac{7}{8} & 3cfrac{1}{8} 
0 & 0 & 26-1cdot 26 & -46-6cfrac{7}{8}cdot 26 & -196cfrac{2}{3}-3cfrac{1}{8}cdot 26
end{bmatrix}=egin{bmatrix}
1 & 2 & 4 & 1 & 5 
0 & 1 & 4cfrac{2}{3} & -1 & -2 cfrac{7}{9} 
0 & 0 & 1 & 6cfrac{7}{8} & 3cfrac{1}{8} 
0 & 0 & 0 & -224cfrac{3}{4} & -277cfrac{11}{12}
end{bmatrix}

Etap czwarty dla i=4

Krok pierwszy - podzielenie wiersza czwartego przez argument a4,4

egin{bmatrix}
1 & 2 & 4 & 1 & 5 
0 & 1 & 4cfrac{2}{3} & -1 & -2 cfrac{7}{9} 
0 & 0 & 1 & 6cfrac{7}{8} & 3cfrac{1}{8} 
cfrac{0}{-224cfrac{3}{4}} & cfrac{0}{-224cfrac{3}{4}} & cfrac{0}{-224cfrac{3}{4}} & cfrac{-224cfrac{3}{4}}{-224cfrac{3}{4}} & cfrac{-277cfrac{11}{12}}{-224cfrac{3}{4}}
end{bmatrix}=egin{bmatrix}
1 & 2 & 4 & 1 & 5 
0 & 1 & 4cfrac{2}{3} & -1 & -2 cfrac{7}{9} 
0 & 0 & 1 & 6cfrac{7}{8} & 3cfrac{1}{8} 
0 & 0 & 0 & 1& 1cfrac{22}{93}
end{bmatrix}

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

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

x_4=a_{4,5}=1cfrac{22}{93}

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

x_3=a_{3,5}-a_{3,4}cdot x_4=3frac{1}{8}-6frac{7}{8}cdot 1frac{22}{93}=-5frac{35}{93}

x_2=a_{2,5}-a_{2,4}cdot x_4-a_{2,3}cdot x_3=-2 cfrac{7}{9}+1cdot 1frac{22}{93}-4cfrac{2}{3}cdot -5frac{35}{93}=23frac{17}{31}

x_1=a_{1,5}-a_{1,4}cdot x_4-a_{1,3}cdot x_3-a_{1,2}cdot x_2=5-1cdot 1frac{22}{93}-4cdot -5frac{35}{93}-2cdot23frac{17}{31}=-21frac{77}{93}

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.

egin{bmatrix}
1 & 2 & 4 & 1-1cdot 1 & 5 -1cdot 1cfrac{22}{93} 
0 & 1 & 4cfrac{2}{3} & -1-(-1)cdot 1 & -2 cfrac{7}{9}-(-1)cdot 1cfrac{22}{93} 
0 & 0 & 1 & 6cfrac{7}{8}-6cfrac{7}{8}cdot 1 & 3cfrac{1}{8}-6cfrac{7}{8}cdot 1cfrac{22}{93} 
0 & 0 & 0 & 1& 1cfrac{22}{93}
end{bmatrix}=egin{bmatrix}
1 & 2 & 4 & 0 & 3cfrac{71}{93} 
0 & 1 & 4cfrac{2}{3} & 0 & -1 cfrac{151}{279} 
0 & 0 & 1 & 0 & -5cfrac{35}{93} 
0 & 0 & 0 & 1& 1cfrac{22}{93}
end{bmatrix}

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

egin{bmatrix}
1 & 2 & 4-4cdot 1 & 0 & 3cfrac{71}{93} - 4cdot 1cfrac{22}{93} 
0 & 1 & 4cfrac{2}{3}-4cfrac{2}{3}cdot 1 & 0 & -1 cfrac{151}{279}-4cfrac{2}{3}cdot -5cfrac{35}{93} 
0 & 0 & 1 & 0 & -5cfrac{35}{93} 
0 & 0 & 0 & 1& 1cfrac{22}{93}
end{bmatrix}=egin{bmatrix}
1 & 2 & 0 & 0 & 25cfrac{25}{93} 
0 & 1 & 0 & 0 & 23cfrac{17}{31} 
0 & 0 & 1 & 0 & -5cfrac{35}{93} 
0 & 0 & 0 & 1& 1cfrac{22}{93}
end{bmatrix}

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

egin{bmatrix}
1 & 2-2cdot 1 & 0 & 0 & 25cfrac{25}{93}-2cdot 23cfrac{17}{31} 
0 & 1 & 0 & 0 & 23cfrac{17}{31} 
0 & 0 & 1 & 0 & -5cfrac{35}{93} 
0 & 0 & 0 & 1& 1cfrac{22}{93}
end{bmatrix}=egin{bmatrix}
1 & 0 & 0 & 0 & -21cfrac{77}{93} 
0 & 1 & 0 & 0 & 23cfrac{17}{31} 
0 & 0 & 1 & 0 & -5cfrac{35}{93} 
0 & 0 & 0 & 1& 1cfrac{22}{93}
end{bmatrix}

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:

egin{bmatrix}
2 & 4 & 8 & 2 & 10  
1 & 8 & 16 & 31 & 17  
22 & 26 & 4 & 190 & 194 
8 & 32 & 26 & 6 & 20  
end{bmatrix}

Odpowiedź:

egin{cases}
x_1= -44  
x_2= 49  
x_3= -11  
x_4= -5 
end{cases}

Załączniki:

Napisany przeze mnie program RownaniaLiniowe

Komentarze