Metoda eliminacji Gaussa


Tematy pokrewne

Algorytm

Podstawową wadą metody Cramera jest konieczność liczenia wyznaczników, co jest dosyć czasochłonne. Dużo lepszym rozwiązaniem jest metoda eliminacji Gaussa. Na początku postępujemy podobnie. Mamy dany układ n równań liniowych z n niewiadomymi:

 

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

 

Pierwszy etap algorytmu zwany jest etapem eliminacji zmiennych. Od i-tego (i = 2,3,...,n) równania odejmujemy równanie pierwsze pomnożone przez ai,1 : a1,1:

 

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

 

W efekcie otrzymujemy układ równań, w którym niewiadoma x1 dla równań nr 2, 3...,n jest wyeliminowana. Współczynniki a' i b' oznaczają współczynniki powstałe po wykonaniu odejmowania.

 

a1,1x1  a1,2x2  + a1,3x3  + ...  + a1,n-1xn-1  + a1,nxn  = b1
  a'2,2x2  + a'2,3x3  + ...  + a'2,n-1xn-1  + a'2,nxn  = b'2
  a'3,2x2  + a'3,3x3 + ...  + a'3,n-1xn-1  + a'2,nxn  = b'3
  ...     ... ...     ...     ...  = ...
  a'n,2x2  + a'n,3x3 + ..   + a'n,n-1xn-1  + a'n,nxn  = b'n

 

Teraz od i-tego (i = 3,4,...,n) równania odejmujemy równanie drugie pomnożone przez a'i,2 : a'2,2. Wyeliminujemy niewiadomą x2 w równaniach poniżej równania nr 2. Przez a'' i b'' oznaczyliśmy współczynniki powstałe po wykonaniu odejmowania:

 

a1,1x1 +  a1,2x2  + a1,3x3  + ...  + a1,n-1xn-1  + a1,nxn  = b1
   a'2,2x2  + a'2,3x3  + ...  + a'2,n-1xn-1  + a'2,nxn  = b'2
        a''3,3x3 + ...  + a''3,n-1xn-1  + a''2,nxn  = b''3
        ... ...     ...     ...  = ...
        a''n,3x3  + ...  + a''n,n-1xn-1  + a''n,nxn  = b''n

 

Postępując dalej w ten sam sposób otrzymamy następujący układ równań:

 

a1,1x1  + a1,2x2  + a1,3x3  + ...   + a1,n-1xn-1  + a1,nxn  = b1
      a'2,2x2  + a'2,3x3  + ...   + a'2,n-1xn-1  + a'2,nxn  = b'2
        a''3,3x3  + ...   + a''3,n-1xn-1  + a''2,nxn  = b''3
            ...     ...  = ...
                  a'''n,nxn  = b'''n

 

Następuje etap zwany postępowaniem odwrotnym. Kolejne niewiadome wyliczamy ze wzoru rekurencyjnego:

 

xn =   b'''n
a'''n,n
xi =   b''i - a''i,nxn - ... - a''i,i+1xi+1 , dla i = n-1, n-2, ... ,1
a''i,i

 

Przykład:

Rozwiążmy podaną wyżej metodą eliminacji Gaussa następujący układ równań:

 

4x1
3
x1
2
x1
2
x1
 - 2x2
+  
x2
 + 4
x2
 - 2
x2
 + 4x3
+ 4
x3
 + 2
x3
+ 4
x3
 - 2x4
+ 2
x4
 +
x4
+ 2
x4
 =  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
3
x1 + x2 + 4x3 + 2x4 - 0,75(4x1 - 2x2 + 4x3 - 2x4) =  7 - 0,758
2
x1 + 4x2 + 2x3 + x4 - 0,5(4x1 - 2x2 + 4x3 - 2x4) = 10 - 0,58
2
x1 - 2x2 + 4x3 + 2x4 - 0,5(4x1 - 2x2 + 4x3 - 2x4) = 2 -0,58

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

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

