Итерационные методы решения слау

                                                    Оглавление.

1. Введение……………………………………………………………………………………………3

2. Тексты решаемых задач…………………………………………………………………….5 

3.  Скриншоты решаемой задачи…………………………………………………………..13 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение. 

Методы решения систем линейных алгебраических уравнений классифицируют на прямые (точные) и итерационные. Прямые методы основаны на выполнении конечного числа арифметических операций, это, например, метод обратной матрицы, метод Гаусса, метод Гаусса-Жордана, метод прогонки для трехдиагональных матриц и т.д. Суть итерационных методов, в свою очередь, заключаются в том, чтобы за счет последовательных приближений получить решение системы, определяемое необходимой точностью.  В данной работе я подробно рассматриваю два метода, а именно методы Якоби и Зейделя.

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

Для итерационных методов можно выделить три последовательных этапа:

1. Приведение исходной системы вида  к итерационной форме   .
2. Проверка условия сходимости. 
3. Решение системы одним из методов.

Сразу условимся, что для общего вида систем выполняется тождество m=n, где m - количество уравнений в системе, n - количество неизвестных. Т.е. не имеет смысла решать недоопределенные (m<n) и переопределенные (m>n) системы, т.к. они могут быть сведены путем элементарных алгебраических преобразований к нормальным (m=n) системам линейных уравнений. Другими словами, если у нас имеется «ненормальная» система, то прежде, чем использовать рассматриваемые методы решения СЛАУ, преобразуйте ее к нормальной.

Пусть рассматривается система Ax = b.  
Для применения итерационных методов система должна быть приведена к эквивалентному виду x=Bx+d. Затем выбирается начальное приближение к решению системы уравнений  
 и находится последовательность приближений к корню. Для сходимости итерационного процесса достаточно, чтобы было выполнено условие  . Критерий окончания итераций зависит от применяемого итерационного метода.

Метод Якоби.

Самый простой способ приведения системы к виду удобному для итерации состоит в следующем: из первого уравнения системы выразим неизвестное  x1, из второго уравнения системы выразим  x2, и т. д. В результате получим систему уравнений с матрицей B, в которой на главной диагонали стоят нулевые элементы, а остальные элементы вычисляются по формулам: 

,    i, j = 1, 2, ... n.

Компоненты вектора d вычисляются по формулам: 

,   i = 1, 2, ... n.

Расчетная формула метода простой итерации имеет вид

,

или в покоординатной форме записи выглядит так:

,  i = 1, 2, ... m.

Критерий окончания итераций в методе Якоби имеет вид:

 ,   где    .

Если   , то можно применять более простой критерий

 окончания итераций

Метод Зейделя.

Как уже говорилось, метод Якоби и метод Зейделя почти идентичны. Разница лишь в том, что в методе Зейделя расчет вектора приближений на текущей итерации происходит с использованием данных, полученных ни только на предыдущей, но и на нынешней итерации. То есть элемент x1 вычисляется на основе x2 и x3, значения которых, расчитаны на предыдущей итерации, а следующий элемент x2 уже вычисляется за счет x1, полученного именно на текущей итерации, и x3 на предыдущей. Другими словами основная идея состоит в том, что при вычислении очередного (n+1)-го приближения к неизвестному  xi при i >1 используют уже найденные (n+1)-е приближения к неизвестным  x1, x2, ..., xi - 1, а не n-ое приближение, как в методе Якоби. Расчетная формула метода в покоординатной форме записи выглядит так:

, 

i = 1, 2, ... m.. Условия сходимости и критерий окончания итераций можно взять такими же как в методе Якоби.

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

Текст решаемой задачи. 

unit Unit1;

interface

uses

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

  Dialogs, StdCtrls, Grids;

type

  TForm1 = class(TForm)

    StringGrid1: TStringGrid;

    Label1: TLabel;

    StringGrid2: TStringGrid;

    Label2: TLabel;

    OpenDialog1: TOpenDialog;

    Button1: TButton;

    Button3: TButton;

    Memo1: TMemo;

    Label3: TLabel;

    procedure Button3Click(Sender: TObject);

    procedure Button1Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  Form1: TForm1;

  i,j,n,m,k:integer;

  a,x:array of array of real;

  xx:array of real;

  f:textfile;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var

f:textfile;

i,j,n,k:integer;

