Диссертация (1150810), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

. ,(2.26)−1где ˜−1 (−1 ) – оценка решения для момента времени −1 , которую можнопредставить в виде˜−1 (−1 ) = −1 (−1 ) + −1 ,где −1 (−1 ) – точное решение (2.26) для момента времени −1 , а −1 – вы­()числительная ошибка, являющейся суммой детерминированной ошибки −1 ,возникающей, например, из-за ошибок округления, и случайной составляю­()щей −1 , обусловленной использованием метода Монте-Карло. Предполага­()ется, что используются несмещенные оценки, поэтому E−1 = 0.Обозначим за ∆ ( ) разность между точным решением (2.26) и * ( )∆ ( ) = ( ) − * ( ).Будем так же считать, что для −1 ≤ ≤ имеет место равенство∆ () = () − * ().Вычтем теперь из системы уравнений (2.26) систему (2.25), подставив внее *Z (, ( )) − (, * ( )) + ∆ (−1 ) + −1 .∆ ( ) =−1(2.27)75Рассмотрим отдельно разность (, ( )) − (, * ( )).

При сделанныхпредположениях относительно вектор-функции (, ) для нее существуетпроизводная по Гато (, ), и указанную разность можно представить ввиде интегралаZ1 (, ( )) − (, * ( )) = (, ( ) + (1 − )* ( ))∆ ( ) =0Z1= (, * ( ) + ∆ ( ))∆ ( ).0Теперь сделаем предположение относительно интегралаZ1 (, * ( ) + ∆ ( )).0Будем считать, что для выбранных интервалов времени [−1 , ] его можнодовольно точно приблизить по формуле прямоугольников в нуле, то естьZ1 (, * ( ) + ∆ ( )) ≈ (, * ( )), −1 ≤ ≤ .(2.28)0После такой замены уравнение (2.27) становится линейным относительно∆ ( ), и в этом случае решение системы (2.27) будет выглядеть следующимобразом∆ ( ) = exp⎧ ⎨ Z (, * ( ))⎩−1⎫⎬(∆ (−1 ) + −1 ).(2.29)⎭Обозначим теперь за ( ) – полную ошибку в момент времени , котораясостоит из ∆ ( ) и . Используя (2.29), легко проверяется, что( ) = exp⎧ ⎨ Z⎩−1 (, * ( ))⎫⎬⎭(−1 ) + .(2.30)76Представим теперь ∆ ( ) и ( ) в виде суммы двух компонент случайной идетерминированной()()∆ ( ) = ∆ ( ) + ∆ ( )( ) = () ( ) + () ( ),()при этом E∆ ( ) = E() ( ) = 0.Возьмем математическое ожидание от левой и правой частей уравнения(2.30) и получим уравнение() ( ) = exp⎧ ⎨ Z (, * ( ))⎩⎫⎬()() (−1 ) + .(2.31)⎭−1Вычтем из (2.30) уравнение (2.31) и получим связь случайной ошибки в мо­мент со случайной ошибкой в момент −1() ( ) = exp⎧ ⎨ Z (, * ( ))⎩⎫⎬()() (−1 ) + .(2.32)⎭−1Таким образом получилось два уравнения, описывающих поведение ошибок– одно для детерминированных ошибок, другое для стохастических.

Введемсокращенное обозначение = exp⎧ ⎨ Z⎩−1 (, * ( ))⎫⎬.⎭Тогда (2.31) и (2.32) примут вид()(2.33)()(2.34)() ( ) = () (−1 ) + ,() ( ) = () (−1 ) + .Транспонируем векторы в левой и правой частях (2.34)()(() ( )) = (() (−1 )) + ( ) .(2.35)77Чтобы оценить ковариацию () ( ), умножим (2.34) на (2.35) и возьмем ма­тематическое ожидание от левой и правой частей получившегося равенства,учитывая, что математическое ожидание части слагаемых в правой частиокажется равным нулю()(2.36)() ( ) = () ( ) + , = 1, 2, .

