Файл: Шнепс, М. А. Численные методы теории телетрафика.pdf

снизу отметки указывают множители, соответствующие корневым лесам рнс. 4.3п и б.

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

Если вычислить значение M без приведения подобных членов, то получим сумму произведений с коэффициентами +1 и — 1. Каж­ дое из этих произведений содержит g множителей, взятых по одно­ му из каждого столбца. Система дуг, соответствующая множеству таких множителей одного слагаемого, удовлетворяет двум первым условиям для корневого леса: из каждой вершины множества Xj исходит одна дуга, каждая дуга имеет начальную вершину в Xj. Третье условие может быть выполненным-— тогда мы имеем дело с корневым лесом, или же невыполненным — тогда все (или неко­ торые) из дуг образуют контур. Для доказательства теоремы уста­ новим, что:

1) произведения типа Р, являющиеся весами корневых лесов, появляются в значении М точно один раз с коэффициентом + 1;

2) произведения типа R, соотве;тст1в'ующие системе дуг -с конту­ ром, исчезают шасле приведения подобных членов.

Рассмотрим вес Р определенного корневого леса множества J. Число появлений и коэффициенты Р в значении М не изменятся, если мы аннулируем все ац, не входящие множителями в Р. Такое

преобразование переводит М в некоторый определитель М. Пока­

жем, что Р = М. Для этого применяем индукцию. Если порядок М равен 1, утверждение очевидно. Пусть оно правильно для мино­ ров порядка k и пусть рассматриваемый вес Р имеет (/е+1) мно­ житель.

Всякий корневой лес содержит не менее одной дуги, конечная вершина которой лежит вне Xj. Пусть (7, j) такая дуга. Множитель

тель, полученный из М отбрасыванием i-ro столбца и строки, т. е. порядка к; множество номеров столбцов этого определителя — это J, за исключением г. С другой стороны, нетрудно видеть, что мно­ жителям произведения Р' — Pja^ соответствует корневой лес данно­

/г-столбцах его аннулируем все ац, не входящие в Ri, и вычислим значение преобразованного определителя, который в блочной запи­ си имеет вид:

Значение этого определителя равно произведению значений оп­ ределителя D и определителя, стоящего в левом верхнем углу, т. е. нулю, так как сумма строк последнего определителя — нулевая строка. Следовательно, все слагаемые в выражении минора М, содержащие множитель Ri, аннулируются после приведения подоб­ ных членов. Теорема доказана.

Ценность установленной теоремы в ее -следствиях, некоторые из которых мы укажем. Для численных же расчетов значительно бо­ лее удобной является некоторая модификация алгоритма Гаусса, которая будет указана в § 4.3.

Пусть матрица А приведена к виду (7). Так как матрица В отличается от А только знаками всех ненулевых элементов, то зна­ чения миноров А и В будут либо совпадать, либо отличаться зна­ ком (при нечетных порядках). В силу определения из любой вер­ шины исходной или промежуточной компоненты достижима хотя бы одна вершина стационарной компоненты. Следовательно, для каждой компоненты одного из двух первых видов существует кор­ невой лес и в (7) матрицы Bi,..., Ви, С),..., С; — все неособенные. Напротив, все матрицы Di,..., Dm — особенные, так как из вершин любой стационарной компоненты недостижима ни одна вершина вне этой компоненты. Поэтому также и каждому множеству Xj, содержащему все вершины некоторой стационарной компоненты,

66

соответствует главный минор с нулевым значением. Однако если из стационарной компоненты исключить хотя бы одну вершину, то остается множество с корневыми лесами. Поэтому ранг любой из матриц Di,..., Dm в точности на единицу меньше ее порядка. Если порядок А равен п, то ранг равен п—т, так как для получения мно­ жества с корневым лесом из множества X всех вершин необходимо исключить хотя бы одну вершину из каждой стационарной компо­ ненты.

4.2.ИЗУЧЕНИЕ МАТРИЦЫ ИНТЕНСИВНОСТЕЙ ПЕРЕХОДА

1.Вычисление переходных вероятностей

Впределах этого раздела / — множество индексов тех состоя­ ний Si, для которых заданы начальные значения /?,•(0 )> 0 , и Н —

жим хотя бы из одного t'6 /.

Как известно, если элементы матрицы А постоянные или являют­ ся функциями от t, подчиненными определенным условиям регу­ лярности (которые удовлетворены в большинстве приложений),

Коэффициенты правой части (12) получаются подстановкой /=0 в (11) и в уравнения, которые дает дифференцирование (11). Если А не зависит от t, то (12) можно написать в виде

я (о =

1=0

Указанные разложения можно использовать, например, для чис­ ленного расчета величин р,(7) при достаточно малых />0. В дан­ ном случае целесообразно привести А к виду (7), так как этот вид сохраняется и при возведении А в степень и при дифференцирова­ нии А. Если не все / достижимы из /, то некоторое упрощение рас­ четов можно получить на основе следующей теоремы.

Теорема 4.2. 1. Пусть v — наименьшая степень, такая, что

xj 6PV Н. Тогда

р,- (f) = a v tv + «v-н ^v+1 + . . ., av > 0.

2. Если индекс k недостижим из I, то ph(t) = 0.

Действительно, тири v = 0 имеем Г°Н = Н, и первая часть теоремы

при /= 0 первое слагаемое правой части равно нулю, а в числе ос­ тальных неотрицательных слагаемых хотя бы одно строго положи­

следовательно, все производные величин #г- неотрицательные, т. ё. эти величины не убывают с возрастанием /. Но тогда свойство неот­ рицательности всех q-} и их производных сохраняется для всех

Следовательно,

<7/(0 > 9/(°)

для всех j, в частности выполняется (14).

Выберем момент /i>0, для которого имеет место следствие тео­ ремы 4.2, в качестве нового начального времени для применения теоремы 4.3. Получаем следующее следствие.

С л е д с т в и е . Для всех /, достижимых из 1,

Р/ (0 > 0

для любого конечного />0; P j ( t ) может аннулироваться только при /->-оо.

Оценка типа (14) соответствует некоторому усеченному про­ цессу. Можно ожидать, что другие модификации исходного процес­

68.

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

Точные решения (11) или системы (3) можно получить, приме­ няя преобразование Лапласа или используя фундаментальную си­ стему решений. Собственные значения матрицы А, т. е. решения уравнения

Det {sE — А) = О

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

(Пароди [115]).

Теорема 4.4. Матрица А имеет всегда собственное значение 5 = 0, которому соответствуют линейные элементарные делители, ес­ ли это значение кратное. Все другие собственные значения принад­

Из последнего утверждения теоремы следует, что для всех не­ нулевых собственных значений имеет место

— 2тах cti < Re (s) < 0. i

В силу теоремы 4.4 при любых начальных условиях любое из Pi(t) можно представить в виде

P iV )= P i+

к

где Pi — постоянные; Su — пробегает все множество ненулевых собственных значений; fih(t) — полиномы от t, степень которых не ■превышает кратности Sh, уменьшенной на единицу. В силу отри­ цательности действительных частей 'всех Sk^O для всех i

lim Pi {t) = ph t-*со

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

2.Свойства стационарных вероятностей с учетом классификации состояний

Стационарными вероятностями будем называть любую систе­ му неотрицательных постоянных рь удовлетворяющих условию нор­

мировки 2 p i= 1 и системе (3), которую запишем в виде i

69