3.1. Численные методы алгебры. Принцип сжатых отображений

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

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

Х*=Тх*

(1)

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

Хn+1=Txn , Х0

(2)

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

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

1) и 2) . (3)

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

	(4)
	(5)

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

(6)

Далее при P1 имеем

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

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

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

(7)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(8)

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

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

< Предыдущая		Следующая >