Автор: Черкасов Артём Владимирович

Рубрика: Технические науки

Опубликовано в Молодой учёный №22 (156) июнь 2017 г.

Дата публикации: 03.06.2017

Статья просмотрена: 8 раз

Библиографическое описание:

Черкасов А. В. Исследование методической погрешности метода квазиэквивалентного укрупнения состояний марковских моделей // Молодой ученый. — 2017. — №22. — С. 98-104.



В предыдущей статье «Принцип квазиэквивалентного укрупнения состояний марковских моделей» мы выяснили, что при квазиэквивалентном укрупнении выходные характеристики Nср (среднее число заявок в системе «процессоры-каналы») и M [tр] (среднее время реакции системы ) системы ведут себя закономерно — увеличиваются с ростом λ (интенсивность поступления заявок) и уменьшаются с ростом μ (интенсивность обслуживания). Следовательно, метод квазиэквивалентного укрупнения заслуживает более детального изучения, в особенности его методической погрешности и её влияния на итоговый результат работы АИС.

Рис. 1. Графы переходов для двухпроцессорной системы: а) граф исходного процесса; б) граф процесса с эквивалентным укрупнением состояний; в) граф процесса с квазиэквивалентным укрупнением состояний

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

(1)

Преобразуем (1).

(2)

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

Второе и последующие приближения будет выглядеть аналогично (3). В общем виде уравнения будут выглядеть так:

(3)

(4)

где αi = (M-i)*α, βi =, λj = (N-j)*λ,

Во время выполнения каждой итерации будем подсчитывать разности значений и вычислять максимум из них. Кроме того, будем анализировать погрешность выходных значений Nср, M [tр], Mср, вычисленных при помощи метода квазиэквивалентного укрупнения (нулевая итерация) и точным методом (финальная итерация). Возьмём Tотк = 100, Tвосст = 10, Tобд = 10, Tреш = 5. Построим график зависимости для системы с заданными характеристиками:

Рис. 2. График зависимости при N=5, M=2 и 10 итерациях

Как видим, при заданных входных параметрах динамика значений максимальных разностей меняется крайне скачкообразно на начальных итерациях. Значения Nср, M [tр] и Mср для метода квазиэквивалентного укрупнения соответственно равны 2,143, 7,503, 1,803, для точного метода — 2,173, 7,686, 1,808. Погрешности их значений составляют 1,38 %, 2,44 % и 0,28 % соответственно. Но что будет, если увеличить количество итераций до 100?

Рис. 3. График зависимости при N=5, M=2 и 100 итерациях

Ситуация улучшилась — значения на последующих итерациях стали плавно уменьшаться. Значения Nср, M [tр] и Mср для точного метода при 100 итерациях соответственно равны 2,19, 7,796, 1,803, а их погрешности — 2,2 %, 3,91 % и 0,02 %. Проверим состояние графика при 1000 итераций.

Рис. 4. График зависимости при N=5, M=2 и 1000 итераций

На 1000 итераций значения выходных характеристик для точного метода составляют 2,19, 7,794, 1,803, а их погрешности — 2,18 %, 3,88 % и 0 %. При дальнейшем увеличении числа итераций Nср, M [tр] и Mср для точного метода сохраняют данные значения. Так или иначе, для рассматриваемой системы метод квазиэквивалентного укрупнения однозначно сходится.

Рассмотрим более обширную систему. Возьмём N=30, M=5. Значения Tотк, Tвосст, Tобд и Tреш оставим прежними. Число итераций сразу поставим равным 1000.

Рис. 5. График зависимости при N=30, M=5 и 1000итерациях

Метод сходится гораздо быстрее, чем для системы с меньшим числом терминалов и процессоров, а значения Nср, M [tр] и Mср для точного и квазиэквивалентного метода совпадают: 21,279, 24,4 и 4,36.

Увеличим число терминалов до 50, а число процессоров — до 10. Все остальные значения оставим прежними.

Рис. 6. График зависимости при N=50, M=10 и 1000 итерациях

При расширении системы график приближается к оси абсцисс ещё быстрее. Однако, значения выходных характеристик для 2-х методов на 1000-й итерации всё ещё различаются: для квазиэквивалентного метода Nср = 34,292, M [tр] = 21,83 и Mср = 7,854, для точного метода — 34,302, 21,85, 7,85. Погрешности данных значений составляют 0,03 %, 0,09 % и 0,05 %соответственно. Если увеличить число итераций до 2000, значения выходных характеристик для обоих методов станут равными.

Сравним на трёх вышеописанных системах поведение выходных характеристик Nср и M [tр] при изменении входных параметров для квазиэквивалентного и точного методов. Для начала зафиксируем значения Tвосст = 10, Tобд = 10, Tреш = 5 и исследуем зависимость Nср(α), где α=1/Tотк (рис. 7). Количество итераций возьмём равным 2000.

Рис. 7. Графики зависимости Nср(α): а) для N=5, M=2; б) для N=30, M=5; в) для N=50, M=10

Как видим, для систем большой размерности (рис 7б и 7в) графики для обоих методов совпадают. Максимальная погрешность для системы с 5-ю терминалами и 2-мя процессорами (рис 7а) составила не более 4,5 %.

Теперь зафиксируем Tотк = 100 и исследуем зависимость Nср(β), где β=1/Tвосст (рис. 8). Остальные параметры оставим прежними.

Рис. 8. Графики зависимости Nср(β): а) для N=5, M=2; б) для N=30, M=5; в) для N=50, M=10

Равно как и в предыдущем случае, графики для систем большей размерности (рис. 8б и 8в) совпадают. Максимальная погрешность для системы с 5-ю терминалами и 2-мя процессорами (рис 8а) составила не более 6,4 %.

Исследуем зависимость M [tр](λ), где λ=1/Tобд (рис. 9), с ранее зафиксированными значениями Tотк, Tвосст и Tреш.

Рис. 9. Графики зависимостиM [tр](λ): а) для N=5, M=2; б) для N=30, M=5; в) для N=50, M=10

Для 3-х рассмотренных систем графики сходятся по мере увеличения интенсивности обдумывания. Т. е. чем меньше Tобд, тем меньше выходная погрешность времени реакции. В среднем расхождение между значениями M [tр](λ) для квазиэквивалентного и точного методов не превысило 3 %.

Рассмотрим финальную зависимость M [tр](μ), где μ=1/Tреш (рис. 10).

Рис. 10. Графики зависимости M [tр](μ): а) для N=5, M=2; б) для N=30, M=5; в) для N=50, M=10

Ситуация прямо противоположная зависимости M [tр](λ) — чем больше Tреш, тем меньше выходная погрешностьM [tр]. Для исследованных систем расхождение между значениями M [tр](μ) варьируется в пределах 1–2 %.

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

Литература:

  1. Шкатов П. Н. Стохастические модели в анализе информационно-вычислительных систем. Учебное пособие
Основные термины (генерируются автоматически): квазиэквивалентного укрупнения, метода квазиэквивалентного укрупнения, точного метода, График зависимости, квазиэквивалентного укрупнения состояний, значения выходных характеристик, метод квазиэквивалентного укрупнения, Графики зависимости, укрупнения состояний марковских, итераций значения выходных, квазиэквивалентного метода, погрешности метода квазиэквивалентного, Максимальная погрешность, точного методов, погрешность метода квазиэквивалентного, числа итераций nср, погрешность выходных значений, укрупнением состояний, методу итераций, Значения Nср.

Обсуждение

Социальные комментарии Cackle
Задать вопрос