Решение системы линейный алгебраических уравнений методом Гаусса с поиском главного элемента по строке

Министерство образования и науки Российской Федерации Государственное образовательное учреждение Высшего профессионального образования

" ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"

Факультет экономики и управления Кафедра математических методов и моделей в экономике ОТЧЕТ По лабораторному практикуму По курсу численные методы по теме «Решение СЛАУ методом Гаусса с поиском главного элемента по строке»

Руководитель:

Яркова О.Н.

Исполнитель Студент гр. 09ММЭ Евдокимов Д. А.

Оренбург 2011

• 1) Постановка задачи
• 2) Краткие теоретические сведения
• 3) Алгоритм
• 4) Блок-схема
• 5) Код программы
• 6) Тестовый пример
• 7) Проверка в MathCad

1) Постановка задачи

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

2) Краткие теоретические сведения

Система линейных алгебраических уравнений (СЛАУ) имеет вид

Ax=b,

где, ,

СЛАУ имеет решение, если ранг матрицы, А равен n (числу переменных) и если матрица, А не является вырожденной.

Существуют следующие методы решения СЛАУ:

1) Метод Крамера;

2) Метод Гаусса;

3) Матричный подход;

4) LU-разложение;

5) и другие.

Рассмотрим метод Гаусса с поиском главного элемента по строке.

Матрицей перестановок Р будет называть матрицу размерности n x n, у которой в каждом столбце/строке только один элемент равен единице, а остальные — 0. Элементарной матрицей перестановок P_kl будем называть матрицу, полученную из единичной перестановкой k-того и l-того столбцов.

Если матрица не является вырожденной, то существует такая матрица перестановок, что матрица P*A имеет отличные от нуля главные миноры.

Найдя максимальный по модулю элемент в текущей строке, ставим его на первое место, используя матрицу перестановок.

После перестановки используем метод LU-разложения, на каждом шаге которого переставляем максимальный и i-тый элементы в i-той строке, используя матрицу перестановок P_ij, где j — номер столбца с максимальным элементом в i-той строке.

гаусс алгебраический уравнение алгоритм

3) Алгоритм

0) А, b, i:=1.

1) Ищем в i-той строке наибольший по модулю элемент и меняем его местами с элементом a_ii, находя А*Р_ji, где j — номер столбца с максимальным элементом в i-той строке А.

2) Находим элементы матрицы Lⁱ, Aⁱ:=Lⁱ*А*Р_ji, Bⁱ:=Lⁱ*b.

3) Если i=n, то переходим к шагу 4. Иначе — i:=i+1, к шагу 1.

4) ,

где — n-ный элемент вектора b^n-1, а — стоящий в нижнем правом углу элемент матрицы a^n-1.

где. х — искомый вектор решений.

4) Блок-схема

5) Код программы

unit Unit1;

interface

uses

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

Dialogs, StdCtrls, XPMan, Grids, ComCtrls;

type

TForm1 = class (TForm)

Edit1: TEdit;

Label1: TLabel;

UpDown1: TUpDown;

StringGrid1: TStringGrid;

Label2: TLabel;

StringGrid2: TStringGrid;

Edit2: TEdit;

Label3: TLabel;

XPManifest1: TXPManifest;

Button1: TButton;

procedure Edit1Change (Sender: TObject);

procedure Button1Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var l, la, a: array [0.100, 0.100] of Real; //Формат: номер матрицы L, строки, столбцы

lb, b, xsolved: array [0.100] of real; //xsolved — вектор-решение СЛАУ

zz:Real; //Промежуточная переменная

i, j, n, k: integer;

ch: array [0.100] of Integer;

Form1: TForm1;

implementation

{$R *.dfm}

procedure lmatrix (num: integer);

//(num+1) — номер очередной матрицы L

//Сама процедура находит L c индексом (num+1)

begin

for i:=0 to (n-1) do begin

