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

©2024 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:

a1,1·x1+a1,2·x2+…+a1,n·xn = b1
a2,1·x1+a2,2·x2+…+a2,n·xn = b2
            
an,1·x1+an,2·x2+…+an,n·xn = bn

wykorzystując metodę eliminacji Gaussa

Rozwiązanie

Układ równań liniowych

a1,1·x1+a1,2·x2+…+a1,n·xn = b1
a2,1·x1+a2,2·x2+…+a2,n·xn = b2
            
an,1·x1+an,2·x2+…+an,n·xn = bn

możemy zapisać w postaci macierzowej jako:

 
a1,1
a1,2
 … 
a1,n
 
 
a2,1
a2,2
a2,n
 
 
an,1
an,2
an,n
 
×
 
x1
 
 
x2
 
 
xn
 
=
 
b1
 
 
b2
 
 
bn
 

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

A|B =
 
a1,1
a1,2
 … 
a1,n
 b1 
 
 
a2,1
a2,2
a2,n
 b2
 
 
an,1
an,2
an,n
 bn
 

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

 
      a1,1
      a1,2
 … 
      a1,n
     b1
 
 
a2,1-a2,1:a1,1·a1,1
a2,2-a2,1:a1,1·a1,2
a2,n-a2,1:a1,1·a1,n
b2-a2,1:a1,1·b1
 
 
an,1-an,1:a1,1·a1,1
an,2-an,1:a1,1·a1,2
an,n-an,1:a1,1·a1,n
bn-an,1:a1,1·b1
 
=
 
a1,1
      a1,2
 … 
      a1,n
     b1
 
 
 0
a2,2-a2,1:a1,1·a1,2
a2,n-a2,1:a1,1·a1,n
b2-a2,1:a1,1·b1
 
 0
 
 0
an,2-an,1:a1,1·a1,2
an,n-an,1:a1,1·a1,n
bn-an,1:a1,1·b1
 
 

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:

A' =
 
a1,1
a1,2
  
a1,n
b1
 
 
 0
a'2,2
a'2,n
b'2
 
 0
 
 0
a'n,2
a'n,n
b'n
 

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

 
a1,1
      a1,2
      a1,3
  
      a1,n
      b1
 
 
 0
      a'2,2
      a'2,3
      a'2,n
      b'2
 
 0
a'3,2-a'3,2:a'2,2·a'2,2
a'3,3-a'3,2:a'2,2·a'2,3
a'3,n-a'3,2:a'2,2·a'2,n
b'3-a'3,2:a'2,2·b'2
 0
 
 0
a'n,2-a'n,2:a'2,2·a'2,2
a'n,3-a'n,2:a'2,2·a'2,3
a'n,n-a'n,2:a'2,2·a'2,n
b'n-a'n,2:a'2,2·b'2
 
=
 
a1,1
a1,2
        a1,3
  
      a1,n
     b1
 
 
 0
a'2,2
        a'2,3
      a'2,n
     b'2
 
 0
 0
a'3,3-a'3,2:a'2,2·a'2,3
a'3,n-a'3,2:a'2,2·a'2,n
b'3-a'3,2:a'2,2·b'2
 0
 0
 
 0
 0
a'n,3-a'n,2:a'2,2·a'2,3
a'n,n-a'n,2:a'2,2·a'2,n
b'n-a'n,2:a'2,2·b'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:

A' =
 
a1,1
a1,2
a1,3
  
a1,n
b1
 
 
 0
a'2,2
a'2,3
a'2,n
b'2
 
 0
 0
a"3,3
a"3,n
b"3
 0
 0
 
 0
 0
a"n,3
a"n,n
b"n
 

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

A"' =
 
a1,1
a1,2
a1,3
 … 
a1,n-1
a1,n
b1
 
 
 0
a'2,2
a'2,3
a'2,n-1
a'2,n
b'2
 
 0
 0
