Ulepszona metoda eliminacji Gaussa-Crouta


Tematy pokrewne

 

Algorytm

Podstawowy algorytm rozwiązywania układu równań liniowych metodą eliminacji Gaussa może w pewnych przypadkach zawieść pomimo istnienia rozwiązania. Otóż w metodzie tej wykonywane jest dzielenie przez element macierzy współczynników AB[ ] leżący na jej diagonali. Element ten może wynosić 0. W takim przypadku obliczenia zostaną wstrzymane.

 

Przykład:

Jeśli wprowadzisz poniższe dane do formularza javascript działającego wg algorytmu eliminacji Gaussa, to otrzymasz informację, iż rozwiązanie układu równań się nie powiodło (sprawdź to koniecznie!):

 

4
0 2 3 4 49
1 0 3 4 45
1 2 0 4 36
1 2 3 0 23

 

Natomiast wprowadzenie tych samych danych do formularza javascript działającego wg wzorów Cramera daje wynik:

 

0x1 + 2x2 + 3x3 + 4x4 = 49
1x1 + 0x2 + 3x3 + 4x4 = 45
1x1 + 2x2 + 0x3 + 4x4 = 36
1x1 + 2x2 + 3x3 + 0x4 = 23
x1 = 2
x2 = 3
x3 = 5
x4 = 7

 

Rozwiązaniem tego problemu jest zmodyfikowany algorytm zwany eliminacją Gaussa-Crouta lub eliminacją z częściowym wyborem elementu podstawowego. Elementem podstawowym nazywamy element macierzy, za pomocą którego dokonujemy eliminacji zmiennej z dalszych równań. W algorytmie Gaussa elementami podstawowymi są elementy leżące na diagonali macierzy - ai,i. W metodzie zmodyfikowanej Gaussa-Crouta elementem podstawowym będzie element ai,j, który posiada największy moduł ze wszystkich współczynników w i-tym wierszu.

Aby uniknąć konieczności przestawiania kolumn, zastosujemy podobne rozwiązanie jak w algorytmie wyliczania wyznacznika macierzy - wektor kolumn. W wektorze tym umieścimy numery kolejnych kolumn. Do kolumn macierzy będziemy się odwoływać pośrednio poprzez zawartość wektora kolumn. Jeśli w wektorze kolumn przestawione zostaną numery kolumn macierzy, to będzie to równoznaczne z przestawieniem tych kolumn. Również niewiadome będą wyliczane wg zawartości tego wektora.

 

Podsumujmy:

  1. Do kolumn macierzy AB[ ] odwołujemy się poprzez wektor kolumn - WK[ ].
  2. Element podstawowy wybieramy jako element o największym module w wierszu.
  3. Po wybraniu elementu podstawowego zamieniamy w wektorze kolumn WK[ ] jego numer z numerem na pozycji i-tej. Dzięki tej operacji wybrany element znajdzie się na diagonali macierzy AB[ ].
  4. Dokonujemy eliminacji wg algorytmu Gaussa
  5. Niewiadome wyznaczamy w tablicy X[ ] wg kolumn umieszczonych w wektorze WK[ ]. Dzięki temu zachowamy spójność numeracji niewiadomych z wprowadzonymi do macierzy AB[ ] przestawieniami kolumn.

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 bi  ai,j,biR;   i,j N,   i,j = 1,2,...,n.
Macierz AB[ ] zdefiniowana została w poprzednim rozdziale.
WK[ ] - wektor kolumn zawierający n + 1 elementów równych kolejnym numerom kolumn macierzy AB[ ].

Dane wyjściowe

true: AB[ ], WK[ ] - tablicę AB[ ] współczynników zredukowano do macierzy trójkątnej. Wektor WK[ ] zawiera numerację kolumn w macierzy AB[ ].
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 GCEliminujX(n, AB[ ], WK[ ])
    K01: Dla i = 1,2,...,n - 1: wykonuj K02...K08
  K02:     k ← i
  K03:     Dla  j = i + 1, i + 2,...,njeżeli | AB[i,WK[k]] | < | AB[i,WK[j]] |, to k ← j
  K04:     WK[k] ↔ WK[i]
  K05:     Jeśli | AB[i,WK[i]] | < ε , to zwróć false i zakończ
  K06:     Dla j = i+1, i+2, ..., n: wykonuj K07... K08
K07:
        m ← -    AB[j,WK[i]]
AB[i,WK[i]]
K08:         Dla k = i+1, i+2, ..., n+1: wykonuj AB[j,WK[k]] ← AB[j,WK[k]] + m × AB[i,WK[k]]
    K09: Zwróć true i zakończ

 

Schemat blokowy

Nowy algorytm eliminacji niewiadomych jest zmodyfikowanym algorytmem eliminacji Gaussa. Dodane elementy zaznaczone zostały na schemacie blokowym kolorem żółtym. Elementy zmodyfikowane zaznaczono kolorem zielonym.

Na początku pętli nr 1 dodano fragment wyznaczający w wierszu i-tym macierzy AB[ ] element maksymalny co do modułu. Gwarantuje nam to, iż nie będzie nigdy wykonywane dzielenie przez 0 - o ile wszystkie współczynniki nie wynoszą 0 - w tym przypadku układu równań nie da się rozwiązać.

