Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Теорема о неподвижной точке

Теорема о неподвижной точке


Определение 1.7. Элемент [math]a[/math] множества [math]A[/math] называют неподвижной точкой отображения [math]f\colon A\to A[/math], если [math]f(a)=a[/math].


Элемент [math]a[/math] упорядоченного множества [math]M[/math] называют наименьшей неподвижной точкой отображения [math]f\colon M\to M[/math], если он является наименьшим элементом множества всех неподвижных точек отображения [math]M[/math].


Теорема 1.7 (теорема о неподвижной точке). Любое непрерывное отображение [math]f[/math] индуктивного упорядоченного множества [math](M,\leqslant)[/math] в себя имеет наименьшую неподвижную точку.


Обозначим через [math]\mathbb{O}[/math] наименьший элемент множества [math]M[/math]. Полагаем [math]f^{0}(x)=x[/math] и [math]f^n(x)=f(f^{n-1}(x))[/math] для любого [math]n>0[/math], т.е. [math]f^n(x)[/math] означает результат n-кратного применения [math]f[/math] к [math]x[/math]. Рассмотрим последовательность элементов [math]M[/math]


[math]\bigl\{f^n(\mathbb{O})\bigr\}_{n\geqslant0}= \bigl\{\mathbb{O}, f(\mathbb{O}), \ldots, f^n(\mathbb{O}),\ldots\bigr\}.[/math]
(1.7)

Докажем, что последовательность (1.7) неубывающая. Используем метод математической индукции. Для элемента [math]\mathbb{O}[/math], как наименьшего элемента множества [math]M[/math], имеем [math]\mathbb{O}-f^0(\mathbb{O}) \leqslant f(\mathbb{O})[/math]. Пусть для некоторого натурального [math]n[/math] верно соотношение [math]f^{n-1}(\mathbb{O})\leqslant f^n(\mathbb{O})[/math]. Согласно теореме 1.6, отображение [math]f[/math] монотонно, и поэтому


[math]f^n(\mathbb{O})= f(f^{n-1}(\mathbb{O})) \leqslant f(f^n(\mathbb{O}))= f^{n+1}(\mathbb{O}),[/math]

т.е. соотношение верно и для номера [math]n+1[/math]. Согласно методу математической индукции, [math]f^n(\mathbb{O})\leqslant f^{n+1}(\mathbb{O})[/math] для любого [math]n\in \mathbb{N}_0[/math], т.е. последовательность (1.7) неубывающая. Следовательно, по определению индуктивного упорядоченного множества, она имеет точную верхнюю грань. Обозначим ее через [math]a:[/math]


[math]a=\sup_{n\geqslant 0}f^n(\mathbb{O}).[/math]
(1.8)

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


Действительно, если а есть точная верхняя грань неубывающей последовательности [math]\{x_n\}_{n\geqslant0}[/math], то [math]a\geqslant x_n[/math] для всякого [math]n\geqslant 0[/math]. В частности, фиксируя произвольно [math]k>0[/math], для любого [math]n\geqslant k[/math] имеем [math]a\geqslant x_n[/math], т.е. а будет верхней гранью подпоследовательности [math]\{x_n\}_{n\geqslant k>0}[/math].


Докажем, что а является точной верхней гранью этой подпоследовательности. Пусть [math]b[/math] — какая-то ее верхняя грань, т.е. [math]b\geqslant x_n[/math] для любого [math]n\geqslant k[/math]. Так как последовательность [math]\{x_n\}_{n\geqslant0}[/math] неубывающая, то [math]x_p\leqslant x_k[/math] для каждого [math]p=\overline{0,k-1}[/math]. Поскольку [math]x_k\leqslant b[/math], то в силу транзитивности отношения порядка [math]x_p\leqslant b[/math] и тем самым [math]b\geqslant x_n[/math] для любого [math]n\geqslant 0[/math], т.е. [math]b[/math] есть верхняя грань всей последовательности [math]\{x_n\}_{n\geqslant0}[/math]. Поскольку [math]a=\mathop{\sup_{n\geqslant0}x_n}\limits^{\phantom{A}^{.}}[/math], то [math]a\leqslant b[/math] и [math]a=\mathop{\sup_{n\geqslant k>0}x_n}\limits^{\phantom{A}^{.}}[/math]. Следовательно, [math]a[/math] — точная верхняя грань последовательности [math]\{x_n\}_{n\geqslant k}[/math].


В силу непрерывности [math]f[/math] получаем


[math]f(a)=f\!\left(\sup_{n\geqslant0}f^n(\mathbb{O})\right)= \sup_{n\geqslant0} f(f^n(\mathbb{O}))= \sup_{n\geqslant0}f^{n+1}(\mathbb{O}).[/math] Но

[math]\sup_{n\geqslant0}f^{n+1}(\mathbb{O})= \sup\bigl\{f^1(\mathbb{O}), f^2(\mathbb{O}), \ldots\bigr\}= \sup_{n\geqslant1}f^n(\mathbb{O})=a.[/math]

Таким образом, доказано, что [math]a[/math] является неподвижной точкой отображения [math]f[/math].


