Случайные инвариантные кубатуры и принцип суперпозиции в методе Монте-Карло тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

ВАН СЯО ЦЮНЬ

СЛУЧАЙНЫЕ ИНВАРИАНТНЫЕ КУБАТУРЫ И ПРИНЦИП СУПЕРПОЗИЦИИ В МЕТОДЕ МОНТЕ-КАРЛО

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

АВТОРЕФЕРАТ

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

САНКТ-ПЕТЕРБУРГ 1994 г.

Работа выполнена на кафедре статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель: доктор физ.-иат. наук, профессор С. М. Ермаков

Официальные оапояекты: доктор физ.-иат. наук, профессор Е. В. Седунов, кавдитат физ.-иат. наук, доцент Л. К. Иовомареижо.

Ведущая организация: Санкт-Петербургский государственный технический университет

Защита состоится ."^.-.У 1994 г. в часов

на заседании специализированного совета Д 063.57.30 по присуждению ученой степени доктора физико-математических ваук в Санкт-Петербургском государственном университете по адресу: 193904, Санкт-Петербург, Ст. Петергоф, Библиотечная пл., 2, ыатеыатико-мех&нический факультет СПбГУ.

С диссертацией можно ознакомиться о библиотеке им. М. Горького СПбГУ, Университетская наб., 7/й.

Автореферат разослал " ^ * \юяа

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

кандидат технических ваук, доцезт Ю.А.Сувшоо

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

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

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

Различные модификаций метода Монте-Карло разрабатываются. Трудоемкость - наиболее естественный критерий качества метода Монте-Карло. Воаросы, связанные с исследованием трудоемкости, являются актуальными и активно изучаются российскими и зарубежными учеными. Здесь следует стремиться к построению аффективных модификаций.

Центральное положение в методе Монте-Карло занимает вычисление интегралов. Вычисление интегралов само по себе является очень важной задачей вычислительной математики. Основополагающие результаты в этой области получены С.Л.Соболевым, И.П.Мысовскид и другими авторами. Несмотря на достигнутые здесь успехи, построение кубатурных формул для существенно многомерных областей остается очень трудной задачей. Это оставляет большие возможности для применения метода Монте-Карло.

Методу Монте-Карло посвящепы исследования Н.С.Бахвалова, С.М.Ермакова, Г.А.Михайлова, И.М.Соболя и др.

Различные случайные кубатуркые формулы были построены многими авторами. Случайные интерполяционно-кубатурные фор-

3

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

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

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

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

Общая методика выполнения исследование. В работе используется теория метода Монте-Карло, теория классических инвариантных кубатурных формул, теория планирования експеря-

4

мента, теория вероятностей и математической статистики и теория групп.

Научная новизна. В диссертации получены следующие новые результаты:

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

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

— Рассмотрены применения принципа суперпозиции. На основании принципа суперпозиции успешно комбинированы некоторые известные методы уменьшения дисперсии, при этом проиллюстрирована большая возможность и эффективность принципа суперпозиции.

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

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

Апробация. Основные результаты диссертационной работы докладывались: на семинаре кафедры статистического моделирования матеыатлко-механического факультета СПбГУ; па меж-

5

дународвой конференции по математический методам в компьютерной моделированием (Саикт-Петербург, 1994 г.).

Публикации. Результаты по теме диссертации опубликованы в работах [1,2].

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации составляет 119 страниц. Список литературы содержит 51 наименование.

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

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

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

В §1.1. дается краткий обзор истории, развития и современного состояния метода Монте-Карло.

В §1.2. приведены теорема Ермакова-Золотухина и результаты о случайных кубатурах с одним случайным узлом.

