3.3. Сжимающие отображения

Пусть — метрическое пространство. Преобразование называется сжимающим отображением (или сжатием), если существует такое число что:

Число s называется коэффициентом сжатия. Сжимающее отображение есть частный случай отображения Липшица, которое также определяется формулой (3.8), где . В этом случае положительная постоянная s называется постоянной Липшица. Таким образом, сжимающее отображение есть отображение Липшица с постоянной меньше 1.

Легко убедиться в том, что вещественное дифференцируемое отображение определенное на прямой R, есть отображение Липшица если для всех (см. упр. 1 в конце этого параграфа).

Если к тому же s < 1, то f есть сжимающее отображение. Например,

определяет сжатие на R, так как . Более интересный пример — отображение на отрезке Оно не является сжатием, так как это отображение Липшица с постоянной 1. Тем не менее, для любого а это отображение является сжатием на отрезке [0, а] (упр. 2 в конце параграфа).

Основные результаты теории сжимающих отображений связаны с неподвижными точками таких отображений. Точка называется неподвижной точкой отображения если:

Понятие неподвижной точки имеет огромное значение, хотя это и не очевидно с первого взгляда. Метод неподвижной точки является основным инструментом математического анализа при доказательстве теорем существования. С его помощью удается, во-первых, доказать существование решения различных уравнений (алгебраических, дифференциальных и др.), а во-вторых, построить это решение. Например, известный метод Ньютона нахождения нулей функции опирается именно на теорию неподвижной точки (упр. 6 в конце параграфа). Мы воспользуемся результатами этой теории для того, чтобы доказать существование предела последовательности множеств, сходящихся к фракталу, и разработать общую схему построения разнообразных фракталов (глава 4).

Если в качестве X взять отрезок в пространстве R, то все основные свойства неподвижных точек можно изобразить графически. Легко заметить, что даже если — просто непрерывная функция из (не обязательно сжатие), то у нее есть неподвижная точка, совпадающая с точкой пересечения графиков (рис. 3.5). Интуиция подсказывает: раз график функции начинается слева а затем движется вправо, не покидая квадрата то он не может не пересечь график функции в некоторой точке внутри квадрата. Упр. 3 в конце параграфа посвящено аналитическому доказательству этого наблюдения. Надо отметить, что, к сожалению, доказать существование неподвижной точки в произвольном метрическом пространстве гораздо сложнее.

Рис. 3.5. Неподвижная точка

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

Теорема 3.3.3, которую мы докажем ниже, утверждает, что и что — единственная неподвижная точка. Процесс сходимости можно изобразить графически, с помощью так называемых паутинных диаграмм (они будут интенсивно использоваться в главе 6).

Рис. 3.6. Алгоритм поиска неподвижной точки

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

Алгоритм 3.3.1. (ПАУТИННАЯ ДИАГРАММА)

Назначение: строит паутинную диаграмму для функции

Вход:

Внешняя функция:

Выход:

графическое окно с паутинной диаграммой для функции

Инициализация:

графический экран с окном

Шаги:

построить график

построить график

провести линию из точки в точку

провести линию из провести линию из

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

Лемма 3.3.1. Пусть — метрическое пространство, — сжимающее отображение с коэффициентом сжатия s, причем — произвольная начальная точка, . Тогда для всех к имеет, место неравенство:

Доказательство. Многократно применяя неравенство треугольника, получим:

Для каждого члена в правой части имеем:

Подставим эти оценки в правую часть неравенства:

Следующая теорема использует условие полноты метрического пространства . Это понятие подробно изложено в прил. . Пока же ограничимся достаточным условием полноты, а именно, если X совпадает с или его замкнутым подмножеством и d — евклидова метрика, то (X, d) — полное метрическое пространство.

Теорема 3.3.3. Пусть (X, d) — полное метрическое пространство, — сжимающее отображение. Тогда отображение имеет в точности одну неподвижную точку, то есть существует такая точка , что:

Кроме того, метод итераций:

где произвольная точка из X, сходится к неподвижной точке . То есть:

Доказательство. Единственность. Докажем сначала, что если неподвижная точка существует, то она единственна. Пусть s — коэффициент сжатия Если имеет две неподвижные точки,

Так как неравенство выполняется только при

Существование и сходимость. Эта часть доказательства использует критерий Коши сходимости последовательностей в полных метрических пространствах (см. прил. А.1). Именно, последовательность сходится к пределу в полном метрическом пространстве (X, d) тогда и только тогда, когда: для каждого существует такой номер N (зависящий от ), что при выполняется неравенство

Заметим, что:

так как

Из неравенств (3.11) и (3.9) следует:

Зафиксируем . Выберем номер N, удовлетворяющий условию:

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

существует в полном метрическом пространстве Обозначим его через Так как Т непрерывно, то учитывая (3.7) имеем:

Следовательно, предел из (3.10) действительно является неподвижной точкой Т. Тем самым теорема доказана.

Стоит еще раз отметить тот замечательный факт, что согласно доказанной теореме, последовательность сходится к единственной неподвижной точке независимо от выбора начальной точки