Способ решения системы линейных уравнений на ЭВМ методом Гаусса

Содержание Введение

1. Решение СЛАУ методом Гаусса Вывод Список использованной литературы

Введение

На практике часто возникает необходимость решить систему линейных уравнений. Если система имеет высокий порядок или просто их много, то приходится прибегать к помощи компьютерной техники. Существуют несколько способов решения систему линейных уравнений на ЭВМ. В этой работе мы рассмотрим метод Гаусса.

гаусс линейный уравнение программа компьютерный

1. Решение СЛАУ методом Гаусса Прямой ход состоит из n (1 шагов исключения.

1-й шаг. Целью этого шага является исключение неизвестного x1 из уравнений с номерами i = 2, 3, …, n. Предположим, что коэффициент a11 (0. Будем называть его главным элементом 1-го шага.

Найдем величины

qi1 = ai1/a11 (i = 2, 3, …, n),

называемые множителями 1-го шага. Вычтем последовательно из второго, третьего, …, n-го уравнений системы первое уравнение, умноженное соответственно на q21, q31, …, qn1. Это позволит обратить в нуль коэффициенты при x1 во всех уравнениях, кроме первого. В результате получим эквивалентную систему

a11×1 + a12×2 + a13×3 + … + a1nxn = b1,

a22(1)x2 + a23(1)x3 + … + a2n (1)xn = b2(1),

a32(1)x2 + a33(1)x3 + … + a3n (1)xn = b3(1),

an2(1)x2 + an3(1)x3 + … + ann (1)xn = bn (1).

в которой aij (1) и bij (1) вычисляются по формулам

aij (1) = aij — qi1a1j, bi (1) = bi — qi1b1.

2-й шаг. Целью этого шага является ислючение неизвестного x2 из уравнений с номерами i = 3, 4, …, n. Пусть a22(1)? 0, где a22(1) — коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага

qi2 = ai2(1) / a22(1) (i = 3, 4, …, n)

и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q32, q42, …, qm2. В результате получим систему

a11×1 + a12×2 + a13×3 + … + a1nxn = b1,

a22(1)x2 + a23(1)x3 + … + a2n (1) = b2(1),

a33(2)x3 + … + a3n (2)xn = b3(2),

an3(2)x3 + … + ann (2)xn = bn (2).

Аналогично проводятся остальные шаги. Опишем очередной k-й шаг.

k-й шаг. В предположении, что главный (ведущий) элемент k-го шага

akk (k-1) отличен от нуля, вычислим множители k-го шага

qik = aik (k-1) / akk (k-1) (i = k + 1, …, n)

и вычтем последовательно из (k + 1)-го, …, n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на qk+1,k, qk+2,k, …, qnk. После (n — 1)-го шага исключения получим систему уравнений матрица A (n-1) которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

a11×1 + a12×2 + a13×3 + … + a1nxn = b1,

a22(1)x2 + a23(1)x3 + … + a2n (1)xn = b2(1),

a33(2)x3 + … + a3n (2)xn = b3(2),

ann (n-1)xn = bn (n-1).

Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное значение xn в предпоследнее уравнение, получим xn-1. Осуществляя обратную подстановку, далее последовательно находим xn-1, xn-2, …, x1. Вычисления неизвестных здесь проводятся по формулам

xn = bn (n-1) / ann (n-1),

xk = (bn (k-1) — ak, k+1(k-1)xk+1 — … — akn (k-1)xn) / akk (k-1), (k = n ;

1, …, 1).

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

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

Рис. 1 — Алгоритм метода Гаусса

Создание приложения Запускаем Delphi, выполняем команду File/New/Form

Рис. 2 — Создание нового окна

На появившемся окне помещаем:

Image1 — изображение — заставка

Timer1 — таймер Рис. 3 — Стартовое окно программы

Далее добавляем еще одну форму (form3) и прописываем в таймере формы 2 время, по истечении которого будет показываться основное окно программы.

Рис. 4. Основное окно программы

На появившейся форме помещаем:

Button1 — решение системы

Button2 — графическое решение системы при N=2

Edit1 — размерность системы

Image1 — вывод результата

Label1, Label2 — подписи

MainMenu1 — создание меню

SavePictureDialog1 — диалог для сохранения изображения в файл

StringGrid1, StringGrid2 — ввод исходных данных Двойным щелчком по форме открываем редактор кода и пишем исходный код программы.

Код unit3

unit Unit3;

interface

uses

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

Dialogs, Grids, StdCtrls, Menus, ExtCtrls, unit1, ExtDlgs, unit4, unit5;

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;

MainMenu1: TMainMenu;

N1: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N6: TMenuItem;

Image1: TImage;

SavePictureDialog1: TSavePictureDialog;

N2: TMenuItem;

Button2: TButton;

procedure Edit1Change (Sender: TObject);

procedure Button1Click (Sender: TObject);

procedure FormCreate (Sender: TObject);

procedure N6Click (Sender: TObject);

procedure N4Click (Sender: TObject);

procedure N3Click (Sender: TObject);

procedure N2Click (Sender: TObject);

procedure Button2Click (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 i:=0 to 249 do begin

for j:=0 to 161 do begin

image1.Canvas.Pixels [i, j]: =image1.Canvas.Pixels[1,1];

end;

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 image1.Canvas.TextOut (1, 1+15*i, ('x'+ floattostr (i)+'= '+floattostr (x[i])));

for i:=0 to 249 do begin

for j:=0 to 161 do begin

if image1.Canvas.Pixels [i, j]<>clblack then image1.Canvas.Pixels [i, j]: =image1.Canvas.Pixels[1,1];

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);

if edit1. Text='2' then button2. Enabled:=true else button2. Enabled:=false;

end; //Button2 работает только при N=2

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))

