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

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

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

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

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

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

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

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

 

 

 

 

    

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

 Отделения,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,...,п). Можно пытаться в первую очередь улучшить ту составляющую решения, которая найдена наименее точно, чтобы при нахождении всех других составляющих употреблять улучшенное ее значение. О точности можно было бы судить по вектору погрешности, , но так как вектор точного решения неизвестен, то в вычислениях заменяют другим вектором, по которому можно, хотя бы неполно, судить о погрешности . Чаще всего для этой цели пользуются вектором поправки на последнем шаге , где . Величины поправок составляющих нумеруют в порядке убывания их абсолютных значений, и в том же порядке вычисляют составляющие следующего приближения : сначала ту составляющую, которая отвечает наибольшей по модулю поправке, и т. д.