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

т ид

1 5 «О!5.

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

На правах, рукописи УДК 519. 24

Мелас Вячеслав Борисович

МАТЕМАТИЧЕСКИЕ МЕТОДЫ ПЛАНИРОВАНИЯ ИМИТАЦИОННЫХ . И РЕГРЕССИОННЫХ ЭКСПЕРИМЕНТОВ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора фиэико-математических наук

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

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

Официальные оппоненты: доктор физико-математических наук, профессор Барабанов Никита Евгеньевич

доктор физико-математических наук, профессор Малптов Михаил Борисович

доктор физико-математических наук, профессор Пененко Владимир Викторович

Ведущая организация! Институт кибернетики имени В.м. Глушкова Академии Наук Украины

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

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

<¿2

Зашита диссертации состоится

в

часов на заседании специализированного совета

Автореферат разослан Учены! секретарь

Специализированного совета

доцент

В. А. С ушков

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

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

.Актуальность,темьг Проведение экспериментов указанных типов

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

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

з

построение)« траекторий случайных процессов. Соответствующая ветвь нетола Монте-Карло получила название имитационного или статистического моделирования (по английски -simulation). Последний тернии (статистическое моделирование) используется в русскоязычной литературе с целью подчеркнуть то обстоятельство,, что моделируемый случайный процесс описывает поведение исследуемой системы опосредованным способен. Методы имитационного и статистического моделирования сложных систем разрабатывались 11. П. Бусленко, И. Н. Коваленко, В. В-Калашниковым. К. А. Шнепсом и их учениками, а также рядом ученых США и Европы, в частности, Дж. фкшнакон, н. Крейнон, Л. Иглехартом и другини. Необходима подчеркнуть, что проведение имитационных экспериментов связано с большими затратами машинного времени, особенно при изучении вероятностей редких событий, определяющих отказ системы. В связи с этим одной из наиболее актуальных проблей имитационного и статистического моделирования сложных систем является оптимальное планирование имитационных экспериментов. В качестве нетодов планирования таких экспериментов могут выступать нетолы планирования регрессионных . экспериментов, разработка которых началась с исследований р.Фишера (30-е годы) и Дж. Кифара и Дж. ^ольфовица (60-е годы). Важный вклад в их развитие внесли В. В. Налимов, Н.П.Клепиков и С.Н.Соколов, С. И. Ермаков, В.В.Федоров, Г. К. Круг, Л.Б.Успенский, Н. Б. Иалютов и др.

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

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

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

уель.работы. Целью ванной работы является

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

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

- сравнение методов планирования имитационных экспериментов;

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

- разработка метода исследования Е-критерия оптимальности;

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

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

исследования. в работе применяются методы

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

&аучная_нрвизна.. Введено понятие плана имитационного

эксперимента по методу растепления и рулетки Как вероятностной меры, управляете* числом параллельно моделируемых траекторий.

Построена теория оптимального планирования таких экспериментов.

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

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

Получена теорема двойственности для критерия Е-оптиналы№ст».

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

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

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

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

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

Санкт-Петербургского университета, на Ленинградском городском

семинаре по теории вероятностей и математической статистике, на семинаре отдепа системного моделирования в Институте кибернетики АН УССР. Некоторые результаты докладывались на республиканских конференциях "Планирование экспериментов в Лабораторных и промышленных исследованиях" (Киев, Í98Ó и 1991). на V, vi, VIII, I* Всесоюзных конференциях по тонированию и автоматизации эксперимента в научных исследованиях (Москва,1977,1980, Ленинград, 1986, Москва,1989), на I. II я IV Всесоюзных конференциях "Перспективные методы планирования и анализа экспериментов при анализе случайных процессов к полей" IНальчик,1982, Севастополь, 19SS, Петрозаводск,1991), на Всесоюзной конференции "Актуальные проблемы вычислительной и прикладной математики" (Новосибирск, 1990), на Международной конференции "Актуальные проблемы вычислительной и прикладной натематики" (Новосибирск, 1931), Международной конференции по теории вероятностей и математической статистике (Вильнюс, 1989), Международном семинаре по кодельно-ориентировакноиу анализу данных (С.-Петербург.1992).

Публикации. По теме диссертации опубликовано свыше двадцати

работ, в тон числе монография (1) и справочник {2]. Основные результаты опубликованы в работах (1-16).

' Диссертация состоит из Введения, Десяти глав,

разбитых на 2 раздела, и заключения. Диссертация занимает 5СЬ" стр. машинописного текста. Библиография содержит í!¿ наименований.

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

Раздел I посвящен математической теории планирования имитационных экспериментов. В главе 1 содержится обзор проблем этой теории.

Имитационным экспериментом Htauxerc* висперямеет. ■ результате которого вычисляются величины

