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

МИИ1СТ-ЕГСТЮ НАУК', БКСы'ЕЛ ШИН И ТЕХНИЧЕСКОЙ ПиЛП'ИК! ГГК'Р

ТСМСЖП ОРДЕНА ОК'ГЯБРЬСКО;! РЕВОЛЮЦИИ И ОРДЕ1Л ТРУДОВОГО КГЛСШГО ЗНАМЕНИ ГБСУДАГСТБЕНШЖ И21ЕЕГС»ТГЬ7 / имени В.В.КУЙ5И2ЕВЛ

На прпмх рукописи УДК О1Ь.27:6Ь1.3?.4

ГГЛЬФАЩ Елена Михайловна

ОЦЕНИ ПАРАМЕТРОВ И ПНЛТЮЗПРСВАНИЕ СССТСЯНИП дискгкгнкх каркг^кх силта по результатам нлатадисш

Специальность 05.I3.IC -Пшякпгетю вк-иолигельшЯ техники, матемлтического моделирпп-зиия .и математических методов в нэучних : исследованиях

л 'в торе ф ерат ■

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

Тонек - 1992

Работа шиолнена в Томском государственно».! университете шеш В.В.КуЙбицева л Сибирском физико-техническом виотятутв имени В.Д.Кузнецсша.

Научный рукоБодатвль: доктор срлзш^о-матемаи'-ическда наук,

профессор Л.Ф.ТЕРПУГОВ. 0.рпдааяьнкв. оппонент: доктор технических паук, профессор Л.И.РУЕАН, кандидат !|;лок:<оч.*ате.:аткческшс наук, доцент к.п.ля&кц. 1 -

Ведущая организация: Г&озогокк» икстапут электронного

лкссвр'л.цвм соосой'.-ск " " ¿2-/</2/У/1992 года

в /7,__чяоу1. иа ваебдзн/г. Олода^к&кровзпкого Оовьхо

Л 063.53.03 при То:.:с;:с!.1 государсгьеунсг.; ушгг-ерстйти но рдреоу: 634010, г. Гокок, г;росиокг Лешша, 36.

С диссертанте;: кочло ознакскгться в Научной библиотеке Томского гоеудецюшшвого университета.

Автореферат разослан ." /и 1992 года. '

Учешы секретарь • «гледаиякзированного Совета, '

к.б-м.н., доцент . . , /■ V Б.Е.Трйвсгкшшо

- 3 -

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

Актуальность проблемы. Одной из важнейших задач, возникающих при анализе временно рядов, является задача исследования характеристик сложных динамических систем по результатам насшюдешш. Особенностью сложных систем чаще всего является то, что нх характеристики точно неизвестны и меняются со временем, поэтому необходимо шеть какую-то формализованную модель функционирования системы, не связанную с ее точной структурой. Такой моделью является дискретная марковская система и непрерывна.! временем. Поведение такой системы характеризуется шк1)инлтезшалышми коэффициентам переходов из состояния в состояние л поэтому, изучая класс таких систем, в первую очередь исследуют эти коэффициента. Получив их, пользователь мог.ет решать ряд практических задач, о,плои из которых является задача прогнозирования состояний диск-' ретных марковских систем по результатам наблюдеый, с целью предпринять действие, не допускающее переход системы в нежелательное для пользователя состояние, чтобы избежать возможных экономических потерь. Исследование таких дшшмпческих систем, поэтому, сводится к следующим задачам:

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

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

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

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

1) оценки параметров, характеризующих систему, строятся по одной реализации наблюдений над системой; ,

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

3) рассматривается случай, когда состояния системы могут

I

Отдел :серт£цк3 1

быть известны неточно;

4) рассматривается также случай, когда имеется линейный дг2йф характеристик системы во временя.

Работа выполнялась в соответствии о госбюджетной уемой • "Математическое моделирование систем обработки информации (шифр "Модель", регистрационный номер 0190000<т26), выполняемой Сибирским физико-техническим институтом в соответствии с Программой Гособразования СССР "Математическое моделирование в научных итехническпх системах", раздел й 9 "Стохастическое моделирование", задание й 129, а также в соответствии о хоздоговорной темо; "Разработка математических моделей и программ обеспечения оценки функционирования сложных технь ¿ескнх систем" (шифр "Жуляш">, выполнявшейся Сибирским ф!Эико-техндческш.1 институтом для КБ ПО "Полет" г. Омска.

Цель работы. При выполнении диссертационной работы ставились следующие задачи:

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

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

- изучение асимптотических свойств построенных оценок;

.- исследование систем, имеащих линейный тренд интенсивностей;

- прогноз состояний системы. . ■

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

Научная новизна.

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

2. В случае наблюдений в случай™е моменты времени (образующие стационарный пуассоновский поток) построены оценки этих же