Zwróć uwagę, iż do kolumn macierzy AB[ ] odwołujemy się poprzez wektor kolumn WK[ ]. Dzięki temu rozwiązaniu kolejność kolumn macierzy AB[ ] może być dowolnie zmieniana.

Po wyznaczeniu elementu podstawowego w wektorze kolumn WK[ ] zamieniamy miejscami kolumnę i-tą z kolumną k-tą. W ten sposób element podstawowy znajdzie się w kolumnie o numerze WK[i].

Następnie sprawdzamy, czy element podstawowy wpada w otoczenie zera o promieniu epsilon. Jeśli tak, to zakładamy, iż jest on równy 0 i kończymy algorytm z błędem.

W przeciwnym razie eliminujemy z pozostałych wierszy elementy w kolumnie WK[i]. Zwróć uwagę, iż elementy te nie są zerowane, gdyż nie będą one już brały udziału w obliczeniach, stąd ich zawartość jest dla reszty algorytmu obojętna. Ważna natomiast jest zmiana pozostałych współczynników macierzy AB[ ].

Gdy pętla nr 1 zakończy działanie, macierz AB[ ] jest zredukowana do macierzy trójkątnej. Algorytm kończy działanie z sukcesem. W wektorze kolumn WK[ ] zapisane są przestawione numery kolumn macierzy AB[ ]. Informacja ta będzie potrzebna w drugiej części algorytmu przy obliczaniu wartości kolejnych zmiennych.


 

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
WK[ ] - wektor kolumn zawierający n + 1 elementów równych kolejnym numerom kolumn macierzy AB[ ].

Dane wyjściowe

