Асинхронно—статистические алгоритмы решения линейных и нелинейных уравнений тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

|2Д 12 9 2

РОССИЙСКАЯ АКАДЕМИЯ НАУК

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР СИБИРСКОГО ОТДЕЛЕНИЯ РАН

На правах рукописи Расулов Абдужаббор Саттарович

УДК 518. 01:510. С

Асинхронно — статистические алгоритмы решения лшгсйных и нелинейных уравнений.

01. 01. 07 — вычислительная математика

Автореферат диссертации на соискание ученой степени доктора фпзико — математических наук

НОВОСИБИРСК - 1992.

Работа выполнена в Ташкентском государственном университете.

Официальные оппоненты:

Доктор филнко — математических паук — Жигливскнй Л. Л. Доктор физико — математических наук—Григорьев 10. Н. Дсктор физико—математических наук — Сабельфельд К. К.

па заседании специализированного совета Д002. 10.01 по защите диссертацш"! на соискание ученой степени доктора паук при Вычислительном центре СО РЛ11 (63009!), Новосибирск, 90, пр. акад. Лаврентьева, 6).

С диссертацией можно ознакомиться и читальном зале ВЦ СО РАН (Новосибирск, 90, пр. акад. Лаврентьва, 6).

Автореферат разослан пе О.Л

Ученый секретарь специализированного совета,

Зсчушаи организамип:

Институт математического моделирования Р А Н

доктор физико — математических

Общая характеристика работы. Актуальность темы; • • Статистические методы в>мислений являются удобным средством решения многомерных задач на современных ЭВМ. Они обладают естественным параллелизмом и аСинхронностыо. Необходимость решения сложных фундаментальных и прикладных задач обуславливает исследование в области разработок и создания высокопроизводительных вычислительных методов и с раде тр. Одним из эффективных способов повышения производительности являются асинхронные методы вычислений в многопроцессорных структурах. Очень важным и актуальным является вопрос о построении эффективных асинхронных алгоритмов, скорость сходимости которых не уступает скорости сходимости лучших синхронных методов.

. Алгоритмы метода Монте-Карло оказываются»как правило,

автоматически распараллеленными в схеме независимых испытаний, вычисления по траекториям могут осудйствХятся независимо. Поскольку метод Монте-Карло сводится в конечном счета к вычислению сумм независимых в вычислительном отношении ■ слагаемых, то оказызаатся чрезвычайно эффективным использование многопроцессорных вычислительных систем. Так как асинхронные методы приводят при решении уравнений к сумми-' рованию. в случайное порядке, то возникают ес-хсственньй связи асинхронных методов с (.»тодом Монте-Карло. Актуальным является исследование вышеупомянутой связи а многопроцессорных вычислительных .струшу яри решении многомер-. ньк линейных и некоторых нелинейных задач математической физики. ■ '■-'■'-. ■ ' ь

Исследование методов, развитых,в теории метода Монте-Карло, позволяющих расшрить сферу применения асинхронных • вычислений является также важной задачей.Следует отаатитъ, что в последнее время асинхронные вычисления и методы -Монте-Карло уепепно применяются при решении тогокзрных , линейных и налйиейнш краевых задач математической физики.

Теория марковских протесов еярзко ¡^пользуется при решении разнообразных .линейных и мзликейиит красны:; задач

математической физики, с помощью которых описываются многие нестационарные Физические процессы.

Получить решение линейных и нелинейных уравнений с начально краевыми условиями в аналитической форме, особенно в многомерном случае удаётся ли¡ш в исключительных случаях. Построение несмещенных оценок' функционалов от решений таких уравнений является одним из основных и быстро развивающихся разделов теории Метода Монте-Карло- Поэтому построение и обоснование эффективных статистических алгоритмов для решения линейных и нелинейных задач математической физики Св том числе некоторых уравнений динамики разряженных газов и уравнений Шредингера) является' актуальным вопросом теории метода Монте-Карло. ; : -

Наличие связей между дифференциальными уравнениями и случайные процессам известно давно. Для интегральных уравнений с полиномиальной нелинейностью существуют связи с ветвящимися марковскими процессами. Решения нелинейных' уравнений в частных' производных представляются в виде интегралов по траекториям ветвящихся процессов. Приближенные вычисления последних» особенно* в многомерно» случае, осуществляются методой Монте-Карло ♦ алгоритмы которого удобны для использования на.многопроцессорных ЗВМ. Создание эффективных алгоритмов моделирования случайного ветвящегося марковского процесса, реализации которых образя-эт "деревья", конструирование несмещенных оценок минимальном дисперсией решений нелинейных задач на траекториях ветвящегося процесса является важны;,! вопросом теории и практики метода (¡¡онТе-Карло., .

Решения линейных и нелинейных. интегральных уравнений методом Монте-Карло возможно в случае абсолютной сходимости ссотеатстоуащбго 'ряда Неймана* Ряд НеЯмзна может сходится медленно'-' или ' в ,некоторых случая;< расходится. Ускорение сходимости .или . расширение области сходимости рядп Неймана,- мньк-.э; елорами рассч^ци»'- аО-п.-пфатюет ■ методч «влдатея'рчени юяк'« кзк'

для теории так и для практических приложений.

Проблею эффективности и исследования сложности асинх-. ронних алгоритмов метода Монте-Карло для решения, практических падач статистической Физики, газовой динамики теплопередачи являются также актуальной задачей.

Вероятностные вычислительные методы в настоящее время являются наиболее распространенным'/! и эффективными при решении-задач динамики разреженных газов и статистической Физики. Это объясняется вероятностной природой кинетических уравнений, высокой рззмерностыо задач и сложной постановкой граничных условий. . '

Задача вычисления собственных чисел и распределений имеет также большое теоретическое и прикладное значение. Тай "многие системы массового обслуживания описываются марковскими процессами, а. их характеристики являются ■ функционалами » от стационарных распределений этих' процессов. Стационарные распределения :ке являются собственным распределением интегрального оператора с переходными-вероятностями в качестве ядра. В виду того, что число состояний процесса велико, а переходы из одного состояния марковского, процесса, в другое описываются, как правило, . алгоритмически, практически единиственным способом вычисления функционала от стационарного. распределения процесса является >,ртод Нонтб-ГСарло. Поэтому развитие алгоритмов метода Монте-Карло '.для решения вышеупомянутых задач является современной проблемой теории и практики метода Монте-Карло.' ; .

Цель работы. Исследовзть глубокие'; связи неудов Монте-Карло. с асинхронными , вычислениями, применять приёмы, . развитые в. теории методов, Монте-Карло Для ¡расширения сферы применения асинхронных процессов, сконструировать асинхронные' алгоритгщ. метода Монте-Карло для решения лмнейньк " и нелинейных краевых задачдля уравненийэллиптического и / параболического типов; Г ' разработать * элективные алгоритмы моделирования - марковских случайных ветвящихся

процессов, на траекториях которых конструируются несмещенные оценки решений ; доказать конечность вторых моментов построенных несмещенных оценок *. используя аппроксимацию Паде расширить область применимости, метода Монте-Карло ; ' сконструировать асинхронные алгоритмы метода Монте-Карло . для вычисления собственных значений и функций для оператог ров,связанных с уравнением Шредингера, и разработать статистически оптимальные алгоритмы для решения нелинейного уравнения Больцмана.

Общая методика исследования. Широко применяются методы вычислительной математики, общая теория марковских случайных ветвящихся процессов, теория мартингалов, теория дифференциальных. уравнений в частных производных й методы статистического моделирования, теория асинхронных методов вычислений.! "

Научная новизна. Диссертация посвящена исследованию связи метода" Монте-Карло и асинхронных методов »разработке асинхронных алгоритмов метода Монте-Карло л^ решения линейных и нелинейных уравнений с полиномиальной нелинейностью, применению аппроксимации Паде для расширения области сходимости ряда Неймана, использованию предложенных алгоритмов для решения задач статистической физики и . газовой динамики. В частности, как следствие полученных в диссертации новых результатов :

- получены условия сходимости вероятностного асинхронного метод? и получен оптимальный- релаксационный параметр, ускоряющий сходимость асинхронного процесса ;

- установлены связи метода' Монте-Карло и асинхронного метода для многопроцессорных систем, а также показано, что -ряд приёмов (выделение главной части, векторные алгоритмы, установление мажорантны условий) развитчх в теории методов Монте-Карло,расширяют также сферу применимости асинхронных методов, ■

- для конструирования несмещенных оценок решения нелиней- • ной задачи Дирихле, , предложен модифицированный алгоритм

построения несмещенных оценок, благодаря чему увеличивает- ся эффективность асинхронного алгоритма Понте-Карло ;

- получены условия для вырождения построенного ветвящегося процесса, конечности дисперсий сконструированных оценок ;

- решена нелинейная задачи Неймана с квадратичной нелинейностью для оператора Лапласа и впервые сравниваются трудоёмкости алгоритмов» использующих оценку по поглощениям и по столкновениям в нелинейном случае;

- разработаны алгоритмы случайного блуждания по сфероидам для решения первой краевой задачи для параболических уравнений с переменными (зависящими от времени) коэффициентами и для уравнения неизотропиой диффузии;

- разработаны асинхронный статистические алгоритмы построения несмещенных и * - смущенных оценок для решения начально краевой задачи для полиномиальных нелинейных параболических уравнений. Обоснованы сходимости оценок с помощью теории мартингалов ;

- для построения эффективных численных алгоритмов впервые использован метод сведения нелинейного уравнения к системам линейных уравнений,дм уравнений в частных производных с полиномиальном нелинейностью ;

- построьн' статистический алгоритм для решений уравнений . теплопроводности s нелинейными граничными условиями и решена практическая задача расчета системы охлаждения одной теплотехнической установки ;

- для расширения области применимости м&тода Монте-Карло для режжия, интегральных уравнений применена аппроксимация Ладе совместно со стохастической аппроксимацией и получены условия сходимости последнего при применении матричной аппроксимации Ладе ;

- Конструированы модифиодюваннш статистические алгоритмы вычисления собственнмх значений и функций для операторов,связанных со стационарными и нестационарными уравнениями Шредингера, вычислены энергии основного состояния системы из трех частиц ;

- для решения нелинейного уравнения Больцмана разработан аналог "сопряженной" схемы в нелинейном случае и предложена вероятностная вычислительная схема с минимальной дисперсией как для пространственно неоднородного, так для пространственно однородного случая.

К диссертации разработано новое направление в теории метода Монте-Карло, связанное с исследованием асихронно--/стптустических методов- решения линейных и нелинейных уравнений в многопроцессорных системах:

Бее основные результаты диссертации являются новыми и опубликованы в работах автора.

Г1 рилокёния. Практическая ценность, работы заключается в том, что её результаты могут быть использованы для' :

а) дальнейшей разработки асинхронных алгоритмов. Монте-

