Метод неподвижной точки (Fixed point method). Сравнение свойств оценок, полученных различными методами, используя метод Монте-Карло

Страницы работы

Фрагмент текста работы

18. Метод неподвижной точки (Fixed point method). Сравнение свойств оценок, полученных различными методами, используя метод Монте-Карло.

Определение 1.7. Элемент множества называют неподвижной точкой отображения $f\colon A\to A$ , если .

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

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

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

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

$a=\sup_{n\geqslant 0}f^n(\mathbb{O}).$

(1.8)

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

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

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

В силу непрерывности получаем

Но

Таким образом, доказано, что является неподвижной точкой отображения .

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

$f(\mathbb{O})\leqslant f(y)=y,\quad f(f(\mathbb{O}))\leqslant f(f(y))=y$ и т.д.

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

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

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

(1.9)

Теорему о неподвижной точке можно трактовать таким образом: для непрерывного отображения индуктивного упорядоченного множества в себя уравнение имеет решение, т.е. существует такой $x_0\in M$ , что выполняется равенство причем множество всех решений этого уравнения имеет наименьший элемент. Этот элемент и будет наименьшей неподвижной точкой отображения .

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

Пример 1.20. Приведем простой пример вычисления наименьшей неподвижной точки. В качестве индуктивного упорядоченного множества возьмем отрезок с естественным числовым порядком $\leqslant$ . Согласно примеру 1.19, это индуктивное упорядоченное множество.

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

$f\Bigl(\lim_{n\to+\infty}x_n\Bigr)= \lim_{n\to+\infty}f(x_n).$

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

$\lim_{n\to+\infty}f(x_n)= \sup f(x_n).$

В итоге получаем

$f(\sup x_n)= f\Bigl(\lim_{n\to+\infty}x_n\Bigr)= \lim_{n\to+\infty}f(x_n)= \sup f(x_n).$

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

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

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

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

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