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

Содержание

 

 

Введение

При решении большого класса прикладных задач возникает  необходимость в нахождении корней САУ. Методы решения САУ можно разделить на два больших класса: точные и итерационные.

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

Итерационные методы решения САУ характеризуется  тем, что точное решение системы  они могут, вообще говоря, давать лишь как предел некоторой бесконечной  последовательности векторов. Исходное приближение при этом разыскивается каким-либо другим способом или задается произвольно. При выполнении определенных требований можно получить достаточно быстро сходящийся к решению итерационный процесс. К этому классу методов относятся: метод итераций и метод Зейделя. 

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

 

Составить программу  решения трапецендиального уравнения  вида x_i=F_i(x₁,х₂,…х_n) модифицированным методом Зейделя. Получить решение системы

Максимальное число  итераций и погрешность вычислений задается с клавиатуры по запросу пользователя.

Для решения задачи используем подпрограммы в которых организуем ввод исходных массивов данных и подпрограмму для  вычисления по исходному методу. Так  же для решения программ используют команды повторения и команды проверки условия для проверки нахождения решения уравнения с заданной точностью. 

2. Математическая формулировка задачи

Метод Зейделя является модификацией метода итераций. Отличие  от метода итераций заключается в  вычислительной процедуре нахождения приближения на i+1 итерации. В отличии от метода простых итераций, где для отыскания i+1 приближения используется i -ое приближение неизвестных xij , в методе Зейделя используются уже вычисленные i+1 значения x .

Для применения метода простой итерации из системы уравнений берется начальное приближение , которое предполагается либо известным, либо произвольным, строим последовательность

 

по следующим формулам

 

Замечание. Для изменения системы уравнений можно использовать прием:

где – релаксационный параметр, определяется методом Зейделя.

Как говорилось выше в методе Зейделя вычисления ведутся по формулам:

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

 

3. Алгоритм решения задачи

 

В переменную е – максимальная абсолютная погрешность. С помощью вспомогательной процедуры ReadSystem в двумерный массив а и одномерный массив b вводится с клавиатуры расширенная матрица системы. Начальное приближение предполагается равным нулю. Оба массива и переменные n и e передаются функции Seidel. в функции Seidel исследуется сходимость системы, и в случае если система не сходится, выполнение функции прекращается с результатом false. В ходе получения погрешность становится меньше заданной, выполнение функции прекращается. Полученное решение выводится на экран при помощи вспомогательной процедуры WriteX.

 

4. Таблица идентификаторов

 

Математическое обозначение  величины	Обозначение в программе	Математический смысл
i	i	Номер строки массива  данных, целочисленная величина
j	j	Номер столбца массива  данных, целочисленная величина
хij	Aij	Двумерный массив данных
е	е	Точность вычислений
n	n	Количество уравнений, целочисленная величина

 

5. Блок – схемы программы

 

Рисунок – Блок-схема  основной программы

 

 

Рисунок – Процедура WriteX

 

 

 

 

 

Рисунок – Процедура ReadSystem 

6. Программа на языке Паскаль

program m_seidel;

Uses CRT;

const n=3;

Type

Matrix = Array[1..n, 1..n] of Real;

Vector= Array[1..n] of Real;

{Процедура ввода  расширенной матрицы системы  }

Procedure ReadSystem(n: Integer; var a: Matrix; var b: Vector);

Var

i, j, r: Integer;

Begin

r := WhereY;

GotoXY(2, r);

Write('A');

For i := 1 to n do begin

 

GotoXY(i * 6 + 2, r);

Write(i);

GotoXY(1, r + i + 1);

Write(i:2);

end;

GotoXY((n + 1) * 6 + 2, r);

Write('b');

For i := 1 to n do begin

For j := 1 to n do begin

GotoXY(j * 6 + 2, r + i + 1);

Read(a[i, j]);

end;

GotoXY((n + 1) * 6 + 2, r + i + 1);

Read(b[i]);

end;

End;

{ Процедура  ввода результатов}

Procedure WriteX(n :Integer; x: Vector);

Var

i: Integer;

Begin

For i := 1 to n do

Writeln('x', i, ' = ', x[i]:6:4);

readln;

End;

{ Функция, реализующая  метод Зейделя}

Function Seidel(n: Integer; a: Matrix; b: Vector; var x: Vector; e: real)

:Boolean;

Var

i, j: Integer;

s1, s2, s, v, m: real;

Begin

{ Исследуем  сходимость}

If j <> i then

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

If s >= Abs(a[i, i]) then begin

Seidel := false;

Exit;

end;

Repeat

m:= 0;

For i := 1 to n do begin

{ Вычисляем суммы}

s1 := 0;

s2 := 0;

For j := 1 to i - 1 do

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

For j := i to n do

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

{ Вычисляем  новое приближение и погрешность}

v := x[i];

x[i] := x[i] - (1 / a[i, i]) * (s1 + s2 - b[i]);

If Abs(v - x[i]) > m then

m := Abs(v - x[i]);

end;

Until m < e;

Seidel := true;

End;

Var

i: Integer;

a: Matrix;

b, x: Vector;

e: real;

Begin

{ClrScr;}

Writeln('Программа  для решения систем уравнений  методом Зейделя');

Writeln;

Writeln('Введите точность вычислений');

Repeat

Write('>');

Read(e);

Until (e > 0) and (e < 1);

Writeln;

Writeln('Введите  расширенную матрицу системы');

ReadSystem(n, a, b);

Writeln;

{ Предполагаем  начальное приближение равным  нулю}

For i := 1 to n do

x[i] := 0;

If Seidel(n, a, b, x, e) then begin

Writeln('Результат  вычислений по методу Зейделя');

WriteX(n, x);

end

else

Writeln('Метод Зейделя  не сходится для данной системы');

Readln;

End.

 

7. Правила работы в программе

 

Для запуска программы  необходимо выполнить следующие действия:

1. Запустить Turbo Pascal.
2. В среде Turbo Pascal загрузить программу (команда меню File® Open).
3. Запустить программу на выполнение командой меню Run® Run
4. Ввести точность вычисления, программа выполнит вычисления и выведет результат на экран.

 

 

Чтобы выйти из программы, пользователь должен завершить работу среды Turbo Pascal: команда меню File® Exit 

8. Заключение

 

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

В случае, когда порядок  системы большой (много уравнений), человеку становится тяжело выводить каждое уравнение, поэтому он задаёт решение хитрым образом. Если присмотреться к уравнениям, то можно узреть закономерность: для вычисления Cx мы отнимаем от Bx сумму всех (кроме одного) Axy*Cy (т.е. Y пробегает от 0 до m-1, перескакивая через X) и делим всё это на Bxx.

 

 

 

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

 

1. Немнюгин С.А. TURBO PASCAL. Практикум. – М. 2005.

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

3. Грошев А.С. Практикум  по программированию в системе  ТУРБО ПАСКАЛЬ 7.0. – Архангельск  2002