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

Санкт-Петербургский государственный университет

г Г 6 ОД

3 Г. /\ЗГ 1393

На правах рукописи

СОБОЛЕВСКИЙ ПАВЕЛ ИОСИФОВИЧ

УДК 517.987.1+519.644+51 :681.3.012

ПРИБЛИЖЕННЫЕ ЫЕТОДЫ ФУНКЦИОНАЛЬНОГО ИНТЕГРИРОВАНИЯ И ПРОБЛЕМЫ ИХ ЧИСЛЕННОЙ РЕАЛИЗАЦИИ

01.01.07 - вычислительная математика

Автореферат

диссертация на соискание ученой степени диктора физико-математических наук

Санкт-Петербург 1993

Работа выполнена в Институте математики Академии наук Веларус!

Официальные оппоненты: доктор физико-математических наук

Жидков Е.П.

доктор физико-математических наук Мысовских И.П.

доктор технических наук Садыхов Р.X.

Ведущая организация - Вычислительный центр Сибирского отделен

Российской Академии наук

Защита состоится " /У" 10 1993 г. в /3 час._мин

на заседании специализированного Совета Д 063.57.30 по защите

диссертаций на соискание ученой степени доктора физико-матема

тических наук в Санкт-Петербургском университете по адресу: 198904, Старый Петергоф, Библиотечная пл., 2, математико-меха нический факультет. Ауд. 01.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского университета.

Автореферат разослан " £ - о% 1993 г.

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

Ю.А.Сушк(

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность ^гемы. Функциональные (континуальные)

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

Для гауссо: jx мер исследования по построению приближенных формул, обладающих заданной степенью точности (точных для функциональных полиномов заданной степени) начатые Камероном Р.Х. и Владимировым B.C. наиболее полное развитие получили в работах Яновича JI.A., Егорова А.Д. и их учеников.

Однако практическое • использование построенных формул ограничено их большой вычислительной сложностью. Так, в частности, построенные составные приближенные формулы предполагают наличие методов вычисления несобственных интегралов, соответствующих многомерному нормальному распределению. Построение эффективных кубатур для этих интегралов произвольной кратности - задача сама по себе достаточно сложная и несомненно актуальная. Это же можно сказать и о построении кубатурных формул заданной (суммарной) степени точности для приближенного вычисления кратных интегралов и рядов, соответствующих другим безгранично делимым многомерным распределениям. В свою очередь кубатурные формулы благодаря своему естественному параллелизму эффективно реализовать на многопроцессорных вычислительных системах. Общая теория построения параллельных форм алгоритма, ориентированных на их отображение на многопроцессорные

вычислительные системы, в частности на систолические матрич^ процессоры на СБИС, далека от завершения и ее развитие та* является актуальной задачей.

й§ль_Еаботы. Исследована проблемы приближение вычисления функциональных интегралов по мерам, задавав! характеристическим функционалом общего вида, включающее в с< разработку приближенных методов, программного обеспечения, также проектирование систолических матричных спецпроцессоре!

ПЕ§£122§£5§9_2_!®2Е®122ё££ЙЗ_значимост)ь. Полученные диссертации теоретические результаты и разработанные мен вносят следующий вклад в теорию функциональн интегрирования:

1. Построены операторы разделенной разности, не тре-ую дифференцируемости функционала. Определен класс мер, которых степень точности приближенной интерполяцион формулы с построенным оператором разделенной разности мо быть повышена специальным выбором узлов интерполирования

2. Предложен новый метод построения элементарных и состав формул для континуальных интегралов, основанный на линей аппроксимациях характеристического функционала, сохраняю заданное число моментов.

3. Построены и исследованы элементарные и составные форь заданной степени точности для приближенного вычисле континуальных интегралов, порождаемых однород! процессами с независимыми приращениями со значениями в <3*1.

4. Выделен клас- континуальных интегралов, включа] интегралы Винера и Пуассона, для которого предложен м< построения приближенных формул заданной степени точно* основанный на интерполяционных способах улучш сходимос 'и последовательностей.

5. Предложен катод построения кубатурных формул зада суммарной степени точности для кратных вероятное интегралов, и рядов, основанный на применении приближе методов континуального интегрирования.

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

Предложенные методы могут быть использованы для 1зработки эффективных алгоритмов приближенного вычисления штинуальных интегралов для широкого класса мер..

Созданная библиотека прикладных программ прошла юударственную регистрацию, включена в государственный реестр эограмм для ЭВМ ГКВТИ СССР и получила широкое юлространение

Разработанные методы проектирования систолических атричных процессоров позволили спроектировать

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

