Введение в технологию моделирования на основе направленных графов

Автор: Клиначёв Н.В.
Источник: http://model.exponenta.ru/lectures/sml_02.htm

Графов теория

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

Граф направленный (сигнальный)

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

Узел направленного графа

Сумматор координат модели динамической системы с одним выходом (поэтому узел направленного графа называют координатой). Обычно в каждом энергетическом домене в качестве координат выступают парные физические величины, чье произведение есть мощность. В пакетах математического моделирования эти парные физические величины называются координатами первого и второго рода. Выходные координаты ветвей собираются в узлы направленного графа согласно постулатам о сохранении материи и энергетического потенциала (первый и второй законы Кирхгофа¹). Узлы направленного графа, ровно как и сам граф, не отражают различий в физической природе координат первого и второго рода (это непреодолимый недостаток направленных графов).

Ветвь направленного графа

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

Контур

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

---

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

²⁾ И для одного энергетического домена закон Ома может иметь несколько форм записи. Например, для электрического домена формула закона Ома отлична для активного сопротивления, индуктивного и емкостного.

Принцип поточного исполнения блок-схем (моделей)

Программы математического моделирования динамических систем относятся к графическим средам разработки иерархически структурированных программ верхнего уровня, и часть из них основана на поточной модели управления. Поточная модель управления – это основополагающее понятие для таких програм, как VisSim, MBTY, Simulink, Easy5. Приведем определение:

Поточная модель управления (Data Flow)

Модель программирования, в которой инструкции, процедуры или функции выполняются только тогда, когда все входные данные (т.е. параметры и аргументы) готовы. Альтернативной моделью программирования является командное управление (Control Flow) в которой счетчик команд контролирует переход в памяти программ от одной команды к другой при их последовательном выполнении.

Рассмотрим пример:

Система уравнений модели составленная пользователем	Упорядоченный программой информационный поток
a) w = log(r) b) e = 1 c) r = e - q d) q = sin(e)	1) e = 1 2) q = sin(e) 3) r = e - q 4) w = log(r)

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

Статический информационный поток, составленный с помощью элементарных библиотечных блоков программы VisSim

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

Библиотеки блоков графических языков

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

1. Блоки - источники сигналов
2. Блоки - преобразователи сигналов
3. Блоки - приемники сигналов
4. Блоки, которые одновременно являются источниками, приемниками и преобразователями сигналов, т.е. это блоки обладающие эффектом памяти (кроме "УВХ")
5. Блоки (структуры) для программирования потока
6. Блоки (структуры) для синхронизации потоков

Большое количество блоков может наблюдаться только в группе преобразователей сигналов. Минимально необходимым является количество 100^+/-10 блоков. Это блоки элементарных математических операций:

1. Арифметические
2. Логические
3. Трансцендентные
4. Матричные
5. Нелинейные
6. Обладающие эффектом памяти

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

Блоки обладающие эффектом памяти

Фундаментальными для построения моделей являются блоки обладающие эффектом памяти. В этой группе два элементарных блока:

• 1/S – "Интегратор" (дискретный квазианалог интегратора)
• 1/Z – "Регистр задержки"

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

В библиотеках программ математического моделирования можно найти еще ряд блоков обладающих эффектом памяти:

• Блок "Передаточная функция"
• Блок "Пространство состояний"
• Блок "Звено чистого запаздывания"
• Блок "Устройство выборки-хранения"¹

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

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

y[n] = y[-1] + _m=0^n-1∑ x[m] ,

где: x[n] - входной сигнал, y[n] - выходной сигнал, n - индекс решетчатой функции.

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

y [n] = y [n-1] .

---

¹⁾ Следует помнить, что УВХ является лишь преобразователем сигнала, т.е. не порождает информационный поток.

Понятие о начальных условиях модели (Initial Condition)

Начальные условия

Значения физических величин первого или второго рода (чье произведение всегда есть мощность) характеризующие динамическое состояние процесса преобразования энергии в системе в интересующий момент времени (обычно это начало функционирования). При моделировании систем начальные условия задаются в силу существования законов коммутации для реактивных по своей природе физических устройств, т.к. их энергетическое состояние не может измениться мгновенно. Начальным условием может быть либо величина потока материи (электрической, магнитной, тепловой, гидравлической, механической, акустической или ротационной) в L-сопротивлении, либо разность энергетических потенциалов (соответствующей природы) на выводах C-сопротивления.

Если рассматривать первый шаг симуляции (n=0), то из сотен библиотечных блоков только те, что обладают эффектом памяти, могут иметь на своих выходах ненулевые значения y[-1]. Эти значения как раз таки и являются начальными условиями и устанавливаются вручную для блоков 1/S и 1/Z (а так же для тех, что построены на их основе).

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

Понятие о параметрах модели

Параметры модели

Физические величины, которые характеризуют модель независимо от ее текущего динамического состояния. К параметрам относятся: сопротивления¹ (электрическое, магнитное, тепловое, гидравлическое, механическое, акустическое, ротационное, и т.д.); отношения сопротивлений (коэффициенты передачи); меры инерционности (постоянные времени).

