Викиконспекты - Вклад участника [ru]

Основы численных методов

2010-06-27T08:16:41Z

Ulyantsev: Новая страница: «Привет. Здесь я постараюсь написать конспект курса по основам численных методов, которые …»

Привет. Здесь я постараюсь написать конспект курса по основам численных методов, которые нам преподавал Александр Соломонович Сегаль.

Делаю я это на добровольной основе и в своем стиле, если вы собираетесь сделать это серьезней, то согласуйте это со мной и флаг вам в руки.

Параллельное программирование

2010-06-26T17:50:17Z

Ulyantsev: /* 15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===2. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===

*[[Глобальные свойства системы]]
*[[Слабый конъюнктивный предикат]]

===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===

Алгоритм Дейксты и Шолтена в английской википедии<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref>.

===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===

*[[Локально стабильный предикат]]
*[[Согласованный интервал]]

===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
Порядок сообщений:
# асинхронный
# FIFO (сообщения доходят получателю в том порядке, в котором они были ему отправлены)
# причинно-следственный (если одно сообщение было отправлено раньше другого, то оно будет доставлено раньше другого (в системе целиком)
# синхронный

===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
*[[Total order]]
*[[Алгоритм Лампорта]]
*[[Алгоритм Скрина]]

===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===

'''Алгоритм Чанди-Робертса''' (Chang and Roberts) выбора лидера <ref>http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm</ref>.

Пусть процессы находятся в кольце.
Посылаем свой номер налево по кольцу.
При получении номера справа посылаем налево максимум из своего номера и полученного справа.
Если полученный справа номер является нашим номером, то заканчиваем работу.

'''Алгоритм Хирчберга-Синклера''' <ref>http://en.wikipedia.org/wiki/HS_algorithm</ref>.

===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

*Каждый узел посылает каждому свое число;
*Процессы запоминают пришедшие числа;
*Новые для себя числа процессы рассылают дальше;
*Каждый процесс выбирает минимально известное ему число.

(возможно, стоит дописать)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Данный вопрос достаточно хорошо описан в <ref>http://ru.wikipedia.org/wiki/Задача_византийских_генералов</ref>.

==Ссылки==
<references/>

Параллельное программирование

2010-06-26T17:49:53Z

Ulyantsev: /* 15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===2. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===

*[[Глобальные свойства системы]]
*[[Слабый конъюнктивный предикат]]

===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===

Алгоритм Дейксты и Шолтена в английской википедии<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref>.

===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===

*[[Локально стабильный предикат]]
*[[Согласованный интервал]]

===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
Порядок сообщений:
# асинхронный
# FIFO (сообщения доходят получателю в том порядке, в котором они были ему отправлены)
# причинно-следственный (если одно сообщение было отправлено раньше другого, то оно будет доставлено раньше другого (в системе целиком)
# синхронный

===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
*[[Total order]]
*[[Алгоритм Лампорта]]
*[[Алгоритм Скрина]]

===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===

'''Алгоритм Чанди-Робертса''' (Chang and Roberts) выбора лидера <ref>http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm</ref>.

Пусть процессы находятся в кольце.
Посылаем свой номер налево по кольцу.
При получении номера справа посылаем налево максимум из своего номера и полученного справа.
Если полученный справа номер является нашим номером, то заканчиваем работу.

'''Алгоритм Хирчберга-Синклера''' <ref>http://en.wikipedia.org/wiki/HS_algorithm</ref>.

===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

*Каждый узел посылает каждому свое число;
*Процессы запоминают пришедшие числа;
*Новые для себя числа процессы рассылают дальше;
*Каждый процесс выбирает минимально известное ему число.

(возможно, стоит дописать)

----

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Данный вопрос достаточно хорошо описан в <ref>http://ru.wikipedia.org/wiki/Задача_византийских_генералов</ref>.

==Ссылки==
<references/>

Параллельное программирование

2010-06-26T16:11:31Z

Ulyantsev:

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===2. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===

*[[Глобальные свойства системы]]
*[[Слабый конъюнктивный предикат]]

===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===

Алгоритм Дейксты и Шолтена в английской википедии<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref>.

===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===

*[[Локально стабильный предикат]]
*[[Согласованный интервал]]

===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===

'''Алгоритм Чанди-Робертса''' (Chang and Roberts) выбора лидера <ref>http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm</ref>.

Пусть процессы находятся в кольце.
Посылаем свой номер налево по кольцу.
При получении номера справа посылаем налево максимум из своего номера и полученного справа.
Если полученный справа номер является нашим номером, то заканчиваем работу.

'''Алгоритм Хирчберга-Синклера''' <ref>http://en.wikipedia.org/wiki/HS_algorithm</ref>.

===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Данный вопрос достаточно хорошо описан в <ref>http://ru.wikipedia.org/wiki/Задача_византийских_генералов</ref>.

==Ссылки==
<references/>

Алгоритм Рикарта-Агравалы

2010-06-26T15:58:52Z

Ulyantsev:

[[Категория: Параллельное программирование]]
'''Алгоритм Рикарта-Агравалы''' взаимного исключения:
# Когда процесс <tex>P_i</tex> хочет войти в критический участок, то рассылает всем сообщение "запрос" с текущей временной меткой.
# Когда процесс <tex>P_k</tex> получает от <tex>P_j</tex> запрос войти в критический участок:
#* если он сам не посылал запрос, то посылает отклик;
#* если он послал свой запрос, он сравнивает временные метки этих двух запросов и посылает отклик только если у его собственного запроса метка позже (на самом деле, при равенстве меток, нужно проверять, у кого больше номер, т.е. для отсутствия блокировок нужно ввести приоритет на потоках);
#* в остальных случаях процесс <tex>P_k</tex> задерживает отправку отклика.
# Процесс может войти в критический участок только после получения откликов ото всех других узлов сети.
# После выхода из него он рассылает задержанные отклики на все ожидающие запросы.

Starvation-free. <tex>2 \cdot (N-–1)</tex> messages.

Отказ любого узла приводит к зависанию. Решается проблема введением таймаутов.

Алгоритм Рикарта-Агравалы

2010-06-26T15:56:33Z

Ulyantsev:

[[Категория: Параллельное программирование]]
'''Алгоритм Рикарта-Агравалы''' взаимного исключения:
# Когда процесс <tex>P_i</tex> хочет войти в критический участок, то рассылает всем сообщение "запрос" с текущей временной меткой
# Когда процесс <tex>P_k</tex> получает от <tex>P_j</tex> запрос войти в критический участок:
#* если он сам не посылал запрос, то посылает отклик
#* если он послал свой запрос, он сравнивает временные метки этих двух запросов и посылает отклик только если у его собственного запроса метка позже (на самом деле, при равенстве меток, нужно проверять, у кого больше номер, т.е. для отсутствия блокировок нужно ввести приоритет на потоках)
#* в остальных случаях процесс <tex>P_k</tex> задерживает отправку отклика
# Процесс может войти в критический участок только после получения откликов ото всех других узлов сети
# После выхода из него он рассылает задержанные отклики на все
ожидающие запросы

Starvation-free. <tex>2 \cdot (N-–1)</tex> messages.

Отказ любого узла приводит к зависанию. Решается проблема введением таймаутов.

Централизованный алгоритм взаимного исключения

2010-06-26T15:24:02Z

Ulyantsev:

[[Категория: Параллельное программирование]]
'''Централизованный алгоритм''' взаимного исключения:
# Центральный управляющий узел ведет очередь запросов на вход.
# Процесс, желающий войти в критический участок, посылает ему сообщение "запрос" и ждет, пока не получит сообщение "разрешение" (когда подходит его очередь).
# Когда процесс выходит из критического участка, то посылает управляющему узлу сообщение "освобождение".

Всего нужно послать три сообщения для каждого случая доступа к критическому ресурсу.

Часы с прямой зависимостью

2010-06-26T15:13:45Z

Ulyantsev:

[[Категория: Параллельное программирование]]
'''Логические часы с прямой зависимостью''' ''(direct dependency)'' - функция из множества событий (прием/посылка сообщений) в вектор из целых чисел.
* Каждый поток имеет целочисленный ''n''-мерный вектор (''n'' – количество потоков), проинициализированный нулями.
* Перед посылкой/принятием сообщения, поток увеличивает на единицу свою компоненту вектора.
* При посылке сообщения к нему отправляющий поток добавляет свою компоненту вектора, а при приеме сообщения обновляем путем выбора максимума только компоненты, отвечающие отсылающему и принимающему процессам.

В отличие от [[Векторные часы|векторных часов]]:
*при посылке сообщения передаем только свою компоненту вектора;
*при приеме сообщения обновляем путем выбора максимума только компоненты, отвечающие отсылающему и принимающему процессам;

Оказывается, что если ввести [[Частичный порядок|частичный порядок]] предшествования на событиях несколько иным образом (потребовать прямую зависимость), то имеет место следующее утверждение:
:''a'' предшествует ''b'', тогда и только тогда, когда логическое время часов с прямой зависимостью события ''a'' меньше логического времени события ''b'' (''a.v[a.p] ≤ b.v[a.p]'', где ''a.p'' – номер процесса, в котором происходит событие ''a'').

Требование '''прямой зависимости''' звучит следующим образом: между событиями ''a'' (процесс ''u'') и ''b'' (процесс ''v'') процесс ''u'' передал процессу ''v'' сообщение, процесс ''v'' его принял. Если говорить более формально, при транзитивном замыкании, упомянутом в определении частичного порядка предшествования, первое правило можно использовать только один раз.

Часы с прямой зависимостью

2010-06-26T15:09:04Z

Ulyantsev:

[[Категория: Параллельное программирование]]
'''Логические часы с прямой зависимостью''' ''(direct dependency)'' - функция из множества событий (прием/посылка сообщений) в вектор из целых чисел.
* Каждый поток имеет целочисленный n-мерный вектор (n – количество потоков), проинициализированный 0-ми.
* Перед посылкой/принятием сообщения, поток инкрементит свою компоненту вектора.
* При посылке сообщения к сообщению отправляющий поток добавляет свою компоненту вектора, а при приеме сообщения обновляем путем выбора максимума только компоненты, отвечающие отсылающему и принимающему процессам.

В отличие от [[Параллельное программирование: Векторные часы|векторных часов]]:
*при посылке сообщения передаем только свою компоненту вектора;
*при приеме сообщения обновляем путем выбора максимума только компоненты, отвечающие отсылающему и принимающему процессам;

Оказывается, что если ввести [[Параллельное программирование: Частичный порядок|частичный порядок]] предшествования на событиях несколько иным образом (потребовать прямую зависимость), то имеет место следующее утверждение:
:''a'' предшествует ''b'', тогда и только тогда, когда логическое время часов с прямой зависимостью события ''a'' меньше логического времени события ''b'' (''a.v[a.p] <tex>\le</tex> b.v[a.p]'', где ''a.p'' – номер процесса, в котором проиходит событие ''a'').

Требование '''прямой зависимости''' звучит следующим образом: между событиями ''a'' (процесс ''u'') и ''b'' (процесс ''v'') процесс u передал процессу ''v'' сообщение, процесс ''v'' его принял. Если говорить более формально, при транзитивном замыкании, упомянутом в определении частичного порядка предшествования, первое правило можно использовать только один раз.

Логические часы Лампорта

2010-06-26T14:28:57Z

Ulyantsev:

[[Категория: Параллельное программирование]]
'''Логическими часами Лампорта''' называется целочисленная функция из множества событий (прием/посылка сообщений).

* Каждый поток имеет целочисленную переменную, проинициализированную 0.
* Перед посылкой, поток увеличивает ее на единицу.
* При посылке сообщения к нему отправляющий поток добавляет значение своей переменной, а при приеме сообщения поток присваивает своей переменной максимум из полученного значения и значения собственной переменной и увеличивает ее на единицу.

Значением вышеупомянутой целочисленной функции на событии является значение переменной, принадлежащей тому же потоку, что и событие. Стоит заметить, что логическое время события не уникально (уникально только в рамках своего потока).

Оказывается, что если в распределенной системе ввести [[Частичный порядок|частичный порядок предшествования на событиях]], то имеет место следующее утверждение:
:Если ''a'' предшествует ''b'', то логическое время часов Лампорта события ''a'' меньше логического времени события ''b'' (обратное, вообще говоря, не верно).

Участник:Ulyantsev

2010-06-26T14:14:11Z

Ulyantsev: Удалено содержимое страницы

Параллельное программирование

2010-06-26T14:08:46Z

Ulyantsev: /* 8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===2. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===

*[[Глобальные свойства системы]]
*[[Слабый конъюнктивный предикат]]

===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===

Алгоритм Дейксты и Шолтена в английской википедии<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref>.

===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===

'''Алгоритм Чанди-Робертса''' (Chang and Roberts) выбора лидера <ref>http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm</ref>.

Пусть процессы находятся в кольце.
Посылаем свой номер налево по кольцу.
При получении номера справа посылаем налево максимум из своего номера и полученного справа.
Если полученный справа номер является нашим номером, то заканчиваем работу.

'''Алгоритм Хирчберга-Синклера''' <ref>http://en.wikipedia.org/wiki/HS_algorithm</ref>.

===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Данный вопрос достаточно хорошо описан в <ref>http://ru.wikipedia.org/wiki/Задача_византийских_генералов</ref>.

<references/>

Параллельное программирование

2010-06-26T13:48:47Z

Ulyantsev: /* 13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===2. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===

'''Алгоритм Чанди-Робертса''' (Chang and Roberts) выбора лидера <ref>http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm</ref>.

Пусть процессы находятся в кольце.
Посылаем свой номер налево по кольцу.
При получении номера справа посылаем налево максимум из своего номера и полученного справа.
Если полученный справа номер является нашим номером, то заканчиваем работу.

'''Алгоритм Хирчберга-Синклера''' <ref>http://en.wikipedia.org/wiki/HS_algorithm</ref>.

===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Данный вопрос достаточно хорошо описан в <ref>http://ru.wikipedia.org/wiki/Задача_византийских_генералов</ref>.

<references/>

Параллельное программирование

2010-06-26T13:40:33Z

Ulyantsev: /* 13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===2. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===

Алгоритм Чанди-Робертса (Chang and Roberts) выбора лидера <ref>http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm</ref>.

Пусть процессы находятся в кольце.
Посылаем свой номер налево по кольцу.
При получении номера справа посылаем налево максимум из своего номера и полученного справа.
Если полученный справа номер является нашим номером, то заканчиваем работу.

===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Данный вопрос достаточно хорошо описан в <ref>http://ru.wikipedia.org/wiki/Задача_византийских_генералов</ref>.

<references/>

Параллельное программирование

2010-06-26T13:39:26Z

Ulyantsev: /* 13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===2. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===

Алгоритм Чанди-Робертса (Chang and Roberts) выбора лидера.

Пусть процессы находятся в кольце.
Посылаем свой номер налево по кольцу.
При получении номера справа посылаем налево максимум из своего номера и полученного справа.
Если полученный справа номер является нашим номером, то заканчиваем работу.

===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Данный вопрос достаточно хорошо описан в <ref>http://ru.wikipedia.org/wiki/Задача_византийских_генералов</ref>.

<references/>

Параллельное программирование

2010-06-26T13:37:53Z

Ulyantsev: /* 13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===2. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===

Алгоритм Чанди-Робертса (Chundy-Roberts) выбора лидера.

Пусть процессы находятся в кольце.
Посылаем свой номер налево по кольцу.
При получении номера справа посылаем налево максимум из своего номера и полученного справа.
Если полученный справа номер является нашим номером, то заканчиваем работу.

===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Данный вопрос достаточно хорошо описан в <ref>http://ru.wikipedia.org/wiki/Задача_византийских_генералов</ref>.

<references/>

Параллельное программирование

2010-06-26T13:21:32Z

Ulyantsev: /* 18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1 */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===2. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===
===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Данный вопрос достаточно хорошо описан в <ref>http://ru.wikipedia.org/wiki/Задача_византийских_генералов</ref>.

<references/>

Параллельное программирование

2010-06-26T13:21:02Z

Ulyantsev:

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===2. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===
===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Данный вопрос достаточно хорошо описан в <ref>http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%B2%D0%B8%D0%B7%D0%B0%D0%BD%D1%82%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D1%85_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D0%BB%D0%BE%D0%B2</ref>.

<references/>

Параллельное программирование

2010-06-26T13:20:37Z

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===2. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===
===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Данный вопрос достаточно хорошо описан в <ref>http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%B2%D0%B8%D0%B7%D0%B0%D0%BD%D1%82%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D1%85_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D0%BB%D0%BE%D0%B2</ref>.

Параллельное программирование

2010-06-26T13:08:14Z

Ulyantsev: /* 17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1 билет===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]
===2 билет===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]

===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===
===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===
===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Консенсус

2010-06-26T13:00:09Z

Ulyantsev:

[[Категория: Параллельное программирование]]
'''Консенсус''' - задача о соглашении при условии, что любой процесс может упасть.
Каждый процесс предлагает некоторое число. Задача - все живые процессы должны вернуть одно и то же значение (согласованность, agreement), которое было предложено одним из потоков (обоснованность).

Параллельное программирование

2010-06-26T12:58:30Z

Ulyantsev: /* 16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1 билет===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]
===2 билет===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]

===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===
===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===
===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Параллельное программирование

2010-06-26T12:03:16Z

=Программирование параллельных и распределенных систем=
===1 билет===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]
===2 билет===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===
===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===
===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===
===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

Два процесса в случае ненадежного канала не могут достичь консенсуса.

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Параллельное программирование

2010-06-26T11:59:13Z

=Программирование параллельных и распределенных систем=
===1 билет===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]
===2 билет===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===
===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===
===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===
===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

Два процесса в случае ненадежного канала не могут достичь консенсуса.

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Параллельное программирование

2010-06-26T11:53:16Z

Ulyantsev: /* 16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации */

=Программирование параллельных и распределенных систем=
===1 билет===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]
===2 билет===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===
===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===
===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===
===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===

Два процесса в случае ненадежного канала не могут достичь консенсуса.

===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===
===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Параллельное программирование

2010-06-26T11:48:44Z

Ulyantsev: /* 15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов */

=Программирование параллельных и распределенных систем=
===1 билет===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]
===2 билет===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===
===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===
===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===
===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

(я не понял, как это)

===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===
===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===
===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Параллельное программирование

2010-06-26T11:40:26Z

Ulyantsev: /* 14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство) */

=Программирование параллельных и распределенных систем=
===1 билет===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]
===2 билет===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===
===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===
===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===
===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===

#Отказ узла
#Отказ связи
#Неустойчивая связь / пропуск пакетов
#Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===
===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===
===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===
===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===

Параллельное программирование

2010-06-26T11:35:45Z

Параллельное программирование

2010-06-26T11:14:13Z

Ulyantsev: /* Программирование параллельных и распределенных систем */

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

2010-06-20T21:01:57Z

Ulyantsev:

У сжимающего отображения <tex>A : \overline{V} \to \overline{V}</tex> существует единственная неподвижная точка <tex>\mathbb{}x^{*}: Ax^{*}=x^{*}</tex>.

===Доказательство теоремы===

Доказательство из википедии, его еще стоит ПЕРЕДЕЛАТЬ!

