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

МИНИСТЕРСТВО КУЛЬТУРЫ РОССИЙСКОЙ ФЕДЕРАЦИИ 
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

КИНО И ТЕЛЕВИДЕНИЯ»

КУРСОВАЯ РАБОТА

По дисциплине: Информатика

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

 

 

 

 

    

                      Выполнила: студентка заочного

 Отделения,6 курса

Бибикова М.А.

Проверил:

 

 

                                          Содержание

Содержание 2

Введение 3

1.Метод итераций 5

1.1.Описание метода 5

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

2.Метод ЗейделЯ 10

2.1.Описание метода 10

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

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

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

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

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

Заключение 23

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

 

                                                 Введение

 

Способы решения линейных систем уравнений разделяют в  на 2 группы.

Первые, точные методы представляющие собой конечные алгорифмы для вычисления корней системы (таковыми например,  являются правило Крамера, метод Гаусса, метод главных элементов, метод квадратных корней и др.).

Вторые, итерационные методы позволяющие получить корни системы  с заданной точностью путем сходящихся бесконечных процессов (к числу  таковых относят, метод итераций, метод Зейделя, метод релаксации).

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

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

Заметим, что эффективное  применение итерационных методов существенно  зависит от удачного выбора приближения  и быстроты итерационного процесса.

Сейчас разберем несколько  определений которые будем использовать в этой работе.

Система  линейных уравнений  с n неизвестными (или, линейная система) в линейной алгебре — это система  уравнений вида

 

    (1)

 

 

Здесь   — неизвестные, которые надо определить. — коэффициенты системы — и — свободные члены — предполагаются известными. Индексы коэффициентов ( ) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно.

 

Система (1) называется однородной, если все её свободные члены равны  нулю ( ), иначе — неоднородной.

 

Система (1) называется квадратной, если число m уравнений равно числу n неизвестных.

 

Решение системы (1) — совокупность n чисел  , таких что подстановка каждого ci вместо xi в систему (1) обращает все ее уравнения в тождества.

 

Система (1) называется совместной, если она имеет хотя бы одно решение, и несовместной, если у нее нет  ни одного решения.

 

Совместная система вида (1) может иметь одно или более  решений.

 

Решения и совместной системы вида (1) называются различными, если нарушается хотя бы одно из равенств:

 

=   соответственно

 

Совместная система вида (1) называется определенной, если она  имеет единственное решение; если же у нее есть хотя бы два различных  решения, то она называется неопределенной. Если уравнений больше, чем неизвестных, она называется переопределённой.

 

                                                   1.Метод итераций

1.1.Описание метода

При большем числе неизвестных  Линейная система (ЛС впоследствии) схема  метода Гаусса, дающая точное приближение, становиться весьма сложной.

В этих условиях для нахождения корней системы иногда удобнее использовать приближенные методы вычисления. Изложим  здесь один из из этих методов – метод итераций.

Пусть дана ЛС

Введя в рассмотрение матрицы

                               (1)

Систему 1 коротко можно  записать в виде матричного уравнения

              (1’)

Предполагая, что диагональные коэффициенты

Разрешим первое уравнение  первое уравнение системы (1) относительно , второе относительно и т. д. Тогда получим эквивалентную систему

       (2)

 

где   при

и при

 

введя матрицы

 

  и 

 

Систему (2) можем записать в матричной форме

 

          (2’)

 

Систему (2) будем решать методом  последовательных приближений. За нулевое  приближение принимаем, например столбец  свободных членов т.е.

Далее строим матрицы столбцы

 

 

Первое приближение

 

 

Второе приближение

Вообще говоря, любое (k+1)-е приближение вычисляется по формуле:

 

          (3)

 

Если последовательность приближений

 

 

Имеет придел

 

То этот придел является решением системы (2). В самом деле, переходя к приделу в равенстве (3) будем иметь:

 

 

или

 

 

т.е. предельный вектор x является решением системы (2’), а следовательно, и системы (1).

Напишем формулы приближений  в развернутом виде

 

Заметим, что иногда систему (1) выгоднее приводить к виду (2), так  чтобы коэффициенты не были равны нулю.

Вообще имея систему:

 

 

 

можно положить

 

 

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

 

 

где

 

    

 

при

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

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

Пример:

Решить систему

 

 

методом итераций

Здесь диагональные элементы, >> чем недиагональные

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

 

 

В матричной форме можно  записать:

 

 

За нулевое приближение  принимаем свободное приближение

 

         

 

K
0	2	3	5
1	1.92	3.19	5.04
2	1.9094	3.1944	5.0446
3	1.90923	3.1945	5.04485

 