¹⁾ Если речь идет о сопротивлениях реактивного характера, то в качестве параметров могут выступать физические величины их определяющие (например, индуктивность катушки, емкость конденсатора, и т.д.).

Понятие о методах интегрирования

На компьютерах, дискретных по своей природе, реализовать интегратор, лишенный методических погрешностей невозможно. Существует группа классических подпрограмм (функций), которые реализуют операцию интегрирования. В простейшем случае математическая функция, закрепленная за всеми интеграторами модели, имеет вид: y [n] = y [n-1] + x [n], - где: x [n] - входной аргумент, y [n] - возвращаемое значение. Погрешности у этих подпрограмм в конкретных ситуациях проявляются по-разному, поэтому все программы математического моделирования в своих настройках содержат переключатель методов интегрирования. Обычно в список входят следующие методы:

• Эйлера (с запаздыванием)
• Трапециидальный
• Рунге-Кутта 2-ого порядка
• Рунге-Кутта 4-ого порядка
• Адаптивный Рунге-Кутта 5-ого порядка
• Адаптивный Булирша-Стоера
• Эйлера (с упреждением)

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

Выбор шага симуляции и метода интегрирования

Шаг симуляции

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

При компьютерном моделировании существенными следует считать четыре источника погрешности:

• Трансцендентные функции, которые вычисляются компьютером путем аппроксимации полиномиальными или степенными рядами:
  
• Дискретный квазианалог интегратора (блок 1/S).
• Итерационный решатель (тот или иной классический алгоритм, предназначенный для решения алгебраических уравнений путем подбора независимых переменных до заданной точности).
• Математический сопроцессор компьютера, чья дискретная природа требует округлений, которые, в свою очередь, обычно проявляются в виде шума при дифференцировании меняющихся в большом диапазоне параболических сигналов n-ого порядка.

Погрешности дискретных квазианалогов интеграторов играют решающую роль в компьютерном моделировании. На рисунке показано, как дискретный квазианалог интегратора (блок 1/S) обрабатывает сигнал синусоидальной формы. Наглядно видно, что при уменьшении шага симуляции погрешность интегрирования дискретным квазианалогом интегратора снижается. Это основное правило, которому надо следовать при настройке параметров симуляции.

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

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

Переходные процессы в системе вызваны ненулевыми начальными условиями. Частотная характеристика разомкнутой системы очевидна (-40 дБ/дек. & -180°). Методу Эйлера с запаздыванием соответствует расходящийся переходный процесс; методу Эйлера с упреждением – сходящийся; методу трапеций – синусоида с постоянной амплитудой

Каскадные алгебраические петли

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

Однако гораздо чаще в блок-схемах наблюдаются обратные связи (ОС). На рисунке приведена структурная схема апериодического звена первого порядка. Систему уравнений, соответствующую этой блок-схеме, составить легко:

a) g = 1 b) x = g - y c) u = 3 * x d) y = o∞ ∫ u dt e) график = y

А как составить информационный поток? Для вычисления координаты x надо знать координату y; для вычисления координаты y надо знать координату u; а для вычисления координаты u надо знать координату x. Ситуация кажется тупиковой, но это не так, и только лишь потому, что в контуре (петле) присутствует блок обладающий эффектом памяти (1/S).

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

y[n] = y[-1] + _m=0^n-1∑ u[m] .

Текущее значение входного сигнала в формуле обозначено индексом n-1, выходное значение индексом n. Легко понять, что на текущем шаге выходное значение дискретного квазианалога интегратора ни как не определено текущим входным значением (связь между текущим входным значением и выходным значением на следующем шаге симуляции не отвергается). Повторим эту мысль в более общей формулировке. На текущем шаге симуляции состояние выходов всех блоков обладающих эффектом памяти не зависит от входного сигнала.

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

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

где: reg – внутренний регистр дискретного квазианалога интегратора, хранящий текущее значение интеграла; y[-1] - начальное условие.

Если на месте интегратора будет безынерционная функция, то составить информационный поток невозможно - это и есть алгебраическая петля. Алгебраические петли появляются либо при неверном методическом подходе к решению неявных уравнений, либо при ошибочном проектировании цепей обратной связи САР (см. красную цепь на рисунке).

Реальные САР всегда обладают инерционными свойствами. Поэтому более точные математические модели САР обычно не содержат алгебраических петель.

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

Каскодные алгебраические петли

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

Существует несколько способов разрыва подобной петли. Разные программы математического моделирования, использующие направленные графы (VisSim, Simulink и пр.) разрывают каскодные алгебраические петли так, как показалось правильным их авторам (не предупреждая об этом пользователя). Часто точка разрыва каскодной петли, а, следовательно, и результаты симуляции меняются в зависимости от того, какие блоки подключены к выходам (происходит это по причине разной приоритетности математических операций).