Rozwiązywanie układów równań liniowych metodą eliminacji Gaussa

Algorytm eliminacji Gaussa

Linki:
http://pl.wikipedia.org/wiki/Metoda_eliminacji_Gaussa    http://edu.i-lo.tarnow.pl/inf/alg/005_root/0006.php    http://www.imio.polsl.pl/Dopobrania/Uklady_rownan.pdf     http://mors.sggw.waw.pl/~astrasburger/ALIGA/wyklad_27_02.pdf    http://www.mif.pg.gda.pl/kmd/magda/pdfy/uklady_rownan.pdf  


Metoda eliminacji Gaussa  wg http://pl.wikipedia.org/wiki/Metoda_eliminacji_Gaussa
– w algebrze liniowej algorytm rozwiązywania układów równań liniowych, obliczania rzędu macierzy, obliczania macierzy odwrotnej oraz obliczania wartości wyznacznika,
wykorzystujący operacje elementarne; jego nazwa pochodzi od nazwiska matematyka niemieckiego Carla Friedricha Gaussa.

Obliczając rząd macierzy metodą Gaussa, należy za pomocą operacji elementarnych na wierszach sprowadzić macierz do macierzy schodkowej.
Wtedy wszystkie niezerowe wiersze są liniowo niezależne i można łatwo odczytać rząd macierzy.

Rozwiązywanie układów równań liniowych
a[i,1])*x1 + a[i,2]*x2 + ...a[i,N]*xN  =  b[i];    i = 1..n 

Rozwiązując układ m równań liniowych z n niewiadomymi należy, za pomocą operacji elementarnych wyłącznie na wierszach, sprowadzić macierz rozszerzoną układu równań liniowych do postaci schodkowej.
Następnie należy rozstrzygnąć istnienie rozwiązań układu z pomocą twierdzenia Kroneckera-Capellego. 
Jeżeli układ nie jest sprzeczny, to zbiór rozwiązań układu wyjściowego jest równy zbiorowi rozwiązań układu reprezentowanego przez powstałą schodkową macierz rozszerzoną.
Sprowadzając do postaci schodkowej (za pomocą operacji kolejno: odjęcia wielokrotności 1. wiersza od 2., 3. i 4. wiersza, zamienienia 2. i 3. wiersza, odjęcia 2. wiersza od 4. wiersza, odjęciu 3. wiersza od 4. wiersza):
Tworzymy macierz główną  C = AB[] złożoną z układu współczynników równań i wyrazów wolnych
Przekształcamy macierz C do macierzy trójkątnej.
Rozwiązujemy trójkątny układ równań, poczynając od ostatniej niewiadomej (z ostatniego równania), kolejno obliczone niewiadome podstawiamy do wyżej połozonych równań (o zwiększajacej się ilości niewiadomych).
Od wiersza 2 odeejmujemy wiersz pierwszy pomnozony przez a2,1/a1,1
Od wiersza 3 odeejmujemy wiersz pierwszy pomnozony przez a3,1/a1,1
Ogólnie od wiersza i odejmujemy równanie pierwsze pomnożone przez ai,1/a1,1.
W ten sposób niewiadoma x1 dla równań 2, 3 ... n jest wyeliminowana.
Następnie od równania i  (i = 3, 4 ... n) odejmujemy równanie 2-gie pomnożone przez a'i,2/a'2,2, gdzie a' - współczynniki powstałe po I eliminacji.
Metodę powtarzamy dla następnych równań.

Algorytm obliczeń w pseudokodzie (Pascal)

Dany układ równań:
a[i,1])*x1 + a[i,2]*x2 + ...a[i,N]*xN  =  b[i];    i = 1..n 

Zapis redukcji - eliminacji zmiennych
Oznaczenia:  ma[]  = C = AB[] -  macierz złożona ze współczynników a  i kolumny wyrazów wolnych b  
mn = m -  mnożnik stosowany przy redukcji (kolejnej eliminacji  niewiadomych)

for i:=1 to n do
  begin {i}
 // { 'Eliminacja zmiennej x[',i,']'); }
   for j:=i+1 to n do
    begin  {j}
      mn:=ma[j,i]/ma[i,i];
          for k:=i to n+1 do
           begin  //  k
            ma[j,k]:=ma[j,k]-ma[i,k]*mn;
           end;  // k
     end; {j}
 end; {i}

Obliczenie niewiadomych
Oznaczenia: wx[i] = x[i] - niewiadome, ma[] = C'[] = A'B'[] - macierz współczynników a'  i wyrazów wolnych  b' po eliminacji zmiennych.

 wx[n]:=ma[n,n+1]/ma[n,n]; // ostatnia niewiadoma
 for i:= n-1 downto 1 do
  begin {i}
   s:=0;
   for k:=i+1 to n do s:=s+ma[i,k]*wx[k];  
   wx[i]:=(ma[i,n+1]-s)/ma[i,i];
  end; {i}