кзметров, показана их сходил ость и проведедо. исследование ас-ялптотическоЯ эффективности.

3. Исследованы подобные оценки в случае, когда система отвдаегся "косвенно" также в детерминированные я случайные '' 1ента времени.

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

■ Практическая ценность. Предложенная методика оценивания па-'.етров переходной матрицы дает возможность подучить харэктерис-ах сьстсм с двукя состояниями в случае явных или "госзэшшх" • владений, полученных в детерминированные иди случайные момента.' 'кони. Кроме того, аналогичные оценки получены и могут проденься для определения характеристик систем, имеющих лтмешшй ;н,г, интенсивно с тей переходов. Методы нахождения оценок' парафов переходной матрицы реализованы в виде подпрограмм на Жъ Ф0РТРА11-1У.

Реализация результатов работы. Предложенные алгоритмы реа-ювоны в виде подпрограмм на языке Ф0РТГАЕ-1У для машин серии , Эти подпрограммы переданы в КБ ПО "Полет", где предполагается дальнейшее использование.

Публикации« По теме диссертации опубликовано 7 печатных работ, эечень которых; приводится в конце автореферата. Материалы дне-. ?таиди были'также излекенн в" отчетах по госб-дяжетной НИР и хоз-.ловор11ой Ш1Р, выполняемых ^ Сибирском физико-техническом ютс-гуте: .

1, Математическое моделирование систем обработки икфомация -гот по НИР (номер государственной регистрации 01900002126)-, тек, 1991. - 35 с.

2. Отчеты по хоздоговорной теме "Еуляны", Томск - 1938;

30.

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

I. Третьей Всесюзной конференции "Перспективные методы анирования и анализа экспериментов при исследовании случайных лей и процессов", Гродно, 1588.

2. Региональный научно-технической конференции "Измерение характеристик случайных сигналов с применением микромашинных средств", Новосибирск, 1988,

3. Республиканской научной конференции "Математическое и программное обеспечение анализа данных", Ккнск, 1990.

4. Всесоюзной научно-технической конференции "Распределении микропроцессорные управляющие системы и локальные вычислительные сети", Томск, 1991.

Работа состоит из введения, четырех глав, заключения и приложения и содержит 159 страниц машинописного текста, 19 рисунков 12 таблиц, а так^е список литературы из 93 наименований.

. . СОДЕРЖАНИЕ РАБОТУ

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

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

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

'Система имеет два состояния: 0 и I, и наблюдается через равные промежутки времени длины 7" . В результате получается массив /<{}J , т.е. массив 0 и I, соответствующих состояниям системы в моменты О, Т, 2?.....У Г. Моделью эволюции системы,

предполагается марковская модель, т.е. переходы 0 —I и обратно образуют дискретную цепь Маркова с непрерывны!.! временем и зшфшштезшалышми кооффлциентами <¿ (для перехода 0 —I) и (для перехода I —С ),

Вместо инфшштезималышх коэффициентов предлагается оцениват. параметры Зк> л H однозначно связанные с ^ л JS> следующим образом:

J>

Параметр И является собственным числом матрицы переходов (второе собственное число равно I), а параметр , являющийся по смыслу финальной вероятностью пребывания системы в состоянии 0, определяет собственные вектора переходной матрицы. Таким образом, по сути дела, оцениваются собствешше числа и собственные вектора переходной матрицы.

Оценки параметров Ji^ и И находятся по метод'- наименьших ква,дратов (KHK) из условия

R.-Zl(*i+< - ^ (2)

и получаются в виде

j£ = / - cci

h ff7 ^ О)

Л/ „ /V-/

„ Uz:*) -

Г. i У ¿=o ' M i'O_

" ~ * j JL

l=P i = o

как видно из (3), свойства этих оценок определяются свойствами статистик у ¿-j

/

4- ъ

'+4

Показано, что при // —»-оо ватячпны ^л

~ ^ сходятся по распределению к двумерной' нор-

мальной случайной величине. На основании этого показано, что оценки -Жо 11 М являются асимптотически несмещешшт и аспмп-тотически нормальными величинами со следующими дисперсиями и ковариациеи

а

И , У (Т^дЛ зл, Н+ 2>ЛоВ Н){4- И)

/ У ' V Яо{-/-Яо)

см- /4 ///- ^ /V-

И

Кроме того, показано, что Ло д И сходятся при У—^оа ,, "З-о л Н почти наверное я их аскмлтотдческая ьф-.Ьектаваосаъ раина I.

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

¡ю втором раздело иерзо-.: глава исследуется та го система, паПтвд.-шш так же яшпо, но пояучеин г мошкжи времени, образу; IV,¡о стш:доа&р;ч:]; луасооиозихшй ноток шгексжшоотя -Я . Вмес о ' £ предлагается оцекьвдтъ следувцве параметры.

