Методы решения СЛАУ. Метод Гаусса

 

   .                      (2.16) 

  На  k-м шаге, используя первые k уравнений, исключаем неизвестные x₁,..,x_k из (k+1)-го уравнения. Затем посредством этого уравнения исключается неизвестное x_k+1 из первых k уравнений и т.д. В результате прямого хода матрица системы приводится к диагональному виду с единицами на главной диагонали. При этом отпадает необходимость обратного хода, поскольку столбец правой части приведенной матрицы и является вектором решения.

4. Метод Гаусса-Жордана. Эта модификация метода Гаусса незначительно отличается от метода оптимального исключения. Операции исключения переменных для каждого приводимого уравнения осуществляют не только ниже, но и выше главной диагонали. Операции с первым уравнением системы полностью аналогичны стандартной схеме. Второе уравнение системы после приведения и домножения на соответствующие коэффициенты вычитаем не только из третьего и последующих уравнений, но и из первого. В результате k таких шагов получаем матрицу

 

   .                                     (2.17) 

  Как и в методе оптимального исключения, матрица системы приводится к  диагональному виду и вектором решения  является столбец  .

        2.8. Сравнение прямых и итерационных методов

        Системы линейных алгебраических уравнений можно решать как с  помощью прямых, так и  итерационных методов. Для систем уравнений средней  размерности чаще используют прямые методы.

        Итерационные методы применяют главным образом для решения задач большой размерности, когда использование прямых методов невозможно из-за ограничений в доступной оперативной памяти ЭВМ или из-за необходимости выполнения чрезмерно большого числа арифметических операций. Большие системы уравнений, возникающие в основном в приложениях, как правило являются разреженными. Методы исключения для систем с разреженным и матрицами неудобны, например, тем, что при их использовании большое число нулевых элементов превращается в ненулевые и матрица теряет свойство разреженности. В противоположность им при использовании итерационных методов в ходе итерационного процесса матрица не меняется, и она, естественно, остается разреженной. Большая эффективность итерационных методов по сравнению с прямыми методами тесно связанна с возможностью существенного использования разреженности матриц.

        Применение итерационных методов для качественного решения  большой системы уравнений требует  серьезного использования ее структуры, специальных знаний и определенного  опыта. 

 

  

3. Описание алгоритма.

  Классическим методом решения систем линейных алгебраических уравнений (СЛАУ) является метод Гаусса. На первом этапе этого метода осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. А именно, среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получавшуюся после перестановки первую строку из остальных строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию. 
    На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений. Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (а она там всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх. Каждой строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки. 

 

4. Блок-схемы алгоритма.

 
5. Листинг программы.

unit Unit3;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, Grids, StdCtrls;

const MaxDimension = 10;

type

  Vector = array[1..MaxDimension] of Double;

  Matrix = array[1..MaxDimension] of Vector;

  TForm3 = class(TForm)

    Label1: TLabel;

    Edit1: TEdit;

    StringGrid1: TStringGrid;

    StringGrid2: TStringGrid;

    Button1: TButton;

    Label2: TLabel;

    Label3: TLabel;

    ListBox1: TListBox;

    procedure Edit1Change(Sender: TObject);

    procedure Button1Click(Sender: TObject);

    procedure FormCreate(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  Form3: TForm3;

implementation

{$R *.dfm}

procedure TForm3.Button1Click(Sender: TObject);

  var a: Matrix;

      b,x: Vector;

      h: Double;

      i,j,k,n:integer;

begin

  //Ввод данных

  //Размерность системы

  n := StrToIntDef(Text, StringGrid1.ColCount);

  //Коэффициенты

  for j := 0 to n - 1 do

    for i := 0 to n - 1 do

      a[i + 1, j + 1] := StrToFloatDef(StringGrid1.Cells[j, i], 0);

  //Правая часть уравнения

  for I := 0 to n - 1 do b[i + 1] := StrToFloatDef(StringGrid2.Cells[0, i], 0);

  //Прямой ход - исключение переменных

  for i:=1 to n-1 do

    for j:=i+1 to n do

    begin

      a[j,i]:=-a[j,i]/a[i,i];

      for k:=i+1 to n do

        a[j,k]:=a[j,k]+a[j,i]*a[i,k];

        b[j]:=b[j]+a[j,i]*b[i]

    end;

    x[n]:=b[n]/a[n,n];

    //Обратный  ход - нахождение корней

    for i:=n-1 downto 1 do

    begin

      h:=b[i];

      for j:=i+1 to n do h:=h-x[j]*a[i,j];

      x[i]:=h/a[i,i]

    end;

    //Вывод результата

    for i:=1 to n do ListBox1.Items.Append('x(' + IntToStr(i) + ')=' + FloatToStr(x[i]));

end;

procedure TForm3.Edit1Change(Sender: TObject);

begin

  with StringGrid1, Edit1 do

  begin

    ColCount := StrToIntDef(Text, 3);

    RowCount := StrToIntDef(Text, 3);

  end;

  with StringGrid2, Edit1 do

    RowCount := StrToIntDef(Text, 3)

end;

procedure TForm3.FormCreate(Sender: TObject);

  var i, j: integer;

begin

  //Заполнить  коэф уравнения

  Randomize;

  for I := 0 to StrToIntDef(Text, StringGrid1.ColCount) - 1 do

    for J := 0 to StrToIntDef(Text, StringGrid1.RowCount) - 1 do

      StringGrid1.Cells[I, J] := IntToStr(Random(100));

  for I := 0 to StrToIntDef(Text, StringGrid2.RowCount) - 1 do

    StringGrid2.Cells[0, I] := IntToStr(Random(100))

end;

end. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

6.Выполнение программы 

 

Рис 6.1

Рис 6.2 

 

 Список  использованной литературы: 

• http:/www.wikipedia.org/wiki/Метод  Гаусса 
• Волков, Е.А. Численные методы: Учебное пособие для вузов / Е.А. Волков. – 2-е изд., испр. – М.:Наука, 1987. – 248 с.
• Карчевская, М.П. Разработка приложений в среде Borland Delphi  /  М.П. Карчевская,  О. Л. Рамбургер, С. В. Тархов,  Е. А. Хамзина; под ред. М.П. Карчевская. – УГАТУ, 2005.
• Мастер – Самоучитель по Delphi 7.  -  AlexSoft , 1997-2001 г.
• Роганин, А.М. Основные формулы высшей математики / А. М. Роганин. – Х.:Торсинг, 2002
• Справочная система Borland Delphi 7.