- Карло при решении линейных и нелинейных уравнений на параллельных транспьютерных системах>и на многопроцессорных" ЭВМ ;

б) дальнейшей разработки чк.ленных методов решения многих прикладных задач, использующих аппарат марковских процессов ;

в) непосредственного решения ряда задач для линейных и нелинейных уравнении диффузии I в том числе.решения линейных и нелинейных задач теплопроводное (например,для расчета с..:тем охлаждения теплотехнических установок) ;

т) определения наименьшего уровня энергии многочастичной системы,описываемой уравнением Шредингера в статистической физике ;

д) ревенпя ряда задач динамики разреженного, гула, в том числе для расчета обт^кь-.мя тела'раэреа иным газом и в исследовании структур ударной волны.-

Апробация работы. . Основные : результаты докладывались

- на ] Всемирном конгрессе общества математической статистики и теории вероятностей имени Бернулли.ТашкентЛЭЗС г.;

- на 8 Мг .-.лународной конференции "Основы теории вычислении" Казань, 1Э?7г. ;

- на Международном симпозиуме г,когеодата, Баку, 1981 г. ;

- па Международной конференции "Применение статистических •методов в производстве и управлении", Пермь,. 1990 г. ;

- на Международном совещании "Метод Монте-Карло и параллельные алгоритмы", Приморско (Болгария), 19УЭ г. ;

- на 5-6-7-8 Всесоюзных совещаниях "Методы Монте-Карло в вычислительной математика и математической физике", 1976--1991 гг., Новосибирск ;

- на Всесоюзной конференции по вероятностным вычислительным методам и средствам, Москва, 1970 г. ;

- на 5 Всесоюзной конференции кубатурных формул, Ташкент, 1937 г. ;

- на Всесоюзных школах - семинарах по методу Монте-Карло и их приложениям (Алма-Ата,'1Э87 г., Ташкент 1903 г.) ; -на Всесоюзной конференции "Актуальные вопросы комплексного анализа", Ташкент, 1988 г. ;

- на 2-3-4 Республиканских конференциях "Методические и прикладные аспекты моделирования сложных систем и управления", Ташкент (1935, 1987,1989 гг.)";

- на семинарах кафедры статистического моделирования Санкт-Петербургского университета (ряс.проф.Ермаков С-М.);

- на семинаре ВЦ СО РАН (рук. член-корр.Р А Н, Михайлов Г. А ■) ;

- на семинаре кафедр прикладной сгтистики и исследования операций, теории вероятностей и математической статистики, вычислительной математики ЭВМ и программирования Ташкентского государственного университета (рук. проф. Азларов Т. А-, проф. Арипов М. М.) ;

- на семинарах института математики АН республики Узбекистан (ряс.прой. Нагаев A.B.) Г

- на семинарах института кибернетики АН Республики Узбекистан (рук.проф. Садулаев P.C.) ;

Публикации- Основные результата,полученные лично соискателем, опубликованы в статьях Р.-Ш и в монографиях Hü.ci 1

в изданиях>входя'дих в установленный ВАК список. Кроир

' —

того по теме диссертации опубликовании работы 110-2П. Объём работа- Диссертационная работа изложена на 2ВТ страницах, включая литературу,и состоит из введения, шести глав, списка литературы, содержащего 194 наименования. Нумерация формул,теорем и т.д. внутри каждой главы своя.

2. Обзор содержания работы.

Во введении обосновывается актуальность темы диссертации, указывется цель работы и главное направление работы-Кроме тог' там сформулированы основные результаты диссертации и приведен краткий обзор работ по изучаемой ; теме.

Перейдем к изложению результатов диссертации по главам.

В первой главе исследуются вероятностно - асинхронные итерационные алгоритмы решения квазилинейных уравнений и их связи с алгоритмами метода Монте-Карло. Пусть X - банахово пространство. Рассмотрим в пространстве X нелинейное (полиномиальное) уравнение вида

*» = Е К«. (*>, :..,♦>} + г= Р (с) (1)

ГП—1 Е

где /"е х, • Кт : хт —»' X - полиномиальное отображение, которое предполагается непрерывным, что эквивалентно ограниченности, т.е. существуют константы ст 0, дня которых при любых х1> х2.....хгп е ^ •

пг= 1,2, . Если

"»У*!.....|1х1"

ш

Кт<*>,..,*>) 1x1 КМ(Х,У,, • • .П ♦>1У1) йу,...^.

•Б В ' ■ 1=1

где В из Ид, х е Б, |Ст (У|,... ,ут) - заданная функция на

Бт+\ то (1) превращается в интегральное уравнение с

полиномиальной нелинейностью. Пуст»' Б* пря! »е произведение 1 - экземпляров множества Б. Полагая х - х^ и умножая

• на »> (х<ч), полученное уравнение таким же образом умножая

' -1

на »> (х3) ит.д. и ооозначая У|(Хр... - 11 »> (.х^)

получим следующую бесконочную5 систему линейных интегральных уравнений

п

.....х ) ~ Е ' ■»• Кй (х-,у.,... ,7П).

11 1 т=1 п,в т ^ А т

йу,...с1ут =-- Дх,) х

ч ' ^О = Ь 1 = 1,?.,... (2)

Рассмотрим урезанную систему (2) при некотором конечном Я,, дополняя ой условиями - '«|1+1 = О (3)

Ле^ма. - Пусть существует у'™ (3 - 1,2,...,!0 решение ли-

• нейной системы (2)-(3), V1' - находится последовательно кз ураспонкй ■