4x1


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

 

Zwróć uwagę, iż z równań 2, 3 i 4 zniknęła niewiadoma x1. 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,5
x2 + x3 + 3,5x4 =  1
5
x2 +  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,5
x2 + x3 + 3,5x4 =  1
5
x2 +  2x4 - 5x2 - 2x3 - 7x4 = 4
-
x2 + 2x3 + 3x4 + x2 + 0,4x3 + 1,4x4 = -1,6

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

4x1


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

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

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

x1 = -1,  x2 = 2,  x3 = 3,  x4 = -2

 

Uwaga:

Metoda eliminacji Gaussa w podanej tutaj postaci nie jest niestety niezawodna. Przy odejmowaniu równań mnożymy współczynniki odejmowanego równania przez wartość będącą ilorazem odpowiednich współczynników układu równań. Może się zdarzyć, iż dzielnik ilorazu wynosi 0 (wpada w otoczenie 0 o promieniu ε). Wtedy iloraz nie istnieje i wykonywanie obliczeń należy przerwać. Rozwiązanie tego problemu podajemy w następnym rozdziale.

 

Algorytm rozwiązywania układu równań liniowych metodą eliminacji Gaussa rozbijemy na dwie części:

- etap eliminacji - macierz współczynników zostaje przemieniona w macierz trójkątną

- etap obliczania niewiadomych - na podstawie danych z macierzy trójkątnej algorytm wylicza kolejne niewiadome.

 

Algorytm eliminacji zmiennych

Dane wejściowe

n - ilość niewiadomych oraz układów równań.   n N, n < 9
AB[ ] - tablica n(n+1) elementowa zawierająca współczynniki ai,j oraz wyrazy wolne biai,j,bi R; i,j N,  i,j = 1,2,...,n.
Macierz AB[ ] zdefiniowana została w poprzednim rozdziale.

Dane wyjściowe

true: AB[ ] - tablicę współczynników zredukowano do macierzy trójkątnej
false - operacja eliminacji nie powiodła się

Zmienne pomocnicze i funkcje

i,j,k - zmienne sterujące pętli iteracyjnych    i,j,k N
m - mnożnik, przez który będą mnożone współczynniki odejmowanych równań.    m R
ε - określa dokładność porównania z zerem.    ε = 0.0000000001

 

Lista kroków

Funkcja EliminujX(n, AB[ ])
    K01: Dla i = 1,2,...,n - 1: wykonuj K02...K05
  K02:     Jeśli | AB[i,i] | < ε , to zwróć false i zakończ
  K03:     Dla j = i+1, i+2, ..., n: wykonuj K04... K05
  K04:
        m ← -    AB[j,i]
AB[i,i]
  K05:         Dla k = i+1, i+2, ..., n+1: wykonuj AB[j,k] ← AB[j,k] + m × AB[i,k]
    K06: Zwróć true i zakończ

 

Schemat blokowy

Algorytm eliminacji niewiadomych zrealizowany został w formie funkcji zwracającej wartość logiczną true, gdy eliminacja została wykonana poprawnie lub false w przypadku błędu.

Pętla nr 1 przebiega przez kolejne wiersze macierzy AB[ ] współczynników od wiersza nr 1 do n - 1 (przedostatniego). Wewnątrz pętli najpierw sprawdzamy, czy będzie można dzielić przez wyraz AB[i,i], który leży na przekątnej macierzy. Jeśli będzie to niemożliwe, to zwracamy wartość logiczną false i kończymy algorytm.

W przeciwnym razie rozpoczynamy pętlę nr 2, która odpowiednio odejmie wiersz i-ty od pozostałych wierszy macierzy. Wewnątrz tej pętli obliczamy mnożnik m, przez który będą mnożone kolejne wyrazy wiersza i-tego.

Odejmowanie wyrazów wiersza i-tego od wyrazów wiersza j-tego wykonuje pętla nr 3. Odejmowane wyrazy są mnożone przez mnożnik m (faktycznie wykonujemy tutaj dodawanie, lecz zwróć uwagę na wzór mnożnika - iloraz jest wzięty ze znakiem minus).