Покажем теперь, что найденная неподвижная точка является наименьшей. Пусть для некоторого [math]y\in M[/math] имеем [math]f(y)=y[/math]. Так как [math]\mathbb{O}\leqslant y[/math], а отображение [math]f[/math], будучи непрерывным, монотонно, то


[math]f(\mathbb{O})\leqslant f(y)=y,\quad f(f(\mathbb{O}))\leqslant f(f(y))=y[/math] и т.д.

Следовательно, для любого [math]n\geqslant 0[/math] имеем [math]f^n(\mathbb{O})\leqslant y[/math], т.е. элемент [math]y[/math] есть верхняя грань последовательности [math]\{f^n(\mathbb{O})\}_{n\geqslant0}[/math]. Поскольку элемент [math]a[/math] (как точная верхняя грань) есть наименьший элемент на множестве всех верхних граней этой последовательности, то [math]y\geqslant a[/math]. Таким образом, мы доказали, что произвольная неподвижная точка отображения [math]f[/math] не меньше элемента [math]a[/math], то есть [math]a[/math] — наименьшая неподвижная точка отображения [math]f[/math].




Нахождение неподвижной точки


Поиск неподвижной точки отображения [math]f\colon M\to M[/math] можно рассматривать как задачу решения уравнения


[math]x=f(x)[/math]
(1.9)

Теорему о неподвижной точке можно трактовать таким образом: для непрерывного отображения [math]f[/math] индуктивного упорядоченного множества в себя уравнение [math]x=f(x)[/math] имеет решение, т.е. существует такой [math]x_0\in M[/math], что выполняется равенство [math]x_0=f(x_0)[/math] причем множество всех решений этого уравнения имеет наименьший элемент. Этот элемент и будет наименьшей неподвижной точкой отображения [math]f[/math].


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


Пример 1.20. Приведем простой пример вычисления наименьшей неподвижной точки. В качестве индуктивного упорядоченного множества [math]M[/math] возьмем отрезок [math][0;1][/math] с естественным числовым порядком [math]\leqslant[/math]. Согласно примеру 1.19, это индуктивное упорядоченное множество.


Рассмотрим на этом множестве уравнение [math]x=\frac{x}{2}+\frac{1}{4}[/math]. Можно показать, что для индуктивного упорядоченного множества [math]M[/math] любая монотонная функция [math]f\colon[0;1]\to[0;1][/math], непрерывная в смысле определения из курса математического анализа, непрерывна и в смысле данного выше определения. Действительно, для любой неубывающей последовательности [math]\{x_n\}[/math] на множестве [math][0;1][/math] справедливо равенство [math]\sup\{x_n\}=\lim_{n\to+\infty}x_n[/math]. В силу непрерывности функции [math]f[/math] в смысле определения из курса математического анализа имеем


[math]f\Bigl(\lim_{n\to+\infty}x_n\Bigr)= \lim_{n\to+\infty}f(x_n).[/math]

Так как функция [math]f[/math] монотонна, то [math]\{f(x_n)\}_{n\geqslant0}[/math] — неубывающая последовательность и


[math]\lim_{n\to+\infty}f(x_n)= \sup f(x_n).[/math]
В итоге получаем
[math]f(\sup x_n)= f\Bigl(\lim_{n\to+\infty}x_n\Bigr)= \lim_{n\to+\infty}f(x_n)= \sup f(x_n).[/math]

Следовательно, правая часть данного уравнения непрерывна.


Заметим, что если бы в правой части стояла линейная функция с отрицательным коэффициентом при [math]x[/math], то условие непрерывности функции в смысле приведенного выше определения было бы уже нарушено, поскольку такая функция не является монотонной в смысле определения 1.6.


Наименьшим элементом рассматриваемого множества является число 0. Вычисляем:


[math]\begin{aligned}& f^0(0)= 0\,,\\ & f^1(0)= 1/4\,,\\ & f^2(0)= (1/2)\cdot (1/4)+1/4=3/8\,,\\ & f^3(0)= (1/2)\cdot (3/8)+1/4=7/16\,,\\ &\cdots \cdots \cdots \cdots \cdots \end{aligned}[/math]

получая последовательность приближений к наименьшей неподвижной точке.

Можно проверить (например, с помощью метода математической индукции), что


[math]f^n(0)=\frac{2^n-1}{2^{n+1}}\,,\quad n\in \mathbb{N}\,.[/math]

Предел этой последовательности равен [math]1/2[/math]. Таким образом, наименьшая неподвижная точка отображения [math]f[/math], определяемого правой частью уравнения, равна [math]1/2[/math]. Это единственная в данном случае неподвижная точка отображения [math]f[/math], что, конечно, очевидно и без теоремы 1.7 о неподвижной точке. Но здесь мы нарочно рассмотрели простой пример, показав, как можно решать подобные уравнения, основываясь на доказательстве теоремы. Мы не будем пока приводить более сложные примеры, так как интересные приложения теоремы о неподвижной точке имеются в теории графов и теории автоматов, и вернемся к этой теореме при решении задачи о путях в ориентированных графах.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved