Метод итераций и метод Зейделя

Пример:

 

 

Приведем эту систему  к удобному для итерации

 

 

В качестве нулевых приближений  корней возьмем 

Применяя последовательно  процесс решения методом Зейделя

 

 

 

 

Результаты вычисления корней приведены в Таблице ниже с  точностью до 4-х знаков

 

 

i
0	1.2000	0.0000	0.0000
1	1.2000	1.0600	0.9480
2	0.9992	1.0054	0.9991
3	0.9996	1.0001	1.0001
4	1.0000	1.0000	1.0000
5	1.0000	1.0000	1.0000

 

Точные значения: ; ;

2.2.Сходимость метода.

Остановимся более подробно на стационарном методе Зейделя; когда при итерациях порядок уравнений сохраняется, матрица В будет одинаковой на всех шагах и составляющие следующего приближения находятся при всяком k по правилу (3).

Разложим матрицу В на сумму двух матриц Н и F, где

 

  .

 

Тогда равенства (2) можно  записать в форме матричного равенства

 

 

откуда следует, что , а так как определитель матрицы

 

 

равен единице и она имеет обратную, то равенство (3) равносильно

 

.                   (4)

 

Поэтому стационарный метод  Зейделя равносилен методу простой итерации, примененному к системе

 

.

 

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

Этот признак может  быть высказан в форме, не требующей обращения Е — Н. Если воспользоваться тем, что   ,   то   можно написать систему равенств

 

 

Поэтому верна

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

 

 

были по модулю меньше единицы.

Укажем еще более простой  достаточный признак сходимости. Предварительно докажем лемму.

Л е м м а 1. Если в матрице диагональные элементы доминируют по строкам или по столбцам, т. е. если

 

 

 

или

 

 

 

 

то определитель матрицы А отличен от нуля.

Д о к а з а т  е л ь с т в о. Для определенности предположим, что имеет место доминирование по строкам. Достаточно показать, что однородная система

 

Ах = 0                                              (6)

 

имеет только нулевое решение.

Допустим противоположное  и будем считать, что система имеет ненулевое решение , Среди составляющих решения выберем наибольшую по модулю;   

 

  

                                                     

Положим и оценим снизу левую часть уравнения номера i системы.(6):

 

 

гак   как и по   условию

леммы. Этот результат противоречит тому, что  есть решение системы, и доказывает неверность допущения.

Т е о р е м а 2. Для сходимости стационарного метода Зейделя (4) достаточно, чтобы выполнялось какое-либо одно из условий:

 

          (7)

 

Или

 

         (8)

 

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

Нужно показать, что  при  выполнении  условия   (7) нее корни уравнения (5) будут по модулю меньше единицы. Будем считать, что  , и рассмотрим сумму модулей   недиагональных   элементов   строки   номера   i матрицы :

 

 

Таким  образом, диагональные элементы  матрицы  доминируют  по  строкам,   и   на  основании леммы 1 определитель этой матрицы отличен от нуля, а значение , для которого , не может быть корнем уравнения (6). Корни этого уравнения все по модулю меньше единицы, и по теореме 1 стационарный метод Зейделя сходится.

2.3.Другая форма метода Зейделя

В ней требуется предварительное преобразование системы Ах =b к виду, в котором все диагональные коэффициенты отличны от нуля. Такое приведение стремятся выполнить, если это возможно, так, чтобы диагональные коэффициенты были наибольшими или даже доминирующими в соответствующих уравнениях.

Мы ограничимся описанием  только стационарного процесса. Пусть  взято какое-либо исходное приближение  к решению системы. Приближение номера k+ 1 находят по приближению номера k с помощью системы соотношений

 

        (9)

 

Если разложить матрицу А на сумму двух матриц

 

 и 

 

то равенства (9) можно  записать в матричном виде

 

Bx^k+l + Cx^k=b,

 

или

 

 

Поэтому ясно, что метод  Зейделя в форме (9) равносилен методу простых итераций, примененному к системе в каноническом виде:

 

 

Для сходимости метода при  любом векторе b необходимо  и  достаточно,   как   следует   из   теорем   2   и   3,

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

 

,

 

и можно формулировать  следующую теорему.

Т е о р е м а 3. Для того чтобы процесс Зейделя, определяемый равенствами (9), сходился при любых свободных членах необходимо и достаточно, чтобы корни уравнения

 

 

все были меньше единицы  по модулю.

 

                                  3.Практическая часть

 

Здесь рассматриваются алгоритмы  описанных выше методов с описанием.

Все программы написаны в  среде Turbo Pascal.

3.1.Метод простой итерации

program iter;

var A: array [1..4,1..4] of real;

    b,x,otv: array [1..4] of real;

    i,j,n: byte;

    eps: real;

    pr: boolean;

begin

write('razmer matrix n=');

readln(n);

for i:=1 to n do   {Ввод данных}

for j:=1 to n do

begin

write('A[',i,',',j,']=');

readln(A[i,j]);

end;

for i:=1 to n do

if a[i,i]=0 then begin

writeln('oshibka vvoda');             {проверка чтобы на диагонали не было

                     exit;   нулевых коэффициэнтов}

                 end;

