close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Известия ТулГУ. Технические науки. 2016. Вып. 9
УДК 519.217.2
РАСЧЕТ ЧИСЛОВЫХ ХАРАКТЕРИСТИК
ПОЛУМАРКОВСКИХ ПРОЦЕССОВ
Г.Н. Клинцов, Е.В. Ларкин
Описываются процессы расчёта основных числовых характеристик полумарковских процессов для анализа быстродействия ЭВМ.
Ключевые слова: дисперсия, закон распределения, математическое ожидание,
матрица, полумарковский процесс, цепи Маркова.
Задача расчета числовых характеристик полумарковских процессов
может быть решена через вычисление интегралов для закона распределения f BV (t ) или f BE (t ) :
∞
T = [Tij ] = [ ∫ f ij (t ) t dt ] ;
∞
(1)
0
D = [ Dij ] = [ ∫ f ij (t ) (t − Tij ) 2 dt ] .
(2)
0
Однако если полумарковский процесс изначально задан числовыми
характеристиками элементов полумарковской матрицы, то такой метод не
является рациональным. Удобнее непосредственно выполнять соответствующие операции с матрицами числовых характеристик. Для описания
этих операций понадобятся формулы для математических ожиданий и
дисперсий композиций случайных величии.
Так, для суммы двух случайных величин взвешенное математическое ожидание закона распределения [αξ(t )] *[βξ(t )] определяется как
∞∞
∞
∞
∞
∞
0 0
0
0
0
0
Tξς = ∫ t ∫ αξ(τ)βς (t − τ)dτdt =αβ ∫ ξ(τ) ∫ tς(t − τ)dτdt =αβ ∫ ξ(τ)[τ + ∫ tς(t )dt ]dτ =
∞
= αβ ∫ ξ(τ)(τ + Tς )dτ = αβ(Tξ + Tς ).
0
Взвешенная дисперсия закона [αξ(t )] *[βξ(t )] находится по формуле
∞
∞
∞
∞
0
0
0
∞
0
∞
0
0
Dξς = ∫ (t − Tξς / αβ) 2 ∫ αξ(τ)βς (t − τ)dτdt = αβ ∫ ξ(τ) ∫ [(t − τ − Tξ ) + (τ − Tς )]2 ⋅
∞
⋅ ς(t − τ)dtdτ = αβ ∫ ξ(τ){ ∫ (t − τ − Tξ ) 2 ς(t − τ)dt + 2(τ − Tς ) ⋅ ∫ (t − τ − Tξ )ς(t − τ)dt +
0
∞
+ (τ − Tς ) 2 ∫ ς(t − τ)dt}dτ = αβ( Dξ + Dζ ),
0
96
Информатика, вычислительная техника, обработка и защита информации
где α и β - некоторые коэффициенты, определяющие "веса" законов ξ(t ) и
ζ(t ) соответственно.
Полученные результаты могут быть достаточно просто экстраполированы математической индукцией на взвешенное суммирование J случайных величин:
 J

Т J = ∏ α i  ∑ Т ξi  ;
ξ
i =1  i =1

(3)
 J

= ∏ αi  ∑ Dξi  ,
ξ
i =1  i =1

(4)
J
J
D
где Т
ξJ
и D
ξJ
J
– соответственно математическое ожидание и дисперсия
взвешенной суммы J случайных величин; Т ξi и Dξi – соответственно математическое ожидание и дисперсия закона распределения i-й случайной
величины композиции; αi – некоторые коэффициенты.
Если композиция случайных величин является такой, что ее закон
распределения представляет собой взвешенную сумм, законов распределения случайных величин с весами, равными вероятностям появления соответствующей величины в композиции (не путать взвешенное суммирование законов распределения е рассмотренным выше случаем взвешенного
суммирования случайных величин!),
J
 J 
ζ (t ) =  ∑ βi ζ i (t ) /  ∑ βi  ,
i =1
 i =1 
J
(5)
где βi и ζ i (t ) - соответственно вероятность появления и закон распределения i-й случайной величины, причем
J
∑ βi ≤ 1 ,
i =1
то математическое ожидание Т ζ такой композиции определяется по зависимости
∞ J
 J  J ∞
 J 
Tζ =  ∫ t ∑ βi ζ i (t )dt  /  ∑ βi  =  ∑ βi ∫ tζ i (t )dt  /  ∑ βi  =
 0 i =1
 i =1  i =1 0
 i =1 
J
 J 
=  ∑ βiTζi (t ) /  ∑ βi .
i =1
 i =1 
97
(6)
Известия ТулГУ. Технические науки. 2016. Вып. 9
Дисперсия Dζ определяется по зависимости
J
∞
  J  ∞ 2 J
 J 
2
Dζ =  ∫ t − Tζ ∑ βi ζ i (t )dt  /  ∑ βi  =  ∫ t ∑ βi ζ i (t )dt  /  ∑ βi  −
 0
 i =1   0 i =1
 i =1 
i =1
J
J
∞
  J  ∞
 J 
−  ∫ 2tTζ ∑ βi ζ i (t )dt  /  ∑ βi  +  ∫ (Tζ ) 2 ∑ βi ζ i (t )dt  /  ∑ βi  =
i =1
i =1
 0
 i =1   0
 i =1 
(
)
J ∞2
 J 
J
 J 
=  ∑ βi ∫ t ζi (t )dt  /  ∑ βi  − (Tζ )2 =  ∑ βi Dζi + Tζi 2  /  ∑ βi  − (Tζ ) 2 , (7)
i =1
 i =1 
i =1 0
 i =1 