Пусть О — область ¿-мерного евклидова пространства Д*( — пространство функций, суммируемых с квадратом с весом р(х) в области 27.

Пусть /(а) € Ьг{0), и задан набор функций <р\{х).....у>»(*),

линейно-независимых в области О.

Общий подход построения случайных кубатур для вычисления интеграла ■/[/"] ь 1р\{х)}(х)р(х)с1х состоит в том, чтобы

(1) кубатурвая сумма является несмещенной оценкой интеграла ./(/| для каждой / из некоторого заданного класса С.

(2) для заданного набора функций Г дисперсия Кя[/] обращается в нуль.

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

6

Определим шгтерволядионно-кубатурпую сумму:

к»(Я = ай. 0 = .....«»>'

где Д|/,«?| .....¥>-.(*>)!!,"я1,

для всех () из множества {9: ^ 0}. Справедлива:

Теорема 1. (С.М.Ермаков, В.Г.Золотухии), Пусть /(г) € £'(0), если : {V«}" — система оргпонормированных функций, то

1. И'(ф) = ¿Да[<?]р(»1),... ,р[я„) является плотностью в Д.

2. Если Q вибираетсх слутйно с плотностью №(()), то а). К*[/] = является несмещенной оценкой У[/],-

б^. выгкмнжетаг неравенство:

ДК-1/1 < (/(*)- ЕГ«>(/.Р»ь)

Яри этом ддж регулярней системм {у>|}* име«т место равенство.

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

В §1.3. приведены необходимые понятия инвариантности и теорема С.Л.Соболева. Формула

^<? = (*..•••,*■,) (1)

называется инвариантной кубатурнай формулой относительно группы преобразований С?, если: 1®: область интегрирования О и взсовая функция р(х) инваритгатпы относительно £7; 2": совокупность узлов формулы (1) представляет собой объединение О-орбит, при этом узлам одной и той же орбиты сопоставляются одинаковые коэффициенты.

Теорема 2 (Соболев С.Л.) Для того чтобы хубатурная формула (1), инвариантная относительно преобразований группы О,

7

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

В диссертации доказана, что для того чтобы куб&турная формула (I) была инвариантной, необходимо и достаточно чтобы она могла аредставиыа в виде JD /(z)p(x)dr.sajr?_iCj(f(xj)}0, где {/(®>))с — среднее звачение функции }{х) по группе G, она определяется равенством

</<•>>■-у^Е™/^) (2)

Следует сразу заметить, что теорема. Соболева справедлива также, когда формула (1) является случайной инвариантной ку-батурной формулой.

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

В $2.1. изложен метод построения таких формуя.

Пусть О — конечная группа ортогональных преобразований Rk в себя (обычно G - ето некоторая группа преобразований правильного многогранника с центром в начале координат в себя). Ф конечномерное подпространство ¿'(^(обозначим через М его размерность). Предположим, что область D, весовая функция р(г) и подпространство Ф инвариантны относительно группы G. Предположим также, что нам ювестен^йнеЙно-независимых га-вариантных функций в пространстве Ф : V>i(e), ... ,V>k(z). Как показано в теории групп и в классической теории инвариантных кубатурных формуя, часто оказывается, что К < М.

Далее, предполагаем , что ipi — const, и нормирована, тогда легко доказать, что fD ф^г>)/(з)р(х:)<1х = jD V»(*)(/(*))ap(x)dx.

Для оценивания интеграла JD\pi(x)f(x)p{x)dx построим слу-

8

чайную сумму

Щ/, Q, т)1 - (3)

где Д[(/)0,$,®(*)} = detj |(/(®|)>в,Л(»|).....**(*!)!£,,

Д[<?,Ф(К-)1 = .....

Q = (*i.....*jr)e{Q:A[«?,»(ir)l?4 0}.

Теорема 3. Если: 1). линейно-независимые инвариантные функции в пространстве Ф являются: ..., 2). (я) = con«i. и ноями^оовмв, фг(х) ортогональна * 0j(s),...3). плотность совместного распределения узлов Xi,,..,хк является W(Q) = CA'IQ, Ф(АГ))р(аг,>1---»М®«-). где С — константа нормировки, то:

(1). случайная кубатурная формула

Jo

инвариантно относительно группа в;

(2). 6|/,ф,Ф(Я0] является несмещенной оценкой интеграла (ф\,/):

Ев[д<?,ф(*)] - №../);

(3). формула (4) точна для всея функций из 9; а также точна для всея функций h{z), если (Ь(х))а - 0;

(4). выполняется неравенство

D0[f,Q,nK)] < /о(Дз> " £<=1(/>ф')ф/)'р(*)<Ь (5)

гдеФ) в функции... —ортонормирований базис пространства функций, для ко тар их точна формула (4), первые М функций из низ являются базисом подпространства 9.

9

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

В сравнении» с методом Ермакова-Золотухина здесь трудность моделирования случайного вектора Q уменьшается (за счет уменьшения порядка определителя Л). Конструкция случайных сумм легче чем в формуле с одним свободным узлом (так как группа G задана заранее). Кроме того, случайная инвариантная формула точна не только для всех функций из Ф, но и автоматически точна для некоторых классов фушсций. Так что, точность оценок повышается.

В §2.2. указан один способ поиска инвариантных функций. Приведены некоторые конкретные примеры, которые иллюстрируют процесс построения случайных инвариантных кубатуриых формул. В качестве группы G можно использовать различные группы. Здесь мы используем "группу симметризации" и грутшу всех ортогональных преобразований гипероктаэдра в себя, построены случайные инвариантные кубатуры с m-свойством для некоторых видов областей.

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