• hJ«,l,ctJl,i v(1)). i*i.a.... .aj). 1»1.г...,;и. 1-1.2.....Н

где (I(I><t)) - независимые ила зависимые траектории моделируемого случайного процесса (lit)), vd) " контролируемы«

параметры процесса, hjl.) - Функции из некоторого класса. По результатам эксперимента требуете* оценить аеяячят вяжа

где fk() ~ заданные функция, (?(t)) - случайны! процесс,

опясываюжя! появление исследуемо! системы, моторы! может и* совпадать с процессом (X(t)}. Выбор процесса I(t), величин v(1),

"(1)' т> и " Функций hjt. ) представляет задачу планирования

эксперимента. В этом общем я абстрактном «яде исследование проблены на представляется содержательным., в диссертация она ясследуется при более точном задания свойств случайного процесса (i(t)) я других объектов.

Дается краткий обзор осномп специальных . методов планирования имитационного эксперимента, обычно изучаемых под названкен методов ш.пяяения дисперсии (в англяйскон языке variance reduction techniques). Описаны методы существенно! выборка, расщепления-рулетки, аналитике-статистический метод, метод контролируемых переменных я непрямых оценок, поправок, обоих случайных чисел, случайных кубатурных формул. ' бается обзор результатов, относяляхся к этям методам.

Перечисленные методы, за исключением метода расщепления-рулетки, обладают высоко! эффективностью лишь при наличии значительной априорно» информации о; моделируемом процессе. При

алгоритмическом описании процесса возможность их применения весьма ограничена. Что же касается метода расщепления-рулетки, он свободен от этого недостатка, так как не требует моделирования случайных величин, распределение которых отличается от распределения величин, образующих исследуемы! случайны! процесс (за исключением величин с равномерным распределением). Этот метод может быть положен в основу универсальных процедур и включен в языки моделирования, внесте с тем, неснотря на ряд содержательных публикаций tl-З]. его исследование далеко от полноты. Значительная часть раздела I посвящена разработке теории этого метода пол названием нетода ветвления траекторий.

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

J(H) • PT R(1).. . RÎKÏhl k) + pTh(о),

где R( k) ( x, y) - P(k)(x,y)a(lc)( x,y>. ( P( k)t x, y) )x yiD - матрица вероятностей перехода дискретно! цепи Маркова, П • {О,1,...} или (1,2,...), а(К)(х,у) " заданные коэффициенты, bT(k) -

(Ых;Ю)хеП - вектор заданных функций, р - начальное распределение (1} Kahn H. Use of different Monte Carlo sampling techniques// Sinposium on Honte Carlo Methods. H.Ï., 1956.P.146-190.

[2] Огибин В. H. о применениях "расщепления и рулетки" в расчетах переноса частиц ' методом Монте-Карло// Метод Монте-Карло . в проблеме переноса излучений. M., 196Т. С. 72-82.

[3] Михайлов Г. t.Оптимизация весовых методов Монте-Карло.К. ,1987.

цели.

Лля однородных цепей Маркова исследуются функционалы

} - а™ - н» ¿!.0 РтР*Ь

И-»» 1 ' N4« ^ °

(в случае поглошающих цепей) и

• <>.Ь) ст 1

(в случае эргодических цепей), где л - стационарное распределение Цепи Маркова. Р - матрица перехода, Ьт» (Ы х>) - заданная функция.

В этой главе изучаются оценки функционала следующего вида

где 50, .....- траектория цепи (р. р( ) 1е1,м,

" "(и'^-гЛ'/РиИЧ-хЛь

Оценки такого вида введены фон Нейманом я Уланом (си. [ 4 )) и

широко используются, в работах по нетоду Монте-Карло, в

предположении однородности цепи и при Н -» ». Однако метод

исследования, основанный на введении стохастических соотношений,

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

как и конкретный вид результатов.

Через рч будем обозначать вектор с элементами,

являющимися произведением элементов ввнторов р и q, и

' 2 2 - матрицы с элементами Р ( х, у) и Р (х, у)/<2( х, у) соответственно.

- Пусть . фиктивная цепь ' Р'1)'1«1:н обладает следующим

СВОЙСТВОМ!

[4] Спанье Дж. , Гвлбар! Э. Иетод Монге-Карпо и задачи переноса нейтронов. И.. 1972. 281 с.

Ш» Р(1)(К, у) > О ВЫТвКа*Т, ЧТО Pj л (к, у) > р,

1-1,г.....и. х,у « о, ei)