Возьмём <tex>\forall x_0 \in \overline{V}</tex> и рассмотрим последовательность <tex>\{x_n\}</tex>, где <tex>x_1=Tx_0, x_2=Tx_1, \dots ,x_{n+1}=Tx_n</tex>.
Покажем, что эта последовательность [[фундаментальная последовательность|фундаментальная]].
В самом деле:
:<tex>d(x_1,x_2)=d(Tx,Tx_1)\leqslant\alpha d(x,x_1)=\alpha d(x,Tx),</tex>
:<tex>d(x_2,x_3)=d(Tx_1,Tx_2)\leqslant\alpha d(x_1,x_2)={\alpha}^{2} d(x,Tx),</tex>
:<tex>\dots,</tex>
:<tex>d(x_n,x_{n+1})=d(Tx_{n-1},Tx_n)\leqslant\alpha d(x_{n-1},x_n)={\alpha}^{n} d(x,Tx)</tex>.

Таким образом, по неравенству треугольника для любых <tex>n,p \in \mathbb{N}</tex>
:<tex>d(x_n,x_{n+p}) \le d(x_n,x_{n+1})+d(x_{n+1},x_{n+p}) \le</tex>
:<tex>\le d(x_{n},x_{n+1}) + d(x_{n+1},x_{n+2})+d(x_{n+2},x_{n+p}) \le \dots</tex>
:<tex>\dots \le d(x_{n},x_{n+1})+d(x_{n+1},x_{n+2})+ \dots + d(x_{n+p-1},x_{n+p})\le</tex>
:<tex>\le {\alpha}^{n}d(x,Tx) + {\alpha}^{n+1}d(x,Tx) + \dots + {\alpha}^{n+p-1}d(x,Tx)=</tex>
:<tex>= ({\alpha}^{n}+{\alpha}^{n+1}+\dots+{\alpha}^{n+p-1})d(x,Tx)
\le\frac{{\alpha}^{n}}{1-\alpha}d(x,Tx) </tex>.

Но <tex>\frac{{\alpha}^{n}}{1-\alpha} \to 0 </tex> при <tex>n \to \infty</tex>, значит для <tex>\varepsilon > 0 \quad\exists N\colon\forall n \geqslant N \to \frac{{\alpha}^{n}}{1-\alpha} < \frac{\varepsilon}{d(x,Tx)+1}</tex>.

Таким образом, для <tex>\varepsilon > 0 \quad \exists N\colon\forall n > N, \forall p \in\mathbb{N}\colon d(x_n,x_{n+p})
\leqslant \frac{{\alpha}^{n}}{1-\alpha}d(x,Tx) < \frac{\varepsilon}{d(x,Tx)+1}d(x,Tx) < \varepsilon </tex>.

Значит <tex>\{x_n\}</tex> фундаментальна. Но т.к. <tex>X</tex> полно, то <tex>\exists x^* \in X\colon\lim_{n \to \infty}x_n = x^*</tex>. Тогда берём <tex>x_{n+1}=Tx_n</tex> и переходим к пределу, т.к. сжимающий оператор — непрерывная функция. Существование доказано.

Докажем единственность. Предположим обратное, т.е. пусть <tex>\exists y^* \in X\colon y^*=Ty^* \Rightarrow d(x^*,y^*) = </tex> (т.к. <tex>x^*</tex> и <tex>y^*</tex> - неподвижные точки) <tex>d(Tx^*,Ty^*) \leqslant\alpha d(x^*,y^*) \Rightarrow d(x^*,y^*) \leqslant \alpha d(x^*,y^*)
\Rightarrow (1-\alpha)d(x^*,y^*) \leqslant 0 \Rightarrow d(x^*,y^*) \leqslant 0 \Rightarrow x^*=y^*</tex>.

Теорема доказана.

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

2010-06-20T20:42:47Z

Ulyantsev: /* Доказательство теоремы */

У сжимающего отображения существует единственная неподвижная точка <tex>\mathbb{}x^{*}: Ax^{*}=x^{*}</tex>.

===Доказательство теоремы===

Возьмём <tex>\forall x \in X</tex> и рассмотрим последовательность <tex>x_1=Tx,x_2=Tx_1,\dots,x_{n+1}=Tx_n</tex>. Получаем <tex>\{x_n\}</tex>. Покажем, что эта последовательность [[фундаментальная последовательность|фундаментальная]]. В самом деле:
:<tex>d(x_1,x_2)=d(Tx,Tx_1)\leqslant\alpha d(x,x_1)=\alpha d(x,Tx),</tex>
:<tex>d(x_2,x_3)=d(Tx_1,Tx_2)\leqslant\alpha d(x_1,x_2)={\alpha}^{2} d(x,Tx),</tex>
:<tex>\dots,</tex>
:<tex>d(x_n,x_{n+1})=d(Tx_{n-1},Tx_n)\leqslant\alpha d(x_{n-1},x_n)={\alpha}^{n} d(x,Tx)</tex>.
Таким образом, по неравенству треугольника для
:<tex>\forall n,p \in \mathbb{N} \quad d(x_n,x_{n+p}) \leqslant d(x_n,x_{n+1})+d(x_{n+1},x_{n+p}) \leqslant d(x_{n},x_{n+1})+d(x_{n+1},x_{n+2})+d(x_{n+2},x_{n+p})
\leqslant \dots</tex>
:<tex>\dots \leqslant d(x_{n},x_{n+1})+d(x_{n+1},x_{n+2})+ \dots + d(x_{n+p-1},x_{n+p})\leqslant</tex>
:<tex>\leqslant {\alpha}^{n}d(x,Tx) + {\alpha}^{n+1}d(x,Tx) + \dots + {\alpha}^{n+p-1}d(x,Tx)
= ({\alpha}^{n}+{\alpha}^{n+1}+\dots+{\alpha}^{n+p-1})d(x,Tx)
\leqslant\frac{{\alpha}^{n}}{1-\alpha}d(x,Tx) </tex>.

Но <tex>\frac{{\alpha}^{n}}{1-\alpha} \to 0 </tex> при <tex>n \to \infty</tex>, значит для <tex>\varepsilon > 0 \quad\exists N\colon\forall n \geqslant N \to \frac{{\alpha}^{n}}{1-\alpha} < \frac{\varepsilon}{d(x,Tx)+1} </tex>.

Таким образом, для <tex>\varepsilon > 0 \quad \exists N\colon\forall n > N, \forall p \in\mathbb{N}\colon d(x_n,x_{n+p})
\leqslant \frac{{\alpha}^{n}}{1-\alpha}d(x,Tx) < \frac{\varepsilon}{d(x,Tx)+1}d(x,Tx) < \varepsilon </tex>.

Значит <tex>\{x_n\}</tex> фундаментальна. Но т.к. <tex>X</tex> полно, то <tex>\exists x^* \in X\colon\lim_{n \to \infty}x_n = x^*</tex>. Тогда берём <tex>x_{n+1}=Tx_n</tex> и переходим к пределу, т.к. сжимающий оператор — непрерывная функция. Существование доказано.

Докажем единственность. Предположим обратное, т.е. пусть <tex>\exists y^* \in X\colon y^*=Ty^* \Rightarrow d(x^*,y^*) = </tex> (т.к. <tex>x^*</tex> и <tex>y^*</tex> - неподвижные точки) <tex>d(Tx^*,Ty^*) \leqslant\alpha d(x^*,y^*) \Rightarrow d(x^*,y^*) \leqslant \alpha d(x^*,y^*)
\Rightarrow (1-\alpha)d(x^*,y^*) \leqslant 0 \Rightarrow d(x^*,y^*) \leqslant 0 \Rightarrow x^*=y^*</tex>.

Теорема доказана.

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

2010-06-20T20:35:10Z

Ulyantsev: Новая страница: «У сжимающего отображения существует единственная неподвижная точка <tex>\mathbb{}x^{*}: Ax^{*}=x^{*}</tex…»

У сжимающего отображения существует единственная неподвижная точка <tex>\mathbb{}x^{*}: Ax^{*}=x^{*}</tex>.

===Доказательство теоремы===

Функциональный анализ

2010-06-20T20:34:24Z

Ulyantsev: /* 22. Теорема Банаха о сжимающем отображении */

Здесь я постараюсь написать теоретический минимум по второй части курса функционального анализа.

Большая часть материала взята из Википедии, чтобы не перебивать формулы и все такое. Все остальное бралось из конспектов, лучший из них лежит на firun.ru

Если вы читаете это, самоуничтожьтесь.

Да, да, '''функциональный анализ''' — раздел математики, в котором изучаются бесконечномерные пространства (в основном пространства функций) и их отображения.

==В прошлых сериях==

*'''Метрическое пространство''' <tex>M</tex> есть множество точек с '''метрикой''' <tex>d \colon M \times M \to \mathbb{R}</tex>:
# <tex>d(x,\;y) \ge 0 ; d(x,\;y)=0\Leftrightarrow x=y</tex>.
# <tex>d(x,\;y)=d(y,\;x)</tex>.
# <tex>d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)</tex>.

*Метрическое пространство называется '''полным''', если любая фундаментальная последовательность в нём сходится к некоторому элементу этого пространства.

*'''Банаховым пространством''' называется нормированное линейное пространство полное по метрике, порождённой нормой.

*'''Пространство непрерывных функций''' — линейное нормированное пространство, элементами которого являются непрерывные на отрезке <tex>[a,b]</tex> функции (обычно обозначается <tex>{\mathrm C}[a,b]</tex>). Норма в этом пространстве определяется следующим образом: <tex>||x||_{{\mathbf C}[a,b]}=\max_{t\in [a,b]}|x(t)|</tex>

* '''Теорема Рисса — Фреше:''' Для любого непрерывного линейного функционала <tex>f</tex> на Гильбертовом пространстве <tex> H</tex> существует единственный вектор <tex>y \in H</tex> такой, что <tex>f(x)=(x,y)</tex> для любого <tex>x \in H</tex>. При этом норма линейного функционала <tex>f</tex> совпадает с нормой вектора <tex>y</tex>: <tex>\|f\|=\sup_{\|x\|=1} |f(x)|= \sqrt{(y,y)}</tex>. Теорема также означает, что пространство всех линейных ограниченных функционалов над <tex>H</tex> изоморофно пространству <tex>H</tex>.

*Теорема (Хан-Банах) о продолжении линейного функционала с сохранением мажоранты: любой линейный функционал <tex>f(x)</tex>, определённый на подпространстве <tex>L</tex> линейного пространства <tex>X</tex> и удовлетворяющий условию <tex>|f(x)| \leq p(x), \forall x \in L</tex>, где <tex>p(x)</tex> — некоторый положительно однородный функционал (определённый на всем пространстве <tex>X</tex>) то <tex>f(x)</tex> может быть продолжен на все пространство <tex>X</tex> с сохранением этого условия.

*Теорема (Хан-Банах) о непрерывном продолжении линейного функционала: всякий линейный функционал <tex>f(x)</tex>, определённый на линейном многообразии <tex>L</tex> линейного нормированного пространства <tex>X</tex>, можно продолжить на все пространство с сохранением нормы.

*Следствие: для любых двух различных точек линейного пространства существует линейный функционал, определённый на всем пространстве и такой, что его значения в этих точках различны.

* '''Ядром''' линейного отображения <tex>f\colon A\to B</tex> называются подмножество <tex>A</tex>, которое отображается в нуль: <tex>\mbox{Ker}\,f = \{ x\in A\mid f(x) = 0 \}</tex>. Ядро линейного отображения образует подпространство в линейном пространстве <tex>A</tex>.

*Пусть <tex>A</tex> — оператор, действующий в банаховом пространстве <tex>E</tex>. Число λ называется ''регулярным'' для оператора <tex>A</tex>, если оператор <tex>R(\lambda)=(A - \lambda I)^{-1}</tex>, называемый '''резольвентой''' оператора <tex>A</tex>, определён на всём <tex>E</tex> и непрерывен. Множество регулярных значений оператора <tex>A</tex> называется '''резольвентным множеством''' этого оператора, а дополнение резольвентного множества — '''спектром''' этого оператора.

==Билеты==
===1. Сопряженный оператор и его ограниченность===

Будем работать с <tex>E</tex>, как с банаховым пространством.

'''Def''': Пространство всех линейных функционалов на <tex>E</tex> образует линейное пространство (прошлый семестр).
Это пространство называется '''сопряжённым''' к <tex>E</tex>, оно обычно обозначается <tex>E^*</tex>.

'''Def''': Пусть <tex>A:E\to F</tex> — непрерывный линейный оператор действующий из банахова пространства <tex>E</tex> в банахово пространство <tex>F</tex>. И пусть <tex>E^*, F^*</tex> — сопряжённые пространства. Обозначим <tex>\forall x\in E, f\in F^* \langle Ax,f\rangle =f(Ax)</tex>. Если <tex>f</tex> — фиксировано, то <tex>\langle Ax,f \rangle </tex> — линейный непрерывный функционал в <tex>E, \langle Ax,f \rangle \in E^*</tex>. Таким образом, для <tex>\forall f\in F^*</tex> определён линейный непрерывный функционал из <tex>E^* </tex>, поэтому определён оператор <tex>A^*:F^*\to E^*</tex>, такой что <tex>\langle Ax,f \rangle=\langle x,A^*f \rangle</tex>.
<tex>A^*</tex> называется '''сопряжённым оператором'''.

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>. Тогда норма оператора <tex>A^*:F^*\to E^*</tex> совпадает с нормой <tex>A</tex>.

(оператор проектирования ??)

===2. Ортогональные дополнения Е и Е*===

'''Def''': Пусть <tex>S</tex> некоторое линейное множество. Тогда его '''ортогональное дополнение''' <tex>S^\perp = \{f \in E^* | f(x) = 0 \; \forall x \in S\}</tex>.

'''Th''': Имеют место соотношения: <tex>E^\perp = \{0\}</tex>; <tex>(E^*)^\perp = \{0\}</tex>.

(при доказательстве используем теорему Хана-Банаха)

===3. Ортогональное дополнение R(A)===

(Здесь можно написать красивый текст из конспекта про важность теорем и все такое)

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>, где <tex>E</tex> и <tex>F</tex> банаховы. Пусть также множество значений <tex>R(A)</tex> замкнуто в <tex>F</tex>. Тогда <tex>R(A) = (Ker(A^*))^\perp</tex>.

===4. Ортогональное дополнение R(A*)===

'''Th''': Пусть множество значений оператора <tex>A</tex> замкнуто: <tex>R(A) = Cl(R(A))</tex>. Тогда верно <tex>R(A^*) = Cl(R(A^*)) = (Ker(A))^\perp</tex>.

----

===5. Арифметика компактных операторов===

'''Def''': Линейный оператор <tex>A:E\to F</tex> называется '''компактным''', если он переводит любое ограниченное множество из <tex>E</tex> в относительно компактное множество в <tex>F</tex>.

Примером является оператор Фредгольма: <tex>\psi(s) = \int\limits_a^b\!K(s, t) \varphi(t)\, dt</tex>.

Установим несколько свойств:

'''Th''': Пусть операторы <tex>A, B:E\to E</tex> такие, что <tex>A</tex> компактен, а <tex>B</tex> ограничен. Тогда операторы <tex>AB</tex> и <tex>BA</tex> компактны.

===6. О компактности А*, сепарабельность R(A)===
[[Теорема о компактности сопряженного оператора]]

===7. Базис Шаудера, лемма о координатном пространстве===

'''Def''': Система векторов <tex>\{e_n\}</tex> топологического векторного пространства <tex>E</tex> называется '''базисом Шаудера''', если каждый элемент <tex>f \in E</tex> разлагается в ''единственный'', сходящийся к <tex>f</tex> ряд по <tex>\{e_n\}</tex>: <tex>f= \sum_{i=1}^{\infty} f_i e_i</tex>, где <tex>f_i</tex> — числа, называемые коэффициентами разложения вектора <tex>f</tex> по базису <tex>\{e_n\}</tex>.

===8. Почти конечномерность компактного оператора===

----
Теперь походим вокруг альтернативы Фредгольма-Шаудера.

===9. О размерности Ker(I-A) компактного А===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор, <tex> H = I - A </tex>.
Тогда, <tex> dim (Ker H)< +\infty </tex>

'''Следствие''' Множество решений операторного уравнения <tex> Ax = \lambda x, \lambda \in \mathbb{R} </tex> конечномерно.

===10. Условие замкнутости R(A) на языке решений операторного уравнения===
'''Утв.''' Пусть <tex> A \in L(E, F) </tex> и <tex> \exists \alpha = const : \forall y \in R(A), y = A(x), \exists x \in E : \|x\| \le \alpha \|y\| </tex>. ''Тогда'', <tex> R(A) </tex> - замкнуто.

===11. О замкнутости R(I-A) компактного А===
'''Утв.''' Пусть оператор <tex> A </tex> - компактный. Тогда, <tex> R(I - A) </tex> - замкнуто.

===12. Лемма о Ker(I-A)*n компактного А===
'''Утв.''' Пусть оператор <tex>A</tex> - компактный, и <tex> k \in \mathbb{N}</tex>.
Тогда, <tex>Ker(I - A)^{k + 1} = Ker(I - A)^k</tex>

===13. Об условии справедливости равенства R(I-A)=Е===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор. Тогда,
<tex> R(I - A) = E \Leftrightarrow Ker(I - A) = \{0\}</tex>

===14. Альтернатива Фредгольма-Шаудера===
'''Th.''' (''Альтернатива Фредгольма-Шаудера'')

Пусть <tex> A : E \rightarrow E </tex> - компактный оператор, <tex>E - B</tex>-пространство.

Тогда, <tex> \forall \lambda \neq 0</tex> возможны только 2 случая:
# <tex> Ker(\lambda I - A) = \{0\} \Rightarrow \lambda \in \rho(A) </tex>
# <tex> Ker(\lambda I - A) \neq \{0\} \Rightarrow </tex> (уравнение <tex>(\lambda I - A)x = y</tex> разрешимо относительно <tex>x) \Leftrightarrow y \in (Ker(\lambda I^{*} - A^{*}))^{\bot}</tex>

===15. О спектре компактного оператора===

----
Теперь это называется Теорией Гильберта-Шмидта

===16. О вещественности спектра ограниченного самосопряженного оператора===
'''Утв.''' Пусть <tex> A </tex> - ограниченный и самосопряженный оператор. Тогда, <tex>\sigma(A) \subset \mathbb{R}</tex>

===17. О характеризации спектра и резольвентного множества ограниченного самосопряженного оператора===
'''Th.''' Пусть <tex> A </tex> - ограниченный и самосопряженный оператор. Тогда,

# <tex> \lambda \in \rho(A) \Leftrightarrow \exists m > 0 : \|(\lambda I - A)x\| \ge m \|x\| </tex>
# <tex> \lambda \in \sigma(A) \Leftrightarrow \exists \{x_n | \|x_n\| = 1\}</tex>, т.ч. <tex> \lim_{n \rightarrow \infty}\|(\lambda I - A)x_n\| = 0 </tex>

===18. О числах m- и m+===
'''Def.''' <tex> m_{-} = \inf_{\|x\| = 1}\langle Ax, x \rangle</tex>

'''Def.''' <tex> m_{-} = \sup_{\|x\| = 1}\langle Ax, x \rangle</tex>

'''Def.''' Если для некоторого оператора <tex>L : \langle Ax, x \rangle \ge 0 </tex>, то <tex>L</tex> называется '''неотрицательным'''.

