Диссертация (1150810), страница 6
Текст из файла (страница 6)
В частности в [4]разобран пример решения интегрального уравнений с квадратичной нелинейностью. Однако в указанных источниках нет достаточно строгого и подробного описания оценок метода Монте-Карло решения систем алгебраическихуравнений с полиномиальной нелинейностью.Рассмотрим нелинейную систему размерности ∈ N, уравнениями вкоторой являются полиномы степени, не превосходящей ∈ N, следующеговида =∑︁ 1 1 . . . , = 1, . .
. , ,(1.28)=(1 ,..., )где { = (1 , . . . , )} – векторы с целочисленными неотрицательными компонентами, для которых выполнено неравенство∑︁ ≤ .=1Далее иногда будет использоваться следующее сокращенное обозначение = 1 1 . . . .для векторов = (1 , 2 , . . . , ) и = (1 , . . . , ). В таких обозначениях40система (1.28) примет вид =∑︁ , = 1, . . . , .Как и ранее получившуюся систему можно записать в векторной форме = .В некоторых случаях будет использоваться следующее обозначение(0,0,...,0) = , = 1, . . .
, , = (1 , . . . , ).Будем далее предполагать относительно оператора , что он являетсясжимающим на замкнутом множестве ⊂ R и выполнено ⊂ . Этообеспечивает существование единственной неподвижной точки * оператора на , а также то, что итерационный процесс+1 = сходится к * для любого начального 0 ∈ .При решении линейных систем уравнений оценки метода Монте-Карлостроились на линейных траекториях цепи Маркова, а ветвящиеся траекториииспользовались в качестве техники уменьшения дисперсии.
В случае же с системами вида (1.28) оценки строятся на ветвящихся траекториях. При этомпроцесс, порождающий такие траектории, удобно интерпретировать как процесс эволюции популяции частиц. Изначально в популяции имеется одна частица. Каждая частица из популяции имеет единичную продолжительностьжизни. В конце жизни каждая частица производит случайное количество потомков. Качественный и количественный состав потомков определяется рассматриваемой системой уравнений.41Рассмотрим связь процесса рождения/гибели частиц и системы (1.28)более подробно. Пусть имеется типов частиц1 , 2 , . .
. , ,каждая из которых связана с определенным уравнением системы (1.28) – частица -ого типа связана с -ым уравнением. Если в популяции есть частица-ого типа, то её потомки определяются членами -ого уравнения. Член уравнения вида 1 1 . . . предполагает рождение 1 частиц первого типа, 2 частиц второго типа итак далее вплоть до частиц -ого типа. Так, например, свободный член(все равны нулю) подразумевает гибель частицы без рождения потомков.Конкретный же член -ого уравнения, определяющий дальнейший сценарий,выбирается случайным образом, так или иначе согласованным с коэффициентами .Одна из возможных траекторий, связанных с системой⎧⎨1 = 21 + 51 2 + 1 + 1,⎩2 = 22 + 1 2 + 21 + 2приведена на рисунке 1.5.В силу того, что указанная выше схема укладывается в понятие ветвящегося случайного процесса, для формального описания результатов разумновоспользоваться развитым математическим аппаратом этой области (см., например, [29, 30]).Текущее состояние популяции частиц будем характеризовать векторомразмерности с целыми неотрицательными компонентами = (1 , .
. . , ),42Рис. 1.5. Возможная траектория. Белые вершины соответсвуют первому уравнению системы, серые – второму.который показывает, что популяция частиц состоит из 1 частиц типа 1 , 2частиц типа 2 и так далее.Считая, что частица любого типа живёт единицу времени, динамика популяции будет рассматриваться в моменты времени 0, 1, 2, . . .
, иначе называемые поколениями.Обозначим за (1 , 2 ) вероятность того, что система в момент времени2 находится в состоянии , если в момент времени 1 она находилась в состоянии . Определенные для 1 ≤ 2 вероятности (1 , 2 ) удовлетворяютусловиям (1 , 2 )≥ 0,∑︁ (1 , 2 ) = 1.Здесь и далее суммирование∑︀производится по всем векторам с целочис43ленными неотрицательными компонентами.
Для случая 1 = 2 = примем (, ) =⎧⎨1, = ⎩0, ̸= Для марковских процессов, а именно с такими мы имеем дело, для любых1 < 2 < 3 вероятности (·, ·) удовлетворяют основному уравнению марковских случайных процессов (1 , 3 ) =∑︁ (1 , 2 ) (2 , 3 ).(1.29)Обозначим за (1 , 2 ) вероятность того, что частица типа за промежуток времени (1 , 2 ) превратится в совокупность частиц = (1 , .
. . , ).Для ветвящихся процессов вероятности (1 , 2 ) не зависят от∙ способа и времени возникновения исходной частицы типа , предполагается лишь её наличие в момент 1 ;∙ частиц популяции в момент 1 , отличных от рассматриваемой частицы,и частиц, возникающих из нее в последующие поколения.Для однородных марковских процессов, вероятности (1 , 2 ) для которых зависят лишь от разности 2 − 1 , уравнение (1.29) перепишется в виде ( + ) =∑︁ () ().Далее, если не будет оговорено другого, будут рассматриваться однородныемарковские процессы.Особую роль для ветвящихся процессов играют вероятности = (1),вероятность того, что частица типа за единицу времени превратится всовокупность частиц = (1 , .
. . , ).44Важным инструментом при исследовании ветвящихся процессов является производящая функция (1 , 2 , ) = (1 (1 , 2 , ), . . . , (1 , 2 , )),(1.30)где = (1 , . . . , ), (1 , 2 , ) =∑︁ (1 , 2 ) .(1.31)Функции (1 , 2 , ) определены при 1 ≤ 2 и удовлетворяют неравенствам| (1 , 2 , )| ≤ 1,если | | ≤ 1, = 1, .
. . , и равенствам (1 , 2 , 1, 1, . . . , 1) = 1.Производящая функция удовлетворяет (см. [29]) функциональному уравнению (1 , 3 , ) = (1 , 2 , (2 , 3 , ))(1.32)и граничному условию (1 , 1 , ) = .В нашем случае, то есть для однородных процессов, производящие функции будут иметь вид (, ) =∑︁ () ,а основную роль будут играть производящие функции (1, ) = () =∑︁ .Уравнение (1.32) для однородных процессов приобретет совсем простойвид ( + 1, ) = ( (, )) = (+1) (),45то есть (, ) является -й итерацией функции (). Иными словами поведение ветвящегося процесса определяется итерациями функции ().Как и в случае систем линейных алгебраических уравнений нам будутинтересны обрывающиеся траектории процесса, и именно на них будут строиться оценки метода Монте-Карло.
Процесс будет считаться выродившимся,если не осталось ни одной частицы типов 1 , 2 , . . . , . Вероятность того,что процесс, начавшись с одной частицы типа , выродится к поколению ,равна(0,0,...,0)() = (, 0, 0, . . . , 0).Вероятность того, что процесс, начавшись с одной частицы типа , рано или(0,0,...,0)поздно выродится, равна пределу (0,0,...,0) = →∞ () при → ∞() = →∞ (, 0, 0, . .
. , 0).Будем считать процесс вырождающимся, если все = 1, = 1, . . . , .Динамику популяции, начавшейся с одно частицы типа и выродившейся к моменту времени , можно записать следующим образом(0) → (1) → · · · → ( ),где (0) = (0, . . . , 1 , . . . , 0), () = (1 (), . . . , ()) – популяция в поколение , а ( ) = (0, 0, . . . , 0).Данное представление, однако, не достаточно подробно для наших целей.Ему могут соответствовать сразу несколько траекторий ветвящегося процесса.
Траекторию ветвящегося процесса удобно представлять в виде ориентированного графа, а точнее сказать дерева, в котором вершинами являютсячастицы, а направленные ребра обозначаю процесс превращения старой частицы в совокупность новых. Чтобы однозначно определить траекторию ветвящегося процесса, необходимо особым образом пронумеровать/обозначитьвершины дерева, соответствующего этой траектории.46Приведем такие обозначения. Начальная частица типа будет обозначаться (), её -ый потомок типа 1 будет обозначаться (1 ), частицы -огопоколения будут нумероваться(11 22 . . . ).Такая запись полностью определяет путь превращений от частицы типа нулевого поколения до частицы типа поколения .
При этом всё деревобудет однозначно определяться метками концевых вершин, соответствующихчастицам, погибшим без рождения потомков.Для траектории с рисунка 1.5 вершины пронумеруются так, как показанона рисунке 1.6.1121 112211111 21221 1111Рис. 1.6. Пронумерованные вершиныТакие обозначения в определенном смысле полезны, однако являются достаточно громоздкими для использования в выражении вероятности траектории.
Для вычисления вероятности траектории важно знать в какое состояниеперейдет та или иная частица из поколения.47Пронумеруем частицы типа поколения от 1 до (). Обозначим состояние, в которое перейдет -ая частица типа поколения за(,) ( + 1). В таких обозначения будет иметь место равенство∑︁(,) ( + 1) = ( + 1),,а выражение для вероятности траектории(1)1 (1) ∏︁∏︁(1 ,1 ) (2) 1···1 =1 1 =1( +1) ∏︁∏︁ =1( , ) ( +1).(1.33) =1Для того, чтобы вероятности (1.33) задавали вероятностную меру на пространстве траекторий необходимо, чтобы процесс был вырождающимся.Для формулировки необходимых и достаточных условий вырождаемостипроцесса введем классификацию типов частиц (см.
[29])1 , 2 , . . . , .Для каждого типа , = 1, . . . , выделим два подмножества и из совокупности типов 1 , 2 , . . . , . Положим ∈ , если при некотором с положительной вероятностью из частицы типа образуется частица типа . Положим ∈ , если при некотором с положительной вероятностьюиз частицы типа образуется частица типа . Пересечением этих типовназовем классом сообщающихся типов () = ∩ . Назовем класс сообщающихся типов Ψ финальным, если каждая частица любого из типов классаΨ всегда с вероятностью единица среди своего потомства имеет ровно одну частицу какого-либо типа из класса Ψ и может иметь еще какие-нибудьчастицы типов, не входящих в Ψ.Известна (см. [29]) следующая теорема.Теорема 9.Пусть случайный ветвящийся процесс с типами частиц1 , 2 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