«I p(kl > О M4TCK»*T, что р(х) >0, X « О. определим функцию |>Т(К) - (*>(x;k) lxtQs

»С• »{u-itj^iti + MN-k-l), H » k+1 * l. Пусгь f(X}0) • p(x?o> » h( x;N), x « (]. f(*.k+U . Ey^ C(l).k.11(x,y)V(H.)c.l,(x,y(i(y;k) +

♦ b(xiM-k-l), H « k > 1, где величины fix, k) * <(H.)t.1)(x.y) определяются при ?M_k_x-x

* CtH.jc_ltCx,yl • 1 ясли у нов противном случае.

Справедлива сладупш« творена.

Теорема г. Пусть (р. pj jjix«l:H " дискретная цепь Маркова и дли фиктивно! цепи «шюднено (1). тогда оценка ¿1(н) является несмещенно* оиенкр! функционала «

• - <Р*/Р. ■

. IIU». Zf(N-k)hik) - h2(k)>,

причем

EfJto| . hJ(H).

ЕЙкМ)2 - (B„„<N-»t)/P(N-k>Е(р(Ю)2 +

+ 2f(k+l)h<II-k-l» - Ih(N-k-l))J, 1(01 - p3/p, l*(k+l) - 1*4k) (R^Ck+ll/PU+lll,

N-l * к * 0.

Теорема 2.1 позволяет, о одной сторош. оценивать дисперсию воличиш 31(NJ по аыборк«, и. с другой стороны, построить оценку с нулево! дисперсна!.

Получен также явный вил опенок ммниииэирующих сунну

дисперсий при оценке нескольких функционалов.

В случае поглошающих цепей Маркова аналогичные результаты получены для оиенки

3 . üíf°:fiL

где g( x) • 1 - Ey P(x.y), k - нонер последнего шаге перед

поглощением. Если за N шагов поглощения не произошло, то принимается J2(н) • О.

Для поглощающих цепей оценки функционала $ и соответствующие результаты получены предельным переходом при Н -* «>, но они известны (см. (5)) и мы не будем приводить соответствующие формулировки.

Несмещенные оценки функционала ' ícT могут быть получены в

ранках двух подходов: регенеративного и связанного с рассмотрением вложенной цепи Соответствующие оиенки были ранее изучены М. Крейном и Д.Иглехартом (в) (регенеративный метод), И.О. Линником [7] и Ю.Н.Каштановым |8) (метод вложенной цепи; но такая

(5) Ермаков С.М. Меток Монте-Карло и смежные вопросы. М. , 1978. (в) Crane A.M., Iglehart O.L. Simulating (table stochastic eysten.

Ill Harcov chains // J.ACM. 1974. Vol.21, p.114-123. ' [7) Линник И.ю. Улучшение сходимости метода Монте-Карло в некоторых задачах массового обслуживания // Кибернетика. М 5. 1973. С. 129-132. {8] Каштанов to. Н. Некоторые способы уменьшения дисперсии при оценивании метолдом Монте-Карло фуннционалов от стационарного распределения марковской цепи // Вести. Лёнингр. ун-та. 1981, * 7. С. 42-49.

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

Глава 3 посвящена теории метода ветвления траекторий для дискретных цепей Маркова.

Для оценки функционала определенного ранее, предлагается

следующая конструкция. Пусть pik) - (PI x;k> )x6j/, k-o, 1.....и,

If\{О) - вектор-столбец с заданными положительными коэффициентами такой, что £Х/Нх;к)<». Определим процедуру

параллельного моделирования копий цепи Пусть на к-он

шаге моделируется некоторое количество {7^) независимых копий

цепи правило вычисления Tij, будет определено далее.

обозначин через и(х, у) - u^lx, у), к=1,2,...,Н-1, число копий,

осуществляющих переход из х в у:

eiU . х г111 - у i ■ i д Ч-l Xl y' 1 ..... u(x, уI

E*,y Vх-У

4*

k'

' Пусть ^ обозначают целую, а а дробную часть

вещественного числа а, г^(х,у) = 0, 1 * ..., ¡и|Х ^ I для

цепи с номером з.. (1-1,2.....х, у)) определим число г. (х,у)

1

формулой

Ц01 У;К) /Э(х;к-+1, если

r^ix.y) rii(k)(x,y)

i. > ß(y;k)/ß(x;k-l), Lß(y;kl/ßtx;k-l)j иначе, '

ine С- - случайная веиичина, определяемая одной яа слелуадцнх 1J

формул :

<V*r

гпе rtj. . aU(X у) ~ независимые случайные величины с равномерным распределением на отрезке [0,1],

Ç. - а + i./Их, у), (2)

1

гпе а - случайная величина с равномерным распределением на отрезке [О, 1].