Расчет (/(*)) 0 по формуле (2) не реален, если порядок группы G велик. В действительности вто и не нужно. Если введем разумную случайную величину u, и 6 С и определим вероятностную меру Р(ь>) такую, чтобы математическое ожидание Еf(u>x) = (/(i))0, тогда можем вычислить {/(х))0 методом Монте-Карло. Естественно, что такой подход сопровождает потерю точности. Другой подход предложен в главе 3, где группа <3 специально найдена из некоторых условий и имеет малый порядок.

Третья глава также посвящена задачам вычисления интегра-

10

лов. Предложен новый общий метод построения случайных кубатур повышенной точности.

В §3.1. приводятся необходимые определения v высказаны трудность и необходимость разработки новых методов построения случайных кубатур повышенной точности.

Совокупность (fcl/],C/(Q)), где /:[/] — оценка, U(Q) — функция распределения случайных узлов, будем называть процедурой метода Манте-Коуло (Процедурой ММК) для класса F, если выполняются: условия несмещепностл а условия конечности' дисперсии.

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

Разумным и выгодным подходом может оказаться "постепенное" достижение высокой точности: первоначально строим оценки со относительно небольшим числом случайных узлов Qf = (г'/',...,!»') (далее, Qj назовем "реплика"). Затем каким-то образом комбинировать эти оценки (т.е. из этих оценок строим новые оценки).

Вопрос состоит в том, как должны выбирать "реплики"? ( или каков закон их распределения?) Как комбинировать эти оценки?

В §3.2. изложен общий принцип суперпозиция для случайных кубатур. Основная идея заключается в следующем: разделить процесс построения процедуры ММК для вычисления интеграла J[f\ на два атапа: Этап А и Этап В.

Этап As Для функций класса F € £'(£>), построим процедуру ММК (&[/J,w) с т-свободнымн узлами: xi,x7,.. ,,xN. Обозначим Q = (xj,xj,...,xn). Несмещенность оценки ft[/,Q] выражается равенством:

V/ 6 F (в)

Этая Bi Пусть LJ(Drt) — пространство функций, суммиру-

\

11

\

емых с квадратом с весом и>(0) в области . Здесь функция ш(£}) рассматривается как весовая функция.

Для вычисления интеграла вида /¡>к 6

состроим процедуру метода Монте-Карло с Л/-свободньши

узлами:

(в[г,0,.....<?м],ИЧ<?>,..., <?*))• (7)

Теорема 4.

1. Совокупность (©¡Ь|/,<3],<51,...,(}«), 1У(<},,. • ,9м) являете* процедурой ММК для вычисления интеграла — ¡Пч>\{х){{х)р{х)6я, где процедуры (*[/, 9), ю(())) и <?ь...,<?«), \ViQu... ,9м)) построены на Этапе А и Этапе Б соответственно.

1. Если построенная процедура на Этапе Б (в, IV) (для класса "лучше" нем простейшая процедура (Р(()),и>{())) ( для класса в смысле величины дисперсии:

Т>ЦГ(0),()и...,()м)<ПРт VF(Q) € Ь1 (£>"), (8)

тогда Ов[Л|/,0],д,.....<?м] < ЛА[/, (?], У/(в) € ^ (9)

Принцип суперпозиции весьма общий, мы не налогаем ограничения на способы построения процедур ва Этапе А и Этапе Б. Степень уменьшения дисперсии зависит от качества процедуры построенной на Этапе Б.

В §3.3. и §3.4. рассмотрены применения принципа суперпозиции. С его помощью успешно комбинированы некоторые известные методы построения случайных кубатур. Это не только проиллюстрирована большая возможность принципа суперпозиции, но и сами втя формулы ( полученные с помощью принципа суперпозиции) являются общими и интересными.

В §3.3. изучены 2 случая:

случай "процедура Е-3 + процедура Б-3 " И случай "процедура Е-3 + процедура с одним свободным узлом". Здесь указаны

12

функция распределения "реплик" и методы комбинирования оценок, полученных при этих "репликах"; а также явно показана степень уменьшения дисперсии Об^!/,*}],^!,... ,(3м).

В §3.4. изучен случай "процедура с одним свободным узлом" + "процедура Е-3". Оказывается такой способ приведет к построению так называемых обобщенных случайных инвариантных формул, которые есть прямое расширение случайпых инвариантных формул, построенных в главе 2.

