Принцип сжимающих отображений

28

Прицели скимающих отображений

(Из хроники НОУ)

Настоящая статья основана на докладе, сделанном ее автором — тогда десятикласиком — на «Празднике математики» в Батуми. В ней расссказывается об одной важной теореме, которая в нашей части применяется при решении больших систем на ЭВМ, но может быть использована и для приближенного нахождения корней «типичного школьных» уравнений.

Неподвижные точки

Пусть $f$ — отображение произвольного множества $A$ в себя. Точка $x \in A$ называется неподвижной точкой $f$ отображения $f$, если

$$f(x) = x. \tag{1}$$

Когда $A \subset R$ (то есть когда $f$ — общная числовая функция), найти неподвижную точку отображения $f$ попросту означает решить уравнение (1). Обратно, если данное уравнение $g(x) = 0$, то его решение будет неподвижной точкой отображения $f$, где

$$f(x) = g(x) + x. \tag{2}$$

Рассмотрим несколько примеров.

1. Поворот плоскости на ненулевой угол около данной точки имеет единственную неподвижную точку (центр поворота).

2. Параллельный перенос плоскости на ненулевой вектор не имеет неподвижной точки.

*) О неподвижных точках расссказывается также в статье Б. Вертгейма («Квант», 1980, № 6).

3. Симметрия плоскости относительно прямой имеет бесконечное множество неподвижных точек (все точки этой прямой).

4. Отображение $x \rightarrow ax^2 + bx + c$, где $a \neq 0$, имеет две, одну или ни одной неподвижной точки в зависимости от знака выражения

$$\Delta = (b - 1)^2 - 4ac.$$

Задание 1. Построите отображение плоскости на себя, имеющееровно $n$ неподвижных точек ($n \in \mathbb{N}$).

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

Как мы заметили выше, решение любого уравнения вида $g(x) = 0$ простым приемом (приавлением $x$ к левой части уравнения) совпится к нахождению неподвижной точки некоторого отображения. Позному очень важно знать условия, при которой неподвижная точка существует, а также умет нахождение саму неподвижную точку. Такое условие мы сейчас указываем.

Пусть данное отображение $f: A \rightarrow A$, где в множество $A$ определено расстояние между точками: $d(x, y)$; (например, $A$ — подмножество прямой, плоскости или пространства). Отображение $f$ называется скимающим, если существует такое число $a < 1$, что для любых точки $x, y$ $A$

$$ad(x, y) \geq d(f(x), f(y)). \tag{3}$$

Иными словами, расстояние между образами точки меньше, чем расстояние между самими точкими, причем оно уменьшается по крайней мере в $a$ «раз», где $a < 1$. Число $a$ называется коэффициентом скимающим. Примеры:

1. Гомотетия плоскости с коэффициентом $0 < k < 1$ будет скимающим отображением (с коэффициентом скимающим $k$).

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

Теорема (приицип скимающих отображений на прямой). Вся-

29

Рис. 1.

кое сжимающее отображение $f$:
$|a; b| \rightarrow |a; b|$ интеграла в себя имеет единственный неподвижную точку.

Единостенное неподвижной точки очевидна: если бы их было две, то расстояние между ними должно быть бы измениться (по условию (3)), в то время как оно на самом деле остается неизменным (ибо сами точки не движются).

Доказательство существования основано на простом, но важном методе интеграции: берем любую точку $x_0 \in |a; b|$ и многократно применяем к ней $f$:

$$x_0, x_1 = f(x_0), x_2 = f(x_1), \dots, x_n = f(x_{n-1}), \dots$$

тогда последовательность $x_1, x_2, \dots, x_n$ … сходится к использованию неподвижной точке.

Прежде чем обосновать этот метод (то есть завершить доказательство теоремы), мы проиллюстрируем его на простейшем примере:

