Непрекъснати оператори

  • Казваме, че операторът $$\Gamma$$ е непрекъснат, ако за всяка монотонно растяща редица $$f_0\subseteq f_1 \subseteq\ldots\subseteq f_n\subseteq\ldots$$ имаме, че $$\Gamma(\bigcup f_n) = \bigcup (\Gamma(f_n))$$. Интуиция - както в анализа.
  • Стр. 175 / Зад. 13 - всеки компактен оператор е непрекъснат
  • Стр. 175 / Зад. 14 - всеки непрекъснат оператор е компактен

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

  • Казваме, че функцията f е неподвижна точка на оператора $$\Gamma$$ от тип (n,n), ако $$\Gamma(f) = f$$. Интуиция - рекурсивно дефинирана функция, операторът е тялото на функцията.
  • Теорема на Кнастер-Тарски - всеки непрекъснат (компактен) оператор има най-малка неподвижна точка. Интуиция - най-малката неподвижна точка на оператора е точно функцията, която се пресмята от компютъра при задаване на рекурсивната дефиниция на някой език на програмиране.
  • Конструкция на Кнастер-Тарски за намиране на най-малка неподвижна точка
    1. f0 = $$\emptyset$$, fn+1 = $$\Gamma$$(fn). Разписваме си първите 3-4 функции в редицата.
    2. Правим индукционно предположение за общия вид на fn, което се удовлетворява от първите функции, които сме разписали. Показваме, че fn+1 има същия вид.
    3. Най-малката неподвижна точка на $$\Gamma$$ е функцията f = $$\bigcup$$fn. Интуиция - получава се от общия вид на fn при $$n\rightarrow\infty$$.

Задачи

  • Стр. 175 / зад. 15 - Намерете всички неподвижни точки на операторите. С помощта на конструкцията на Кнастер-Тарски намерете най-малката неподвижна точка.
  • Стр. 177 / Зад. 17 - Намерете най-малката неподвижна точка на оператора. Докажете, че тя е единствена. Пример за най-малка неподвижна точка, която не е нито празната, нито тотална функция.
  • Стр. 179 / Зад. 20 - Намерете най-малката неподвижна точка на оператора.
Последно модифициране: събота, 12 ноември 2011, 17:38