. ^15<Х) а Я / |Ст(Х,У1....,У1) *>(1)(У,) ^1_1.>(У2) • , 13=1 0 (

р<1-«Я+0(уя) ^ ... йу1П+'/(Х) (4)

^ « ... = я 0. которые' разрешимы при

кайлом 1 <1 - 1,2,...). Тогда имеет место ^'^(х).

При достаточно большем М, ч^ будет сходится к р (х) если сходятся метод последовательных приближений (4). Систему линейных уравнений (2),<3) перепишем в виде .у = ? у. где , *-., = г, (^,..., ,

. • . '''г = г2 <*'1.....Ун>»-.: (5).

V., а (Ур....,»<;,).

Пусть - последовательность непустых подмножеств

множества- <1,2,...) которую называют хаотической (случайной) последователыюс'И'Ю множеств.При ; заданном КО) _ вектора нзчзл&ного приближения будем 'строить . последовательность Ь' {л) итераций-по правилу

" V (п+1 )= Рт- (Кп)) , ¡1 = 0, 1,

-. и -

или поэлементно

{^•-.fn) . если 1 « J-., 1 n+l

У'

(/^0(11)), если 1 <3 .Tmr n 0,1.2,...

Метод асинхронных итераций для (4) строится по следующему правилу :

jV.(n-l) , если 1 « Jn

= (/'¿(»jCSjin)),...-.^^))), если 1 в Jn.

Здесь < К1(п) , i -- 1,..., N последовательность ца-лнх неотрицательных чисел, удовлетворяющих условиям для любого 1 - 1,...,N S^n) £ n - 1, п = 1,2,..., Sj(n)-» « при n —> о- ; г 1 - встречается бесконечно много раз в <ТП. Величины S^(n) - называют запаздыванием и позволяют при вычислении вектора текущей , итерации использовать ' произвольные компонента векторов предыдущих итераций-Теорема. Если спектральный радиус р (F) <: 1,' то асинх-. ронпнй итерационный процесс (6), построенный для решения системы (5), сходится. . .

• Лемма. Если вероятность появления произвольного элемента 1 в -Тп подчиняется простейшим законам Бернуллй или Пуассона, то хаотическая последовательность имеет 'максимальный ОСаДОК С аероъгно1Г6к> e<j.nH«4*- •

При условии, что элементы Jn подчиняются простым вероятностным законам и Р - нелинейный оператор,справедливо следующее утверждение • '

Теорема. Пусть оператор P.: X —»-X является р - сжимающим на X с матрицей сжатия L, тогда для :любого у(0) * X • последовательность . итераций, построенных по , асинхронному итерационному методу (G\ сходится к р/действенной непод-, вижной точке оператора F в X. .

Пусть qn - количество макроитераций в п - 'ом шаге асинхронного процесса. Получена оценка скорости сходимости

Г Чп '->

асинхронного процесса Г; i - Ilm log р(Ь). ЭфФс-к-

тивность Е - асинхронного процесса ..

С] я

Е £ - Ilm f --") log р (L), гле cn - характериз^т П—к» ^П J

затраты при вычислении п итераций (количество арифметических операций). Для асинхронных итераций сп= (| J, | + ..

+ |Jnl). f n . где! Л j I - равно количеству элементов множества -Jj. Вероятностные модели асинхронного процесса изучается § 2 главы 1. Рассматривается система линейных алгебраических уравнений вида v = A v + В, где А - матрица порядка N. Пусть каждую компоненту (или группу компонент) вычисляет отдельный процессор и за'случайный промежуток времени каждый процессор успевает завершить п - ю итерацию. Пусть время успешной итерации подчиняется рэсп-.. редёлению Бернулли. £(п) - случайное значение в п - ом ■ шаге итерации.

Теорема. Если р (А) <1, то lira М f(n) = Т\ где v ре-

п—>~j>

шение системы.

, Пусть р - вероятность успешного вычисления отдельного шага итерации.

Теорема- Если время успешной итерации процессором п - го

шага подчиняется закону Пуассона с параметром = г р и

р (А) < i, то ' lim М ?(n) =v. . п—>®

В нашем случае количество'макроитераций ' qn- п р. Тогда для этого случая скорость сходимости асинхронного процесса

R > - .lim р log (р (I.)V. Эффективность Е £ -lim f U-1 log

П-+о) ' П C J

'..(p (!•)). Другими словами асинхронный процесс сходится к , неподвижной точке медленно, по сравнению с методом, простой итерации, а.эффективность увеличивается. Это подтверждается численными экспериментами. ■. В следующем § 3 введением релаксационного параметра изучены вопросы ускорения асинхронного итерационного процесса. Рассмотрено нелинейное операторное уравнение v - F (v)4-.

N

+ v , где ? - оператор определенный на К П И II j- гиль° - 3-1

бертовы пространства.Пусть F удовлетворяет условиям типа ■ • монотонности, т.е. для произвольного х и у «s H

(F(y) - F(x).x-y) г гх II x-y M * Il i'(x)-P(y)ll 8

s i-, (F(y) - F(x), x-y) (7) .

Определим оператор G с параметром P > О

G (y) = y + P (P (v) - v + vc), v - (5 (v) (8) Теорема. Если выполнены условия (7) и О <?, / (2 + тогда нелинейное операторное уравнение (8) имеет в II единственное решение для любого v0 « H. При Р * Р 0..т * (1+г,) / (1+ 2)-, р о

= ' ^ + гг2 + г\г2>

Теорема. Если хаотическая последовательность «Гп имеет максимальный осадок и р (Аопт) < 1/!'. тогда асинхронный процесс'для уравнения (8) сходится. .

Проведенныо вычислительные эксперименты для А х =f (9)

линейной систем алгебраических уравнений при' Р = 2/11 Л II показывают, что сходиморть асинхронного процесса явно ускоряется.

В последнем параграфе главы 1 приведены результаты ис-. следований связи метода Mcùxe-Карло асинхронных методов для многопроцессорных вычислительных систем. Оказалось, что для решения с..стем линейных алгебраических уравнений, условия,при которых сходится метод хаотической релаксации, близки к условиям применимости схемы Неймана-Улама, т.е. • ■ первое собственное число . модуля ' матрицы системы должно Оьгть меньше единицы. В - § 4 показано 'что ряд приёмов, , ■ развитых в теории, методов Монте-Карло с целью расширения • сферы их применимости расширяют также применимость хлоти- . ; -ческих релаксаций г Так, например; для решения системы X ■ .

-Вх + Р пусть сходится метод последовательных, приближений. Теорема.. Если хаотическая последовательность множеств'Jj,1/.' имеет максимальный осадок» и (В) <1, то существует

кое целое п > 0,-что сходится метод хаотических Hït?p3i:vfii.

Пусть ^jj (jA|) > 1-. Идею известного метода выделение

главной части для уменьшения дисперсии также мокно

.использован- совместно с асинхронными методами. Предполо-

m

жим, что существует матрица Aj вида Aj "^Sa^b^. где aj--

_ t < ** írií.T v.^íí» i,<r>4

= (aj ) , u^ (bj ) заданные линеино-

-нозависимш пасторы-Мокно выбрать так,что -nax( JA—А,!> -'L-

К = А - Aj, х s -Е (bJ(x) ¡Г1 + К~1Л

Теорема. Если единица на является точкой спектра матрицы А, то решенио уравнения А х = f можно найти решая я + 1 систем уравнения К и^ = ар 1 = 1,...,т, К w - /"асинхронным методом, затем .систему

и -1 ■ 1 (bj,x) s -jfi Cbi.x) (1С 1 aj,^) + (К 1л üj).

Выбор в качество a j и bj, J = l,i¡i , a-j = l).j - pj, где 3-й собственный вектор, является оптимальным в среднек-вадратической метрике для симметричной матрицы. Этот приём позволяет 'во многих случаях применить метод Монте-Карло и асинхронные методы к системам уравнений (3), для которых не выполняется условие (¡Ai) <1.

Другим приёмом, тесно связанным с теорией метода Монте-Карло является;использование блочных итераций (зекторных алгоритмов). Установлено, что блочно асинхронные итерации мог/т сходится в случаях когда расходится обычный асинхронный процесс. В работе рассмотрена в качестве примера краевая задача для бигармоничес кого уравнения azu л u |_ - О i ¿ u j„ - 0. Показано, что о с ли в бигармо ническоч оператора заменить производные соответствующими (четвертыми) разностями на правильной сетке, то для полученной системы уравнений невозможно применить асинхронные методы. Однако, если перейти к система л Ц = v, и |г = 0, ¿ v =¡jf. v '|r = 0, то показано, что построенный блочный асинхронный метод сходится. Примером асинхронных алгоритмов^могут служить алгоритмы метода Моте--Карло для решения уравнений. О частности,известная схема Неймана-Улама» использующая независимые реализации цепи Маркова, естественным образом

асинхронна. Оказалось, эффективные асинхронные - статиСти—, чйские алгоритмы 'для решения нелинейных уравнений тесно -v. связаны с ветвящимися марковскими процессами.. Первые результаты в этом направлении получены С. М* Ермаковым.. '

По второй главе разработана универсальная система асинх-т. ронно - .ст. гистических • алгоритмов, для' решения, класса, нелинейны,: краевых задач эллиптического "типа. В 4 1 пред- . ложек . статистический" алгоритм' решения квазилинейной.• краевой, задачи следующего вида -.-г.

■д и (X) - г (х,и(х)), и (X) = >>(х). х е D С К3 (10);

n \ . • . v ■'.' ■. ••

где f(x, u u)) =1Е а^х) гг(х) -ь Г (х), а^х) > 0»

1 = 1,п, г (х) - гладкие функции. Сконструированы и изучены вычислительные алгоритмы для реиения нелинейной крае- ,, вой задачи (10). Изучено поведение построенных несмещенных -.■"-' оценок и получены условия для .'конечности дисперсии; Пост--.-'; роен процесс "блуждания по сферам с ветвлением".Пусть М(х). среднее число ветвлений ■ для траекорий,выходящих -из точки .. х е D с if. Тогда справедлива . ' .'• , ' .. ' • Теорема. Среднее число ветвлений М (х) удовлетворяет ре- S

шению следующей краевой'задачи-Дирихле-в D :'•

п . ' • ' ' ' ■ 1 ■ ■ -'

Д М (х) ь с («п+1 + 1 - .1) И(х) = - са0, М(х)1г-0, ' :

где с - sug (о /(х.и)Л>и), 0< а^ < 1. ; ■.!

Теорема. -Среднее число ветвлений в.*построенном процессе "блуждания гю сферам с ветвлением" конечно тогда и только тогда, когда .sug'ic (b(x) '- i)> <>|.. . ... . *;'

Здесь К > 0 первое собственное чис .о задачи Д и(х)+

+ \ и (х) = 0, u (x)jr = 0. в В, Ъ (х) = (2^ i «! + .

+ ~ '-) C1 U) + 1, где q (х) = 1 - е -fc / Gh (р^с), р ~ радуис максимальной сферы. Подробно рассмотрена. .¡"р->'~ вам "адача ' ..''.".. Л .. ,;

Д Ч>:) =u\ х)' + u'x) |r=K x) sox.« -D ■

\ . Теорема. Для того чтобы задача (И) имела неотрицательное решение, необходимо и достаточно, чтобы решение и (:<}

; - . . 4' - — .. г»

. задачи,' Д u(x) - Дх). и(х)!г' - К*) было неотрицательным. Неотрицательное.решение (11) единственно. " ß § 2. главы 2-предложен модифицированный алгоритм пост-Y; ; роения несмещенных оценок, благодаря чему можно уменьшить '•V .." ■ дисперсию (увеличить эффективность алгоритма) построенных V ;... несмещенных оценок. Пусть последовательность к<?с-

. . мещенных. оценок- для решения и(х>. задачи (11) б точке у. * В. ■ ■. ■- Теорема.'-■■■Дисперсия оценки <t(x) при < «,-) удовлетворяет неравенству D ??(х) ' И ^°(х). где ^ > о.

■ . . Также получены условия» при которых дисперсия пост-.-"•• роенной оценки, м-шимальна (нуль). Асинхрошо-стэтистичес-

, -, • .-', кие'алгоритмы решения нелинейной задачи Неймана приведены в § 3.. Рассмотрена следующая задача- -д u(x) + E(x)U(x) -. = и(х)), <П1(Х)/<>П I .= о в ;< -н D с Р.". где п > 3.

;' • m . . 1 х 1

„-' . - Дх,и(х)).'=. Е ^-i(x) и (х). -Показаны способы моделирования ". - ■ 1=0 "* .

ветвящегося, , процесса' .. и на траектории процесса построены

несмещенные оценки 7 t(x) решения. Пусть d - диаметп облае -

■ та р, 0 < 1,.~1'~ 1,... ,m.+ J.

Теосема. Если ' ' < ? <*-г(п-Г -'if, nt»x U(с2-

—- ; - : ';'.. -.. • ; (х.у)

- G(y))p ' С (n-3)/(cV + с(п-;;:)М < то t ,.(x) яв-

ляьтся супермартингалом и-сходится с вероктп-.'-ггь») единица . к интегрируемой -случайной' величине CJx) и MY<':| (х) < -к». . В четвертом, параграфе '-рассмотрен случай в ('/■) с'. *. Дх,и(х))=b(х)uz(х), /Сх) ■ Пусть i»(x,y)«l-exif(-cp)(i+cp) .

;-- - ',: Теооена. .--"■ -Если - iax.-.<>-ЬОО'Х.'Гл» «Дх)< min ■ ■ ■. ■• • •■' , - ; , Cv • ' •' ■ л.уос

Ь*Нх,уj /;,ü ), тогда.'MjC.^x) < +<« и с ьероятносл-ю единица'; построенный .ветвящийся, процесс, вырождается. ; . '. - , Исследованию сравнительной, трудоёмкости оценок по гюг-,- -.'.;_. лощениям и по:столкновениям, в нелинейном случае посвящен 1з . .'.5"гл. i.. Ка примере,нелинейного интегрального уравнения

n m

m-1 D D 1,1 1 ' 1=1 1 1 1

где D с Itn, приведены некоторые рекомендации о выборе

оценок для увеличения эффективности алгоритма вычислений..

Пусть 1>с и 1>п - дисперсии оценок по столкновениям и по

поглощениям ~ нелинейном случае. G(x) = Дх)/(2Кх)~Ах)) ■

Теорема. Если f (х) г: о вероятность обрыва траекторий

ветвящегося процесса • « fo.mln G(x)), то справедливо

J x^D

неравенство Dc < Dn. . -

При f (х) < 0 утверждается, что Dn < Dc. Таким образом, используя априорную информацию о решении исследуемого уравнения, можно дать некоторые рекомендации о выборе каких- •. -либо из оценок. •

При решении краевых задач для конструирования асинхронно-статистических алгоритмов удобно использовать естест- . венные вероятностные представления. Однако они не всегда непосредственно приводят к пр остому Монте-Карловскому. алгоритму 'решения задачи^ Для прямой реализации вероятностных. представкой решения этих задач следовало бы моделировать процессы сложной .природы, что является весьма трудоёмкой процедурой. _ :

В главе 3 даются' вычислительные алгоритмы решения некоторых линейных и нелинейных■ диффузионных задач.При '. конструировании статистических алгоритмов использованы-. теоремы о среднем для параболических уравнений.В § 1 ^формулировании теоремы о среднем для параболических операто-. ров. Важным отличием Формул среднего в параболическом случае от формул среднег ■> дня эллиптически,, уравнений являет- , ся обращение ядер среднего в нуль и их неограниченность в

области интегрирования. В § 2 для оператора

tn

L = s/ i t - - а (t) Е о / о xi, а (t) > 0 (12) 1 1-1 1

рассмотрен.» начально краевая задача 1 u(x,t)=7(x,t),

rn

(x.t) е Й = Ь ГО,TU (X, г) - < V - - »xm-1> <S О. 11 с К% С

началькши и граничными условиями и(,х,^ = у(х,1;),,,х «з

д В, X с Ш,Т), и(х,0)= = пх), х « В (13).

Используя формулы параболического среднего для решения

задачи,записывается интегральное уравнение, ядро которо'го

является плотностью распределения случайной точки.

Моделируется цепь. Маркова, согласованная с интегральным уравнением. Основываясь на теории мартингалов^ доказывается сходимость процесса к граничной точке и приведена оценка для среднего числа шагов до попадания в « -окрестность границы области.На траекториях процесса строится последовательность несмещенных оценок и показывается,

что они образует квадратично интегрируемый мартингал.В § 3

к , К

для оператора I» & о / о 1 о / а * ^к-ь!

при ш = 2 К построен статистический алгоритм решения задачи (13). Вводятся матрицы размера (ш х ш) и разбиваются на квадратные блоки размера (К * к), которые в блочной записи имеют вид : О =. , а = 4,э1Г ] , й(.е>) =

11/2^ 10 = Хо Ь = (1/2) .). где

, - единичная матрица ХК * к) и а = Ь Ьт. Используя фундаментальное решение 2(х, и у,т) уравнения- Ь и = вводится область,зависящая от параметраV. Пусть 2('хД;у,г) =

= л"""г> «а»'-'г(1-т)-т ехр{-й(1/(^т))у-е"'5с1(1/(г-т))х)Т

К а (й(1/(^т))у - в'11 (1(1/(г-г))х)}, где 0 а а - опреде- .

литель матрицы а, - экспонента матрицы (-Р), е-^!,;,-^.

Область Ог(х,г)={(у,Ъ):г(х;г;у,т) > а- И"2 г2",

т <11- называется'"шароид"-ом радиуса г с центром в точке (х, Л), ОДх, 1) - "сфероид". Пусть г - г (х,Ч) >0 такое, что 0Г(.\ .Ю с о. Тогда используя формулы параболи- ,

ческого среднего для решения задачи (13) получим следующее интегральное представление u(x)= J-* ^(^"^(о)^11) * « u(y(e~p'2Ml)> тСе"^2")) da dp + /

- о а Ч1"2 r"2m J /(у,т) fly dr 4 (14),

где Sj(0) - (m-1) - мерная единичная Сфера, Н '<=

Sj(O) - единичный вектор,Р^р) = e'V^/r (l+m/2)

-плотность гамма-распределенной случайной величины г/,

к • параметром (1 4 т/2), Р2(Н) = + / '

г(х) = t - г2\2, у (х,Ц) ^ e~TKß х' + (2m inilA))1'2 «

* d (rV) b~?ll, - площадь . поверхности единичной, ш

- мерной сферы. Определим цепь Маркова (х^, t^j-p используя представление (14).

Теорема. . Марковская цепь •ix*', .сходится'при Ц—>«•

с вероятностью единица к случайной точке (хш, t") & о п.

На траектории Марковской цепи построим случайные вели- .' чины Равенством;: . . '"„•'.'

ч, = (tr/(nifl))l4w2 V Г2, /(y^^ +.'uix'U1), где. J=1 J

- случайная точка, пироида Q^x^,^) .Приведены модб-лируыщие формулы случайной точки (у^,. Теорема. Последовательность образует, мартингал .

относительно последовательности с-'- -алгебр ; Если

u , (x,t) < + м ¡1 и < + о). , то- 1/1 является -

/,0,0 И,0,0 1 ;.;'

квадратично интегрируемой. . • • / '•:

Здесь-3j_= ЧСр.. . ^^(у0^0), •. ((уН,г14)) '

где Cj - гамма, <*> - с плотностью р2(.И) распределенные случайные величины- Далее показана с - смещенность построй ■; енной оценки. Проведены вычислительные эксперименты .котоЦ ; рые подтвердили эффективность - и. работоспособностьпостро-,-

енных алгоритмов. Используя результаты предыдущих параграфов в § 4 построен асинхронно-статистический алгоритм

решения краевой задачи для уравнений параболического типа полиномиальной нелинейностью.При предположении существования-непрерывного решения задачи <> u(x,t)/a t - u(x,t) =

= £ c^x.t) u^x.t), (x,t) « Q (15),

1=0 • • •

U(x,t) = v<(x,t), X <3 Г, -t e 10,Tl, U(X,0) = p(x), x e"D, v

Q = D x 10,Tl, сконструирован алгоритм для численного

определения U(x,t) методом Монте-Карло. Пусть 1 > > О,

1 = 0,к ,Вг(х, 1;)-иароид радиуса г,с центром в точке (x,t). Теорема. Еслц г> О таков, что Br(x,t) с Q, то решение уравнения (15) удовлетворяет следующему соотношению : u (x,t) .= ^ Г (х, t). Здесь

М u(yJrTj) с вероятностью 1 ~ Чщ

(Г/ -<0)И( ехр(Ч )с0(у,т) —I— «о qm

Kx.t) = (1/a0jM((1-^'n exp(-0)Cj<y,r) и(?,т) ~s~«tqm

(r/agHtCU-v1** exp(-?))c2(y,r)u2(y,r) -«-«2qm

exp(4))ck(y,r)uk(y,r)

где y1 = x + (4 г р exp(-2p/ro))ly/z.Tj= t-r exp(-2p/m), . у = x. + (2 r m « с ехр(тО)"'2 "> т = t - г •с.'2'"" ехр (-<).,

qa = (1 + р. и ? - гамма-распределенные слу-

чайные величины с параметром (l+m/2) m/2 соответственно, 'f - бетта распределенная случайная величина с параметром (2,2/га), <•> - изотропный вектор.

Смоделирован ветвящийся процесс в Q и на траектории про цесса построена последовательность несмещенных оценок для u (x;t).

Теорема. Если г > 0 таково, что B^Cx-,t) с Q, г-r(х,t) < с min'( min ' «,.(• sup c«(x,t), l / snp c.(x,t)V, о Ü<i<!f, i^i (x",t)-c-Q . ■ (x,

последовательность образует супермартингэл отн-'-

сительно ^ гп = и( х, ^, Здесь - алгебра

порожденная.последовательностью тд,т,,. - ,тп,где Т0=(хД,1),

Т1 = • • ~ точечное распределение в

момент времени 1. 1

Вычислительные эксперименты . для случая с квадратичной нелинейностью проведены в § 5 г л 3. Для этого случая предложены оптимальные моделирующие формулы ветвящегося процесса. Результата § 3, способы решения уравнения неизотропной диффузии,обобщены на случай уравнений с полиномиальной нелинейностью з вестом параграфе. Пусть X = (Х1,..>ХП), х<4> = (Х^.^Х^), = (х]с+1... ,Х'П>,

(<?и/«>х(2)) = ( А х'1'-лапласиан

(&> 1 г ' ■

по переменным х , « с (<3), 1=0,2* (0 и /

«> ¡») к

)х и / )•

Рассмотрим краевую задачу : («П1 / <Н)- л Ц>ц ■» (<дд / о

X ♦

Х<2,)хш = ч^х.гХСх.Ч) + Чо(хД) КхЛ) (16).

и(х,г) = »- (хЛ), (х,г) « ¿в. Ю.Т), ' и (х»0) .= р (х), х « 3.

Уравнение (16) ввел и изучал Колмогоров А.Н. при =

- О для описания неизотропных ' диффузионных ■ процессов. Пусть суцу "твует решение уравнения (16) с соответствующими начальными и краевыми условиями. Используя известные приёмы статистического моделирования предложена асинхронно^ -статастическая вычислительная схема реиекия задачи. ' Теорема. С вероятностью единица построенный везящийс'я . процесс либо вырождается, либо сходится к точечному, распределению ^ = (х1,п^.0,..,х1с,пк,гк),д/1Я которого х{«\ «я 0 при п —» вд. Среднее число ветвлений меньше единицы \. и координаты точечного процесса образуют ограниченный мар-- V.

\

тннгал.

Теорема. Пусть t> <1/2 r(x,t) для любого (x,t) е «г О.Тогда построенная последовательность iT>n3n--l *на тРаек~ торгах ветвящегося процесса, образует ограниченный мартингал и чт(х'\t°) является несмещенной оценкой решения задачи в точке (x°,t°) где т -марковский момент.

В § 7 обоснованы две асинхронно-статистические вычислительные схемы для задачи теплопроводности с нелинейными граничными условиями и сравнивается их эффективность. Пусть X - (XpX^Xg), t с- [0,tl, r^ - внутренняя норм ль к границе г области D « П4. Рассмотрим задачу : u(x,t) / ot =

AU(3C,t)+/(XrtJ:,U(x,0)ip1<X),-«U/enx lr^2(X,t,H(x,t)) (17).

По физическому закону охлаждения .Ньютона функция

, «>2(x,t»u(x,t)) строго возрастает по ' и. Нелинейность на границе появляется при очень высоких и низких температурах. Рассмотрены различные методы линеаризации на примере i>2('x,tvU(x,t),) = uz(x,t). При первом способе линеаризации нелинейный член u2(x,t) приближенно заменяется u'n>(x,t) х

* u'"*"(x,t),'где п - шаг.итерации. Пусть с = (sup *,(х),

х 1

если Дх) ^ о, . lnl я,(х), если Дх) >0).

■ Теорема. . итерационное реиение u (x,t) при п —» о>; если ,<пГ(х,ъу/.я^ Ir = - u<n>(x>t) u'n""(x,t) сходится к решению задачи (17). . . ,'.

Второй способ связан с ветвящимися' процессами. Здесь: впервнз подробно описывается методик^» использовг ля оценки по. "столкновениям" в нелинейном случае. Сравниваются два метода . решения -сеточного.- -аналога : уравнения теплопроводности '; при г нелинейных Граничных ., условиях. Устанавливается преимущество метода, связанного с ветвящимися , процессами в многомерном случае со. сложной формой границ области;D. Сконструированная асинхронно - статиста-чаская вычислительная схема, применена для решения'нелинейной задачи теплотехники б следующем v 8:. Рассматривает- ■

ся случай 1>о(х,»(х)) = - с. иг(хг,0 + Л.Здесь с - ВА, А=

- В и* / х, где х - коэффициент теп л о про во/а юс ти, В -

* .

- некоторая константа, и.р - температура окружающей среды.

Разлагая производную <'й (х„, >?,. в ряд Тейлора на от-

II г

резке внут1>енней нормали длиной 1 по степени 1 и.удерживая

члены до первого порядка малости включительно и решая относительно ис.хг,г) получим и(хгД)=1>2и2Сх1,г)-|р1иСх1,1) + + Р0А, где Р2 = с 1/з, р^- 1/в, р0= 1/з, з.= 1 + 1 + с1. Алгоритм таков, что после попадания блуждающей частицы на . г. - окрестность границы с вероятность» р-. рождаются две' равноценные частицы в точке .Хр с вероятность» р^ - одна частица,а с вероятностью р0блуждащая частица поглощается.. Использован алгоритм блуждания по сферам с ветвлением. Оценка температуры производилась в точке, равноудаленной от образующих цилиндрических поверхностей и--перемещающейся вдоль продольной оси. Область состоит из ограниченных друХч коаксиальных цилиндрических поверхностей с наружным и внутренними радиусами Гц и Р^ и конечной длиной -Ь.

Кроме того; предположено» что-' вещество изотропно относительно теплофизических характеристик, а они от температуры не зависят. Задачи в такой постановке встречаются в разработке автономной системы охлаждения некоторых теплотехнических установок.. В <з 9. при помощи ао..лроино-ста-тистического алгоритма решена сопряжейная краевая задача. При формировании моделирующих Формул и уравнений на границе используется физическая сущность изучаемого процесса. Результаты вычислительного эксперимента показывают, что для решения сопряженных задач можно эффективно применять алгоритм "блуждания по .сферам"'"в сочетании с алгоритмом "блуждания но сетке". При этом отметим, .что до попадания : блуждающей частицы на « - окрестность сопряженной < раницы работает алгоритм "блуждания по:сферам",и до выхода из неё '■ работает алгоритм "блуждания, по сетке". Б а Ю развивается >■ новый подход построения аеинхронно-сгатестического : алго- ' •

- ?Л ~

ритма решения первой краевой задачи для параболических уравнений с полиномиальной нелинейностью. Пусть С| > 0,с>, ДхД), 1>(х), >/<х, I) - таковы, что существует единственное непрерывное решение залами (<т(хД) / <Н) - а Ц(хД) + с^.КхД) = с?н2(хЛ)+'/(х,1), (хД) о (18),

11(хД) = = У-(хД) 2: О, X Т>. X в С0,Т1, и(х,0) - *> (х) 2: 0, хеБ , где 0=1)« 10,Т1. Задача (18) эквивалентна следующему интегральному уравнению ■

К1(х^;у,г)и(у,т)с1уат ь

+ К2(х,1;у1,г1;у2,г2) »(Ур^Жуо, Г,,) йу^Ь^у^г,,

+ 7(хД) (19), где

.0, ' если (хД) е <30,

' _г(1/2)(г--(г-т))Сог1.(х,г;у1,т1) я ■ = )(у1,Т1)'" в(угу2) *(т1Гт2).

если (хД) е 0; о если (хД)^С1

^хД) = { г •'

Ч"(х, О, Лсли х о '/-'(>) если х - 13

Здесь ?.(х'Д;У,т) - фундаментальное решение уравнения тсп-лопроводности, У'Г<~ х, 1;;у,.г) = г(хД;у,т)-(4нг>)-т-'5,-,0г(х 1)-■ - шароид. <?СЗг(хД) - сфероид радуиса г с центром в (х Д) • 1д(хД) - индикатор множества А,<5(х) обобщенная Функция.

П Ь 1»

.Обозначим (хД) = (Хру,..^,^), О11 = (! - ... * 0, ¡с к- •

" (Хр^;.. = П* . »(х^Д^, ^(с1ул1г) - веро-

ятностная мера, сосродл'!\.ченизя в точке (хД). Сведем интегральный оператор в;'с ядром !С((хД)п,(с!у,<.1г)'\>, где К((хД)п,(ау,с1г)к) =..'

о .. п-1 . , 1 з к < г - 1

' К = 11 * 11

' К1(х1Д1;у1.т1)'(1у1аг1 1;=п/п й

. С1т1 . ) , К = П+1, П < К ■ 1-е 1 1

О а остальных случаях при' некотором достаточно большом N. Тогда уравнению (19)

можно сопоставить систему лине иных уравнений ч = +

т — т " I- „

где « , -Пусть Е-^ О ч (х,1) ,

» - минимальная - алгебра содержащая Е. Рассмотрим марковскую цепь с фазовым пространством (Е,5), с соответствующим начальны,! распределением и плотностями перехода. Пусть т=1 -(1/2)((т+2)/(га+4))**ы/г, (х,1)° - поглощающей состояние. ?0 = (х,г>, -т-,^,.. Марковская цепь с начальным распределением ^(dy.tif) и переходной функцией .Р((х^)",(ау,аг)к), кр((х,1)п,(у,т)к)=К.((х^)'\(йу,(1г)^ /

/ р «х, •*)"> (Чу, ао!:).

Теорема- Пусть Ъ + 1 - момент обрыва марковской цепи-и. |с21 <'С11га-с/З, '^пах^ Их,г)! < (2/3) Ч1т СГ Тогда.

случайная величина V - ¡^(Ср,^). ... /

.'/ е шляется несмещенной оценкой: для 1.) я ц(х,1) и дисперсия её конечна. -.'

Здесь б(?) = Е(хД) - вероятность обрыва1 Марковской цепи. Сконстуиросана с -'емзщенн'ая, но практически реализуемая оценгаи показано, что - и(х, 0( . < М.Д(0> где А(.) - модуга. непрерывности.функции и(х,ц). Алгоритм удобен в том отношении, что известно шкеима-льное возмощное число частиц. Результата, вычислительного эксперимента покаывают, 'что эти алгоритмы более эффективны,чем в случае' моделирования ветвящегося процесса. . '

Для решения интегральных уравнений, которые получаются-'; при решении краевых задач,•возможно построить алгоритмы

статистического моделирования", когда ряд Неймана для майорантного уравнения сходится. Однако, многие интегральны* уравнения,к которым сводятся краевые задачи нуудовлетворяют этому условию. Солее того, ряд Неймана может расходится. Существуют различные способы констуировання асинхронно-статистических алгоритмов в таких случаях. Среди них эффективным оказалось использование Пале аппроксимации резольвенты, которая рассмотрена в главе 4. 8 частности пусть

*Чх) = К(х,у) <КУ)(1У + Дх), где В с ТС. Для Т^;^,),).

и» л

где П(х) - произвольная-функция, имеем (»>,h) - Е с.,хх.

1-0

где cn = .. -Гц h(y1)lC(y1,y2)...K(yn_1,yn)Ayn)<Iy1..clyu-Для решения интегральных уравнений предпочтительно использовать диагональные аппроксимации Паде.Б 5 1 главы 4 рассмотрен случай когда. сп вычисляется методом Монте-Карло. В чатности установлено, когда |cn-c^j < «sn < <5, где "с^ -

- монте-кэрловская оценка, то

N 1-inix 1/lnR Jn|x I/1 nU

*

Здесь R-радуис сходимости резольвенты, sup |П,(7) |=M

n

Если лежит внутри крута сходимости ряда t .

то можно брать N -■ Nq достаточно большое, если нет,тс моагчо выбрать на основе информации о характере погрешности в коэффициентах "с^. ¡.'аилучиая оценка имеет порядок (5l-lnIxj/].:R при н _ ^ inCMol\tl/(o(R-|xj;,))/Jn 11. Метод Монте-Карло дзет значение коэффициентов с.п со случайной погрешностью и анализ погрешностей' коэффициент'.-в дробно-полиномиального приближения является сложной задачей. Поэтому в § 2 главы ,4 предлагается. испол! окять метод стохастической - аппроксимации. Использование ^того метода дает возможность построить последовательную дуру оценивания коэффициентов и -указать асимптотичес;,'^--распределение погрешностей. Пусть.сп = гл<» <<п,п -

- мерная случайная'1''ол!*ми1!-.| с заданной слтн-?;п-й и-»'!!-- . ре деления.' Дли опред^лч'нпл r.-nK'ntyteinvi'. vi'iit«.*" куп:!*» П<-

де нужно решить систему линейных алгебраических уравнений

С b = - с" (20), где cjj =

c=(cu+1,..,cL+M), b = (Ъм,...bj). l,m - степени полиномов

аппроксимации Паде. Пусть 0 < « <1, Л,В- некоторые

постоянные, Ь*~ точное решение системы (20), ^-минимальное собственное значение матрицы С-

Теорема. Пусто для всех b, и СЬ и < Л » Ь н-В, >. b > 1,

lnit (b - b\ Cb +"с) >0, Если *<»b-b t<lA

И » tcb(^) + V bM_j cL_M+J (<vW3< +

то P (lim b"°=b* } = 1, M в b"°-l)V 0 при к -».»и k—«>

порядок СХОДИМОСТИ II bifc'- b*n = о (1/к).

В первой главе для решения интегрального уравнения (1) с полиномиальной нелинейностью получена система линейных уравнений (2) - (3). В § 3 главы 4 »заменив интегралы системы на квадратурные суммы,получим систему линейных алгебраических уравнений. Для решения полученной*системы предложен алгоритм матричной аппроксимации Паде..Б § 4 метод стохастический аппроксимации применен совместно с. аппроксимацией Паде для решения систем интегральных уравнений. Результаты вычислительного эксперимента показывают, что матричную аппроксимацию Паде можно успешно использовать при peiaei. ¡и систем интегральных уравнений.

Глава 5 посвящена разработке и обоснованию асинхронпо-- статистических алгоритмов для определения наименьшего (основного) уровня энергии уравнения Шредингера. Рассмотрим Ну = Д v - f(x)v = х ч>. Это-уравнение описывает поведение кзантовомехан1;ческой частицы в силовом полр, задаваемом потенциалом Чх). Наименьшее сооственное значение"

оператора И соответствует ос.нс?яюму. уровню энергии, части*

- 2Ь. ~ ■

цы. В § 1 исследуется предложенный Калосом алгоритм метода Монте-Карло для вычисления энергии основного состояния многочастичной системы. Этот алгоритм в модифицированном виде используется для решения нестационарного уравнения Шредингера в 5 2 главы 2. Рассмотрим N частиц с гамильтонианом Н = - Da + <Чх), где D = (l/2m), m - масса каждой частицы (дня простоты мы ограничимся случаем равных масс). Пусть хт- постоянный сдвиг начала отсчрта энергии. \

Тогда уравнение Шредингера принимает вид : (-Mx.iJ)/^) = (Н-^т)Кх» (21).

Введем упр'авлющую функцию . vT(x). Пусть -Тх.гО = vT(x)

v< х, ri), тогда вместо (21) запишем эквивалентное

уравнение эволюции Г(х,р+г)=х Рв{х,т ,т) ехр С- <V"Vr > кг ,п) dx', где

pd(x,x',t) - диффузионная матрица ши люсти (функция Грина), соответствующая диффузии и сносу от.х к х',

-SN/2 2

pd(x,x',t) =■ (2nnr) ехр t-tx-x'-т P(x')i > / 4dt

P(>,s> = 2» v"1 v v'T> xb(x)=v~1li vT. Если использовать точную матрицу плотности, то получим

Дх,Р+т) = s p(x,x',T)e"V (v1,(x)/vT(x,))Ax'- 1) ttx*.

Выбирая произвольную плотность рт (в частности ядро » --мерного гармонического осциллятора)'* получим интегральное уравнение для точной матрицы плотности p(x,x',/3) =Рт(Х,Х' ,Р) + f CtP'f d;<"p(x,x",^-/?')K(x",x',ri'), где ядро К(х",х' .Р') - - ГНХ„ + o/Wi i>T(x",x' ,Р').

Осуществляя преобразования Лапласа получим интепхзльное уравнение,которое не зависит.от Р.Далее предложен алгоритм решения полученного уравнения и способы вычисления энергии основного состояния: Предложенный алгоритм имеет существенное ограничение, ядро К должно быть.'полпэгит^льнш.Предлагаются способы обхода -¿того ограничения. В _?< ирод.-т-н новый асинуpoHiio-CTaTiKTSiM-rrкий алгоритм для .¡"«-имя im-

стационарного уравнения 01р«дингера. Подучено интегральное уравнение для неизвестной функции Грина (матрицы плотное-, ти), ядро которого является функцией плотности вероятностей. Энергию основного состояния можно- вычислить двумя способами : по изменениям размера семейства конфигураций и усреднением локальной энергии. При К =-3, рассматриваются только дау/час тачные потенциалы. В § 4 в качестве кеэтас-тичногс. ваиыодействия выбран известный Корнельский потенциал V(r) = - « / г + г / а2 + с, с параметрами * -0.52,

а = 2.34,-с - -0.975.tn - 0.33, временной шаг 0.5. В» результате численного '¡эксперимента для энергии основного состояния получен - 0.0902 -t 0,0023, который согласуется с результатами расчетов (Себрикова F>. G - и др., которые вычисляяи основное-состояние методом Монте-Карло.

Задачи газовой динамики могут, служить примером задач, .для решения которых .необходимо использование современных многопроцессорных компьютеров. В частности, многомерное уравнение Больцмаиа для своего решения требует использование такой техники. Сложный характер ядра этого, уравнения и гависимость решения от многих переменных обусловили необходимость применения метода Монте-Карло.Этот м<под; как известно, особенно удобен для многопроцессорных ЭВМ и

допускает естественное распараллеливание..

В главе С предложены . статистические алгоритмы • решения

нелинейного уравнения . Сольцмана в пространственно

неоднородном и пространственно однородном . случае,

элективно реализуем!,>е на параллельных вычислительных

системах. Подход к решению . нелинейного уравнения

Больцмана на основе моделирования ветвящихся ' щоцесеив

был прйдяожен С.М.Ермякоиым. Г-.В.Иекрушш построил

кетвящийся процесс "1-*мамций" широкий *'

кинетических уравнений. В главе б продолжены эти исслс-л-.'-.

оания и построена одна из нелинейных ветвящихся моделей для решения уравнений типа Больцмана. В § 1 с (формулирована постановка задачи. Рассмотрим нелинейное интегральное уравнение вида

Ft(clr,du) = Pq<<lr-ut,clu)e>pf-ll(r, u) clsfexp {-ПСг.и)»

» (t-3)) VD 'It-3(llp'(lli:ri',1.,rz-u1) lUr^uJPgttfr^nu,) x '

. ?а{Ст2Л\г) 1 (22), где

(Г,и) a De if « flr\ (rj.Uj) « D при 1=1.2, t e R. 1

Р{.?0-|,нры в D , Щг.и)- неотрицательная функция, Tt-j/B.l^.Uj,!^,^) - при боре леве ком Визшртаяфункция аргументов ; • (^,1^,^,1!,.), а при §кксированних (rt>u,»ra»u2) - мзра в D. !,fepu Pt, ?0, Tt_3 считаются неотрицдтслыипли^. Подробно рассматривается .частный случай, когда ll(r»u) Ч с = con3t, В § 2 рассматривается случай когда мери irPg имеют плотность' (абсолютно непрерывны). После вспомогательных преобразований получается интегральное уравнение, которое названо "основным уравнением". Оно имеет следующий.тл :

rt(r,u) = /o(r-ut,u)exp (-ct) + (l-expi-ctl)jr^ ds /(з) -" fW <1 ~ PUjUa(r-n(t-s)-rx)) /gir-iiit-s).»!)^^,^)« '

* ^ PUc.,u_llclw>U(_+|u_Uclu(r-u(t-3)-r2)x

* » rs(r-u(t-3),uc-|u-uch ) •^(r^iij.+lq-u^K ) dr du, (2o)

Здесь f,(a) = с охр С- c(t-3)) / (V -VpC^ct)),

pu ^(r) = (а(и,,иг)/(4/3)« -sc >.П(|Г| < *) • где s( |r| < e) - индякатор множества Jr} < с, . ,

f «г| ПРИ 1«,-Uj < Cj,

°<W. S [<7 С, при ln.-llj 2t-cr

, » = n йг, где d - диаметр молекулы газа,

с = Cj о / (4/3)" -с3, •«> - изотропный единичный вектор.

В параграфе 3 конструируется случайный ветвящийся мар- . ковский процесс, на траекториях которого вычисляется несмещенная оценка функционала (Ii,./)» где г,u) ~ заданная функция. Предлагаются для решения уравнения (23) вероятностные, вычислительные. схемы, которые являются аналогом' "сопряженной" вычислительной схемы в линейном случае.Доказывается теорема об оптимальном выборе марковской ц^-пи.Получены уравнения для M(r,u,.t) - среднего числа ветвлений для траектории, выходящих из точки (r.u,t).

Применение построенных "сопряженных" вероятностных вычислительных схем'к конкретным Физическим задачам приводится, в 5 4. Получены результаты; которые' согласуются с ранее известными численными результатами.

Б § 5 главы 6 рассмотрен пространственно однородный случай уравнения (22). Предлагается эффективная Мрнте-кар-ловская вычислительная схема для численной реализации первого этапа (столкновений частиц в ..ячейках), в известной статистической модели Белоцоркоаского-Яницкого "частиц в ячейках".Приведены результаты вычислительного эксперимента.

В заключение выражаю глубокую благодарность своему учителю С. Ы. Ермакову за освети и замечания, которые имели важное значение дпя выполнения настоящей работы.

Основные результаты диссертации опубликованы в следующих расотах : , ' . ■

1. Расулов'А.С. О методе Монте-Карло, связанном с игера- . ционными процессами'при введении релаксационного параметра. Вопросы вычислительной и прикладной:математики.' Таш- ' кент. ФАН. 1976, Вып.34, с..42-45.;-.

2. Расулов А.С.Континуальное интегрирование л задачах нелинейной диффузии. Вопросы. вычислительной . и прикладной математики. Ташкент. .1978. Вып. 51, с.129-137.

3. Расулов A.C. О вычислительной схеме метода Монте-Карло для решения нелинейного кинетического уравнения Больцмана.; Методы Мон-е-Карло в вычислительной математике и на тема та-

ческой физике.. Новосибирск. 1970, с- 152-160. • 4'. Расулов А-С. Эффективность двух моделей метода Монте-Карло для решения нелинейных задач. Прикладная математика' и механика. Труды ТаиГУ, Ташкент, 1903, с. 00-64.

■ 5. Расулов A.C. Об одном алгоритме метода Монте-Карло для решения нелинейной задачи Неймана. Приложения дкффереи-

■ циальных уравнений' в механике и теории управляемых процессов. Труды ТашГУ. Ташкент, 1Э85, с. G2-G5.

б.: Расулов A.C. Алгоритмы для решения некоторых линейных и нелинейных уравнений параболического типа. Методы Монте-Карло в вычислительной математике и математической физике. Новосибирск, 1985, с. 177-Ш. . 7. Расулов A.C. Конструирование несмещенных оценок для решения одной нелинейной задачи Неймана. -Алгоритмы и численные методы решения прикладной механики. Труды ТашГУ, Ташкент, 138S, с. 64-60. 4

8. Rasulov Л,S. Л simplset probability model оГ asycîiron-оиз iterations. -lecture "¡otea In Computer Selena. Berlln--ToKyo; SpringerVerlag. i9f>?f Vol.. 273, p. 113-115.

9. Расулов A.C.;,Алгоритм решения краевой задачи для нелинейного уравнения неизотропной диффузии.-Алгроитмы и численные методы ' решения" задач вычислительной и прикладной Математики.Труды ТашГУ, Ташкент,1988,с.61 -64.

10.. Расулов A.C. О решении нелинейной задачи неизотроннои диффузий. -Теория и алгоритмы статистического моделщлэва-. иия .Новосибирск, ВЦ СО АН СССР, 1533,с.41 -45.

11. Rasulo? A.S. Monte-Carlo solution of non-linear equation of diffusion. -Monte-Carlo methods ancl parallel, algp-

. rlthms; ®эгМ Scientific, Singapore-Hew Jersey-tondon' Hong Koos. 1989,p j03-1СГГ.

12. Расулов А-С. Об использовании процесса Роббинса-Монро в з'ппроксимации-'Пал» .резольвенты.-- Методы статис-таческого ¡.рделирования. ВЦ СО АН СССР, Новосибирск, 1990,

• ', -J3.- расулор А,С, .Сттустнческий алгоритм реюжия

уравнения одной динамической системы.- Тез.докл.на Международной научно технической конференции "Применение статистических методов в производстве и управлении". Пермь, 1990 ic.165-167.

14-. Расулов Л-С. О решении сметанной задачи для нелинейного обобщённого уравнения Колмогорова.- Методы Понте-Карло в вычислительной математике и математической Физик». Новосибирск,19Э1 ,с. 150-161,

15. Расулов A.C. Метод Ыдаге-Кадоо для решния нежной-

ннх задач.-Ташкент, Фан,1992. 104 с. (монография под.ред. проф.С.Ы. Ермакова Ь

16. Ермаков' С.И.,Расулов A.C. О. ропйнии методом. Монте-Карло уравнения теплопроводности при нелинейных граничных условиях,- Методы Монте-Карло в вычислительной математике и математическойфизике. Новосибирск, 1976,с .136-142.

.17.- расулов A.C.,Силин A.C. Решание одного нелинейного' . уравнения методом Ыоьте-Карло.- Методы Монте-Карло в вычислительной штематжв-« математической физике. Новосибирск,1976,с.149-155. . • . 18. Расулов А.С.уПушкэрЗв' Л.И. Решэнйя краевых задач с нелинейность» б граничном условии.- ¿опросы вычислитель- • ной и предавай матет^СТ.Сб.науч.тфудсч Института Кибериотики Респ .Узбекистан, вш. 61 .Таскент i960,с. <17-52-.

19. Ершкоа С.И.5Расулов А.С, Простейшая р^роятностная шдзль сстаропш ■вычислений!.*' *Тез. докл. Мй£дународного кснгрзсса "Основытеории вычисдем#%КйзааьЛ987.с.Ш-115

20. ' -Расулов А.С.,Бакоев М. Решит с»ити»'юй задач* для квазилинейных параболических уравнений мотодом Нонте-Кар-ло.~ I-ßceiuspfaüi конгресс , общества 0йрнуАУ..Теа.докл; . И.: Наука,1985,^472. ¡-•■,..'

2li EpißKüs C.iS.fPacyJipH А.С.^Бакоеа М.Т^Бвседоьская Ä.3. Избран! та азгоритю; штолз Нонте-('грло.Так^1ГГ,^н^рситйТ - ':. -1992,132с. (гйглграфия код рад.цл.корр.РАЦ -