a,x:array of array of real;

xx,b:array of real;

Amod,s:real;

begin

if OpenDialog1.Execute() then

begin

AssignFile(f,OpenDialog1.FileName);

Reset(f);

readln(f,n);

setLength(a,n,n+1);

setLength(x,n+1,2);

setLength(xx,n+1);

setLength(b,n);

for I:=0 to n-1 do

for J:=0 to n do

read(f,a[i,j]);

StringGrid1.RowCount:=N;

StringGrid1.ColCount:=N;

StringGrid2.RowCount:=N;

for I := 0 to N -1 do

b[i]:=a[i,n];

for I := 0 to N - 1 do

for J := 0 to N - 1 do

StringGrid1.Cells[I,J]:=FloatToStr(A[J,I]);

for i := 0 to N - 1 do

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

CloseFile(f);

AssignFile(f,OpenDialog1.FileName+'prJakobi.txt');

ReWrite(f);

write(f,'||A||=max{');

Amod:=0;

for I:=0 to n-1 do

begin

s:=0;

for J:=0 to n-1 do

s:=s+abs(a[i,j]);

if s>Amod then Amod:=s;

write(f,s:6:3,';');

end;

write(f,'}=',Amod:6:3);

if Amod>1 then writeln(f,'>1')

else

begin

//Вот тут то все и начинается

writeln(f,'<1');

s:=0;//Для поиска максимума в правой части

for i:=0 to n-1 do

if abs(a[i,n])>s then s:=abs(a[i,n]);

writeln(f,'||f||=',s:6:3);

k:=trunc(ln(0.001*(1-Amod)/s)/ln(Amod));

writeln(f,'k>=',k:6);

writeln(f);

writeln(f,'Метод Якоби');

write(f,' k ');

for i:=1 to n do

begin

write(f,' x',i:1,' ');

x[i,1]:=a[i-1,n];

end;

writeln(f,' delta k');

k:=0;

repeat

write(f,k:2);

for i:=1 to n do

write(f,' ',x[i,1]:12:6);

if k=0 then writeln(f)

else

begin

s:=0;

for i:=1 to n do

if abs(x[i,1]-x[i,0])>s then s:=abs(x[i,1]-x[i,0]);

writeln(f,s:12:6);

end;

for i:=1 to n do

x[i,0]:=x[i,1];

for i:=1 to n do

begin

x[i,1]:=0;

for j:=0 to n-1 do

x[i,1]:=x[i,1]+a[i-1,j]*x[j+1,0];

x[i,1]:=x[i,1]+a[i-1,n];

end;

k:=k+1;

until s<0.00044;

writeln(f);

writeln(f,'Метод Зейделя');

write(f,' k ');

for i:=1 to n do

begin

write(f,' x',i:1,' ');

x[i,1]:=a[i-1,n];

xx[i]:=0;

x[i,0]:=0;

end;

writeln(f,' delta k');s:=10000;

k:=0;

repeat

write(f,k:2);

for i:=1 to n do

write(f,' ',x[i,1]:12:6);

if k=0 then writeln(f)

else

begin

s:=0;

for i:=1 to n do

if abs(x[i,1]-xx[i])>s then s:=abs(x[i,1]-xx[i]);

writeln(f,s:12:6);

end;

for i:=1 to n do

xx[i]:=x[i,1];

for i:=1 to n do

x[i,0]:=x[i,1];

for i:=1 to n do

begin

x[i,1]:=0;

for j:=0 to n-1 do

x[i,1]:=x[i,1]+a[i-1,j]*x[j+1,0];

x[i,1]:=x[i,1]+a[i-1,n];

x[i,0]:=x[i,1];

end;

k:=k+1;

until s<0.00044;

write(f,'Ответ:');

for i:=1 to n do

write(f,x[i,1]:8:4)

end;

a:=nil;x:=nil;xx:=nil;

closefile(f);

end;

end; 

procedure TForm1.Button3Click(Sender: TObject);

begin

  Memo1.Lines.LoadFromFile(OpenDialog1.FileName+'prJakobi.txt');

end;

end. 

Скриншоты решаемой задачи. 

1. Скриншот файла с исходными данными.

 
 
 
 
 
 
 
 

2. Скриншоты программы.

 
 
 
 
 

 
 
 
 
 
 

3. Результаты работы программы.