a"3,3
a"3,n-1
a"3,n
b"3
 0
 0
 
 0
 0
 0
   0
a"'n,n
b"'n
 

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

 
a1,1
a1,2
a1,3
 … 
a1,n-1
a1,n
 
 
 0
a'2,2
a'2,3
a'2,n-1
a'2,n
 
 0
 0
a"3,3
a"3,n-1
a"3,n
 0
 0
 
 0
 0
 0
   0
a"'n,n
 
×
 
x1
 
 
x2
 
x3
 
xn
 
=
 
b1
 
 
b'2
 
b"3
 
b"'n
 

Kolejne niewiadome xi znajdujemy teraz rekurencyjnie wg wzorów:

xn =
 b"'n
a"'n,n
xi =
 b"i-a"i,n·xn-…-a"1,j+1·xi+1
,i = n-1,n-2,…,1
           a"i,i

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

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

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,5x4x3
=
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 kroki K04..K07
K04:   Dla j = i+1,i+2,…,n:
       wykonuj kroki K05…K07
K05:     Jeśli |AB[i,i]| < ε, ; jeśli dzielnik równy zero, kończymy
         to zakończ
K06:     m ← -AB[j,i]:AB[i,i] ; obliczamy mnożnik
K07:     Dla k = i+1,i+2,…,n+1: ; dodajemy wiersz i-ty pomnożony przez m
         wykonuj: AB[j,k] ← B[j,k]+m·AB[i,k]
K08: Dla i = n,n–1,…,1:       ; etap wyliczania niewiadomych
     wykonuj kroki K09…K12
K09:   s ← AB[i,n+1]          ; do s trafia współczynnik bi
K10:   Dla j = n,n–1,…,i+1:   ; od bi odejmujemy kolejne iloczyny aij·xj
       wykonuj: s ← sAB{i,jX[j]
K11:   Jeśli |AB[i,i]| < ε,   ; nie można dzielić!!!
       to zakończ
K12:   X[i] ← s/AB[i,i]       ; 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, (n+1)-sza liczba odnosi się do wyrazu wolnego b. Poniżej mamy przykładowe dane wejściowe dla programu:

Równanie:

4x1–2x2+4x3–2x4 =  8
3x1+ x2+4x3+2x4 =  7
2x1+4x2+2x3+ x4 = 10
2x1–2x2+4x3+2x4 =  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]);

  writeln;

  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];

  cout << endl;

  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

Print

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
Python (dodatek)
# Eliminacja Gaussa
# Data: 18.04.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------

EPS = 1e-12; # stała przybliżenia zera

# Funkcja realizuje algorytm eliminacji Gaussa
#---------------------------------------------
def gauss(AB,X):

    # eliminacja współczynników

    n = len(X)
    for i in range(n-1):
        for j in range(i+1,n):
            if abs(AB[i][i]) < EPS: return False
            m = -AB[j][i]/AB[i][i]
            for k in range(i+1,n+1):
                AB[j][k] += m*AB[i][k]

    # wyliczanie niewiadomych

    for i in reversed(range(n)):
        s = AB[i][n]
        for j in reversed(range(n)):
            s -= AB[i][j]*X[j]
        if abs(AB[i][i]) < EPS: return False
        X[i] = s/AB[i][i]
    return True

# Program główny
#---------------

# odczytujemy liczbę niewiadomych

n = int(input())

# tworzymy macierze AB i X

AB = []
X  = []

# odczytujemy dane dla macierzy AB

for i in range(n):
    X.append(0)
    a = input().split()
    a = [float(a[j]) for j in range(n+1)]
    AB.append(a)

print()

if gauss(AB,X):
    for i in range(n):
        print("x%d = %9.4f" % (i+1,X[i]))
else:
    print("DZIELNIK ZERO")

# usuwamy macierze z pamięci

del AB,X,a
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
©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: i-lo@eduinf.waw.pl

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

Informacje dodatkowe.