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

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

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

, задаётся производящими функциями 1 (), . . . , (). Для то­48го, чтобы он был вырождающимся, необходимо и достаточно, чтобы выпол­нялись следующие условия1. Система типов 1 , 2 , . . . , не содержит ни одного финального клас­са.2. Все собственные числа матрицы = ‖, ‖,=1 , где, = (1, 1, . . . , 1),лежат в единичном круге || < 1.Далее будем предполагать, что для рассматриваемых ветвящихся про­цессов выполнены условия теоремы.Теперь, после сделанной подготовительной работы, вернемся к поискурешения задачи (1.28) методом Монте-Карло. С системой (1.28) свяжем слу­чайны ветвящийся процесс, определяемый производящими функциями вида(1.31), в которых вероятности удовлетворяют условиям согласования:∙ > 0 для всех и , для которых ̸= 0.Будем предполагать, что для уравнения (1.28) выполнено мажорантное усло­вие: сходится метод последовательных приближений ( + 1) =∑︁(1.34)| | (), = 1, .

. . , при начальном (0) = , = 1, . . . , .Оценки метода Монте-Карло строятся на траекториях ветвящегося про­цесса, поэтому на траектории (1.33) одной из оценок может быть аналог оцен­ки по поглощению для линейного случая, а именно(1) =1 (1) ∏︁∏︁(1) 1 =1 1 =1(1 ,1 )(2)1(1 ,1 ) (2)1···( +1)(0,0,...,0) ∏︁∏︁ =1 =1(0,0,...,0).(1.35)49Если бы ветвящийся процесс был таким, что все траектории обрывалисьбы к поколению , то математическое ожидание (1.35) вычислялось бы каксумма( +1)1 (1) ∏︁ ∏︁∏︁∏︁(1 ,1 ) (2)(0,0,...,0)(1)1··· =0 (1),...,( )1 =1 1 =1 =1 =1∑︁∑︁=(1.36)= (( ) (0)) = (( −1) ())Последнее равенство легко проверяется индукцией по .

Действительно, (0) = = ((0) ()) ,а индукционный переход +1 (0) = ( (0)) = ( −1 ()) = ().В сделанных предположениях, хотя процесс и вырождающийся, а следо­вательно почти все траектории конечны, однако могут иметь сколь угодномного поколений. Поэтому, чтобы вычислить E нужно перейти в (1.36) кпределу при → ∞. Учитывая мажорантное условие (1.34), получимE = lim (( ) ()) = * .

→∞(1.37)Выражение для второго момента будет иметь видˆ ( ) (),E2 = lim →∞гдеˆ () =∑︁ ( )2(1.38) , = 1, . . . , .Таким образом, в данном разделе было дано формальное описание ме­тода Монте-Карло для решения систем алгебраических уравнений с полино­миальной нелинейностью. Используя аппарат теории ветвящихся процессов,50был описан процесс построения оценок на ветвящихся траекториях, связан­ных с решаемой системой. Были исследованы свойства построенных оценок.Важно будет отметить, что как и в случае с линейными системами процессвычисления оценки решения без труда распараллеливается путем распреде­ления моделируемых ветвящихся траекторий по разным процессорам.1.3.

Численные экспериментыДля асинхронных итераций численные эксперименты проводились дляслучайным образом смоделированной матрицы размерности 4 × 4, такойчто 1 () = 0.76, 1 (||) = 1.64, ‖‖ = 2.04.На рисунке 1.7 изображена норма вектора ошибок для асинхронных ите­раций с множествами = { ∈ N| = 0}, = 1, . . . , 4,a () = − 1, = 1, .

. . , 4, = 1, 2, . . . . В данном случае наблюдаетсяэкспоненциальный рост ошибки.На рисунке 1.8 изображена норма вектора ошибок для асинхронных ите­раций c частичной синхронизацией. Теорема 4 гарантирует сходимость нормыошибки к нулю при = 2, = 6, однако сходимость будет наблюдаться ужепри значениях = 2, = 3.Для метода Монте-Карло численные эксперименты проводились для слу­чайным образом смоделированной матрицы размерности 10×10, такой что1 () = 0.79, 1 (||) = 3.21, ‖‖ = 8.45.На рисунке 1.9 изображено стандартное отклонение оценки при решении(1.22) методом Монте-Карло с использованием оценок (1.14) и (1.18) для пара­метров = 5, = 100. В этом случае наблюдается явление стохастическойнеустойчивости.51Рис.

1.7. Расходимость асинхронных итера­Рис. 1.8. Частичная синхронизацияцийУвеличение количества моделируемых траекторий до = 1000 исправ­ляет ситуацию, что можно наблюдать на рисунке 1.10На рисунке 1.11 изображено стандартное отклонение оценки при реше­нии (1.20)–(1.21) методом Монте-Карло использованием оценок (1.14) и (1.18)для параметров = 5, = 3. При этом = 1000 при расчете (1.20) и = 1000 при расчете каждой итерации в (1.21). Пики на графиках соответ­ствуют периоду использования асинхронного метода.В качестве примера использования метода Монте-Карло для решениясистем с полиномиальной нелинейностью рассмотрим матричное уравненияРиккати (см. [31, 32])= () + 1 () + 2 () + (), (0 ) = 0(1.39)где – матрица неизвестных размерности × , (), 1 (), 2 (), () –заданные матрицы, зависящие от , размерности × . Уравнение Риккатииграет важную роль в вариационном исчислении и в квантовой теории поля.52Рис. 1.9.

