Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Eliminacja Gaussa

SPIS TREŚCI
Tematy pomocnicze

Problem

Należy znaleźć rozwiązanie układu równań liniowych postaci:

wykorzystując metodę eliminacji Gaussa

Rozwiązanie

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 a 2, 1, a 3, 1, ... , a n, 1 leżące pod pierwszym elementem a 1, 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 : a 1, 1 ):

obrazek

Zwróć uwagę, iż po tej operacji elementy pierwszej kolumny leżące poniżej a 1, 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 ):

obrazek

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:

obrazek

Operację kontynuujemy dla kolejnych podmacierzy, aż otrzymamy macierz trójkątną:

obrazek

Macierz ta odpowiada przekształconemu układowi równań liniowych:

obrazek

Kolejne niewiadome x i  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ń:

4x 1
3x 1
2x 1
2x 1
 – 2x 2
+ 1x 2
 + 4x 2
 – 2x 2
 + 4x 3
+ 4x 3
 + 2x 3
+ 4x 3
 – 2x 4
+ 2x 4
 + 1x 4
+ 2x 4
=  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.

3x 1 + x 2 + 4x 3 + 2x 4 – 0,75 • ( 4x 1 – 2x 2 + 4x 3 – 2x 4 ) =  7 - 0,75 • 8
2x 1 + 4x 2 + 2x 3 + x 4 – 0,5 • ( 4x 1 – 2x 2 + 4x 3 – 2x 4 ) = 10 – 0,5 • 8
2x 1 – 2x 2 + 4x 3 + 2x 4 – 0,5 • ( 4x 1 – 2x 2 + 4x 3 – 2x 4 ) = 2 –0,5 • 8

4x 1 – 2x 2 + 4x 3 – 2x 4 = 8
3x 1 + x 2 + 4x 3 + 2x 4 – 3x 1 + 1,5x 2 – 3x 3 + 1,5x 4 =  1
2x 1 + 4x 2 + 2x 3 + x 4 – 2x 1 + x 2 – 2x 3 + x 4 = 6
2x 1 – 2x 2 + 4x 3 + 2x 4 – 2x 1 + x 2 – 2x 3 + x 4 = –2

4x 1 – 2x 2 + 4x 3 – 2x 4 = 8
3x 1 – 3x 1 + x 2 + 1,5x 2 + 4x 3 – 3x 3 + 2x 4 = 1,5x 4 =  1
2x 1 – 2x 1 + 4x 2 + x 2 + 2x 3 – 2x 3 + x 4 + x 4 = 6
2x 1 – 2x 1 – 2x 2 + x 2 + 4x 3 – 2x 3 + 2x 4 + x 4 = –2

4x 1 – 2x 2 + 4x 3 – 2x 4 = 8

4,0x 1


 – 2,0x 2
2,5x 2
5,0x 2
 –x 2
 + 4,0x 3
+   x 3
+         
+ 2,0x 3
 –  2,0x 4
 
+ 3,5x 4
2,0x 4
+ 3,0x 4
 =  8
=  1
=  6
= –2

Zwróć uwagę, iż z równań 2, 3 i 4 zniknęła niewiadoma x 1, 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.

4x 1 – 2x 2 + 4x 3 – 2x 4 = 8
2,5x 2 + x 3 + 3,5x 4 =  1
5x 2 +  2x 4 –2 • ( 2,5x 2 + x 3 + 3,5x 4 ) = 6 – 2
–x 2 + 2x 3 + 3x 4 + 0,4 • ( 2,5x 2 + x 3 + 3,5x 4 ) = –2 + 0,4

4x 1 – 2x 2 + 4x 3 – 2x 4 = 8
2,5x 2 + x 3 + 3,5x 4 =  1
5x 2 +  2x 4 – 5x 2 – 2x 3 – 7x 4 = 4
–x 2 + 2x 3 + 3x 4 + x 2 + 0,4x 3 + 1,4x 4 = –1,6