Działanie odejmowania jest zoptymalizowane - modyfikowane są tylko te wyrazy macierzy AB[ ], które w dalszej części algorytmu będą uczestniczyły w obliczeniach. Zatem w rzeczywistości w macierzy AB[ ] współczynniki przy eliminowanych niewiadomych nie są zerowane, lecz nie ma to większego znaczenia, gdyż wyrazy te nie uczestniczą w obliczeniach wartości niewiadomych - liczy się zmiana pozostałych wyrazów macierzy!

Gdy wszystkie pętle wykonają się do końca, algorytm zakończy się z wynikiem pozytywnym.

Operacja eliminacji niewiadomych zawiera trzy zagnieżdżone w sobie pętle, zatem ma klasę złożoności obliczeniowej równą O(n3).


 

Algorytm obliczania niewiadomych

Dane wejściowe

n - ilość niewiadomych oraz układów równań. n N, n < 9
X[ ] - tablica n-elementowa liczb rzeczywistych, w której algorytm umieści obliczone niewiadome.
AB[ ] - tablica n(n+1) elementowa zawierająca współczynniki ai,j oraz wyrazy wolne biai,j,bi R; i,j N,  i,j = 1,2,...,n

Dane wyjściowe

true: X[ ] - tablica niewiadomych zawiera rozwiązania
false - operacja wyznaczania niewiadomych nie powiodła się

Zmienne pomocnicze i funkcje

i,j - zmienne sterujące pętli iteracyjnych i,j N
s - używane do zliczania sumy iloczynów niewiadomych przez ich współczynniki. s R
ε - określa dokładność porównania z zerem. ε = 0.0000000001

 

Lista kroków

Funkcja ObliczX(n, X[ ], AB[ ])
    K01: Dla i = n, n-1,...,1: wykonuj K02...K05
  K02:     Jeśli | AB[i,i] | < ε , to zwróć false i zakończ
  K03:     s ← AB[i,n+1]
  K04:     Dla j = n, n-1, ..., i + 1: wykonuj s ← s - AB[i,j] × X[j]
  K05:
    X[i] -   s
AB[i,i]
    K06: Zwróć true i zakończ

 

Schemat blokowy

Algorytm wyznaczania niewiadomych układu równań bazuje na wcześniejszym algorytmie eliminacji, który przygotowuje w odpowiedni sposób macierz współczynników.

Wyznaczanie niewiadomych rozpoczynamy od ostatniej niewiadomej xn. Zadanie to realizuje pętla nr 1, która przebiega wartości w kierunku odwrotnym - od n do 1. Przy każdym obiegu wyznaczana jest kolejna niewiadoma.

Wyliczanie xi wymaga dzielenia przez współczynnik ai,i stojący przy tej niewiadomej. Jeśli wpada on w otoczenie ε zera, to algorytm kończymy z wynikiem negatywnym.

Niewiadomą xi zawsze wyliczamy z równania:

 

aiixi + aii+1xi+1 + ... + ainxn = bi

 

gdzie niewiadome xi+1, ..., xn zostały wyznaczone w poprzednich obiegach pętli nr 1.  W zmiennej s obliczamy wartość:

 

s = bi - ainxn - ... - aii+1xi+1

 

Zadanie to realizuje pętla nr 2. Po wyznaczeniu wartości s możemy wyliczyć niewiadomą xi dzieląc s przez współczynnik aii.

Gdy pętla nr 1 zakończy działanie w tablicy X[ ] mamy obliczone kolejne niewiadome zadanego układu równań. Algorytm kończymy.

Ponieważ w algorytmie występują dwie zagnieżdżone pętle, to jego klasa złożoności obliczeniowej wynosi O(n2).

Pełny algorytm wykorzystuje podane wyżej dwa algorytmy częściowe w następujący sposób:

 