. Все результаты, сформулированные в виде емм, теорем, приближенных формул и методов, являются новыми.

Публикации. По результатам исследований в рамках данной иссертации опубликовано 64 работы, включая две монографии, ,ва выпуска библиотеки научных программ, 24 изобретения СССР, юновные результаты диссертации опубликованы в главах 4,5,7,8 юнографий [1,2] и в статьях [3-40]. Участие автора в ювместных работах с учениками выражалось в постановке задач и [аритетном выполнении этих работ. .

Апп2обация_ваботы^ Основные результаты диссертации • были федставлены и докладывались на международном конгрессе ттематиков, Варшава, 1982 г., на международной конференции 'Parallel Cmlputing Technologies", Новосибирск, 1991 г., на /II Всесоюзном совещании "Методы Монте-Карло в вычислительной математике и математической физике", Новосибирск, 1985 г., на

II Всесоюзной конференции по актуальным проблемам информатики и вычислительной техники,- Ереван, 1987, на I Всесоюзной конференции "Однородные вычислительные среды и систолические структуры", Львов, 1990 г., на республиканских конференциях, на семинарах в Институте математики АН Беларуси, Санкт-Петербургском университете, Объединенном институте ядерных исследований г.Дубна.

Объем и структура диссертации. Диссертация состоит и;, введения, пяти глав, разбитых на параграфы, списка литература из 217 наименований и приложения. Объем основного тексту диссертации - 359 страниц, включая 6 таблиц и 21 рисунок.

СОДЕРЖАНИЕ РАБОТЫ

Рассматриваем: э в диссертации континуальные интеграль от функционалов Г, заданных на линейнок

топологическом пространстве X с мерой ц, . определяются характеристическими функционалами вида

Х(1)"^1(х)ц(<1х) - ехрШ(ш) + 1(р((1]

где 1 - произвольный линейный непрерывный функционал на X, " 9к к

£ ~£г,аг) — заданная ана-итическая в окрестности нул» к-2 К'

функция, и- среднее значение меры ц, (V ,<1} - некоторое

метрическое пространство (УсК, б - метрика), V - конечная мер« на и, р(и):и Х- заданное отображение. Если X - некоторое пространство функций х(Ь) на отре-<е [0,Т)сй, то функциона; (1) можно рассматривать как характеристический функциона.) случайного процесса

х^р^и^СсЫ + ть, ЬеТ (2]

где < - стохастическая ортогональная мера о

^^(.Ч), а континуальный интеграл

^•(х)и((1х)-ЫР(х)

■южно определять как математическое ожидание функционала Г от случайного процесса.

Необходимые определения и сведения приведены в начале первой главы, а также вводятся в процессе изложения материала циссертации.

Первая глава диссертации посвящена построению и исследованию приближенных формул, основанных на интегрировании интерполяционных полиномов Ньютона.

§1.1 носит вспомогательный характер. Здесь дается эпределение оператора разделенной разности (ОРР) лз-ого порядка ?[х0;...¡хт], построенного по заданному функционалу ^ и узлам Гф,...,хтеХ. Определение содержит требование, чтобы оператор разделенной разности ш-ого порядка чнулировал произвольный функциональный многочлен степени меньше т. Рассмотрен случай кратных узлов (интерполирование Эрмита) и связь с формулой Гейлора.

§1.2 посвящен построению конкретных операторов разделенных разностей. В основе построения лежит оператор разделенной разности первого порядка Р[х0;х^].

Известный ОРР в пространстве Ь2[0,1] имеет вид

Г^х0;х17й=||гЧх0+т(х_1-х0; .бЖйЖсЬг, (3)

и требует вычисления двукратного интеграла от производной функционала Г.

Используя интеграл Римана-Стилтьеса от функции действительного переменного те[а,Ь]сШ со значением в пространстве X и эбобщение понятия отрезка, соединяющего две точки х0,х^Х: KQ+g^(xJ-x0), где g - линейный оператор из X в X, зависящий эт параметра хе[а,Ь], такой, что ga(x)-О, £к(х.'=х для любого

а . О

кеХ (О- нулевой элемент пространства X), получен новый опера-гор разделенной разности (Лемма 1.1)

Е[х0;х1]Ь=]Р'(х^у:(х1-х0),Ь)11(Ь№т.(1}), (4)

который в случае специального выбора приводится к вид!

не требующему дифференцируемости функционала

со

(х,р(и))р(и)\г(с1и), (х.у)- £ У>.

к-1 К *

^к^ ' ,2..... - базис в X', а р(и): (а ,Ь]—Х и мера V на [а

таковы, что х—^(х,р(и)р(и)1г(с}и).

Построен дискретный аналог оператора разделенной разнос в пространстве X с базисом (ек}, к-1,2,...,

1—1 1 1 и

где 1^а)-га)-£а-1), ё^х)-^ <^к.х>ек. а {£к

к-1,2,..., - дуальный базис.

Теоремы 1.1 и 1.2 определяют ОРР высших порядков, исхо, из ОРР (4;, а теоремы 1.3 и 1.4 - исходя из ОРР (5).

Построены дискретные операторы разделенных разност высших порядков. Показано, что ОРР, " примененные цилиндрическим функционалам, приводят к формулам, совподающ с разделенными разностями соответствующих порядков функц многих переменных.

В §1!3 исследов'на задача повышения точности ;риближенн формул, основанных на линейном интерполировании интегрируемо функционала. Показано (Теорема 1.5), что если корреляциони функционал меры К(1,1)=^12(х-т)ц(с}х) не вырожден,

приближенную интерполяционную формулу с ОРР (3) нельзя сделе точной длг произвольных полиномов второй степени ника* выбором узлов интерполяции. Показано также (Теорема 1.6), I если корреляционный функционал меры допускает представление

где ё(х)

-

КС 1,1)—J (gjp))dl (gjq))'

~tJ^l(p(T))l(p(s))(p,p(min(r,s)))(q,p(vax(T,s))>i>(dT)v(ds),

о степень точности интерполяционной формулы можно повысить на дин порядок специальным выбором узлов интерполирования.

Приближенная интерполяционная формула второй степени очности имеет вид:

« F(nn-cq)-

~о2\ ft*'P(x)) d F(m+cq+-Lg (р-с2q)). (7)

i (p-czq,p(x)) c x

В частности, для континуальных интегралов, порождаемых щнородными процессами с независимыми приращениями, формула 7) -меет вид:

}JF(x) и F(m( -)+с)+

—|ydF(m(-)+c - —-Х, rl(t)((-)<r9+c2)), с*0. b <т2Ь+сг с {-.и J

Получен дискретный аналог приближенной формулы (7).

В конечномерном случае полученное условие на

корреляционный функционал равносильно требовании, чтобы

элементы b^., i,j—l,2.....N, корреляционной матрицы В имели

вид Ь. .-p">^(i,j)qwaX(i,j) ^ J

В частности, для приближенного вычисления кратного интеграла

* ,

— f(ц,,...,им; х

,-гги- Ь 1 N

/(2п) П (t.-t.,) R v i-1 1 1 J

N (u.-u, ,)2

exp{"2" -i r-1 "1(t)

получена приближенная интерполяционная формула второй j степени точности

N 2 t, t .

Iff; « f(c.....с) + I _£_73v.fC---1.....-~.c.....c),

i-1 tfti* 10 c

c*0.

Построенные в первой г аве приближенные формулы основанные на интегрировании интерполяционных полиномов, имею фиксированную алгебраическую степень точности, совпадающую с степенью интерполяционного полинома. Теоремы 1.5 и 1. показывают принципиальные трудности, возникающие при желани повысить степень точности специальным выбором узло интерполирования.

Во второй главе предложен другой метод построени приближенных формул заданной степени точности, основанный н линейных приближениях характеристических функциоьалов сохраняющих заданное число моментов. При той же, что и интерполяционных формулах кратности интегралов, входящих аппроксимирующие в: >ажения, формулы имеют в два раза боле высокую степень точности.

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

В §2.3 построена аппроксимация процесса

e(tN-n)+ P(tN)i + m(t) (е

fW) w

где -T.ek<*> а ек(Ь) " pt(tk} либ

ek(t) - j { Pt(u) v(du) (второй тип аппроксимации), здес

к 7к

~ независимые случайные ве ичины с распределение Р (d£). Независящий от случайный процесс ,г

определен линейной аппроксимацией своего характеристическог

функционала

„¿ххо™-"1) . ! + ? Г вш<х*<»»А(а>> * оГл2п+Ъ.

к=1 * 1Г Л

где коэффициенты , функции Хк(и) и мера определены

Теоремой 2.1 так, что аппроксимация (8) сохраняет при фиксированном N моменты до порядка 2л+1 включительно. На основе аппроксимации (8) построена приближенная формула (2п+1)-& степени точности

/ ГСх) и(с1х) « а) +

X я" (9)

икГ<Хк(и) +

Е екак. - п ? (<1*к).

к-1 К К к-1 к К

Показано (следствия 2.1, 2.2) существование бесчисленного множества формул типа (9), отличающихся количеством ¿-кратных интегралов по мере входящих в правую часть формулы.

Приближенные формулы типа (9), основанные на следствии 2.1

>

содержат в общем случае С2п-к+2 таких интегралов. В §2.4, §2.5 рассмотрено несколько конкретных типов характеристических функционалов, когда это число удалось уменьшить. В частности для таких интегралов как гауссовский, пуассоновский и некоторых других построены формулы рекуррентного типа, которые при переходе к новому л требуют вычисления лишь к+1 новых

V

к-кратных интегралов по мере

Получена, элементарная формула (2п+1)-И степени точности для приближенного вычисления пуассоновских континуальных интегралов

С 12л <

} Г(х) ц(с1х) » -- £ п (1 - (-1) " " ) х

