Eliminacja Gaussa


Tematy pokrewne
Macierze
Podstawowe pojęcia dotyczące macierzy
Reprezentacja macierzy w pamięci komputera
Mnożenie macierzy przez skalar
Dodawanie macierzy
Transponowanie macierzy
Mnożenie macierzy
Potęgowanie macierzy
Eliminacja Gaussa
Eliminacja Gaussa-Crouta
Wyznacznik macierzy
Rozkład LU
Rozkład LU – rozwiązywanie układu równań liniowych
Rozkład LU – macierz odwrotna
Rozkład LU – wyznacznik macierzy

Problem

Znaleźć rozwiązanie układu równań liniowych postaci:

a1,1x1 + a1,2x2 + ... + a1,nxn = b1
a2,1x1 + a2,2x2 + ... + a2,nxn = b2
...
an,1x1 + an,2x2 + ... + an,nxn = bn

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 (- ai,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
+   x2
 + 4x2
 - 2x2
 + 4x3
+ 4x3
 + 2x3
+ 4x3
 - 2x4
+ 2x4
 + x4
+ 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.

 

4x1 - 2x2 + 4x3 - 2x4 = 8
3x1 + x2 + 4x3 + 2x4 - 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
2,5x2
5x2
 -x2
 + 4x3
+   x3
+        
+ 2x3
 -  2x4
 
+ 3,5x4
2x4
+ 3x4
 =  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 - 2x4 = 8
2,5x2 + x3 + 3,5x4 =  1
5x2 +  2x4 -2 • (2,5x2 + x3 + 3,5x4) = 6 - 2
-x2 + 2x3 + 3x4 + 0,4 • (2,5x2 + 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

4x1


 - 2x2
2,5x2   
 +  4x3
+    x3
-2x3
2,4x3
 -    2x4
 
+ 3,5x4
-    5x4
+ 4,4x4
 =  8
=  1
=  4
= -1,6

 

Ostatnia eliminacja:

– od równania 4 odejmujemy stronami równanie 3 przemnożone przez 2,4/-2 = -1,2:

 

4x1 - 2x2 + 4x3 - 2x4 = 8
2,5x2 + x3 + 3,5x4 =  1
-2x3 - 5x4 = 4
2,4x3 + 4,4x4 +1,2 • (-2x3 - 5x4) = -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

 

4x1 - 2x2 +  4x3 - 2x4 = 8
  2,5x2 + x3+  3,5x4 = 1
    -2x3-  5x4 = 4
      -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

 

Algorytm eliminacji Gaussa

Wejście
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
Wyjście:

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.

Elementy pomocnicze:
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
Lista kroków:
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 K04..K08  
K04:     Dla j = i+1,i+2,...,n wykonuj K05...K08  
K05:         Jeśli |AB[i,i]| < ε, to zakończ ; jeśli dzielnik równy zero, kończymy
K06:
        m ← -    AB[j,i]
AB[i,i]
; obliczamy mnożnik
K07:         Dla k = i+1,i+2,...,n+1 wykonuj K08  
K08:             AB[j,k] ← AB[j,k] + m • AB[i,k] ; dodajemy wiersz i-ty pomnożony przez m
K09: Dla i = n,n-1,...,1 wykonuj K10...K14 ; etap wyliczania niewiadomych
K10:     sAB[i,n+1] ; do s trafia współczynnik bi
K11:     Dla j = n,n-1,...,i+1 wykonuj K12  
K12:         ss - AB{i,j] • X[j] ; od bi odejmujemy kolejne iloczyny aijxj
K13     Jeśli |AB[i,i]| < ε, to zakończ  
K14:
    X[i] ←   s
AB[i,i]
; obliczamy niewiadomą
K15: r ← true ; zaznaczmy sukces
K16: Zakończ  

 

Program

Ważne:

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:

 

4x1
3x1
2x1
2x1
 - 2x2
+   x2
 + 4x2
 - 2x2
 + 4x3
+ 4x3
 + 2x3
+ 4x3
 - 2x4
+ 2x4
 + x4
+ 2x4
 =  8
=  7
=10
=  2

 

Dane dla programu:

 

4
4 -2 4 -2 8
3 1 4 2 7
2 4 2 1 10
2 -2 4 2 2

 

Lazarus
// Eliminacja Gaussa
// Data: 15.02.2010
// (C)2012 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.
Code::Blocks
// Eliminacja Gaussa
// Data: 15.02.2010
// (C)2012 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;
}
Free Basic
' Eliminacja Gaussa
' Data: 15.02.2010
' (C)2012 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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.