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

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

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

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

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

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

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

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

Докажем, что последовательность (1.7) неубывающая. Используем метод математической индукции. Для элемента \mathbb{O}, как наименьшего элемента множества M, имеем \mathbb{O}-f^0(\mathbb{O}) \leqslant f(\mathbb{O}). Пусть для некоторого натурального n верно соотношение f^{n-1}(\mathbb{O})\leqslant f^n(\mathbb{O}). Согласно теореме 1.6, отображение f монотонно, и поэтому т.е. соотношение верно и для номера n+1. Согласно методу математической индукции, 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. В частности, фиксируя произвольно k>0, для любого n\geqslant k имеем a\geqslant x_n, т.е. а будет верхней гранью подпоследовательности \{x_n\}_{n\geqslant k>0}.

Докажем, что а является точной верхней гранью этой подпоследовательности. Пусть b — какая-то ее верхняя грань, т.е. 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, т.е. b есть верхняя грань всей последовательности \{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}^{.}}. Следовательно, a — точная верхняя грань последовательности \{x_n\}_{n\geqslant k}.

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

 Но

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

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

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, т.е. элемент y есть верхняя грань последовательности \{f^n(\mathbb{O})\}_{n\geqslant0}. Поскольку элемент a(как точная верхняя грань) есть наименьший элемент на множестве всех верхних граней этой последовательности, то y\geqslant a. Таким образом, мы доказали, что произвольная неподвижная точка отображения f не меньше элемента a, то есть a — наименьшая неподвижная точка отображения f.


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

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

x=f(x)

(1.9)

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

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

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

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

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

Так как функция f монотонна, то \{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).

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

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

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

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

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

Предел этой последовательности равен 1/2. Таким образом, наименьшая неподвижная точка отображения f, определяемого

Похожие материалы

Информация о работе

Предмет:
Эконометрика
Тип:
Ответы на экзаменационные билеты
Размер файла:
184 Kb
Скачали:
0