АЛГОРИТМЫ

Новости

Рассылка новостей

Форум

AlgoPascal

Редактор блок-схем

Статьи

О сайте

Контакты
Содержание - Системы линейных уравнений - Метод Гаусса

Решение СЛАУ методом Гаусса

Процедура решает неоднородную систему n линейных алгебраических уравнений с n неизвестными:

a11 x1  + a12 x2  + ... +a1n xn  = a1n+1 
a21 x1  + a22 x2  + ... +a2n xn  = a2n+1 
....
an1 x1  + an2 x2  + ... +ann xn  = ann+1 

Вначале находим отличный от нуля коэффициент при x1 . Соответствующее уравнение переставляем с первым (если это необходимо). Получаем систему с a11  отличным от нуля. Разделив коэффициенты этого уравнения на a11 , получим:

x1  + b12 x2  + ... + b1n xn  = b1n+1 

При помощи этого уравнения исключаем x1  из исходной системы:

a (1)22 x2  + a (1)23 x3  + ... + a (1)2n xn  = a (1)2n+1 
....
a (1)n2 x2  + a (1)n3 x3  + ... + a (1)nn xn  = a (1)nn+1 

где

a (1)ij  = aij  - ai1 b1j  , i,j= 2...n

Полученная система содержит n-1 уравнение. Применяем описанную выше процедуру к этой системе. Операции повторяем требуемое число раз, пока не приведем систему к треугольному виду:

x1  + с12 x2  + ... + с1n xn  = с1n+1 
x2  + ... + c2n xn  = c2n+1 
....
xn  = cnn+1 

Теперь легко определить xn , xn-1 , ..., x1 .

Если при поиске отличного от нуля коэффициента такого не окажется, то матрица системы вырождена и алгоритм неприменим. Для сравнения с нолем в алгоритм передается малое число epsilon, и любое число, по модулю меньшее epsilon, считается нолем. В случае вырожденой матрицы функция возвращает False. Если матрица невырождена, то функция возвращает True, а переменная X содержит решение системы.

Если нашли ошибку в алгоритме - сообщите!


Реализации алгоритма на различных языках:

Реализация алгоритма на C++
Реализация алгоритма на Delphi
Реализация алгоритма на Visual Basic 6

Блоксхемы:

Посмотреть блок-схему алгоритма
Скачать блок-схему алгоритма

Реализация алгоритма на AlgoPascal:

unit LESGaussUnit;

interface LESGaussSolve;

implementation

(*******************************************************************
Функция решения системы линейных уравнений вида:
A[1,1]*X[1] + .. + A[1,N]*X[N] = A[1,N+1]
        ....................
A[N,1]*X[1] + .. + A[N,N]*X[N] = A[N,N+1]
методом Гаусса.

Функция   возвращает   True,   если    det(A') <>0
(Х хранит решение), и False если det(A')=0,     в
таком случае X не хранит решение.
A' - матрица из первых N столбцов матрицы A.

Epsilon определяет точность сравнения чисел. Если
число по модулю меньше или равно Epsilon, то оно
считается равным 0. Это число позволяет указать
алгоритму, насколько именно переданная в него матрица
должна быть близка к вырожденной, чтобы вызвать выход
со значением True.

Чтобы проводить вычисления независимо от того, насколько
матрица близка к вырожденной, следует задать epsilon
равным 0.
*******************************************************************)
function LESGaussSolve(
            A   :   array of array of Real;
    const   N   :   Integer;
    out     X   :   array of Real;
    const   Epsilon : Real):Boolean;
var
    k  : Integer;
    u  : Integer;
    m  : Integer;
    j  : Integer;
    i  : Integer;

    t  : Real;
begin
  SetBounds( x, [1, n] );
  u:=0;
  Result:=True;
  repeat
    u:=u+1;
    k:=u;
    while (AbsReal(a[k,u])<=Epsilon)and(k<n) do
    begin
      k:=k+1;
    end;
    if (k<>n)or (AbsReal(a[n,u])>Epsilon) then
    begin
      if k<>u then
      begin
        m:=u;
        repeat
          t:=a[u,m];
          a[u,m]:=a[k,m];
          a[k,m]:=t;
          m:=m+1;
        until not(m<=n+1);
      end;
      j:=n+1;
      repeat
        a[u,j]:=a[u,j]/a[u,u];
        j:=j-1
      until not(j>=u);
      m:=n+1;
      if k+1<=n then
      begin
        i:=k+1;
        repeat
          j:=u+1;
          repeat
            a[i,j]:=a[i,j]-a[i,u]*a[u,j];
            j:=j+1
          until not(j<=m);
          i:=i+1
        until not(i<=n);
      end;
    end
    else
    begin
      Result:=False;
    end;
  until not((u<>n)and Result);
  
  if Result then
  begin
    i:=n;
    repeat
      x[i]:=a[i,m];
      if i<>1
      then
      begin
        k:=i-1;
        repeat
          a[k,m]:=a[k,m]-a[k,i]*x[i];
          k:=k-1
        until not(k>=1);
      end;
      i:=i-1
    until not(i>=1);
  end;
end;

end.

 


Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU