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

обратное: всякая полулинейная вырожденная динамическая система, для которой характеристический пучок матриц имеет индекс 1, преобразованием нормализации приводится к системе уравнений дескрипторной нейронной сети. Дается точное описание конструкции (логической схемы) сети. В разделе 3 продемонстрировано применение «нормализованной» дескрипторной нейронной сети к анализу исходной динамической (разностной) системы. В частности, исследуются допустимые многообразия состояний, которые имеют размерность, равную числу динамических компонент вектора внутренних состояний сети. Анализируются рекурсивное и эволюционное отображения дескрипторной динамической системы с помощью аналогичных отображений модельной нейронной сети. Эти результаты создают предпосылки для эффективного анализа кардинальных качественных свойств дескрипторных динамических систем - устойчивости, выявления периодических режимов, аттракторов и т.п.

Литература: 1. Hopfield I.I. Neural Networks and Physical Systems with Emergent Collective Computational Abilities, Proc.of the National Academy of Science. 1982. 79. P.25542558. 2. Бодянский Е.В., Руденко О.Г. Искусственные нейронные сети: архитектуры, обучение, применения. Харьков, ТЕЛЕТЕХ, 2004. 372 с. 3. Mc Culloch W.S., Pitts W. A Logical Calculus of the Ideals Immanent in Nervous Activity, Bulletin of Mathematical Biophysics. 1943. № 5. P. 115-133. 4. Руденко О.Г., Бодянский Е.В. Искусственные нейронные сети, Харьков, «СМИТ», 2005. 408 с. 5. БенабдаллахМ., Руткас А.Г., Соловьев А.А. Об устойчи-

УДК 519.23 '

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

ГЕРАСИН С.Н., МИХАЙЛОВ Е.А.______________

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

1. Введение

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

вости вырожденных разностных систем в банаховых пространствах // Динамические системы. Киев-Симфе-рополь, 1987. Вып.6. С. 103-109. 6. Bondarenko M.F., Rutkas A.G. On a class of implicit difference equations // Доповіді НАН України. 1998. №7. С.11-15. 7. Campbell S.L. Singular Systems of Differential Equations - San Francisco, London, Melbourne: Pitman Publishing, Research Notes in Mathematics; I . 1980. Vol.40176 p.; II. 1982. Vol.61. 234 p. 8. Власенко Л.А. Импульсные дифференциальноалгебраические уравнения в математических моделях электрических цепей // Радиоэлектроника и информатика. 2004. №3(28). С.27-31.9. Weierstrass K.,Zur Theorie der bilinearenund quadratischen Formen, Monatsh. Akad. Wissenschaft, Berlin (1867). Р. 310-338. 10. Гантмахер Ф.Р. Теория матриц. М.: Наука, 1966. 576 с. 11. Власенко Л.А. Эволюционные модели с неявными и вырожденными дифференциальными уравнениями. Днепропетровск: Системные технологии. 2006. 273 с. 12. Халанай А., ВекслерД. Качественная теория импульсных систем. М.: Мир, 1971. 312 с. 13. Bender D.I., Laub A. The linear-quadratic optimal regulator for descriptor systems, IEE Transactions on Automatic Control. 1987. Vol.AC-32, № 6. P.2062-2077. 14. Campbell S.L. Nonregular descriptor systems with delays, IMA I.Math.Control and Information. 1995. V.12. P.57-67.

Поступила в редколлегию 11.06.2008

Рецензент: д-р техн. наук, проф.Кривуля Г.Ф.

Руткас Андрей Анатольевич, аспирант ХНУРЭ. Научные интересы: машинный перевод, искусственные нейронные сети, динамические системы. Увлечение и хобби: электронное и математическое обеспечение систем GPS, системы безопасности и слежения. Адрес: Украина, 61001, Харьков, ул. Плехановская, 2/5, кв. 29, тел.: (057) 732-28-35.

разному [1]. В данной работе предлагаются некоторые способы нахождения решений, базирующиеся на редукции бесконечных систем, т. е. пути сведения к конечным системам. С методической точки зрения этот подход применим и к системам с большим числом состояний. Например, при исследовании нейронных сетей их модель в виде марковской цепи может иметь 106-108 состояний, что делает ее потенциально бесконечной с точки зрения машинных вычислений.

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

2. Однородный процесс со счетным числом состояний

Будем рассматривать марковский процесс с непрерывным временем и счетным множеством состояний. Пусть его поведение описывается матрицей интенсивностей (инфинитезимальной матрицей) Л = (X у), i, j = 1, 2,...; по определению данная матрица вырождена. Покажем, что применение метода редукции к матрице Л = (X у) возможно и что в этом случае поэлементной сходимости, вообще говоря, недостаточно. Известен тот факт, что если sup Xjj <ж, то соответствующая система уравнений Колмогорова

16

РИ, 2008, № 2

p'ft) = pft)Л

имеет единственное решение, которое можно наити как предел соответствующих редуцированных систем [2]. При доказательстве этого факта редуцирование проводилось простым отбрасыванием элементов матрицы Л = (Я jj), начиная с (n +1 -й строки и столбца. Матрица Л = (X у)у=1 в этом случае перестает быть вырожденной и не определяет марковский процесс.

Определим редуцированную матрицу A(n) = (Xjj) следующим образом:

^12 + EM • j=n+1 •• M

A<n = ^ 21 ад + E^ 2j j=n+1 - % 2 •• ^ 2n

^ n1 V ад + E^ nj j=n+1 ^ n2 .. Xn /

или

dxn/dt = Bn ft) •:

работе [3], однако в этой статье предполагается, что A - постоянная матрица и при i < j (или і >j) aij ^ °, если і ^ ж .

Обозначим

где

естественная норма.

Последовательность матриц {A^ftX сходится поэлементно к матрице Л , и с небольшими изменениями доказательство теоремы 1 можно перенести на доказательство следующего факта.

Теорема 1. Пусть имеет место поэлементная сходимость последовательности редуцированных систем p'(t) = p(<)л( "> и последовательность решений системы q(n) сходится к собственному вероятностному распределению Q = (Qi,Q2, ^.Qi > ° при

ад

всех j и £ Qi = 1, тогда исходная последователь-

i=i

ность имеет стационарное распределение p* = Q. Последовательность решений редуцированной системы Колмогорова с матрицами сходится к решению системы (1).

Пусть X(nftt) - редуцированный марковский процесс с множеством состояний[°, 1,n] и матрицей интенсивностей A^(t). Положим Bn(t) = ft).

Тогда прямую систему Колмогорова для цепи X (n) (t) можно записать в виде

ФпМ = pn -A^ft)

Теорема 2. Пусть X(t) - марковская цепь с ограниченными скачками; X(°) = k, где k є N. Тогда для любого n и любого t > ° выполняется следующее неравенство:

||pft) - pn ft! ^2 •t2 • M2ft) • exp{M0 • о.

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

систему Колмогорова для X(t) можно переписать в следующем виде:

dx/dt = Bn ft) • Х + {B

Пусть Un(t, s) - оператор Коши [3] уравнения (5). Из (5) получаем

xft)=Un ft, °) • x(°)+\ Un ft, X МО - Bn ft)} • xft) •dx .

°

Пусть x(°) = xn (°) = k . Тогда Un (t, °) • x(°) = xn ft) и с учетом того, что при любых t, т, (° <т< t) ||Un (t, ^| < 1 в lj -норме справедливо неравенство

||xft) - xnft)| ^ ЛUnft> 01 ' ||{Bft)“ Bn(0}' x(0| ' dx ^

°

XIIМО-B0Oft x(01-ф

°

Отметим, что при всех t элементы строк с номерами °,..., (n - N являются тождественными нулями. Тогда

llfcft) - Bn ft)} • ooi ^Mft) • е МО ^

i=

ад

< mo • E MO.

i=n - N+1

где pn - вектор-строка вероятностей состояний и

xn = pT .

Хорошо известно [2], что для любого фиксированного отрезка М pn ^ p при n ^ да (покоординатно). Однако обычно какие-либо оценки скорости этой сходимости отсутствуют. Далее будет оцениваться

||p - pn||. Отметим, что некоторые оценки имеются в РИ, 2°°8, № 2

ад

Оценим теперь Е |pift)|. Рассмотрим уравнение

1

= B1z + fft),

i=n - N+1

dz

"dt

m

где Z = (p!,p2, ...)T, f = (am,a°2> "0T, B1 - lb1ijj’

b1ij _ a1ij _ aij a°i .

17

1= n - N +1

и его решение

t

z(t) = V(t, o) • z(o) + J V(t, x) • f (t) • dx ,

PM - suP ЕЦМОі + МФ

1 k >1 i>l

< sup £ {ak^^| + |ao^^) < suP £ {ak^0| + |ao№1 ^

k >1 i>1 k >1 i>1

К IA0I.1 s MO

Тогда в норме l1:

II'V

VX J

If (OK M0* MO

e K(0 ^ e K(0 К KOI ^

i=n+1 i=n +1

< ex^MO  0  I Ы1+MO  ex^{M0  0  t ^ < 2 • t • MO  ex^{M0  0-

Значит,

ад

E IpKOI ^2 •t • MO • ex^{M0 • 0.

i=n+1

Каждая матрица в последовательности связана с предыдущей соотношением:

где x(o) = ek (если k = О , то z(o) = О), а V(t, x) - д(п+0 =

оператор Коши.

Рассмотрим пространство l1. Имеем следующую достаточно грубую оценку:

Y - kn • q1

Y - kn • q

Y - kn • Y £

\(n+1) An+1,1 \(n+1) An+1,2 * \(n+1) •• An+1,n \(n+1) /Y+1,n+1

где q(n) - собственный вектор матрицы МО соответствующий нулевому собственному значению; kn -произвольные коэффициенты, удовлетворяющие ус-

КО

ловию o < kn < —ту, i = 2,..n .

n q(n) ’

qi

f Дп+1) '. 1 „

Последовательность j k | ограничена, т.е.

1 n=1

n+1)

7M+1,n+1

kn

Рассмотрим проекцию разности векторов q(n) - q(n+° на вектор

s=te!. i(nn?1......^n:n?1-^n;?„1)T. (если. > n

q(^ . o):

то

|qW _ qn M >

(qW _ q(n+1)). S qW. S - q(n+0. S

ISII ISII

Теперь, используя оценки (6), (7) , получаем в норме

І1:

||р(0 - рКОІ=1КО - МО -2 •t2 • MK0 • expM0 • 0 -

Теорема 2 доказана.

Заметим, что, как и в случае цепей, верно аналогичное утверждение для последовательности редуцированных инфинитезимальных матриц |д(п) |Щ_1, т.е. поэлементной сходимости ^ Л при n не доста-

точно для сходимости нулевых собственных векторов q(n) матриц к собственному вектору q мат-

рицы л -

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

, обладающую следующими свойствами: lim Л( n) =Л

EqK‘МК -Е>+1)-^М1

i=1

i =1

ife!)2

i=1

Так как £qfn+° МпК = o и = kn • q|n):

i =1

i = 1,..., n , то

qW - q^+D|:

kn • q1

2 ll»"2

Л(п+1) Y

n+1,n+1

v Cn J c2

Vc2 + M2

qW|2 + M2

= const > o

и

2

n

q

18

РИ, 2oo8, № 2

Следовательно, последовательность jq(n) не схо-

дится к нулевому собственному вектору матрицы Л .

Довольно часто система уравнений Колмогорова содержит бесконечное число уравнений и ее нельзя непосредственно решить на ЭВМ. Для того чтобы сделать вычислительный процесс конечным, обычно используют метод редукции, при котором исходная бесконечномерная система уравнений (а значит и соответствующий ей процесс) заменяется конечной системой. Отвечающий конечной системе процесс должен иметь ту же вероятностную природу, что и исходный процесс. Предельные характеристики «усеченной» системы могут быть определены аналитически и, если число уравнений достаточно велико, должны быть близки к соответствующим характеристикам исходной системы. Доказательства сходимости вероятностей состояний «усеченных» или редуцированных систем к исходной системе можно найти в работах [4,5]. Мы же ограничимся иллюстрацией сходимости на примере конкретных систем уравнений и укажем характерные особенности таких типов сходимости.

Пусть неоднородный марковский процесс §(t) с непрерывным временем и счетным фазовым пространством определяется прямой системой Колмогорова

Р'(t) = Р(0А0>

В случае расходимости ряда из положительных элементов редукция осуществляется с учетом коррекции диагонального элемента так, чтобы сумма в соответствующей строке по-прежнему равнялась нулю. Для случая процессов рождения и гибели с постоянными коэффициентами получены оценки скорости сходимости усеченной системы к бесконечной. При этом скорость сходимости является геометрической. Более сильные оценки найдены для неоднородного сильно квазиэргодического процесса [6]. И в этом случае скорость сходимости также является геометрической. Следовательно, стабилизация решений может наблюдаться визуально на графике даже при небольших значениях t.

При построении матрицы использовались сходящие-

n 1

ся ряды вида Хт“Г, где 1 < p < 2 . Для случая n = 5

k=1 k

и p = {1.866,1.905,1.274,1.453,1.748} матрица имеет вид:

1.791 1.313 0.274 0.128 0.075

1.282 -1.744 0.267 0.123 0.071

3.409 0.413 - 4.24 0.246 0.171

2.115 0.365 0.202 - 2.817 0.133

1.432 0.297 0.146 0.088 -1.965

где A(t) - матрица интенсивностей или квазистохастическая,

р( 0=Ы4 -.p^O), pi (0=P(^ о=О

- вектор вероятностей состояний. Данную систему будем рассматривать как дифференциальное уравнение в банаховом пространстве последовательностей

Мы рассмотрим следующие типы инфинитезимальной матрицы AO:

1. AO _ A - (aij ),i, j = 1,2,... - постоянная матрица, причем все элементы ограничены в совокупности.

2. Последовательность {au} расходится к бесконечности.

3. Диагональные элементы au (О < <» для t > 0 .

4. Существуют такие строки, что lim a„ (О -ю .

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

ется квазистохастической, т.е

.е. £ aif) = 0.

РИ, 2008, № 2

На рис. 1 представлены решения p^O уравнения Колмогорова для соответствующих инфинитезимальных матриц An) (n = 5,10,15). Начальные распределения задавались вида (1, 0, 0, А. Легко заметить, что решения стремятся к предельному (для n = ю) значению первого компонента собственного вектора инфинитезимальной матрицы, который показан пунктирной линией.

Рис. 1. График поведения компоненты pA) решения уравнения Колмогорова для инфинитезимальных матрицAn)

Аналогичная картина наблюдается и в том случае, когда одна из строк матрицы представляет собой расходящийся ряд. Например, для случая n = 5 последняя строка матрицы имеет вид (1,1,1,1, - 5. На

19

рис. 2 представлены решения уравнения Колмогорова для инфинитезимальных матриц размерностью n = {5,15} с расходящимся рядом (сплошной линией) и соответствующие решения для сходящихся рядов (пунктиром).

1

ex 4

1

exth(

1

x -1.3

1

exch(

1

x -1.2

2.8

ex4 ,

th

1

x -1.3

Рис. 2. График поведения решения уравнения Колмогорова для инфинитезимальных матриц размерности n = {5,15} с расходящимся рядом

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

Значения компонентов р1 собственного вектора инфинитезимальной матрицы размерности n

n Р1

5 0.471608 0.472563

10 0.448391 0.452449

15 0.441258 0.446921

20 0.436602 0.443301

25 0.432906 0.439821

30 0.429618 0.436376

35 0.427278 0.434072

40 0.424726 0.430964

45 0.422531 0.428262

50 0.420564 0.42579

55 0.419752 0.425631

60 0.418429 0.424094

ГО 0.412662 0.422695

Кроме инфинитезимальных матриц, заданных числовыми последовательностями, были исследованы матрицы, элементами которых являются функциональные ряды, представляющие собой разложения в ряд Тейлора гиперболических функций с аргументом вида 1/t в бесконечно удаленной точке. Например, для n = 5 были выбраны следующие функции:

Сходимость компонент собственного вектора к предельному значению происходит довольно быстро. На рис. 3 показан график первого компонента собственного вектора матрицы для n = 5 и n = 15 . Как и в случае числовых последовательностей, если одна или несколько строк представляют собой расходящиеся ряды, сходимость сохраняется.

0.15

0.125

0.1

0.075

0.05

0.025

10 20 30 40

Рис. 3. График поведения компоненты ыо собственного вектора инфинитезимальной матрицы при n = 5 и n = 15

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

Выводы

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

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

20

РИ, 2008, № 2

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

Литература: 1. Сарымсаков Т.А. Основы теории цепей Маркова. М.: Гостехиздат, 1954. 208 с.2. Баруча Рид А.Т. Элементы теории марковских процессов и их приложения. М.: Наука, 1969. 511 с.3. ЗейфманА.И. Об асимптотическом поведении решений прямой системы Колмогорова // Украинский математический журнал. 1983. № 5. С. 621-624. 4. Валеев К.Г., Жаутыков О.А. Бесконечные системы дифференциальных уравнений. Алма-Ата: Наука, 1974. 415 с.5. Герасин С.Н. Проблемы стабилизации распределений неоднородных марковских систем. Харьков: ХТУРЭ, 1999. 212 с. 6. Зейфман А.И. О равномерной

квазиэргодичности и устойчивости неоднородных марковских цепей с непрерывным временем // Проблемы устойчивости стохастических моделей: Труды семинара ВНИИ системных исследований. 1989. С. 45-47.7. Бабенко К. И. Основы численного анализа. М.: Наука, 1986. 744 с.

Поступила в редколлегию 03.06.2008

Рецензент: д-р техн. наук, проф. Шабанов-Кушнаренко С.Ю.

Герасин Сергей Николаевич, д-р техн. наук, профессор кафедры ВМ ХНУРЭ. Научные интересы: теория стохастических процессов. Хобби: исторический туризм, театр. Адрес: Украина, 61166, Харьков, пр. Ленина, 14, тел 70213-72.

Михайлов Евгений Алексеевич, преподаватель кафедры высшей математики Харьковского университета воздушных сил. Научные интересы: теория стохастических процессов. Хобби: горный туризм. Адрес: Украина, 61000, Харьков, ул. Сумская, 77/79, дом.тел. 714-60-59.

УДК519.63:519.85:533:532.542

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НЕСТАЦИОНАРНОГО НЕИЗОТЕРМИЧЕСКОГО ТЕЧЕНИЯ ГАЗА ПО УЧАСТКУ ТРУБОПРОВОДА

ТЕВЯШЕВ А.Д., СМИРНОВА В.С._________

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

1. Введение

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

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

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

2. Построение математической модели

Основные дифференциальные уравнения, описывающие неустановившееся движение газа в трубопроводе, получим из общих теорем газовой динамики: интегральных законов сохранения массы, количества движения и энергии. Выделим в газе произвольный неподвижный объем Q, ограниченный поверхностью ю с заданным на ней единичным вектором внешней нормали n. Тогда в случае отсутствия внутренних источников притока массы, согласно [4], законы сохранения можно записать в следующем виде:

— J pdQ + ] pv • ndra = 0,

dt Q ш

_d

dt

j pvdQ + j pvv • ndra =

Q ю

= -J pndro + j pFdQ+ j fdro

ю Q ю

d r

dt і/

(

,2 )

v

u +— 2

v

(

Ш + jp

,2 )

u + -

V

v • ndra =-J pv • ndra +

2

+ jpv• FdO+jv• fdra+jQdQ-jq• ndra .

Здесь p - плотность газа; p - давление; v - векторное поле скоростей; F и f - векторы плотности массовых и поверхностных сил соответственно; u - удельная (отнесенная к единице массы) внутренняя энергия газа; Q - отнесенная к единице объема мощность внешних по отношению к газу источников тепла; q -вектор плотности потока тепла, переносимого посред-

РИ, 2008, № 2

21