'''Th.''' Пусть <tex>A</tex> - ограниченный и самосопряженный оператор. Тогда, <tex>\sigma(A) \subset [m_{-}, m_{+}]</tex>, и
<tex>m_{-} \in \sigma(A), m_{+} \in \sigma(A)</tex>

===19. Спектральный радиус ограниченного самосопряженного оператора===
'''Th.''' Пусть <tex>A</tex> - ограниченный, самосопряженный оператор. Тогда, <tex>\|A\| = r_{\sigma} = \max\{|m_{-}|, |m_{+}|\}</tex>

===20. Теорема Гильберта-Шмидта===

===21. О диагонализации компактного самосопряженного оператора и разложении его резольвенты===

----
Элементы нелинейного функционального анализа.

===22. Теорема Банаха о сжимающем отображении===

'''Def''': Пусть на метрическом пространстве <tex>(M, \rho)</tex> определён оператор <tex>A: M \to M</tex>. Он называется сжимающим на <tex>M</tex>, если <tex>\exists\alpha\in(0; 1)</tex> такой, что для <tex>{\forall}x,y \in M</tex> выполняется <tex>{\rho(Ax,Ay)\leqslant\alpha{\cdot}\rho(x,y)}</tex>.

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

===23. Дифференциал Фреше===

===24. Неравенство Лагранжа===

===25. Локальная теорема о неявном отображении===
'''Th.'''(''о неявном отображении'')

Пусть <tex>\overline{V}</tex> - замкнутый шар в <tex> X, \overline{V} \subset X</tex>.

Пусть <tex>\overline{W} \subset Y</tex> - замкнутый шар в <tex>Y</tex> и задан оператор <tex>T : \overline{V} \times \overline{W} \rightarrow Y</tex> и <tex>z = T(x, y), \: x \in \overline{V}, \: y \in \overline{W},\: z \in Y</tex>.

Пусть <tex>x_0 \in V,\: y_0 \in W,\: T(x_0, y_0) = \theta \in Y</tex>.