где Dζi и Т ζi - соответственно математическое ожидание и дисперсия за-
(
)
кона распределения ζ i (t ) композиции (5).
Для удобства записи и разработки алгоритмов вычислений могут
быть определены следующие операции над матрицами, легко реализуемые
на любой универсальной ЭВМ с достаточным объемом памяти:
развернутое сложение числовых матриц α ij размерностью I × J и
[ ]
[βij ] размерностью J × K
[vikj ] = [αij ]+ < [β jk ] = (αij + β jk ) j ;
(8)
развернутое умножение числовых матриц [αij ]размерностью I × J
и [βij ] размерностью J × K
[vikj ] = [αij ]× < [β jk ] = (αij × β jk ) j ;
(9)
прямое деление матриц:
αikj # βikj = αikj / βikj ;
(10)
В результате выполнения операции (8) формируется J-мерный вектор матриц размерностью I × K , каждый элемент vikj которых определяет-
[ ][ ] [
]
ся как сумма α ij + β jk .
В результате выполнения. операции (9) формируется J-мерный вектор матриц размерностью I × K , каждый элемент vikj которых определяется как произведение αij × β jk .
В результате прямого деления матриц формируется матрица, каждый элемент которой представляет собой частное от деления элемента
матрицы-делимого на соответствующий элемент матрицы-делителя Указанная операция является обратной операцией по отношению к прямому
умножению, т.е. если αikj и βikj - матрицы одинаковой размерности, то
[ ] [ ]
[αikj ]# [βikj ]⊗ [βikj ] = [αikj ]. Неопределенности
разрешаются в сторону нуля: 0/0 = 0.
98
типа 0/0 в этой операции
Известия ТулГУ. Технические науки. 2016. Вып. 9
Так, математическое ожидание и дисперсия времени одного перехода из начальных состояний в алгоритме определяются по зависимостям:
T
1
B
D
B1
= Q[T ⊗ P ][1,1, K ,1]T ;
(11)
( B )2 ;
= Q[[T ⊗ T + D ] ⊗ P ][1,1,K,1]T − T
1
(12)
где Q - вектор начальных распределений; T и D - соответственно матрицы
математических ожиданий и дисперсий; P - вложенная цепь Маркова.
Числовые характеристики времени достижения состояний подмножества V за один переход равны:
T
BV 1
D
BV 1
= (Q[T ⊗ P ]V ) / (QPV ) ;
(13)
( BV )2 ;
= (Q[[T ⊗ T + D ] ⊗ P ]V ) / (QPV ) − T
1
(14)
где V - вектор-строка.
Для описания полумарковского процесса, состоящего из к переходов алгоритма в сопряженные операторы, необходимо определить числовые матрицы T k и D k Указанные матрицы могут быть выражены через
рекуррентные соотношения:
T1 = T ;
{[(
)] }
) (
T k = T k −1 + < T ⊗ P k −1× < P ε # P k ;
(15)
D1 = D;
Dk =
[({(D k −1+ < D)+ [(T k −1 ⊗ T k −1 )× < (T ⊗ T )]}⊗ (P k −1× < P))ε]#
k
k
k
#P −T ⊗T ;
(16)
где 1 < k < ∞; P k = P k −1 × P;
С использованием (15) и (16) выражения для числовых характеристик закона распределения достижения области V для случая, если на траектории решения не накладывается дополнительных ограничений, принимают следующий вид:
∞
 ∞

TBV =  ∑ Q V T k ⊗V P k V  /  ∑ Q V P K V  ;
(17)
k =1
 k =1

[(
[ ((
)]
(
)]
)
)
(
)
∞
 ∞

DBV =  ∑ Q V T k ⊗V T k + D ⊗V P k V  /  ∑ Q V P kV  − (TBV )2 ; (18)
k =1
 k =1

Вероятность достижения подмножества состояний V из B.
∞
PBV = Q ∑ V P K V ;
k =1
100
(19)
Информатика, вычислительная техника, обработка и защита информации
В (17) - (19) величины V T , V D , V P представляют собой числовые
матрицы, полученные из матриц T, D, P с учетом того, что состояния
a j (V ) = V ⊂ A , для которых выполняется условие V ∩ E ≠ ∅ , должны
{
}
быть преобразованы в квазипоглощающие состояния.
Преобразования производятся с использованием соотношений
 Tij , Dij , pij , при ai ∉ V ,
V
Tij , V Dij , V pij = 
(20)
[
]
a
V
0
,
0
,
0
,
при
∈
i

В частном случае при совпадении подмножества состояний V с
подмножеством поглощающих состояний E (V = E) события достижения
полумарковским процессом M подмножества поглощающих состояний E,
хотя бы и за бесконечно большое количество шагов k, составляют полную
группу несовместных событий. Очевидно, что в этом случае PBE = 1
вследствие того, что дополнительных ограничений на траектории решения
не наложено и других поглощающих состояний, кроме E, в полумарковском процессе M нет.
Величины TBE . и DBE вычисляются по зависимостям
] [
]
[(
)]
[
∞
TBE = ∑ Q V T k ⊗V P k E ,
∞
[ ((
k =1
)
(21)
)]
DBV = ∑ Q V T k ⊗V T k +V D k ⊗V P k E − (TBE )2
k =1
(22)
в которыхe E - вектор-столбец.
В случае, если на траектории решения наложены ограничения тина
"отражение" или-"игнорирование", элементы матриц вложенной цепи
Маркова Р' И Р", математических ожиданий T ′ и T ′′ , дисперсий D ′ и D′′
определяются по нижеследующим выражениям.
Для ограничений типа "отражение":

0, для j , при которых a j ∈ V ,

pij′ =  pij , для j = i, при которых a j ∉ V ,

 pii + ∑ pij , для j = i, j (V ) − индексы j , при которых a j ∈ V ;
j (V )

0, для j , при которых a j ∈ V ,

Т ij , для j = i, при которых a j ∉ V ,



Т ij′ = 
 p Т + ∑ p Т  /  p + ∑ p , для j = i, j (V ) − индексы j ,
ij ij   ii
ij 
 ii ii
j(V)
j(V)



при которых a ∈ V
j

101
Известия ТулГУ. Технические науки. 2016. Вып. 9
0, для j , при которых a j ∈ V ,

 Dij , для j = i, при которых a j ∉ V ,



Dij′ = 
 p (Т )2 + D + ∑ p (Т )2 + D  /  p + ∑ p , для j = i,
ii
ij ii
ii   ii
ij 
 ii ii
j(V)
j(V)



 j (V ) − индексы j , при которых a ∈ V
j

[
]
[
]
Для ограничений Типа "игнорирование":
0, для j , при которых a j ∈V ,




pij′′ =  pij / 1 − ∑ pij , для j , при которых a j ∉V ,
 j (V ) 




 j (V ) − индексы j , при которых a j ∈V
[0,0], для
j , при которых a ∈ V ,
j
[Tij′′ , Dij′′ ] = [T ′′ − D′′ ], для j, при которых
a
 ij
ij
j ∉V ,
Дальнейшее определение числовых характеристик процессов проводится по зависимостям (15) - (22), но уже с использованием для расчетов
в качестве исходных данных преобразованных матриц.
Список литературы
1. Евстигнеев В.А. Применение теории графов в программировании. М.: Наука, 1985. 352 с.
2. Игнатьев В.М., Ларкин Е.В. Об одном методе декомпозиции
граф-схем алгоритмов / ТулПИ. Тула, 1987. 12 с.
3. Кристофидес Н. Теория графов: Алгоритмический подход. М.:
Мир, 1978. 432 с.
4. Ларкин Е.В. Вычисление временных характеристик стохастических алгоритмов // Алгоритмы и структуры систем обработки информации.
Тула: ТГГУ, 1993. С. 34-41.
5. Свами М. Тхуласираман К. Графы, сети и алгоритмы. М.: Мир,
1984. 455 с.
6. Сильвестров Д.С. Полумарковские процессы с дискретным множеством состояний. М.: Сов. радио, 1980. 272 с..
7. Ширяев А.Н. Вероятность. М.: Наука, 1989. 640 с.
Клинцов Григорий Николаевич, асп., argon-eldar@mail.ru, Россия, Тула, Тульский государственный университет,
Ларкин Евгений Васильевич, д-р техн. наук, проф., зав.
elarkin@mail.ru, Россия, Тула, Тульский государственный университет
102
кафедрой,
Информатика, вычислительная техника, обработка и защита информации
CALCULATION OF THE NUMERICAL CHARACTERISTICS
OF SEMI-MARKOV PROCESSES
G.N. Klintsov, E.V. Larkin
The process of calculating the basic numerical characteristics of semi-Markov
processes for the analysis of computer performance are described.
Key words: dispersion, distribution law, expected value, matrix, semi-Markov
process, Markov chain.
Klintsov Grigoriy Nikolaevich, postgraduate, argon-eldar@mail.ru, Russia, Tula,
Tula State University,
Larkin Eugene Vasilyevich, doctor of technical science, professor, head of chair,
elarkin@mail.ru, Russia, Tula, Tula State University
УДК 004.9; 528.87
СОВРЕМЕННЫЕ ПОДХОДЫ К ОБРАБОТКЕ ДАННЫХ
ПРИ ПОСТРОЕНИИ ГЕОИНФОРМАЦИОННЫХ СИСТЕМ
ЭКОЛОГИЧЕСКОГО МОНИТОРИНГА
А.Н. Колесенков
Рассмотрены современные методы и технологии обработки аэрокосмических
снимков в задачах построения геоинформационных систем экологического мониторинга объектов и территорий. Представлены способы адаптации алгоритмов обработки
данных к работе в условиях неполной информации. Выполнены исследования методов
вегетационного индексирования аэрокосмических снимков. Предложен способ применения генетического подхода для выявления экологических опасностей. Проведены экспериментальные исследования по тестированию алгоритмов на реальных данных со
спутников Электро-Л и Канопус-В.
Ключевые слова: геоинформационная система, ГИС, вегетационный индекс,
нечеткая кластеризация, генетический подход, эволюционный алгоритм, ДЗЗ, космический снимок.
Ежегодно объекты окружающей среды подвергаются воздействию
ряда неблагоприятных факторов, среди которых можно выделить пожары,
затопления, загрязнения, вырубку лесов, незаконные свалки твердых бытовых отходов и т.д., которые приводит к серьезной угрозе состоянию экосистем. Актуальным является разработка математических и алгоритмических
основ построения систем экологического мониторинга, способных осуществлять эффективную информационную поддержку деятельности
103
Документ
Категория
Без категории
Просмотров
12
Размер файла
448 Кб
Теги
процессов, полумарковское, характеристика, расчет, числовые
1/--страниц
Пожаловаться на содержимое документа