Метод Релаксації для розв'язку Слар

 

Розділ 2. Практична реалізація методу релаксації

1.  Приклад розв’язання системи методом релаксації

Приклад 1: Розв’язати наступну систему методом релаксації

(2.1)

Обчислення  проводити з точністю до двох знаків після коми.

Розв’язання:

Наводимо систему (2.1) до виду, зручного для рішення методом релаксації

(2.2)

Задаємо початкове  наближення нульовими значеннями

(2.3)

Знаходимо значення невязок

 

Детальніше  див. таблицю 2.1

 

Таблиця 2.1 Процес знаходження  невідомих і нев’язок

	0	0,60	0	0,70	0	0,80
		0,16		0,16		-0,80
		0,76		0,86		0
		0,17	0,86	-0,86		0,09
		0,93		0		0,09
	0,93	-0,93		0,09		0,09
		0		0,09	0,18	0,18
		0,04		0,04		-0,18
		0,04	0,13	0,13		0
		0,03		-0,13		0,01
	0,07	0,07		0		0,01
		-0,07		0,01		0,01
		0		0,01	0,02	0,02
		0		0		-0,02
		0
		0	0,01	0,01		0
		0		-0,01		0
		0		0		0
	1,00		1,00		1,00

 

Отже,

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

Для перевірки  підставляємо знайдені значення коренів  у вихідне рівняння; в цілому система вирішена точно.

2. Блок-схема алгоритму

Рисунок 2.1 Блок-схема методу релаксації

 

 

 

3. Опис програмної реалізації методу релаксації

 

Для запуску  програми, що реалізує метод релаксації потрібно запустити файл Relax.exe. Програма Relax реалізована мовою програмування паскаль.

Програма бере дані із файлу 'a.txt', який розміщається в каталозі, де розміщена сама програма. 'a.txt' містить в першому рядку  число n, що характеризує розмірність матриці. І в наступних n рядкам містить по n+1 елементу, які відповідають коефіцієнтам матриці і вільним членам.

У програмі задана точність у змінній sigma:=1e-7, тобто 1*10^-7. Програма також обмежена максимальною кількістю кроків 10000.

Перелічимо  основні функції і процедури даної програми і їх вхідні параметри:

1. norma – знаходить норму, тобто визначає похибку. У вхідних параметрах приймає вектор правої частини системи типу TVector і повертає число – похибку типу double.
2. copyVector – робить копію вектора, що передається в параметрах. Вхідні параметри даної процедури це вектора, який копіюємо і у який копіюємо , а також їх розмірність.
3. addVector – сумує два вектори, які приймає у вхідних параметрах.
4. subVector – процедура, що знаходить різницю двох векторів, які приймає у вхідних параметрах.
5. linearSolveFullRelax – головна функція програми знаходження розв’язку СЛАР методом релаксації.

До вихідних даних даної програми належить набір  значень, що є розв’язком СЛАР. Вихідні  дані записуються в файл у кореневій  директорії програми під назвою 'result.txt'.

Текстовий приклад  роботи програми.

Внесемо у файл 'a.txt' наступні дані:

3

10 -2 -2 6

-1 10 -2  7

-1 -1 10 8

Запускаємо  програму (рис. 2.2).

Рисунок 2.2 Демонстрація роботи програми Relax.exe

Перевіряємо файл 'result.txt' і бачимо , що він містить наступні дані (розв’язок СЛАР):

      1.000000

      1.000000

      1.000000

Зауваження. Для успішної компіляції програми в середовищі Turbo Pascal 7.0 необхідно установити режим компіляції  Numeric processing в 8087/80287 (рис. 2.3)

Рисунок 2.3 Режим компіляції Numeric processing 8087/80287.

 

Висновок

 

Можна стверджувати, що майже будь-яке завдання обчислювальної математики зводиться в кінцевому  підсумку до вирішення отриманої  системи лінійних або тензорних  алгебраїчних рівнянь (СЛАР).

Але такі системи рівнянь можуть бути, по-перше, дуже великого розміру, наприклад, NxN = 10000х10000, і навіть більше, по-друге, система рівнянь може виявитися недовизначеною, по-третє, вона може виявитися з лінійно залежними рівняннями, по-четверте, вона може виявитися перевизначеною і несумісною. Крім того, по-п'яте, обчислювальна техніка може мати далеко не рекордну швидкодію і обсяг оперативної пам'яті, і явно кінцеву розрядність двійкового представлення чисел та пов'язані з цим ненульові обчислювальні похибки. Тому ітераційні методи отримали велике застосування у розв’язанні СЛАР. Сучасна обчислювальна техніка дозволяє проводити дослідження стійкості та збіжності ітераційного методу в залежності від параметрів задачі.

Найбільш ефективно  метод релаксацій застосовується при розв’язанні багатьох близьких алгебраїчних систем лінійних рівнянь. На першому етапі проводиться розв’язання однієї з систем з різними значеннями ітераційного параметра w і з аналізу швидкості збіжності ітераційного процесу вибирається оптимальне значення цього параметра. Потім всі інші системи вирішуються з обраним значенням w.

Ще одна перевага ітераційного методу верхніх релаксацій полягає в тому, що при його реалізації на ЕОМ алгоритм обчислень має  простий вигляд і дозволяє використовувати всього один масив для невідомого вектора.

При виконанні  курсової роботи я навчився розв’язувати системи лінійних рівнянь методом релаксації (ослаблення) змінних, і закріпив набуті навички розробкою програми.

 

