Algorytmy i Struktury Danych - Eliminacja Gaussa

Układ równań liniowych

\[
\begin{matrix}
a_{1,1} \cdot x_1 + a_{1,2} \cdot x_2 + \dots + a_{1,n} \cdot x_n = b_1 \\
a_{2,1} \cdot x_1 + a_{2,2} \cdot x_2 + \dots + a_{2,n} \cdot x_n = b_2 \\
\dots \\
a_{n,1} \cdot x_1 + a_{n,2} \cdot x_2 + \dots + a_{n,n} \cdot x_n = b_n
\end{matrix}
\]

możemy zapisać w postaci macierzowej jako:

text\[
\begin{bmatrix}
a_{1,1} & a_{1,2} & \dots & a_{1,n} \\
a_{2,1} & a_{2,2} & \dots & a_{2,n} \\
\dots & \dots & \dots & \dots \\
a_{n,1} & a_{n,2} & \dots & a_{n,n}
\end{bmatrix}
\times
\begin{bmatrix}
x_1 \\
x_2 \\
\dots \\
x_n
\end{bmatrix}
=
\begin{bmatrix}
b_1 \\
b_2 \\
\dots \\
b_n
\end{bmatrix}
\]

lub w skrócie:

\[A \times X = B\]

gdzie:

\(A\) : macierz kwadratowa o wymiarze \({n\times 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 =
\begin{bmatrix}
a_{1,1} & a_{1,2} & \dots & a_{1,n} & b_1 \\
a_{2,1} & a_{2,2} & \dots & a_{2,n} & b_2 \\
\dots & \dots & \dots & \dots & \dots \\
a_{n,1} & a_{n,2} & \dots & a_{n,n} & b_n
\end{bmatrix}
\]

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{-}\text{tego}}\) (i = 2, 3, …, n) dodajemy kolejne elementy wiersza pierwszego przemnożone przez \(–\frac{a_{i,1}}{a_{1,1}}\):

\[
\begin{aligned}
&\begin{bmatrix}
a_{1,1} & a_{1,2} & \dots & a_{1,n} & b_1 \\
a_{2,1} - \frac{a_{2,1}}{a_{1,1}} \cdot a_{1,1} & a_{2,2} - \frac{a_{2,1}}{a_{1,1}} \cdot a_{1,2} & \dots & a_{2,n} - \frac{a_{2,1}}{a_{1,1}} \cdot a_{1,n} & b_2 - \frac{a_{2,1}}{a_{1,1}} \cdot b_1 \\
\dots & \dots & \dots & \dots & \dots \\
a_{n,1} - \frac{a_{n,1}}{a_{1,1}} \cdot a_{1,1} & a_{n,2} - \frac{a_{n,1}}{a_{1,1}} \cdot a_{1,2} & \dots & a_{n,n} - \frac{a_{n,1}}{a_{1,1}} \cdot a_{1,n} & b_n - \frac{a_{n,1}}{a_{1,1}} \cdot b_1
\end{bmatrix} = \\
\\
&\begin{bmatrix}
a_{1,1} & a_{1,2} & \dots & a_{1,n} & b_1 \\
0 & a_{2,2} - \frac{a_{2,1}}{a_{1,1}} \cdot a_{1,2} & \dots & a_{2,n} - \frac{a_{2,1}}{a_{1,1}} \cdot a_{1,n} & b_2 - \frac{a_{2,1}}{a_{1,1}} \cdot b_1 \\
0 & \dots & \dots & \dots & \dots \\
0 & a_{n,2} - \frac{a_{n,1}}{a_{1,1}} \cdot a_{1,2} & \dots & a_{n,n} - \frac{a_{n,1}}{a_{1,1}} \cdot a_{1,n} & b_n - \frac{a_{n,1}}{a_{1,1}} \cdot b_1
\end{bmatrix}
\end{aligned}
\]

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:

\[
A' =
\begin{bmatrix}
a_{1,1} & a_{1,2} & \dots & a_{1,n} & b_1 \\
0 & a'_{2,2} & \dots & a'_{2,n} & b'_2 \\
0 & \dots & \dots & \dots & \dots \\
0 & a'_{n,2} & \dots & a'_{n,n} & b'_n
\end{bmatrix}
\]

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{-}\text{tych}}\) (i = 3, 4, …, n) dodajemy wiersz drugi pomnożony przez \(–\frac{a'_{i,2}}{a'_{2,2}}\):