Замечание: при применении метода простой итерации нет необходимости  брать за нулевое приближение  столбец свободных членов. Как  будет доказано ниже, сходимость процесса зависит от свойств матрицы  .

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

Теперь докажем сходимость процесса итерации, для этого надо доказать сходимость .

Выясним условия сходимости последовательности

 

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

 

  .         (3)

 

Д о к а з а т  е л ь с т в о. Найдем значение любого выражения через

  (4)

 

Отсюда и из условия  теоремы с учетом свойств опеделителя матрицы сразу следует что при и

 

,

 

Откуда  .

Что касается необходимости  условия , то ответ на вопрос дает

 

Т е о р е м а 2. Если требовать, чтобы последовательность сходилась к при любом начальном приближении , то условие (3) является необходимым

 

Д о к а з а т  е л ь с т в о.  Пусть для всякого начального приближения будет . Имеем

 

.

 

При разность стремиться к нулю, поэтому последний член цепи равенства должен стремиться к нулю, каким бы ни был вектор . Отсюда следует, что , последнее же будет лишь в том случае, когда верно неравенство (3)

Применение теорем 1 и 2 требует  знания границ собственных значений матрицы В; нахождение их часто является нелегкой задачей. Укажем более простые, но только достаточные признаки сходимости.

 

 Т е о р е м а 3. Для того чтобы последовательность приближений в методе простой итерации сходилась, достаточно, чтобы какая-либо норма матрицы В была меньше единицы.

 

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

Непосредственным следствием теоремы (3) и равенств определяющих кубическую и октаэдрическую норму матрицы, является

 

Т е о р е м а 4. Последовательность в методе простой итерации сходится, если для матрицы В выполняется одно из неравенств:

 

1.  
2.  

 

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

Т е о р е м а 5. Если какая-либо норма матрицы В, согласованная с рассматриваемой нормой вектора , меньше единицы, то верна следующая оценка погрешности приближения в методе простой итерации:

 

.      (5)

 

Д о к а з  а т е л ь с т в о. Для выше дано выражение (4), и так как , то

Поэтому

 

       (6)

 

и, стало быть,

 

.

 

Часто за принимают вектор b. В этом случае оценка (5) немного упростится; подставляя =b в (6) получим

 

. 

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

2.1.Описание метода

Метод Зейделя применяют  в двух видоизменениях. Рассмотрим сначала случай канонической формы  системы для метода итерации

 

                                                                                 (1)

 

В методе простой итерации следующее приближение  находится по предыдущему путем подстановки x^k в правую часть всех уравнений системы (1). Для нас сейчас удобнее записать результат подстановки не в векторной форме, а в развернутом виде по составляющим:

 

                                                                         (2)

 

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

О принципах выбора порядка  уравнений будет говориться ниже, а сейчас предположим, что для  перехода от приближения  к следующему — нами выбран какой-то порядок привлечения уравнений для подстановок. Изменяя, если необходимо, нумерацию уравнений и неизвестных, можно считать, что уравнения для подстановок берутся в порядке роста их номеров. Для каждого шага от приближения k до k+1 порядок привлечения уравнений может быть своим, и должны быть выполнены свои изменения нумерации и перестановки, что влечет за собой свое изменение матрицы В системы и свободного вектора b. Чтобы отметить это, обозначим матрицу В для рассматриваемого, шага и свободный вектор . В этих обозначениях итерация в методе Зейделя выполняется в следующем порядке:

 

                        (3)                                    

 

После нахождения вектора устанавливают порядок подстановок в уравнения значений  (i = 1, ..., п) и переходят к вычислению вектора  и т. д.

Приведем теперь пример принципа, на основании которого можно устанавливать  порядок привлечения уравнений  для подстановок  (i = 1,...,п). Можно пытаться в первую очередь улучшить ту составляющую решения, которая найдена наименее точно, чтобы при нахождении всех других составляющих употреблять улучшенное ее значение. О точности можно было бы судить по вектору погрешности, , но так как вектор точного решения неизвестен, то в вычислениях заменяют другим вектором, по которому можно, хотя бы неполно, судить о погрешности . Чаще всего для этой цели пользуются вектором поправки на последнем шаге , где . Величины поправок составляющих нумеруют в порядке убывания их абсолютных значений, и в том же порядке вычисляют составляющие следующего приближения : сначала ту составляющую, которая отвечает наибольшей по модулю поправке, и т. д.

Пример:

 

 

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

 

 

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

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

 

 

 

 

Результаты вычисления корней приведены в Таблице ниже с  точностью до 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²¹ и являете настолько большим, что становится ясной невозможность решать указанным путем на современных машинах систему даже двадцати уравнений.