procedure TForm3. N6Click (Sender: TObject);

begin

form1.Visible:=true;

end;

procedure TForm3. N4Click (Sender: TObject);

begin

close;

end;

procedure TForm3. N3Click (Sender: TObject);

var

filename: string;

begin

if savepicturedialog1. Execute then

begin

FileName:= savepicturedialog1. FileName;

image1.Picture.SaveToFile (filename);// сохранение Image1 в файл

end;

procedure TForm3. N2Click (Sender: TObject);

begin

form4.Visible:=true;

end;

procedure TForm3. Button2Click (Sender: TObject);

var

i, j: integer;

begin

form5.Image1.Canvas.Rectangle (0,0,400,400);

for i:=1 to 398 do begin

for j:=1 to 398 do begin

form5.Image1.Canvas.Pixels[i, j]: =form3.Image1.Canvas.Pixels[1,1];

end;

end; //рисуем рамку и красим ее в цвет окна

form5.Visible:=true;

form5.Image1.Canvas.pen.Color:=clred;

form5.Image1.Canvas.MoveTo (0,200−50*round ((strtofloat (stringGrid2.Cells[0,0])+4*strtofloat (stringGrid1.Cells[0,0]))/strtofloat (stringGrid1.Cells[1,0])));

form5.Image1.Canvas.LineTo (400,200−50*round ((strtofloat (stringGrid2.Cells[0,0])-4*strtofloat (stringGrid1.Cells[0,0]))/strtofloat (stringGrid1.Cells[1,0])));

form5.Image1.Canvas.Pen.Color:=clblue;

form5.Image1.Canvas.MoveTo (0,200−50*round ((strtofloat (stringGrid2.Cells[0,1])+4*strtofloat (stringGrid1.Cells[0,1]))/strtofloat (stringGrid1.Cells[1,1])));

form5.Image1.Canvas.LineTo (400,200−50*round ((strtofloat (stringGrid2.Cells[0,1])-4*strtofloat (stringGrid1.Cells[0,1]))/strtofloat (stringGrid1.Cells[1,1])));

form5.Image1.Canvas.Pen.Color:=clblack;

i:=0;

form5.Image1.Canvas.MoveTo (200,0);

form5.Image1.Canvas.LineTo (200,400);

form5.Image1.Canvas.MoveTo (0,200);

form5.Image1.Canvas.LineTo (400,200);

repeat

i:=i+50;

form5.Image1.Canvas.MoveTo (i, 195);

form5.Image1.Canvas.LineTo (i, 205);

form5.Image1.Canvas.MoveTo (195,i);

form5.Image1.Canvas.LineTo (205,i);

until i>300;

form5.Image1.Canvas.TextOut (185,145,'1');// процедура, описывающая построение графика

end;

unit Unit4;

interface

uses

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

Dialogs, jpeg, ExtCtrls;

type

TForm4 = class (TForm)

Image1: TImage;

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form4: TForm4;

implementation

{$R *.dfm}

end.

На этой форме разместим Image1, на которой и будем реализовать график. Его алгоритм прописан в Unit3

Код unit5

unit Unit5;

interface

uses

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

Dialogs, ExtCtrls;

type

TForm5 = class (TForm)

Image1: TImage;

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form5: TForm5;

implementation

{$R *.dfm}

end.

Код unit1

unit Unit1;

interface

uses

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

Dialogs, StdCtrls;

type

TForm1 = class (TForm)

Label1: TLabel;

procedure FormCreate (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1. FormCreate (Sender: TObject);

begin

label1.Caption:='Данная программа реализует решение'+#10#13+'систем линейных алгебраических уравнений'+#10#13+ 'методом Гаусса';

end;

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

1. http:/www.wikipedia.org/wiki/Метод Гаусса

2. Карчевская М. П., Рамбургер О. Л., Тархов С. В., Хамзина Е. А. «Разработка приложений в среде Borland Delphi», УГАТУ-2005

3. Мастер — Самоучитель по Delphi 7 AlexSoft 1997;2001 г.