Lista kroków

K01: Czytaj n oraz współczynniki do tablicy AB[ ]
K02: Jeśli EliminujX(n,AB[ ]) = false, to idź do K05
K03: Jeśli ObliczX(n,X[ ],AB[ ]) = false, to idź do K05
K04: Pisz X[ ] i zakończ
K05: Pisz "Rozwiązanie układu równań nie powiodło się"
K06: Zakończ

 

Programy

Z uwagi na uciążliwość wprowadzania danych z klawiatury programy odczytują dane z pliku in.txt i zapisują wyniki do pliku out.txt. Pliki znajdują się w bieżącym katalogu. Plik in.txt powinien posiadać następującą strukturę:

W pierwszym wierszu liczba od 1 do 100 (jeśli chcesz obliczać układy równań o większej liczbie niewiadomych, to musisz odpowiednio zmodyfikować program) określająca ilość równań, czyli n. Jednakże uważaj - zapotrzebowanie na pamięć wzrasta z kwadratem liczby elementów. Również czas obliczeń jest proporcjonalny do sześcianu z n.

W następnych n wierszach powinny być umieszczone współczynniki. Jeden wiersz określa współczynniki jednego równania. Kolejne współczynniki powinny być od siebie oddzielone przynajmniej jedną spacją. Pierwsze n współczynników odnosi się do współczynników przy kolejnych niewiadomych. Ostatni (n+1)-szy współczynnik określa wyraz wolny bi. Programy uruchomiono z plikiem in.txt o następującej zawartości:

 

5
2 -2  2 -7  6 -4
7 -3 -2  7  2 11
2  2 -1  1  4  9
9  8 -2  2 -2 21
4  8 -3  3 -1 16

 

Plik określa układ 5 równań liniowych:

 

2x1 - 2x2  +  2x3 - 7x4  +  6x5 =   -4
7x1 - 3x2 - 2x3  +  7x4  +  2x5  =  11
2x1  +  2x2 - x3  +  x4  +  4x5  =    9
9x1  +  8x2 - 2x3  +  2x4 - 2x5  =  21
4x1  +  8x2 - 3x3  +  3x4 - x5  =  16

 

Efekt uruchomienia programu
Układ równań liniowych  - metoda eliminacji Gaussa
--------------------------------------------------
(C)2006 mgr Jerzy Wałaszek         I LO w Tarnowie


--------------------------------------------------
Wyniki:

x1 =      1,00000
x2 =      2,00000
x3 =      3,00000
x4 =      2,00000
x5 =      1,00000

--------------------------------------------------
Koniec. Naciśnij klawisz Enter...

 

Free Pascal
// Program rozwiązuje układ równań liniowych o n niewiadomych
// za pomocą metody eliminacji Gaussa.
//-----------------------------------------------------------
// (C)2006 mgr J.Wałaszek                     I LO w Tarnowie

program mzfl5;

const
  EPS   = 0.0000000001; // dokładność porównania z zerem
  MAXEQ = 100;          // maksymalna ilość równań w układzie

type
  xwektor = array[1..MAXEQ] of double;
  macierz = array[1..MAXEQ,1..MAXEQ + 1] of double;

// Funkcja dokonująca eliminacji niewiadomych. Jeśli operacja
// się powiedzie, zwraca true. Inaczej zwraca false.

function EliminujX(n : integer; var AB : macierz) : boolean;
var
  i,j,k : integer;
  m     : double;
begin
  for i := 1 to n - 1 do
  begin
    if abs(AB[i,i]) < EPS then
    begin
      Result := false; exit;
    end;
    for j := i + 1 to n do
    begin
      m := -AB[j,i] / AB[i,i];
      for k := i + 1 to n + 1 do AB[j,k] := AB[j,k] + m * AB[i,k];
    end;
  end;
  Result := true;
end;

