, или ,

где r^(k) = Ax^(k)-b - вектор невязки. Метод сходится для симметричных положительно определенных матриц при .

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

.

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

При втором способе вычисляют нормы невязки до начала итераций и на каждой итерации. Итерации прекращают при выполнении неравенства

.

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

,

где q (0,1), то метод сходится со скоростью геометрической прогрессии со знаменателем q. Можно определить, потребовав, чтобы qⁿ < , число итераций n, достаточное для того, чтобы начальная погрешность уменьшилась в заданное число раз:

.

Целая часть числа n₀() является минимальным числом итераций, необходимым для получения заданной точности .

Величина ln(1/q) является скоростью сходимости итерационного метода.

2. Описание используемого метода

Для решения методом Зейделя система линейных алгебраических уравнений Ax = b должна быть приведена к виду x = Gx+f , где G - некоторая матрица, f - преобразованный вектор свободных членов. Затем выбирается начальное приближение - произвольный вектор x⁽⁰⁾ - и строится рекуррентная последовательность векторов x⁽¹⁾, x⁽²⁾,..., x^(k),... по формуле

.

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

или .

Чем меньше норма матрицы G, тем быстрее сходится итерационный процесс.

Преобразование системы можно осуществить, просто решая каждое i-е уравнение относительно x_i :

.

Метод Зейделя использует следующий алгоритм построения приближений:

Если A - матрица с доминирующей диагональю, т.е. , то метод Зейделя сходится при любом начальном приближении x⁽⁰⁾.

Метод Зейделя сходится примерно так же, как геометрическая прогрессия со знаменателем ||G|| . Если норма матрицы G близка к 1, то скорость сходимости очень медленная. Для ускорения сходимости используется метод релаксации. Суть его в том, что полученное по методу Зейделя очередное значение пересчитывается по формуле:

Здесь 0<2 – параметр релаксации. Если <1 - нижняя релаксация, если >1 – верхняя релаксация. Параметр подбирают так, чтобы сходимость метода достигалась за минимальное число итераций.

Метод Зейделя является одношаговым итерационным методам, когда для нахождения x^(k+1) требуется помнить только одну предыдущую итерацию x^(k).

Погрешность итерации вычисляется по формуле:

n - порядок матрицы A.

Если меньше заданной точности , то итерационный процесс прекращают.

Элементы главной диагонали называются главными. Заметим, что если в ходе расчётов по данному алгоритму на главной диагонали окажется нулевой элемент, то произойдет сбой программы. Для того, чтобы избежать этого, следует перестановку строк таким образом, чтобы на главной диагонали находились максимальные элементы строк. Т. е., если в k-й строке максимальным является i-й элемент, необходимо поменять местами k-ю и i-ю строки, и поменять местами соответствующие элементы вектора b. Такой выбор главного элемента необходим для сходимости итерационного процесса.

Приведём блок-схему реализации данного метода:

3. Анализ результатов.

Скорость сходимости итерационного процесса зависит от заданной матрицы коэффициентов. В зависимости от вида исходных данных( матрицы коэффициентов и матрицы b) программа подбирает оптимальный параметр релаксации (при котором решение достигается за минимальное число итераций).

Для достижения наивысшей скорости сходимости итерационного процесса для уравнения, заданного на рис.3 программой был выбран параметр релаксации =1,26. Таким образом, была применена верхняя релаксация. Заданная точность =0,0001 была достигнута за 40 итераций.

График зависимости количества итераций от параметра релаксации приведен на рис 1.

Р ис. 1

Для достижения наивысшей скорости сходимости итерационного процесса для уравнения, заданного на рис.4 программой был выбран параметр релаксации =0,98. Таким образом, была применена нижняя релаксация. Заданная точность =0,0001 была достигнута за 17 итераций. График зависимости количества итераций от параметра релаксации приведен на рис 2.

Рис. 2

Правильность решения СЛАУ была проверена с помощью программного пакета Mathcad 2000 professional. Отметим, что программа даёт правильное решение СЛАУ почти во всех случаях, когда каждый элемент главной диагонали является максимальным в своей строке.

Вывод

Программа, разработанная в данной курсовой работе, реализует метод Зейделя для решения СЛАУ 6-го порядка. Она даёт гарантированно правильное решение системы линейных уравнений, если каждый элемент главной диагонали матрицы коэффициентов является единственным максимальным в своей строке, ненулевым, либо справедливы условия: максимальный элемент строки является единственным максимальным в своём столбце, ненулевым, а ни один из остальных элементов столбца не является максимальным в своей строке, все элементы каждой строки кроме максимального одинаковы.

При исходных данных:

была достигнута точность 0,0001 в решении:

з а 2 итерации при параметре релаксации =0,97.

Программа строит график зависимости количества итераций от параметра релаксации для данной СЛАУ, находит параметр релаксации , при котором решение достигается за минимальное количество итераций и, разумеется, само решение. Программа проста в эксплуатации и нетребовательна к ресурсам. Реализованная в современной среде разработки Delphi 5.0, она без труда может быть доработана или исправлена.

Недостатки программы: 1) применима не для всех систем линейных уравнений; 2)оптимальный параметр релаксации вычисляется методом подбора, и, поэтому, количество итераций, требуемое для его отыскания достаточно велико(около 18000), однако, для современных ПК, это не является затруднением.

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

1. Волков Е.А. Численные методы. М.: Наука, 1987. 254 с.

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

1. Мудров А.Е. Численные методы для ПЭВМ на языках БЕЙСИК, ФОРТРАН и ПАСКАЛЬ. Томск, МП "Раско", 1992. 270 с.