Opis danych

Dane zapisuje się w oknie tekstowym programu.
W programie wprowadzone są do okna tekstowego dane dla układu równań liniowych o 4 niewiadomych.
Dane mozna też skopiować z pliku tekstowego lub wkleić do schowka i zapisac do pliku.
W pierwszym wierszu  wpisujemy  ilość rownan N (równa ilosci niewiadomych)
W kolejnych wierszach - wspołczynniki a[i]  rownań i wyrazy wolne b[i]  (liczby po prawej stronie równania)
Liczby powinny być oddzielone od siebie przynajmniej jedną spacją.
Dane: liczby calkowite lub liczby z kropka dziesietna

Układ moze nie miec rozwiazania.
Twierdzenie Kroneckera-Capellego - uklad rownan ma rozwiazania wtedy i tylko wtedy
gdy rzad macierzy glownej (wspolczynniki przy niewiadomych) rowny jest rzedowi macierzy uzupelnionej o wyrazy wolne.

Przykład obliczeń

Dane:
4
4 -1 -1 0 1
-1 4 0 -1 2
-1 0 4 -1 0
0 -1 -1 4 1

Wyniki obliczeń (wykonane innymi programami zamieszczonym na stronie) :

1) Z programu w Pascalu   (dane i wyniki zaokraglone do 3 miejsc)

Rozwiazanie ukladu rownan liniowych met. eliminacji Gaussa
================================================================

Ilosc niewiadomych  n=4

Dane: wspolczynniki i wyrazy wolne
         4.0000        -1.0000        -1.0000         0.0000         1.0000
        -1.0000         4.0000         0.0000        -1.0000         2.0000
        -1.0000         0.0000         4.0000        -1.0000         0.0000
         0.0000        -1.0000        -1.0000         4.0000         1.0000

Uklad rownan po redukcji
  4.000 -1.000 -1.000  0.000  1.000
  0.000  3.750 -0.250 -1.000  2.250
  0.000  0.000  3.733 -1.067  0.400
  0.000  0.000 -0.000  3.429  1.714

Niewiadome:
x(1) =          0.5000
x(2) =          0.7500
x(3) =          0.2500
x(4) =          0.5000


2) Z programu w Basicu (dane i wyniki zaokraglone do 3 miejsc)

ROZWIAZANIE UKLADU ROWNAN LINIOWYCH  METODA GAUSSA

A(i,1)*X(1) + A(i,2)*X(2) + A(i,n)*X(n) = B(i), i = 1..n

Dane

Ilosc niewiadomych =  4
A( 1 , 1 )=   4.000    A( 1 , 2 )=  -1.000    A( 1 , 3 )=  -1.000    A( 1 , 4 )=   0.000    B( 1 )=    1.000
A( 2 , 1 )=  -1.000    A( 2 , 2 )=   4.000    A( 2 , 3 )=   0.000    A( 2 , 4 )=  -1.000    B( 2 )=    2.000
A( 3 , 1 )=  -1.000    A( 3 , 2 )=   0.000    A( 3 , 3 )=   4.000    A( 3 , 4 )=  -1.000    B( 3 )=    0.000
A( 4 , 1 )=   0.000    A( 4 , 2 )=  -1.000    A( 4 , 3 )=  -1.000    A( 4 , 4 )=   4.000    B( 4 )=    1.000

Obliczenia

ZEROWANIE SCHODKOWE
A( 2 ,  1 )=   0.000   A( 2 ,  2 )=   3.750   A( 2 ,  3 )=  -0.250   A( 2 ,  4 )=  -1.000   B( 2 )=   2.250
A( 3 ,  1 )=   0.000   A( 3 ,  2 )=  -0.250   A( 3 ,  3 )=   3.750   A( 3 ,  4 )=  -1.000   B( 3 )=   0.250
A( 3 ,  2 )=  -0.000   A( 3 ,  3 )=   3.733   A( 3 ,  4 )=  -1.067   B( 3 )=   0.400
A( 4 ,  2 )=  -0.000   A( 4 ,  3 )=  -1.067   A( 4 ,  4 )=   3.733   B( 4 )=   1.600
A( 4 ,  3 )=  -0.000   A( 4 ,  4 )=   3.429   B( 4 )=   1.714

Obliczone niewiadome

x( 1 ) =    0.500
x( 2 ) =    0.750
x( 3 ) =    0.250
x( 4 ) =    0.500



Opis algorytmu met. Gaussa.

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

 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

Metoda eliminacji Gaussa w podanej tutaj postaci nie zawsze jest  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 i wtedy wykonywanie obliczeń należy przerwać.