Метод итераций. Рассмотрим уравнение вида .

Рассмотрим уравнение вида .

Функция удовлетворяет условию Липшица на отрезке [ a; b ] с константой , если справедливо следующее неравенство:

Коэффициент называется константой Липшица для функции .

Класс функций, удовлетворяющих условию Липшица, непуст. В частности, если данная функция дифференцируема на [ a; b ] (), то она удовлетворяет условию Липшица с константой (это утверждение следует из теоремы Лагранжа о конечных приращениях).

Теорема 3.1. Пусть функция определена на некотором отрезке
[ x ₀; x ₀ +r ] и удовлетворяет на нем условию Липшица с константой (0< a < 1). Пусть также справедливо условие .

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

,

где x ₀ - начальное приближение, .

Доказательство.

Покажем, что все x_k Î [ x ₀; x ₀ +r ]. Без ограничения общности можно считать, что x ₀ = 0. Тогда условие теоремы запишется следующим образом:

. (3.1)

Запишем условие Липшица:

, x Î [0; r ]. (3.2)

Так как x Î [0; r ], то x > 0, следовательно,

.

Преобразуем данное неравенство:

;

.

Рассматривая правую часть получившегося неравенства, с учетом (3.1) получаем:

.

Поскольку , следовательно, если x_{k -1}Î [0; r ], то x_k Î [0; r ],

т.е. какое бы приближение мы не брали, каждое следующее также будет попадать в указанный отрезок.

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

сходится при .

.

При фиксированном значении p выражение .

Поскольку 0< a < 1, то с ростом n выражение ® 0; следовательно, критерий сходимости Коши выполняется и существует предел:

.

Покажем, что x * является решением уравнения. Рассмотрим равенство

.

Учитывая непрерывность функции j, перейдем к пределу:

следовательно, x * - корень уравнения.

Докажем единственность решения. Пусть имеется два решения: x * и x **. Тогда

; .

Вычитая эти равенства, получим:

;

. (3.3)

С другой стороны, т.к. рассматриваемая функция удовлетворяет условию Липшица, то

. (3.4)

Сравнивая (3.3) и (3.4) и учитывая, что a < 1, получаем:

,

т.е. решение единственно.

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

Оценим погрешность метода простых итераций:

,

причем имеет место сходимость со скоростью геометрической прогрессии со знаменателем меньше 1.

Геометрический смысл метода итераций заключается в отыскании точки пересечения графиков функций y = x и y = j (x). Процесс сходимости показан на рис. 3.1, если функция убывает (-1< j ^/< 0), и на рис. 3.2, если функция возрастает (0< j ^/< 1).

Рис. 3.1. Рис. 3.2.

Условие 0 < a < 1 является достаточным, но не необходимым: если a> 1, то итерации могут разойтись, а уравнение может иметь решение. (В качестве примера следует рассмотреть функцию j (x) = bx, где b > 1. Итерации разойдутся, если в качестве начального приближения взять любое x ₀ ¹ 0.)

Метод итераций можно применять и для решения нелинейных систем уравнений.

Рассмотрим пространство Rⁿ с введенной на этом пространстве нормой || x ||.

Замкнутым шаром S(x ⁽⁰⁾, r) с центром в точке x ⁽⁰⁾ и радиусом r называется множество всех n -мерных векторов x таких, что расстояние между x и Y не превосходит r:

.

Рассмотрим нелинейное уравнение , где j - вектор-функция, а х – п -мерный вектор, т.е. рассмотрим систему:

Определим матрицу

.

Теорема 3.2. Пусть функция j непрерывно дифференцируема в шаре S. Пусть также в шаре S выполняются условия:

и .

Тогда справедливо утверждение теоремы 3.1.