Пусть $f: ] - 1; 1[ \rightarrow ] - 1; 1[$ — отображение, заданное формулой $f(x) = \dot{x}^2$ (рис. 1). Возьмем точку $x_0 = 0,1$. Тогда

$$x_1 = (0,1)^2 = 0,01,$$
$$x_2 = (0,01)^2 = 0,0001,$$

Очевидно, $\lim_{k \to \infty} x_k = 0$. Точка 0 действительно неподвижна, либо $0^2 = 0$.

(Kстати, этим способом мы решили уравнение $x^2 - x = 0, x \ni 1$; 1[]).

Возвращаясь к доказательству теоремы, обозначим через $(x_n)$ последовательность (4). Покажем, что эта последовательность обладает следующим свойствам.

(K) Для любого $\varepsilon > 0$ существует такой номер $n_0$, что для всех больших номеров $n, m > n_0$ выполняется неравенство

$$d(x_n, m) < \varepsilon.$$

Иными словами, точки последовательности с достаточно большими номерами сколь угодно близки.

Чтобы это доказать, применим $k$ раз неравенство (3); получим

$$d(x_k, x_{k+1}) \leq \alpha^{k-1} d(x_1, x_2).$$

Позтому

$$d(x_n, x_{n+p}) \leq d(x_n, x_{n+1}) + d(x_{n+1}, x_{n+2}) + \dots + d(x_{n+p-1}, x_{n+p}) \leq \alpha^{n-1} + \alpha^n + \dots + \alpha^{n+p-2} d(x_1, x_n) = \frac{\alpha^{n-1}(1-\alpha)^p}{1-\alpha} d(x_1, x_n) \leq \frac{\alpha^{n-1}}{1-\alpha} d(x_1, x_2).$$

Теперь для любого данного им $\varepsilon > 0$ мы в качестве $n_0$ можем взять

$$n_0 = \log_a \frac{\varepsilon(1-\alpha)}{d(x_1, x_2)}.$$

Тогда для любых $n, m > n_0$ из неравенства (6) сразу следует нужное

30

Рис. 2.

нам неравенство (5) (проверьте!). Свойство (K) доказано.

Пользовать свойством (K), доказаем теперь сходимость последовательности $(x_n)$. Для числа $\varepsilon = 1/2$, по свойству (K), найдется такой номер $n_1$, что при $m > n_1$ выполняется $d(x_m, x_{n_1}) < 1/2$, то есть $x_m \in ]a_1; b_1[$, где $a_1 = x_{n_1} - 1/2$, $b_1 = x_{n_1} + 1/2$. Расстоянием далее число $\varepsilon = 1/4$ и аналогично найдем такой номер $n_2$, что при $m > n_2$ выполняется $x_m \in ]a_2; b_2[$, где $a_2 = x_{n_2} - 1/2$, $b_2 = x_{n_2} + 1/2$. Если одна из точек $a_2, b_2$ не лежит в $]a_1; b_1[$, то мы ее заменим на $a_1$ (соответствие $b_1$), сохранить обозначение $]a_2; b_2[$ для построенного отрезка. И так далее (см. рис. 2).

Получим последовательность интегралов

$$]a_1; b_1[ \supset ]a_2; b_2[ \supset ... \supset ]a_n; b_n[ \supset ...$$

длина $n$-го интеграла не превыходит $1/2^{n-1}$, и для каждого из них существует такой номер, что все $x_i$ с большими номерами лежат в этом интеграле.

Рассмотрим последовательность $(a_n)$ левых концов наших интегралов. Она возрастает и ограничена сверху (например, числом $b_1$) и, следовательно (см. «Алгебра и начала анализа 9», п. 32), имеет предел $x = \lim_{n \to \infty} a_n$. Покажем, что это же число $x$ является пределом последовательности $(x_n)$. Действительно,

$$d(x, x_n) \leq d(x, a_n) + d(a_n, x_n);$$

оба слагаемых в правой части скольго уголно малы (при достаточно больших $n$), стало бы $d(x, x_n)$ скольго уголно мал (при достаточно больших $n$), то есть $x = \lim_{n \to \infty} x_n$.

Нам осталось только доказать, что $x$ — неподвижная точка отображения $f$. Имеем

$$0 \leq d(x, f(x)) \leq d(x, x_n) + d(x_n, f(x)) = d(x, x_n) + d(f(x_{n-1}), f(x)) \leq d(x, x_n) + a d(x_{n-1}, x).$$

Последение два слагаемых скольго уголно малы (при достаточно больших $n$), значит, $d(x, f(x)) = 0$, то есть $f(x) = x$, что и требовалось доказать.

Легко видеть, что теорема остатся верной, если интеграл $]a; b[$ мы заменим отрезком, лучом или даже все прямой $R$. Более того, она остается верной и на плоскости.

Задание 2. Сформируйте и доказите прицили скимающих отображений для круга на плоскости.

Указание. Воспользовитесь координатами.

Если вы проделали это упражнение, вам, конечно, ясно, что наш прицили остатся верным для получения или полосы и даже в пространстве — скажем, для шара. Естественно спроисить: а как формулировать этот прицили с тем, чтобы охватить как можно больше случае? Как найти наиболее общую формулировку?

Поставив этот вопрос, мы попали в ситуацию, характерную для творческого работ математика-исследования. И сейчас мы посмотрим

Как рассуждает математик

Matematик-proфессional здесь стал бы думать примерно так:

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

Во-первых, мы пользовались определением скимающего отображения (3). Значит, в множество $A$ должно быть определено расстояние $d(x, y)$ между точками $x, y$ в прямой — это число

$$d(x, y) = |x - y|.$$

Но важно ли, что оно задается именно так? Наверное, нет: ведь на плоскости $d(x, y)$ определено иначе, а доказательство все же проходит. Стало бы, нужно смотреть, какие свойства расстояния на самом деле использются. Посмотрим.

31

В конце доказательства мы пользовались тем, что две точки, находящиеся на нульевом расстоянии, совпадают. Запишем это так:

$$d(x, y) = 0 \iff x = y.$$ (I)

Далее нам было нужно (где?), чтобы

$$d(x, y) = d(y, x)$$ (II)

(для любых $x, y \in A$).

Наконец, мы неоднократно (например, при доказательстве неравенства (6)) пользовались неравенством треугольника:

$$d(x, z) \leq d(x, y) + d(y, z)$$ (III)

(для любых $x, y, z \in A$).

Теперь подумаем — какие-нибудь другие свойства расстояния нам были нужны? Просмотрим еще раз доказательство; нет, от расстояния больше ничего не требуется. Таким образом, нам нужны лишь общные аксимоны расстояния.

Пойдем далее. Проследим, как была доказана сходимость последовательности (4), обладающей свойством (K). Довольно хитро, с использованием специфических свойств интервалов на прямой. Понять, какие именно общее свойство здесь использованы, трудно. Остается только один выход: «убрать трудность в аксиому», то есть поступил в ответ, что всякая последовательность, обладающая свойством (K), сходится. Ведь это сделать очень просто — достаточно орангиится теми множеств $A$, для которых из условий (K) следует сходимость!

Подведем итог. Доказательство проходит для скимающего отображения, если в $A$ есть расстояние, удовлетворяющее условиям (I) — (III), причем любая последовательность точек из $A$, обладающая свойством (K), сходится к точке из $A$.

Формулировка в общем случае

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

Множество $A$, на котором каждой паре точек $x, y \in A$ сопоставлено число $d(x, y) \in \mathbb{R}$, называется метрическим пространством, если для $d$ выполнены условия (I) — (III); при этом число $d(x, y)$ называется расстоянием между точками $x$ и $y$.

Послеовательность точек $x_1, x_2, \dots, x_k$, … метрического пространства $A$ называется функentialной (или последовательностью Коши), если для любого $\varepsilon > 0$ существует такой номер $n_0$, что

$$n, m > n_0 \Rightarrow d(x_n, x_m) < \varepsilon.$$

Послеовательность ($x_n$) в метрическом пространстве $A$ называется сходящейся, если существует точка $x$, такая что для любого $\varepsilon > 0$ найдется номер $n_0$, для которого

$$n > n_0 \Rightarrow d(x_n, x) < \varepsilon.$$

Точка $x$ в этом случае называется пределом последовательности $x_n$. Обозначение: $\lim_{n \to \infty} x_n = x$.

Наконец, метрическое пространство называется полным, если любая функentialная последовательность в нем сходится.

Теорема (общий принцип сложимощих отображений). Любое скимающее отображение полного метрического пространства в себя имеет единственное неподвижную точку.

Доказательство по существу не отличается от доказательства первой теоремы, только конец процесса: из того, что последовательность (4) функentialна (то есть обладает свойством (K)), и из полоты пространства $A$ по определению следует, что (4) сходится.

Задание 3. Напишите доказательство подробно.

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

32

Как работает ЭВМ
Мы уже отмечали, что метод интерации дает нам способ приближенного нахождения неподвижной точки:
так как последовательность $x_0, x_1 = f(x_0), x_2 = f(x_1)$, … сходится к $x$, точку $x$ можно получить с заданной точностью $\varepsilon$, выбрав номер $n$ так, чтобы $|x_n - x| < \varepsilon$.

Это прекрасно может сделать компьютер, действующий по алгоритму, показанному на рисунке (так называемой «блок-схеме» алгоритма). Посмотрите на него внимательно и попытите, как действует этот алгоритм.

Ясно, что в условиях теоремы о скимаюших отображениях машина после конечного числа интерации выдает на печать число $x_n$, удовлетворящее условию $|x_n - x| < \varepsilon$, то есть приближенное (с заданной точностью $\varepsilon$) значение $x$. Если же эти условия не выполнены, машина может «работать вечно» (если она не сломается, так и не выдав нам ответа).

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

Задание 4. Применить описанный выше алгоритм для приближенного решения уравнения
$$g(x) = x^3 + 3x + x \cos^2 x - \sin(\cos x) = 0,$$

Рис. 4.