X . <2»(Ю)а Ь-1

к

1 Пъ Е рСи.Я« + С-1/к уСГТ^Г) * т) vлídu;. ип * к-1 к а

которая требует для вычисления 2Л л-кратных интегралов по мере

I>п(йи). При а=0 она обращается в известную формулу для гауссовских интегралов.

Получено обобщение приведенной формулы на случай, когда в характеристическом функционале (1)

ссГ а

В

1

§2.6

О, а * О при р > 1. случайных

для случайных процессов определяемых характеристическими функционалами к-1 вк-1

-Р

а-Ц

аппроксимации вида N

¿=2,3..... pfc(u) - l[uj]<t)>

t е [О,Г], (1), где

построены

1,2,

на

[0,Т]

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

- (Ы)

случайные величины, ц^ независимые и при фиксированном N

одинаково распределенные случайные числа принимающие с

заданными вероятностями три определенных значения. Доказана

(лемма 2.1) сходимость характеристических функционалов

(N)

Jie-1-11* We"""" при

соотношение моментов:

Л

N —»со .

[р/2]-1

Получено (лемма 2.2)

М1р(ам) - Н1р(0 + z —а_ „Ш.

р — 4,5.....(первые четыре момента совпадают).

Используя интерполяционное преобразование степени

последовательности Sl !^(F) 1

—г- , i - 0,1, . . . , i интерполируются

(N) ■

N*

'), при котором величины точно, построена приближенная формула (2(i+j)+3)-й степени "^чности J

Fix) u(dx1 »

X

где

г ^ i+q (~1)1*ч'р(р*к )1 (р+к)

Г F(x) u(dx» « £ v(kn.....к-). Z ---—S 1 (F).

J П=п ч u J p=Q

4=0 4 " ° р=0 п!(1+ч-р)!

целочисленые параметры к^г. 1, д = 0,1......7.

коэффициенты ■■ определяются Теоремой 2.2. Напр

формула (21+3)-й степени точности (.7=0) имеет вид:

а

i (~l)i-pip*N)1 (p+N)

Г F(x) u(dx) « Z -:-s (F> (10)

£ p=0 p!(i-p)!

Показано (Теорема 2.3), что если F непрерывный hi Lo[0,T]

( w)

функционал,и семейство случайных величин ) равномерно

интегрируемо, то имеет место сходимость

S(N)(F) -*j F(x) fi(dx) при W-»cn . X

Если кроме того последовательность S^^(F) имеет почти алгебраический тип сходимост.», т.е.

сю г а<3 а«+1 аг^г(Ю

S (F) - Г F(x) u(dx) + — + ——г- + --- , а то.

Jx N4 N4 1 N 4

qtl, vr(N) О при Wи, то при qsisr-q приближенаая формула (10) будет давать погрешность порядка o(N~с}).

В третьей главе диссертации разработаны и исследованы методы приближенного вычисления континуальных интегралов по мерам, порождаемым однородными процессами с независимыми приращениями £fc, О s t s Г < <», удовлетворяющими условию О. При построении составных формул использованы аппроксимации процесса вида

-N

Е -m(tk))ek(t) + m(t), к

7 rain(t,t )

где ek(t) - l[t Tj(t) либо ек(Ь) =» -—, 0=t0<ti<...<tNsT.

vtk

В §3.1 построены составные формулы 1, 3, 5 степеней

точности и применены к вычислению интегралов Т

J exp(Jc(Cfc+ x)dt)f(ST+ x)u(dZ) = U(T.x), 0

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

В §3.2 лостроены формулы произвольной степени точности 2п+1. Так составная формула для пуассоновского континуального

интеграла имеет рекуррентный вид

I Г(х) ц(ох) « 4т"

X пГ N . (и)

п-1 к лп~к_1

- I

к=1 (п-к)! где

с.

, , 1.» N (МЬ^) * л _

--е п -*-е Ес^х

* (2Т)п сг7----см-0 ск/ Р-0 П

Е А(1 1) }.":?. Г I го+ .....1 —N 1 р к=1 Лк 'Ч'

где все параметры формулы определены в явном виде.

Для винеровского процесса, если его рассматривать как однородный процесс с независимыми приращениями, составная приближенная формула (%п+1)~й степени точности также имеет вид (11), только в данном случае

Г Г

--- Г.?.ГГГ Г(СГ/Я)1/2 х

х

л N Vш1п( • .Ь.) Е З1вп(и.)(1, ш . т1(-) - Т. 1 Пи^и-—

) +

.2

и ЧтпС-.Ь,,) N 1■

+ Е --— ) П -===- е^ък ¿([¿¿п.. . .¿и

к-1 ЧЬк

\-[ьк-гьк>- ь-1-2.....

Построенные в первых двух параграфах приближенные формул!

эбщьны на континуальные интегралы по мерам, порождаемым учайными процессами, представимыми стохастическими тетралами вида (2)

xt~lPb(u)d(iu+ a(t)' (12)

е Çu однородный процесс с независимыми приращениями, а а(Ъ) - заданные неслучайные функции.

В §3.3 с учетом представления (12) построен ряд составных мближенных формул произвольной (2п+1)-ой степени точности [я континуальных интегралов по условной меве Винера. В ютности, одна из простейших составных формул первой степени >чности имеет вид

F(x)d .х « ' ÏÏ

ЧтШ-.Ъь.) (•) И

«I - - '

Кк 24 t.

•Г р( Е 1к(----)) п ———- е2™к с!Ск.

¥ к-1 7 к*1

Для интегралов по условной мере Винера построены оставные формулы Владимирова (Теорема 3.2) точные для роизвольных функциональных полиномов третьей степени, а также ля функционалов вида 12(х - х^^)У(х), где 1 произвольный инейный непрерывный на С[0,Т] функционал, а V - заданный ункционал, удовлетворяющий определенным условиям.

В §3.4 этой главы построены и исследованы приближенные юрмулы заданной суммарной степени точности 2п+1 для «числения кратных континуальных интегралов, порождаемых >днородными процессами с независимыми приращениями , ОлЬ*Т<оа, принимающими значения , в

Получена система нелинейных алгебраических уравнений для зпределения числовых параметров приближенной формулы (Теоремы 3.3, 3.4). В частности, построенная элементарная формула ',2п+1)~й суммарной степени точности для й-кратного интеграла Зинера имеет вид

~пГ£ (Г) ¿1 а (п-к) I к ¿п

3(Л)СГ)--I \*\тт/п)1/2 ж

(2ТйГ з......0-1 д о

Х е[(За+1)/2)Ш1- аип •

ек-(0. ... ,0, 1 ,0.....0).

к (к)

В §3.5 доказана сходимость построенных состав» приближенных формул для кратных интегралов при аппроксимац: процесса ступенчатыми функциями

К 1 " *к+1

и ломанными

,м) N ЧтШЪ.Ь.) л с к-1 К

Определены условия сходимости (при N—> ю) составн: приближенных формул третьей суммарной степени точное (Теоремы 3.5, 3.7) и произвольной (2п+1)~й. степени точное (Теоремы 3.6,3.8).

В четвертой главе диссертации исследуются пробле] численной'реализации построенных приближенных формул.

В §4.1 построены кубатурные формулы заданной суммар» степени "точности для кратных несобственных вероятности интегралов и рядов, входящих в составные приближенные форму, континуального интегрирования. Метод получения иском1 кубатурных формул основан на применении элементари приближенных формул заданной степени точности к вычислен] континуальных интегралов от цилиндрических функционал«

(£)•=£(!}£+ .....). Важной особенностью полученных таким

1 N

разом кубатурных формул является то, что кратность тегралов (рядов), для которых строятся формулы, не имеет инципиального значения и входит в явные выражения для узлов коэффициентов формул как параметр.

Примерами построенных кубатурных формул могут служить |рмулы рекуррентного типа для кратных интегралов, ютветствующих многомерному нормальному распределению:

N 1 ~

.....^д-^-2'*«*- зг«^« -

ВТ у/2пЧк (13)

"I1 к пп~к г(к), ■ _ г(а)(£} ■ ¿1 п (п-к)! *К ТМ (£} •

[е

N П < уп, п

Б

[Г'Ь)--^- Е П ? . (£((Т/аУ1/2 Е е. ) +

(2Т)п 11.....±п"1 а=1 а а

7/Р п N

+ ¿(-(Т/пУ'^ £ е. )). Т - Е V , V >0, а=1 2а а=1

кубатурные формулы для вычисления кратных пуассоновских адов

1к

СО N (Ачк) К -АЧк , »

Е ГП,.....V П -е ш1я Ш С14)

имеет такой же рекурентный вид (13) с той лишь 13ницей, что в данном случае

= -1----Е П 7- Е х

(2Т)П .....Хк Р-о п

X /(А7 + Е е, + х£п> Е е .

Б"! Я в-р+1 3

А(±п)-1----, х[п)-0,5( 1±Л+4ХТ/п) ,

Л+4\Т/П '

N

Т - Е V., ----XV-

1=1 1

В §4.2 описанным выше методом получены кубатурн формулы, основанные на результатах §2.6. Относитель сходимости этих кубатур справедливо замечание сделанное в §2 о сходимости соответствующих формул для континуальн интегралов.

В §4.3 приведено краткое описание библиотеки прикладн программ приближенного вычисления кратных интегралов вида

, 1 „ .....иы> ¿А] аиг--аия- д>с

У (2ттА) К* ■ . ^ 1=1 '

винеровских континуальных интегралов

^ССх^.т^т}|ехр| |с('хт^х|-£('хт^ЙГх, кратных рядов

Я ¿Л е'**

£ га......¿„> п ,— . д.>0,

^.....¿^-о 1 " ¿"-2 \Г

и пуасоновских континуальных интегралов, соответствую! центрированному пуасоновскому процессу с параметром Л:

1^С(хг;.х)(!т}ио(с1х). |ехр/ .

Полное описание библиотеки программ приведено приложении.

Пятая глава диссертации посвящена задаче проектирова: систолических матричных спецпроцессоров для аппаратур реализации вычислительных алгоритмов. В первых трех парагра излагаются результаты, полученные в области разви формальных методов отображения алгоритмов вычислитель математики на систолические матричные спецпроцессоры.

В §5.1 предлагается систематический подход к юектированию систолических вычислителей (СВ) исходя из ггоритма, представленного в виде системы однородных ¡куррентных уравнений. Предлагаемый метод основан на эстроении вычислительного графа алгоритма и размещении его в -мерной целочисленной решетке 7й с последующим отбражением в зостранство 2Г (г-1,2,3).

При декомпозиции исходного алгоритма возникает проблема

гыковки (согласования) вычислительных графов, построенных для

рагментов алгоритма. В этом параграфе задача стыковки

эрмализована и найдены условия для пространственного и

ременного согласования двух вычислительных графов (Теорема

.1). Проектирование на основе вычислительного графа

лгоритма, размещенного в пространстве 2е*, физически

еализуемых г-мерных (г-1,2,3) систолических структур

существляется отображением с помощью линейного оператора с! г

:2 -»2 . Найдены необходимые и достаточные условия для орректности такого очбражения (Теорема 5.2). Получен снованный на этой теореме алгоритм, позволяющий для заданного -тображения тг найти множество всех допустимых таймирующих |ункций, определяющих параллельные формы исходного 1ЫЧ..слительного алгоритма. В §5.2 предложен метод достижения »дномерности при отображении я:2^-»2г.

В §5.3 предложен метод синтеза СВ, реализующих [терационные алгоритмы. Ключевыми особенностями предлагаемого «етода являются:

1. Построение вычислительных графов, выполняющих отдельное итерационные шаги алгоритма.

2. Получение с помощью метода стыковки бесконечной цепоч-<и вычислительных графов, согласованно выполняющих 1роизвольное число итераций и расположенных в цилиндре, циаметр которого не зависит от числа итераций.

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

вектор образующей цилиндра. Такое отображение позволяв получать систолические структуры. с числом процессорны элементов, че зависящим от числа итераций.

4. Выбор оптимального временного режима функционировани СВ (таймирования), согласованного с оператором отображения не зависящего от числа итераций.

Все полученные теоретические результаты проиллюстрирован конкретными примерами проектирования систолически вычислителей для решения таких задач как перемножение тре матриц (§5.1), двумерного дискретного преобразования Фурь (§5.2), решение частичной' проблемы собственных значени степенным методом (§5.3) и др.

Разработанные в первых трех параграфах методы применяютс в §5.4 при проектировании систолических спецпроцессоров дл реализации вычислительных алгоритмов континуальног интегрирования. В этом параграфе спроектирован систолически спецпроцессор для реализации кубатурных формул для вычислен« кратных интегралов (рядов) и формул для приближенног континуального интегрирования, основанных на вычислен» взвешенных сумм

меняющейся кратности (т=1,2,...). Доказана оптимальное1] временных характеристик спецпроцессора (Теорема 5.6).

Во второй части этого параграфа сроектирован двумернь систолический вычислитель для реализации приближенных методе континуального и кратного интегрирования, основанных I интерполяционном преобразования степени I числовс последовательности

т » 1

Е Е У<Ь)Х(Ь.....V

'т Ь"1

т

0-1.2.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В РАБОТАХ:

.. Егоров А.Д., Соболевский П.И., Янович Л.А. Приближенные методы_вычисления континуальных интегралов. - Мн: Наука и техника, 1985. - 310 с.

2. Egorov A., Sobolevsky P., Yanovich L. Functional Integrals: Approximate Evaluation and Applications. - Kluwer Acad. Publ., 1995. - 419p.

3. Соболевский П.И., Янович Л.A. О приближенном вычислении интегралов Винера // Becqi АН БССР. Сер.ф1з.-мат.навук. -

1970. - Н2. - С.22-31.

4. Соболевский П.И., Янович Л.А. О некоторых приближенных формулах для кратных интегралов Винера // Докл.АН СССР. -

1971. Т. 15, N7. - С.578-581.

5. Соболевский П.И., Янович Л.А. О некоторых формулах с действительными параметрами для приближенного вычисления интегралов по гауссовой мере // Докл.АН БССР. - 1972.

Т.16, N3. - С.197-200.

6. Соболевский П.И. Об оценке остатка одной приближенной формулы для интегралов по гауссовой мере // Весц1 АН БССР. Сер.ф1з.-мат.навук. - 1974. - N6. - С.50-57.

7. Соболевский П.И., Янович Л.А. О. формулах В.С.Владимирова для приближенного вычисления интегралов по гауссовой мере /У Докл.АН БССР. - 1974, - Т.18, N11. - С.965-968.

8. Соболевский П.И. Об одной формуле для приближенного вычисления интегралов по гауссовой мере // Becni АН БССР. Сер.ф1з.-мат.навук. - 1975. - NX. - С.44-47.

9. Соболевский П.И. Приближенные формулы для вычисления континуальных интегралов по гауссовой мере //Докл.АН БССР. - 1976. -.Т.20, .W4. - С.293-296.

10. Соболевский П.И. Интерполяция функционалов и' некоторые приближенные формулы для интегралов по гауссовой мере // Bec4i АН БССР. Сер.ф1з.-мат.навук. - 1975. - К2. - С.5-12.

11. Соболевский П.И. Некоторые формулы для приближенного

вычисления кратных интегралов по гауссовской мере / Докл.АН БССР. - 1976. - Т.20, N7. - С.585-588.

12. Егоров А.Д., Соболевский П.И. 0 линейных дифференциальны уравнениях с частными производными в функциональны пространствах // ДУ. - 1977. - Т.13, N9. - С.1716-1719.

13. Соболевский П.И. Аппроксимации условного винеровског процесса, сохраняющие заданное число моментов // Becni А БССР. Сер.ф1з.-мат.навук. - 1984. - N1. - С.3-8.

14. Соболевский П.И. Приближенное вычисление условны винеровских гконтинуальных интегралов. Элементарные составные формулы // Весц1 АН БССР. Сер.ф1з.-мат.навук. 1984. - N3. - С.6-11.

15. Соболевский П.И. О приближенном вычислении континуальны интегралов // Short communications (abstracts), XII, S, 15 18. Int. Congr. Math. - Warsiawa, 1982.

16. Соболевский П.И. О приближенном вычислении континуальны интегралов по некоторым мерам, задаваемым с помощь характеристического функционала // Докл.АН БССР. - 1976. Т.20, N10 - С.873-876.

17. Соболевский П. И. Один метод приближенного выделен* континуальных интегралов // ^окл.АН БССР. - 1977. - Т.23 NB. - С.677-680.

18. Соболевский П.И. Об одном методе . приближенного вычислен континуальных интегралов // Докл.АН БССР. - 1977. - Г.21 N10. - С.869-871.

19. Соболевский П.И. Составные приближенные формулы дз пуассоновских континуальных интегралов // Докл.АН БССР. 1978. - Т.22, N6. - С.492-495.

20. Соболевский П.И. Составные формулы для приближенно! вычисления континуальных интегралов, порождаемых линейные процессами пуассоновского типа // Докл.АН БССР. - 1978. Т.22, W11. - С.971-974.

21. Лиходед Н.А., Соболевский П.И. Составные формулы -д: приближенного вычисления континуальных интегралов i бесконечному г-распределению // Весц1 АН БСС1

Сер.фхз.-мат.навук. - 1979. - N5. - С.37-43.

. Соболевский П.И. Рекуррентные формулы для, приближенного вычисления пуассоновских континуальных интегралов // Докл.АН БССР. - 1981. - Т.25, N1. - С.5-8.

Лиходед H.A., Соболевский П.И. Составные формулы для приближенного вычисления континуальных интегралов по мерам, порождаемым г-процессом // Beciji АН БССР. Сер.ф1з.-мат.навук. - 1981. - N2. - С.27-32.

Соболевский П.И. О некоторых методах приближенного вычисления континуальных интегралов // Докл.АН БССР. -1982. - Т.26, N5. - С.397-400.

. Соболевский П.И. Аппроксимация одного класса континуальных и кратных интегралов, основанная на интерполяционных способах улучшения сходимости. - VII Всесоюзное совещание "Методы Монте-Карло в вычислительной математике и математической физике", 9-11 окт. Новосибирск, 1985. С.76-79.

I. Лиходед H.A., Соболевский П.И. Аппроксимации винеровских континуальных интегралов, основанные на интерполяционных способах улучшения сходимости // Докл.АН БССР. - 1985. -Т.29, N12 - С.1065-1067.

Лиходед H.A., Соболевский П.И. О приближенном вычислении одного класса континуальных и кратных интегралов // Весц1 АН БССР. Сер.ф1з.-мат.навук. - 1988. - W1. - С.3-8.

3. Лиходед H.A., Соболевский П.И. Об одном подходе к построению кубатурных формул заданной суммарной степени точности для кратных вероятностных интегралов // Докл.АН БССР. - 1984. - Т.28, N9. - С.773-776.

Э. Лиходед H.A., Соболевский П.И. Приближенное интегрирование с плотностями, соответствующими многомерным каноническим нормальным распределениям. Приближенное вычисление винеровских континуальных интегралов. - Программное обеспечение ЭВМ : Библиотека прикладных программ БИМ-М / АН БССР Ин-т математики. - Мн.,1987. - Вып.5 : Численный математический анализ. - 66с.

30. Лиходед Н.А., Соболевский П.И. Приближенное вычислена кратных интегралов с весами, соответствующими многомерны) пуассоновским распределениям, и пуассоновских континуальны: интегралов. - Программное обеспечение ЭВМ Библиотек! прикладных программ БИМ-М / АН БССР Ин-т математики. Мн.,1988. - Вып.14 : Численный математический анализ. 46с.

31. Лиходед Н.А., Соболевский П.И. Стыковка базовы систолических вычислителей// Докл. АН БССР. - 1989. - Т.33 N 5. - С.389-392.

32. Likhoded N.A., Sobolevskii P.I., Tiountchik A.A. Design о systolic arrays for iterative algorithms: eigenvalu computations. Proc. Int. Conf. Parallel Computin Technologies, Novosibirsk, USSR, Sept.7-11, 1991. Published by World Scientific, Singapore, New Jersey London, Hong Kong, 1991, P.129-138. (In English)

33. Kosianchouk V.V., Likhoded N.A., Sobolevskii P.I. Systoli architecture array synthesis. - Minsk, 1992. - 24p. (Preprint/ Institute of Mathematics, Acad. Sci. of Belarus No 6(484)). (In English)

34. Соболевский П.И., Лиходед Н.А. Внешняя стыковка пр реализации одношаговых итерационных процессов н систолических структурах. - Мн.,'. 1990. - 60с. - (Препринт АН БССР. Институт математики; N 15(415)).

35. Лиходед Н.А., Соболевский П.И., Тиунчик А.А. Один мете синтеза систолических структур, реализующих итерационна алгоритмы // Весц1 АНБ. Сер.ф1з.-мат.навук. - 1992, N 3-А С.109-113.

36. Лиходед Н.А., Соболевский П.И., Якуш В.П. Проектироваш систолических вычислителей двумерного дискретног преобразования Фурье. - Мн., 1988. - 44с. - ■ (Препринт/ / БССР. Институт математики; W 10(320)).

37. Косьянчук В.В. , Лиходед Н.А. , Соболевский П.И. Cmm систоличеслих вычислителей (на примере двумерной свертки; - Мн., 1988. - 34с. - (Препринт/ АН БССР. Инститз