true: X[ ] - tablica n-elementowa niewiadomych zawiera rozwiązania układu równań
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 GCObliczX(n, X[ ], AB[ ], WK[ ])
    K01: Dla i = n, n-1,...,1: wykonuj K02...K05
  K02:     Jeśli | AB[i,WK[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,WK[j]] × X[WK[j]]
  K05:
    X[WK[i]] -   s
AB[i,WK[i]]
    K06: Zwróć true i zakończ

 

Schemat blokowy

Algorytm obliczania niewiadomych jest dokładnie taki sam jak algorytm podany w poprzednim rozdziale. Modyfikacja polega na zmianie sposobu odwoływania się do kolumn macierzy AB[ ] oraz do wyrazów tablicy X[ ], w której wyliczone zostaną niewiadome. Teraz wykonywane jest to poprzez wektor kolumn WK[ ].

Zmiany w stosunku do oryginalnego algorytmu zaznaczono na schemacie blokowym kolorem zielonym.

Po zakończeniu działania algorytmu w tablicy X[ ] znajdują się wartości kolejnych zmiennych pierwotnego układu równań. Elementy tej tablicy są ułożone już we właściwej kolejności i możemy je bezpośrednio przetwarzać.

Zwróć uwagę na operację:

s ← AB[i,n+1]

Ostatnia, n+1-sza kolumna macierzy AB[ ] nigdy nie jest przestawiana. Zawiera ona wyrazy wolne bi układu równań. Zatem odwołanie do tej kolumny może być bezpośrednie - bez korzystania z pośrednictwa wektora kolumn WK[ ].


 

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-Crouta
---------------------------------------------------------
(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-Crouta.
//-----------------------------------------------------------
// (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;
  kwektor = array[1..MAXEQ + 1] of integer;
  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 GCEliminujX(n : integer;
                     var AB : macierz; var WK : kwektor) : boolean;
var
  i,j,k,tmp : integer;
  m         : double;
begin
  for i := 1 to n - 1 do
  begin
    k := i;
    for j := i + 1 to n do
      if abs(AB[i,WK[k]]) < abs(AB[i,WK[j]]) then k := j;
    tmp := WK[k]; WK[k] := WK[i]; WK[i] := tmp;
    if abs(AB[i,WK[i]]) < EPS then
    begin
      Result := false; exit;
    end;
    for j := i + 1 to n do
    begin
      m := -AB[j,WK[i]] / AB[i,WK[i]];
      for k := i + 1 to n + 1 do
        AB[j,WK[k]] := AB[j,WK[k]] + m * AB[i,WK[k]];
    end;
  end;
  Result := true;
end;

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

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

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

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

begin
  writeln('Uklad rownan liniowych  - metoda eliminacji Gaussa-Crouta');
  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
    begin
      WK[i] := i;  // inicjujemy wektor kolumn
      for j := 1 to n + 1 do read(f,AB[i,j]);
    end;
    WK[n + 1] := n + 1;
    closefile(f);

// Dokonujemy eliminacji oraz obliczania niewiadomych x

    writeln('---------------------------------------------------------');
    writeln('Wyniki:');
    writeln;
    if GCEliminujX(n,AB,WK) and GCObliczX(n,X,AB,WK) 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-Crouta.
//-----------------------------------------------------------
// (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 GCEliminujX(int n, double AB[][MAXEQ+1], int WK[])
{
  int    i,j,k,tmp;
  double m;

  for(i = 0; i < n - 1; i++)
  {
    for(k = i, j = i + 1; j < n; j++)
      if(fabs(AB[i][WK[k]]) < fabs(AB[i][WK[j]])) k = j;
    tmp = WK[k]; WK[k] = WK[i]; WK[i] = tmp;
    if(fabs(AB[i][WK[i]]) < EPS) return false;
    for(j = i + 1; j < n; j++)
    {
      m = -AB[j][WK[i]] / AB[i][WK[i]];
      for(k = i + 1; k <= n; k++) AB[j][WK[k]] += m * AB[i][WK[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 GCObliczX(int n, double X[], double AB[][MAXEQ+1], int WK[])
{
  int    i,j;
  double s;

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

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

int main()
{
  ifstream fin;
  ofstream fout;
  int i,j,n,WK[MAXEQ+1];
  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-Crouta\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++)
    {
      WK[i] = i; // inicjujemy wektor kolumn
      for(j = 0; j <= n; j++) fin >> AB[i][j];
    }
    WK[n] = n;
    fin.close();

// Dokonujemy eliminacji oraz obliczania niewiadomych x

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

    if(GCEliminujX(n,AB,WK) && GCObliczX(n,X,AB,WK))
    {
      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-Crouta.
'-----------------------------------------------------------
' (C)2006 mgr J.Wałaszek                     I LO w Tarnowie

Declare Function GCEliminujX(n As Integer, AB() As Double, WK() As Integer) As Integer
Declare Function GCObliczX(n As Integer, X() As Double, AB() As Double, WK() As Integer) 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, WK(MAXEQ)
Dim As Double AB(MAXEQ - 1, MAXEQ), X(MAXEQ - 1)

print "Uklad rownan liniowych  - metoda eliminacji Gaussa-Crouta"
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
      WK(i) = i    ' inicjujemy wektor kolumn
      For j = 0 To n : Input #1, AB(i, j): Next
   Next
   WK(n) = n
   Close #1

   ' Dokonujemy eliminacji oraz obliczania niewiadomych x

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

   If GCEliminujX(n, AB(), WK()) And GCObliczX(n, X(), AB(), WK()) 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 równań!"
   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 GCEliminujX(n As Integer, AB() As Double, WK() As Integer) As Integer
  Dim As Integer i, j, k
  Dim m As Double

  For i = 0 To n - 2
    k = i
    For j = i + 1 To n - 1
      If Abs(AB(i, WK(k))) < Abs(AB(i, WK(j))) Then k = j
    Next
    Swap WK(k), WK(i)
    If Abs(AB(i, WK(i))) < EPS Then Return 0
    For j = i + 1 To n - 1
      m = -AB(j, WK(i)) / AB(i, WK(i))
      For k = i + 1 To n: AB(j, WK(k)) += m * AB(i, WK(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 GCObliczX(n As Integer, X() As Double, AB() As Double, WK() As Integer) As Integer
  Dim As Integer i, j
  Dim s As Double

  For i = n - 1 To 0 Step -1
    If Abs(AB(i, WK(i))) < EPS Then Return 0
    s = AB(i, n)
    For j = n - 1 To i + 1 Step -1 : s -= AB(i, WK(j)) * X(WK(j)) : Next
    X(WK(i)) = s / AB(i, WK(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-Crouta
        </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-Crouta.
//-----------------------------------------------------------
// (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 GCEliminujX(n, AB, WK)
{
  var i,j,k,m,tmp;

  for(i = 0; i < n - 1; i++)
  {
    for(k = i, j = i + 1; j < n; j++)
      if(Math.abs(AB[i][WK[k]]) < Math.abs(AB[i][WK[j]])) k = j;
    tmp = WK[k]; WK[k] = WK[i]; WK[i] = tmp;
    if(Math.abs(AB[i][WK[i]]) < EPS) return false;
    for(j = i + 1; j < n; j++)
    {
      m = -AB[j][WK[i]] / AB[i][WK[i]];
      for(k = i + 1; k <= n; k++) AB[j][WK[k]] += m * AB[i][WK[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 GCObliczX(n, X, AB, WK)
{
  var i,j,s;

  for(i = n - 1; i >= 0; i--)
  {
    if(Math.abs(AB[i][WK[i]]) < EPS) return false;
    s = AB[i][n];
    for(j = n - 1; j > i; j--) s -= AB[i][WK[j]] * X[WK[j]];
    X[WK[i]] = s / AB[i][WK[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);
  var WK = 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);
          WK[i] = i;
          for(j = 0; j <= n; j++)
            z = z && !isNaN(AB[i][j] = parseFloat(s[k++]));
        }
        WK[n] = n;
        if(z)
        {

// Dokonujemy eliminacji oraz obliczania niewiadomych x

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

          if(GCEliminujX(n,AB,WK) && GCObliczX(n,X,AB,WK))
            for(i = 0; i < n; i++)
              t += "x<sub>" + (i + 1) + "</sub> = " + X[i] + "<br>";
          else
t += "<font color=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-Crouta

(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.