// Funkcja oblicza kolejne niewiadome x z macierzy AB
// przetworzonej przez funkcję Eliminuj_X().
// Jeśli operacja się powiedzie, zwraca true. Inaczej
// zwraca false.

function ObliczX(n : integer; var X : xwektor; var AB : macierz) : boolean;
var
  i,j : integer;
  s   : double;
begin
  for i := n downto 1 do
  begin
    if abs(AB[i,i]) < EPS then
    begin
      Result := false; exit;
    end;
    s := AB[i,n + 1];
    for j := n downto i + 1 do s := s - AB[i,j] * X[j];
    X[i] := s / AB[i,i];
  end;
  Result := true;
end;

//-----------------------------------------------------
// Program główny
//-----------------------------------------------------

var
  f     : Text;
  i,j,n : integer;
  AB    : macierz;
  X     : xwektor;

begin
  writeln('Uklad rownan liniowych  - metoda eliminacji Gaussa');
  writeln('--------------------------------------------------');
  writeln('(C)2006 mgr Jerzy Walaszek         I LO w Tarnowie');
  writeln;

// Dane dla programu odczytujemy z pliku tekstowego o nazwie in.txt,
// który musi się znajdować w tym samym katalogu co program
// Pierwszy wiersz pliku powinien zawierać liczbę n
// Następne n kolejnych wierszy powinno zawierać współczynniki ai dla
// tego wiersza, a na końcu współczynnik bi. Kolejne współczynniki
// oddzielone są od siebie przynajmniej jedną spacją.

  assignfile(f,'in.txt');
  reset(f);
  readln(f,n);
  if n <= MAXEQ then
  begin
    for i := 1 to n do
      for j := 1 to n + 1 do read(f,AB[i,j]);
    closefile(f);

// Dokonujemy eliminacji oraz obliczania niewiadomych x

    writeln('--------------------------------------------------');
    writeln('Wyniki:');
    writeln;
    if EliminujX(n,AB) and ObliczX(n,X,AB) then
    begin
      assignfile(f,'out.txt');
      rewrite(f);
      for i := 1 to n do
      begin
        writeln('x',i,' = ',X[i]:12:5);
        writeln(f,X[i]);
      end;
      closefile(f);
    end
    else writeln('Rozwiazanie ukladu rownan nie powiodlo sie');
  end
  else
  begin
    writeln('Zbyt wiele rownan!');
    closefile(f);
  end;
  writeln;
  writeln('--------------------------------------------------');
  writeln('Koniec. Nacisnij klawisz Enter...');
  readln;
end.
Code::Blocks
// Program rozwiązuje układ równań liniowych o n niewiadomych
// za pomocą metody eliminacji Gaussa.
//-----------------------------------------------------------
// (C)2006 mgr J.Wałaszek                     I LO w Tarnowie

#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <cstdlib>

using namespace std;

const double EPS   = 0.0000000001; // dokładność porównania z zerem
const int    MAXEQ = 100;          // maksymalna ilość równań w układzie

// Funkcja dokonująca eliminacji niewiadomych. Jeśli operacja
// się powiedzie, zwraca true. Inaczej zwraca false.

bool EliminujX(int n, double AB[][MAXEQ+1])
{
  int    i,j,k;
  double m;

  for(i = 0; i < n - 1; i++)
  {
    if(fabs(AB[i][i]) < EPS) return false;
    for(j = i + 1; j < n; j++)
    {
      m = -AB[j][i] / AB[i][i];
      for(k = i + 1; k <= n; k++) AB[j][k] += m * AB[i][k];
    }
  }
  return true;
}

// Funkcja oblicza kolejne niewiadome x z macierzy AB
// przetworzonej przez funkcję Eliminuj_X().
// Jeśli operacja się powiedzie, zwraca true. Inaczej
// zwraca false.

bool ObliczX(int n, double X[], double AB[][MAXEQ+1])
{
  int    i,j;
  double s;

  for(i = n - 1; i >= 0; i--)
  {
    if(fabs(AB[i][i]) < EPS) return false;
    s = AB[i][n];
    for(j = n - 1; j > i; j--) s -= AB[i][j] * X[j];
    X[i] = s / AB[i][i];
  }
  return true;
}