1. Самарский А.А., Гулин А.В. Численные методы. М.: Наука, 1989. 432с.

2. Кэнту М. Delphi 4 для профессионалов СПб: «Питер», 1999 1200с.

3. Delphi 5.0 help.

Приложение(распечатка программы, результатов)

Распечатка программы:

unit kurs1;

interface

uses

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

Grids, StdCtrls, ComCtrls, ToolWin, Menus, Unit1, TeEngine, Series,

ExtCtrls, TeeProcs, Chart;

type

TFormk1 = class(TForm)

StringGrid1: TStringGrid;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

StringGrid2: TStringGrid;

Label5: TLabel;

Label6: TLabel;

StringGrid3: TStringGrid;

Label7: TLabel;

Label8: TLabel;

Button1: TButton;

MainMenu1: TMainMenu;

Chart1: TChart;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N1: TMenuItem;

Label1: TLabel;

Series1: TFastLineSeries;

procedure FormCreate(Sender: TObject);

procedure matrix;

procedure Button1Click(Sender: TObject);

procedure N1Click(Sender: TObject);

procedure N3Click(Sender: TObject);

procedure N4Click(Sender: TObject);

procedure decision;

private

{ Private declarations }

public

{ Public declarations }

end;

var

Formk1: TFormk1;

// formk1: Tmainmenu;

implementation

var

n,m,i,j,k,l,number_of_iteration,min :integer;

delta,E,sum,max,W,tmp :extended;

A : array[1..6,1..6] of extended;

B : array[1..6] of extended;

X : array[1..6] of extended;

Xp: array[1..6] of extended;

am: array[1..200] of integer;

W_all:array[1..200] of extended;

procedure TFormk1.matrix;

begin

randomize;

for i:=1 to n do stringgrid1.cells[i-1,0]:='*X'+inttostr(i);

for i:=0 to n-1 do

for j:=1 to m do

StringGrid1.cells[i,j]:='2';

for i:=0 to n-1 do

StringGrid1.cells[i,i+1]:='3';

end;

{$R *.DFM}

procedure Tformk1.decision;

begin

delta:=E+1;

number_of_iteration:=0;

for i:=1 to 6 do X[i]:=B[i]/A[i,i];

while (delta>E) and (number_of_iteration < 100) do

begin

for i:=1 to 6 do Xp[i]:=X[i];

for i:=1 to 6 do

begin

sum:=0;

for j:=1 to 6 do sum:=sum+A[j,i]*X[j];

X[i]:=W*(B[i]- sum + A[i,i]*X[i])/A[i,i] + (1-W)*Xp[i];

end;

delta:=abs(X[1]-Xp[1]);

for i:=1 to 6 do

if abs(X[i]-Xp[i])>delta then delta:=abs(X[i]-Xp[i]);

inc(number_of_iteration);

end;

end;

procedure TFormk1.FormCreate(Sender: TObject);

begin

n:=6;m:=6;

matrix;

randomize;

stringgrid2.cells[0,0]:='*1';

for j:=1 to m do

StringGrid2.cells[0,j]:='5';

end;

procedure TFormk1.Button1Click(Sender: TObject);

begin

series1.clear;

for i:=0 to n-1 do

for j:=1 to m do

A[i+1,j]:=strtofloat(StringGrid1.cells[i,j]);

for j:=1 to m do

B[j] :=strtofloat(StringGrid2.cells[0,j]);

for i:=1 to 6 do

begin

max:=abs(A[1,i]);

for j:=1 to 6 do

if abs(A[j,i])>=abs(max) then

begin

max:=A[j,i];

m:=j;

end;

if m<>i then

begin

for l:=1 to 6 do

begin

tmp:=A[l,m];

A[l,m]:=A[l,i];

A[l,i]:=tmp;

end;

tmp:=b[m];

b[m]:=b[i];

b[i]:=tmp;

end;

end;

E:=0.0001;

W:=0.2;

l:=0;

while W<=1.8 do

begin

decision;

inc(l);

am[l]:=number_of_iteration;

W_all[l]:=W;

series1.addxy(W,number_of_iteration,'',clteecolor);

W:=W+0.01;

end;

min:=am[1];

for i:=1 to 200 do

if (am[i]<=min) and (am[i]<>0) then

begin

min:=am[i];

W:=W_all[i];

end;

decision;

if (number_of_iteration>100) or (delta>E) then

begin

label2.Caption:='Программа не может решить данную СЛАУ.';

label3.Visible:=false;

end

else

begin

Chart1.BottomAxis.Automatic:=false;

Chart1.BottomAxis.minimum:=0.2;

Chart1.BottomAxis.maximum:=1.8;

Chart1.BottomAxis.increment:=0.1;

Chart1.LeftAxis.Automatic:=false;

Chart1.LeftAxis.minimum:=0;

Chart1.LeftAxis.maximum:=100;

Chart1.LeftAxis.increment:=5;

label6.visible:=false;

label7.visible:=true;

label8.visible:=true;

label1.visible:=true;

StringGrid3.visible:=true;

stringgrid3.cells[0,0]:='*1';

for i:=1 to 6 do

StringGrid3.cells[0,i]:=floattostr(X[i]);

end;

end;

procedure TFormk1.N1Click(Sender: TObject);

begin

close;

end;

procedure TFormk1.N3Click(Sender: TObject);

begin

chart1.visible:=true;

end;

procedure TFormk1.N4Click(Sender: TObject);

begin

chart1.Visible:=false;

end;

end.

Результаты, рис. 3 и 4:

Рис. 3

Р ис. 4