Сравнение эффективности различных методов решения систем линейных алгебраических уравнений. Метод Гаусса и метод простой итерации

5

к виду единичной матрицы методом Гаусса—Жордана; в результате на месте

изначальной единичной матрицы справа оказывается обратная к исходной матрица: [pic]);

определения ранга матрицы (согласно следствию из теоремы Кронекера—Капелли ранг матрицы равен числу её главных переменных);

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

Достоинства метода

Менее трудоёмкий по сравнению с другими методами.

Позволяет однозначно установить, совместна система или нет, и если совместна, найти её решение.

Позволяет найти максимальное число линейно независимых уравнений — ранг матрицы системы.[1]

5

     1.2.2Метод  простой  итерации

Для использования этого метода систему, имеющую вид:

[pic]

нужно привести к следующему виду (называемому нормальным):

              [pic]              (*)

Затем в полученную систему подставляют начальное приближение решения, т.е. некоторый набор значений [pic]  и вычисляют следующее приближение решения – набор значений [pic]. Полученный набор значений снова подставляют в систему (*) для вычисления следующего приближения и т.д. Процесс повторяется до тех пор, пока не будет достигнута необходимая точность решения.

Данный метод сходится при выполнении одного из следующих условий:

              [pic]              (**)

Т.е. метод простой итерации решения СЛАУ сходится, если максимальная из сумм модулей коэффициентов при неизвестных системы (*) взятых по строкам меньше единицы либо если максимальная из сумм модулей коэффициентов при неизвестных системы (*) взятых по столбцам меньше единицы, либо если сумма квадратов всех коэффициентов при неизвестных в правой части системы (*) меньше единицы. Каждое из этих условий является достаточным для сходимости метода, но не необходимым. Это означает, что метод сходится при выполнении хотя бы одного из этих условий, но он так же может сходиться и тогда, когда ни одно из них не выполняется. В данном случае руководствуются эмпирическим правилом: если в ходе итераций некторая десятичная цифра повторилась 3 и более раз – её можно считать верной.

Во всех остальных случаях (когда выполняется одно из условий (**)) степень приближения к точному решению оценивается по формуле:

              [pic],              (***)

Где α – величина, вычисляемая по одной и формул (**) по которой обнаружена сходимость метода.[2]

5

1.3 Блок-схемы алгоритмов программ (подпрограмм)

Метод Гаусса

5

5

5

5

5

Метод простой итерации

5

5

5

5

5

5

   2. Практическая часть

2.1  Текст программы

unit Unit1;

interface

uses

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

  Dialogs, Menus, XPMan, StdCtrls, Grids;

type

  TForm1 = class(TForm)

    StringGrid1: TStringGrid;

    StringGrid2: TStringGrid;

    Label1: TLabel;

    MainMenu1: TMainMenu;

    Label2: TLabel;

    Memo1: TMemo;

    XPManifest1: TXPManifest;

    N1: TMenuItem;

    N2: TMenuItem;

    N3: TMenuItem;

    N4: TMenuItem;

    N5: TMenuItem;

    N6: TMenuItem;

    N7: TMenuItem;

    N8: TMenuItem;

    N10: TMenuItem;

    Memo2: TMemo;

    procedure N4Click(Sender: TObject);

    procedure FormCreate(Sender: TObject);

    procedure Razmernost();

    procedure N8Click(Sender: TObject);

    procedure N2Click(Sender: TObject);

    procedure N10Click(Sender: TObject);

    procedure N6Click(Sender: TObject);

  private

    { Private declarations }

  public

5

    { Public declarations }

  end;

var

  Form1: TForm1;

  M: array[1..100,1..100] of real; // матрица коэффициентов

  B: array[1..100] of real;        // столбец свободных членов (ССЧ)

  N: integer;                      // размерность матрицы

  xG: array [1..100] of double;    // решение методом Гаусса

  xI:array [1..100] of double;     // решение методом простых итераций

  eps: double;                     // точность решения

  max_it: integer;                 // максимальное число итераций

implementation

uses Unit2;

{$R *.dfm}

// кнопка "Выход"

procedure TForm1.N4Click(Sender: TObject);

begin

  Application.Terminate;

end;

// процедура изменения размерности

procedure TForm1.Razmernost();

begin

  StringGrid1.ColCount := N;

  StringGrid1.RowCount := N;

  StringGrid2.RowCount := N;

end;

// начальная инициализация

procedure TForm1.FormCreate(Sender: TObject);

begin

  N := 4;

  Razmernost;

  eps := 0.0001;

  max_it := 1000;

end;

5

// открытие формы настроек

procedure TForm1.N8Click(Sender: TObject);

begin

  Form2.ShowModal;

  Razmernost;

end;

// задание значений по варианту

procedure TForm1.N2Click(Sender: TObject);

begin

  N := 4;

  Razmernost;

  StringGrid1.Cells[0,0] := '10,9'; StringGrid1.Cells[1,0] := '1,2';

  StringGrid1.Cells[0,1] := '1,2';  StringGrid1.Cells[1,1] := '11,2';

  StringGrid1.Cells[0,2] := '2,1';  StringGrid1.Cells[1,2] := '1,5';

  StringGrid1.Cells[0,3] := '0,9';  StringGrid1.Cells[1,3] := '2,5';

  StringGrid1.Cells[2,0] := '2,1';  StringGrid1.Cells[3,0] := '0,9';

  StringGrid1.Cells[2,1] := '1,5';  StringGrid1.Cells[3,1] := '2,5';

  StringGrid1.Cells[2,2] := '9,8';  StringGrid1.Cells[3,2] := '1,3';

  StringGrid1.Cells[2,3] := '1,3';  StringGrid1.Cells[3,3] := '12,12';

  StringGrid2.Cells[0,0] := '-7';

  StringGrid2.Cells[0,1] := '5,3';

  StringGrid2.Cells[0,2] := '10,3';

  StringGrid2.Cells[0,3] := '24,6';

  Form2.Edit1.Text := '4';

  Form2.Edit2.Text := '1000';

  Form2.Edit3.Text := '0,0001';

