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

5

Б. Вергейм

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

Когда мы ищем решение какого-нибудь уравнения, хорошо знать заранее, что у него есть решение — ведь если нет, то зачем время зря тратить? Это сообщение становится весом серъезным, когда речь идет о решении сложных уравнений и систем на мощных ЭВМ с дорогостями машинным временем. Поэтому очень важно роль играют так называемые теоремы существования и, которые заранее гарантируют наличие решения. Об одной из них — теореме Брауэра о неподвижной точке, интересной и полезной уже на школьном уровне, — и рассказано в этой статье.

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

Путниковоеовое один направляется из пункта $a$ в пункта $b$, другой все время гуляет на дороге $ab$. Очевидно, их встреча неизбежна: путики хотят бы раз поравняются (оказутся одновременно в одной точке). Опишем это подробнее (рис. 1).

Пусть $x$ — координата первого ($a \leqslant x \leqslant b$) путика и скорость его постоянна; $y$ — координата второго ($a \leqslant y \leqslant b$). Каждому значению $x$ (положению первого путика) соответствует единственное значение $y$ (положение второго путика в тот же момент времени); итак, имеем функицию $y = f(x)$. Уравнение

$$f(x) = x$$

определяет место встречи.

Пример 1. Пусть $a = 0$, $b = 1000$ м, $y = 100 + 0,7x$. Если $x = 0$, то $y = 100$; если $x = 1000$, то $y = 800$ — первый обошел! Уравнение 100+

Рис. 1

6

+0,7x = x дает координату x = 333 1/3 м — здесь первый догонит второго.

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

Однако это «очевидно» нас как математиков неSTRAINВАЕТ; преждечем пойти дальше, мы уточним математическую постановку задачи и доказем существование встречи.

Предположим (как в примере 1), что функция f отображает отрезок [a; b] в себя, т. е. для всех x ∈ [a; b] имеем a ≤ f(x) ≤ b. Тогда всякое решение уравнения f(x) = x называется неподвижной точкой отображения f. (В нашем примере неподвижная точка — это как раз точка встречи.) Когда же она есть?

Теорема. У всякой непрерывной функции f, отображающей отрезок [a; b] в себя, существует неподвижная точка.

В теореме существны как непрерывность функции f, так и то, что речь идет об отрезке.

Упражнение 1. Укажите пример разрывной функции f, отображающей [a; b] в себя, без неподвижной точки.

Упражнение 2. Укажите примеры непрерывных функций, отображающих в себя, без неподвижных точки: а) объединение двух отрезков [a; b] ∪ [c; d]; б) * интегвал ]a; b[.

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

$$\varphi(x) = f(x) - x.$$

Ясно, что c ∈ [a; b] будет неподвижной точкой для f тогда и только тогда, когда c — корень уравнения $\varphi(x) = f(x) - x = 0$. Поэтому мы будем искать корень этого уравнения. Заметим, что из условия a ≤ x ≤ b, a ≤ f(x) ≤ b сразу следует $\varphi(a) ≥ 0$ и $\varphi(b) ≤ 0$. Мы будем считать оба неравенства строгими (в противном случае задача решения). Разделим теперь отрезок [a; b] на 10 равных частей и раскраим в красный цвет все отрезки, для которых значение

$$\cos x^3 - x = 0?$$

Функция cos x³ непрерывна; она отображает отрезок [−π/2, π/2] в себя (далее в отрезок [−1, 1]); значит, по теореме существует решение c ∈ [−π/2, π/2].

7

Заметим, что числа $a_n, \delta_n$ — это приближения к корню, и что делить отрезок можно не на 10, а скажем, на 2 части; такой прием (способ Большано — по имену чешского математика) фактически применяется наряду с другими алгоритмами приближенного решения уравнения.

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

Чашка кофе

А теперь — чашка кофе! Размещая его плаваными круговыми движениями, увидим в центре неподвижную точку. При некоторых движениях картина сложнее, но если рассмотреть положения части в два разных момента времени, можно найти частицу, неподвижную в том смысле, что она оба раза — нё, быть может, не все время! — находится в одном и том же месте. Это оченьно, если приять физическое условие неподвижности части у стенок из-за трения, и не оченьно — но верно! — и без такого условия, лишь бы имела место непрерывность соответствующего отображения (то есть «близкие» частицы не расходились бы слишком далеко).

Чтобы «математизировать» рассмотренную ситуацию, нам будут нужны некоторые определения.

Пусть $M$ — множество точек (например, часть прямой, плоскости или пространства); $f$ — отображение множества $M$ в себя: оно каждой точке $x \in M$ ставит в соответствии ее образ $y = f(x) \in M$. Такое отображение называется непрерывным, если для любой точки $x_0 \in M$ и любого $E > 0$ существует такое $\delta > 0$, что для всех точек $x \in M$, удаленных от $x_0$ на расстояние, меньше $\delta$, расстояние между их образами $f(x_0)$ и $f(x)$ оказывается меньше $\varepsilon$.

Для случая, когда $M$ лежит на числовой прямой, расстояния между точками равно $|x_0 - x|$, между их образами — $|f(x_0) - f(x)|$, так что наше определение в существии совпадает с определением непрерывной функции («Алгебра и начала анализа 9», п. 38).

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

Как и раньше, мы назовем точку $x \in M$ неподвижной точкой отображения $f$ множество $M$ в себя, если $f(x) = x$.

Когда у отображения $f$ обязательно есть неподвижная точка? Ответ на этот вопрос дает

Teорема Брауэра
о неподвижной точке

Эта знаменита теорема строго доказана не так уж давно — в 1911 году*). Вместе с многочисленными обобщениями она играет видающего роль в ряде областей современной математики. Теоремы о неподвижных точках важны и в теории, и для приложений: их применяют и для расчета крыльев самолетов, и для анализа оптимальных стратегий и состояний равновесия в играх, и в математике-экономических моделях.