. . .Теорема 11.Если для всех натуральных выполнены неравенства()()‖ ‖ ≤ 1 < 1, ‖ ‖‖ ‖ ≤ 2 < 1, ‖ ‖ < 1 < ∞ и ‖ ‖ < 2 < ∞,то верны следующие оценкиlim ‖() ( )‖ ≤→∞1,1 − 1lim ‖() ( )‖ ≤→∞2.1 − 2Доказательство. Используя выражения (2.33) и (2.36) выпишем неравен­ства для норм () ( ) и () ( )()()‖ ( )‖ ≤ ‖ ‖‖ (−1 )‖ +()‖ ‖≤ ··· ≤1 ‖() (0 )‖+−1∑︁1 1 .=1()‖() ( )‖ ≤ ‖ ‖‖() (−1 )‖‖ ‖ + ‖ ‖ ≤ . . .... ≤2 ‖() (0 )‖+−1∑︁2 2 .=1После перехода к пределу при → ∞ в левых и правых частях неравенствполучим утверждение теоремы.Таким образом, при сделанном предположении (2.28) и выполнении усло­вий теоремы 11 последовательный алгоритм Монте-Карло будет стохастиче­ски устойчивым.78Одним из преимуществ алгоритмов метода Монте-Карло является про­стота их реализации. Однако усложнение алгоритма для деревьев по сравне­нию с линейным случаем очевидно, и рассмотрение алгоритма и особенностейего эффективной реализации становится необходимым.Моделирование ветвящейся траектории, как нетрудно видеть, носит ре­куррентный характер.

Всё начинается с рождения корневой частицы. Длянеё определяется состав потомков и время гибели. Затем для каждого изпотомков выполняется аналогичная операция, далее то же следует для по­томков потомков и так далее. Можно было бы организовать алгоритм в видерекуррентного вызова функции ( , ), которая бы по времени рожде­ния и типу частицы моделировала время гибели и состав потомков, а такжерассчитывала оценку (2.22), делая рекуррентный вызов⏟1 ( , +1 ) ⏞ ( , ) = (1 , +1 ) . . . (1 , +1 ) . .

. ( ) ( , +1 ). . . ( , +1 ) . . . ( , +1 ),⏟⏞в случае непустого состава потомков, и, обрывая рекурсию по формуле ( , ) =0 ( ),0 ( )в случае гибели частицы без рождения потомков. Однако даже небольшое ко­личество ветвлений при сравнительно малой вероятности поглощения можетпривести к переполнению стека вызова функций.Чтобы избежать такого эффекта предлагается следующий подход.

В ал­горитме будет использоваться структура, описывающая вершину в модели­руемом дереве. Эта структура хранит информацию о типе частице, времениеё рождения, времени гибели, составе потомков и ссылку на предка. В ходеалгоритма будут моделироваться потомки, соответствующие им вершины бу­дут добавляться в память, а после их обработки удаляться из неё. Помимо79этого будет использоваться указатель на текущую обрабатываемую верши­ну. Оценку метода Монте-Карло обозначим за .

Алгоритм моделированиядерева и расчета по нему оценки можно записать в следующем виде:Шаг 0 . Инициализация. По распределение 0 моделируется тип исходной ча­стицы . := ℎ /0 . Создаётся вершина с типом временем рож­дения и неопределенными временем гибели, составом потомков и безссылки на предка. Указатель текущей вершины указывает на корневуювершину.Шаг 1 . Если для текущей вершины не определён состав потомков, то перехо­дим к шагу 2, иначе переходим к шагу 3.Шаг 2 . Для текущей вершины по распределению ( ) моделируется .Если = (0, . . .

, 0), то0 ( ) := 0, ( )вершина считается обработанной и удаляется из памяти, а указательперемещается на предка, если он есть, текущей вершины, после чеговыполняется переход к шагу 1. Отсутствие предка означает, что мыобработали все вершины с их потомками и алгоритм завершается.Если ̸= (0, . . . , 0), то по распределению ( , ) находится время +1гибели текущей частицы. Рассчитывается оценка ( , +1 ) := . ( ) ( , +1 )Выполняется переход к шагу 1.Шаг 3 . Если для текущий вершины есть необработанные потомки, то из нихвыбирается первый. По его типу создаётся вершина. Количество потом­ков, данного типа, которые необходимо обработать для текущей верши­80ны уменьшается на 1.