\[
\begin{aligned}
&\begin{bmatrix}
a_{1,1} & a_{1,2} & a_{1,3} & \dots & a_{1,n} & b_1 \\
0 & a'_{2,2} & a'_{2,3} & \dots & a'_{2,n} & b'_2 \\
0 & a'_{3,2} - \frac{a'_{3,2}}{a'_{2,2}} \cdot a'_{2,2} & a'_{3,3} - \frac{a'_{3,2}}{a'_{2,2}} \cdot a'_{2,3} & \dots & a'_{3,n} - \frac{a'_{3,2}}{a'_{2,2}} \cdot a'_{2,n} & b'_3 - \frac{a'_{3,2}}{a'_{2,2}} \cdot b'_2 \\
0 & \dots & \dots & \dots & \dots & \dots \\
0 & a'_{n,2} - \frac{a'_{n,2}}{a'_{2,2}} \cdot a'_{2,2} & a'_{n,3} - \frac{a'_{n,2}}{a'_{2,2}} \cdot a'_{2,3} & \dots & a'_{n,n} - \frac{a'_{n,2}}{a'_{2,2}} \cdot a'_{2,n} & b'_n - \frac{a'_{n,2}}{a'_{2,2}} \cdot b'_2
\end{bmatrix} = \\
\\
&\begin{bmatrix}
a_{1,1} & a_{1,2} & a_{1,3} & \dots & a_{1,n} & b_1 \\
0 & a'_{2,2} & a'_{2,3} & \dots & a'_{2,n} & b'_2 \\
0 & 0 & a'_{3,3} - \frac{a'_{3,2}}{a'_{2,2}} \cdot a'_{2,3} & \dots & a'_{3,n} - \frac{a'_{3,2}}{a'_{2,2}} \cdot a'_{2,n} & b'_3 - \frac{a'_{3,2}}{a'_{2,2}} \cdot b'_2 \\
0 & 0 & \dots & \dots & \dots & \dots \\
0 & 0 & a'_{n,3} - \frac{a'_{n,2}}{a'_{2,2}} \cdot a'_{2,3} & \dots & a'_{n,n} - \frac{a'_{n,2}}{a'_{2,2}} \cdot a'_{2,n} & b'_n - \frac{a'_{n,2}}{a'_{2,2}} \cdot b'_2
\end{bmatrix}
\end{aligned}
\]

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'' =
\begin{bmatrix}
a_{1,1} & a_{1,2} & a_{1,3} & \dots & a_{1,n} & b_1 \\
0 & a'_{2,2} & a'_{2,3} & \dots & a'_{2,n} & b'_2 \\
0 & 0 & a''_{3,3} & \dots & a''_{3,n} & b''_3 \\
0 & 0 & \dots & \dots & \dots & \dots \\
0 & 0 & a''_{n,3} & \dots & a''_{n,n} & b''_n
\end{bmatrix}
\]

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