4x 1 – 2x 2 + 4x 3 – 2x 4 = 8
2,5x 2 + x 3 + 3,5x 4 =  1
5x 2 – 5x 2 – 2x 3 +  2x 4 – 7x 4 = 4
–x 2 + x 2 + 2x 3 + 0,4x 3 + 3x 4 + 1,4x 4 = –1,6
4,0x 1


 –  2,0x 2
2,5x 2
 +
+
 4,0x 3
1,0
x 3
2,0x 3
2,4x 3
 –
+

+
 2,0x 4
3,5x 4
5,0x 4
4,4x 4
 =
=
=
=
   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:

4x 1 – 2x 2 + 4x 3 – 2x 4 = 8
2,5x 2 + x 3 + 3,5x 4 =  1
–2x 3 – 5x 4 = 4
2,4x 3 + 4,4x 4 +1,2 • ( –2x 3 – 5x 4 ) = –1,6 + 1,2 • 4

4x 1 – 2x 2 + 4x 3 – 2x 4 = 8
2,5x 2 + x 3 + 3,5x 4 =  1
–2x 3 – 5x 4 = 4
2,4x 3 + 4,4x 4 – 2,4x 3 – 6x 4 = 3,2

4x 1 – 2x 2 + 4x 3 – 2x 4 = 8
2,5x 2 + x 3 + 3,5x 4 =  1
–2x 3 – 5x 4 = 4
2,4x 3 – 2,4x 3 + 4,4x 4 – 6x 4 = 3,2
4,0x 1 2,0x 2 + 4,0x 3 2,0x 4 = 8,0
  2,5x 2 + 1,0x 3 + 3,5x 4 = 1,0
    2,0x 3 5,0x 4 = 4,0
      –1,6x 4 =  3,2

Rozpoczynamy postępowanie odwrotne. Idąc od końca wyznaczamy kolejnie niewiadome:

x 4 =   3,2 = 2
–1,6

Mając x 4 możemy obliczyć x 3 z równania nr 3:

x 3 =   4 + 5x 4 = 4 + 5 • ( –2 )  =  4 – 10 = –6  = 3
–2 –2 –2 –2

Obliczamy x 2 z równania nr 2:

x 2 =   1 – 3,5x 4 – x 3 = 1 – 3,5 • ( –2 ) – 3  =  1 + 7 – 3 = 5  = 2
2,5 2,5 2,5 2,5

I ostatnią niewiadomą x 1 otrzymamy z równania nr 1:

x 1=   8 + 2x 4 – 4x 3 + 2x 2 = 8 + 2 • ( –2 ) – 4 • 3 + 2 • 2  =  8 – 4 – 12 + 4 = –4  =1
4 4 4 4

i ostatecznie możemy zapisać rozwiązanie:

x 1 = –1
x 2 =  2
x 3 =  3
x 4 = –2

Algorytm eliminacji Gaussa

Wejście:

n  –  liczba niewiadomych, n  ∈ N.
AB  – macierz n  × ( n  + 1 ) zawierająca współczynniki a i, j, i  = 1...n ; j  = 1...n,  oraz w kolumnie n  + 1 współczynniki b i  układu równań, AB  ∈ R.
X  – wektor n elementowy, w którym zostaną umieszczone niewiadome x i, 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.

Zmienne pomocnicze:

i, j, k  –  zmienne sterujące pętli. i, j, kN.
m  – mnożnik, przez który będą mnożone elementy macierzy AB. mR.
s  – zlicza sumę iloczynów. sR.
ε  – 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 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 b i
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  

Przykładowe programy

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:

4x 1
3x 1
2x 1
2x 1
 – 2x 2
+   x 2
 + 4x 2
 – 2x 2
 + 4x 3
+ 4x 3
 + 2x 3
+ 4x 3
 – 2x 4
+ 2x 4
 + x 4
+ 2x 4
=  8
=  7
=10
=  2
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.
C++
// 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
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 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: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.