Пусть {0} - фиктивное состояние пени, ßtx;0) - 1. Пуден считать, что на нулевой шаге цепь переходит из состояния {0} в состояние xsl с вероятностью Их). На нулевой шаге ноделируется т) - L независимых реализаций (копий) цепи (i^'k г °Ь "а к""

шаге (К-1,2.....U-1) каждая моделируемая копия, переходящая из

состояния х в состояние у заменяется r^ j ^tх. yl копияни,

моделируемыми далее независимо и стартующими из состояния у.

Jplh.-H) - (.1/1) ы^*1;

тле ^j.1' ( i" 1. ?......V^) ~ значения, прининаомыо копиями цепи

к г 0} на к-н шаге (они обозначаются так же, как

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

(р(х;0) - h(х;Н),

f{ x;k+l) - 0(|5)'*;У> »'( + h(x; N-k-1), k-0.1....H-l

Введен обозначения

1)- |>(ХЛ1-1С1-Е С|(к>(х,у) «>г| у)Ы-к»-(Е 01к)(х,у) »>( у;Ы-к))а, х«1[ И у«1 у«1

» #(0)Н» - Е Ну) у- (Е »'{у) ».(у/Н))а,

У«* У«* - Л. . .

0<х{к) .

гр(х;Н-к> - И ^ Кк1*.У) Ок(х.у) (|р( у(Н-к) у ;к-_ " , х»1,

г (0;Ы( - £ И у) ((Р( у ,-N1 >г у«1

гК1х,у> - У')■ »я1у) • Ю(г1 (р)(0,у)).-к»1.а,

Через (Ита)(у) будем обозначать компоненту вектора с

номером у, через Т^ - общее число моделируеных значений цепа

(общее число шагов всех копий)

т0 чк " . .... -Для случая счетного множества состояний предположим, что . кт|ь|(о) < «. 1Ы (к) < «, д<к,<з<к) < ». (3)"

к-1,2.....N-1. Для конечного кножества состояний эти неравенстве

тривиальны.

Предложенная здесь схема является более общей, чек схема ветвления в предшествующих работах (см. [1-3)1 и позволяет ввести понятие плана имитационного эксперимента' Определение. Набор дискретных вероятностных нер г(к) - {0(х)к)/ЕхР<х(к)). к-1, 2-----М-1,

определяющих процедуру параллельного моделирования независимых копий цепи назовем планом (имитационного) эксперимента (по методу ватвления траекторий!.

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

Творена ü'l для произвольно* дискретно* цепи Маркова, удовлетворяюще! сформулированному условно (3), каковы бы ни были положительные числа 0<x;k), k-1. . ... Н-1, х « I, величина-JpOwN) является несмещенной оценкой Функционала J(h;N>. При этом

h;N) -U/LIE^J £ j(prQ(k,My)p"liyik)t»Qf(y;N-k)+rQiy,H-k>J +

f (l/L) (D^tO.-NI «- rv(0;N)J э"1(0;0). <*>

E Tß ■ I, lEÜJlJ ит <2(k> ßt k) + 1). Важно отметить, что при использовании формулы (2) величины

i^lxjN-kl и r(,(0;N) имеют вид Oll/L). Отбрасывая соответствующие

члены в полученном представлении, для трудоемкости метода, определяемой как произведение CJ^Ih;NlET^lh;N> f получаем выражение вида

ZkXl c(i;k)0(i;k) E^f 1 ;k)p"X(i;k),

из которого план экслеринента, обеспечивающий наименьшую грудоемкость, получается в явном вида на основе неравенства Шварца. Оценки функционалов } и Jcj, строятся подобным образом ■

для них получены представления, аналогичные (4).

При этом введение зависимости коэффициентов Э(х;к) от номера шага оказывается излишним и под планом эксперимента понимается мера

г(х) • р(х)/£ 1(01х).

где (3( х) положительные числа (#(х|К) * /Их). k-1, 2,...).

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

Rp(h) = Zii(x)fi(x) .£Ti(x)|3~J(x)I>pi(x)f

г не

v(x) = Jp(x,dy)p2(y) - <Jp<x,dy)£(y))2, £(x) - р(х) при использовании Mxl-,? вместо h( x), а план, минимизирующий эту величину, имеет вид

r*(x) - const(Z> £(х))1/2. Для построена несмешанная оценка.

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

Колее сложной является задача нахождения планов ниниииз ирукяцих величину определителя дисперсионной матрицы. Как известно, этот критерий обеспечивает построение оценок с корреляционным эллипсоидом минимального объема [9]. Но аналогии с теорией регрессионного планирования такие планы можно назвать D-оптимальными. Ллл таких планоо автором получена теорема эквивалентности,. во многом аналогичная из вестной теореме Кифера-Вольфоиица (см. [9), гл.З), и итерационная процедура.

Изучены оценки метода ветвления для вероятности выхода случайного блуждания за горизонтальный барьер. В теореме 10.1 указано разложение, сходное с разложением в теореме 2. 1. D теореме 10.2 показано, что если распределение величины, определяющей случайное блуждание, {fix)}, х е П, удовлетворяет условиям

C_.fi*> е лх . а,

£(х) s С е~*х,

¡9] Ермаков с. и.. ¡Киглявский А. А. Математическая теория оптинального эксперимента. М. , 1987.

1 и цлн bei HHiiiei ос:я имитационного плана

/3(х) - fi*(x) - e"iX, х s х , ßlxi - /3*1хо), x > x0,

где t » niiri{A, а/2), произведение дисперсии оценки на среднюю алину xpdfeHгории (эффективноеть) имеет вид 0(е21п2(1/8), при а г 2л, 0(ÜV), V - «/А при А < а < 2*. при и * О, где б - оцениваемая величина (вероятность выхода случайного блуждания за прямую Y - X ).

Дополнительные результаты получены для конечной цели Маркова II = {о,1,.. , iu 1)), для которой вероятности перехода "вверх"

при 1*0) отличны от нуля только для ближаИпего

состояния ^ii+k"0, Такие цепи часто используются в

теории надежности {10]

В главе 4 осуществляется обобщение основных результатов глав

2 и 3 на случай общих цепей Маркова. Получены аналоги теорем

главы 2 для оценок функционалов ^ (fjj и Проводится изучение

оценок линейных функционалов от стационарного распределения. Основное допущение состоит в тон, что для функции вероятности перехода Pix.dy) существуют целое число raQ, неотрицательная

функция s(x) и вероятностная мера v такие, что го

Р °(х, В) г s(x) WB) (5)

*ри х е i, В б Л, где - измеримое пространство, на

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

flü] Коваленко И. Н. Исследования по анализу надежности сложных систем. Киев, 1976. 204 с.

из условия неприводимости иепи. Однако применение регенеративноги метода для построения оценок требует явного задания пары (в,v). Нахождение такой пары в обшей случае - сложная самостоятельная задача, выходящая за рамки диссертации. Однако для многих систем массового обслуживания пара ta.v) найдена в явная виде в ( 11 J Для класса цепей Наркова, удовлетворяющих условию (В), построена схема метода ветвления траекторий для оценки линейного функционала от стационарного распределения цепи Наркова

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

Пусть - О. 8а - в,- V*,..... V

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

е - Р{ вир 8 i.»l ■ И|*) ■ 1- 1|»|, о«ж»

hl и)

S, • О, Р{5 « dais ' t) - ?(и, t)du - f(u-t) - du,

1 n*1 n h(t)

где fi(u) < X • (h(u);h[u> > 0, J^flu, t)chi « 1>. Определи» оценку

К" - Kti-h,*>-

где z определяется соотношением < x,. . . , S^ij < x.

* A( 11

при некотором и (обозначим его п^) и е^ j ■ о, если такого п не существует, tsj,*') • траектория процесса {§„}. hl z)»ht о)/К( г). Справедливо следующее утверждение

[11JSigman К. Queues as Harris recurrent Marcov chains //Queueing systems. 1988. Vol,3. P. 179-198.

Теорема S. 1. При любом S « M оцеп«« в'являете« несмещенной, еункция

Й(Х~г>, Kl, 1 , иначе

принадлежат множеству функций И я Св^1' • О, EnJ • 0(1п(1/8))

при й(г) • const й*(«1.

Эта теорема указывает оценку о нулевой дисперсией. Пра замене Й(х) на известное асимптотическое представлена* М(х> _ conet ехр(-Ах)

данная оценка приобретает вид оценки, предложенной .Л. Зигмундом [12] из других соображений При этом дисперсия оценки при О -» О, как показал Д.Зигмунд, имеет вид Ив^1' - Ol в2).

В качестве альтернативы изучаются оценка регенеративного метода я их обобщение по методу ветвления Показано, что среднее время моделирования асах возникайте а процесса ветвления траекторий инеет вид Ol1п(1/в)J (такой же как у метода существенной выборка), а дисперсии оценки пр* использовании плана 0<У)" ехр(-Ху), ysx, ß{y) » ехр(-хх) пр« у>х н некоторых дополнительных ограничениях имеет вид 01 1/0»). Таким

образом, эффективность нетода ветвления блажа к эффективности метода существенно* выборки, однако последний требует ирделирования случайных величин с плотностью вала ft х)ехр( Ах)/с.

В главе s рассматривается задача агрегации яатыж имитационного моделирования'в еледупией постановке.. Пусть некоторая система моделируется до ее отказа.. Моменты откааоа при многократном

{12} Sigmund О. Inpotance sampling In the Honte Carlo study of шрч uentlal teats )l Ann.Stat. Vol.3.' P. 179-198.

K( z) - fi*(z)

вопроизведении траектории (с изменением начальных значений датчиков случайных чисел) можно рассматривать как независимые

случайные величины i с " тем же распределением.

Пусть плотность этого распределения известна с точностью до параметров в i икает вид

f(x,e> - 90<х> + E^e^lx), где Р|(х) - известные линейно-независимые функции, которые заданы и непрерывны на (О,а). Пусть внесто Z1,.. ., Zn используются лишь величины, равные числу значений Z^ в " 10. х^.' *2 • {хг х2),

• *x-i " 'xJc-l'"k1, а оценивание параметров производится по методу наиненьтих квадратов. Возникает задача выбора значений х^. которая является частным случаем обпей постановки,

сформулированной в главе 1.

Выделим nQ < п наблюдений и по ним (после указанной агрегации

данных) построим оценку нетода наименьших квадратов, а по »ставшимся "~п0 наблюдений построим оценку метода наименьших

иплпратов с использованием первой оценки для учета корреляций. Тогда дисперсионная матрица последней оценки имеет асимптотический вид (теорема 2. 2)

" п^п"" ^а-Л pi(x)dx JX »jCiOe*/^ f(x,0)dx)™

где " (х^,®). Найдена связь этой матрицы при т-к с

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

структуру задачи.

Раздел II диссертации посвящен развитии теории планировании регрессионных экспериментов. Результаты этого раздела актуальны как для указанной теории, так и для ее применения к планирование инитационных экспериментов. .

Глава 6 посвящена обзору некоторых основных направлений теории планирования регрессионных экспериментов,

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

Гт(х) - (*г(х).....*п<хИ. »(х) - (*1(х).....»в<х)1. п<п,

где Ф1(х).....*п(х) - ортонормировании* базис конечномерного

пространства функций, суммируемых с квадратом по мере Л(йх), определенной на а-алгебре подмножеств линейного топологического пространства I, Пусть результаты эксперимента ""(У^.....^н'*

описываются стандартной моделью линейной регрессии у^ - вт£(х3) + Су 1.1. г.., ..»I Н < п.

Под планом эксперимента понимается совокупность различных

точен 1:£»{х1.....хн). По результатам эксперимента необходимо

л т

построить модель (р(х) так, чтобы минимизировать величину

• } - Е Лвц|И*1 " вт«*»|2Ийх|.

где к - матрица линейного метода оценивания * **>■

При этом в классе линейных оценок минимум } постигается для обобщенной оценки метода наименьших квадратов. а план, доставлявший минимум величины ЛГ называется и. с.

I минимизирующим сманен») планок. Эта задача изучалась а работах (13-iSJ, но полученные ники результаты являются более общими.

Инструментом исследования служит матрица проектора 61£) «э Rn на подпространство Rn, порожденное линейными комбатами* векторов i(xx).....f(x„). Осн мпп результатом

является теорема экви>ал»нтности, которая, в частности, утверждает, что и. с. свойство плана равносильно! 1а) существованию ■ кубатурных формуя с весовыми функциями tjlxlkldn).....*и(х)Л(ах) я узлами * точках плана, которые точны

для всех обобщенных многочленов «ада eTf(x)|

(б) утверждению: tr18(<*)TT - в, (матрица Т имеет структуру

tlJOH, причем trfS(OT для любого плана.

Утверждение (а) позволяет, в частности, использовать теорему Соболев« об обобщенных многочленах, обращающихся в нуль а узлах кубатуршх формул. С помощью теоремы эквивалентности получена характеристика течем к. с. плана ял л случаи, когда *^(х) алгебраические мног'очлеш одно» или нескольких переменшх,

lit») Box e.K.f.,' Draper К.К. h basis tor selection of a respase surface design // J.Amer.Statist.Assoc. 1959. Vol.54, p. 623-654.

[14] Ермаков С.И.. Седуноа ЕВ. О несмещенных планах регрессионных экспериментов в конечномерных пространствах функций П Вестник ЛГУ, 1974, N 1. С. 12-ЕО. |1К) Седунов С. В. Несмещенное планирование и анализ регрессионных экспериментов в конечномерных пространствах функций // математические методы планировав*» эксперимента Новосибирск. 1981. С. 102-1*0.

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

(I-S( es>) f(xs+1) fT(xstlH I-S( езп

гда «s ■ <Х1.....V' «S+1 ■ <Х1.....

Глава S посвящена сформулироввнной н доказанной автором теореме двойственности для критерия Е-оптиналыюсти.

Пусть М(£| - матрица информации для непрерывного плана £ и стандартной модели регрессии НУ ■ eTf(x). План, максимизирующий

величину V ) в классе всевозножных непрерывных планов

называется Е-оптимальным. Получена следующая теорема

двойственности. Рассмотрим задачу: найти min 1/tr А.

где А пробегает множестпо всех неотрицательно определенных m х ш матриц, удовлетворяющих условию

паххеГ fT'x>Af<x» s 1. . Теорема 2. 1 утверждает, что указанная задача и задача нахождения Е-оптимального плана связаны соотношением

двойственности

min 1/tr* - sup Лт1п1М<е)>.

при отон в точках Е-оптинального плана х^ достигается равенство

1Т(Х|)АГ(ХА) - 1 (следствие 2.1).

Ранее аналогичная теорема для D-критерия была указана Свбсоном (16), общая теория (из которой, однако, трудно получить

(16) Sibson R. Од-optimality and duality // Progress in Statistics! Aesterdam, 1974, 2, p.677-692.

вышеприведенны! результат) построена почти одновременно с автором диссертации Пукепьсгейном (17). С помощью теоремы двойственности найдены Е-оптимальные планы для тригонометрической регрессии на отрезке.

Глава 9 посвящена минимаксным оценкам параметров регрессии в случае, когда до постановки эксперимента известно, что оцениваемый вектор принадлежит заданному множеству общего вида, специальные случаи этой задача (в которых удается получить явный вид оценки) рассматривались Куксом [18}, Куксом и Ольнаном (19) а другим» авторама {20]. В главе содержатся также результаты по одновременному оптимальному выбору оценки и плана.

Для стандартной модели Е{Ух10) • Хв качество плана £ • {Xj, ••••*„? * линейной оценки в - TYX

характеризуется величиной

qtX.T) - supec0 Е{<е-ТУх)тС(е-ТУх> |0>,

где 6 - произвольная фиксированная неотрицательно определенная матрица. П - множество в Rra.

основной результат состоит в следующем (теорема 2. 1 ):

[17} Pukalshein F. On linear regression designs which maximize information Ц 3. Statist.Planning and Inference, 1980 Vol.4, p.339-364.

[18] Куке Я. Минимаксная оценка коэффициентов регрессии // Изв. ДН ЭССР. »из. Мат. . 20, 1971, с. 480-482.

[19] Куке Я.. Ольман В. Минимаксная линейная оценка коэффициентов регрессии // Изв. АН ЭССР, Физ.М&т., 21, 1972, с. 65-72.

[20] Stahlecker P. and Lauterbach J. Approximate linear ninimax estimation in regression with ellipsoidal constraints // Communications in Statistics; Theory and Methods. 1989.

для произвольного множества Пс К® справедливо соотношение 1п£тч(Х,Т) - зир(3<г21гСВ(ХТХ+<721)-1,

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

0 - Е1.1

е О, п 5 га1т+1)/2 + 1. Цс^ - 1, р^ > О.

Доказан также аналог теоремы эквивалентности для данной задачи и предложена итерационная процедура ее решения.

В главе 10 изучается проблема планирования эксперимента для нелинейной по параметран регрессионной модели вида

*<х> - ехрС-^х) + с(х)

при стандартных предположениях об ошибках; Ес(х) - О, 2 2

Ее1х)е1х')-0, х * х'. Ее 1х) - а- . гдв а^. Х^ - оцениваемые

параметры. Модели такого вида используются в теории массового обслуживания для аппроксимации распределений [21], а также во многих, в частности физических, приложениях (22}. В качестве критерия оптикальности рассматривается О-нритерий.

Пусть г - { х^ .. .. х()}, х^ е [О.»)- план эксперимента. В

качестве критерия оптимальности рассмотрим величину 1п^бП йеЪ М(г',в),

[21] Bertsimas 0. An exact FCFS waiting time analysis for a general class of G/G/s queuoing sistems // Queueing systems, 1988, V.3, p.305-320.

[22] Wiese W.L. Atomic transition probabilities. // Nucl. Inst, and Methods, 1970, v.90, p.25.

где

- катрвца информации,

®т - <4.....V аю.....а11-1- -ак0.....акхх»

для множества О вида

а - {Л- А^А^ e PJ. i-1. ....k-1, i аь

d, р^ - произвольные фиксированные положительные числа такие,, что

< d I от величин а^ при а^ » о оптимальный план не зависит).

Теорена 2. 1. При любом фиксированном плане, число различных точек которого не меньше числа оцениваемых параметров, нижняя грань критерия достигается при Aj-d, Aj-d-pj,».. , A^-d-pj-... -pj^.j-

Таким образок, задача нахождения оптимальных планов в смысле введенного критерия сводится к построению локально D-оптимальных планов, понимаемых как планы, максимизирующие величину detMtt, 0) при фиксированном Л. Такие плана удается исследовать с точки зрения функциональной зависимости Xj от Л при условии, что

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

Будем рассматривать случай ...1^-1. общий случай

формулируется аналогично.

* 2к к определение. Назовем отображение т (Л):5-»1 , где S-<0,«) ,

J-[О,и), оптимальной план-функцией, если при дабон Л е S

det М(т*(Л),в)/ П (А.-А.А- sup „det И(Г,в)/ П (А.-АлД i<j - ' т • i<j 1 1

где обе части доопределены по непрерывности при совпадении

некоторых координат . Л, а верхняя грань берется по всем планам ..

вида t - (xr., ,.x2k), Xj * хг * ... * x2k. . ,

Основной результат состоит в следующем (Теорена 3.1):

Оптимальная план-функция г (Л) - {Xj(A).....Х2К(Л)} существует и

определена единственным образом. Кроне того, х^(Л| « О, Х^(Л)

(1-2,....2к) есть аналитические функции, которые монотонно строго убывают по каждому А^ (j-1.....к).

ЗАКЛЮЧЕНИЕ

Сформулируем основные результаты, полученные в диссертации.

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

2. Исследованы некоторые методы агрегации результатов имитационного моделирования. Установлена связь этих методов с теорией планирования регрессионных экспериментов.

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

4. Получена теорема двойственности для E-оптимальных планов регрессионных экспериментов и вид таких планов для тригонометрической регрессии на отрезке.

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

множеству общего вида. основанный на сведении нхнимакской задачи к задаче на максимум.

6. Разработан метод исследования оптимальных планов эксперимента для случая нелинейных по параметрам моделей экспоненциального типа, основанный на изучении локально--оптямальных планов как функций оцениваемых параметров. Показано, что для моделей с ограничением на разность показателей экспонент построение планов, оптимальных в смысле минимаксного . подхода, сводится к построению локально-оптимальных планов. Доказана теорема о монотонной зависимости точек локально D-оптимальных насыщенных планов от значений оцениваемых параметров.

основное содержание диссертации опубликовано в следующих работах:

1. Математический эксперимент с моделями сложных стохастических систем. СП б, 1993, 270 с. (совместна . с С. И. Ермаковым).

2. Математическая теория планирования эксперимента. И.,1983, 392 с. (совместно с С.М.Ермаковым, В. 3. Бродским и др.).

3. Optiaal designs for exponential regression // Math, operationsforsh. Stat. Ser. statistics. 1978. Vol. 9, p.45-59.

4. оптимальное планирование эксперимента для экспоненциальной регрессии // Кат. методы планир. экспер. , Новосибирск, 1981, с. 174-193.

5. 0 выборе плана эксперимента и метода оценивания при нз-личии априорных сведений о параметрах // математические нетолы планирования эксперимент^ Новосибирск. 1981. С. 153-173.

6. Планирование эксперимента при оценивании параметров пуас-соновского процесса (процессы размножения и гибели) // Вопросы кибернетики. Нетрадиционные подходы к планированию эксперимента, и., 1981. С. 98-101.

7. Планирование и интерпретация эксперимента при н&личин априорных сведений о паракетрах недели // Вопросы кибернетики. Нетрадиционные подходы к планированию эксперимента.К. ,1881. с.<6-88

8. Одна теорена двойственности и итерационный метод нахождения h-оптимальных планов // Вестн. Ленингр. ун-та. 1982. Сер. 1. Bun. 2, с. за-43 (совместно с С. К. Ермаковых!.

9. Одна теорена двойственности х Е-оптимальности // Заводская лаборатория, 1982, N 3, с. 48-60.

10. об одном подходе к оптимальному планированию имитационных экспериментов // Статистические методы и модели. К., 1887. С. 77-86.

11. О методе ветвления траекторий при имитационном моделировании сложных систен // Изв. вузов. Математика. 1988. N S. с. 11-16, (совместно с С. М. Ермаковым).

12. Об оптимальном ветвлении траекторий при имитация систем, описываемых стационарными случайными процессами // Изв. III СССР. Техн. кибернет. N 2. 1389, с. 64-68 (совместно с С. И. Ермаковым).

13. On optimal experimental design for stochastic process simulation // Fifth International Vilnius conference on probability theory and mathematical statistics. Vilnius, 1989. Abstracts of connunications. v.IZi M-Z. Vilnius, 1989, p. 18-19.

14. О методе ветвления траекторий для повышения эффективности моделирования сложных систем. Киев. 1990. 22с.-Препринт 80-29.

19. Об одном подходе к сжатию данных имитационного моделирования // Вестн.Ленингр. ун-та, 1991. Сер. 1. Вып. 2, с. 40-47.

16. сравнение методов существенной выборки и ветвления траекторий // Перспективные методы планирования и анализа экспериментов при исследовании случайных полей * процессов. Тез. докл. IV Всесовзн. конф. (Петрозаводск, 1991 г.). N.. 1В91, с. 22-23.