Rozwiązywanie układów równań liniowych - Metoda eliminacji Gaussa.

Metoda ta jak sama nazwa wskazuje polega na eliminowaniu poszczególnych zmiennych oraz równań. Proces eliminacji prowadzony jest w znany sposób przez wzynaczanie "wartości" jednej zmiennej z jednego równania i wstawianie jej do pozostałych równań. Następnie prowadzony jest proces odwrotny, w którym wyznaczane są dopiero wartości poszczególnych niewiadomych układu równań.
Metoda w swojej normalnej postaci jest skuteczna prawie zawsze gdy elementy macierzy współczynników na jej głównej przekątnej nie są równe zeru. W przeciwnym przypadku stosowane są jej modyfikacje z częściowym i pełnym wyborem elementu macierzy. Poniższe ilustracje przedstawiają proces eliminacji oraz proces odwrotny z ich opisem.

Weźmy pod uwagę układ równań z n- niewiadomymi. Na początek wyznaczymy "wartość" pierwszej niewiadomej x₁.

Wyznaczenie zmiennej Eliminacja zmiennej 

Tak wyznaczoną wartość x₁ wstawiamy do pozostałych równań (w przykładzie podstawiłem do drugiego równania) i w ten sposób wyeliminowaliśmy jedną z niewiadomych tego układu równań, a tym samy jedno równanie mniej (nie jest ono usuwane - pozostaje w pamięci by móc wyznaczyć później z jego pomocą niewiadome układu równań). Powstaje w ten sposób nam układ z n-1 niewiadomymi o współczynnikach z indeksem 1 (indeks oznacza nam kolejne działania eliminacji) i n-1 równaniami (rysunek niżej).

Układ po pierwszej eliminacji

Proces eliminacji powtarzamy do momentu aż pozostanie nam jedno równanie i jedna niewiadoma - czyli n-1 razy. Efektywność tego procesu zapewnia nam poniższy wzór (dla potrzeb programu wyrazy wolne b₁,...,b_n zapisujemy w n+1 kolumnie macierzy współczynników).

Układ po procesie eliminacji Wzór rekurencyjny

Teraz gdy otrzymaliśmy już jedno równanie z jedną niewiadomą nic nie stoi na przeszkodzie by ją wyznaczyć. Kolejne niewiadome od przedostatniej do pierwszej (kolejność odwrotna) wyznaczamy podstawiając do kolejnych równań (od przedostatniego do pierwszego) co dopiero wyznaczone wcześniej niewiadome.

Wyznaczenie Zmiennych 

W czasie dokonywania eliminacji jak i przy wyznaczaniu zmiennych występuje nam dzielenie. Zmusza nas ono do sprawdzenia czy współczynnik będący dzielnikiem jest różny od zera. W przeciwnym przypadku (gdy taka sytuacja nastąpi) musimy przerwać proces i zakończyć obliczenia. Jest to jedyna wada tej metody - elementy macierzy przed i po procesie eliminacji na jej głównej przekątnej muszą być różne od zera.
Po procesie eliminacji warunek ten sprawdzamy obliczając wyznacznik macierzy współczynników równania. Wyznacza się go mnożąc ze sobą elementy macierzy występujące na jej głównej przekątnej.

procedure elimgaussa;
var i,j,k,n: integer;
  sum,det: real;
  a: array [1..10,1..11] of real; //Macierz współczynników plus 1 kolumna dla wyrazów wolnych
  x: array [1..10] of real; //tablica niewiadomych
Label kon;
begin
{W tym miejscu procedury należy wczytać ilość równań n oraz dane do macierzy a (ewentualnie wczytać je wcześniej)}

  for k:=1 to n-1 do
  for i:=k+1 to n do
  for j:=k+1 to n+1 do
  if a[k,k]<>0 then //ten warunek sprawdza czy współczynniki nie są równe 0
  a[i,j]:=a[i,j]-(a[k,j]*a[i,k])/a[k,k] //jeśli nie
  else goto kon; //gdy tak przerywa obliczenia
{Gdy współczynnik będzie równy 0 nie wystąpi dzielenie przez 0 i program nam się nie wysypie.}

  det:=1;
  for i:=1 to n do det:=det*a[i,i]; //wyznaczamy wyznacznik macierzy współczynników

{Obliczony wyznacznik sprawdzamy czy nie jest zbyt mały. Poniższy warunek daje nam zabezpieczenie przed wystąpieniem błędów obliczeń - złe uwarunkowanie układu równań, lub jak wiadomo gdy wyznacznik jest równy zeru układ nie posiada rozwiązań. Jeśli jest wszystko ok to wyznaczamy niewiadome układu równań.}

  if Abs(det)>1e-8 then
  begin
    x[n]:=a[n,n+1]/a[n,n];
    for i:=n-1 downto 1 do
    begin
      sum:=0;
      for j:=i+1 to n do
      sum:=sum+a[i,j]*x[j];
      x[i]:=(a[i,n+1]-sum)/a[i,i];
    end;
  end;
//W tym miejscu możesz odczytać wyniki obliczeń
  kon:
end;

Ta niewielka procedura w zupełności pozwala na prowadzenie wielu obliczeń. Nawet gdy niektóre współczynniki są równe 0 wystarczy zamienić równania miejscami i spokojnie można kontynuować obliczenia. Przy okazji wyznaczamy także wyznacznik macieży współczynników. Metoda ta należy do metod dokładnych i szybkich, a stosując dodatkowe modyfikacje jest bardzo efektywna.

Metoda eliminacji Gaussa z częściowym wyborem elementu podstawowego

Ta modyfikacja polega na wybraniu przed każdym krokiem eliminacji takiego równania, w którym pierwszy element jest największy co do wartości, w porównaniu z pozostałymi równaniami. Następnie sprawdzamy czy element ten jest równy zeru, jeśli tak to przerywamy dalsze obliczenia. Jeśli znaleźliśmy takie równanie to zamieniamy je z naszym bieżącym i po tym kroku dokonujemy kolejnej eliminacji. Zamieniając równania miejscami dokonujemy zamiany znaków w jednym z nich aby wyznacznik był równy z wyznacznikiem układu wejściowego Poniżej przedstawiam fragment kodu, który należy wstawić do poprzedniej procedury.

for k:=1 to n-1 do //po tym wierszu wklejamy poniższy kod

max:=0; w:=k;
for i:=k to n do
if max<Abs(a[i,k]) then //sprawdzamy czy dany współczynnik jest większy od max
begin //i jeśli tak to zapamiętujemy numer równania i oraz wartość tego współczynnika
  max:=Abs(a[i,k]);
  w:=i;
end;
if max=0 then goto kon;
if w>k then //jeżeli znaleziony został większy współczynnik to zamieniamy wiersze miejscami
for i:=k to n+1 do
begin
  pom:=a[k,i];
  a[k,i]:=-a[w,i];
  a[w,i]:=pom;
end;

//Dokonujemy jeszcze małej poprawki
if a[k,k]<>0 then //ten warunek z poprzedniej procedury możemy już usunąc ponieważ teraz wcześniej dokonujemy tego sprawdzenia.

Tak zmodyfikowana metoda pozwala na prowadzenie obliczeń w przypadkach gdy na głównej przekątnej macierzy współczynników występują (lub mogą wystąpić w czasie obliczeń) zerowe współczynniki.

---