//-----------------------------------------------------
// Program główny
//-----------------------------------------------------

int main()
{
  ifstream fin;
  ofstream fout;
  int i,j,n;
  double AB[MAXEQ][MAXEQ+1], X[MAXEQ];

  cout << setprecision(5)     // 5 cyfr po przecinku
       << fixed;              // format stałoprzecinkowy

  cout << "Uklad rownan liniowych  - metoda eliminacji Gaussa\n"
          "--------------------------------------------------\n"
          "(C)2006 mgr Jerzy Walaszek         I LO w Tarnowie\n\n";

// Dane dla programu odczytujemy z pliku tekstowego o nazwie in.txt,
// który musi się znajdować w tym samym katalogu co program
// Pierwszy wiersz pliku powinien zawierać liczbę n
// Następne n kolejnych wierszy powinno zawierać współczynniki ai dla
// tego wiersza, a na końcu współczynnik bi. Kolejne współczynniki
// oddzielone są od siebie przynajmniej jedną spacją.

  fin.open("in.txt");
  fin >> n;
  if(n <= MAXEQ)
  {
    for(i = 0; i < n; i++)
      for(j = 0; j <= n; j++) fin >> AB[i][j];
    fin.close();

// Dokonujemy eliminacji oraz obliczania niewiadomych x

    cout << "\n--------------------------------------------------\n"
            "Wyniki:\n\n";

    if(EliminujX(n,AB) && ObliczX(n,X,AB))
    {
      fout.open("out.txt");
      for(i = 0; i < n; i++)
      {
        cout << "x" << i + 1 << " = " << setw(12) << X[i] << endl;
        fout << X[i] << endl;
      }
      fout.close();
    }
    else cout << "Rozwiazanie ukladu rownan nie powiodlo sie\n";
  }
  else
  {
    fin.close();
    cout << "Zbyt wiele rownan!\n";
  }
  cout << "\n--------------------------------------------------\n\n";
  system("pause");
  return 0;
}
FreeBASIC
' Program rozwiązuje układ równań liniowych o n niewiadomych
' za pomocą metody eliminacji Gaussa.
'-----------------------------------------------------------
' (C)2006 mgr J.Wałaszek                     I LO w Tarnowie

Declare Function EliminujX(n As Integer, AB() As Double) As Integer
Declare Function ObliczX(n As Integer, X() As Double, AB() As Double) As Integer

Const EPS As Double = 0.0000000001 ' dokładność porównania z zerem
Const MAXEQ As Integer = 100       ' maksymalna ilość równań w układzie

'-----------------------------------------------------
' Program główny
'-----------------------------------------------------

Dim As integer i, j, n
Dim As double AB(MAXEQ - 1, MAXEQ), X(MAXEQ - 1)

print "Uklad rownan liniowych  - metoda eliminacji Gaussa"
print "--------------------------------------------------"
print "(C)2006 mgr Jerzy Walaszek         I LO w Tarnowie"
Print

' Dane dla programu odczytujemy z pliku tekstowego o nazwie  in.txt,
' który musi się znajdować w tym samym katalogu co program
' Pierwszy wiersz pliku powinien zawierać liczbę n
' Następne n kolejnych wierszy powinno zawierać współczynniki ai dla
' tego wiersza, a na końcu współczynnik bi. Kolejne współczynniki
' oddzielone są od siebie przynajmniej jedną spacją.

