Принцип сжатых отображений: как Банах гарантирует неподвижную точку

Уравнение $x=\cos x$ не решается ни алгеброй, ни тригонометрией: корень существует, а формулы для него нет. Перепишем уравнение в виде $x=g(x)$ и будем просто подставлять: любое число подействуем $g$, потом ещё раз, ещё — и посмотрим, куда сойдётся цепочка. Принцип сжимающих отображений Банаха заранее отвечает на оба вопроса: сойдётся ли эта цепочка и как далеко мы сейчас от истинного корня. Это один из самых полезных мостов между функциональным анализом и вычислениями: тем же механизмом доказываются существование и единственность решения задачи Коши для ОДУ и теорема об обратной функции.

Сжимающее отображение: определение#

Работаем в метрическом пространстве $(X,d)$ с расстоянием $d$. Отображение $T:X\to X$ называется сжимающим, если оно сближает любые две точки не меньше чем в $q$ раз, где $q$ — константа строго меньше единицы:

Из определения сразу следует непрерывность: если $x_n\to x$, то $d(T{x}_n,Tx)\le qd(x_n,x)\to 0$. Неподвижная точка — точка, которую отображение не двигает: $T(x^{\ast })=x^{\ast }$. Для уравнения $x=g(x)$ это ровно корень уравнения, так что поиск неподвижной точки — общий язык для всех задач вида «что-то равно самому себе». Слово «сжатие» здесь буквальное: шар радиуса $r$ отображается внутрь шара радиуса $qr$ — карта вмещает собственную территорию, и повторные применения гасят любое начальное расхождение. На прямой константу сжатия находят через производную: по теореме Лагранжа о среднем достаточно оценить производную по всему отрезку:

Теорема Банаха и схема доказательства#

Теорема. Если $X$ — полное метрическое пространство и $T:X\to X$ сжимающее, то у $T$ существует ровно одна неподвижная точка $x^{\ast }$, и последовательность $x_{n+1}=T(x_n)$ сходится к ней из любой стартовой точки $x_0$. Схема доказательства — четыре шага, каждый честный и короткий.

Шаг первый: соседи по цепочке итераций сближаются в геометрической прогрессии. Применяем сжатие $n$ раз подряд:

Шаг второй: цепочка фундаментальна. По неравенству треугольника $d(x_n,x_m)$ оценивается суммой соседних расстояний — а сумма $q^n+q^{n+1}+\dots$ это геометрическая прогрессия с малым знаменателем, она стремится к нулю. Шаг третий: пространство полное, значит у фундаментальной последовательности есть предел $x^{\ast }$. Шаг четвёртый: переход к пределу в $x_{n+1}=T(x_n)$ законен из-за непрерывности $T$, получаем $x^{\ast }=T(x^{\ast })$. Единственность — бесплатно: если бы неподвижных точек было две, то $d(x^{\ast },y^{\ast })=d(T{x}^{\ast },T{y}^{\ast })\le qd(x^{\ast },y^{\ast })$, а при $q<1$ это возможно только при нулевом расстоянии. В функциональных пространствах — интегральные уравнения, уравнения в частных производных — та же схема опирается на полноту и даёт сходимость последовательных приближений, часто усиливаемую до равномерной сходимости.

Есть и апостериорная версия — по фактически наблюдаемому последнему шагу: $d(x_n,x^{\ast })\le \frac{q}{1-q}d(x_n,x_{n-1})$. Она обычно в разы точнее, потому что учитывает реальное поведение цепочки, а не худший старт.

Числовой опыт: x = (cos x + 1)/2#

Берём $g(x)=(\cos x+1)/2$ на отрезке $[0;1]$. Производная $g^{\prime }(x)=-\sin (x)/2$ по модулю не превосходит $\sin (1)/2\approx 0,42$, так что сжатие есть: возьмём с запасом $q=0,5$. Отрезок отображается в себя: $g(0)=1$, $g(1)\approx 0,77$ — все значения в $[0,5;1]$. Стартуем от $x_0=0$, предел $x^{\ast }\approx 0,83543$.

Обратная задача решается той же оценкой: чтобы гарантировать точность $\epsilon$, нужно $n\ge \frac{\ln (d(x_1,x_0)/(\epsilon (1-q)))}{\ln (1/q)}$ шагов. При $q=0,5$ каждый дополнительный знак точности стоит ровно один шаг; при $q=0,9$ — уже около 22 шагов на знак. Отсюда практическое правило: прежде чем итерировать, добейтесь маленького $q$ — иногда достаточно чуть иначе переписать уравнение.

Расстановка уравнения — половина успеха. Для $x^3-x-1=0$ форма $x=x^3-1$ даёт $|g^{\prime }(x)|=3x^2\approx 5,3$ у корня $x^{\ast }\approx 1,32$ — итерации разлетаются. Форма $x=\sqrt[3]{x+1}$ даёт $|g^{\prime }|=1/\left(3\sqrt[3]{(x+1{)}^2}\right)\approx 0,19$ у того же корня — сходимость за пять-шесть шагов: $1,26;1,31;1,32;\dots$ Уравнение одно, а судьба итераций противоположная: прежде чем считать, ищите запись с маленьким $q$.

Где метод живёт и где ломается#

Требование полноты тоже не украшение, а несущая стена: в неполном пространстве фундаментальная цепочка может не иметь предела внутри него, и весь вывод рушится. Второе условие, о котором забывают, — отображение должно переводить пространство (или выбранный замкнутый шар) в себя: иначе сжатие локально есть, а цепочка уезжает за границу области. Оценкой пользуются и в обратную сторону: посчитав несколько шагов и измерив $d(x_n,x_{n-1})$, легко предсказать, сколько шагов осталось до заданной точности — прогрессия геометрическая, скорость известна.

• Проверять сжатие только в стартовой точке: константа q нужна на всём отрезке, куда попадают итерации.
• Забывать вложенность T([a, b]) ⊂ [a, b]: без неё итерации уходят с отрезка, даже если локально q < 1.
• Путать оценки: q/(1−q)·d(x_n, x_{n−1}) — апостериорная (после шага), q^n/(1−q)·d(x_1, x_0) — априорная (до старта).
• Считать, что при q ≥ 1 итерации обязаны расходиться: теорема молчит, а не запрещает — конкретная задача может сходиться.
• Применять принцип в неполном пространстве: последовательность 1; 1,4; 1,41; … фундаментальна, но её предела в ℚ нет.
• Итерировать дольше нужного: как только апостериорная оценка гарантирует требуемую точность, счёт можно останавливать.

Итог: сжатие плюс полнота равняются существованию, единственности и готовой оценке ошибки — редкий случай, когда теория дарит вычислителю всё сразу. Наш числовой опыт с $x=(\cos x+1)/2$ показал все слои: честная проверка $q$, восемь итераций, фактический множитель $0,37$ против гарантированных $0,5$ и расхождение между обещанными 15 шагами и реальными 9. Метод простых итераций — базовый инструмент из арсенала решения нелинейных уравнений; дальше по курсу функционального анализа этот же принцип вернётся в доказательствах существования — от интегральных уравнений до дифференциальных.