Метод неподвижной точки — один из основных инструментов для доказательства существования решения разных уравнений. Уравнение представляется в виде F(x)=x и ищется неподвижная точка преобразования F, то есть точка, которая под действием преобразования не меняется. Это своего рода симметрия, а симметрия лежит в основе буквально всего.
Вопрос только в том, почему искать неподвижную точку какой-нибудь функции G(x) проще, чем решать уравнение G(x)-x=0?
Дело в теоремах о неподвижных точках, которых есть несколько и которые гарантируют существование таковой или даже существование и единственность.
Сначала пара примеров. Если мы возьмем кольцо между двумя окружностями и повернем его на 90 градусов, то неподвижных точек не будет. С другой стороны, если мы возьмем банку муки и хорошенько (или не хорошенько, неважно!) перемешаем муку, хотя бы одна крупинка вернется на свое место: это теорема Брауэра, о которой в другой раз. Если же мука уплотнилась, так что расстояния между крупинками уменьшились, то ровно одна крупинка осталась на месте.
Есть очень сильная теорема, гарантирующая существование единственной неподвижной точки у преобразования: если оно сжимает.
Сжатие — это такое свойство: расстояние между образами точек должно быть меньше, чем между самими точками. Формально так:
Число 0<L<1 одно для всех x и y.
Расстояние не обязано быть обычным евклидовым расстоянием. Это произвольная функция, именуемая метрикой, от которой нужно всего три свойства:
- расстояние между различными точками всегда положительно, а между совпадающими равно нулю;
- расстояние от x до y равно расстоянию от y до x;
- в объезд длиннее: сумма расстояний от x до y и от y до z не может быть меньше, чем от x до z.
Последнее называется неравенством треугольника.
Не всегда, кстати, эти свойства имеют место. Так, метрика в теории относительности псевдориманова, и там могут быть различные точки с нулевым расстоянием. Рейс самолета "туда" обычно стоит дороже или дешевле, чем рейс обратно. Ну и были случаи, когда рейс Санкт-Петербург-Нью-Йорк с пересадкой в Москве стоил дешевле, чем Москва-Нью-Йорк тем же бортом.
Метрика, заданная на множестве, превращает его в метрическое пространство и позволяет определять расстояния, шары, сходимость.
Последовательность элементов сходится, если расстояние между элементами и пределом можно сделать сколь угодно малым, выбрав достаточно большие номера элементов. То есть, вся последовательность начиная с какого-то номера находится в сколь угодно малой окрестности предела.
Может быть так, что расстояния между элементами последовательности становятся все меньше, но предела нет. Например, если задать обычное расстояние на рациональных числах. Последовательность сложных процентов все меньше меняется, но ни к какому рациональному пределу не приближается.
Пространство называется полным, если у любой такой последовательности (их называют фундаментальными) предел есть. Пространство всегда можно пополнить, добавив пределы фундаментальных последовательностей.
Итак. Пусть отображение F(x) сжимает в метрике полного пространства. Тогда оно имеет ровно одну неподвижную точку.
То есть если вы встряхнули банку муки так, что частицы стали ближе друг к другу (уплотнились), то ровно одна частица осталась на месте. Это странно же, правда?
Доказательство очень просто. Берем любую точку и следим за тем, куда она переходит. Либо это и есть неподвижная точка, угадали, либо получим последовательность, у которой расстояние между элементом и следующим за ним становится все меньше. Из-за полноты она имеет предел, который и есть неподвижная точка, так как он обязан остаться на месте (иначе нарушится сжатие). Единственность получается еще проще: если неподвижных точек две, то они переходят в себя же, но расстояние между образами должно уменьшиться.
Теперь о пользе фантазии. Часто бывает так, что естественное понятие расстояния не годится: интересующая вас функция не сжимает. Но если вам удастся придумать метрику, в которой сжатие есть, то есть и неподвижная точка. Всё.
Вот два примера. Первый: теорема Пикара о существовании и единственности локального решения задачи Коши для обыкновенного дифференциального уравнения. Уравнение y'=f(x,y), где y=y(x). Задача Коши — это уравнение с начальным условием вроде y(0)=1. Есть решение у такой задачи? Единственное ли? В другой раз обсудим подробнее, а пока заметим два момента:
1. Уравнение можно переписать в интегральной форме,
Если функция удовлетворяет одному, она удовлетворяет и другому. И задача сводится к поиску неподвижной точки преобразования, которое задано правой частью.
2. Если f имеет ограниченную производную по второму аргументу, то |f(t,x)-f(t,y)| ≤ M|x-y|, где M — максимум производной. В этом случае преобразование является сжатием, если отрезок по оси х не слишком большой.
Теорема доказана: решение существует и единственно, но может быть локальным: в окрестности начальной точки. Требуемое свойство функции f (наличие ограниченной производной) может быть ослаблено. Но примеры неединственного решения имеются, так что единственность "небесплатна".
Второй пример. Пусть у матрицы А все собственные числа по модулю меньше единицы. Тогда можно найти такую норму, в которой отображение Ах сжимает. Но тогда у него есть единственная неподвижная точка. Однако одну точку мы знаем, это х=0. Значит, других нет.
Результат можно усилить. Если отображение слабо сжимает, то есть расстояние между точками после преобразования меньше (просто меньше, без константы L), чем между исходными точками, то на компактном множестве оно имеет единственную неподвижную точку. На компактном множестве нельзя просто быть меньше на сколь угодно малую величину — обязательно будет "зазор".
Еще есть такой полезный результат: если отображения А и В коммутируют и у одного из них есть единственная неподвижная точка, то и другое обладает неподвижной точкой (не обязательно единственной), причем той же самой, что у В. То есть коммутирующие операторы очень тесно связаны, у них общие неподвижные точки. Это вам не числа, которые всегда коммутируют))
В самом деле, коммутация — это ABx=BAx для любого х. Пусть у B есть единственная неподвижная точка b: Bb=b. Но тогда BAb=ABb=Ab, то есть у B нашлась вторая неподвижная точка: Ab. Из-за единственности имеем Ab=b.
Коммутирующие отображения редки, это верно, но степени отображения (АА, ААА и т.п.) точно коммутируют, так что если какая-нибудь степень сжимает, то у самого преобразования есть неподвижная точка. Причем единственная, потому что неподвижная точка отображения есть неподвижная и для любой его степени.