end;

// кнопка "Очистка"

procedure TForm1.N10Click(Sender: TObject);

var i, j: integer;

begin

  for i:=0 to N-1 do

  begin

    for j:=0 to N-1 do

      StringGrid1.Cells[j,i] := '';

    StringGrid2.Cells[0,i] := '';

  end;

  Memo1.Clear;

  Memo2.Clear;

end;

5

// выполнение расчета

procedure TForm1.N6Click(Sender: TObject);

var i, j, k, iter: integer;

    x: array [1..100] of double;

    d, s: double;

    flag: boolean;         // флаг достижения заданной точности

begin

  Memo1.Clear;

  Memo2.Clear;

  // метод Гаусса

  Memo1.Lines.Add('Метод Гаусса:');

  k := 0;

  // считываем данные

  for i:=1 to N do

    for j:=1 to N do

      M[i,j] := StrToFloat(StringGrid1.Cells[j-1,i-1]);

  for i:=1 to N do

    B[i]:= StrToFloat(StringGrid2.Cells[0,i-1]);

  // прямой ход - приводим матрицу к треугольному виду

  for i:=1 to N-1 do

  begin

    for k:=i+1 to N do

    begin

      d := M[k,i] / M[i,i];

      for j:=i+1 to N do

      begin

        M[k,j] := M[k,j] - M[i,j] * d;

        inc(iter);   // счетчик итераций

      end;

      B[k]:= B[k] - B[i] * d;

    end;

  end;

  // обратный ход - находим решение

  for i:=N downto 1 do

  begin

    for j:=i+1 to N do

    begin

      B[i] := B[i] - M[i,j] * xG[j];

      inc(k);        // счетчик итераций

    end;

    xG[i] := B[i] / M[i,i];

  end;

5

  Memo1.Lines.Add('Полученный результат:');

  for i:=1 to N do

    Memo1.Lines.Add('X['+IntToStr(i)+']='+FloatToStrF(xG[i], ffFixed, 10, 5));

  Memo1.Lines.Add('Итераций: '+IntToStr(iter));

  Memo1.Lines.Add('--------------------------------------------');

  // метод простых итераций

  Memo2.Lines.Add('Метод простых итераций');

  // считываем данные

  for i:=1 to N do

    for j:=1 to N do

      M[i,j] := StrToFloat(StringGrid1.Cells[j-1,i-1]);

  for i:=1 to N do

    B[i]:= StrToFloat(StringGrid2.Cells[0,i-1]);

  iter := 0;

  for i:=1 to n do

    for j:=1 to n do

      M[i,j] := StrToFloat(StringGrid1.Cells[i-1,j-1]);

  for i:=1 to n do

    B[i] := StrToFloat(StringGrid2.Cells[0,i-1]);

  for i:=1 to n do

    xI[i] := 0;

  j := 0;

  flag := False;

  repeat

    for i:=1 to n do

    begin

      s := 0;

      for k:=1 to n do

        if (i  k) then

          s := s + M[k,i] * xI[k];

      x[i] := (B[i] - s) / M[i,i];

    end;

    for i:=1 to n do

    begin

      if (abs(x[i] - xI[i]) > eps) then

        flag := false

      else

        flag := true;

      xI[i]:=x[i];

    end;

    inc(iter);       // счетчик итераций

  until (flag = true);

5

  if (flag = false) then

    Memo2.Lines.Add(IntToStr(iter)+'Заданная точность не достигнута');

  Memo2.Lines.Add('Полученный результат:');

  for i:=1 to n do

    Memo2.Lines.Add('X['+IntToStr(i)+']='+FloatToStrF(xI[i], ffFixed, 10, 5));

  Memo2.Lines.Add('Итераций: '+IntToStr(iter));

  Memo2.Lines.Add('--------------------------------------------');

end;

end.

5

2.2. Результаты (графическое представление результатов)

Рисунок 2.2.1 Скриншот работы программы для метода Гаусса и метода простой итерации

5

ЗАКЛЮЧЕНИЕ

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

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

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

Можно сделать вывод,что при малых размерах матрицы наиболее разумно использовать метод Гаусса, а при больших — метод простой итерации.

В ходе выполнения работы были получены навыки в разработке программ в  Delphi 7.0, усовершенствованы знания по решению СЛАУ.

5

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1.  Калиткин Н.Н. Численные методы: / Н.Н. Калиткин. – М.: Наука, 1978. – 512 с.

Крылов В.И. Вычислительные методы, том I: Учеб. пособие / В.И. Крылов, В.В. Бобков, П.И. Монастырский. – М., Наука, 1976. – 303 с.

Фаронов, В.В. Система программирования Delphi / В.В. Фаронов. – СПб.: БХВ-Петербург, 2003. – 888 с.

Климова, Л.М. Delphi 7: основы программирования, решение типовых задач: самоучитель / Л.М. Климова. – Москва: Кудиц-образ, 2005. – 480 с.

5