Open "in.txt" For Input as #1
Input #1, n
If n <= MAXEQ Then
  For i = 0 To n - 1
    For j = 0 To n
      Input #1, AB(i, j)
    Next
  Next
  Close #1

  ' Dokonujemy eliminacji oraz obliczania niewiadomych x

  Print
  print "--------------------------------------------------"
  print "Wyniki:"
  Print

  If EliminujX(n, AB()) And ObliczX(n, X(), AB()) Then
    Open "out.txt" For Output as #1

    ' Wypisujemy wyniki do okna konsoli oraz do pliku out.txt

    For i = 0 To n - 1
      print Using "x{##} = ######.#####"; i + 1; X(i)
      print #1,Using "x{##} = ######.#####"; i + 1; X(i)
    Next
    Close #1
  Else
    print "Rozwiazanie ukladu rownan nie powiodlo sie"
  End If
Else
  print "Zbyt wiele rownan!"
  Close #1
End If

Print
print "--------------------------------------------------"
Print
print "Koniec. Nacisnij klawisz Enter..."

Sleep

End

' Funkcja dokonująca eliminacji niewiadomych. Jeśli operacja
' się powiedzie, zwraca true. Inaczej zwraca false.

Function EliminujX(n As Integer, AB() As Double) As Integer
  Dim As Integer i, j, k
  Dim m As Double

  For i = 0 To n - 2
    If Abs(AB(i, i)) < EPS Then Return 0
    For j = i + 1 To n - 1
      m = -AB(j, i) / AB(i, i)
      For k = i + 1 To n : AB(j, k) += m * AB(i, k) : Next
    Next
  Next
  Return 1
End Function

' Funkcja oblicza kolejne niewiadome x z macierzy AB
' przetworzonej przez funkcję Eliminuj_X().
' Jeśli operacja się powiedzie, zwraca true. Inaczej
' zwraca false.

Function ObliczX(n As Integer, X() As Double, AB() As Double) As Integer
  Dim As Integer i, j
  Dim s As Double

  For i = n - 1 To 0 Step -1
    If Abs(AB(i, i)) < EPS Then Return 0
    s = AB(i, n)
    For j = n - 1 To i + 1 Step -1 : s -= AB(i, j) * X(j) : Next
    X(i) = s / AB(i, i)
  Next
  Return 1
