русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Доказательство


Дата добавления: 2015-07-23; просмотров: 1019; Нарушение авторских прав


[1] "xÎX (a x), следовательно, a – нижняя граница X. Пусть b – любая нижняя граница X, тогда b a, так как aÎX. Следовательно, a – наибольшая нижняя граница.

[2] "xÎX (a x), поскольку a – нижняя граница X, и значит это наименьший элемент, поскольку aÎX.

СЛЕДСТВИЕ Пусть М – частично упорядоченное множество, а Х – любое его подмножество. Тогда:

  1. Если существует наибольший элемент a = max X, то a = sup X;
  2. Если существует супремум a = sup X и aÎX, то a = max X.

Говорят, что частично упорядоченное множество линейно полно, если любое его линейно упорядоченное подмножество имеет супремум.

ПримерЕсли множество X конечно, то – линейно полно относительно .

 

1.8.5. Монотонные и непрерывные функции

Примеры

4. Пусть f : M ® M – некоторая функция. Тогда функция перехода к образам (см. 1.6.3.) F : 2M ® 2M является монотонно возрастающей по включению.

ТЕОРЕМА 1 Суперпозиция одинаково монотонных функции монотонна в том же смысле.

ДоказательствоПусть a b и g монотонно возрастает, тогда g(a) g(b). Но f также монотонно возрастает и значит f(g(a)) f(g(b)).

Функция f : M ® M, где M – частично упорядоченное множество, называется непрерывной, если для любой возрастающей последовательности a1 an …, для которой существует супремум, выполнено равенство

f(sup{ai}) = sup{f(ai)}.

 

ЗАМЕЧАНИЕ Учитывая теоремы подраздела 1.8.1 и последнее замечание подраздела 1.8.2, непрерывность можно определить через строго убывающие и имеющие инфимум последовательности.

 

ТЕОРЕМА 2. Непрерывная функция монотонно возрастает.

Доказательство Пусть a b. Тогда sup{a, b} = b. Имеем f(b) = f(sup{a, b}) = sup{f(a), f(b)}. Следовательно, f(a) f(b).

 

ТЕОРЕМА 3 Суперпозиция непрерывных функций непрерывна.



Доказательство Рассмотрим строго монотонно возрастающую последовательность , имеющую супремум .
f(g(a)) = = = .

 

1.8.5’. Наименьшая неподвижная точка

Рассмотрим функцию f : M ® M. Элемент xÎM называется неподвижной точкой функции f, если f(x) = x.

ЗАМЕЧАНИЕ Неподвижная точка функции f – это то же, что и корень уравнения f(x) = x.

Пример Пусть f : X ® X. Рассмотрим функцию перехода к образам F : 2X ® 2X. Тогда множество A = Ç {YÌX | F(YY} (т. е. пересечение всех таких подмножеств Y множества X, образы которых являются подмножествами аргументов) является неподвижной точкой функции F. Покажем, что F(A) Ì A. Действительно,
F(A) = F(Ç {YÌX | F(YY}) Ì Ç F(Y) = A. Отсюда по монотонности F имеем F(F(A)) Ì F(A), то есть F(A) удовлетворяет условию для множеств Y и значит
A Ì F(A). Имеем A = F(A) и значит A – неподвижная точка функции перехода к образам F.

Замечание Если A= Ç {YÌX | F(YY} = Æ, то F(Æ) = Æ и пустое множество является неподвижной точкой функции перехода к образам по определению.

Вообще говоря, функция f : X ® X может не иметь неподвижных точек, иметь одну неподвижную точку или иметь их несколько, может быть даже бесконечно много. Если множество X упорядочено, и функция f : X ® X имеет неподвижные точки, то среди них можно выделить наименьшую неподвижную точку. Однако даже если функция имеет неподвижные точки, среди них может не быть наименьшей, просто потому, что не всякое, даже конечное частично упорядоченное множество имеет наименьший элемент.

Пример Наименьшей неподвижной точкой для функции перехода к образам F : 2X ® 2X является множество A = Ç {YÌX | F(YY}, введенное в предыдущем примере. Действительно, пусть $BÌX(F(B)=B & AËB). Тогда F(BB, и значит, множество B является одним из множеств Y.Получается, что пересечение не является подмножеством одного их пересекаемых множеств – противоречие.

ТЕОРЕМА [о наименьшей неподвижной точке]. Если множество Х частично упорядочено, линейно полно, имеет наименьший элемент 0 = min X, и функция
f : X ® X непрерывна и тотальна
,dom f = X, то a = sup{f n(0) | n³0} является наименьшей неподвижной точкой функции f.

Доказательство Поскольку функция f тотальна, элементы f n(0) определены для любого n³0. Рассмотрим подмножество Y := {f n(0) | n³0}. Имеем: f 0(0)= 0 f 1(0), поскольку 0 – наименьший элемент. Поскольку функция f непрерывна, она и монотонна, а значит f 1(0)= f(f 0(0)) f 2(0) = f(f 1(0)), f 2(0)= f(f 1(0)) f 3(0) = f(f 2(0)) и вообще f n(0) f n+1(0) для любого n³0. Таким образом, подмножество Y линейно упорядочено, а значит элемент a = sup{f n(0) | n³0} определен по условию теоремы.

Покажем теперь, что элемент a действительно является неподвижной точкой функции f, то есть f(a) = a. Имеем:

f(a) = f(sup{f n(0) | n³0}) = sup{f(f n(0)) | n³0} = sup{f n(0) | n³1} = sup{0, a} = a.

Покажем теперь, что a – наименьшая неподвижная точка. Пусть b – любая неподвижная точка. Поскольку f(b)=b, имеем "n³0 (f n(b) =b). Но 0 b и функция f монотонна, следовательно "n³0 (f n(0) b), то есть b – верхняя граница множества {f n(0) | n³0}, а значит a b.

ЗАМЕЧАНИЕ Требование непрерывности в формулировке теоремы нужно только для того, чтобы гарантировать существование супремумов. Вообще говоря, если супремумы заведомо существуют, то от функции требуется только монотонность.

 

ОТСТУПЛЕНИЕ Фактически, приведенная теорема о наименьшей неподвижной точке служит обоснованием одного из случаев, когда для решения уравнения x=f(x) правомерно применять метод итераций: xi+1:=f(xi).

 



<== предыдущая лекция | следующая лекция ==>
Доказательство | Полная решётка


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.193 сек.