н - е ~ СоС

Оодшш этззс пара?,¡строи искались по ШК. Их вид определяет следующая система уравнений:

. ¿V^^нЬа-и^)

г7

1 ^ /7- И Ъ)

с}

= 0

идно, что первое уравнение дает зависит,гость оценки от

ценки , а оценку И легко найти численно, решая второе бычное трансцендентное уравнение. Показано, что при М— ценки ^ и н являются асимптотически несмещенными и сходятся истинным значениям С^ и И по вероятности. Определены дис-эрсии оценок ¿¿о м И . При определении эффективности оценок Ло и И использовалось неравенству информации Фиаера. Графики эвксимости эффективно с те к оценок Зо и //от значений пара-этра Д, я величины Л = ^приведены на рис. I и рис.2.

ЕМ Л,

тй

а. Ш

А-

г Яо-

1

о.г аъ р.2

а< ае*

* б

а.

Ряс. I Рис. 2

Во второй главе рассматривается такая л:е дпс:-:г.етная г.'-рков-

екая система, имеющая два состояния: 0 и I, но наблюдаемые состояния системы связаны с истинными состояниями с вероятностными характеристиками Р0 и Р^ следущим образом: если система находится в состоянии 0, ю с вероятностью Ра пользователь наблюдает токе 0, а с вероятностью I - Р0 наблюдается I, а дая состояния I с вероятностью/°уна&иодается I, а с вероятностью 1-Я/ наблюдается 0.

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

А - i

lo =

Po+Pt - *

лГ

У-f

(5)

н■

// ^ - / ¿

í Vi} ~ наблюдаемые значения системы с Ра и // , свя-зашше с истинными / QJ- л „

Так как свойства оценок и И определяются свойствами

статистик

£

/V " J7 &

С-о

1/ & ' с-О

то при /V -оо показывается асимптотическая нормальность j'C/ и , а затем р;е и асимптотическая нормальность самих оценок JÜ, и И . Найдены яыше выражения для дисперсий оценок

и ^

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

Ом ' } ' 2- 4 Ус

где

1-е

У

4 Ро+

I

-7

а =

^ + &-2нг- Ло

№ - ¿о {р, -- /} * £ (р0 +р< - *)) Л^-гЛСРо+Ъ-'}*

Я = /^//^ Л - //1^"'- 4м*{а - //

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

Во втором разделе второй главы опять хе в системе с двумя СОСТОЯКИЯГ.'Л и ЖЙИНВтеЗКДОЛЫПЛЯ! кооту-.нплонтамл о/ И оцв-

тшзамтся параметры и // по результатам косгеашсс наблюдений в моменты времени, образующие стацаоаэриий пуасссновский поток кнтенсгашсста Л . С покодко метода кашенкже квадратов строится система уравнений, псвзоляп::?я, геяыэ трлпоце.'.донтпоа уравнение, 1гп11тл // , а с пс;.;0|Чыо // койтя .

• Б СЛучГ.О "КОСП'ЗЛаЧх" НЭЛТОГ.СЧКХ В случпишю ГСМОИТ!! временя удалось показать, что в асимптотическом случай оценок

^ и // яптжтсся ао;,:.'1гготл''30лП ьоеют»ош::лк и сходятся ¡п зероятноста в поташ;?.! зиоче-ндям параметр",? и /У •

Третья глава посвящена исеявдовшшп хярпктерпоч'/.к оастртч ^ (,нумч состоят?;::« п|-и уо."о?;й(, что пчтеисит«иости иорох^чоп из

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

+ Х^-Л +Л г

и система "стареет" с одинаковой скоростью, т.е.

<*2. _ А

^ Л

- Г

Вместо параметров, определяющих инфянитезимальные коэффициенты ' и ^ 0чеЕИЗа'1ИСЬ параметры

Н. г-«"*1 „ л -

Л ч " .

Вод оценок , Н а & определяют статистики (6) и система уравнений (7)

• ' (6) / и .

' -{- Ло - в : '

л г