End Function
JavaScript
<html>
  <head>
  </head>
  <body>
    <div align="center">
      <form style="BORDER-RIGHT: #ff9933 1px outset; PADDING-RIGHT: 4px;
                   BORDER-TOP: #ff9933 1px outset; PADDING-LEFT: 4px;
                   PADDING-BOTTOM: 1px; BORDER-LEFT: #ff9933 1px outset;
                   PADDING-TOP: 1px; BORDER-BOTTOM: #ff9933 1px outset;
                   BACKGROUND-COLOR: #ffcc66" name="frmbincode">
        <h3 style="TEXT-ALIGN: center">
          Demonstracja rozwiązywania układu równań<br>
          metodą eliminacji Gaussa
        </h3>
        <p style="TEXT-ALIGN: center">
          (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
        </p>
        <hr>
        <p style="TEXT-ALIGN: center">
          Tutaj wprowadź wiersze ze współczynnikami układu równań:
        </p>
        <p style="TEXT-ALIGN: center">
          <textarea rows="9" name="input" cols="70">5
2 -2  2 -7  6 -4
7 -3 -2  7  2 11
2  2 -1  1  4  9
9  8 -2  2 -2 21
4  8 -3  3 -1 16</textarea>
        </p>
        <p style="TEXT-ALIGN: center">
          <input type="button" value="Rozwiąż układ równań"
                 name="B1" onclick="main()">
        </p>
        <div id="out" align=center>...</div>
      </form>

<script language=javascript>

// Program rozwiązuje układ równań liniowych o n niewiadomych
// za pomocą metody eliminacji Gaussa.
//-----------------------------------------------------------
// (C)2006 mgr J.Wałaszek                     I LO w Tarnowie

var EPS   = 0.0000000001; // dokładność porównania z zerem
var MAXEQ = 100;          // maksymalna ilość równań w układzie

// Funkcja dokonująca eliminacji niewiadomych. Jeśli operacja
// się powiedzie, zwraca true. Inaczej zwraca false.

function EliminujX(n, AB)
{
  var i,j,k,m;

  for(i = 0; i < n - 1; i++)
  {
    if(Math.abs(AB[i][i]) < EPS) return false;
    for(j = i + 1; j < n; j++)
    {
      m = -AB[j][i] / AB[i][i];
      for(k = i + 1; k <= n; k++) AB[j][k] += m * AB[i][k];
    }
  }
  return true;
}

// Funkcja oblicza kolejne niewiadome x z macierzy AB
// przetworzonej przez funkcję Eliminuj_X().
// Jeśli operacja się powiedzie, zwraca true. Inaczej
// zwraca false.

function ObliczX(n, X, AB)
{
  var i,j,s;

  for(i = n - 1; i >= 0; i--)
  {
    if(Math.abs(AB[i][i]) < EPS) return false;
    s = AB[i][n];
    for(j = n - 1; j > i; j--) s -= AB[i][j] * X[j];
    X[i] = s / AB[i][i];
  }
  return true;
}

//-----------------------------------------------------
// Program główny
//-----------------------------------------------------

function main()
{
  var i,j,n,s,t,z;
  var AB = new Array(MAXEQ);
  var X =  new Array(MAXEQ);

// Dane dla programu odczytujemy z pola tekstowego.
// Pierwszy wiersz pola powinien zawierać liczbę n
// Następne n kolejnych wierszy powinno zawierać współczynniki ai dla
// tego wiersza, a na końcu współczynnik bi. Kolejne współczynniki
// oddzielone są od siebie przynajmniej jedną spacją.

  t = "<font color=red><b>Złe dane</b></font>";
  s = document.frmbincode.input.value;
  if(s.length > 0)
  {

// Odczytujemy współczynniki z pola tekstowego formularza

    while((j = s.indexOf('\n')) != -1)
      s = s.substring(0,j) + " " + s.substring(j + 1,s.length);
    while((j = s.indexOf('\r')) != -1)
      s = s.substring(0,j) + " " + s.substring(j + 1,s.length);
    while((j = s.indexOf('\t')) != -1)
      s = s.substring(0,j) + " " + s.substring(j + 1,s.length);
    while(s.length > 0 && (s.charAt(0) == " "))
      s = s.substring(1,s.length);
    while(s.length > 0 && (s.charAt(s.length-1) == " "))
      s = s.substring(0,s.length - 1);
    while(s.length > 0 && ((j = s.indexOf("  ")) != -1))
      s = s.substring(0,j) + s.substring(j+1,s.length);
    s = s.split(' ');
    if(s.length > 0)
    {
      n = parseInt(s[0]);
      if((!isNaN(n)) && (s.length >= n * (n + 1) + 1) && (n <= MAXEQ))
      {
        k = 1; z = true;
        for(i = 0; i < n; i++)
        {
          AB[i] = new Array(n + 1);
          for(j = 0; j <= n; j++)
            z = z && !isNaN(AB[i][j] = parseFloat(s[k++]));
        }
        if(z)
        {

// Dokonujemy eliminacji oraz obliczania niewiadomych x

t = "<table border='0' cellpadding='4' style='border-collapse: collapse'><tr><td>";

          if(EliminujX(n,AB) && ObliczX(n,X,AB))
            for(i = 0; i < n; i++)
              t += "x<sub>" + (i + 1) + "</sub> = " + X[i] + "<br>";
          else
t += "<font colo=red><b>Rozwiązanie układu równań nie powiodło się</b></font>";
          t += "</td></tr></table>";      
        }
      }
    }
  }
  document.getElementById("out").innerHTML = t;
}

</script>
    </div>
  </body>
</html>

 

Tutaj możesz przetestować działanie prezentowanego skryptu:

Demonstracja rozwiązywania układu równań
metodą eliminacji Gaussa

(C)2006 mgr Jerzy Wałaszek I LO w Tarnowie


Tutaj wprowadź wiersze ze współczynnikami układu równań:


...


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.