Принцип сжатых отображений.

Пусть Х – полное метрическое пространство, - расстояние между элементами х и у. Пусть, кроме того, S – замкнутое ограниченное множество (компакт): S X и Т – оператор (вообще говоря, – нелинейный), действующий из S в S, то есть отображающий множество S в себя: .

Назовем точку неподвижной точкой оператора Т, если

х*=Тх*

(1)

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

х^n+1=Tx^n, х^0

(2)

При этом важно, чтобы такая последовательность { xⁿ } сходилась к единственной точке х*. Следующая теорема формулирует достаточные условия сходимости итерационного процесса (2).

Теорема 3.1. (Принцип сжатых отображений).Пусть Т – оператор сжатия на S, то есть для любых двух точек выполняются следующие два условия

1) и 2) . (3)

Тогда в S существует единственная неподвижная точка оператора Т, являющаяся пределом последовательности { xⁿ }, определяемой процедурой итераций (2), начиная с . При этом скорость сходимости оценивается неравенствами:

	(4)
	(5)

Докажем, что последовательность { xⁿ }– фундаментальная. Рассмотрим

(6)

Далее при p 1 имеем

{ вставим точку и воспользумся неравенством треугольника}

{продолжаем вставлять точки}

{на основании (6)}

(7)

Отсюда следует, что , ,

следовательно, последовательность { xⁿ } – фундаментальная, и согласно критерию Коши-Вейерштрасса последовательность { xⁿ }сходится к элементу (так как S - компакт).

Таким образом, имеем .

Далее, используя (2) и условие сжатия 2), получаем:

Следовательно, , т.е. - неподвижная точка оператора .

Докажем единственность неподвижной точки х*.

От противного. Пусть : х*=Тх*, у*=Ту*. Тогда

Полученное противоречие доказывает утверждение о единственности точки .

Далее заметим, что формула (4) следует из формулы (7) при р :

т.к. правая часть неравенства (7) не зависит от р.

Покажем, что условие (5) следует из (4). Действительно,

{неравенство треугольника}

Отсюда Деля обе части этого неравенства на (1-α), получаем (5).

Замечание. Неравенство (4) показывает, что последовательность { xⁿ } сходится к х* со скоростью геометрической прогрессии (такая скорость называется линейной): каждый шаг в раз приближает к х*. Кроме того, неравенство (4) позволяет определить, сколько итераций (шагов) необходимо сделать для достижения заданной точности . Для этого нужно решить неравенство:

относительно .

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

Теорема 3.2. Пусть Х – банахово пространство, то есть полное нормированное пространство с нормой элементов . Т – оператор, определенный на замкнутом множестве S и отображающий S в себя. Тогда, если выполняется условие

(8)

(условие Липшица с константой ), то справедливо утверждение теоремы 3.1.

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

3.2. Метод простых итераций для функциональных уравнений.

Теорема 3.3. Пусть (одномерный случай) и задана функция f (x), удовлетворяющая условиям:

1) - условие Липшица с константой на отрезке [ a, b ]; 2) .

(1)

Тогда оператор f (x) - сжимающий и уравнение f(x)=х имеет единственную неподвижную точку, которую можно найти методом простых итераций:

.

Действительно, определим . Следовательно, выполняется условие Липшица из теоремы 3.2, откуда и следует результат.

Теорема 3.4. Пусть , причем выполнены условия:

1) ; 2)

(8)

Тогда оператор f (x) является сжимающим, и справедливо утверждение теоремы 3.1, т.е. последовательность сходится к единственному коню уравнения .

Пусть , тогда , согласно условию 1) теоремы. Далее по индукции устанавливаем, что все члены последовательности принадлежат . Пусть . Согласно теореме о среднем

, . Оценим это неравенство по модулю:

согласно условию 2) теоремы.

Таким образом, выполняются все условия теоремы 3.3., откуда и следует результат.

Рассмотрим задачу поиска корней уравнения . Пусть известны границы для единственного корня этого уравнения и мы хотим найти этот корень методом итераций. Если удастся привести уравнение к виду x=f (x), так чтобы выполнялись условия теоремы 3.3 или теоремы 3.4, то в этом случае можно будет применить метод итераций. Такое преобразование, вообще говоря, не единственно, причем главная трудность заключается в определении того замкнутого ограниченного множества S (а в одномерном случае – отрезка [ a, b ]), для которого помимо условия сжатости, выполняется условие .

Лемма 3.1. Определим множество - замкнутый r -“шар” с центром в точке х ₀ (в одномерном случае – отрезок). Пусть оператор Т - сжимающий на S и выполняется следующее условие:

