Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemNależy znaleźć rozwiązanie układu równań liniowych postaci:
wykorzystując metodę eliminacji Gaussa |
Układ równań liniowych
możemy zapisać w postaci macierzowej jako:
lub w skrócie:
A × X = B
gdzie:
A | : | macierz kwadratowa o wymiarze n × n współczynników stojących przy niewiadomych x |
X | : | wektor kolumnowy n niewiadomych |
B | : | wektor kolumnowy n wyrazów wolnych |
W pierwszym kroku dopisujemy do macierzy A wektor wyrazów wolnych B, otrzymując w ten sposób macierz rozszerzoną:
W kolejnych krokach rozpoczynamy przekształcanie rozszerzonej macierzy A|B w macierz trójkątną górną. Etap ten nosi nazwę etapu eliminacji. Najpierw redukujemy do zera kolejne elementy a2, 1, a3, 1, … , an, 1 leżące pod pierwszym elementem a1, 1 w kolumnie 1. W tym celu do kolejnych elementów wiersza i-tego (i = 2, 3, …, n) dodajemy kolejne elementy wiersza pierwszego przemnożone przez ( – a i, 1 : a1, 1):
Zwróć uwagę, iż po tej operacji elementy pierwszej kolumny leżące poniżej a1, 1 zostają wyzerowane. Otrzymujemy macierz nowych elementów, które oznaczyliśmy znakiem prim:
Pierwszy wiersz jest taki sam jak w macierzy rozszerzonej, natomiast pozostałe wiersze są już inne. Teraz redukujemy do zera elementy w drugiej kolumnie leżące pod a'2, 2. Wykonujemy identyczną operację, lecz dla macierzy z pominięciem pierwszej kolumny i pierwszego wiersza – do kolejnych wierszy i-tych (i = 3, 4, …, n) dodajemy wiersz drugi pomnożony przez ( – a'i, 2 : a' 2, 2):
W efekcie elementy drugiej kolumny leżące pod a'2, 2 uległy wyzerowaniu i znów otrzymaliśmy macierz z nowymi elementami, oznaczonymi znakiem bis:
Operację kontynuujemy dla kolejnych podmacierzy, aż otrzymamy macierz trójkątną:
Macierz ta odpowiada przekształconemu układowi równań liniowych:
Kolejne niewiadome xi znajdujemy teraz rekurencyjnie wg wzorów:
Powyższa metoda nosi nazwę metody eliminacji Gaussa (ang. Gauss elimination method).
Przykład:
Rozwiążmy podaną wyżej metodą eliminacji Gaussa następujący układ równań:
4x1 3x1 2x1 2x1 |
– 2x2 + 1x2 + 4x2 – 2x2 |
+ 4x3 + 4x3 + 2x3 + 4x3 |
– 2x4 + 2x4 + 1x4 + 2x4 |
= 8 = 7 =10 = 2 |
Rozpoczynamy etap eliminacji zmiennych:
– od równania 2 odejmujemy stronami równanie 1 przemnożone przez
3/4 = 0, 75
– od równania 3 odejmujemy stronami równanie 1 przemnożone przez 2/4
= 0, 5
– od równania 4 odejmujemy stronami równanie 1 przemnożone przez 2/4
= 0, 5.
3x1 + x2 + 4x3 + 2x
4 – 0,75 • (4x1
– 2x2 + 4x3 – 2x4) = 7 - 0,75
• 8 2x1 + 4x2 + 2x3 + x4 – 0,5 • (4x1 – 2x2 + 4x3 – 2x4) = 10 – 0,5 • 8 2x1 – 2x2 + 4x3 + 2x4 – 0,5 • (4x1 – 2x2 + 4x3 – 2x4) = 2 – 0,5 • 8 4x1 – 2x2 + 4x3 – 2x4 = 8 3x1 + x2 + 4x3 + 2x4 – 3x1 + 1,5x2 – 3x3 + 1,5x4 = 1 2x1 + 4x2 + 2x3 + x4 – 2x1 + x2 – 2x3 + x4 = 6 2x1 – 2x2 + 4x3 + 2x4 – 2x1 + x2 – 2x3 + x4 = – 2 4x1 – 2x2 + 4x3 – 2x4 = 8 3x1 – 3x1 + x2 + 1,5x2 + 4x3 – 3x3 + 2x4 = 1,5x4 = 1 2x1 – 2x1 + 4x2 + x2 + 2x3 – 2x3 + x4 + x4 = 6 2x1 – 2x1 – 2x2 + x2 + 4x3 – 2x3 + 2x4 + x4 = – 2 |
4x1 – 2x2 + 4x3 – 2x4
= 8
4,0x1 |
– 2,0x2 2,5x2 5,0x2 – x2 |
+ 4,0x3 + x3 + + 2,0x3 |
– 2,0x4 + 3,5x4 2,0x4 + 3,0x4 |
= 8
= 1 = 6 = – 2 |
Zwróć uwagę, iż z równań 2, 3 i 4 zniknęła niewiadoma x1, ponieważ współczynnik przy niej został zredukowany do zera. Eliminujemy następne niewiadome:
– od równania 3 odejmujemy stronami równanie 2 przemnożone przez
5/2,5 = 2
– od równania 4 odejmujemy stronami równanie 2 przemnożone przez – 1/
2,5 = – 0,4.
4x1 – 2x2 + 4x3 – 2x
4 = 8 2,5x2 + x3 + 3,5x4 = 1 5x2 + 2x4 – 2 • (2,5x2 + x 3 + 3,5x4) = 6 – 2 – x2 + 2x3 + 3x4 + 0,4 • (2,5x 2 + x3 + 3,5x4) = – 2 + 0,4 4x1 – 2x2 + 4x3 – 2x4 = 8 2,5x2 + x3 + 3,5x4 = 1 5x2 + 2x4 – 5x2 – 2x3 – 7x4 = 4 – x2 + 2x3 + 3x4 + x2 + 0,4x3 + 1,4x4 = – 1,6 4x1 – 2x2 + 4x3 – 2x4 = 8 2,5x2 + x3 + 3,5x4 = 1 5x2 – 5x2 – 2x3 + 2x4 – 7x4 = 4 – x2 + x2 + 2x3 + 0,4x3 + 3x4 + 1,4x4 = – 1,6 |
4,0x1 |
– | 2,0x2 2,5x2 |
+ + – |
4,0x3 1,0x3 2,0x3 2,4x3 |
– + – + |
2,0x4 3,5x4 5,0x4 4,4x4 |
= = = = |
8,0 1,0 4,0 – 1,6 |
Ostatnia eliminacja:
– od równania 4 odejmujemy stronami równanie 3 przemnożone przez 2,4/– 2 = – 1,2:
4x1 – 2x2 + 4x3 – 2x
4 = 8 2,5x2 + x3 + 3,5x4 = 1 – 2x3 – 5x4 = 4 2,4x3 + 4,4x4 +1,2 • ( – 2x3 – 5x 4) = – 1,6 + 1,2 • 4 4x1 – 2x2 + 4x3 – 2x4 = 8 2,5x2 + x3 + 3,5x4 = 1 – 2x3 – 5x4 = 4 2,4x3 + 4,4x4 – 2,4x3 – 6x4 = 3,2 4x1 – 2x2 + 4x3 – 2x4 = 8 2,5x2 + x3 + 3,5x4 = 1 – 2x3 – 5x4 = 4 2,4x3 – 2,4x3 + 4,4x4 – 6x4 = 3,2 |
4,0x1 – | 2,0x2 + | 4,0x3 – | 2,0x4 = | 8,0 |
2,5x2 + | 1,0x3 + | 3,5x4 = | 1,0 | |
– 2,0x3 – | 5,0x4 = | 4,0 | ||
– 1,6x4 = | 3,2 |
Rozpoczynamy postępowanie odwrotne. Idąc od końca wyznaczamy kolejnie niewiadome:
x4 = | 3,2 | = – 2 |
– 1,6 |
Mając x4 możemy obliczyć x3 z równania nr 3:
x3 = | 4 + 5x4 | = | 4 + 5 • ( – 2) | = | 4 – 10 | = | – 6 | = 3 |
– 2 | – 2 | – 2 | – 2 |
Obliczamy x2 z równania nr 2:
x2 = | 1 – 3,5x4 – x3 | = | 1 – 3,5 • ( – 2) – 3 | = | 1 + 7 – 3 | = | 5 | = 2 |
2,5 | 2,5 | 2,5 | 2,5 |
I ostatnią niewiadomą x1 otrzymamy z równania nr 1:
x1= | 8 + 2x4 – 4x3 + 2x2 | = | 8 + 2 • ( – 2) – 4 • 3 + 2 • 2 | = | 8 – 4 – 12 + 4 | = | – 4 | = – 1 |
4 | 4 | 4 | 4 |
i ostatecznie możemy zapisać rozwiązanie:
x1 = – 1
x2 = 2
x3 = 3
x4 = – 2
n | : | liczba niewiadomych, n ∈ N. |
AB | : | macierz n × (n + 1) zawierająca współczynniki ai, j, i = 1…n ; j = 1…n, oraz w kolumnie n + 1 współczynniki bi układu równań, AB ∈ R. |
X | : | wektor n elementowy, w którym zostaną umieszczone niewiadome xi, X ∈ R. |
Jeśli zmienna r ma wartość true, to wektor X zawiera rozwiązanie układu równań. W przeciwnym razie nastąpiło dzielenie przez zero i algorytm nie może znaleźć poprawnych rozwiązań układu równań. Pierwotna macierz współczynników AB zostaje zniszczona – zastąpiona macierzą trójkątną, powstałą w czasie redukcji współczynników.
i, j, k | : | zmienne sterujące pętli. i, j, k ∈ N. |
m | : | mnożnik, przez który będą mnożone elementy macierzy AB. m ∈ R. |
s | : | zlicza sumę iloczynów. s ∈ R. |
ε | : | określa dokładność porównania z zerem; ε = 10 – 12, ε ∈ R. |
K01: | r ← false | zakładamy porażkę |
K02: | ε ← 10– 12 | określamy dokładność porównania z zerem |
K03: | Dla i = 1, 2, …,
n – 1: wykonuj kroki K04..K07 |
|
K04: | Dla j
= i + 1, i + 2, …, n : wykonuj kroki K05…K07 |
|
K05: |
Jeśli |AB [i, i] | <
ε, to zakończ |
jeśli dzielnik równy zero, kończymy |
K06: | obliczamy mnożnik | |
K07: | Dla
k = i + 1, i + 2, …, n + 1: wykonuj: AB [j, k] ← B [j, k] + m · AB [i, k] |
dodajemy wiersz i-ty pomnożony przez m |
K08: | Dla i = n,
n – 1, …, 1: wykonuj kroki K09…K12 |
etap wyliczania niewiadomych |
K09: | s ← AB [i, n + 1] | do s trafia współczynnik bi |
K10: | Dla j
= n, n – 1, …, i + 1: wykonuj: s ← s – AB{i, j] • X [j] |
od bi odejmujemy kolejne iloczyny aijxj |
K11: |
Jeśli |AB [i, i] | < ε, to zakończ |
nie można dzielić!!! |
K12: | obliczamy niewiadomą | |
K13: | r ← true | zaznaczmy sukces |
K14: | Zakończ |
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program wczytuje dane definiujące
macierz współczynników
AB i wylicza niewiadome X. Jeśli
obliczenie nie może zostać wykonane, program wypisuje komunikat
"DZIELNIK ZERO". Dane dla macierzy AB są zdefiniowane następująco: Pierwsza liczba określa liczbę niewiadomych n. Następne n × (n + 1) liczb określa zawartość macierzy AB wierszami – pierwsze n liczb każdego wiersza odnosi się do współczynników a, a (n + 1)-sza liczba odnosi się do wyrazu wolnego b. Poniżej mamy przykładowe dane wejściowe dla programu: Równanie:
|
Dane przykładowe (przekopiuj do schowka i
wklej do okna konsoli):
4 4 -2 4 -2 8 3 1 4 2 7 2 4 2 1 10 2 -2 4 2 2 |
Pascal// Eliminacja Gaussa // Data: 15.02.2010 // (C)2020 mgr Jerzy Wałaszek //----------------------------- program gauss; type NReal = array of double; // typ tablic wierszy MReal = array of NReal; // typ tablicy wskaźników const eps = 1e-12; // stała przybliżenia zera // Funkcja realizuje algorytm eliminacji Gaussa //--------------------------------------------- function gauss (n : integer; var AB : MReal; var X : NReal) : boolean; var i, j, k : integer; m, s : double; begin // eliminacja współczynników for i := 0 to n - 2 do begin for j := i + 1 to n - 1 do begin if abs (AB [i][i]) < eps then exit (false); m := -AB [j][i] / AB [i][i]; for k := i + 1 to n do AB [j][k] := AB [j][k] + m * AB [i][k]; end; end; // wyliczanie niewiadomych for i := n - 1 downto 0 do begin s := AB [i][n]; for j := n - 1 downto i + 1 do s := s - AB [i][j] * X [j]; if abs (AB [i][i]) < eps then exit (false); X [i] := s / AB [i][i]; end; gauss := true; end; // Program główny //--------------- var AB : MReal; X : NReal; n, i, j : integer; begin // odczytujemy liczbę niewiadomych read (n); // tworzymy macierze AB i X SetLength (AB, n); SetLength (X, n); for i := 0 to n - 1 do SetLength (AB [i], n + 1); // odczytujemy dane dla macierzy AB for i := 0 to n - 1 do for j := 0 to n do read (AB [i][j]); if gauss (n, AB, X) then begin for i := 0 to n - 1 do writeln('x', i + 1, ' = ', X [i] :9:4); end else writeln('DZIELNIK ZERO'); // usuwamy macierze z pamięci for i := 0 to n - 1 do SetLength (AB [i], 0); SetLength (AB, 0); SetLength (X, 0); end. |
// Eliminacja Gaussa // Data: 15.02.2010 // (C)2020 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <iomanip> #include <cmath> using namespace std; const double eps = 1e-12; // stała przybliżenia zera // Funkcja realizuje algorytm eliminacji Gaussa //--------------------------------------------- bool gauss (int n, double ** AB, double * X) { int i, j, k; double m, s; // eliminacja współczynników for(i = 0; i < n - 1; i++) { for(j = i + 1; j < n; j++) { if(fabs (AB [i][i]) < eps) return false; m = -AB [j][i] / AB [i][i]; for(k = i + 1; k <= n; k++) AB [j][k] += m * AB [i][k]; } } // wyliczanie niewiadomych for(i = n - 1; i >= 0; i--) { s = AB [i][n]; for(j = n - 1; j >= i + 1; j--) s -= AB [i][j] * X [j]; if(fabs (AB [i][i]) < eps) return false; X [i] = s / AB [i][i]; } return true; } // Program główny //--------------- int main() { double **AB, *X; int n, i, j; cout << setprecision (4) << fixed; // odczytujemy liczbę niewiadomych cin >> n; // tworzymy macierze AB i X AB = new double * [n]; X = new double [n]; for(i = 0; i < n; i++) AB [i] = new double [n + 1]; // odczytujemy dane dla macierzy AB for(i = 0; i < n; i++) for(j = 0; j <= n; j++) cin >> AB [i][j]; if(gauss (n, AB, X)) { for(i = 0; i < n; i++) cout << "x" << i + 1 << " = " << setw (9) << X [i] << endl; } else cout << "DZIELNIK ZERO\n"; // usuwamy macierze z pamięci for(i = 0; i < n; i++) delete [] AB [i]; delete [] AB; delete [] X; return 0; } |
Basic' Eliminacja Gaussa ' Data: 15.02.2010 ' (C)2020 mgr Jerzy Wałaszek '----------------------------- Const eps As Double = 1e-12 ' stała przybliżenia zera ' Funkcja realizuje algorytm eliminacji Gaussa '--------------------------------------------- Function gauss (n As Integer, AB As Double Ptr Ptr, X As Double Ptr) As Integer Dim As Integer i, j, k Dim As Double m, s ' eliminacja współczynników For i = 0 To n - 2 For j = i + 1 To n - 1 If Abs (AB [i][i]) < eps Then Return 0 m = -AB [j][i] / AB [i][i] For k = i + 1 To n AB [j][k] += m * AB [i][k] Next Next Next ' wyliczanie niewiadomych For i = n - 1 To 0 Step -1 s = AB [i][n] For j = n - 1 To i + 1 Step -1 s -= AB [i][j] * X [j] Next If Abs (AB [i][i]) < eps Then Return 0 X [i] = s / AB [i][i] Next gauss = 1 End Function Dim AB As Double Ptr Ptr Dim X As Double Ptr Dim As Integer n, i, j Open Cons For Input As #1 ' odczytujemy liczbę niewiadomych Input #1, n ' tworzymy macierze AB i X AB = New Double Ptr [n] X = New Double [n] For i = 0 To n - 1 AB [i] = New Double [n + 1] Next ' odczytujemy dane dla macierzy AB For i = 0 To n - 1 For j = 0 To n Input #1, AB [i][j] Next Next Close #1 If gauss (n, AB, X) = 1 Then For i = 0 To n - 1 Print Using "x# = ####.####"; i + 1;X [i] Next Else Print "DZIELNIK ZERO" End If ' usuwamy macierze z pamięci For i = 0 To n - 1 Delete [] AB [i] Next Delete [] AB Delete [] X End |
Wynik: |
4 4 -2 4 -2 8 3 1 4 2 7 2 4 2 1 10 2 -2 4 2 2 x1 = -1.0000 x2 = 2.0000 x3 = 3.0000 x4 = -2.0000 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.