Указатель перемещается на созданную вершину.Выполняется переход к шагу 1.Если все потомки текущей вершины обработаны, то указатель перехо­дит на его предка, а сама вершина удаляется, затем выполняется пе­реход к шагу 1. В случае его отсутствия все вершины обработаны иалгоритм завершается.Основным преимуществом такого алгоритма является тот факт, что длядеревьев ∈ Ω количество единовременно хранимых в памяти вершин внезависимости от степени ветвления процесса не превосходит . Простота реа­лизации и естественный параллелизм метода Монте-Карло делают алгоритмэффективным средством вычисления оценок (2.22) на многопроцессорных си­стемах.2.3.

Общий случайДо этого момента обсуждалось решения интегральных уравнений с поли­номиальной нелинейностью. Перейдем к рассмотрению уравнений вида (2.3)с произвольной нелинейностью. Его предлагается заменить на приближенноеZ∑︁ () =(0,...,0) (, )1 1 ( ) . . . ( ) + (), = 1, . . . , .0 =(1 ,..., )Приближенное уравнение можно решать методом Монте-Карло, способамиизложенными в предыдущих пунктах.Как известно, метод Монте-Карло позволяет находить оценку решениядля задачи˜ = ,(2.37)˜ – оператор с полиномиальной нелинейностью.

Однако в прикладных за­где дачах часто встречаются случаи с операторами произвольной нелинейности.81Пусть требуется решить задачу = (2.38)c произвольным нелинейным оператором , сжимающим на некоторой обла­сти , с постоянной сжатия < 1. И пусть * – единственная на непо­движная точка оператора .В данном случае разумно предложить заменить исходный нелинейный˜ , который в свою очередь будетоператор на приближенный оператор обладать свойством полиномиальной нелинейности. И далее вместо исходнойзадачи (2.38) решать систему (2.37) методом Монте-Карло.˜ может и не иметь неподвижных точек вВ общем случае оператор области или же иметь несколько неподвижных точек. Далее будем счи­˜ – сжимающий на замкнутом множестве 0 ⊂ , и ˜ 0 ⊂ 0 .тать, что ˜ наЭто гарантирует существование единственной неподвижной точки * у множестве 0 .

Вообще говоря, * может и не совпадать с * .Запишем оператор в виде˜ + ∆. = Нетрудно показать, что * = * тогда и только тогда, когда ∆* = 0. Тоесть, чтобы, решая приближенное уравнение (2.37), получилось решение близ­кое к решению системы (2.38), нужно выбирать приближение таким образом,чтобы значение остатка ∆ в точке * по норме было как можно меньше.Ситуацию осложняет тот факт, что * является предметом поиска и нельзя˜ и ∆.заранее проверить адекватность выбора В связи с этим соображением рассмотрим следующую постановку. Пред­положим, что оператор может быть приближен оператором с полиноми­альной нелинейностью с заданной точностью ≥ 0, иными словами‖∆‖ < , ∀ ∈ .82Далее возникает вопрос – на сколько решение задачи (2.37) отличается отрешения (2.38).

Ответ на этот вопрос даёт следующая оценка. Рассмотримитерационный процесс˜ ,+1 = который при сделанных выше предположениях сходится к * . Верно следую­щее˜ − ∆ + − +1 + +1 − * ‖,‖+1 − * ‖ = ‖+1 − ˜ ‖ + ‖∆ ‖ + ‖ − +1 ‖ + ‖+1 − * ‖ ≤‖+1 − * ‖ ≤ ‖+1 − ˜ ‖ + ‖∆ ‖ + ‖ − +1 ‖ + ‖+1 − * ‖.≤ ‖+1 − И в итоге‖+1 − * ‖ ≤1˜ ‖ + ‖∆ ‖ + ‖ − +1 ‖).(‖+1 − 1−(2.39)Переходя к пределу при → ∞ в левой и правой частях неравенства(2.39) получим оценку‖ * − * ‖ ≤1‖∆ * ‖ ≤.1−1−(2.40)Таким образом, ответ на поставленный вопрос получен.Теперь перейдем к ряду примеров применения предложенных методовдля решения задач, которые либо являются системами обыкновенных диф­ференциальных уравнений вида (2.1), либо могут быть к ней сведены.2.3.1. Уравнение теплопроводностиНачнем с рассмотрения уравнения теплопроводности (см.

Характеристики

Список файлов диссертации