Teорема Брауэра. У всякою непрерывного отображения $f$ круга $M$ (вместе с его границей) в себя существует непрерывная точка.

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

*) Л. Э. Я. Брауэр — голландский математик; до него теорему применял латышский математик П. Боль, и ее называют еще теоремой Боля — Брауэра.

8

Рис. 4.

Однако она справедлива не для всякого $M$:

Упражнение 3. Указите пример ограниченного множества $M$ на плоскости и его непрерывного отображения в себя без неподвижной точки.

Упражнение 4*. Построите непрерывное отображение круга без границы в себя, не имеющее неподвижной точки.

Упражнение 5. Построите разрывное отображение круга (с границей $M$ в себя без неподвижной точки.

Мы не будем доказывать теорему Браузера в наиболее общей ситуации, а рассмотрим случай, когда $M$ — равносторонний треугольник. Для доказательства нам нужно потребовать цветные карандаши, но теперь уже три: красный, синний и зеленьй. (В пространстве потребовалось бы четыре!) Они будут нужны для доказательства одного вспомогательного утверждения, известного под названием

Лемма Шперера

На рисунке 4 показана «сеть» для лова точек в правильном треугольнике $ABC$ со стороны $a$. Узлы отмечены кругжами, из каждой узла исходит 3 линии (ребра), соединяя его с соседними узлами. Ячейки сети — правильные шестиугольники со стороны $b$. Стороны треугольника разделены на $n$ равных частей, точки деления — центры граничных ячеек. $nb\sqrt{3} = a$ и $(n+1)(n+2)/2$ — общее число ячеек.

Каждая внутренняя вершина принадлежит тем, а граничная — двумя ячеекам.

Пометим теперь числом 1 все ячеек, кроме последней одной стороны, числом 2 — ячеек второй, числом 3 — ячеек третьей (рис. 4). Оставшиеся (внутренние) ячеки помещим числам 1, 2, 3 совершенно произвольно. Раскрасием ячеки типа 1, 2 и 3 в зеленьй, синий и красный цвет соответственно. Назовем вершину полной, если она содержится в ячейках всех трех цветов.

Лемма. Существует полная вершина*).

Доказательство. Строим шаг за шагом ломанную, составляя ее из ребер «типа 1—2», примыкающих к ячейкам с числам 1 и 2. Начнем с края, где по условию есть лишь одно такое «двухцветное» ребро $p_0p_1$, и за конечное число шагов приходим к полной вершине: если ребро типа 1—2 $p_{k-1}p_k$, $k=1, 2, \dots$, привело нас к неполной вершине $p_k$, то найдется еще одно ребро типа 1—2, исходящие из узла $p_k$ (рис. 5), оно дает вершину $p_{k+1} \neq p_k$. Этот путь, очевидно, не возвращается ни на край, ни к проиденным вершинам (почему?). Так как множество вершин конечно, то ломаная обязаательно закончится в полной вершине.

Лебедь, рак да шука

Доказем теперь теорему Браузера для случая, когда $M$ — правильный

*) Эта лемма лишь частичный случай знаментий леммы, принадлежащей немецком математику Шпереру.