(9)

Тогда для любой точки выполняется: .

Достаточно доказать, что Имеем: {неравенство треугольника} .

Пример 1. Решить уравнение

с точностью .

Приведем уравнение к виду:

(10)

Графическое решение уравнения (10) приведено на рисунке 3.1.

Рис. 3.1. Графическое решение уравнения (10). Кривая (1) - график функции . Кривая (2) - график функции .

Найдем первую производную: .

При имеем: (значение можно использовать в итерациях). Можно улучшить оценку для , если заметить, что по графику на рис.3.1

. Но это значение константы сжатия следует подтвердить выполнением условия (9) леммы 3.1.

Для простоты положим =0,5 и оценим радиус “шара” r, взяв в качестве начальной точки . Тогда получим:

; .

Таким образом, если положить

,

то условие (9) выполняется. Последовательно находим:

Продолжаем процедуру, пока 4 значащие цифры после запятой не установятся. При придется сделать 10 итераций, при этом х*=х ₁₀=0,4816.

Пример 2. Решить уравнение F (x) = tg x – x= 0, x Î[ ; ].

Решить самостоятельно: построить график, затем сделать замену переменных:

x= + arctg y и привести уравнение к виду: y= + arctg y=f (y), показать, что данное уравнение удовлетворяет принципу сжатых отображений. Оценить α и запустить процедуру для ε = 0,001.

3.3. Метод Ньютона.

Пусть снова задано уравнение f (x) = 0. Запишем его тождественно в виде ,

где , и положим .

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

Отсюда находим, что . Подставляя в исходное уравнение, получаем рекуррентную формулу:

, . (11)

Это и есть итерационная процедура Ньютона.

Метод Ньютона известен и под другим названием: метод касательных. Дадим графическую иллюстрацию данного метода.

Пусть и строго выпукла (т.е. ). Пусть, кроме того, - единственный корень функции на промежутке .

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

. Далее в точке графика проводим новую касательную, и т.д. В результате получаем итерационную процедуру Ньютона (11).

Метод касательных проиллюстрирован на рис.3.2.

Рис.3.2. Графическая иллюстрация метода Ньютона (метода касательных). Начальная точка x₀ = 8. Точное значение корня x* = 1. x₁ и x₂ – два последовательных приближения к корню, полученные с помощью касательных.

Исследуем условия сходимости метода Ньютона.

Теорема 3.5. Пусть , на , и имеет единственный действительный корень на . Тогда , такое, что на множестве

процедура Ньютона (1) сходится к точке со скоростью геометрической прогрессии, а в некоторой малой окрестности точки x^* и с квадратичной скоростью.

В силу непрерывности функций на [ a,b ], обе производные ограниченыпоэтому , причем по условию.

Заметим, что итерационная процедура (11) равносильна методу простых итераций для уравнения

(12)

Очевидно, что является неподвижной точкой функционального оператора , называемого операторной функцией Ньютона-Рафсона. Проверим условия сжатости данной функции. Для этого вычислим и оценим производную . Имеем:

.

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

(13)

Поскольку - корень уравнения , то, как следует из неравенства (13),

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

Запишем формулу конечных приращений Лагранжа

.

Оценивая по модулю, получаем

.

Подставляя эту оценку в (13), получаем:

.

Условие сжатости будет, очевидно, выполнено, если

. (14)

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

Так как по условию теоремы непрерывна на , то справедливо тэйлоровское разложение функции с центром в точке с остаточным членом в форме Лагранжа

Положим в последнем равенстве :

.

Выражая отсюда , получим:

(15)

Вычтем (15) из (11):

;

Оценивая последнее равенство по модулю, получаем:

(16)

Продолжим далее оценку по модулю, используя (14):

.

Таким образом, если , где определяется из неравенства (14), то точка . Следовательно, выполняется и второе условие теоремы 3.4, а значит последовательность сходится к корню со скоростью геометрической прогрессии (т.е. линейно). Далее из неравенства (16) следует, что как только при некотором выполнится условие , так в дальнейшем, при сходимость становится квадратичной:

.

Пример 3. Вычислить с точностью до 3-х верных знаков после запятой.

Положим . Заметим, что , т.е. – строго выпукла всюду. Согласно процедуре Ньютона (11),

.

В качестве начального приближения возьмем . На третьей итерации заданная точность достигается:

x ₃=3,60555»3,6056 (точное значение .

Дата добавления: 2015-07-16