\[
A''' =
\begin{bmatrix}
a_{1,1} & a_{1,2} & a_{1,3} & \dots & a_{1,n-1} & a_{1,n} & b_1 \\
0 & a'_{2,2} & a'_{2,3} & \dots & a'_{2,n-1} & a'_{2,n} & b'_2 \\
0 & 0 & a''_{3,3} & \dots & a''_{3,n-1} & a''_{3,n} & b''_3 \\
0 & 0 & \dots & \dots & \dots & \dots & \dots \\
0 & 0 & 0 & \dots & 0 & a'''_{n,n} & b'''_n
\end{bmatrix}
\]

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

\[
\begin{bmatrix}
a_{1,1} & a_{1,2} & a_{1,3} & \dots & a_{1,n-1} & a_{1,n} \\
0 & a'_{2,2} & a'_{2,3} & \dots & a'_{2,n-1} & a'_{2,n} \\
0 & 0 & a''_{3,3} & \dots & a''_{3,n-1} & a''_{3,n} \\
0 & 0 & \dots & \dots & \dots & \dots \\
0 & 0 & 0 & \dots & 0 & a'''_{n,n}
\end{bmatrix}
\times
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
\dots \\
x_n
\end{bmatrix}
=
\begin{bmatrix}
b_1 \\
b'_2 \\
b''_3 \\
\dots \\
b'''_n
\end{bmatrix}
\]

Kolejne niewiadome \(x_i\) znajdujemy teraz rekurencyjnie wg wzorów:

\[
\begin{aligned}
&x_n = \frac{b'''_n}{a'''_{n,n}} \\
\\
&x_i = \frac{b''_i - a''_{i,n} \cdot x_n - \dots - a''_{i,j+1} \cdot x_{i+1}}{a''_{i,i}} , \quad i = n-1, n-2, \dots, 1
\end{aligned}
\]

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₁–2x₂+4x₃–2x₄=  83x₁+1x₂+4x₃+2x₄=  72x₁+4x₂+2x₃+1x₄= 102x₁–2x₂+4x₃+2x₄=  2

Rozpoczynamy etap eliminacji zmiennych:

– od równania 2 odejmujemy stronami równanie 1 przemnożone przez \({\frac{3}{4} = 0{,}75}\)
– od równania 3 odejmujemy stronami równanie 1 przemnożone przez \({\frac{2}{4} = 0{,}50}\)
– od równania 4 odejmujemy stronami równanie 1 przemnożone przez \({\frac{2}{4} = 0{,}50}\).

4x₁–2x₂+4x₃–2x₄ = 8
3x₁+ x₂+4x₃+2x₄–0,75×(4x₁–2x₂+4x₃–2x₄) =  7-0,75×8
2x₁+4x₂+2x₃+ x₄–0,5 ×(4x₁–2x₂+4x₃–2x₄) = 10–0,5 ×8
2x₁–2x₂+4x₃+2x₄–0,5 ×(4x₁–2x₂+4x₃–2x₄) =  2–0,5 ×8

4x₁–2x₂+4x₃–2x₄ = 8
3x₁+ x₂+4x₃+2x₄ – 3x₁+1,5x₂–3x₃+1,5x₄ =  1
2x₁+4x₂+2x₃+ x₄ – 2x₁+   x₂–2x₃+   x₄ =  6
2x₁–2x₂+4x₃+2x₄ – 2x₁+   x₂–2x₃+   x₄ = –2

4x₁–2x₂+4x₃–  2x₂ = 8
3x₁–3x₁+ x₂+1,5x₂+4x₃–3x₃+2x₄+1,5x₄ =  1
2x₁–2x₁+4x₂+   x₂+2x₃–2x₃+ x₄+   x₄ =  6
2x₁–2x₁–2x₂+   x₂+4x₃–2x₃+2x₄+   x₄ = –2

4,0x₁–2,0x₂+4,0x₃–2,0x₄=  8
     2,5x₂+   x₃+3,5x₄=  1
     5,0x₂+     2,0x₄=  6
       –x₂+2,0x₃+3,0x₄= –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 \({\frac{5}{2{,}5} = 2{,}0}\)
– od równania 4 odejmujemy stronami równanie 2 przemnożone przez \({-\frac{1}{2{,}5} = -0{,}4}\).

4x₁–2x₂+4x₃–  2x₄ = 8
 2,5x₂+ x₃+3,5x₄ = 1
   5x₂+     2x₄ – 2×(2,5x₂+x₃+3,5x₄) =  6–2,0
   –x₂+2x₃+  3x₄+0,4×(2,5x₂+x₃+3,5x₄) = –2+0,4

4x₁–2x₂+4x₃–  2x₄ = 8
 2,5x₂+ x₃+3,5x₄ = 1
   5x₂+     2x₄–x₂–2x₃–  7x₄ =  4,0
   –x₂+2x₃+  3x₄+x₂+0,4x₃+1,4x₄ = –1,6

4x₁–2x₂+4x₃–  2x₄ = 8
              2,5x₂+ x₃+3,5x₄ =  1
    5x₂–5x₂–2x₃+    2x₄–7,0x₄ =  4.0
   –x₂+x₂+2x₃+0,4x₃+3x₄+1,4x₄ = –1,6

4,0x₁–2,0x₂+4,0x₃–2,0x₄=  8,0
      2,5x₂+1,0x₃+3,5x₄=  1,0
          2,0x₃–5,0x₄=  4,0
          2,4x₃+4,4x₄= –1,6

Ostatnia eliminacja:

– od równania 4 odejmujemy stronami równanie 3 przemnożone przez \({\frac{2{,}4}{-2} = -1{,}2}\):

4x₁–2x₂+4x₃–  2x₄ = 8
 2,5x₂+ x₃+3,5x₄ = 1
     –2x₃–  5x₄ = 4
    2,4x₃+4,4x₄+1,2·(–2x₃–5x₄) = –1,6+1,2×4

4x₁–2x₂+4x₃–  2x₄ = 8
 2,5x₂+ x₃+3,5x₄ = 1
     –2x₃–  5x₄ = 4
    2,4x₃+4,4x₄ – 2,4x₃–6x₄ = 3,2

4x₁–2x₂+4x₃–  2x₄ = 8
 2,5x₂+ x₃+3,5x₄ = 1
     –2x₃–  5x₄ = 4
    2,4x₃–2,4x₃+ 4,4x₄–6x₄ = 3,2

4,0x₁–2,0x₂+4,0x₃–2,0x₄ = 8,0
     2,5x₂+1,0x₃+3,5x₄ = 1,0
         –2,0x₃–5,0x₄ = 4,0
              –1,6x₄ = 3,2

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

\[
x_4 = \frac{3{,}2}{-1{,}6} = -2
\]

Mając \(x_4\) możemy obliczyć \(x_3\) z równania nr 3:

\[
x_3 = \frac{4 + 5 \cdot x_4}{-2} = \frac{4 + 5 \cdot (-2)}{-2} = \frac{4 - 10}{-2} = \frac{-6}{-2} = 3
\]

Obliczamy \(x_2\) z równania nr 2:

\[
x_2 = \frac{1 - 3{,}5 \cdot x_4 - x_3}{2{,}5} = \frac{1 - 3{,}5 \cdot (-2) - 3}{2{,}5} = \frac{1 + 7 - 3}{2{,}5} = \frac{5}{2{,}5} = 2
\]

I ostatnią niewiadomą \(x_1\) otrzymamy z równania nr 1:

\[
x_1 = \frac{8 + 2 \cdot x_4 - 4 \cdot x_3 + 2 \cdot x_2}{4} = \frac{8 + 2 \cdot (-2) - 4 \cdot 3 + 2 \cdot 2}{4} = \frac{8 - 4 - 12 + 4}{4} = \frac{-4}{4} = -1
\]

i ostatecznie możemy zapisać rozwiązanie:

\[
\begin{aligned}
&x_1 = -1 \\
&x_2 = \phantom{-}2 \\
&x_3 = \phantom{-}3 \\
&x_4 = -2
\end{aligned}
\]

Algorytm eliminacji Gaussa

Wejście:

\(n\) : liczba niewiadomych; \({n\in\mathbb{N}}\).
\(AB\) : macierz \({n\times(n+1)}\) zawierająca współczynniki \({a_{i,j}, \; i = 1\dots n; j = 1\dots n}\), oraz w kolumnie \({n+1}\) współczynniki \(b_i\) układu równań; \({AB\in\mathbb{R}}\).
\(X\) : wektor \(n\) elementowy, w którym zostaną umieszczone niewiadome \(x_i\); \({X\in\mathbb{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\in\mathbb{N}}\).
\(m\) : mnożnik, przez który będą mnożone elementy macierzy \(AB\); \({m\in\mathbb{R}}\).
\(s\) : zlicza sumę iloczynów; \({s\in\mathbb{R}}\).
\(\varepsilon\) : określa dokładność porównania z zerem; \({\varepsilon = 10^{–12}; \varepsilon\in\mathbb{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 b_iK10:   Dla j = n, n–1, …, i+1: ; od b_i odejmujemy kolejne iloczyny a_ij×x_j
       wykonuj: s ← s–AB{i, j]×X[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\times(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){-}\text{sza}}\) liczba odnosi się do wyrazu wolnego \(b\). Poniżej mamy przykładowe dane wejściowe dla programu:

Równanie:

\[
\begin{aligned}
4x_1 - 2x_2 + 4x_3 - 2x_4 &= \phantom{1}8 \\
3x_1 + \phantom{1}x_2 + 4x_3 + 2x_4 &= \phantom{1}7 \\
2x_1 + 4x_2 + 2x_3 + \phantom{1}x_4 &= 10 \\
2x_1 - 2x_2 + 4x_3 + 2x_4 &= \phantom{1}2
\end{aligned}
\]

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

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

// stała przybliżenia zera
const double eps = 1e-12

// 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
'-----------------------------

 ' stała przybliżenia zera
Const eps As Double = 1e-12

' 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  = [0 for i in range(n)]
# odczytujemy dane dla macierzy ab
for i in range(n):
    arr = input().split()
    arr = [float(arr[j]) for j in range(n+1)]
    ab.append(arr)
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
ab = None
x = None

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

do podrozdziału do strony

Eliminacja Gaussa