-/ ЛоО-Хо)/* = £>

с . <"

г

Л и

Откуда получаем, что 71о = 3 , а оценка й. из решения трансцендентного уравнения (8)

а, (е <{)

= '

е с< -

Получлв (Ь ме.-шо пойти И , например, в виде + _ А.

^ -и

Тан. как поведение оценок , И и ¿?- характеризуется поведением статистик 3 , & и С{ , то найдена дней ер мш этих статистик в случае —>■ оо и их козариацш!. Кова^назунокняя: матрица величин $ , и обозначена как ~ С-

Асимдтотшеская коварпашюниач матриц? оценок „'4, , Н я >1-иаходнтсч из решения системы (7) с пешдаэ метода лшеарпсашш. Считая разности ¿Л^ =• - , а И •* // " М и л Л ¿ь - еь. малшл и линеаризуя систему (7) по неизвестны* параметрам, полу-

Г о —1 1

о

С,

о

. с, .

где 6 , Со , С< отличаются от 5 , Со и тем, что

вместо ¿Сс содерка? ^ = - -У + ¿Ео . Обращая матрицу находим ковариационную матрицу оценок ^ , ,у л & в виде

<~е> А/ <

^ и

и из нее получаем енд дисперсии оценок , // и ¿2- . С

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

находился (8)

О)

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

3 первом разделе приведены результаты имитационного моделирования для систем с двумя состояниями, наблюдаемых явно в детерминированные моменты времени, описана логическая процедура построения массива возможных значений системы. Моделирование проводилось для различных значений параметров -^о и И при различных* объемах выборки /V не менее 300 раз.

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

Б результате моделирования получилось,' что необходима наблюдать не менее 300 состояний системы, чтобы применять процедуру нахождения оценок (I). Результаты моделирования отражены в таблицг и частично на гистограммах. ■ .

Например, для И = 0.63 таблица I содержит для = 0.05, Яо= 0.55 и = 0.95, объемы выборки, с которых оценки будут нормальными, согласно выбранного критерия

Таблица I

и = 0.63

£о 0.05 0.55 0.95

А/ 5РП 300 500

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

. В этом случае сначала моделировался сам пуассоновский потек на интервале моделирования 7" , а ухе з-,тем по заданном исходим значениям Л? , Н и Т через интервалы, образующие этот поток, моделировались возможные состояния системы. Дня как-

}

дог о набора' Ло , Н я Т моделирование проводилось не менее 300 раз. Для такой системы проводилось определение минимального интервала модрдироваш: Т с которого оценки и И будут нормально распределены с нулевым средним и полученной в разделе 1.2 дисперсией. Соответствие нормальному распределению проводилось по критерию X1 с пятипроцентным уровнем значимости и девятью степенями свобода.

Необходезшй интервал-моделирования (для случая Л - I) приведен да различных пар и И в таблицах, а для некоторых пар еце. и на гистограммах. Например, в таблице^ указана шши-чалытя ,длина 7~ для нормальности оценки параметра

./£= 0.55, дня Ч = 0.05, //= 0.63, /У=0.95

. Телица 2

•¿¿с, - О.^о

Н 0.05 0.63 0.95

т ГОСО 300 ЗСО

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

Четвертый раздел посвящен описанию входных и выходных пара-етров и первых строк подпрограмм нахождения оценок. Все подпро-рашн написаны на языке Ф0РТРАН-1У и переданы заказчику, где зпользуются при анализе поведения сложных систем.

В приложении приведена Справка об использовании результатов эботы.

Основные результаты работы и выводы.

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

о) когда наблюдения явные и.получены в дотегмшшрованннэ •менты времени;

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

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

г) тогда наблюдения "косвенные" ,■ моменты наблюдений случайные ;

д) когда подразумевается, что интенсивности переводов в системе зависят от ьремени и имеют линейный тренд и одинаков^? скорость "старения". Кай/хюдения явные в дегерх-шнкропакныа моменты времени.

2. Исследоваки асшпмтичеыше свойства предлагаемых оценок: нормальность, нескеи;внпооть, эффективность.

3. Разработан дожш;; подпрограмм, написаниях на языке С0ГТ?;л:-Г/ и реализующих нахоздотю предугагаог.прс оценок, к нровйдеко имитационное моделирование, подтверждающее теоретические результаты. '

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

1. Гельфанд Е.М. Прогнозирование состояний дискретной динамической системы по результатам наблюдений // В сб. Поиск аигнала в многоканальных системах. Вып. 2. Томск: Изд-во Томск, ун-та, 1Ы!7, С.Ь5-64.

2. Гсль^энд ЕЛ.!. Прогнозирование состоядхй дискретной динамической системы по результатам кисвеюплс наблюдений //■ Техника средств связи. Серия СО, 1989, вып. 7. С..92-99;

3. .Терпугов Л.Ф., Гельфаид Е.М. Оценка параметров динамической дискретной системы по результатам наблюдений б случайные имюнта времени // Радиотехника, 1991, $ 5. С. 16-19.

4. ГелнТднд Е.М., Терпугов Л.О. Оценка интенсивиостей переходов в дискретной динамической системе // Перспективные модели планирования и анализа экспериментов при исследовании случайных полей и процессов. Тезисы докладов. 4.1. Гродно, 1988. С.26-27.

' - 5. Гельфанд Е.Ы., Терпугов А.Ф. Прогнозирование состояния дискретной динамической -системы по результатам наблюдений // Измерение характеристик случайных сигналов с применением микро-мзенннкх средств. Тезисы докладов. 4.1. Новосибирск, 1988. О. 36-36.