Сходимость итерационных методов
Сравнивая формулы (2.10) метода Якоби и
(2.12) метода Зейделя, можно заметить, что
если методы сходятся, то есть в некотором
смысле
,
то они сходятся к решению исходных задач
.
Теорема 2.4. Пусть А - симметричная положительно определенная матрица, A > 0; итерационные параметры удовлетворяют соотношению
.
Тогда стационарный итерационный метод сходится.
Следствие 1. Пусть А - симметричная положительно определенная матрица. Тогда метод верхней релаксации
сходится при 0 < < 2. В частности, метод Зейделя ( = 1) сходится.
Следствие 2. Пусть А - симметричная положительно определенная матрица с диагональным преобладанием, то есть имеет место
.
Тогда метод Якоби сходится.
Методы решения нелинейных уравнений: метод простых итераций, условие сходимости. Метод простых итераций
Этот метод заключается в замене уравнения
(3.1) эквивалентным ему уравнением вида
. (3.2)
После этого строится итерационный
процесс
(3.3)
при некотором заданном значении
.
Для приведения выражения (3.1) к требуемому
виду (3.2) можно воспользоваться простейшим
приемом:
Если в выражении (3.2) положить
,
можно получить стандартный вид
итерационного процесса для поиска
корней нелинейного уравнения:
.
Пример 3.1. Решим уравнение cos(x) - x = 0. Представим это уравнение в виде
.
Результаты расчетов приведены в табл. 3.1. Ход итерационного процесса отражен на рис. 3.3. Таблица 3.1
Результаты итерационного вычисления корня уравнения cos(x) - x = 0
-
итерация
Аргумент x
1
0
2
1,0
3
0,540302306
4
0,857553216
...
...
30
0,739078886
31
0,739089341
Корень уравнения (с абсолютной погрешностью
не более
)
равен 0,739085133.
Рис. 3.3. Поиск корня нелинейного уравнения cos(x) - x = 0
Рассмотрим отрезок длиной 2r с центром
в точке a:
.
Теорема 3.1. Если функция
на отрезке А удовлетворяет условию
Липшица1
с константой 0 < С < 1, причем
, (3.4)
то уравнение (3.2) имеет на отрезке А
единственное решение
,
метод простой итерации
сходится к
при любом
и имеет место оценка
. (3.5)
Доказательство.
Докажем “по индукции”, что определяемые
в соответствии с формулой (3.2) величины
.
по условию теоремы.
Пусть
;
покажем, что и
.
В силу имеем
то есть .
Теперь оценим разность получаемых решений для произвольного n:
.
Отсюда получаем
.
Для двух произвольных значений
(для определенности положим p > q) на
основании этого соотношения имеем
При выводе последнего соотношения
использована формула для суммы членов
геометрической прогрессии со знаменателем
С, а также условие, что 0 < C < 1, и тем
более
.
Очевидно, что при
имеет место
,
и в соответствии с признаком Больцано - Коши
.
Переходя к пределу в соотношении , в силу непрерывности функции получаем:
,
то есть
- решение уравнения (3.2).
Теперь покажем, что получаемое решение
единственно. В самом деле, пусть
- два различных решения уравнения (3.2).
Тогда
,
что может иметь место при условии 0 <
C < 1 лишь в случае
.
Оценим погрешность метода простой итерации после выполнения N итераций:
,
откуда получаем:
.
Что и требовалось доказать.
Следствие 1. Если
,
а также имеет место соотношение
,
то уравнение (3.2) имеет единственное решение, метод простых итераций сходится и имеет место оценка (3.5).
Действительно, согласно теореме Лагранжа,
,
то есть в качестве константы условия Липшица можно принять
.
В этом случае условия теоремы (3.1) выполняются и все ее утверждения имеют место.