Цепи Маркова (1121219), страница 89
Текст из файла (страница 89)
(3.7.9).Аналогично для задачи интерполяции с.м.м. без ограничений множествоΘ = P (см. (3.7.12)), поэтому естественная функция Ляпунова имеет видF (P) = L(P | XT = xT),P ∈ P,(3.9.37)см. (3.7.30). Разрешающее множество совпадает здесь с множеством F Πнеподвижных точек преобразования Π:FΠ = {P ∈ P : Π (P) = P}.Примеры, которые мы будем иметь в виду, возникнут из соотношений(3.8.33) и (3.7.38 б). В этих примерах= Z = ( , P, Q) для задачифильтрации с.м.м.
и = P для задачи интерполяции с.м.м. Сейчас отображение M на самом деле взаимно однозначное (т. е. переводит точкув точку) и совпадает с отображением Φ в задаче фильтрации и с Π в задачеинтерполяции.С этого момента предполагаем, что M( ) для любого ∈ Θ — компактное множество. Это охватывает вышеупомянутый случай преобразованийΦ и Π. Действительно, в задаче фильтрации с.м.м. без ограничений преобразование Φ действует на множестве Θ = U , в то время как в задачеинтерполяции с.м.м. без ограничений Π действует на множестве Θ = P ,причем оба множества U и P компактны в соответствующих евклидовыхпространствах (ср. с соотношениями (3.7.11) и (3.1.5) – (3.1.7)).Определение 3.9.7.
Говорят, что отображение M замкнуто в точке∈ Θ, если из сходимости (k) → для точек (k) ∈ Θ и сходимости(k) → для точек (k) ∈ M( (k)) следует, что ∈ M( ). Если отображение M замкнуто в каждой точке ∈ Θ, то говорят, что M замкнуто намножестве Θ.В оставшейся части данного параграфа будем предполагать, что всерассматриваемые отображения замкнуты на множестве Θ. Очевидно, еслиM : Θ → Θ — взаимно-однозначное отображение, то M замкнуто в точке ,если M непрерывно в точке .
В общем случае многозначного отображенияM точки в множество мы по-прежнему будем говорить об алгоритмеA с начальной точкой (0) ∈ Θ, порождающем последовательность точек(N+1)= A( (N) ), если (N+1) ∈ M( (N) ), N > 0. Такой алгоритм простозадается отображением точки в точку, которое мы снова обозначим A,устанавливающим единственный выбор элемента A( ) из множества M( ).Определение 3.9.8. Функция F : Θ → R называется функцией, возрастающей на траекториях, или функцией Ляпунова (ascent function), длязамкнутого многозначного отображения M точки в множество с разрешающим множеством (solution set) Γ ⊂ Θ, если1) F непрерывна и ограничена на Θ;2) F (b) > F ( ) ∀ ∈ Θ и b ∈ M( );5633) из условия F (b) = F ( ) для некоторого b ∈ M( ) следует, что ∈ Γ.Пример функции Ляпунова возникает в контексте задач без ограничений для с.м.м.
Как было сказано ранее, для задачи фильтрации Θ == U , отображение M совпадает с преобразованием Баума —Уэлча («точкав точку») Z ∈ U 7→ Φ (Z) (см. (3.8.33)) и разрешающее множество Γсовпадает с множеством FΦ неподвижных точек отображения Φ:Перейдем теперь к общей ситуации, мотивированной изложеннымивыше примерами, на которые мы будем периодически ссылаться. Удобноработать с многозначным отображением M, переводящим точки в мно∈ Θжества.
В общем случае такое отображение переводит точкув подмножество M( ) ⊂ Θ, где Θ — заданная область в евклидовом пространстве Rn ,M : ∈ Θ 7→ M( ) ⊂ Θ.(3.9.34)§ 3.9. Обобщения алгоритма Баума—Уэлча. Глобальная сходимость итерацийГлава 3. Статистика цепей Маркова с дискретным временем562(3.9.38)Заметим, что оба множества FΦ и FΠ — замкнутые подмножества множеств U и P соответственно.Желательно доказать, что последовательности моделей (Z (N) ) и (P (N) )сходятся или имеют предельные точки при N → ∞. Напомним, что геометрически Z (N) и P (N) являются образами начальных моделей Z (0) и P (0) приотображениях ΦN и ΠN (т.
е. при N-кратных итерациях преобразований Φи Π). Поэтому нужно рассмотреть пределlim ΦN (Z) = Z∗ ,N→∞lim ΠN (P) = P∗ .N→∞(3.9.39)Для краткости изучим преобразование Φ, поскольку рассуждения относительно Π полностью аналогичны. Очевидно, что предельные модели Z ∗будут неподвижными точками преобразования Φ:Φ (Z∗) = Z∗ ,(3.9.40)что согласуется с соотношениями (3.8.23) – (3.8.25).Из общих результатов, установленных далее, можно вывести следующее утверждение.Глава 3. Статистика цепей Маркова с дискретным временемN = 0, 1, . . .и(N+1)=k→∞|| (k + 1) − (k) || 6для всех k > k0 .3(3.9.43)Возьмем точку ∗1 ∈ C1 .
Тогда существует сколь угодно большое k0 > k0 ,для которого || (k0) − ∗1 || < /3. Так как точки (k), k > k0 , имеют предельную точку из C2 , существует такое k00 > k0 , что dist( (k00), C2) 6 2 /3.Здесь и далее под расстоянием между точкой и множеством понимается,как обычно:dist( , C) = inf [|| − e|| : e ∈ C] .Теорема 3.9.9 дает достаточные условия глобальной сходимости итераций, но содержит слишком сильные предположения и оставляет открытымважный вопрос о проверке условий 3 и 4.
Эти вопросы являются областью интенсивного исследования, как аналитического, так и численногохарактера; см. замечание 3.9.14.Наш первый пример в рамках только что принятой общей постановкизадачи выглядит так.Пример 3.9.10 (теорема Ляпунова). Пусть F — ограниченная непрерывная функция Θ → R, а A — непрерывное отображение точки в точку, где..(Nk)k→∞(3.9.42)множество ее предельных точек образует замкнутый связный континуум.Решение. Замкнутое связное множество в Rn не может быть представлено в виде объединения двух непересекающихся непустых замкнутыхмножеств; если такое множество содержит более одной точки, то онообразует континуум.
Легко видеть, что предельные точки рассматриваемойпоследовательности образуют замкнутое множество. Предположим, чтоэто множество содержит более одной точки и что мы представили егов виде объединения непересекающихся множеств C 1 ∪ C2 , где C1 и C2оба замкнуты. Тогда существует такое > 0, что расстояние от любойточки C1 до любой точки из C2 не менее . В силу нашего предположенияо норме существует такое k0 , что∗= lim(N)Докажите, что ∗ ∈ Γ.Решение. Поскольку последовательность F ( (N) ) монотонно не убывает по N и ограничена сверху, существует предел limN→∞ F ( (N) ).
В силунепрерывности функции F этот предел совпадает с F ( ∗). С другой стороны, в силу непрерывности отображения A и вышеупомянутой монотонностион также совпадает с F (A( ∗)). Поэтому F (A( ∗)) = F ( ∗), и с учетомусловия (3.9.42) мы получаем ∗ ∈ Γ.Пример 3.9.11 (теорема Островского). Рассмотрим последовательность точек (k) ∈ Rn , для которых || (k + 1) − (k) || → 0. Тогда либоэта последовательность сходится (т. е. существует предел lim (k)), либо=∗(N)limN→∞(откуда следует, что значение F (Z∗) одно и то же для всех предельных точек Z∗).3.
Предположим дополнительно, что ||Z (N+1) − Z (N) || → 0 приN → ∞ и предельные точки Z∗ образуют замкнутое компактноесвязное множество U . Следовательно, либо существует единственная предельная точка, либо предельные точки образуют замкнутый компактный континуум.4. При условии 3 предположим, что F имеет конечное или счетное число точек глобального максимума (т. е. функция правдоподобия L( ; Z), имеет не более чемсчетное число оценок максимальногоправдоподобия) и что F Z (N) сходится (глобально) к максимальному значению F.
Тогда в утверждении 3 предельная точка ∗единственна, и, значит, имеет место сходимость∈ Γ.Пусть ∗ — предельная точка последовательности= A( (N) ) с начальной точкой (0) ∈ Θ:N→∞если F (A( )) = F ( ), тоПредположим, что F (Z) = L( ; Z), Z ∈ U (ср. с (3.9.36)), являетсяфункцией Ляпунова, удовлетворяющей условиям 1 и 2 из определения 3.9.8, причем разрешающим множеством Γ является множествоFΦ неподвижных точек Φ. Тогда справедливы следующие утверждения.1. Любая предельная точка Z∗ последовательности Z (N) лежитв множестве FΦ , т.
е. является фиксированной точкой отображения Φ.2. Значения F Z (N) монотонно возрастают, и поэтомуlim F Z (N) = F (Z∗)Z (N+1) = Φ (Z (N) ),565Θ → Θ. Предположим, что F — функция Ляпунова с разрешающим множеством Γ, т. е.(3.9.41)F (A( )) > F ( )Теорема 3.9.9. Пусть последовательность {Z (N) } порождена итерациями преобразования Φ начальной модели Z (0) :§ 3.9. Обобщения алгоритма Баума—Уэлча. Глобальная сходимость итераций564Предположим, что k1 — наименьшее число k00 с таким свойством. Тогда§ 3.9.
Обобщения алгоритма Баума—Уэлча. Глобальная сходимость итерацийТеперь из непрерывности A следует, чтофункции F следует, что= A( 0), а из монотонностиdist( (k1 − 1), C2) > 2 ,00567Глава 3. Статистика цепей Маркова с дискретным временем5663F ( 00) = F ( 0) = lim F ((N)N→∞dist( (k1), C2) >.Видим, что< dist( (k1), C2) 62.3(3.9.44)k→∞влечет за собой, что либо предельная точка одна (т. е. последовательность (N) сходится к пределу), либо множество предельных точек —это замкнутый связный континуум. Предположим, что условие (3.9.47) невыполняется.
Тогда можно извлечь такую последовательность (Nk) , длякоторой существуют пределы lim (Nk) = 0 и lim (Nk +1) = 00 , но 0 6= 00 .(N)=(∞).(3.9.48)Замечание 3.9.14. Возможный путь проверки условия в) теоремы3.9.13 — это проверить, что а) функция Ляпунова F имеет единственныйглобальный максимум max ∈ Θ и б) значения F ( (N) ) сходятся к максимальному значению F ( max). Для задачи фильтрации с.м.м. аналогичныйрезультат содержится в теореме 3.9.9.На практике условия а) –в) теоремы 3.9.13 выполняются в широкомклассе случаев. Однако строгая их проверка не так уж проста. Это вынудило некоторых авторов обсудить паллиативные меры, которые, однако,могут быть полезными в некоторых ситуациях. См. монографию [McLK] истатью C. F.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