for j:=0 to (n-1) do L[i, j]: =0;

L[i, i]: =1;

end;

L[num, num]: =1/a[num, num];

for i:=(num+1) to (n-1) do begin

L[i, num]: =-a[i, num]*L[num, num];

L[i, i]: =1;

end;

end;

procedure lamatrix (num:integer);

//Получаем матрицу L (num+1)*…*L (1)*A

var x: real;

begin

if num=0 then

for i:=0 to (n-1) do

for j:=0 to (n-1) do

LA[i, j]: =a[i, j]

else

for i:=0 to (n-1) do

for j:=0 to (n-1) do begin

x:=0;

for k:=0 to (n-1) do

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

LA[i, j]: =x;

end;

for i:=0 to (n-1) do

for j:=0 to (n-1) do

a[i, j]: =La[i, j];

end;

procedure lbvector (num:integer);

//Получаем вектор L (num+1)*…*L (1)*b

var x: real;

begin

if num=0 then

for j:=0 to (n-1) do

LB[j]: =b[j]

else

for i:=0 to (n-1) do begin

x:=0;

for j:=0 to (n-1) do

x:=x+l[i, j]*b[j];

LB[i]:=x;

end;

for i:=0 to (n-1) do b[i]: =lb[i];

end;

procedure replace (num:integer);

begin

//Поиск максимального элемента по текущей строке

zz:=la[num, num];

for i:=(num+1) to (n-1) do

if Abs (zz)

zz:=la[num, i];

ch[num]:=i;

end;

//Меняем местами самый левый ненулевой столбец и столбец, содержащий максимальный элемент в первой строке

for i:=0 to (n-1) do begin

zz:=la[i, ch[num]];

la[i, ch[num]]:=la[i, num];

la[i, num]:=zz;

end;

for i:=0 to (n-1) do

for j:=0 to (n-1) do

a[i, j]: =La[i, j];

end;

procedure solving;

begin

xsolved[n-1]: =lb[n-1]/la[n-1, n-1];

for i:=(n-2) downto 0 do begin

zz:=0;

for j:=i to (n-1) do

zz:=zz+la[i, j]*xsolved[j];

xsolved[i]:=lb[i]-zz;

end;

for i:=(n-2) downto 0 do begin

zz:=xsolved[ch[i]];

xsolved[ch[i]]:=xsolved[i];

xsolved[i]:=zz;

end;

end;

procedure TForm1. Edit1Change (Sender: TObject);

begin

n:=StrToInt (Edit1.Text);

StringGrid1.ColCount:=n;

StringGrid1.RowCount:=n;

StringGrid2.RowCount:=n;

end;

procedure TForm1. Button1Click (Sender: TObject);

var i, j: integer;

begin

//Обнуляем все матрицы для независимости от результатов предыдущих вычислений

for j:=0 to n do begin

for k:=0 to n do begin

l[j, k]: =0;

la[j, k]:=0;

a[j, k]:=0;

end;

lb[j]:=0;

b[j]:=0;

xsolved[j]:=0;

end;

Edit2.Text:='';

//Считывание элементов матрицы, А и вектора b

for i:=0 to (n-1) do begin

for j:=0 to (n-1) do

a[i, j]: =StrToFloat (StringGrid1.Cells[j, i]);

b[i]:=StrToFloat (StringGrid2.Cells[0,i]);

end;

for i:=0 to (n-2) do begin

lamatrix (i);

lbvector (i);

replace (i);

lmatrix (i);

end;

lamatrix (n-1);

lbvector (n-1);

solving;

for i:=0 to (n-1) do Edit2. Text:=Edit2.Text+'x'+IntTostr (i+1)+'='+FloatTostr (xsolved[i])+'; ';

end;

end.

6) Тестовый пример

Рисунок 1 — решение СЛАУ.

7) Проверка в MathCad

Рисунок 2 — решение СЛАУ с помощью программного пакета MathCad.