Содержание к диссертации
Введение
1. Основные результаты. 15
2. Решетчатые спиновые модели поля в высокотемпературной области. 68
2.1. Корпускулярная структура, возникающая в спиновых решетчатых моделях 68
2.1.1. Основные конструкции 68
2.1.2. Инвариантное подпространство %\ 75
2.1.3. Разложение подпространства *К^ 78
2.2. Асимптотика убывания корреляций в решетчатых моделях поля 85
2.2.1. Спектральные свойства операторов 7 и XIх на подпространстве !Ki 86
2.2.2. Вычисление асимптотики убывания корреляций нечетных мономов 92
2.2.3. Спектральные свойства операторов 7 и Ux на подпространстве 1 97
2.2.4. Вычисление асимптотики убывания корреляций четных мономов 102
3. Спектральный анализ стохастических динамик. 108
Спектральный анализ одномерной стохастической модели Изинга со случайным взаимодействием 108
3.1.1. Полное спектральное разложение одномерной стохастической модели Изинга со случайным взаимодействием 109
3.1.2. Асимптотическое поведение автокорреляционной функции. Случай ограниченного взаимодействия, имеющего изолированный максимум. 123
3.1.3. Общий случай положительного ограниченного взаимодействия 137
3.1.4. Асимптотическое поведение автокорреляционной функции. Случай неограниченного взаимодействия 152
Спектральный анализ стохастической модели плоских ротаторов при высоких температурах 161
3.2.1. Асимптотика убывания корреляций в случае одновременного сдвига по времени и по пространству. 162
3.2.2. Конструкция двучастичного инвариантного подпространства 179
3.2.3. Спектральный анализ генератора на двучастич-ном инвариантном подпространстве 186
Эволюция квазичастиц различных видов на примере
стохастической модели Блуме-Капел (the Blume-Capel
model) при высоких температурах 202
3.3.1. Основные построения для модели Блуме-Капел. 203
3.3.2. Построение инвариантного подпространства %\ С Яш 206
3.3.3. Инвариантное подпространство J{2 С !Кеие"в{1}.212
3.3.4. Спектральный анализ оператора L на подпространствах Oil и %2 214
3.3.5. Генератор L на инвариантных подпространствах Щ С 3iodd и^С Ят 224
4. Применение методов теории гиббсовских случайных полей к задачам обработки изображений . 227
4.1. Байесовский подход в задачах восстановления изображений 228
4.2. Алгоритмы на основе стохастических динамик 231
4.3. Сходимость аппроксимационных схем 234
4.4. Эргодические свойства аппроксимационных схем 239
4.5. Результаты вычислений 241
5. Предельные теоремы и предельный диффузионный процесс для неоднородного случайного блуждания на решетке. 249
5.1. Локальная предельная теорема для неоднородного случайного блуждания на решетке 250
5.2. Предельный диффузионный процесс для неоднородного случайного блуждания на одномерной решетке . 268
Заключение 281
Литература 283
- Асимптотика убывания корреляций в решетчатых моделях поля
- Полное спектральное разложение одномерной стохастической модели Изинга со случайным взаимодействием
- Алгоритмы на основе стохастических динамик
- Предельный диффузионный процесс для неоднородного случайного блуждания на одномерной решетке
Введение к работе
Актуальность темы. Системы, состоящие из большого числа взаимодействующих компонент, являются основным классом моделей, с помощью которых удается изучить поведение больших (бесконечных) физических или информационных систем. Такие системы проявляют коллективное поведение, в котором детали изменения каждой компоненты становятся несущественными. Вместо этого основной характеристикой такой системы является вероятностное описание доли компонент, которые обладают некоторым определенным свойством. Общая структура таких многокомпонентных моделей требовала новой концепции, которая была разработана на рубеже 19-20 веков Л. Больцманом и затем Дж.У. Гиббсом. Возникла новая наука, которую назвали статистической механикой. Первоначально статистическая механика была предназначена для решения физических проблем, однако разработанные новые методы и подходы оказались настолько универсальными, что стали применяться к различным ситуациям, далеко выходящим за рамки физических задач. Основы математической статистической механики были заложены в 40-50х годах Л. Ван Ховом, Л. Онзагером, Н.Н. Боголюбовым и В.И. Хаце-том, Т. Ли и К. Янгом, и позднее в 60-70е годы были развиты Р. Л. Добрущиным, О. Лэнфордом, Д. Рюэллем, Г. Галлавотти, Р. Гриф-фитсом, Ж. Жинибром, Д. Робинсоном, Ф. Спитцером, Ж. Лебо-вицем, С. Миракль-Солем, Ф. А. Березиным, Р. А. Минлосом, Я. Г. Синаем, когда на математическом уровне строгости были введены понятия гиббсовского случайного поля (ДЛР-состояния), построены предельные гиббсовские распределения, исследованы корреляционные функции непрерывных и решетчатых систем, построена теория фазовых переходов, введены неравновесные модели и изучена их связь с гиббеовскими состояниями.
Математический аппарат статистической механики включает в себя разнообразные методы из различных областей математики: теории вероятностей и теории случайных процессов, функционального анализа и теории дифференциальных уравнений. Данная работа посвящена результатам, полученным главным образом при помощи техники функционального анализа, и в частности, операторных методов. Основы такого функционального подхода к анализу многокомпонентных систем были заложены в 7G-80x годов в работах Р.А. Минлоса, Я.Г. Синая, В.А. Малышева и их учеников [29, 23, 24, 27, 56, 25, 26]. Дело в том, что изучение систем с близкодействующим взаимодействием между ее компонентами можно свести к изучению соответствующих марковских процессов с локальным взаимодействием и их переходных операторов. Все модели, рассмотренные в данной работе, характеризуются локальным взаимодействием, и изучение поведения этих моделей во многом сводится к исследованию спектральных свойств операторов, описывающих их эволюцию: трансфер-матриц гиббеовских случайных полей, генераторов стохастических динамик, стохастических операторов марковских цепей. Эти операторы действуют в специально построенных бесконечномерных пространствах и имеют специфическую, так называемую многочастичную или "корпускулярную"структуру. Это означает, что гильбертово пространство, в котором действуют эти операторы, может быть разложено в прямую ортогональную сумму подпространств, инвариантных относительно соответствующего оператора, и при этом ограничение оператора на каждое из этих подпространств, или по крайней мере, на несколько первых подпространств, будет иметь вид оператора, описывающего систему ровно п взаимодействующих между собой "частиц". Мы будем называть такие операторы n-частичными операторами. "Частицы"этой конструкции можно интерпретировать как квазичастицы, т.е. "коллективные "элементарные возбуждения исходной системы.
Помимо общей структуры спектра, важна также более детальная информация о спектральных характеристиках, таких как величина спектральной щели, интегральная плотность состояний, внутренняя структура спектра, наличие дискретного спектра и т.д. Эта информация позволяет найти оценки, а во многих случаях даже асимптотики, убывания корреляций (для равновесных моделей), или убывания временных корреляционных функций (для стохастических моделей). Свойство быстрого убывания корреляций эквивалентно так называемому свойству перемешивания. Это означает, что поведение системы в объемах, далеких друг от друга, (статистически) почти независимо. Для стохастических динамик асимптотика убывания временных (автокорреляционных) функций определяет скорость сходимости к равновесному состоянию, что особенно важно для приложений. Таким образом, спектральный анализ многочастичных операторов, описывающих поведение многокомпонентных систем, и в особенности, информация о старших ветвях спектра позволяет получить детальное и очень точное описание асимптотических характеристик этих сложных многокомпонентных систем, что и будет продемонстрировано в данной работе.
Отдельная глава работы посвящена приложению методов теории гиббсовских полей и соответствующих решетчатых стохастических моделей к задачам обработки изображений. Идея такого подхода, когда изображение моделируется с помощью некоторого гиббсовско-го распределения, а решение задачи глобальной оптимизации стро ится с помощью стохастической динамики, была предложена в 80х годах и восходит к работам С. Гемана, Д. Гемана и К. Хванга [47, 48]. При этом подходе изображение рассматривается как конфигурация случайного гиббсовского поля, определенного на двумерной решетке, со значениями спинов ("пикселей") на некотором конечном или компактном подмножестве вещественной прямой. В качестве восстановленного (или результирующего) изображения принимается конфигурация, на которой достигается минимум полной энергии системы. Сложность задачи заключается в том, что энергия является функцией огромного числа переменных и имеет очень много локальных минимумов. Поэтому детерминистские алгоритмы, такие как, например, метод градиентного спуска, в такой ситуации бесполезен, так как приводит систему к ближайшему локальному минимуму. В отличие от детерминистских, стохастические алгоритмы, базирующиеся на эргодических свойствах стохастических динамик, позволяют построить конфигурацию, глобально минимизирующую энергию, но при этом требуют выполнения достаточно большого числа итераций.
Основная идея стохастических алгоритмов заключается в том, чтобы построить некоторую марковскую цепь и соответствующую ей случайную последовательность конфигураций, сходяїцуюся за большое число шагов к искомой конфигурации, на которой достигается глобальный минимум энергии. Построение этой марковской (нестационарной) цепи происходит в два этапа. Сначала выбирается некоторая равновесная динамика со стационарным температурным гибб-совским распределением, например, глауберова динамика, Метрополис-динамика, или диффузионная динамика. С помощью этой динамики далее строится нестационарный марковский процесс (марковская цепь), соответствующий некоторой процедуре понижения температуры до нуля. Этот алгоритм, который носит название аннилинга, или медленного охлаждения, был введен в работах С. Киркпатри-ка, К. Гелатта, М. Вечи [53] и Б. Хаека [51]. Их эвристические рассуждения были основаны на формальной аналогии с физическими процессами, когда очень медленное охлаждение приводит реальные физические системы в устойчивые низкоэнергетические состояния. В дальнейшем процедура аннилинга была изучена на математическом уровне, см., например, [47, 49, 43, 72]. Основная идея аннилинга заключается в том, что скорость уменьшения температуры должна быть очень медленной, чтобы дать возможность системе выйти из многочисленных локальных минимумов.
В настоящее время эти идеи и конструкции получили широкое применение в задачах обработки изображений благодаря тем блестящим практическим результатам, которые получаются в результате численных вычислений на основе этой методики.
Цель работы. В работе рассматриваются следующие системы:
- гиббсовские поля статистической физики,
- марковские процессы с локальным взаимодействием, в том числе, стохастические динамики,
- спиновые системы в теории обработки изображений,
- неоднородные случайные блуждания.
Основной целью работы является изучение асимптотических характеристик этих систем (асимптотика убывания корреляций локальных функционалов от поля, асимптотика убывания автокорреляционных функций, асимптотика убывания корреляций при одновременном сдвиге по времени и по пространству), и лежащий в основе этого исследования спектральный анализ соответствующих операторов. Для анализа стохастических систем со случайным взаимодействием разработаны новые специальные методы, позволяющие изучить асимптотическое поведение усредненной автокорреля ционной функции. Особое место в работе уделяется разработке и обоснованию новых алгоритмов для задач обработки изображений, которые основываются на эргодических свойствах диффузионных динамик и апроксимационной технике.
Методика исследования. В наших исследованиях мы существенно используем методы функционального анализа, и в частности, преобразование Фурье, спектральное разложение для самосопряженного оператора, спектральный анализ стохастических операторов соответствующих марковских процессов и исследование их резольвент в комплексной плоскости, метод перевала для вычисления асимптотики корреляционных функций.
При исследовании поведения классических решетчатых систем в высокотемпературном режиме используется подход, который базируется на так называемом "московском методе "изучения гиббеов-ских полей с локальным взаимодействием. Основная идея этого подхода заключается во введении некоторой марковской цепи со сложным пространством состояний, ассоциированной с гиббеовским полем, и последующим спектральным анализом стохастического оператора этой марковской цепи, который называется трансфер матрицей гиббсовского поля. Если взаимодействие достаточно мало, то удается построить старшие инвариантные подпространства трансфер матрицы, изучить структуру соответствующих ветвей спектра, и далее по этой информации найти асимптотику корреляций значений поля в далеко отстоящих друг от друга точках. При использовании этого метода мы существенно опираемся на технику кластерных разложений и принцип сжимающих отображений.
Главным методом исследования стохастических систем остается детальный спектральный анализ генераторов стохастических динамик, которые имеют многочастичную структуру, аналогичную струк туре трансфер матриц гиббсовских полей. Для изучения трансляционно-инвариантных моделей используется некоторая модификация схемы, применяемой при анализе трансфер матриц, которая также основывается на технике кластерных разложений и принципе сжимающих отображений. Для изучения стохастической модели Изинга со случайным взаимодействием разработаны новые методы, основанные на построении старшего инвариантного подпространства генератора с последующим применением методов спектрального анализа случайных операторов, и в особенности, случайных матриц Якоби с зависимыми элементами. Здесь особое значение имеет техника ос-цилляционной теоремы, применяемая для вычисления интегральной плотности состояний генератора на краю спектра.
Разработка новых алгоритмов для задач обработки изображений основывается на общей теории стохастических динамик (марковских процессов на пространстве состояний системы) и их генераторов. При этом информация о спектральных свойствах генераторов играет решающую роль при изучении эргодических свойств стохастических процессов. Существенно используются также методы аппрок-симационной техники, базирующиеся на формуле Троттера-Куртца.
Содержание работы. В первой главе вводятся модели, которые изучаются в диссертации, и формулируются все основные результаты. Вторая глава посвящена исследованию свойств классических спиновых решетчатых систем. Найдена асимптотика убывания корреляций локальных функционалов от поля для ферромагнитной модели Изинга при высоких температурах в любой размерности. При этом по-отдельности изучается случай четных и нечетных функционалов.
Рассмотрена также более общая модель решетчатого спинового поля с произвольным конечным или компактным спиновым про странством. Показано, что для этих моделей характерна более сложная иерархическая структура спектра трансфер матрицы и соответствующих инвариантных подпространств, что доказывает существование квазичастиц различного вида.
Во третьей главе диссертации рассматривается несколько стохастических моделей:
- стохастическая модель плоских ротаторов при высоких температурах;
- обобщенная стохастическая модель Изинга со спином, принимающим три значения: -1, 0, 1;
- одномерная стохастическая модель Изинга со случайным взаимодействием.
В стохастической модели плоских ротаторов при высоких температурах найдена асимптотическая формула для убывания корреляций в случае одновременного сдвига по времени и по пространству. Для этой модели исследован также спектр генератора на двучастич-ном инвариантном подпространстве.
Для обобщенной стохастической модели Изинга при высоких температурах построены два одночастичных инвариантных подпространства генератора, описывающих состояния квазичастиц различных видов и сравниваются эргодические свойства этих квазичастиц.
В диссертации представлены результаты цикла работ, посвященных изучению одномерной стохастической модели Изинга со случайным взаимодействием. Описано точное местоположение спектра генератора с вероятностью 1. Доказано, что в этой модели существует полное спектральное разложение генератора для любой фиксированной реализации случайного взаимодействия. В результате весь спектр генератора описывается через спектр генератора на одно-частичном инвариантном подпространстве, где генератор унитарно эквивалентен случайной якобиевой матрице. Используя эту связь с теорией случайных операторов, в зависимости от вида распределения случайного взаимодействия удалось либо установить асимптотику, либо получить точные двусторонние оценки на усредненную автокорреляционную функцию. Показано, что усредненная автокорреляционная функция модели со случайным парным взаимодействием убывает быстрее, чем временная корреляционная функция трансляционно-инвариантной модели, за счет дополнительного убывающего субэкспоненциального множителя. Тем самым, на теоретическом уровне строгости доказано, что присутствие случайности может существенно улучшить эргодические свойства стохастических динамик.
Четвертая глава посвящена приложению методов теории гибб-совских случайных полей к задачам обработки изображений. В работе предложен, обоснован и изучен алгоритм для обработки изображений, который основывается на эргодических свойствах диффузионных динамик (соответствующих классическим стохастическим моделям с непрерывным спиновым пространством) с последующим применением аппроксимационной техники. В результате мы получаем некоторые стохастические итерационные алгоритмы, которые представляют собой аппроксимацию (по времени) диффузионной динамики и для которых доказана сходимость к диффузионному процессу. Отметим, что характерной особенностью предложенных алгоритмов является тот факт, что в качестве начального изображения для итерационной схемы можно использовать произвольную конфигурацию.
В работе представлены также результаты численных вычислений, проделанных Кс. Декомбом (ИНРИА) для задач восстановления изображений, в которых были использованы предложенные нами алгоритмы. Эти вычисления показали, что подходы с использованием Метрополис-алгоритма, применяемого ранее, и новых диф фузионных алгоритмов дают очень близкие результаты при выполнении большого числа итераций. С другой стороны, схема, использующая диффузионный алгоритм, показывает быструю сходимость уже на первой стадии вычислений (примерно после 300-500 итераций).
В пятой главе изучается асимптотическое поведение неоднородного случайного блуждания частицы по решетке, у которого переходные вероятности отличаются от переходных вероятностей однородного симметричного блуждания лишь в конечной окрестности начала координат. Доказано, что в размерности два и три имеет место локальная предельная теорема, а в одномерном случае найдена поправка к гауссовскому члену, которая имеет тот же порядок, что и главный член. Для одномерного случайного блуждания построен предельный диффузионный процесс на прямой, который оказывается не винеровским процессом, а принадлежит классу обобщенных диффузионных процессов (так называемый процесс с эластичным экраном в нуле, обобщающий понятие процесса с поглощающим или отражающим экраном в нуле).
Теоретическая ценность. Работа имеет теоретический характер. В диссертации разработаны новые подходы, которые в сочетании с известными методами исследований, позволили получить новые результаты и доказать утверждения, существующие ранее в виде гипотез. Результаты и методы работы могут быть использованы в статистической физике, в теории вероятностей, и кроме того, имеют приложение для практических задач обработки информации.
Практическая ценность. Изучение свойств стохастических динамик легло в основу исследований по разработке алгоритмов для задач восстановления изображений. Сравнение с ранее используе мыми алгоритмами и анализ предложенных схем позволяют рассматривать разработанные нами алгоритмы в качестве достойного кандидата для реализации оптимизационной схемы в задачах обработки изображений.
Апробация результатов и публикации. Результаты работы докладывались на научных семинарах в ИІШИ РАН под руководством Р.А. Минлоса и М.С. Пинскера (1996-2003), на спецсеминаре по математической физике в МГУ под руководством Р.А. Минлоса (1990-2003), а также обсуждались и докладывались в 1997-2003 годах на многочисленных российских и зарубежных научных семинарах, в том числе на семинарах в ИТЭФ под руководством Ф.С. Джапарова и В.Е. Шестопала, семинарах Технического Университета г. Мюнхена под руководством Г. Шпона, семинарах Университета г. Билифельда под руководством Ю.Г. Кондратьева и М. Рёкнера, семинарах Университета г. Бонна под руководством С. Альбеверио, семинаров Университетов I и III г. Рима (Ла Сапиенца) под руководством Э. Скаччиателли и С. Пелегринноти, семинарах Университета г. Камсрино под руководством К. Болдригини, на семинаре Университета г. Цюриха под руководством Э. Больтхаузена, на семинаре Эколь Нормаль, г. Лозанны под руководством Ш. Пфистера, на семинаре Университета г. Ралей (Северная Каролина, США) под руководством Х.Крима. Кроме того, прочитан мини-курс по спектральному анализу решетчатых моделей статистической физике в Университете г. Пекина (2000).
Результаты докладывадись на многочисленных международных конференциях, среди которых отметим конференции в Воронеже (1997), Киеве (1997, 1999), Ереване (1996, 1999, 2001, 2003), Праге (1998), Обервольфахе (2000) и Камерино (2004).
Асимптотика убывания корреляций в решетчатых моделях поля
В этом разделе мы покажем, как информация об одно- и двучастич-ных инвариантных подпространствах трансфер-матрицы может быть использована для нахождения асимптотики убывания корреляций в модели Изинга. Мы сформулируем ниже основные факты, касающиеся спектральных свойств модели Изинга в высокотемпературной области, на которых базируются доказательства теорем 1.2 -1.4. Согласно результатам работ [25, 26, 56] при достаточно малых (3 справедливо следующее разложение К - К0 Є %х Є %% Ф %ъ Ф 3U, (2.61) где все подпространства !К инвариантны относительно оператора Ти унитарной группы {Ux, х YQ] пространственных трансляций. Здесь "Ко - пространство констант, пространства 0i\ и К$ состоят из функционалов, нечетных относительно инволюции J, а 0Ї2 и И4 содержат четные функционалы. Обозначим через Ъ = Т%, U = UxWk,k = 1,2,3,4, сужения операторов 7 и Ux на соответствующие подпространства %k- Для операторов Оз и Т4 при всех достаточно малых /3 справедливы следующие оценки Ы СЛ №\\ С/3\ (2.62) где С - некоторая абсолютная константа, а операторы Ті и Тг имеют спектр порядка /? и (З2 соответственно. Далее мы подробно опишем свойства операторов Т и Ux, действующих в пространствах !Hi, %.
Спектральные свойства операторов Т и Ux на подпространстве Уі\.
Операторы Ті и Ux унитарно эквивалентны операторам умножения на функции: ТіДА) = о(А)/(А), UPf(X) - е Л /(А), / Є L2{Td,dX), причем вид и свойства функции а(Х) в случае модели Изинга могут быть изучены достаточно подробно. Лемма 2.5. Функция а (А) = о (Х,(3) допускает разложение а (А, /?) = /Зао (А, /?) + /3 (A, j3). (2.63)
При этом обе функции аа (А, /?), а\ (А, /3) вег естеекны, четны при X ETd и аналитически продолжаются до периодических функций в полосе Wp W$ = (2.64) JA= (A(1\...,A(d)) eCd, ImX{k) -1п/?-1пД fc = l,...,rf}, где D — D(d) - некоторая абсолютная константа} не зависящая от (3. Функция а\ (А, /3) является равномерно ограниченной в полосе Wp вместе со всеми своими производными, а функция ао (А, (3) представляется в рядом оо ... d Епя=ЛГ
Доказательство опирается на конструкцию инвариантного подпространства Кх. Для каждой точки х Є YQ С Zd+1 нулевого слоя Y0 обозначим множество {у Є YQ : у х} через Vx С YQ , где у х понимается в смысле лексикографического порядка на решетке YQ (— Zd) . Определим функции . , а{х) тх (и) (l-rj(ff))a где тх(а) = (а(х)\ o\Vx) - условное среднее по мере fi/з при условии, что фиксирована конфигурация поля т(ж) на множестве Vx. Тогда семейство функций вида где / С YQ - произвольное конечное подмножество YQ, образует ор-тонормированный базис в пространстве К. При этом справедливо следующее представление: их (а) = а (х) - {3 2 (х - еь) + k=i,...,d где вк - единичный вектор, направленный вдоль к-й оси, а их может быть записано в виде: IcVxU{x} с некоторыми коэффициентами В], см. [25, 26]. При этом из оценок на Bf, следует, что при всех х,у Є YQ, х у имеем {?ux,uy) = /a(x + ed+l)U(y)-P ]Г а(у-ек) \ + (2.66) + 0{[C(5f-y\+2). Аналогичное выражениие имеет место для х у.
Из общей структуры первого инвариантного подпространства следует, что в 0i\ существует ортонормированный базис вида: vx = ux+ 2 Siuf ICY0,\I\ 2 где Sf - некоторые коэффициенты. При этом справедливо представление для матричных элементов оператора 7\ — Т \дх в базисе {vx, х є YQ}: а у = (7гух, Vy)Xi = (ТіИя!) иу) + О ((СДа:-у+2) . (2.67) Далее, для любого у = (y(l\...,y(d)) Є Уо из общей формулы, выражающей моменты через семиинварианты, см. [25], имеем ( Ыг) (») = /?""+1 П(Ы + В, + О ((СР)Ы+2) . (2.68) Поэтому из (2.66), (2.67) и (2.68) вытекает, что a„ = /3H+i_ + 0(( ), (2.69) где и = (к ,...,« ). Наконец, используя унитарное преобразование К : !Ki - з (Td, dA), И () - е А Є L2 (Td, dX) , получаем, что оператор 9 i унитарно эквивалентен оператору умножения на функцию Таким образом, утверждение леммы 2.5 следует из (2.69).
Полное спектральное разложение одномерной стохастической модели Изинга со случайным взаимодействием
Генератор L(w) глауберовой динамики действует в пространстве функций Oiu == 2( , dfi[}(u)) по формуле: (Ь(и Ж т) = Y, c(n,a,u)(f( T )-f(a)), / Є И , (3.1) где интенсивность изменения спина 7п в узле п задается формулой: c(n,a,uj)=i + An( v (3.2) а Є И - конфигурация, которая отличается от конфигурации а только в узле п, Н(а,ш) = 2_ Мп,п &п ?п , 7n = ±1, л-п =1 wn,n = &п ,п — шь Є R - независимые одинаково распределенные случайные величины, заданные на ребрах Ь — (n,nf), \п — п!\ = 1 решетки Z1 и имеющие общее распределение р р(и).
Сейчас мы опишем некоторый ортонормированный базис пространства D w, с помощью которого строятся инвариантные подпространства генератора Ь(ш). Обозначим через vn(a, и) функции вида: vn( ?,u) = — п є Z\ (3.3) где ( 7 я) условное среднее по мере ції,) ПРИ условии, что значения конфигурации а левее точки п фиксированы. Тогда в работе [39] по аналогии с тем как это было сделано выше в главе 2, см. лемму 2.5, показано, что функции вида vI( T,ui) = Y[vn(a,u}), «в = 1, (3.4) где / — {пі,..., nr} С Zl всевозможные конечные подмножества решетки Z1, образуют ортонормированный базис пространства "Я . Лемма 3.1. Подпространства Oil {%ш = {const}), которые являются линейной оболочкой функций
Заметим, что любое конечное подмножество / С Z1 можно представить в виде объединения г подмножеств Um=i "i таких что каждое /т представляет собой множество последовательных ТОЧек Іт = ІУтіУт + ! Ут + &т}) И ЄСЛИ МЫ обозначим через ути zm соответственно первую и последнюю точки из 1т, тогда \ут+1 — Zm\ 2. Выражение (3.11) можно переписать в виде М / = (Л /+ (3.12) у1 г 2/лиУт m=l Таким образом, формулы (3.7), (3.12) доказывают лемму 3.1. Мы определим канонический изоморфизм Vk{u ) : Эф - [(WZ1)) ]", fc = 0,1,2,... при помощи следующего отображения базисных векторов: Vk(u) : Vl - є, Є [(feCZ1)) ]", (3.13) где / = {nb...,n }, / = fc, и функция ej(yi,...,t/fe), І/І Є Z1 имеет вид e/(yi,...,yfc)-( ( 1)ИЛР к гда{у1,...,№} = {«ь..-,п } = / 1 0, иначе
Здесь 7Г - перестановка последовательности уі,...,ук в порядке возрастания элементов уіх ... уік,и 7г - четность этой перестановки. Таким образом, из формул (3.7), (3.11), (3.12) следует, что оператор переходит в оператор lk(oj) = Vk(u;)Lk(w)Vk (u ) : [ftKZ1)) !" - [(«Z1)) ]", который имеет следующее представление: 1к(и) = Li(w) g Я ... Я + ... + Я ... Я g Li(w), где Li(w) — VI(OJ)LI{U})V{{UJ) - оператор, действующий в faiZ1). Так как функции {VJ((T,UJ)} образуют ортонормированный базис в пространстве ЛШу мы определили унитарное отображение V{u) пространства %ш в антисимметричное пространство Фока Jos(/2(Z1)): V{ui) : X- ftKZ1)), 113 и доказали представление (1.22) для оператора Ь(ш). Теорема 1.5 полностью доказана.
Таким образом, спектр оператора L{w) полностью определяется его первой ветвью S(Li(w)). Далее мы найдем местоположение этой ветви спектра с вероятностью 1. Мы докажем два включения: Si С [-1 - С, -1 + С], для некоторого С с = tanh2/?72, (3.14) [-1-с,-1 +с] С Ei, c tanh2 72. (3.15) 1) Рассмотрим случайный оператор М(ш) = i(w) + ?, отличающийся от Li(w) на единичный оператор Е. Так как М(ш) - самосопряженный оператор при любом ш Є П, то ЦМ)с -8upM(w),supAf(w) jj из где М(й ) - норма оператора в %&\ М{ш) : ЗС — JC, порожденная нормой в пространстве ${&, a Е(М) = Si + 1 - спектр оператора М(ш), который является неслучайным множеством для п.в. и. Введем пространство L функций вида: L={/ = Ylw н/іь = 2ы } пег1 пєг1 Тогда L - банахово пространство, которое плотно в пространстве OVQ , и для любой функции / L мы имеем: И/11%. = II J cn nll » $ сп IWk = ll/IU Норма ограниченного оператора В в L определяется следующим образом BL = sup Sn,m, п т где Вщт - матричные элементы В в базисе {ап} / — ЬЧІІЬ -J7fir т Далее нам понадобится лемма из работы [58]. Лемма 3.2. (Р.А. Минлос? [58]). Если В самосопряженный оператор в 3 такой, что В : L — L и ограничение B\L является ограниченным оператором в L, тогда В будет ограниченным оператором в 3 , причем
Алгоритмы на основе стохастических динамик
В задачах, связанных с восстановлением изображений, ранее, как правило, использовался алгоритм Метрополиса-Хастингса, который основан на свойствах глауберовых динамик для модели Поттса в сочетании с аннилинг алгоритмом (см. [47, 51, 53]). Действие последнего алгоритма имитирует медленное охлаждение системы до нулевой температуры, в результате чего гиббсовское распределение сосредоточивается на искомых конфигурациях (4.6), и соответствующий стохастический процесс на пространстве конфигураций стремится к Emm независимо от начальных условий: lim Р{Х{п) Є Smin) - 1. (4.7)
Напомним, как действует алгоритм Метрополиса-Хастингса. Обозначим через рХіУ произвольную симметричную переходную матрицу на конечном пространстве спинов S — {s\,..., s }, которая задает так называемое распределение предложения. Выберем новое значение конфигурации ХІ Є S в узле і Є А согласно распределению предложения и обозначим через У новую конфигурацию отличающуюся от конфигурации X значением только в одном узле г. Далее, новая конфигурация Y принимается с вероятностью QX,Y - ехр { [Я(У, в) - H(Xt в)}+ где [и}+ = и при и 0 и [и]+ — О при и 0. Прежняя конфигурация X сохраняется, соответственно, с вероятностью 1 — QX,Y Таким образом, последовательно рассматриваются значения конфигурации Х(п) — {Xi(n)} по всем узлам решетки Л и строится новая конфигурация Х(п-\-1). Кроме того, параметр тп выбирается не постоянным, а специальным образом убывающим к нулю при п — со (так называемый режим охлаждения). В работах [47, 51] было доказано, что если lim а log п Я, П— 00 где константа R зависит от функции энергии Н, то выполняется соотношение (4.7).
Если рассмотреть не дискретное, а непрерывное компактное пространство спинов, то для каждого значения параметра а можно ввести диффузионную динамику, обратимую относительно распределения, заданного в гиббсовской форме. Диффузионные процессы такого вида изучались, например, в работах [52, 38]. Таким образом, гиббсовская мера будет инвариантной мерой этого процесса. Далее, так же, как и выше, преобразуем стационарный процесс в нестационарный под действием процедуры аннилинга с тем, чтобы выполнялось соотношение (4.7). Доказано, см., например, [43, 48, 72], что для этого параметр a(t) должен убывать при всех достаточно больших t как ff2(t) = i " (4-8) где С О достаточно велико. Рассуждения и методы доказательств в этих работах опираются на идеи теории Вентцеля-Фрейдлина [3] -[5], развитые для изучения инвариантных мер диффузионных процессов с малой диффузией.
Соответствующие диффузионные процессы описываются системой взаимодействующих стохастических дифференциальных уравнений (см. (4.12) ниже). Мы не ставим перед собой задачу найти решение стохастических дифференциальных уравнений в явном виде, так как нас интересует довольно общий класс уравнений, а постараемся найти приближенное решение. Для этого рассматриваются различные дискретизации (по времени) диффузионного процесса, т.е. построены соответствующие аппроксимационные схемы и доказана их сходимость к диффузионному процессу.
Обозначим 1 = [s, s]m и рассмотрим гильбертово пространство функций 2(n,d/v), заданных на пространстве Q, с совпадающими граничными значениями по каждому аргументу. Скалярное произведение определяется с помощью гиббсовской меры -%Н{Х,в) dfb№ = Zh{(j) dvoiX), (4.9) где в качестве свободной меры на Q берется произведение нормированных мер Хаара на [—s, в]: фо — П dyh а Z\( r) - нормирующий ІЄЛ множитель. Генератор ha диффузионного процесса на О, с обратимой гиббсовской мерой (4.9), т.е. такой что (LJ, 9) = (/, Lag) (4.10) имеет следующий общий вид: (W)W = ± ь х) х) + Щ(х)-(Х) где матрица В(Х) = {bij(X)} при любом X симметрична и положительно определена. Из условия (4.10), в частности, следует, что процесс с генератором La является стационарным с инвариантным распределением (4.9).
Далее мы будем рассматривать случай, когда матрица диффузии является единичной матрицей В(Х) — Ей поэтому вектор сноса зависит только от градиента функции энергии: гЛ іЄЛ (4.11) Оператор La является генератором процесса Xa(t) на Q, обратимого относительно fia- Этот процесс называется диффузионной, или ланжевеновой, динамикой и может быть найден как решение стохастических дифференциальных уравнений dXa(t) = a(Xa{t))dt + adW(t), t 0, (4.12) где а 0 - параметр, характеризующий температуру системы, вектор а{Х) - а{Х,д) = -ЧхН{Х,в) определяет снос, который зависит от данных в и от текущей конфигурации X, dW(t) - диффузионный член, W = {W(t),t 0} - m-мерный винеровский процесс. В дальнейшем мы не будем использовать индекс а в обозначениях для Xa(t), помня, что решение, конечно, зависит от 7.
Из приведенных в начале этого параграфа рассуждений следует, что для почти всех реализаций процесса (4.12) значение процесса X(t) при t —» оо и a = a{t) — 0 согласно соотношению (4.8) стремится к одной из искомых конфигураций X Є mm, минимизирующих функцию энергии Н(Х,в). Это свойство является решающим для построения алгоритмов на основе стохастических динамик.
Предельный диффузионный процесс для неоднородного случайного блуждания на одномерной решетке
В этом параграфе мы докажем теорему 1.23. Для доказательства сходимости стохастических полугрупп мы воспользуемся аппрокси-мационной техникой из книги [45], согласно которой достаточно доказать сходимость генераторов соответствующих процессов на некотором существенном подпространстве функций.
Введем стохастический оператор Тп для случайного блуждания по решетке Zn с шагом 1/ /п, индуцированного нашим исходным блужданием по решетке Z с помощью формулы: где х = t, у = JL, kuk2 в Z. Тогда оператор Тп действует в пространстве функций 1) (Zn), 7 0) на Zn по формуле (Тп р)(у) - («) Рг(п,(у-«) (5-46) \ 4 V" //Pi,bhM где ер Є Цп {%п), J/,« Zn. Напомним, что норма в пространстве Ц(Zn), 7 0, определяется следующим образом
Из (5.46), в частности, следует, что функция hfl(y)} определенная формулой (1.63), может быть записана в виде hf}(y) = (a?W) (У), где 7Г„/ Є К, (Zn) - сужение функции /(ж) на решетку Zn С R. Введем далее оператор в пространстве ly{Zn) Лп = (Г„ - Е) п, (5.47) который по своему виду напоминает "разностный"генератор.
Сейчас мы сформулируем апроксимационную теорему из книги [45], на которой и будет базироваться наше дальнейшее доказательство.
Теорема 5.1. (S.N. Ethier, T.G. Kurtz, [45]) Пусть Тп - линейные сжатия в банаховых пространствах Ln соответственно, п — 1,2,..., и пусть T(t),t 0 - сильно непрерывная сэюимающая полугруппа на банаховом пространстве L с генератором А, и D -некоторое существенное подпространство для . Через тгп : L — Ln обозначим некоторые ограниченные линейные отображения пространства L в пространства Ln , причем, предполагается, что нормы 7гп равномерно ограничены: sup„ J7rnj оо.
Тогда следующие условия эквивалентны. 1) для любой функции / Є L: при п — оо равномерно на любом конечном отрезке [ii, 2]) 2) для любой функции / Є D существует последовательность функций fn Є Ln, п = 1,2,..., что \\fn 7rnf\\Ln 0 (n-юо) (5.48) Л./» - г,И/Ік- О (n oo) (5.49) Здесь оператор Лп определен формулой (5.47).
Далее, для того, чтобы применить теорему 5.1 к доказательству теоремы 1.23, положим Ln = /- (Zn), L = / (Я, гід), Тп выберем совпадающими с операторами (5.46), действующими в lj(Zn), 7 ( ) - это стохастическая полугруппа операторов (1.62) для диффузионного процесса с эластичным экраном в нуле, действующая в L = L2(R,dn), см. теорему 1.22, и тг : І2(й,гі/і) —+ l (Zn) - вложения пространства L2{R,dfx) в пространства p(Z„) соответственно: {v«f)(kfy/n) = f{kfy/n), keZ,neN.
Далее мы опишем существенное подпространство для генератора Ак полугруппы Tk(t) (1.62). Рассмотрим совокупность непрерывных функций с компактным носителем р(х) CQ(R) таких, что сужения этих функций (р± = фк на полуоси й± являются бесконечно дифференцируемыми функциями на R± соответственно, и кроме того, существуют и конечны односторонние пределы производных всех порядков в нуле: р+ (0+) 00, ір_(0-) 00, m = 1,2,... Обозначим пространство таких функции через D : D = {ф) є C0(R), р±(х) Є C R ), уэ± (0±) — существуют и конечны, m = 1,2,...}, и рассмотрим следующие подпространства функций 1?& С D : Dk = { p(x)D, /(0-) - 7/(0+) = 0), где 7 — izf) & 1- Введем кроме того подпространства D+I = WI)GHM /m)(0+) oo, m = 0,l,2,..., /(0+) = 0), _! = { (: :) є С(Я„), /т)(0-) оо, т = 0,1,2,..., /(0-) = 0),
Лемма 5.3. Множество D& С -О(Л ), & 1 является существенным подпространством для оператора Ак , т.е. Ak\ok = А&, где замыкание оператора берется в норме L2 (R, dpi). Доказательство. Пусть \к\ 1 , и обозначим через й-у замыкание пространства функций D в следующей норме : \Ы\и = фМЦ + У %, (5.50) где \\(р\\ = J \(p(x)\2dfi(x) - норма в пространстве L2{R,dfj,) , а через ф"{х) обозначена функция V ( \ ( _)", х 0.
Так как CQ (R) С D, то пространство Й7 состоит из функций g Є L2{R,dp) таких, что (р±)" Є L2(R,dfi): Щ = {дє L2(R, dfi), ($±)" Є 2(Д, Ф)}, и, следовательно, содержит область Z?(Afc) оператора А . Кроме того, если „ —» у?, (рп Є D в смысле нормы (5.50), то это значит, что Уп — , Рп —» уЛ (п — со) в смысле нормы L2(R,dfj,). Нам остается доказать, что предельная функция 93 6 D(Ak). Заметим для этого, что Я7 является гильбертовым пространством со скалярным произведением (/,0)7= // MW+ / /+ЙФМ+ / flf-dn(x), /,уєя7. 271 Рассмотрим на #7 четыре функционала: F±g = g(0±), Ifg = sf(0±). (5.51)
Тогда пользуясь теоремой Рисса, несложно доказать, что функционалы (5.51) являются непрерывными на Щ . Для этого достаточно построить функции / , /- є Н1 такие, что для всех р(х) из некоторого всюду плотного множества в Щ , например j для всех (р(х) Є D. С помощью несложных вычислений легко убедиться, что функция fi(x), соответствующая функционалу F+, имеет вид: h[ "\ smf2, х 0, и аналогичные представления имеют функции /{"(ж), fo(x). Так как функции tp(%) Є Dk обладали следующими свойствами 0+)- (0-) = 0, (0-)-7 (0+) = 0, то в силу непрерывности функционалов (5.51) после замыкания множества Dk по норме (5.50) для любой функции д(х) Є Dk эти свойства сохраняются. Следовательно, Dk - существенное подпространство оператора At .