Список використаних джерел

 

1. Воеводин В.В. «Вычислительные основы линейной алгебры». Москва «Наука», 1977.
2. Фаддеев Д.К., Фаддеева В.Н. «Вычислительные методы линейной алгебры». Москва «Физматгиз», 1963.
3. Самарский А.А., Гулин А.В.» Численные методы». Москва «Наука», 1989.
4. Самарский А.А., Николаев Е.С. «Методы решения сеточных уравнений». Москва «Наука», 1978.
5. Самарский А.А. «Введение в численные методы». Москва «Наука», 1987.
6. Стренг Г. «Линейная алгебра и ее применение». Москва «Мир», 1980.
7. Карманов В.Г. «Математическое программирование». Москва «Наука», 1989.
8. Алексеев Е.Р. «Программирование на С++». Москва «НТ Пресс», 2007.
9. http://www.exponenta.ru/   -  сайт посвящен решению математических задач в прикладных программных пакетах.
10. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. - М.: Наука, 1987.- 600 с.

 

 

 

 

 

 

 

 

 

Додатки

 

Додаток А

Текст програми

uses crt;

const

   MAX_SIZE=20;                          {максимальний размір матриці}

 

type

   TMatrix= array [1..MAX_SIZE] of array [1..MAX_SIZE] of double;

   TVector= array [1..MAX_SIZE] of double;

 

var

   i, j: integer;

   a: TMatrix;                            {матрица коефіцієнтів}

   f: TVector;                            {вектор правої частини}

   res: TVector;                          {вектор розвязання системи}

   n: integer;                            {размірність системи}

   sigma: double;                         {точність обрахунків}

   max_step: longint;                     {максимальне число кроків}

   data_file: text;                       {файл даних}

   result_file: text;                     {файл результату}

 

{евклідова норма  вектору}

function norma(var r: TVector; n: integer): double;

var

   res: double;

 

begin

   for i:=1 to n do begin

      res:=res+sqr(r[i]);

   end;

 

   norma:=sqrt(res);

end;

 

 

{копіювання  вектора}

procedure copyVector(var v: TVector;

                     var r: TVector;

                     n: integer);

var

   i: integer;

begin

   for i:=1 to n do begin

      r[i]:=v[i];

   end;

end;

 

 

{добуток матриці  на вектор}

procedure multMatrixVector(var m: TMatrix;

                           var v: TVector;

                           var r: TVector;

                           n: integer);

var

   i, j: integer;

   res: double;

 

begin

   for i:=1 to n do begin

      res:=0;

      for j:=1 to n do begin

         res:=res+m[i,j]*v[j];

      end;

      r[i]:=res;

   end;

end;

 

 

{сума векторів}

procedure addVector(var v1: TVector;

                    var v2: TVector;

                    var r: TVector;

                    n: integer);

var

   i: integer;

begin

   for i:=1 to n do begin

      r[i]:=v1[i]+v2[i];

   end;

end;

 

 

{різниця векторів}

procedure subVector(var v1: TVector;

                    var v2: TVector;

                    var r: TVector;

                    n: integer);

var

   i: integer;

begin

   for i:=1 to n do begin

      r[i]:=v1[i]-v2[i];

   end;

end;

 

 

{розв’язання  системи}

procedure linearSolveFullRelax(var a: TMatrix;      {матрица коефіцієнтів}

                               var f: TVector;        {вектор  правої частини}

                               var res: TVector;     {результат}

                               n: integer;                {розмірність системи}

                               sigma: double);       {похибка}

var

   x, r, alpha, t: TVector;

   k, max_step: longint;

 

begin

   k:=0;

   max_step:=10000;

   copyVector(f,x,n);

 

   repeat

      multMatrixVector(a,x,t,n);

      subVector(f,t,r,n);

 

      for i:=1 to n do begin

         alpha[i]:=r[i]/a[i,i];

      end;

 

      addVector(x,alpha,t,n);

      copyVector(t,x,n);

 

      k:=k+1;

   until (k>=max_step) or (norma(r,n)<=sigma);

 

   writeln('Число  кроків: ',k);

 

   if(k=max_step) then begin

      writeln('Задана точність не досягнута');

   end;

 

   copyVector(x,res,n);

end;

 

 

begin

   sigma:=1e-7;

   max_step:=10000;

 

   clrscr;

   writeln('Розвязок  СЛАР');

   writeln('Метод  повної релаксації);

   writeln;

 

   assign(data_file, 'a.txt');

   reset(data_file);

   read(data_file, n);

 

   for i:=1 to n do begin

      for j:=1 to n do begin

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

      end;

      read(data_file, f[i]);

   end;

 

   close(data_file);

 

   writeln('Розширена  матриця системи:');

   for i:=1 to n do begin

      for j:=1 to n do begin

         write(a[i,j]:14:6);

      end;

      writeln(f[i]:14:6);

   end;

   writeln;

 

   linearSolveFullRelax(a,f,res,n,sigma);

 

   writeln('Результат:');

   for i:=1 to n do begin

      writeln(res[i]:14:6);

   end;

   writeln;

 

   assign(result_file, 'result.txt');

   rewrite(result_file);

 

   for i:=1 to n do begin

      writeln(result_file, res[i]:14:6);

   end;

 

   close(result_file);

 

   readkey;

end.

 

 

 

 

 

 

 

 

 

 

 

Додаток Б

 

 

 

І-31     091851КП	Аркуш