Пусть <tex> \forall x \in V, \forall y \in W \quad \exists T^{'}_y </tex> - дифференциал Фреше, непрерывный как отображение переменных <tex>x</tex> и <tex>y</tex>.

Пусть также <tex>T^{'}_{y}(x_0, y_0)</tex> - непрерывно обратим.

'''Тогда''', задача о неявном отображении для <tex>T(x, y) = 0</tex> c начальным решением <tex>T(x_0, y_0) = 0</tex> разрешима в некоторой окрестности точки <tex>(x_0, y_0)</tex>

===26. Теорема о локальной обратимости отображения===

===27. Локальная теорема о простой итерации===

===28. Локальная теорема о методе Ньютона-Канторовича===

===29. О проекторах Шаудера===

===30. Теорема Шаудера о неподвижной точке===

Равностепенная непрерывность

2010-06-20T20:29:15Z

Ulyantsev: Новая страница: «Пусть <tex>X</tex>, <tex>Y</tex> — компактные метрические пространства и <tex>C(X,\;Y)</tex> — множество непр…»

Пусть <tex>X</tex>, <tex>Y</tex> — компактные метрические пространства и <tex>C(X,\;Y)</tex> — множество непрерывных отображений <tex>X</tex> в <tex>Y</tex>.
Множество <tex>D\in C(X,\;Y)</tex> называется равностепенно непрерывным, если для любого <tex>\varepsilon > 0</tex> существует такое <tex>\delta>0</tex>, что из <tex>d_X(x,\;y)<\delta</tex> вытекает <tex>d_Y(f(x),\;f(y))<\varepsilon</tex> для любой <tex>f\in D</tex>.

Теорема о компактности сопряжённого оператора

2010-06-20T20:28:19Z

Ulyantsev: /* Доказательство теоремы */

Пусть <tex>A</tex> является компактным оператором. Тогда сопряженный к нему оператор <tex>A^*</tex> также является компактным.

===Доказательство теоремы===

Итак, рассмотрим оператор <tex>A^*: F^* \to E^*</tex>.
По определению сопряженного оператора, если <tex>\phi \in F^*</tex>, то <tex>A^*\phi = \phi A</tex>.
Будем последовательны.

1. Для доказательства необходимо показать, что множество <tex>\{A^*\phi \mid \|\phi\| \le 1\}</tex> будет относительно компактно в <tex>E^*</tex>.
Для этого надо показать, что если взята последовательность <tex>\{\phi_n\}</tex> такая, что <tex>\|\phi_n\| \le 1\</tex>, то можно выбрать <tex>\{\phi_{n_k}\}</tex> такую, что <tex>A^*\phi_{n_k}</tex> сходится в <tex>E^*</tex>.

2. Рассмотрим в <tex>E</tex> единичный замкнутый шар <tex>\overline{V}</tex>.
По компактности оператора <tex>K = Cl(A(\overline{V})) \subset F</tex> будет метрическим компактом.
Рассмотрим ''сужение'' функционалов <tex>\phi_n</tex> на <tex>K</tex>.

3. Докажем [[равностепенная непрерывность|равностепенную непрерывность]] этой последовательности: рассмотрим <tex>y, z \in K</tex>.
Норма
:<tex>\|\phi_n(z) - \phi_n(y)\| = \|\phi_n(z - y)\| \le \|\phi_n\| \|z - y\| \le \|z - y\|</tex>
не зависит от <tex>n</tex>, а следовательно <tex>\{\phi_n\}</tex> равностепенно непрерывна.

4. Выполняется и ''равномерная ограниченность'' последовательности. Для любого <tex>y \in K</tex>:
:<tex>\|\phi_n(y)\| \le \|\phi_n\| \|y\| \le \|y\| \le const</tex>.

5. Таким образом <tex>\{\phi_n\}</tex> равномерно ограничена и равностепенно непрерывна, следовательно, по теореме Арцела — Асколи из нее можно выделить равномерно сходящуюся последовательность <tex>\{\phi_{n_m}\}</tex> в <tex>K</tex>.

Для доказательства теоремы осталось показать, что <tex>A^*\{\phi_{n_m}\}</tex> сходится в <tex>E^*</tex>. Для этого достаточно выяснить, что <tex>A^*\{\phi_{n_m}\}</tex> равномерно сходится (при устремлении <tex>m</tex> к бесконечности) на <tex>\overline{V}</tex>.

6. Рассмотрим <tex>\varepsilon > 0</tex>. По равномерной сходимости <tex>\{\phi_{n_m}\}</tex> на <tex>K</tex>:
<tex>\exists p_0 : \forall i, j \ge p_0 : \forall y \in K : \| \phi_{n_j}(y) - \phi_{n_i}(y) \| \le \varepsilon</tex>.

7. Следовательно, для любого <tex>x \in \overline{V}</tex> верно <tex>\| \phi_{n_j}(Ax) - \phi_{n_i}(Ax) \| \le \varepsilon</tex>.
Замечая, что <tex>\phi_{n_i}(Ax) = A^*(\phi_{n_i}, x)</tex>, приходим к равномерной сходимости <tex>A^*\phi_{n_m}</tex> на <tex>\overline{V}</tex>.

Таким образом, теорема доказана.

Теорема о компактности сопряжённого оператора

2010-06-20T20:25:02Z

Ulyantsev: /* Доказательство теоремы */

Пусть <tex>A</tex> является компактным оператором. Тогда сопряженный к нему оператор <tex>A^*</tex> также является компактным.

===Доказательство теоремы===

Итак, рассмотрим оператор <tex>A^*: F^* \to E^*</tex>.
По определению сопряженного оператора, если <tex>\phi \in F^*</tex>, то <tex>A^*\phi = \phi A</tex>.
Будем последовательны.

1. Для доказательства необходимо показать, что множество <tex>\{A^*\phi \mid \|\phi\| \le 1\}</tex> будет относительно компактно в <tex>E^*</tex>.
Для этого надо показать, что если взята последовательность <tex>\{\phi_n\}</tex> такая, что <tex>\|\phi_n\| \le 1\</tex>, то можно выбрать <tex>\{\phi_{n_k}\}</tex> такую, что <tex>A^*\phi_{n_k}</tex> сходится в <tex>E^*</tex>.

2. Рассмотрим в <tex>E</tex> единичный замкнутый шар <tex>\overline{V}</tex>.
По компактности оператора <tex>K = Cl(A(\overline{V})) \subset F</tex> будет метрическим компактом.
Рассмотрим ''сужение'' функционалов <tex>\phi_n</tex> на <tex>K</tex>.

3. Докажем ''равностепенную непрерывность'' этой последовательности: рассмотрим <tex>y, z \in K</tex>.
Норма
:<tex>\|\phi_n(z) - \phi_n(y)\| = \|\phi_n(z - y)\| \le \|\phi_n\| \|z - y\| \le \|z - y\|</tex>
не зависит от <tex>n</tex>, а следовательно <tex>\{\phi_n\}</tex> равностепенно непрерывна.

4. Выполняется и ''равномерная ограниченность'' последовательности. Для любого <tex>y \in K</tex>:
:<tex>\|\phi_n(y)\| \le \|\phi_n\| \|y\| \le \|y\| \le const</tex>.

5. Таким образом <tex>\{\phi_n\}</tex> равномерно ограничена и равностепенно непрерывна, следовательно, по теореме Арцела — Асколи из нее можно выделить равномерно сходящуюся последовательность <tex>\{\phi_{n_m}\}</tex> в <tex>K</tex>.

Для доказательства теоремы осталось показать, что <tex>A^*\{\phi_{n_m}\}</tex> сходится в <tex>E^*</tex>. Для этого достаточно выяснить, что <tex>A^*\{\phi_{n_m}\}</tex> равномерно сходится (при устремлении <tex>m</tex> к бесконечности) на <tex>\overline{V}</tex>.

6. Рассмотрим <tex>\varepsilon > 0</tex>. По равномерной сходимости <tex>\{\phi_{n_m}\}</tex> на <tex>K</tex>:
<tex>\exists p_0 : \forall i, j \ge p_0 : \forall y \in K : \| \phi_{n_j}(y) - \phi_{n_i}(y) \| \le \varepsilon</tex>.

7. Следовательно, для любого <tex>x \in \overline{V}</tex> верно <tex>\| \phi_{n_j}(Ax) - \phi_{n_i}(Ax) \| \le \varepsilon</tex>.
Замечая, что <tex>\phi_{n_i}(Ax) = A^*(\phi_{n_i}, x)</tex>, приходим к равномерной сходимости <tex>A^*\phi_{n_m}</tex> на <tex>\overline{V}</tex>.

Таким образом, теорема доказана.

Теорема о компактности сопряжённого оператора

2010-06-20T19:53:07Z

Ulyantsev: /* Доказательство теоремы */

Пусть <tex>A</tex> является компактным оператором. Тогда сопряженный к нему оператор <tex>A^*</tex> также является компактным.

===Доказательство теоремы===

Итак, рассмотрим оператор <tex>A^*: F^* \to E^*</tex>.
По определению сопряженного оператора, если <tex>\phi \in F^*</tex>, то <tex>A^*\phi = \phi A</tex>.

Для доказательства необходимо показать, что множество <tex>\{A^*\phi \mid \|\phi\| \le 1\}</tex> будет относительно компактно в <tex>E^*</tex>.
Для этого надо показать, что если взята последовательность <tex>\{\phi_n\}</tex> такая, что <tex>\|\phi_n\| \le 1\</tex>, то можно выбрать <tex>\{\phi_{n_k}\}</tex> такую, что <tex>A^*\phi_{n_k}</tex> сходится в <tex>E^*</tex>.

Рассмотрим в <tex>E</tex> единичный замкнутый шар <tex>\overline{V}</tex>.
По компактности оператора <tex>K = Cl(A(\overline{V})) \subset F</tex> будет метрическим компактом.
Рассмотрим сужение функционалов <tex>\phi_n</tex> на <tex>K</tex>. (?еще что-то)

Докажем ''равностепенную непрерывность'' этой последовательности: рассмотрим <tex>y, z \in K</tex>.
Норма
:<tex>\|\phi_n(z) - \phi_n(y)\| = \|\phi_n(z - y)\| \le \|\phi_n\| \|z - y\| \le \|z - y\|</tex>
не зависит от <tex>n</tex>, а следовательно <tex>\{\phi_n\}</tex> равностепенно непрерывна.

Выполняется и ''равномерная ограниченность'' последовательности. Для любого <tex>y \in K</tex>:
:<tex>\|\phi_n(y)\| \le \|\phi_n\| \|y\| \le \|y\| \le const</tex>.

Таким образом <tex>\{\phi_n\}</tex> равномерно ограничена и равностепенно непрерывна, следовательно, по теореме Арцела — Асколи из нее можно выделить равномерно сходящуюся последовательность <tex>\{\phi_{n_m}\}</tex> в <tex>K</tex>.

Для доказательства теоремы осталось показать, что <tex>A^*\{\phi_{n_m}\}</tex> сходится в <tex>E^*</tex>. Для этого достаточно выяснить, что <tex>A^*\{\phi_{n_m}\}</tex> равномерно сходится (при устремлении <tex>m</tex> к бесконечности) на <tex>\overline{V}</tex>.

Теорема о компактности сопряжённого оператора

2010-06-20T18:35:23Z

Ulyantsev:

Функциональный анализ

2010-06-19T12:27:30Z

Ulyantsev: /* 22. Теорема Банаха о сжимающем отображении */

Здесь я постараюсь написать теоретический минимум по второй части курса функционального анализа.

Большая часть материала взята из Википедии, чтобы не перебивать формулы и все такое. Все остальное бралось из конспектов, лучший из них лежит на firun.ru

Если вы читаете это, самоуничтожьтесь.

Да, да, '''функциональный анализ''' — раздел математики, в котором изучаются бесконечномерные пространства (в основном пространства функций) и их отображения.

==В прошлых сериях==

*'''Метрическое пространство''' <tex>M</tex> есть множество точек с '''метрикой''' <tex>d \colon M \times M \to \mathbb{R}</tex>:
# <tex>d(x,\;y) \ge 0 ; d(x,\;y)=0\Leftrightarrow x=y</tex>.
# <tex>d(x,\;y)=d(y,\;x)</tex>.
# <tex>d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)</tex>.

*Метрическое пространство называется '''полным''', если любая фундаментальная последовательность в нём сходится к некоторому элементу этого пространства.

*'''Банаховым пространством''' называется нормированное линейное пространство полное по метрике, порождённой нормой.

*'''Пространство непрерывных функций''' — линейное нормированное пространство, элементами которого являются непрерывные на отрезке <tex>[a,b]</tex> функции (обычно обозначается <tex>{\mathrm C}[a,b]</tex>). Норма в этом пространстве определяется следующим образом: <tex>||x||_{{\mathbf C}[a,b]}=\max_{t\in [a,b]}|x(t)|</tex>

* '''Теорема Рисса — Фреше:''' Для любого непрерывного линейного функционала <tex>f</tex> на Гильбертовом пространстве <tex> H</tex> существует единственный вектор <tex>y \in H</tex> такой, что <tex>f(x)=(x,y)</tex> для любого <tex>x \in H</tex>. При этом норма линейного функционала <tex>f</tex> совпадает с нормой вектора <tex>y</tex>: <tex>\|f\|=\sup_{\|x\|=1} |f(x)|= \sqrt{(y,y)}</tex>. Теорема также означает, что пространство всех линейных ограниченных функционалов над <tex>H</tex> изоморофно пространству <tex>H</tex>.

*Теорема (Хан-Банах) о продолжении линейного функционала с сохранением мажоранты: любой линейный функционал <tex>f(x)</tex>, определённый на подпространстве <tex>L</tex> линейного пространства <tex>X</tex> и удовлетворяющий условию <tex>|f(x)| \leq p(x), \forall x \in L</tex>, где <tex>p(x)</tex> — некоторый положительно однородный функционал (определённый на всем пространстве <tex>X</tex>) то <tex>f(x)</tex> может быть продолжен на все пространство <tex>X</tex> с сохранением этого условия.

*Теорема (Хан-Банах) о непрерывном продолжении линейного функционала: всякий линейный функционал <tex>f(x)</tex>, определённый на линейном многообразии <tex>L</tex> линейного нормированного пространства <tex>X</tex>, можно продолжить на все пространство с сохранением нормы.

*Следствие: для любых двух различных точек линейного пространства существует линейный функционал, определённый на всем пространстве и такой, что его значения в этих точках различны.

* '''Ядром''' линейного отображения <tex>f\colon A\to B</tex> называются подмножество <tex>A</tex>, которое отображается в нуль: <tex>\mbox{Ker}\,f = \{ x\in A\mid f(x) = 0 \}</tex>. Ядро линейного отображения образует подпространство в линейном пространстве <tex>A</tex>.

*Пусть <tex>A</tex> — оператор, действующий в банаховом пространстве <tex>E</tex>. Число λ называется ''регулярным'' для оператора <tex>A</tex>, если оператор <tex>R(\lambda)=(A - \lambda I)^{-1}</tex>, называемый '''резольвентой''' оператора <tex>A</tex>, определён на всём <tex>E</tex> и непрерывен. Множество регулярных значений оператора <tex>A</tex> называется '''резольвентным множеством''' этого оператора, а дополнение резольвентного множества — '''спектром''' этого оператора.

==Билеты==
===1. Сопряженный оператор и его ограниченность===

Будем работать с <tex>E</tex>, как с банаховым пространством.

'''Def''': Пространство всех линейных функционалов на <tex>E</tex> образует линейное пространство (прошлый семестр).
Это пространство называется '''сопряжённым''' к <tex>E</tex>, оно обычно обозначается <tex>E^*</tex>.

'''Def''': Пусть <tex>A:E\to F</tex> — непрерывный линейный оператор действующий из банахова пространства <tex>E</tex> в банахово пространство <tex>F</tex>. И пусть <tex>E^*, F^*</tex> — сопряжённые пространства. Обозначим <tex>\forall x\in E, f\in F^* \langle Ax,f\rangle =f(Ax)</tex>. Если <tex>f</tex> — фиксировано, то <tex>\langle Ax,f \rangle </tex> — линейный непрерывный функционал в <tex>E, \langle Ax,f \rangle \in E^*</tex>. Таким образом, для <tex>\forall f\in F^*</tex> определён линейный непрерывный функционал из <tex>E^* </tex>, поэтому определён оператор <tex>A^*:F^*\to E^*</tex>, такой что <tex>\langle Ax,f \rangle=\langle x,A^*f \rangle</tex>.
<tex>A^*</tex> называется '''сопряжённым оператором'''.

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>. Тогда норма оператора <tex>A^*:F^*\to E^*</tex> совпадает с нормой <tex>A</tex>.

(оператор проектирования ??)

===2. Ортогональные дополнения Е и Е*===

'''Def''': Пусть <tex>S</tex> некоторое линейное множество. Тогда его '''ортогональное дополнение''' <tex>S^\perp = \{f \in E^* | f(x) = 0 \; \forall x \in S\}</tex>.

'''Th''': Имеют место соотношения: <tex>E^\perp = \{0\}</tex>; <tex>(E^*)^\perp = \{0\}</tex>.

(при доказательстве используем теорему Хана-Банаха)

===3. Ортогональное дополнение R(A)===

(Здесь можно написать красивый текст из конспекта про важность теорем и все такое)

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>, где <tex>E</tex> и <tex>F</tex> банаховы. Пусть также множество значений <tex>R(A)</tex> замкнуто в <tex>F</tex>. Тогда <tex>R(A) = (Ker(A^*))^\perp</tex>.

===4. Ортогональное дополнение R(A*)===

'''Th''': Пусть множество значений оператора <tex>A</tex> замкнуто: <tex>R(A) = Cl(R(A))</tex>. Тогда верно <tex>R(A^*) = Cl(R(A^*)) = (Ker(A))^\perp</tex>.

----

===5. Арифметика компактных операторов===

'''Def''': Линейный оператор <tex>A:E\to F</tex> называется '''компактным''', если он переводит любое ограниченное множество из <tex>E</tex> в относительно компактное множество в <tex>F</tex>.

Примером является оператор Фредгольма: <tex>\psi(s) = \int\limits_a^b\!K(s, t) \varphi(t)\, dt</tex>.

Установим несколько свойств:

'''Th''': Пусть операторы <tex>A, B:E\to E</tex> такие, что <tex>A</tex> компактен, а <tex>B</tex> ограничен. Тогда операторы <tex>AB</tex> и <tex>BA</tex> компактны.

===6. О компактности А*, сепарабельность R(A)===

===7. Базис Шаудера, лемма о координатном пространстве===

'''Def''': Система векторов <tex>\{e_n\}</tex> топологического векторного пространства <tex>E</tex> называется '''базисом Шаудера''', если каждый элемент <tex>f \in E</tex> разлагается в ''единственный'', сходящийся к <tex>f</tex> ряд по <tex>\{e_n\}</tex>: <tex>f= \sum_{i=1}^{\infty} f_i e_i</tex>, где <tex>f_i</tex> — числа, называемые коэффициентами разложения вектора <tex>f</tex> по базису <tex>\{e_n\}</tex>.

===8. Почти конечномерность компактного оператора===

----
Теперь походим вокруг альтернативы Фредгольма-Шаудера.

===9. О размерности Ker(I-A) компактного А===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор, <tex> H = I - A </tex>.
Тогда, <tex> dim (Ker H)< +\infty </tex>

'''Следствие''' Множество решений операторного уравнения <tex> Ax = \lambda x, \lambda \in \mathbb{R} </tex> конечномерно.

===10. Условие замкнутости R(A) на языке решений операторного уравнения===
'''Утв.''' Пусть <tex> A \in L(E, F) </tex> и <tex> \exists \alpha = const : \forall y \in R(A), y = A(x), \exists x \in E : ||x|| \le \alpha ||y|| </tex>. ''Тогда'', <tex> R(A) </tex> - замкнуто.

===11. О замкнутости R(I-A) компактного А===
'''Утв.''' Пусть оператор <tex> A </tex> - компактный. Тогда, <tex> R(I - A) </tex> - замкнуто.

===12. Лемма о Ker(I-A)*n компактного А===
'''Утв.''' Пусть оператор <tex>A</tex> - компактный, и <tex> k \in \mathbb{N}</tex>.
Тогда, <tex>Ker(I - A)^{k + 1} = Ker(I - A)^k</tex>

===13. Об условии справедливости равенства R(I-A)=Е===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор. Тогда,
<tex> R(I - A) = E \Leftrightarrow Ker(I - A) = \{0\}</tex>

===14. Альтернатива Фредгольма-Шаудера===
'''Th.''' (''Альтернатива Фредгольма-Шаудера'')

Пусть <tex> A : E \rightarrow E </tex> - компактный оператор, <tex>E - B</tex>-пространство.

Тогда, <tex> \forall \lambda \neq 0</tex> возможны только 2 случая:
# <tex> Ker(\lambda I - A) = \{0\} \Rightarrow \lambda \in \rho(A) </tex>
# <tex> Ker(\lambda I - A) \neq \{0\} \Rightarrow </tex> (уравнение <tex>(\lambda I - A)x = y</tex> разрешимо относительно <tex>x) \Leftrightarrow y \in (Ker(\lambda I^{*} - A^{*}))^{\bot}</tex>

===15. О спектре компактного оператора===

----
Теперь это называется Теорией Гильберта-Шмидта

===16. О вещественности спектра ограниченного самосопряженного оператора===
'''Утв.''' Пусть <tex> A </tex> - ограниченный и самосопряженный оператор. Тогда, <tex>\sigma(A) \subset \mathbb{R}</tex>

===17. О характеризации спектра и резольвентного множества ограниченного самосопряженного оператора===
'''Th.''' Пусть <tex> A </tex> - ограниченный и самосопряженный оператор. Тогда,

# <tex> \lambda \in \rho(A) \Leftrightarrow \exists m > 0 : \|(\lambda I - A)x\| \ge m \|x\| </tex>
# <tex> \lambda \in \sigma(A) \Leftrightarrow \exists \{x_n | \|x_n\| = 1\}</tex>, т.ч. <tex> lim_{n \rightarrow \infty}\|(\lambda I - A)x_n\| = 0 </tex>

===18. О числах m- и m+===
'''Def.''' <tex> m_{-} = \inf_{\|x\| = 1}\langle Ax, x \rangle</tex>

===19. Спектральный радиус ограниченного самосопряженного оператора===

===20. Теорема Гильберта-Шмидта===

===21. О диагонализации компактного самосопряженного оператора и разложении его резольвенты===

----
Элементы нелинейного функционального анализа.

===22. Теорема Банаха о сжимающем отображении===

'''Def''': Пусть на метрическом пространстве <tex>(M, \rho)</tex> определён оператор <tex>A: M \to M</tex>. Он называется сжимающим на <tex>M</tex>, если <tex>\exists\alpha\in(0; 1)</tex> такой, что для <tex>{\forall}x,y \in M</tex> выполняется <tex>{\rho(Ax,Ay)\leqslant\alpha{\cdot}\rho(x,y)}</tex>.

'''Th''' (Банах): У сжимающего отображения существует единственная неподвижная точка <tex>\mathbb{}x^{*}: Ax^{*}=x^{*}</tex>.

===23. Дифференциал Фреше===

===24. Неравенство Лагранжа===

===25. Локальная теорема о неявном отображении===

===26. Теорема о локальной обратимости отображения===

===27. Локальная теорема о простой итерации===

===28. Локальная теорема о методе Ньютона-Канторовича===

===29. О проекторах Шаудера===

===30. Теорема Шаудера о неподвижной точке===

Функциональный анализ

2010-06-19T12:25:26Z

Ulyantsev: /* 22. Теорема Банаха о сжимающем отображении */

Здесь я постараюсь написать теоретический минимум по второй части курса функционального анализа.

Большая часть материала взята из Википедии, чтобы не перебивать формулы и все такое. Все остальное бралось из конспектов, лучший из них лежит на firun.ru

Если вы читаете это, самоуничтожьтесь.

Да, да, '''функциональный анализ''' — раздел математики, в котором изучаются бесконечномерные пространства (в основном пространства функций) и их отображения.

==В прошлых сериях==

*'''Метрическое пространство''' <tex>M</tex> есть множество точек с '''метрикой''' <tex>d \colon M \times M \to \mathbb{R}</tex>:
# <tex>d(x,\;y) \ge 0 ; d(x,\;y)=0\Leftrightarrow x=y</tex>.
# <tex>d(x,\;y)=d(y,\;x)</tex>.
# <tex>d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)</tex>.

*Метрическое пространство называется '''полным''', если любая фундаментальная последовательность в нём сходится к некоторому элементу этого пространства.

*'''Банаховым пространством''' называется нормированное линейное пространство полное по метрике, порождённой нормой.

*'''Пространство непрерывных функций''' — линейное нормированное пространство, элементами которого являются непрерывные на отрезке <tex>[a,b]</tex> функции (обычно обозначается <tex>{\mathrm C}[a,b]</tex>). Норма в этом пространстве определяется следующим образом: <tex>||x||_{{\mathbf C}[a,b]}=\max_{t\in [a,b]}|x(t)|</tex>

* '''Теорема Рисса — Фреше:''' Для любого непрерывного линейного функционала <tex>f</tex> на Гильбертовом пространстве <tex> H</tex> существует единственный вектор <tex>y \in H</tex> такой, что <tex>f(x)=(x,y)</tex> для любого <tex>x \in H</tex>. При этом норма линейного функционала <tex>f</tex> совпадает с нормой вектора <tex>y</tex>: <tex>\|f\|=\sup_{\|x\|=1} |f(x)|= \sqrt{(y,y)}</tex>. Теорема также означает, что пространство всех линейных ограниченных функционалов над <tex>H</tex> изоморофно пространству <tex>H</tex>.

*Теорема (Хан-Банах) о продолжении линейного функционала с сохранением мажоранты: любой линейный функционал <tex>f(x)</tex>, определённый на подпространстве <tex>L</tex> линейного пространства <tex>X</tex> и удовлетворяющий условию <tex>|f(x)| \leq p(x), \forall x \in L</tex>, где <tex>p(x)</tex> — некоторый положительно однородный функционал (определённый на всем пространстве <tex>X</tex>) то <tex>f(x)</tex> может быть продолжен на все пространство <tex>X</tex> с сохранением этого условия.

*Теорема (Хан-Банах) о непрерывном продолжении линейного функционала: всякий линейный функционал <tex>f(x)</tex>, определённый на линейном многообразии <tex>L</tex> линейного нормированного пространства <tex>X</tex>, можно продолжить на все пространство с сохранением нормы.

*Следствие: для любых двух различных точек линейного пространства существует линейный функционал, определённый на всем пространстве и такой, что его значения в этих точках различны.

* '''Ядром''' линейного отображения <tex>f\colon A\to B</tex> называются подмножество <tex>A</tex>, которое отображается в нуль: <tex>\mbox{Ker}\,f = \{ x\in A\mid f(x) = 0 \}</tex>. Ядро линейного отображения образует подпространство в линейном пространстве <tex>A</tex>.

*Пусть <tex>A</tex> — оператор, действующий в банаховом пространстве <tex>E</tex>. Число λ называется ''регулярным'' для оператора <tex>A</tex>, если оператор <tex>R(\lambda)=(A - \lambda I)^{-1}</tex>, называемый '''резольвентой''' оператора <tex>A</tex>, определён на всём <tex>E</tex> и непрерывен. Множество регулярных значений оператора <tex>A</tex> называется '''резольвентным множеством''' этого оператора, а дополнение резольвентного множества — '''спектром''' этого оператора.

==Билеты==
===1. Сопряженный оператор и его ограниченность===

Будем работать с <tex>E</tex>, как с банаховым пространством.

'''Def''': Пространство всех линейных функционалов на <tex>E</tex> образует линейное пространство (прошлый семестр).
Это пространство называется '''сопряжённым''' к <tex>E</tex>, оно обычно обозначается <tex>E^*</tex>.

'''Def''': Пусть <tex>A:E\to F</tex> — непрерывный линейный оператор действующий из банахова пространства <tex>E</tex> в банахово пространство <tex>F</tex>. И пусть <tex>E^*, F^*</tex> — сопряжённые пространства. Обозначим <tex>\forall x\in E, f\in F^* \langle Ax,f\rangle =f(Ax)</tex>. Если <tex>f</tex> — фиксировано, то <tex>\langle Ax,f \rangle </tex> — линейный непрерывный функционал в <tex>E, \langle Ax,f \rangle \in E^*</tex>. Таким образом, для <tex>\forall f\in F^*</tex> определён линейный непрерывный функционал из <tex>E^* </tex>, поэтому определён оператор <tex>A^*:F^*\to E^*</tex>, такой что <tex>\langle Ax,f \rangle=\langle x,A^*f \rangle</tex>.
<tex>A^*</tex> называется '''сопряжённым оператором'''.

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>. Тогда норма оператора <tex>A^*:F^*\to E^*</tex> совпадает с нормой <tex>A</tex>.

(оператор проектирования ??)

===2. Ортогональные дополнения Е и Е*===

'''Def''': Пусть <tex>S</tex> некоторое линейное множество. Тогда его '''ортогональное дополнение''' <tex>S^\perp = \{f \in E^* | f(x) = 0 \; \forall x \in S\}</tex>.

'''Th''': Имеют место соотношения: <tex>E^\perp = \{0\}</tex>; <tex>(E^*)^\perp = \{0\}</tex>.

(при доказательстве используем теорему Хана-Банаха)

===3. Ортогональное дополнение R(A)===

(Здесь можно написать красивый текст из конспекта про важность теорем и все такое)

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>, где <tex>E</tex> и <tex>F</tex> банаховы. Пусть также множество значений <tex>R(A)</tex> замкнуто в <tex>F</tex>. Тогда <tex>R(A) = (Ker(A^*))^\perp</tex>.

===4. Ортогональное дополнение R(A*)===

'''Th''': Пусть множество значений оператора <tex>A</tex> замкнуто: <tex>R(A) = Cl(R(A))</tex>. Тогда верно <tex>R(A^*) = Cl(R(A^*)) = (Ker(A))^\perp</tex>.

----

===5. Арифметика компактных операторов===

'''Def''': Линейный оператор <tex>A:E\to F</tex> называется '''компактным''', если он переводит любое ограниченное множество из <tex>E</tex> в относительно компактное множество в <tex>F</tex>.

Примером является оператор Фредгольма: <tex>\psi(s) = \int\limits_a^b\!K(s, t) \varphi(t)\, dt</tex>.

Установим несколько свойств:

'''Th''': Пусть операторы <tex>A, B:E\to E</tex> такие, что <tex>A</tex> компактен, а <tex>B</tex> ограничен. Тогда операторы <tex>AB</tex> и <tex>BA</tex> компактны.

===6. О компактности А*, сепарабельность R(A)===

===7. Базис Шаудера, лемма о координатном пространстве===

'''Def''': Система векторов <tex>\{e_n\}</tex> топологического векторного пространства <tex>E</tex> называется '''базисом Шаудера''', если каждый элемент <tex>f \in E</tex> разлагается в ''единственный'', сходящийся к <tex>f</tex> ряд по <tex>\{e_n\}</tex>: <tex>f= \sum_{i=1}^{\infty} f_i e_i</tex>, где <tex>f_i</tex> — числа, называемые коэффициентами разложения вектора <tex>f</tex> по базису <tex>\{e_n\}</tex>.

===8. Почти конечномерность компактного оператора===

----
Теперь походим вокруг альтернативы Фредгольма-Шаудера.

===9. О размерности Ker(I-A) компактного А===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор, <tex> H = I - A </tex>.
Тогда, <tex> dim (Ker H)< +\infty </tex>

'''Следствие''' Множество решений операторного уравнения <tex> Ax = \lambda x, \lambda \in \mathbb{R} </tex> конечномерно.

===10. Условие замкнутости R(A) на языке решений операторного уравнения===
'''Утв.''' Пусть <tex> A \in L(E, F) </tex> и <tex> \exists \alpha = const : \forall y \in R(A), y = A(x), \exists x \in E : ||x|| \le \alpha ||y|| </tex>. ''Тогда'', <tex> R(A) </tex> - замкнуто.

===11. О замкнутости R(I-A) компактного А===
'''Утв.''' Пусть оператор <tex> A </tex> - компактный. Тогда, <tex> R(I - A) </tex> - замкнуто.

===12. Лемма о Ker(I-A)*n компактного А===
'''Утв.''' Пусть оператор <tex>A</tex> - компактный, и <tex> k \in \mathbb{N}</tex>.
Тогда, <tex>Ker(I - A)^{k + 1} = Ker(I - A)^k</tex>

===13. Об условии справедливости равенства R(I-A)=Е===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор. Тогда,
<tex> R(I - A) = E \Leftrightarrow Ker(I - A) = \{0\}</tex>

===14. Альтернатива Фредгольма-Шаудера===
'''Th.''' (''Альтернатива Фредгольма-Шаудера'')

Пусть <tex> A : E \rightarrow E </tex> - компактный оператор, <tex>E - B</tex>-пространство.

Тогда, <tex> \forall \lambda \neq 0</tex> возможны только 2 случая:
# <tex> Ker(\lambda I - A) = \{0\} \Rightarrow \lambda \in \rho(A) </tex>
# <tex> Ker(\lambda I - A) \neq \{0\} \Rightarrow </tex> (уравнение <tex>(\lambda I - A)x = y</tex> разрешимо относительно <tex>x) \Leftrightarrow y \in (Ker(\lambda I^{*} - A^{*}))^{\bot}</tex>

===15. О спектре компактного оператора===

----
Теперь это называется Теорией Гильберта-Шмидта

===16. О вещественности спектра ограниченного самосопряженного оператора===
'''Утв.''' Пусть <tex> A </tex> - ограниченный и самосопряженный оператор. Тогда, <tex>\sigma(A) \subset \mathbb{R}</tex>

===17. О характеризации спектра и резольвентного множества ограниченного самосопряженного оператора===
'''Th.''' Пусть <tex> A </tex> - ограниченный и самосопряженный оператор. Тогда,

# <tex> \lambda \in \rho(A) \Leftrightarrow \exists m > 0 : \|(\lambda I - A)x\| \ge m \|x\| </tex>
# <tex> \lambda \in \sigma(A) \Leftrightarrow \exists \{x_n | \|x_n\| = 1\}</tex>, т.ч. <tex> lim_{n \rightarrow \infty}\|(\lambda I - A)x_n\| = 0 </tex>

===18. О числах m- и m+===

===19. Спектральный радиус ограниченного самосопряженного оператора===

===20. Теорема Гильберта-Шмидта===

===21. О диагонализации компактного самосопряженного оператора и разложении его резольвенты===

----
Элементы нелинейного функционального анализа.

===22. Теорема Банаха о сжимающем отображении===

'''Def''': Пусть на метрическом пространстве <tex>(M, \rho)</tex> определён оператор <tex>A: M \to M</tex>. Он называется сжимающим на <tex>M</tex>, если <tex>\exists\alpha\in(0; 1)</tex> такой, что для <tex>{\forall}x,y \in M</tex> выполняется <tex>{\rho(Ax,Ay)\leqslant\alpha{\cdot}\rho(x,y)}</tex>.

===23. Дифференциал Фреше===

===24. Неравенство Лагранжа===

===25. Локальная теорема о неявном отображении===

===26. Теорема о локальной обратимости отображения===

===27. Локальная теорема о простой итерации===

===28. Локальная теорема о методе Ньютона-Канторовича===

===29. О проекторах Шаудера===

===30. Теорема Шаудера о неподвижной точке===

Функциональный анализ

2010-06-19T12:25:06Z

Ulyantsev: /* 22. Теорема Банаха о сжимающем отображении */

Здесь я постараюсь написать теоретический минимум по второй части курса функционального анализа.

Большая часть материала взята из Википедии, чтобы не перебивать формулы и все такое. Все остальное бралось из конспектов, лучший из них лежит на firun.ru

Если вы читаете это, самоуничтожьтесь.

Да, да, '''функциональный анализ''' — раздел математики, в котором изучаются бесконечномерные пространства (в основном пространства функций) и их отображения.

==В прошлых сериях==

*'''Метрическое пространство''' <tex>M</tex> есть множество точек с '''метрикой''' <tex>d \colon M \times M \to \mathbb{R}</tex>:
# <tex>d(x,\;y) \ge 0 ; d(x,\;y)=0\Leftrightarrow x=y</tex>.
# <tex>d(x,\;y)=d(y,\;x)</tex>.
# <tex>d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)</tex>.

*Метрическое пространство называется '''полным''', если любая фундаментальная последовательность в нём сходится к некоторому элементу этого пространства.

*'''Банаховым пространством''' называется нормированное линейное пространство полное по метрике, порождённой нормой.

*'''Пространство непрерывных функций''' — линейное нормированное пространство, элементами которого являются непрерывные на отрезке <tex>[a,b]</tex> функции (обычно обозначается <tex>{\mathrm C}[a,b]</tex>). Норма в этом пространстве определяется следующим образом: <tex>||x||_{{\mathbf C}[a,b]}=\max_{t\in [a,b]}|x(t)|</tex>

* '''Теорема Рисса — Фреше:''' Для любого непрерывного линейного функционала <tex>f</tex> на Гильбертовом пространстве <tex> H</tex> существует единственный вектор <tex>y \in H</tex> такой, что <tex>f(x)=(x,y)</tex> для любого <tex>x \in H</tex>. При этом норма линейного функционала <tex>f</tex> совпадает с нормой вектора <tex>y</tex>: <tex>\|f\|=\sup_{\|x\|=1} |f(x)|= \sqrt{(y,y)}</tex>. Теорема также означает, что пространство всех линейных ограниченных функционалов над <tex>H</tex> изоморофно пространству <tex>H</tex>.

*Теорема (Хан-Банах) о продолжении линейного функционала с сохранением мажоранты: любой линейный функционал <tex>f(x)</tex>, определённый на подпространстве <tex>L</tex> линейного пространства <tex>X</tex> и удовлетворяющий условию <tex>|f(x)| \leq p(x), \forall x \in L</tex>, где <tex>p(x)</tex> — некоторый положительно однородный функционал (определённый на всем пространстве <tex>X</tex>) то <tex>f(x)</tex> может быть продолжен на все пространство <tex>X</tex> с сохранением этого условия.

*Теорема (Хан-Банах) о непрерывном продолжении линейного функционала: всякий линейный функционал <tex>f(x)</tex>, определённый на линейном многообразии <tex>L</tex> линейного нормированного пространства <tex>X</tex>, можно продолжить на все пространство с сохранением нормы.

*Следствие: для любых двух различных точек линейного пространства существует линейный функционал, определённый на всем пространстве и такой, что его значения в этих точках различны.

* '''Ядром''' линейного отображения <tex>f\colon A\to B</tex> называются подмножество <tex>A</tex>, которое отображается в нуль: <tex>\mbox{Ker}\,f = \{ x\in A\mid f(x) = 0 \}</tex>. Ядро линейного отображения образует подпространство в линейном пространстве <tex>A</tex>.

*Пусть <tex>A</tex> — оператор, действующий в банаховом пространстве <tex>E</tex>. Число λ называется ''регулярным'' для оператора <tex>A</tex>, если оператор <tex>R(\lambda)=(A - \lambda I)^{-1}</tex>, называемый '''резольвентой''' оператора <tex>A</tex>, определён на всём <tex>E</tex> и непрерывен. Множество регулярных значений оператора <tex>A</tex> называется '''резольвентным множеством''' этого оператора, а дополнение резольвентного множества — '''спектром''' этого оператора.

==Билеты==
===1. Сопряженный оператор и его ограниченность===

Будем работать с <tex>E</tex>, как с банаховым пространством.

'''Def''': Пространство всех линейных функционалов на <tex>E</tex> образует линейное пространство (прошлый семестр).
Это пространство называется '''сопряжённым''' к <tex>E</tex>, оно обычно обозначается <tex>E^*</tex>.

'''Def''': Пусть <tex>A:E\to F</tex> — непрерывный линейный оператор действующий из банахова пространства <tex>E</tex> в банахово пространство <tex>F</tex>. И пусть <tex>E^*, F^*</tex> — сопряжённые пространства. Обозначим <tex>\forall x\in E, f\in F^* \langle Ax,f\rangle =f(Ax)</tex>. Если <tex>f</tex> — фиксировано, то <tex>\langle Ax,f \rangle </tex> — линейный непрерывный функционал в <tex>E, \langle Ax,f \rangle \in E^*</tex>. Таким образом, для <tex>\forall f\in F^*</tex> определён линейный непрерывный функционал из <tex>E^* </tex>, поэтому определён оператор <tex>A^*:F^*\to E^*</tex>, такой что <tex>\langle Ax,f \rangle=\langle x,A^*f \rangle</tex>.
<tex>A^*</tex> называется '''сопряжённым оператором'''.

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>. Тогда норма оператора <tex>A^*:F^*\to E^*</tex> совпадает с нормой <tex>A</tex>.

(оператор проектирования ??)

===2. Ортогональные дополнения Е и Е*===

'''Def''': Пусть <tex>S</tex> некоторое линейное множество. Тогда его '''ортогональное дополнение''' <tex>S^\perp = \{f \in E^* | f(x) = 0 \; \forall x \in S\}</tex>.

'''Th''': Имеют место соотношения: <tex>E^\perp = \{0\}</tex>; <tex>(E^*)^\perp = \{0\}</tex>.

(при доказательстве используем теорему Хана-Банаха)

===3. Ортогональное дополнение R(A)===

(Здесь можно написать красивый текст из конспекта про важность теорем и все такое)

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>, где <tex>E</tex> и <tex>F</tex> банаховы. Пусть также множество значений <tex>R(A)</tex> замкнуто в <tex>F</tex>. Тогда <tex>R(A) = (Ker(A^*))^\perp</tex>.

===4. Ортогональное дополнение R(A*)===

'''Th''': Пусть множество значений оператора <tex>A</tex> замкнуто: <tex>R(A) = Cl(R(A))</tex>. Тогда верно <tex>R(A^*) = Cl(R(A^*)) = (Ker(A))^\perp</tex>.

----

===5. Арифметика компактных операторов===

'''Def''': Линейный оператор <tex>A:E\to F</tex> называется '''компактным''', если он переводит любое ограниченное множество из <tex>E</tex> в относительно компактное множество в <tex>F</tex>.

Примером является оператор Фредгольма: <tex>\psi(s) = \int\limits_a^b\!K(s, t) \varphi(t)\, dt</tex>.

Установим несколько свойств:

'''Th''': Пусть операторы <tex>A, B:E\to E</tex> такие, что <tex>A</tex> компактен, а <tex>B</tex> ограничен. Тогда операторы <tex>AB</tex> и <tex>BA</tex> компактны.

===6. О компактности А*, сепарабельность R(A)===

===7. Базис Шаудера, лемма о координатном пространстве===

'''Def''': Система векторов <tex>\{e_n\}</tex> топологического векторного пространства <tex>E</tex> называется '''базисом Шаудера''', если каждый элемент <tex>f \in E</tex> разлагается в ''единственный'', сходящийся к <tex>f</tex> ряд по <tex>\{e_n\}</tex>: <tex>f= \sum_{i=1}^{\infty} f_i e_i</tex>, где <tex>f_i</tex> — числа, называемые коэффициентами разложения вектора <tex>f</tex> по базису <tex>\{e_n\}</tex>.

===8. Почти конечномерность компактного оператора===

----
Теперь походим вокруг альтернативы Фредгольма-Шаудера.

===9. О размерности Ker(I-A) компактного А===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор, <tex> H = I - A </tex>.
Тогда, <tex> dim (Ker H)< +\infty </tex>

'''Следствие''' Множество решений операторного уравнения <tex> Ax = \lambda x, \lambda \in \mathbb{R} </tex> конечномерно.

===10. Условие замкнутости R(A) на языке решений операторного уравнения===
'''Утв.''' Пусть <tex> A \in L(E, F) </tex> и <tex> \exists \alpha = const : \forall y \in R(A), y = A(x), \exists x \in E : ||x|| \le \alpha ||y|| </tex>. ''Тогда'', <tex> R(A) </tex> - замкнуто.

===11. О замкнутости R(I-A) компактного А===
'''Утв.''' Пусть оператор <tex> A </tex> - компактный. Тогда, <tex> R(I - A) </tex> - замкнуто.

===12. Лемма о Ker(I-A)*n компактного А===
'''Утв.''' Пусть оператор <tex>A</tex> - компактный, и <tex> k \in \mathbb{N}</tex>.
Тогда, <tex>Ker(I - A)^{k + 1} = Ker(I - A)^k</tex>

===13. Об условии справедливости равенства R(I-A)=Е===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор. Тогда,
<tex> R(I - A) = E \Leftrightarrow Ker(I - A) = \{0\}</tex>

===14. Альтернатива Фредгольма-Шаудера===
'''Th.''' (''Альтернатива Фредгольма-Шаудера'')

Пусть <tex> A : E \rightarrow E </tex> - компактный оператор, <tex>E - B</tex>-пространство.

Тогда, <tex> \forall \lambda \neq 0</tex> возможны только 2 случая:
# <tex> Ker(\lambda I - A) = \{0\} \Rightarrow \lambda \in \rho(A) </tex>
# <tex> Ker(\lambda I - A) \neq \{0\} \Rightarrow </tex> (уравнение <tex>(\lambda I - A)x = y</tex> разрешимо относительно <tex>x) \Leftrightarrow y \in (Ker(\lambda I^{*} - A^{*}))^{\bot}</tex>

===15. О спектре компактного оператора===

----
Теперь это называется Теорией Гильберта-Шмидта

===16. О вещественности спектра ограниченного самосопряженного оператора===
'''Утв.''' Пусть <tex> A </tex> - ограниченный и самосопряженный оператор. Тогда, <tex>\sigma(A) \subset \mathbb{R}</tex>

===17. О характеризации спектра и резольвентного множества ограниченного самосопряженного оператора===
'''Th.''' Пусть <tex> A </tex> - ограниченный и самосопряженный оператор. Тогда,

# <tex> \lambda \in \rho(A) \Leftrightarrow \exists m > 0 : ||(\lambda I - A)x|| \ge m ||x|| </tex>
# <tex> \lambda \in \sigma(A) \Leftrightarrow \exists \{x_n | ||x_n|| = 1\}</tex>, т.ч. <tex> lim_{n \rightarrow \infty}||(\lambda I - A)x_n|| = 0 </tex>

===18. О числах m- и m+===

===19. Спектральный радиус ограниченного самосопряженного оператора===

===20. Теорема Гильберта-Шмидта===

===21. О диагонализации компактного самосопряженного оператора и разложении его резольвенты===

----
Элементы нелинейного функционального анализа.

===22. Теорема Банаха о сжимающем отображении===

'''Def''': Пусть на метрическом пространстве <tex>(M, \rho)</tex> определён оператор <tex>A: M \to M</tex>. Он называется сжимающим на <tex>M</tex>, если <tex>\exists\alpha\in(0; 1)</tex> такой, что для <tex>{\forall}x,y \in M<\tex> выполняется <tex>{\rho(Ax,Ay)\leqslant\alpha{\cdot}\rho(x,y)}</tex>.

===23. Дифференциал Фреше===

===24. Неравенство Лагранжа===

===25. Локальная теорема о неявном отображении===

===26. Теорема о локальной обратимости отображения===

===27. Локальная теорема о простой итерации===

===28. Локальная теорема о методе Ньютона-Канторовича===

===29. О проекторах Шаудера===

===30. Теорема Шаудера о неподвижной точке===

Функциональный анализ

2010-06-19T12:12:01Z

Ulyantsev: /* 21. О диагонализации компактного самосопряженного оператора и разложении его резольвенты */

Здесь я постараюсь написать теоретический минимум по второй части курса функционального анализа.

Большая часть материала взята из Википедии, чтобы не перебивать формулы и все такое. Все остальное бралось из конспектов, лучший из них лежит на firun.ru

Если вы читаете это, самоуничтожьтесь.

Да, да, '''функциональный анализ''' — раздел математики, в котором изучаются бесконечномерные пространства (в основном пространства функций) и их отображения.

==В прошлых сериях==

*'''Метрическое пространство''' <tex>M</tex> есть множество точек с '''метрикой''' <tex>d \colon M \times M \to \mathbb{R}</tex>:
# <tex>d(x,\;y) \ge 0 ; d(x,\;y)=0\Leftrightarrow x=y</tex>.
# <tex>d(x,\;y)=d(y,\;x)</tex>.
# <tex>d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)</tex>.

*Метрическое пространство называется '''полным''', если любая фундаментальная последовательность в нём сходится к некоторому элементу этого пространства.

*'''Банаховым пространством''' называется нормированное линейное пространство полное по метрике, порождённой нормой.

*'''Пространство непрерывных функций''' — линейное нормированное пространство, элементами которого являются непрерывные на отрезке <tex>[a,b]</tex> функции (обычно обозначается <tex>{\mathrm C}[a,b]</tex>). Норма в этом пространстве определяется следующим образом: <tex>||x||_{{\mathbf C}[a,b]}=\max_{t\in [a,b]}|x(t)|</tex>

* '''Теорема Рисса — Фреше:''' Для любого непрерывного линейного функционала <tex>f</tex> на Гильбертовом пространстве <tex> H</tex> существует единственный вектор <tex>y \in H</tex> такой, что <tex>f(x)=(x,y)</tex> для любого <tex>x \in H</tex>. При этом норма линейного функционала <tex>f</tex> совпадает с нормой вектора <tex>y</tex>: <tex>\|f\|=\sup_{\|x\|=1} |f(x)|= \sqrt{(y,y)}</tex>. Теорема также означает, что пространство всех линейных ограниченных функционалов над <tex>H</tex> изоморофно пространству <tex>H</tex>.

*Теорема (Хан-Банах) о продолжении линейного функционала с сохранением мажоранты: любой линейный функционал <tex>f(x)</tex>, определённый на подпространстве <tex>L</tex> линейного пространства <tex>X</tex> и удовлетворяющий условию <tex>|f(x)| \leq p(x), \forall x \in L</tex>, где <tex>p(x)</tex> — некоторый положительно однородный функционал (определённый на всем пространстве <tex>X</tex>) то <tex>f(x)</tex> может быть продолжен на все пространство <tex>X</tex> с сохранением этого условия.

*Теорема (Хан-Банах) о непрерывном продолжении линейного функционала: всякий линейный функционал <tex>f(x)</tex>, определённый на линейном многообразии <tex>L</tex> линейного нормированного пространства <tex>X</tex>, можно продолжить на все пространство с сохранением нормы.

*Следствие: для любых двух различных точек линейного пространства существует линейный функционал, определённый на всем пространстве и такой, что его значения в этих точках различны.

* '''Ядром''' линейного отображения <tex>f\colon A\to B</tex> называются подмножество <tex>A</tex>, которое отображается в нуль: <tex>\mbox{Ker}\,f = \{ x\in A\mid f(x) = 0 \}</tex>. Ядро линейного отображения образует подпространство в линейном пространстве <tex>A</tex>.

*Пусть <tex>A</tex> — оператор, действующий в банаховом пространстве <tex>E</tex>. Число λ называется ''регулярным'' для оператора <tex>A</tex>, если оператор <tex>R(\lambda)=(A - \lambda I)^{-1}</tex>, называемый '''резольвентой''' оператора <tex>A</tex>, определён на всём <tex>E</tex> и непрерывен. Множество регулярных значений оператора <tex>A</tex> называется '''резольвентным множеством''' этого оператора, а дополнение резольвентного множества — '''спектром''' этого оператора.

==Билеты==
===1. Сопряженный оператор и его ограниченность===

Будем работать с <tex>E</tex>, как с банаховым пространством.

'''Def''': Пространство всех линейных функционалов на <tex>E</tex> образует линейное пространство (прошлый семестр).
Это пространство называется '''сопряжённым''' к <tex>E</tex>, оно обычно обозначается <tex>E^*</tex>.

'''Def''': Пусть <tex>A:E\to F</tex> — непрерывный линейный оператор действующий из банахова пространства <tex>E</tex> в банахово пространство <tex>F</tex>. И пусть <tex>E^*, F^*</tex> — сопряжённые пространства. Обозначим <tex>\forall x\in E, f\in F^* \langle Ax,f\rangle =f(Ax)</tex>. Если <tex>f</tex> — фиксировано, то <tex>\langle Ax,f \rangle </tex> — линейный непрерывный функционал в <tex>E, \langle Ax,f \rangle \in E^*</tex>. Таким образом, для <tex>\forall f\in F^*</tex> определён линейный непрерывный функционал из <tex>E^* </tex>, поэтому определён оператор <tex>A^*:F^*\to E^*</tex>, такой что <tex>\langle Ax,f \rangle=\langle x,A^*f \rangle</tex>.
<tex>A^*</tex> называется '''сопряжённым оператором'''.

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>. Тогда норма оператора <tex>A^*:F^*\to E^*</tex> совпадает с нормой <tex>A</tex>.

(оператор проектирования ??)

===2. Ортогональные дополнения Е и Е*===

'''Def''': Пусть <tex>S</tex> некоторое линейное множество. Тогда его '''ортогональное дополнение''' <tex>S^\perp = \{f \in E^* | f(x) = 0 \; \forall x \in S\}</tex>.

'''Th''': Имеют место соотношения: <tex>E^\perp = \{0\}</tex>; <tex>(E^*)^\perp = \{0\}</tex>.

(при доказательстве используем теорему Хана-Банаха)

===3. Ортогональное дополнение R(A)===

(Здесь можно написать красивый текст из конспекта про важность теорем и все такое)

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>, где <tex>E</tex> и <tex>F</tex> банаховы. Пусть также множество значений <tex>R(A)</tex> замкнуто в <tex>F</tex>. Тогда <tex>R(A) = (Ker(A^*))^\perp</tex>.

===4. Ортогональное дополнение R(A*)===

'''Th''': Пусть множество значений оператора <tex>A</tex> замкнуто: <tex>R(A) = Cl(R(A))</tex>. Тогда верно <tex>R(A^*) = Cl(R(A^*)) = (Ker(A))^\perp</tex>.

----

===5. Арифметика компактных операторов===

'''Def''': Линейный оператор <tex>A:E\to F</tex> называется '''компактным''', если он переводит любое ограниченное множество из <tex>E</tex> в относительно компактное множество в <tex>F</tex>.

Примером является оператор Фредгольма: <tex>\psi(s) = \int\limits_a^b\!K(s, t) \varphi(t)\, dt</tex>.

Установим несколько свойств:

'''Th''': Пусть операторы <tex>A, B:E\to E</tex> такие, что <tex>A</tex> компактен, а <tex>B</tex> ограничен. Тогда операторы <tex>AB</tex> и <tex>BA</tex> компактны.

===6. О компактности А*, сепарабельность R(A)===

===7. Базис Шаудера, лемма о координатном пространстве===

'''Def''': Система векторов <tex>\{e_n\}</tex> топологического векторного пространства <tex>E</tex> называется '''базисом Шаудера''', если каждый элемент <tex>f \in E</tex> разлагается в ''единственный'', сходящийся к <tex>f</tex> ряд по <tex>\{e_n\}</tex>: <tex>f= \sum_{i=1}^{\infty} f_i e_i</tex>, где <tex>f_i</tex> — числа, называемые коэффициентами разложения вектора <tex>f</tex> по базису <tex>\{e_n\}</tex>.

===8. Почти конечномерность компактного оператора===

----
Теперь походим вокруг альтернативы Фредгольма-Шаудера.

===9. О размерности Ker(I-A) компактного А===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор, <tex> H = I - A </tex>.
Тогда, <tex> dim (Ker H)< +\infty </tex>

'''Следствие''' Множество решений операторного уравнения <tex> Ax = \lambda x, \lambda \in \mathbb{R} </tex> конечномерно.

===10. Условие замкнутости R(A) на языке решений операторного уравнения===
'''Утв.''' Пусть <tex> A \in L(E, F) </tex> и <tex> \exists \alpha = const : \forall y \in R(A), y = A(x), \exists x \in E : ||x|| \le \alpha ||y|| </tex>. ''Тогда'', <tex> R(A) </tex> - замкнуто.

===11. О замкнутости R(I-A) компактного А===
'''Утв.''' Пусть оператор <tex> A </tex> - компактный. Тогда, <tex> R(I - A) </tex> - замкнуто.

===12. Лемма о Ker(I-A)*n компактного А===
'''Утв.''' Пусть оператор <tex>A</tex> - компактный, и <tex> k \in \mathbb{N}</tex>.
Тогда, <tex>Ker(I - A)^{k + 1} = Ker(I - A)^k</tex>

===13. Об условии справедливости равенства R(I-A)=Е===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор. Тогда,
<tex> R(I - A) = E \Leftrightarrow Ker(I - A) = \{0\}</tex>

===14. Альтернатива Фредгольма-Шаудера===

===15. О спектре компактного оператора===

----
Теперь это называется Теорией Гильберта-Шмидта

===16. О вещественности спектра ограниченного самосопряженного оператора===

===17. О характеризации спектра и резольвентного множества ограниченного самосопряженного оператора===

===18. О числах m- и m+===

===19. Спектральный радиус ограниченного самосопряженного оператора===

===20. Теорема Гильберта-Шмидта===

===21. О диагонализации компактного самосопряженного оператора и разложении его резольвенты===

----
Элементы нелинейного функционального анализа.

===22. Теорема Банаха о сжимающем отображении===

===23. Дифференциал Фреше===

===24. Неравенство Лагранжа===

===25. Локальная теорема о неявном отображении===

===26. Теорема о локальной обратимости отображения===

===27. Локальная теорема о простой итерации===

===28. Локальная теорема о методе Ньютона-Канторовича===

===29. О проекторах Шаудера===

===30. Теорема Шаудера о неподвижной точке===

Функциональный анализ

2010-06-19T12:10:38Z

Ulyantsev: /* Билеты */

Здесь я постараюсь написать теоретический минимум по второй части курса функционального анализа.

Большая часть материала взята из Википедии, чтобы не перебивать формулы и все такое. Все остальное бралось из конспектов, лучший из них лежит на firun.ru

Если вы читаете это, самоуничтожьтесь.

Да, да, '''функциональный анализ''' — раздел математики, в котором изучаются бесконечномерные пространства (в основном пространства функций) и их отображения.

==В прошлых сериях==

*'''Метрическое пространство''' <tex>M</tex> есть множество точек с '''метрикой''' <tex>d \colon M \times M \to \mathbb{R}</tex>:
# <tex>d(x,\;y) \ge 0 ; d(x,\;y)=0\Leftrightarrow x=y</tex>.
# <tex>d(x,\;y)=d(y,\;x)</tex>.
# <tex>d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)</tex>.

*Метрическое пространство называется '''полным''', если любая фундаментальная последовательность в нём сходится к некоторому элементу этого пространства.

*'''Банаховым пространством''' называется нормированное линейное пространство полное по метрике, порождённой нормой.

*'''Пространство непрерывных функций''' — линейное нормированное пространство, элементами которого являются непрерывные на отрезке <tex>[a,b]</tex> функции (обычно обозначается <tex>{\mathrm C}[a,b]</tex>). Норма в этом пространстве определяется следующим образом: <tex>||x||_{{\mathbf C}[a,b]}=\max_{t\in [a,b]}|x(t)|</tex>

* '''Теорема Рисса — Фреше:''' Для любого непрерывного линейного функционала <tex>f</tex> на Гильбертовом пространстве <tex> H</tex> существует единственный вектор <tex>y \in H</tex> такой, что <tex>f(x)=(x,y)</tex> для любого <tex>x \in H</tex>. При этом норма линейного функционала <tex>f</tex> совпадает с нормой вектора <tex>y</tex>: <tex>\|f\|=\sup_{\|x\|=1} |f(x)|= \sqrt{(y,y)}</tex>. Теорема также означает, что пространство всех линейных ограниченных функционалов над <tex>H</tex> изоморофно пространству <tex>H</tex>.

*Теорема (Хан-Банах) о продолжении линейного функционала с сохранением мажоранты: любой линейный функционал <tex>f(x)</tex>, определённый на подпространстве <tex>L</tex> линейного пространства <tex>X</tex> и удовлетворяющий условию <tex>|f(x)| \leq p(x), \forall x \in L</tex>, где <tex>p(x)</tex> — некоторый положительно однородный функционал (определённый на всем пространстве <tex>X</tex>) то <tex>f(x)</tex> может быть продолжен на все пространство <tex>X</tex> с сохранением этого условия.

*Теорема (Хан-Банах) о непрерывном продолжении линейного функционала: всякий линейный функционал <tex>f(x)</tex>, определённый на линейном многообразии <tex>L</tex> линейного нормированного пространства <tex>X</tex>, можно продолжить на все пространство с сохранением нормы.

*Следствие: для любых двух различных точек линейного пространства существует линейный функционал, определённый на всем пространстве и такой, что его значения в этих точках различны.

* '''Ядром''' линейного отображения <tex>f\colon A\to B</tex> называются подмножество <tex>A</tex>, которое отображается в нуль: <tex>\mbox{Ker}\,f = \{ x\in A\mid f(x) = 0 \}</tex>. Ядро линейного отображения образует подпространство в линейном пространстве <tex>A</tex>.

*Пусть <tex>A</tex> — оператор, действующий в банаховом пространстве <tex>E</tex>. Число λ называется ''регулярным'' для оператора <tex>A</tex>, если оператор <tex>R(\lambda)=(A - \lambda I)^{-1}</tex>, называемый '''резольвентой''' оператора <tex>A</tex>, определён на всём <tex>E</tex> и непрерывен. Множество регулярных значений оператора <tex>A</tex> называется '''резольвентным множеством''' этого оператора, а дополнение резольвентного множества — '''спектром''' этого оператора.

==Билеты==
===1. Сопряженный оператор и его ограниченность===

Будем работать с <tex>E</tex>, как с банаховым пространством.

'''Def''': Пространство всех линейных функционалов на <tex>E</tex> образует линейное пространство (прошлый семестр).
Это пространство называется '''сопряжённым''' к <tex>E</tex>, оно обычно обозначается <tex>E^*</tex>.

'''Def''': Пусть <tex>A:E\to F</tex> — непрерывный линейный оператор действующий из банахова пространства <tex>E</tex> в банахово пространство <tex>F</tex>. И пусть <tex>E^*, F^*</tex> — сопряжённые пространства. Обозначим <tex>\forall x\in E, f\in F^* \langle Ax,f\rangle =f(Ax)</tex>. Если <tex>f</tex> — фиксировано, то <tex>\langle Ax,f \rangle </tex> — линейный непрерывный функционал в <tex>E, \langle Ax,f \rangle \in E^*</tex>. Таким образом, для <tex>\forall f\in F^*</tex> определён линейный непрерывный функционал из <tex>E^* </tex>, поэтому определён оператор <tex>A^*:F^*\to E^*</tex>, такой что <tex>\langle Ax,f \rangle=\langle x,A^*f \rangle</tex>.
<tex>A^*</tex> называется '''сопряжённым оператором'''.

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>. Тогда норма оператора <tex>A^*:F^*\to E^*</tex> совпадает с нормой <tex>A</tex>.

(оператор проектирования ??)

===2. Ортогональные дополнения Е и Е*===

'''Def''': Пусть <tex>S</tex> некоторое линейное множество. Тогда его '''ортогональное дополнение''' <tex>S^\perp = \{f \in E^* | f(x) = 0 \; \forall x \in S\}</tex>.

'''Th''': Имеют место соотношения: <tex>E^\perp = \{0\}</tex>; <tex>(E^*)^\perp = \{0\}</tex>.

(при доказательстве используем теорему Хана-Банаха)

===3. Ортогональное дополнение R(A)===

(Здесь можно написать красивый текст из конспекта про важность теорем и все такое)

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>, где <tex>E</tex> и <tex>F</tex> банаховы. Пусть также множество значений <tex>R(A)</tex> замкнуто в <tex>F</tex>. Тогда <tex>R(A) = (Ker(A^*))^\perp</tex>.

===4. Ортогональное дополнение R(A*)===

'''Th''': Пусть множество значений оператора <tex>A</tex> замкнуто: <tex>R(A) = Cl(R(A))</tex>. Тогда верно <tex>R(A^*) = Cl(R(A^*)) = (Ker(A))^\perp</tex>.

----

===5. Арифметика компактных операторов===

'''Def''': Линейный оператор <tex>A:E\to F</tex> называется '''компактным''', если он переводит любое ограниченное множество из <tex>E</tex> в относительно компактное множество в <tex>F</tex>.

Примером является оператор Фредгольма: <tex>\psi(s) = \int\limits_a^b\!K(s, t) \varphi(t)\, dt</tex>.

Установим несколько свойств:

'''Th''': Пусть операторы <tex>A, B:E\to E</tex> такие, что <tex>A</tex> компактен, а <tex>B</tex> ограничен. Тогда операторы <tex>AB</tex> и <tex>BA</tex> компактны.

===6. О компактности А*, сепарабельность R(A)===

===7. Базис Шаудера, лемма о координатном пространстве===

'''Def''': Система векторов <tex>\{e_n\}</tex> топологического векторного пространства <tex>E</tex> называется '''базисом Шаудера''', если каждый элемент <tex>f \in E</tex> разлагается в ''единственный'', сходящийся к <tex>f</tex> ряд по <tex>\{e_n\}</tex>: <tex>f= \sum_{i=1}^{\infty} f_i e_i</tex>, где <tex>f_i</tex> — числа, называемые коэффициентами разложения вектора <tex>f</tex> по базису <tex>\{e_n\}</tex>.

===8. Почти конечномерность компактного оператора===

----
Теперь походим вокруг альтернативы Фредгольма-Шаудера.

===9. О размерности Ker(I-A) компактного А===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор, <tex> H = I - A </tex>.
Тогда, <tex> dim (Ker H)< +\infty </tex>

'''Следствие''' Множество решений операторного уравнения <tex> Ax = \lambda x, \lambda \in \mathbb{R} </tex> конечномерно.

===10. Условие замкнутости R(A) на языке решений операторного уравнения===
'''Утв.''' Пусть <tex> A \in L(E, F) </tex> и <tex> \exists \alpha = const : \forall y \in R(A), y = A(x), \exists x \in E : ||x|| \le \alpha ||y|| </tex>. ''Тогда'', <tex> R(A) </tex> - замкнуто.

===11. О замкнутости R(I-A) компактного А===
'''Утв.''' Пусть оператор <tex> A </tex> - компактный. Тогда, <tex> R(I - A) </tex> - замкнуто.

===12. Лемма о Ker(I-A)*n компактного А===
'''Утв.''' Пусть оператор <tex>A</tex> - компактный, и <tex> k \in \mathbb{N}</tex>.
Тогда, <tex>Ker(I - A)^{k + 1} = Ker(I - A)^k</tex>

===13. Об условии справедливости равенства R(I-A)=Е===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор. Тогда,
<tex> R(I - A) = E \Leftrightarrow Ker(I - A) = \{0\}</tex>

===14. Альтернатива Фредгольма-Шаудера===

===15. О спектре компактного оператора===

----
Теперь это называется Теорией Гильберта-Шмидта

===16. О вещественности спектра ограниченного самосопряженного оператора===

===17. О характеризации спектра и резольвентного множества ограниченного самосопряженного оператора===

===18. О числах m- и m+===

===19. Спектральный радиус ограниченного самосопряженного оператора===

===20. Теорема Гильберта-Шмидта===

===21. О диагонализации компактного самосопряженного оператора и разложении его резольвенты===

===22. Теорема Банаха о сжимающем отображении===

===23. Дифференциал Фреше===

===24. Неравенство Лагранжа===

===25. Локальная теорема о неявном отображении===

===26. Теорема о локальной обратимости отображения===

===27. Локальная теорема о простой итерации===

===28. Локальная теорема о методе Ньютона-Канторовича===

===29. О проекторах Шаудера===

===30. Теорема Шаудера о неподвижной точке===

Функциональный анализ

2010-06-19T11:53:11Z

Ulyantsev: /* Билеты */

Здесь я постараюсь написать теоретический минимум по второй части курса функционального анализа.

Большая часть материала взята из Википедии, чтобы не перебивать формулы и все такое. Все остальное бралось из конспектов, лучший из них лежит на firun.ru

Если вы читаете это, самоуничтожьтесь.

Да, да, '''функциональный анализ''' — раздел математики, в котором изучаются бесконечномерные пространства (в основном пространства функций) и их отображения.

==В прошлых сериях==

*'''Метрическое пространство''' <tex>M</tex> есть множество точек с '''метрикой''' <tex>d \colon M \times M \to \mathbb{R}</tex>:
# <tex>d(x,\;y) \ge 0 ; d(x,\;y)=0\Leftrightarrow x=y</tex>.
# <tex>d(x,\;y)=d(y,\;x)</tex>.
# <tex>d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)</tex>.

*Метрическое пространство называется '''полным''', если любая фундаментальная последовательность в нём сходится к некоторому элементу этого пространства.

*'''Банаховым пространством''' называется нормированное линейное пространство полное по метрике, порождённой нормой.

*'''Пространство непрерывных функций''' — линейное нормированное пространство, элементами которого являются непрерывные на отрезке <tex>[a,b]</tex> функции (обычно обозначается <tex>{\mathrm C}[a,b]</tex>). Норма в этом пространстве определяется следующим образом: <tex>||x||_{{\mathbf C}[a,b]}=\max_{t\in [a,b]}|x(t)|</tex>

* '''Теорема Рисса — Фреше:''' Для любого непрерывного линейного функционала <tex>f</tex> на Гильбертовом пространстве <tex> H</tex> существует единственный вектор <tex>y \in H</tex> такой, что <tex>f(x)=(x,y)</tex> для любого <tex>x \in H</tex>. При этом норма линейного функционала <tex>f</tex> совпадает с нормой вектора <tex>y</tex>: <tex>\|f\|=\sup_{\|x\|=1} |f(x)|= \sqrt{(y,y)}</tex>. Теорема также означает, что пространство всех линейных ограниченных функционалов над <tex>H</tex> изоморофно пространству <tex>H</tex>.

*Теорема (Хан-Банах) о продолжении линейного функционала с сохранением мажоранты: любой линейный функционал <tex>f(x)</tex>, определённый на подпространстве <tex>L</tex> линейного пространства <tex>X</tex> и удовлетворяющий условию <tex>|f(x)| \leq p(x), \forall x \in L</tex>, где <tex>p(x)</tex> — некоторый положительно однородный функционал (определённый на всем пространстве <tex>X</tex>) то <tex>f(x)</tex> может быть продолжен на все пространство <tex>X</tex> с сохранением этого условия.

*Теорема (Хан-Банах) о непрерывном продолжении линейного функционала: всякий линейный функционал <tex>f(x)</tex>, определённый на линейном многообразии <tex>L</tex> линейного нормированного пространства <tex>X</tex>, можно продолжить на все пространство с сохранением нормы.

*Следствие: для любых двух различных точек линейного пространства существует линейный функционал, определённый на всем пространстве и такой, что его значения в этих точках различны.

* '''Ядром''' линейного отображения <tex>f\colon A\to B</tex> называются подмножество <tex>A</tex>, которое отображается в нуль: <tex>\mbox{Ker}\,f = \{ x\in A\mid f(x) = 0 \}</tex>. Ядро линейного отображения образует подпространство в линейном пространстве <tex>A</tex>.

*Пусть <tex>A</tex> — оператор, действующий в банаховом пространстве <tex>E</tex>. Число λ называется ''регулярным'' для оператора <tex>A</tex>, если оператор <tex>R(\lambda)=(A - \lambda I)^{-1}</tex>, называемый '''резольвентой''' оператора <tex>A</tex>, определён на всём <tex>E</tex> и непрерывен. Множество регулярных значений оператора <tex>A</tex> называется '''резольвентным множеством''' этого оператора, а дополнение резольвентного множества — '''спектром''' этого оператора.

==Билеты==
===1. Сопряженный оператор и его ограниченность===

Будем работать с <tex>E</tex>, как с банаховым пространством.

'''Def''': Пространство всех линейных функционалов на <tex>E</tex> образует линейное пространство (прошлый семестр).
Это пространство называется '''сопряжённым''' к <tex>E</tex>, оно обычно обозначается <tex>E^*</tex>.

'''Def''': Пусть <tex>A:E\to F</tex> — непрерывный линейный оператор действующий из банахова пространства <tex>E</tex> в банахово пространство <tex>F</tex>. И пусть <tex>E^*, F^*</tex> — сопряжённые пространства. Обозначим <tex>\forall x\in E, f\in F^* \langle Ax,f\rangle =f(Ax)</tex>. Если <tex>f</tex> — фиксировано, то <tex>\langle Ax,f \rangle </tex> — линейный непрерывный функционал в <tex>E, \langle Ax,f \rangle \in E^*</tex>. Таким образом, для <tex>\forall f\in F^*</tex> определён линейный непрерывный функционал из <tex>E^* </tex>, поэтому определён оператор <tex>A^*:F^*\to E^*</tex>, такой что <tex>\langle Ax,f \rangle=\langle x,A^*f \rangle</tex>.
<tex>A^*</tex> называется '''сопряжённым оператором'''.

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>. Тогда норма оператора <tex>A^*:F^*\to E^*</tex> совпадает с нормой <tex>A</tex>.

(оператор проектирования ??)

===2. Ортогональные дополнения Е и Е*===

'''Def''': Пусть <tex>S</tex> некоторое линейное множество. Тогда его '''ортогональное дополнение''' <tex>S^\perp = \{f \in E^* | f(x) = 0 \; \forall x \in S\}</tex>.

'''Th''': Имеют место соотношения: <tex>E^\perp = \{0\}</tex>; <tex>(E^*)^\perp = \{0\}</tex>.

(при доказательстве используем теорему Хана-Банаха)

===3. Ортогональное дополнение R(A)===

(Здесь можно написать красивый текст из конспекта про важность теорем и все такое)

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>, где <tex>E</tex> и <tex>F</tex> банаховы. Пусть также множество значений <tex>R(A)</tex> замкнуто в <tex>F</tex>. Тогда <tex>R(A) = (Ker(A^*))^\perp</tex>.

===4. Ортогональное дополнение R(A*)===

'''Th''': Пусть множество значений оператора <tex>A</tex> замкнуто: <tex>R(A) = Cl(R(A))</tex>. Тогда верно <tex>R(A^*) = Cl(R(A^*)) = (Ker(A))^\perp</tex>.

----

===5. Арифметика компактных операторов===

'''Def''': Линейный оператор <tex>A:E\to F</tex> называется '''компактным''', если он переводит любое ограниченное множество из <tex>E</tex> в относительно компактное множество в <tex>F</tex>.

Примером является оператор Фредгольма: <tex>\psi(s) = \int\limits_a^b\!K(s, t) \varphi(t)\, dt</tex>.

Установим несколько свойств:

'''Th''': Пусть операторы <tex>A, B:E\to E</tex> такие, что <tex>A</tex> компактен, а <tex>B</tex> ограничен. Тогда операторы <tex>AB</tex> и <tex>BA</tex> компактны.

===6. О компактности А*, сепарабельность R(A)===

===7. Базис Шаудера, лемма о координатном пространстве===

'''Def''': Система векторов <tex>\{e_n\}</tex> топологического векторного пространства <tex>E</tex> называется '''базисом Шаудера''', если каждый элемент <tex>f \in E</tex> разлагается в ''единственный'', сходящийся к <tex>f</tex> ряд по <tex>\{e_n\}</tex>: <tex>f= \sum_{i=1}^{\infty} f_i e_i</tex>, где <tex>f_i</tex> — числа, называемые коэффициентами разложения вектора <tex>f</tex> по базису <tex>\{e_n\}</tex>.

===8. Почти конечномерность компактного оператора===

----
Теперь походим вокруг альтернативы Фредгольма-Шаудера.

===9. О размерности Ker(I-A) компактного А===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор, <tex> H = I - A </tex>.
Тогда, <tex> dim (Ker H)< +\infty </tex>

'''Следствие''' Множество решений операторного уравнения <tex> Ax = \lambda x, \lambda \in \mathbb{R} </tex> конечномерно.

===10. Условие замкнутости R(A) на языке решений операторного уравнения===

===11. О замкнутости R(I-A) компактного А===

===12. Лемма о Ker(I-A)*n компактного А===

===13. Об условии справедливости равенства R(I-A)=Е===

===14. Альтернатива Фредгольма-Шаудера===

===15. О спектре компактного оператора===

===16. О вещественности спектра ограниченного самосопряженного оператора===

===17. О характеризации спектра и резольвентного множества ограниченного самосопряженного оператора===

===18. О числах m- и m+===

===19. Спектральный радиус ограниченного самосопряженного оператора===

===20. Теорема Гильберта-Шмидта===

===21. О диагонализации компактного самосопряженного оператора и разложении его резольвенты===

===22. Теорема Банаха о сжимающем отображении===

===23. Дифференциал Фреше===

===24. Неравенство Лагранжа===

===25. Локальная теорема о неявном отображении===

===26. Теорема о локальной обратимости отображения===

===27. Локальная теорема о простой итерации===

===28. Локальная теорема о методе Ньютона-Канторовича===

===29. О проекторах Шаудера===

===30. Теорема Шаудера о неподвижной точке===

Функциональный анализ

2010-06-19T11:49:55Z

Ulyantsev: /* В прошлых сериях */

Здесь я постараюсь написать теоретический минимум по второй части курса функционального анализа.

Большая часть материала взята из Википедии, чтобы не перебивать формулы и все такое. Все остальное бралось из конспектов, лучший из них лежит на firun.ru

Если вы читаете это, самоуничтожьтесь.

Да, да, '''функциональный анализ''' — раздел математики, в котором изучаются бесконечномерные пространства (в основном пространства функций) и их отображения.

==В прошлых сериях==

*'''Метрическое пространство''' <tex>M</tex> есть множество точек с '''метрикой''' <tex>d \colon M \times M \to \mathbb{R}</tex>:
# <tex>d(x,\;y) \ge 0 ; d(x,\;y)=0\Leftrightarrow x=y</tex>.
# <tex>d(x,\;y)=d(y,\;x)</tex>.
# <tex>d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)</tex>.

*Метрическое пространство называется '''полным''', если любая фундаментальная последовательность в нём сходится к некоторому элементу этого пространства.

*'''Банаховым пространством''' называется нормированное линейное пространство полное по метрике, порождённой нормой.

*'''Пространство непрерывных функций''' — линейное нормированное пространство, элементами которого являются непрерывные на отрезке <tex>[a,b]</tex> функции (обычно обозначается <tex>{\mathrm C}[a,b]</tex>). Норма в этом пространстве определяется следующим образом: <tex>||x||_{{\mathbf C}[a,b]}=\max_{t\in [a,b]}|x(t)|</tex>

* '''Теорема Рисса — Фреше:''' Для любого непрерывного линейного функционала <tex>f</tex> на Гильбертовом пространстве <tex> H</tex> существует единственный вектор <tex>y \in H</tex> такой, что <tex>f(x)=(x,y)</tex> для любого <tex>x \in H</tex>. При этом норма линейного функционала <tex>f</tex> совпадает с нормой вектора <tex>y</tex>: <tex>\|f\|=\sup_{\|x\|=1} |f(x)|= \sqrt{(y,y)}</tex>. Теорема также означает, что пространство всех линейных ограниченных функционалов над <tex>H</tex> изоморофно пространству <tex>H</tex>.

*Теорема (Хан-Банах) о продолжении линейного функционала с сохранением мажоранты: любой линейный функционал <tex>f(x)</tex>, определённый на подпространстве <tex>L</tex> линейного пространства <tex>X</tex> и удовлетворяющий условию <tex>|f(x)| \leq p(x), \forall x \in L</tex>, где <tex>p(x)</tex> — некоторый положительно однородный функционал (определённый на всем пространстве <tex>X</tex>) то <tex>f(x)</tex> может быть продолжен на все пространство <tex>X</tex> с сохранением этого условия.

*Теорема (Хан-Банах) о непрерывном продолжении линейного функционала: всякий линейный функционал <tex>f(x)</tex>, определённый на линейном многообразии <tex>L</tex> линейного нормированного пространства <tex>X</tex>, можно продолжить на все пространство с сохранением нормы.

*Следствие: для любых двух различных точек линейного пространства существует линейный функционал, определённый на всем пространстве и такой, что его значения в этих точках различны.

* '''Ядром''' линейного отображения <tex>f\colon A\to B</tex> называются подмножество <tex>A</tex>, которое отображается в нуль: <tex>\mbox{Ker}\,f = \{ x\in A\mid f(x) = 0 \}</tex>. Ядро линейного отображения образует подпространство в линейном пространстве <tex>A</tex>.

*Пусть <tex>A</tex> — оператор, действующий в банаховом пространстве <tex>E</tex>. Число λ называется ''регулярным'' для оператора <tex>A</tex>, если оператор <tex>R(\lambda)=(A - \lambda I)^{-1}</tex>, называемый '''резольвентой''' оператора <tex>A</tex>, определён на всём <tex>E</tex> и непрерывен. Множество регулярных значений оператора <tex>A</tex> называется '''резольвентным множеством''' этого оператора, а дополнение резольвентного множества — '''спектром''' этого оператора.

==Билеты==
===1. Сопряженный оператор и его ограниченность===

Будем работать с <tex>E</tex>, как с банаховым пространством.

'''Def''': Пространство всех линейных функционалов на <tex>E</tex> образует линейное пространство (прошлый семестр).
Это пространство называется '''сопряжённым''' к <tex>E</tex>, оно обычно обозначается <tex>E^*</tex>.

'''Def''': Пусть <tex>A:E\to F</tex> — непрерывный линейный оператор действующий из банахова пространства <tex>E</tex> в банахово пространство <tex>F</tex>. И пусть <tex>E^*, F^*</tex> — сопряжённые пространства. Обозначим <tex>\forall x\in E, f\in F^* \langle Ax,f\rangle =f(Ax)</tex>. Если <tex>f</tex> — фиксировано, то <tex>\langle Ax,f \rangle </tex> — линейный непрерывный функционал в <tex>E, \langle Ax,f \rangle \in E^*</tex>. Таким образом, для <tex>\forall f\in F^*</tex> определён линейный непрерывный функционал из <tex>E^* </tex>, поэтому определён оператор <tex>A^*:F^*\to E^*</tex>, такой что <tex>\langle Ax,f \rangle=\langle x,A^*f \rangle</tex>.
<tex>A^*</tex> называется '''сопряжённым оператором'''.

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>. Тогда норма оператора <tex>A^*:F^*\to E^*</tex> совпадает с нормой <tex>A</tex>.

(оператор проектирования ??)

===2. Ортогональные дополнения Е и Е*===

'''Def''': Пусть <tex>S</tex> некоторое линейное множество. Тогда его '''ортогональное дополнение''' <tex>S^\perp = \{f \in E^* | f(x) = 0 \; \forall x \in S\}</tex>.

'''Th''': Имеют место соотношения: <tex>E^\perp = \{0\}</tex>; <tex>(E^*)^\perp = \{0\}</tex>.

(при доказательстве используем теорему Хана-Банаха)

===3. Ортогональное дополнение R(A)===

(Здесь можно написать красивый текст из конспекта про важность теорем и все такое)

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>, где <tex>E</tex> и <tex>F</tex> банаховы. Пусть также множество значений <tex>R(A)</tex> замкнуто в <tex>F</tex>. Тогда <tex>R(A) = (Ker(A^*))^\perp</tex>.

===4. Ортогональное дополнение R(A*)===

'''Th''': Пусть множество значений оператора <tex>A</tex> замкнуто: <tex>R(A) = Cl(R(A))</tex>. Тогда верно <tex>R(A^*) = Cl(R(A^*)) = (Ker(A))^\perp</tex>.

----

===5. Арифметика компактных операторов===

'''Def''': Линейный оператор <tex>A:E\to F</tex> называется '''компактным''', если он переводит любое ограниченное множество из <tex>E</tex> в относительно компактное множество в <tex>F</tex>.

Примером является оператор Фредгольма: <tex>\psi(s) = \int\limits_a^b\!K(s, t) \varphi(t)\, dt</tex>.

Установим несколько свойств:

'''Th''': Пусть операторы <tex>A, B:E\to E</tex> такие, что <tex>A</tex> компактен, а <tex>B</tex> ограничен. Тогда операторы <tex>AB</tex> и <tex>BA</tex> компактны.

===6. О компактности А*, сепарабельность R(A)===

===7. Базис Шаудера, лемма о координатном пространстве===

'''Def''': Система векторов <tex>\{e_n\}</tex> топологического векторного пространства <tex>E</tex> называется '''базисом Шаудера''', если каждый элемент <tex>f \in E</tex> разлагается в ''единственный'', сходящийся к <tex>f</tex> ряд по <tex>\{e_n\}</tex>: <tex>f= \sum_{i=1}^{\infty} f_i e_i</tex>, где <tex>f_i</tex> — числа, называемые коэффициентами разложения вектора <tex>f</tex> по базису <tex>\{e_n\}</tex>.

===8. Почти конечномерность компактного оператора===

===9. О размерности Ker(I-A) компактного А===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор, <tex> H = I - A </tex>.
Тогда, <tex> dim (Ker H)< +\infty </tex>

'''Следствие''' Множество решений операторного уравнения <tex> Ax = \lambda x, \lambda \in \mathbb{R} </tex> конечномерно.

===10. Условие замкнутости R(A) на языке решений операторного уравнения===

===11. О замкнутости R(I-A) компактного А===

===12. Лемма о Ker(I-A)*n компактного А===

===13. Об условии справедливости равенства R(I-A)=Е===

===14. Альтернатива Фредгольма-Шаудера===

===15. О спектре компактного оператора===

===16. О вещественности спектра ограниченного самосопряженного оператора===

===17. О характеризации спектра и резольвентного множества ограниченного самосопряженного оператора===

===18. О числах m- и m+===

===19. Спектральный радиус ограниченного самосопряженного оператора===

===20. Теорема Гильберта-Шмидта===

===21. О диагонализации компактного самосопряженного оператора и разложении его резольвенты===

===22. Теорема Банаха о сжимающем отображении===

===23. Дифференциал Фреше===

===24. Неравенство Лагранжа===

===25. Локальная теорема о неявном отображении===

===26. Теорема о локальной обратимости отображения===

===27. Локальная теорема о простой итерации===

===28. Локальная теорема о методе Ньютона-Канторовича===

===29. О проекторах Шаудера===

===30. Теорема Шаудера о неподвижной точке===

Функциональный анализ

2010-06-19T11:48:43Z

Ulyantsev: /* 7. Базис Шаудера, лемма о координатном пространстве */

Здесь я постараюсь написать теоретический минимум по второй части курса функционального анализа.

Большая часть материала взята из Википедии, чтобы не перебивать формулы и все такое. Все остальное бралось из конспектов, лучший из них лежит на firun.ru

Если вы читаете это, самоуничтожьтесь.

Да, да, '''функциональный анализ''' — раздел математики, в котором изучаются бесконечномерные пространства (в основном пространства функций) и их отображения.

==В прошлых сериях==

*'''Метрическое пространство''' <tex>M</tex> есть множество точек с '''метрикой''' <tex>d \colon M \times M \to R</tex>:
# <tex>d(x,\;y) \ge 0 ; d(x,\;y)=0\Leftrightarrow x=y</tex>.
# <tex>d(x,\;y)=d(y,\;x)</tex>.
# <tex>d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)</tex>.

*Метрическое пространство называется '''полным''', если любая фундаментальная последовательность в нём сходится к некоторому элементу этого пространства.

*'''Банаховым пространством''' называется нормированное линейное пространство полное по метрике, порождённой нормой.

*'''Пространство непрерывных функций''' — линейное нормированное пространство, элементами которого являются непрерывные на отрезке <tex>[a,b]</tex> функции (обычно обозначается <tex>{\mathrm C}[a,b]</tex>). Норма в этом пространстве определяется следующим образом: <tex>||x||_{{\mathbf C}[a,b]}=\max_{t\in [a,b]}|x(t)|</tex>

* '''Теорема Рисса — Фреше:''' Для любого непрерывного линейного функционала <tex>f</tex> на Гильбертовом пространстве <tex> H</tex> существует единственный вектор <tex>y \in H</tex> такой, что <tex>f(x)=(x,y)</tex> для любого <tex>x \in H</tex>. При этом норма линейного функционала <tex>f</tex> совпадает с нормой вектора <tex>y</tex>: <tex>\|f\|=\sup_{\|x\|=1} |f(x)|= \sqrt{(y,y)}</tex>. Теорема также означает, что пространство всех линейных ограниченных функционалов над <tex>H</tex> изоморофно пространству <tex>H</tex>.

*Теорема (Хан-Банах) о продолжении линейного функционала с сохранением мажоранты: любой линейный функционал <tex>f(x)</tex>, определённый на подпространстве <tex>L</tex> линейного пространства <tex>X</tex> и удовлетворяющий условию <tex>|f(x)| \leq p(x), \forall x \in L</tex>, где <tex>p(x)</tex> — некоторый положительно однородный функционал (определённый на всем пространстве <tex>X</tex>) то <tex>f(x)</tex> может быть продолжен на все пространство <tex>X</tex> с сохранением этого условия.

*Теорема (Хан-Банах) о непрерывном продолжении линейного функционала: всякий линейный функционал <tex>f(x)</tex>, определённый на линейном многообразии <tex>L</tex> линейного нормированного пространства <tex>X</tex>, можно продолжить на все пространство с сохранением нормы.

*Следствие: для любых двух различных точек линейного пространства существует линейный функционал, определённый на всем пространстве и такой, что его значения в этих точках различны.

* '''Ядром''' линейного отображения <tex>f\colon A\to B</tex> называются подмножество <tex>A</tex>, которое отображается в нуль: <tex>\mbox{Ker}\,f = \{ x\in A\mid f(x) = 0 \}</tex>. Ядро линейного отображения образует подпространство в линейном пространстве <tex>A</tex>.

*Пусть <tex>A</tex> — оператор, действующий в банаховом пространстве <tex>E</tex>. Число λ называется ''регулярным'' для оператора <tex>A</tex>, если оператор <tex>R(\lambda)=(A - \lambda I)^{-1}</tex>, называемый '''резольвентой''' оператора <tex>A</tex>, определён на всём <tex>E</tex> и непрерывен. Множество регулярных значений оператора <tex>A</tex> называется '''резольвентным множеством''' этого оператора, а дополнение резольвентного множества — '''спектром''' этого оператора.

==Билеты==
===1. Сопряженный оператор и его ограниченность===

Будем работать с <tex>E</tex>, как с банаховым пространством.

'''Def''': Пространство всех линейных функционалов на <tex>E</tex> образует линейное пространство (прошлый семестр).
Это пространство называется '''сопряжённым''' к <tex>E</tex>, оно обычно обозначается <tex>E^*</tex>.

'''Def''': Пусть <tex>A:E\to F</tex> — непрерывный линейный оператор действующий из банахова пространства <tex>E</tex> в банахово пространство <tex>F</tex>. И пусть <tex>E^*, F^*</tex> — сопряжённые пространства. Обозначим <tex>\forall x\in E, f\in F^* \langle Ax,f\rangle =f(Ax)</tex>. Если <tex>f</tex> — фиксировано, то <tex>\langle Ax,f \rangle </tex> — линейный непрерывный функционал в <tex>E, \langle Ax,f \rangle \in E^*</tex>. Таким образом, для <tex>\forall f\in F^*</tex> определён линейный непрерывный функционал из <tex>E^* </tex>, поэтому определён оператор <tex>A^*:F^*\to E^*</tex>, такой что <tex>\langle Ax,f \rangle=\langle x,A^*f \rangle</tex>.
<tex>A^*</tex> называется '''сопряжённым оператором'''.

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>. Тогда норма оператора <tex>A^*:F^*\to E^*</tex> совпадает с нормой <tex>A</tex>.

(оператор проектирования ??)

===2. Ортогональные дополнения Е и Е*===

'''Def''': Пусть <tex>S</tex> некоторое линейное множество. Тогда его '''ортогональное дополнение''' <tex>S^\perp = \{f \in E^* | f(x) = 0 \; \forall x \in S\}</tex>.

'''Th''': Имеют место соотношения: <tex>E^\perp = \{0\}</tex>; <tex>(E^*)^\perp = \{0\}</tex>.

(при доказательстве используем теорему Хана-Банаха)

===3. Ортогональное дополнение R(A)===

(Здесь можно написать красивый текст из конспекта про важность теорем и все такое)

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>, где <tex>E</tex> и <tex>F</tex> банаховы. Пусть также множество значений <tex>R(A)</tex> замкнуто в <tex>F</tex>. Тогда <tex>R(A) = (Ker(A^*))^\perp</tex>.

===4. Ортогональное дополнение R(A*)===

'''Th''': Пусть множество значений оператора <tex>A</tex> замкнуто: <tex>R(A) = Cl(R(A))</tex>. Тогда верно <tex>R(A^*) = Cl(R(A^*)) = (Ker(A))^\perp</tex>.

----

===5. Арифметика компактных операторов===

'''Def''': Линейный оператор <tex>A:E\to F</tex> называется '''компактным''', если он переводит любое ограниченное множество из <tex>E</tex> в относительно компактное множество в <tex>F</tex>.

Примером является оператор Фредгольма: <tex>\psi(s) = \int\limits_a^b\!K(s, t) \varphi(t)\, dt</tex>.

Установим несколько свойств:

'''Th''': Пусть операторы <tex>A, B:E\to E</tex> такие, что <tex>A</tex> компактен, а <tex>B</tex> ограничен. Тогда операторы <tex>AB</tex> и <tex>BA</tex> компактны.

===6. О компактности А*, сепарабельность R(A)===

===7. Базис Шаудера, лемма о координатном пространстве===

'''Def''': Система векторов <tex>\{e_n\}</tex> топологического векторного пространства <tex>E</tex> называется '''базисом Шаудера''', если каждый элемент <tex>f \in E</tex> разлагается в ''единственный'', сходящийся к <tex>f</tex> ряд по <tex>\{e_n\}</tex>: <tex>f= \sum_{i=1}^{\infty} f_i e_i</tex>, где <tex>f_i</tex> — числа, называемые коэффициентами разложения вектора <tex>f</tex> по базису <tex>\{e_n\}</tex>.

===8. Почти конечномерность компактного оператора===

===9. О размерности Ker(I-A) компактного А===
'''Утв.''' Пусть <tex> A </tex> - компактный оператор, <tex> H = I - A </tex>.
Тогда, <tex> dim (Ker H)< +\infty </tex>

'''Следствие''' Множество решений операторного уравнения <tex> Ax = \lambda x, \lambda \in \mathbb{R} </tex> конечномерно.

===10. Условие замкнутости R(A) на языке решений операторного уравнения===

===11. О замкнутости R(I-A) компактного А===

===12. Лемма о Ker(I-A)*n компактного А===

===13. Об условии справедливости равенства R(I-A)=Е===

===14. Альтернатива Фредгольма-Шаудера===

===15. О спектре компактного оператора===

===16. О вещественности спектра ограниченного самосопряженного оператора===

===17. О характеризации спектра и резольвентного множества ограниченного самосопряженного оператора===

===18. О числах m- и m+===

===19. Спектральный радиус ограниченного самосопряженного оператора===

===20. Теорема Гильберта-Шмидта===

===21. О диагонализации компактного самосопряженного оператора и разложении его резольвенты===

===22. Теорема Банаха о сжимающем отображении===

===23. Дифференциал Фреше===

===24. Неравенство Лагранжа===

===25. Локальная теорема о неявном отображении===

===26. Теорема о локальной обратимости отображения===

===27. Локальная теорема о простой итерации===

===28. Локальная теорема о методе Ньютона-Канторовича===

===29. О проекторах Шаудера===

===30. Теорема Шаудера о неподвижной точке===

Функциональный анализ

2010-06-19T11:43:08Z

Ulyantsev: /* 7. Базис Шаудера, лемма о координатном пространстве */

Здесь я постараюсь написать теоретический минимум по второй части курса функционального анализа.

Большая часть материала взята из Википедии, чтобы не перебивать формулы и все такое. Все остальное бралось из конспектов, лучший из них лежит на firun.ru

Если вы читаете это, самоуничтожьтесь.

Да, да, '''функциональный анализ''' — раздел математики, в котором изучаются бесконечномерные пространства (в основном пространства функций) и их отображения.

==В прошлых сериях==

*'''Метрическое пространство''' <tex>M</tex> есть множество точек с '''метрикой''' <tex>d \colon M \times M \to R</tex>:
# <tex>d(x,\;y) \ge 0 ; d(x,\;y)=0\Leftrightarrow x=y</tex>.
# <tex>d(x,\;y)=d(y,\;x)</tex>.
# <tex>d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)</tex>.

*Метрическое пространство называется '''полным''', если любая фундаментальная последовательность в нём сходится к некоторому элементу этого пространства.

*'''Банаховым пространством''' называется нормированное линейное пространство полное по метрике, порождённой нормой.

*'''Пространство непрерывных функций''' — линейное нормированное пространство, элементами которого являются непрерывные на отрезке <tex>[a,b]</tex> функции (обычно обозначается <tex>{\mathrm C}[a,b]</tex>). Норма в этом пространстве определяется следующим образом: <tex>||x||_{{\mathbf C}[a,b]}=\max_{t\in [a,b]}|x(t)|</tex>

* '''Теорема Рисса — Фреше:''' Для любого непрерывного линейного функционала <tex>f</tex> на Гильбертовом пространстве <tex> H</tex> существует единственный вектор <tex>y \in H</tex> такой, что <tex>f(x)=(x,y)</tex> для любого <tex>x \in H</tex>. При этом норма линейного функционала <tex>f</tex> совпадает с нормой вектора <tex>y</tex>: <tex>\|f\|=\sup_{\|x\|=1} |f(x)|= \sqrt{(y,y)}</tex>. Теорема также означает, что пространство всех линейных ограниченных функционалов над <tex>H</tex> изоморофно пространству <tex>H</tex>.

*Теорема (Хан-Банах) о продолжении линейного функционала с сохранением мажоранты: любой линейный функционал <tex>f(x)</tex>, определённый на подпространстве <tex>L</tex> линейного пространства <tex>X</tex> и удовлетворяющий условию <tex>|f(x)| \leq p(x), \forall x \in L</tex>, где <tex>p(x)</tex> — некоторый положительно однородный функционал (определённый на всем пространстве <tex>X</tex>) то <tex>f(x)</tex> может быть продолжен на все пространство <tex>X</tex> с сохранением этого условия.

*Теорема (Хан-Банах) о непрерывном продолжении линейного функционала: всякий линейный функционал <tex>f(x)</tex>, определённый на линейном многообразии <tex>L</tex> линейного нормированного пространства <tex>X</tex>, можно продолжить на все пространство с сохранением нормы.

*Следствие: для любых двух различных точек линейного пространства существует линейный функционал, определённый на всем пространстве и такой, что его значения в этих точках различны.

* '''Ядром''' линейного отображения <tex>f\colon A\to B</tex> называются подмножество <tex>A</tex>, которое отображается в нуль: <tex>\mbox{Ker}\,f = \{ x\in A\mid f(x) = 0 \}</tex>. Ядро линейного отображения образует подпространство в линейном пространстве <tex>A</tex>.

*Пусть <tex>A</tex> — оператор, действующий в банаховом пространстве <tex>E</tex>. Число λ называется ''регулярным'' для оператора <tex>A</tex>, если оператор <tex>R(\lambda)=(A - \lambda I)^{-1}</tex>, называемый '''резольвентой''' оператора <tex>A</tex>, определён на всём <tex>E</tex> и непрерывен. Множество регулярных значений оператора <tex>A</tex> называется '''резольвентным множеством''' этого оператора, а дополнение резольвентного множества — '''спектром''' этого оператора.

==Билеты==
===1. Сопряженный оператор и его ограниченность===

Будем работать с <tex>E</tex>, как с банаховым пространством.

'''Def''': Пространство всех линейных функционалов на <tex>E</tex> образует линейное пространство (прошлый семестр).
Это пространство называется '''сопряжённым''' к <tex>E</tex>, оно обычно обозначается <tex>E^*</tex>.

'''Def''': Пусть <tex>A:E\to F</tex> — непрерывный линейный оператор действующий из банахова пространства <tex>E</tex> в банахово пространство <tex>F</tex>. И пусть <tex>E^*, F^*</tex> — сопряжённые пространства. Обозначим <tex>\forall x\in E, f\in F^* \langle Ax,f\rangle =f(Ax)</tex>. Если <tex>f</tex> — фиксировано, то <tex>\langle Ax,f \rangle </tex> — линейный непрерывный функционал в <tex>E, \langle Ax,f \rangle \in E^*</tex>. Таким образом, для <tex>\forall f\in F^*</tex> определён линейный непрерывный функционал из <tex>E^* </tex>, поэтому определён оператор <tex>A^*:F^*\to E^*</tex>, такой что <tex>\langle Ax,f \rangle=\langle x,A^*f \rangle</tex>.
<tex>A^*</tex> называется '''сопряжённым оператором'''.

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>. Тогда норма оператора <tex>A^*:F^*\to E^*</tex> совпадает с нормой <tex>A</tex>.

(оператор проектирования ??)

===2. Ортогональные дополнения Е и Е*===

'''Def''': Пусть <tex>S</tex> некоторое линейное множество. Тогда его '''ортогональное дополнение''' <tex>S^\perp = \{f \in E^* | f(x) = 0 \; \forall x \in S\}</tex>.

'''Th''': Имеют место соотношения: <tex>E^\perp = \{0\}</tex>; <tex>(E^*)^\perp = \{0\}</tex>.

(при доказательстве используем теорему Хана-Банаха)

===3. Ортогональное дополнение R(A)===

(Здесь можно написать красивый текст из конспекта про важность теорем и все такое)

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>, где <tex>E</tex> и <tex>F</tex> банаховы. Пусть также множество значений <tex>R(A)</tex> замкнуто в <tex>F</tex>. Тогда <tex>R(A) = (Ker(A^*))^\perp</tex>.

===4. Ортогональное дополнение R(A*)===

'''Th''': Пусть множество значений оператора <tex>A</tex> замкнуто: <tex>R(A) = Cl(R(A))</tex>. Тогда верно <tex>R(A^*) = Cl(R(A^*)) = (Ker(A))^\perp</tex>.

----

===5. Арифметика компактных операторов===

'''Def''': Линейный оператор <tex>A:E\to F</tex> называется '''компактным''', если он переводит любое ограниченное множество из <tex>E</tex> в относительно компактное множество в <tex>F</tex>.

Примером является оператор Фредгольма: <tex>\psi(s) = \int\limits_a^b\!K(s, t) \varphi(t)\, dt</tex>.

Установим несколько свойств:

'''Th''': Пусть операторы <tex>A, B:E\to E</tex> такие, что <tex>A</tex> компактен, а <tex>B</tex> ограничен. Тогда операторы <tex>AB</tex> и <tex>BA</tex> компактны.

===6. О компактности А*, сепарабельность R(A)===

===7. Базис Шаудера, лемма о координатном пространстве===

'''Def''': Система векторов <tex>\{e_n\}</tex> топологического векторного пространства <tex>L</tex> называется '''базисом Шаудера''', если каждый элемент <tex>f \in L</tex> разлагается в ''единственный'', сходящийся к <tex>f</tex> ряд по <tex>\{e_n\}</tex>: <tex>f= \sum_{i=1}^{\infty} f_i e_i</tex>, где <tex>f_i</tex> — числа, называемые коэффициентами разложения вектора <tex>f</tex> по базису <tex>\{e_n\}</tex>.

===8. Почти конечномерность компактного оператора===

===9. О размерности Ker(I-A) компактного А===

===10. Условие замкнутости R(A) на языке решений операторного уравнения===

===11. О замкнутости R(I-A) компактного А===

===12. Лемма о Ker(I-A)*n компактного А===

===13. Об условии справедливости равенства R(I-A)=Е===

===14. Альтернатива Фредгольма-Шаудера===

===15. О спектре компактного оператора===

===16. О вещественности спектра ограниченного самосопряженного оператора===

===17. О характеризации спектра и резольвентного множества ограниченного самосопряженного оператора===

===18. О числах m- и m+===

===19. Спектральный радиус ограниченного самосопряженного оператора===

===20. Теорема Гильберта-Шмидта===

===21. О диагонализации компактного самосопряженного оператора и разложении его резольвенты===

===22. Теорема Банаха о сжимающем отображении===

===23. Дифференциал Фреше===

===24. Неравенство Лагранжа===

===25. Локальная теорема о неявном отображении===

===26. Теорема о локальной обратимости отображения===

===27. Локальная теорема о простой итерации===

===28. Локальная теорема о методе Ньютона-Канторовича===

===29. О проекторах Шаудера===

===30. Теорема Шаудера о неподвижной точке===

Функциональный анализ

2010-06-19T10:46:38Z

Ulyantsev: /* Билеты */

Функциональный анализ

2010-06-19T10:40:04Z

Ulyantsev:

Функциональный анализ

2010-06-19T10:37:57Z

Ulyantsev:

Здесь я постараюсь написать теоретический минимум по второй части курса функционального анализа.

Большая часть материала взята из Википедии, чтобы не перебивать формулы и все такое.

Если вы читаете это, самоуничтожьтесь.

Да, да, '''функциональный анализ''' — раздел математики, в котором изучаются бесконечномерные пространства (в основном пространства функций) и их отображения.

==В прошлых сериях==

*'''Метрическое пространство''' <tex>M</tex> есть множество точек с '''метрикой''' <tex>d \colon M \times M \to R</tex>:
# <tex>d(x,\;y) \ge 0 ; d(x,\;y)=0\Leftrightarrow x=y</tex>.
# <tex>d(x,\;y)=d(y,\;x)</tex>.
# <tex>d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)</tex>.

*Метрическое пространство называется '''полным''', если любая фундаментальная последовательность в нём сходится к некоторому элементу этого пространства.

*'''Банаховым пространством''' называется нормированное линейное пространство полное по метрике, порождённой нормой.

*'''Пространство непрерывных функций''' — линейное нормированное пространство, элементами которого являются непрерывные на отрезке <tex>[a,b]</tex> функции (обычно обозначается <tex>{\mathrm C}[a,b]</tex>). Норма в этом пространстве определяется следующим образом: <tex>||x||_{{\mathbf C}[a,b]}=\max_{t\in [a,b]}|x(t)|</tex>

* '''Теорема Рисса — Фреше:''' Для любого непрерывного линейного функционала <tex>f</tex> на Гильбертовом пространстве <tex> H</tex> существует единственный вектор <tex>y \in H</tex> такой, что <tex>f(x)=(x,y)</tex> для любого <tex>x \in H</tex>. При этом норма линейного функционала <tex>f</tex> совпадает с нормой вектора <tex>y</tex>: <tex>\|f\|=\sup_{\|x\|=1} |f(x)|= \sqrt{(y,y)}</tex>. Теорема также означает, что пространство всех линейных ограниченных функционалов над <tex>H</tex> изоморофно пространству <tex>H</tex>.

*Теорема (Хан-Банах) о продолжении линейного функционала с сохранением мажоранты: любой линейный функционал <tex>f(x)</tex>, определённый на подпространстве <tex>L</tex> линейного пространства <tex>X</tex> и удовлетворяющий условию <tex>|f(x)| \leq p(x), \forall x \in L</tex>, где <tex>p(x)</tex> — некоторый положительно однородный функционал (определённый на всем пространстве <tex>X</tex>) то <tex>f(x)</tex> может быть продолжен на все пространство <tex>X</tex> с сохранением этого условия.

*Теорема (Хан-Банах) о непрерывном продолжении линейного функционала: всякий линейный функционал <tex>f(x)</tex>, определённый на линейном многообразии <tex>L</tex> линейного нормированного пространства <tex>X</tex>, можно продолжить на все пространство с сохранением нормы.

*Следствие: для любых двух различных точек линейного пространства существует линейный функционал, определённый на всем пространстве и такой, что его значения в этих точках различны.

* '''Ядром''' линейного отображения <tex>f\colon A\to B</tex> называются подмножество <tex>A</tex>, которое отображается в нуль: <tex>\mbox{Ker}\,f = \{ x\in A\mid f(x) = 0 \}</tex>. Ядро линейного отображения образует подпространство в линейном пространстве <tex>A</tex>.

*Пусть <tex>A</tex> — оператор, действующий в банаховом пространстве <tex>E</tex>. Число λ называется ''регулярным'' для оператора <tex>A</tex>, если оператор <tex>R(\lambda)=(A - \lambda I)^{-1}</tex>, называемый '''резольвентой''' оператора <tex>A</tex>, определён на всём <tex>E</tex> и непрерывен. Множество регулярных значений оператора <tex>A</tex> называется '''резольвентным множеством''' этого оператора, а дополнение резольвентного множества — '''спектром''' этого оператора.

==Билеты==
===1. Сопряженный оператор и его ограниченность===

Будем работать с <tex>E</tex>, как с банаховым пространством.

'''Def''': Пространство всех линейных функционалов на <tex>E</tex> образует линейное пространство (прошлый семестр).
Это пространство называется '''сопряжённым''' к <tex>E</tex>, оно обычно обозначается <tex>E^*</tex>.

'''Def''': Пусть <tex>A:E\to F</tex> — непрерывный линейный оператор действующий из банахова пространства <tex>E</tex> в банахово пространство <tex>F</tex>. И пусть <tex>E^*, F^*</tex> — сопряжённые пространства. Обозначим <tex>\forall x\in E, f\in F^* \langle Ax,f\rangle =f(Ax)</tex>. Если <tex>f</tex> — фиксировано, то <tex>\langle Ax,f \rangle </tex> — линейный непрерывный функционал в <tex>E, \langle Ax,f \rangle \in E^*</tex>. Таким образом, для <tex>\forall f\in F^*</tex> определён линейный непрерывный функционал из <tex>E^* </tex>, поэтому определён оператор <tex>A^*:F^*\to E^*</tex>, такой что <tex>\langle Ax,f \rangle=\langle x,A^*f \rangle</tex>.
<tex>A^*</tex> называется '''сопряжённым оператором'''.

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>. Тогда норма оператора <tex>A^*:F^*\to E^*</tex> совпадает с нормой <tex>A</tex>.

(оператор проектирования ??)

===2. Ортогональные дополнения Е и Е*===

'''Def''': Пусть <tex>S</tex> некоторое линейное множество. Тогда его '''ортогональное дополнение''' <tex>S^\perp = \{f \in E^* | f(x) = 0 \; \forall x \in S\}</tex>.

'''Th''': Имеют место соотношения: <tex>E^\perp = \{0\}</tex>; <tex>(E^*)^\perp = \{0\}</tex>.

(при доказательстве используем теорему Хана-Банаха)

===3. Ортогональное дополнение R(A)===

(Здесь можно написать красивый текст из конспекта про важность теорем и все такое)

'''Th''': Пусть задан линейный оператор <tex>A:E\to F</tex>, где <tex>E</tex> и <tex>F</tex> банаховы. Пусть также множество значений <tex>R(A)</tex> замкнуто в <tex>F</tex>. Тогда <tex>R(A) = (Ker(A^*))^\perp</tex>.

===4. Ортогональное дополнение R(A*)===

'''Th''': Пусть множество значений оператора <tex>A</tex> замкнуто: <tex>R(A) = Cl(R(A))</tex>. Тогда верно <tex>R(A^*) = Cl(R(A^*)) = (Ker(A))^\perp</tex>.

----

===5. Арифметика компактных операторов===

'''Def''': Линейный оператор <tex>A:E\to F</tex> называется '''компактным''', если он переводит любое ограниченное множество из <tex>E</tex> в относительно компактное множество в <tex>F</tex>.

Примером является оператор Фредгоьма: <tex>\psi(s) = \int\limits_a^b\!K(s, t) \varphi(t)\, dt</tex>.

Установим несколько свойств:

'''Th''': Пусть операторы <tex>A, B:E\to E</tex> такие, что <tex>A</tex> компактен, а <tex>B</tex> ограничен. Тогда операторы <tex>AB</tex> и <tex>BA</tex> компактны.

===6. О компактности А*, сепарабельность R(A)===

===7. Базис Шаудера, лемма о координатном пространстве===

8. Почти конечномерность компактного оператора.

9. О размерности Ker(I-A) компактного А.

10. Условие замкнутости R(A) на языке решений операторного уравнения.

11. О замкнутости R(I-A) компактного А.

12. Лемма о Ker(I-A)*n компактного А.

13. Об условии справедливости равенства R(I-A)=Е.

14. Альтернатива Фредгольма-Шаудера.

15. О спектре компактного оператора.

16. О вещественности спектра ограниченного самосопряженного оператора.

17. О характеризации спектра и резольвентного множества ограниченного самосопряженного оператора.

18. О числах m- и m+.

19. Спектральный радиус ограниченного самосопряженного оператора.

20. Теорема Гильберта-Шмидта.

21. О диагонализации компактного самосопряженного оператора и разложении его резольвенты.

22. Теорема Банаха о сжимающем отображении.

23. Дифференциал Фреше.

24. Неравенство Лагранжа.

25. Локальная теорема о неявном отображении.

26. Теорема о локальной обратимости отображения.

27. Локальная теорема о простой итерации

28. Локальная теорема о методе Ньютона-Канторовича.

29. О проекторах Шаудера.

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