Стохастическая неустойчивость при малом кол-ве моделируемых траекторийНеобходимость решать систему нелинейных уравнений может возник­нуть, например, при использовании неявного метода Рунге-Кутты (см. [33,34]): = ∆ ( ( ) + 1 ( ) + 2 ( ) + ( )) + −1 , = 1, 2, . . .(1.40)53Рис. 1.10. Ограниченное отклонениегде ∆ – шаг по времени, = 0 + ∆ , = ( ).В модельном примере будем считать матрицы (), 1 (), 2 (), (), независящими от времени. Результаты эксперимента приведены в таблице 1.1Одновременное выполнение условий |1 ()| < 1 и 1 (||) > 1 можетсоздать определенные трудности при использовании как детерминированных,54Рис. 1.11.

Оценка с частичной синхронизациейтак и стохастических асинхронных методов для решения системы (1.12).В детерминированном случае возможным выходом является использо­вание частичной синхронизации, когда асинхронные итерации чередуются ссинхронными. Представление о соотношении количества синхронных и асин­хронных итерации даёт теорема 4. Стоит отметить, что такой подход, вообще55Таблица 1.1Количество траекторийN = 10 N = 100 N = 1000 N = 10000Норма ошибки0.180.030.00170.0057Стандартное отклонение0.0940.0280.0090.003говоря, вписывается в концепцию асинхронных итераций.Комбинируя алгоритмы асинхронного типа и алгоритмы с синхрониза­цией метода Монте-Карло, мы, как и в детерминированном случае, можемрасширить сферу асинхронности при использовании стохастических методов.Случайный характер ошибки создаёт свои особенности, которые, как мы ви­дели, легко учесть.

Богатый арсенал средств понижения дисперсии оценоксоздаёт много возможностей для совершенствования алгоритмов и, по мне­нию автора, для больших систем уравнений метод Монте-Карло может бытьпредпочтительнее детерминированных асинхронных итераций.56Глава 2Глава 2. Решение систем обыкновенныхдифференциальных уравнений методомМонте-КарлоВ данном разделе речь пойдет о решении систем обыкновенных диффе­ренциальных уравнений. Основное внимание будет сосредоточено на алгорит­мах метода Монте-Карло, однако один из параграфов будет посвящен методуасинхронных итераций. Рассмотрение рандомизированных методов обуслов­лено потенциально большой размерностью системы и необходимостью прово­дить вычисления на многопроцессорных системах, а именно в этих аспектахметод Монте-Карло зарекомендовал себя в качестве эффективного метода.Рассмотрим систему обыкновенных дифференциальных уравнений пер­вого порядка, записанную в векторной форме˙ = (, ),(2.1)где = () = (1 (), 2 (), .

. . , ()) – искомая вектор-функция, ∈ R, (, ) = (1 (, ), 2 (, ), . . . , (, )) – оператор из R+1 в R , ∈ N –размерность системы. Пусть также задано начальное условие(0 ) = 0 .(2.2)Относительно функций (, ), = 1, . . . , предполагается, что они непре­рывны на области определения. Точно так же будет предполагаться, что част­ные производные (, 1 , .

. . , ), , = 1, . . . , существуют и непрерывны на области определения.57Идея предлагаемого метода состоит в том, чтобы заменить систему диф­ференциальных уравнений (2.1) на систему интегральных уравнений, имею­щую то же решение, что и исходная система. А затем решать получившуюсясистему интегральных уравнений методом Монте-Карло.Вероятно, самой простой из таких замен, не требующих никаких до­полнительных преобразований правой части уравнения (2.1), является ин­тегральное уравнениеZ() = (, ( )) + 0 .(2.3)0Впрочем, в некоторых случаях представляется выгодным выделить ли­нейную часть у функции (, ).

Рассмотрим равносильную (2.1) систему сле­дующего вида˙ = () + (, ) − (),(2.4)где () – матрица × , зависящая от . Введем следующие обозначения(, ) = (, ) − (),Z() =(),0где операция интегрирования выполняется поэлементно, и перейдем к инте­гральному уравнениюZ() = () −( ) (, ( )) + () 0 .(2.5)0Нетрудно проверить, что если = () – некоторое решение уравнения (2.4),определенное на интервале 1 < < 2 и удовлетворяющее начальному усло­вию (0 ) = 0 , то для функции () на всем интервале 1 < < 2 выполне­но интегральное тождество (2.5). Обратно, если для некоторой непрерывной58функции = () на интервале 1 < < 2 выполнено интегральное тож­дество (2.5), то функция = () дифференцируема, является решениемуравнения (2.4) и удовлетворяет начальному условию (2.2).Далее будут исследованы алгоритмы метода Монте-Карло для решениясистемы (2.1), в которой компоненты функций или являются полинома­ми от степени, не превосходящей ∈ N.

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

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