Рис. 5.

9

треугольник $ABC$ (рис. 4). Пометим точку $A$ числом 1, $B$ — числом 2, $C$ — 3 и запишем эти числа в соответствующих трех ячейках. Далее, в ячейках с центрами на стороне $AB$ пишем 1, на $BC$ — 2; на $CA$ — 3. Каждый внутренней точке $x$ ставим в соответствие метку — одно из чисел 1, 2, 3 — по следующему правилу: число 1, если расстояние от точки $x$ до стороны $AB$ не больше, чем расстояние от точки $y=f(x)$ до $AB$ (точка $x$ не «снижается» при отображении $f$); если этого нет, то число 2, когда точка $x$ не приближается к $BC$ (расстояние от $x$ до $BC$ не больше расстояния от $y$ до $BC$); в остальных случаях берем 3 — при этом точка $x$ удаляется от стороны $CA$ (см. на рисунке 4 области для $\vec{x}y$, которые отвечают метки 1, 2, 3). Запишем в каждую внутреннюю точку метку ее центра. По лемме Шпернана найдем полную вершину $x_0$ и вспомним значения басно Крылова:

…Лебедь рвется в облака,
Рак пятится назад,
а циука тянет в воду —
Да только воз и ныне там!
Мы как раз ищем неподвижную точку: подобие этого воз из басни составляют ячейки с чисlami 1, 2, 3, связанные с полной вершиной $x_0$. (Эта вершина «почти неподвижна» — при достаточно малом $b$ она мало приближается к $AB$, к $BC$ и к $CA$, т. е. мало двигается.)

Возьем теперь последовательность чисел $b_1, b_2, ..., b_k$, …, стремяшихся к нулю, и для каждой $k$ найдем свою полную вершину $x_k$. Получим последовательность точек

$$x_1, x_2, ..., x_k, ...$$

Первый случай. Если эта последовательность сходится*) к точке $\bar{x} = \lim_{k \to \infty} x_k$, то $\bar{x}$ — неподвижная точка данного отображения. (Ее неподвижность следует из того, что $\bar{x}$ не приближается ни к одной из трех сторон треугольника.)

Упражнение 6. Докажите неподвижность точки $\bar{x}$.

Второй случай. Если последовательность $x_1, x_2, ..., x_k$, … не сходится, то можно подобрать последовательность номеров $n_1 < n_2 < ... < n_k < ...$ так, чтобы последовательность точек

$$x_{n_1}, x_{n_2}, ..., x_{n_k}, ...$$

сходилась к некоторой точке $\bar{x}' = \lim_{k \to \infty} x_{n_k}$.

Упражнение 7. Докажите существование такой последовательности номеров $n_1, n_2, ..., n_k, ...$ и неподвижность точки $\bar{x}'$.

Развитие метода неподвижных точек

Теорема Браузера, которое мы доказали для отрезка и для треугольника, обобщается не только на трехмерное пространство (как было указано выше), но и на «пространство любого числа измерений». Более того, пользователь математик Ю. Шаудер обобщил ее на случай «бесконечномерных» пространств. Дальнейшее развитие этого направление получило в работе академика А. Н. Тихонова. Полский математик С. Банах доказал важную теорему о скатии пространств, обогатившую метод неподвижных точек. В последнее время построения, подобные рисунку 4, применяются для счета на ЭВМ приближении к неподвижным точкам и для решения многохлizких задач.

Упражнения

8. Применяя теорему Браузера (для отрезка) показать, что следующее уравнение имеет решение: а) $x - \cos x = 0$; б) $\cos (\sin x) - x = 0$.

9. Отображение $f:(x, y) \rightarrow (x', y')$, где $x' = x^2 + 1, 5xy, y' = 0, 5xy + y^2$, на отрезке $S = \{(x, y) | x \geq 0, y \geq 0, x + y = 1\}$ имеет неподвижную точку. Докажать это по теореме Браузера, а также решая систему $x = x^2 + 1, 5xy; y = 0, 5xy + y^2$.

10. Показать, что система

$$\begin{cases} x = \sin(x + y), \\ y = 0, 5(x^2 + xy^3) \end{cases}$$

иметет решение.

11. Исследовать систему

$$\begin{cases} x_1 = x_2^2 + 2x_2x_3 + x_1x_2, \\ x_2 = x_3^2 + x_3x_1, \\ x_3 = x_1^2 + x_1(x_2 + x_3) \end{cases}$$

на существование ненулевого решения (по теореме Браузера). Решить ее элементарными средствами.