Здесь в отличие от главы 2, группа <7 заранее не задана, а нужно ее найти из некоторых условий. Эта группа преобразований в может быть не ортогоаальвал. Второч отличие состоит в том, что для заданной функции /(г), обобщенная средняя функция по группе (7 определяется равенством

где |/г| — якобианы преобразований Г € С. Формула вида !о называется обобщенной случайной

кубатурной формулой. Для таких формуя справедливы аналогичные утверждения Теоремы 3.

Здесь также показала возможность построения обобщенных классических (неслучайных) кубатурных формул, инвариантных относительно более общей, чем ортогональной группы преобразований. Доказал обобщение теоремы С.Л. Соболева.

Четвертая глава посвящена задачам несмещенного рандо-мизоваппого планирования эксперимента. Предложен принцип суперпозиции с целью увеличения эффективности.

В §4,1. даются необходимые определения и формальная постановка задачи.

Пусть у(х, и) — функция случайного аргумента ь и параметра х, Е»у(х,и) - ч(х) для калщой х € X. Пусть щ — реализации случайной функции у при х — {} = 1,,..

Предположим, что неизвестная функция регрессия г)(х) принадлежит пространству функций Г С <). Пусть {у9»(х)}Г

13

— заданный набор ортоворыиров анпых функций ш Г,

Функцию регрессии ч(х) будем приближать с помощью линейной комбинацией т/{х,у) = имел в своем распоряжении значения у,.

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

[ ц{х)<р,(х)ц(<1х), < = 1,...,т. (10)

4X

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

В §4.2. изложен принцип суперпозиции. Как в Главе 3, мы разделим процесс построения оценок ва два этапа:. Этап А и Этап В.

Этап А. У?(х) € Р, для оценивания ¡х т](х)<р^х)ц(<1х) («' = 1,... ,т) построим процедуру (&[7,<?1,«>(<2)), где 0 = (»,,.. распределена по закону по отношению к мере р". Здесь в

отличие от главы 3, мы требуем, чтобы функция распределения ш(<Э) была одинаковой для всех »,» = 1,...,т. Т.е. и>(0) является общей плотностью распределения для всех «.

Этап Б точно также, как в главе 3. Здесь для вычисления интеграла вида /„ Г(<?)ш(<?)А? (Р(()) е 1?(Хн,цы) построим процедуру метода Монте-Карло: (е|К,<?1 , ...,<3л/],...,Ом)).

Обозначим

Бели па Этапе А и Этапе В заменим г](х^ значениями наблю-дяний уу, то получим оценки и [у], тогда оценки б; [у]

14

будут отличаться от оценок Qj(ijJ, но справедлива

Теорема 5. Предположим, что у(х,и) — г/(х) + е(х,и), « для каждой г € X есть Eu *(*.«) = 0. Если совокупность $ [Д Q],w(Q))

— процедура ММК для класса F Ç L'(X, /i), а совокупность ^в, W^

— процедура ММК дл* масса L*( Обозначим метод 04e-нивания

Тогда

J, Пара (а,га) и пара (S,W) являются несмещенной процедурой рандомизованного планирования и анализа регрессионны* экспериментов.

2. Для каждой i (i = 1,... ,т), есть расделения

D^(u,Q] = D(;> + D« D ОД = D(s° + D^ где D<'> = D ¿M, Di'> в D êi\E, О]; Dg> = D eftlv.Ql], D« = DO^M)].

3. При предположении (8) имеем

Dy><D<'\ D^><Di'>.

D^ и D^ не зависят от случайной помехи, их сравнения произведено в главе 3. D^ и D,^ не зависят от функции регрессии 17(2), они определяются случайной ошибкой. Естественно, степень уменьшения дисперсий зависит от качества процедуры, построенной на Этапе Б.

Метод построения функционала в (.F, <Ji,..., Qjv] ва Этапе В — ото и есть метод комбинирования оиенвок в, (i/iQ>!. полученных при "репликах " Qj, {j = 1.....M). Положим F — ûifaQ) и получим новую оценку 64(17]. Функция распределения W(Qi,... ,Qu)

15

— вто и есть распределения "реплик" Qj(j — 1.....M)- "Реплик"

наблюдений должны выбираться случайно в соответствии с плотностью распределения W(CJi,. ,.,Qm).

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

В §4.3. рассмотрены применения принципа суперпозиции для несмещенного рандомизованного плава. Здесь явно показано, насколько дисперсии оценок, полученных на Этапе В, меньше чем дисперсии оценок, полученных на Этапе А. Также показано, что несмещенная процедура (5, W) может быть более эффективной чем многие другие процедуры.

Все предложенные в работе методы проиллюстрированы на конкретных примерах.

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

Публикации по теме диссертации

[1] Ermakov S. M., Wang Xiao Qun. Superposition principle for unbiased random quadrature formulas // International work shop on Mathematical methods and Tbob in computer simulation. St.-Petersburg. 1994, p. 52-53.

(2] Ермаков С. M., Ван Сяо Июнь. Случайные инвариантные кубатурные формулы //Веста. С-Петерб. ун-та, Сер.1, 1994. Вып.4.

1в