for i:=1 to n do

begin

write('b[',i,']=');

readln(b[i]);

end;

for i:=1 to n do

begin

for j:=1 to n do

begin

if i=j then continue;        {Выражаем x1,x2,x3…из системы}

a[i,j]:=-a[i,j]/a[i,i];

end;

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

a[i,i]:=0;

end;

for i:=1 to n do

begin

for j:=1 to n do

write(a[i,j]:4:2,'  ');

writeln(b[i]:4:2);

end;

for i:=1 to n do

x[i]:=0;

write('tochnost=');  {Вводим точность}

readln(eps);

repeat

for i:=1 to n do

begin

for j:=1 to n do

otv[i]:=otv[i]+a[i,j]*x[j];   {алгоритм решения}

otv[i]:=otv[i]+b[i];

end;

 

for i:=1 to n do

if abs(otv[i]-x[i])<eps then pr:=true;

 

for i:=1 to n do

begin

x[i]:=otv[i];

otv[i]:=0;

end;

until pr;

for i:=1 to n do

writeln(x[i]);  {Вывод результата}

end.

 

Контрольный тест

Размер матрицы

4

 

Введите точность вычислений

0.000001

 

Введите расширенную матрицу  системы

A      1      2      3      4       b

 

1     4.1   0.1   0.2   0.2   21.14

2     0.3   5.3   0.9   -0.1  -17.82

3     0.2   0.3   3.2   0.2   9.02

4     0.1   0.1   0.2   -9.1  17.08

 

 

 

Результат вычислений по методу простой итерации

5.1999999341E+00

-4.2000000396E+00

2.9999996021E+00

-1.7999999492E+00

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

program seidel;

var A: array [1..4,1..4] of real;

    b,x,otv: array [1..4] of real;

    i,j,n: byte;

    eps,s1,s2: real;

    pr: boolean;

begin

write('razmer matrix n=');

readln(n);

for i:=1 to n do

for j:=1 to n do   {Ввод данных}

begin

write('A[',i,',',j,']=');

readln(A[i,j]);

end;

for i:=1 to n do

if a[i,i]=0 then begin

                     writeln('oshibka vvoda');   {Проверка на сходимость}

                     exit;

                 end;

for i:=1 to n do

begin

write('b[',i,']=');

readln(b[i]);

end;

for i:=1 to n do

begin

for j:=1 to n do

begin

if i=j then continue;

a[i,j]:=-a[i,j]/a[i,i];    {Выражение аргументов}

end;

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

a[i,i]:=0;

end;

for i:=1 to n do

begin

for j:=1 to n do

write(a[i,j]:4:2,'  ');

writeln(b[i]:4:2);

end;

for i:=1 to n do

begin

x[i]:=b[i];

otv[i]:=b[i];

end;

write('tochnost=');

readln(eps);

 

repeat

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];

x[i]:=s1+s2+b[i];

end;

for i:=1 to n do

if abs(otv[i]-x[i])<eps then pr:=true

                        else begin

                             pr:=false;

                             break;

                             end;

for i:=1 to n do

otv[i]:=x[i];

 

until pr;

for i:=1 to n do

writeln(x[i]);   {Вывод результата}

end.

 

 

Контрольный тест

 

Размер матрицы

4

 

Введите точность вычислений

0.000001

 

Введите расширенную матрицу  системы

A      1      2      3      4       b

 

1     4.1   0.1   0.2   0.2   21.14

2     0.3   5.3   0.9   -0.1  -17.82

3     0.2   0.3   3.2   0.2   9.02

4     0.1   0.1   0.2   -9.1  17.08

 

 

 

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

5.2000000061E+00

-4.2000000026E+00

2.9999999999E+00

-1.8000000000E+00

 

                                           Заключение

Линейные системы имеют в вычислениях очень большое значение, так как к ним может быть приведено приближенное решение широкого круга задач. Теория этих систем сравнительно проста и доведена во многих частях до совершенства. Что же касается практики решения систем, то наши возможности еще сильно отстают от потребностей. Здесь многое зависит от порядка системы, т. е. от числа уравнений и неизвестных в ней. С увеличением порядка число операций, нужных для решения системы, быстро растет.

Число операций, требующихся  для решения, зависит не только от порядка системы, но также от выбора метода вычислений. Поясним это примером. Предположим, что дана система п уравнений с п неизвестными и с определителем, отличным от нуля. По теореме Крамера система имеет единственное решение. В этой теореме указывается явное выражение для значений неизвестных в виде отношения двух определителей порядка я, при этом число различных определителей в отношениях

равно .

Пусть для нахождения решения  мы хотим воспользоваться теоремой Крамера, при этом детерминанты будем вычислять по их обычному определению, как сумму со знаками произведений элементов по одному из каждой строки и каждого столбца. Легко можно подсчитать, что для нахождения решения нужно будет приблизительно п^гп  умножений и делений. Уже при  п = 20 это число приблизительно равно 10²¹ и являете настолько большим, что становится ясной невозможность решать указанным путем на современных машинах систему даже двадцати уравнений.