Содержание к диссертации
Введение
ГЛАВА 1. Гибридные системы и программное обеспечение для их моделирования 33
1.1 От таймированного автомата к гибридному. 35
1.2 От классических динамических к гибридным системам. 41
1.3 Компьютерное моделирование динамических систем . 55
1.3.1 Математические пакеты. Однокомпонентные модели. 55
1.3.2 Многокомпонентные модели. 56
1.3.3 Графические оболочки на базе гибридных автоматов. 60
1.3.4 Автоматическое Формирование итоговой системы. 62
1.3.5 Численные методы для решения гибридных АДУ. 63
1.3.6 Динамический графический образ. 65
1.3.7 Язык проведения вычислительного эксперимента. 66
Выводы и результаты. 68
Литература 69
ГЛАВА 2. Открытые гибридные системы 72
2.1 Предпосылки. 76
2.2 Изолированный примитивный гибридный автомат. 85
2.3 Траектории примитивного гибридного автомата . 91
2.4 Вырожденное поведение. Автомат Зенона. 94
2.5 События, сигналы. 100
2.6 Примитивный автомат с несколькими переходами. 102
2.7 Автомат с несколькими длительными состояниями. 104
2.8 Композиция гибридных автоматов. 107
2.9 Открытый примитивный гибридный автомат 110
2.10 Блок-схемы открытых автоматов. 112
2.11 Открытый гибридный автомат с контактами. 125
2.12 Частичная синхронизация гибридных автоматов. 128
2.13 О практической ценности примитивных автоматов. 129
Выводы и результаты. 129
Литература 132
ГЛАВА 3. Формирование и структурный анализ уравнений, продвижение модельного времени . 134
3.1 Структурный анализ уравнений. 138
3.2 Структура анализатора в пакете MVS. 149
3.2.1 Вычислимые последовательности ФОРМУЛ. 150
3.2.1 Структурно невырожденные системы нелинейных алгебраических уравнений 153
3.2.3 Системы нелинейных алгебраических уравнений с подстановками. 155
3.3.3 Системы дифференциальных уравнений. 156
3.3 Поиск точки переключения 157
3.3.1 Поиск в условиях, когда можно вычислить только значение предиката в окрестности точки переключения. 160
3.3.2 Поиск в условиях, когда можно вычислить не только значение функции, определяющей точку переключения, но и ее производную. 161
3.3.3 Поиск в условиях, когда точка переключения определяется как корень уравнения на решении, описывающем поведение. 162
3.3.4 Программная реализация поиска точек переключения 164
3.4 Построение графиков функций. 169
3.4.1 Проблемы, возникающие при построении графиков. 170
3.4.2 Аккуратные графики 174
3.4.3 Синхронное и асинхронное построение графиков 177
Синхронный способ. Возможные алгоритмы 181
Выводы и результаты 181
Литература 183
ГЛАВА 4. Математическое обеспечение для моделирования гибридных систем 184
4.1 Организация библиотеки 184
4.2. Структура решателей 186
Автоматические решатели. 186
Решатели для задач конкретного типа 187
Решатели для отладки. 187
4.3 Системы нелинейных алгебраических уравнений . 196
Программы для решения нелинейных уравнений 196
Программа автомат 199
4.4 Дифференциальные уравнения. 200
Программы для решения нежестких уравнений. 202
Программы для решения жестких уравнений. 204
Программа автомат. 206
Отладочные программы 208
4.5 Алгебро-дифференциальные уравнения 209
Явный способ 210
Неявный способ
Программа - автомат для решения алгебро-дифсЬеренциальных уравнений 212
4.6 О реализации матричных операций в MVS 213
Реализация матричных вычислений. 215
Подпрограммы первого УРОВНЯ. 215
Подпрограммы второго УРОВНЯ. 218
Операции третьего уровня. 222
О реализации численных методов на Паскале. 225
4.7 Тестирование библиотеки. 226
Проверочные примеры систем нелинейных алгебраиче ских уравнений 230
Системы линейных уравнений для оценки точностных характеристик. 232
Системы линейных уравнений для оценки временных характеристик. 232
Системы нелинейных уравнений. 232
Нелинейное скалярное уравнение 233
Проверочный пример 1. 233
Проверочный пример 2. 234
Проверочный пример 3. 235
Проверочный пример 4. 235
Проверочный пример 5. 236
Проверочный пример 6. 237
Проверочный пример 7. 238
4.9 Тестирование численных методов для проекта «Открытая физика». 238
Тестовые задачи с устойчивыми ОДУ. 243
Тестовые задачи с неустойчивыми ОДУ. 245
Выводы и результаты 252
Литература
- Компьютерное моделирование динамических систем
- Траектории примитивного гибридного автомата
- Структурно невырожденные системы нелинейных алгебраических уравнений
- Системы нелинейных алгебраических уравнений
Введение к работе
Разработка и исследование универсальных программных комплексов автоматизированного проектирования, анализа и визуализации сложных динамических систем для различных естественнонаучных и технических областей остается одной из ключевых проблем теории и практики вычислительного эксперимента.
Актуальность темы.
Термин «сложные динамические системы» сегодня чаще всего употребляется для обозначения класса динамических систем, который мог бы называться иерархическими событийно-управляемыми динамическими системами переменной структуры и состава. Под сложностью систем понимается - 1) сложность поведения и 2) сложность структуры, 3) переменный, зависящий от времени состав моделируемых объектов и 4) большое число решаемых уравнений. Сложные динамические системы отличаются высоким уровнем абстракции, трудно воспринимаются человеком и требуют визуализации и на стадии проектирования модели, и при ее анализе.
Сложные динамические системы чрезвычайно востребованы практикой и для их моделирования во всем мире создаются программные комплексы визуального моделирования, включающие в себя графические языки проектирования и отладки моделей, управления вычислительным экспериментом, средства визуализации поведения и интерактивного вмешательства в ход эксперимента.
Сложность поведения модели, прежде всего, связана с наличием нескольких режимов, смена которых обусловлена наступлением внешних или внутренних событий. Сегодня уже не достаточно изучать каждый режим отдельно. Необходимо строить модель всего изучаемого объекта и исследовать ее как единый объект. Для описания и исследования сложных объектов требуются новые математические модели.
Сложность структуры в сочетании со сложностью поведения также требует решения новых научных задач. Современные методы проектирования основаны на блочном, агрегатном подходе, в котором новая модель собирается в основном из унифицированных компонентов и немногочисленных уникальных блоков. Затем она автоматически представляется в виде большой, трудно воспринимаемой человеком, требующей численного решения, системы уравнений. Для построения модели используются два типа блоков - блоки с входами-выходами, пришедшими из теории управления, и блоки с контактами, успешно используемыми при проектировании механических, гидравлических и электрических систем. Сложные модели, состоящие из компонентов различной физической природы и оснащенные цифровыми системами управления, требуют одновременного использования блоков различного типа. Автоматическое построение совокупной системы уравнений, форма и число которых зависят от времени, и выбор подходящего для нее численного метода становится актуальной теоретической и технической задачей.
В последнее время интерес к графическим языкам моделирования настолько вырос, что их стали рассматривать независимо от реализующих их программных сред. Появились языки, претендующие на звание универсальных. Это - Универсальный Язык Моделирования (UML) и язык «физического» моделирования Modelica. В то же время наиболее распространенным остается подход, реализованный совокупностью компонентов Simulink, Stateflow, SimMechanics, SimPowerSystems пакета Matlab.
Графический язык компонента Simulink (восходящий еще к эпохе аналоговых машин) и язык Modelica поддерживают работу с моделями, режимы поведения и, следовательно, структура решаемых уравнений которых практически не меняются во времени.
Настоятельная практическая потребность моделировать событийно-управляемые объекты заставила авторов Matlab ввести еще один компонент - Stateflow, с помощью которого непрерывные и дискретные модели компонента Simulink управляются картами состояния Харела, а необходимость поддерживать «физическое» моделирование - компоненты SimMechanics, SimPowerSystems.
Первоначально авторы языка Modelica предполагали, что в рамках «физического» моделирования им удастся проектировать модели с различными режимами поведения. Однако им не удалось справиться с трудностями, возникающими в этом случае при формировании совокупной системы. Возможность менять форму и число уравнений при различных режимах в последних версиях языка ограничена.
Описывать и изучать объекты со сложным поведением можно с помощью гибридных систем.
Понятие гибридной системы было введено в начале 90-х годов прошлого столетия с целью распространить методы исследования конечных автоматов на сложные динамические системы с непрерывным временем. Появились программные комплексы символьной верификации, такие как HyTech. Однако возможности этого подхода пока еще ограничены и позволяют исследовать только очень простые гибридные системы.
В середине 90-х автором было предложено использовать гибридные автоматы как основу графических языков программных комплексов для визуального моделирования и численного исследования сложных динамических систем.
Этот подход был в дальнейшем реализован в семействе графических оболочек Model Vision. За рубежом одновременно с первым универсальным пакетом MV 2.1 семейства появился программный комплекс SHIFT для моделирования задач частного типа, а позже гибридные автоматы для численного моделирования стали использовать авторы программных оболочек Ptolemy II и Charon.
Цель работы.
Целью работы является разработка основ теории гибридных систем, необходимой для создания графических оболочек, предназначенных для численного моделирования иерархических, многокомпонентных, событийно-управляемых систем, состоящих из компонентов с различными типами связей, поведение которых представлено гибридными автоматами, и воплощение теоретических положений в конкретных программных продуктах.
Основные задачи.
Для достижения этой цели ставились следующие задачи. Разработать:
- требования к графическим оболочкам, обеспечивающие быстрое, эффективное и надежное моделирование и численное исследование событийно-управляемых динамических систем;
- основы теории открытых гибридных систем, графическое представление которых в виде открытых гибридных автоматов может быть положено в основу нового графического языка моделирования и поддерживающего его математического обеспечения;
- методы синхронизации открытых гибридных систем и реализовать их в виде алгоритмов;
- структуру математического обеспечения, поддерживающего формализм открытых гибридных автоматов, и реализовать ее в виде численных библиотек на различных алгоритмических языках.
Методы исследования
Для решения поставленных задач использовались теория систем, в частности теория непрерывно-дискретных или гибридных систем, систем с переменной структурой, а также разделы численного анализа, посвященные вычислительным методам линейной алгебры, решению систем нелинейных алгебраических, обыкновенных дифференциальных и алгебро-дифференциальных систем.
Научная новизна
Впервые в мировой практике при создании программных комплексов визуального моделирования сложных динамических систем использован, разработанный автором, формализм открытых гибридных автоматов.
Разработаны основы теории открытых гибридных систем, что позволило автоматизировать процесс проектирования и численного исследования многокомпонентных иерархических событийно-управляемых динамических систем, в состав которых могут входить блоки различной физической природы со сложным поведением.
Упрощена и систематизирована теория изолированных гибридных систем за счет введения нового понятия - «примитивного гибридного автомата», ориентированного на использование гибридных автоматов для численного моделирования, и расширяющего класс исследуемых моделей до систем алгебро-дифференциальных уравнений
Предложен новый принцип синхронизации открытых гибридных систем. Два метода синхронизации, традиционного дискретного и нового непрерывного типа, реализованы в виде алгоритмов формирования совокупной системы алгебро-дифференциальных уравнений для иерархических функциональных схем с блоками различного типа.
Для автоматизированного построения и анализа совокупной системы уравнений:
- Создана классификация уравнений, требующих предварительной проверки корректности. Она позволяет применять для каждого выделенного типа уравнений более простые численные методы, чем это необходимо для решения систем алгебро-дифференциальных уравнений общего вида.
- Обобщено понятие структурной вырожденности, использовавшееся для систем линейных алгебраических уравнений большой размерности, и доказано, что для проверки корректности всех выделенных типов уравнений может быть применен единый алгебраический подход, в основе которого лежит аналог LU-разложения матрицы инцидентности. - Разработан новый подход, на основании которого можно строить различные алгоритмы поиска точки переключения методом установления. Предложены алгоритмы поиска точек переключения для различных типов предикатов.
Практическая ценность. На базе теории открытых гибридных автоматов разработана структура математического обеспечения, необходимого для моделирования и численного исследования гибридных систем. В частности, разработана структура эвристических управляющих программ, необходимых для автоматического, без участия пользователя, решения уравнений следующих типов: а) систем нелинейных алгебраических уравнений, б) систем обыкновенных дифференциальных уравнений, с) систем алгебро-дифференциальных уравнений, возникающих при построении совокупной системы уравнений по иерархическим функциональным схемам с блоками с входами и выходами и блоками с контактами.
Предложенная структура математического обеспечения реализована в виде численных библиотек: на языке Фортран для семейства графических оболочек Model Vision Studium, на языке Java для графической среды Anylogic, как объектно-ориентированный код на языке Java для проекта «Открытая физика». Показаны преимущества и эффективность разработанного программного обеспечения при решении реальных прикладных задач.
Разработанные графические оболочки (MV 2.1 - свидетельство о регистрации № 950277 от 08. 1995, MVS 3.0 - свидетельство о регистрации № 990643 от 09. 1999) уже на протяжении десяти лет используются во многих научных организациях для научной и конструкторской работы, что подтверждено актами о внедрении.
Графические оболочки успешно используются и в учебном процессе десятков университетов и даже школах: Model Vision в России и странах СНГ (Казахстан, Узбекистан, Украина), проект «Открытая физика» - в США и пакет EJS - в Испании.
Графические оболочки семейства Model Vision по выразительности языка превосходят широко известные компоненты Simulink и Stateflow пакета Matlab и не уступают им по мощности численных библиотек.
Создаваемая в настоящее время версия Model Vision 4.0 решает более широкий класс задач, чем пакет Dymola с входным языком Modelica и компоненты физического моделирования SimMechanics, SimPowerSystems пакета Matlab. Достоверность результатов
Достоверность результатов подтверждается сравнением качества и точности численного моделирования в пакетах семейства Model Vision с результатами моделирования в других пакетах и решением большого количества практических задач. Только в недавно изданном «Справочнике по расчету гидравлических и вентиляционных систем» графическая среда Model Vision использована для решения более 300 задач.
Апробация работы
Результаты работы с 1996 по 2004 год докладывались более чем на 20 конференциях. На ежегодных отечественных конференциях: «Математика, компьютер, образование», «Компьютерное моделирование»,
«Математические методы в технике и технологиях», «Дифференциальные уравнения и их приложения», «Информационные технологии в моделировании и управлении» в Санкт-Петербурге и Москве. На международных конференциях - «Информатика и теория управления» (ICI&C) в Санкт-Петербурге, «Winter Simulation Conference» в Орландо (США), и на конференциях международных ассоциаций WSES (в Греции), ШЕЕ (в Словении), CoLoS (в США, Германии, Франции, Словении).
Реализация и внедрение результатов работы
Численные библиотеки семейства Model Vision (www.exponenta.ru) используются также в графической оболочке AnyLogic (www.xjtek.com), проекте «Открытая физика» (США) (http://webphvsics.davidson.edu). Семейство графических оболочек Model Vision применяется не только в Санкт-Петербурге: в государственном политехническом университете (http://dcn.nord.nw.ru, http://tmm.spbstu.ru), технологическом институте, институте международных образовательных программ (www.imop.spbstu.ru), международном банковском институте, университете водного транспорта, государственном университете аэрокосмического приборостроения и военно-космической академии им А.Ф. Можайского, но в других отечественных университетах и институтах Москвы, Нижнего Новгорода, Новосибирска, Иркутска, Ростова-на-Дону, Пскова, Пензы для научных исследований и обучения. Графические оболочки используются в странах СНГ - Узбекистане, Казахстане и на Украине.
Актами о внедрении подтверждено использование графических оболочек в 000 «Наука» (Санкт-Петербург), 000 «ПО Киришинефтеоргсинтез», Министерстве Обороны Российской Федерации.
Основные положения, выносимые на защиту
теоретический аппарат, необходимый для моделирования численного исследования сложных динамических систем на базе гибридных автоматов и математическая модель иерархических открытых гибридных автоматов позволяющая строить модели из блоков с входами и выходами и из блоков с контактами, с синхронизацией параллельных процессов во временной щели по непрерывному типу; структура математического обеспечения для численного моделирования и исследования иерархических гибридных систем;
- структура численной библиотеки и управляющих программ для решения уравнений конкретных типов;
- алгебраический подход к структурному анализу уравнений;
- принцип построения методов поиска точки переключения методом установления.
Публикации.
Список публикаций содержит 43 работы: книги и учебники - 4, научные статьи - 12, доклады конференций - 14 и научно-методические статьи - 13, в которых описывается теория и технология моделирования гибридных систем в семействе графических оболочке Model Vision, обосновываются основные научные положения, демонстрируются возможности пакетов для научных исследований и обучения естественнонаучным дисциплинам. книги и учебники
1. Сениченков Ю.Б. Моделирование. Вычислительный практикум: Учеб. пособие./ Веселова И.Ю. - СПб.: Изд-во СПбГТУ, 1999. - 107с.
2. Сениченков Ю.Б. Визуальное моделирование сложных динамических систем.- / Колесов Ю.Б.-СПб.: Изд-во «Мир и семья & Интерлайн», 2000. -242с.
3. Сениченков Ю.Б. Практическое моделирование сложных динамических систем. / Бенькович Е.С., Колесов Ю.Б.- СПб.: Изд-во БХВ, 2001.-441с.
4. Сениченков Ю.Б. Численное моделирование гибридных систем. - СПб.: Изд-во СПбГПУ, 2004,- 206 с.
научные статьи
5. Сениченков Ю.Б. Библиотека программ для решения ОДУ. / Колесов Ю.Б. // Вычислительные, измерительные и управляющие системы: Тр. СПбГТУ. № 462. СПб: Изд-во СПбГТУ, 1996. -С. 116-122.
6. Сениченков Ю.Б. Экспертная оценка качества программных реализаций численных методов для решения ОДУ. / Воскобойников СП., Устинов CM II Вычислительные, измерительные и управляющие системы: Тр. СПбГТУ. № 462. СПб: Изд-во СП6ГТУД996. С. 122-141.
7. Сениченков Ю.Б. Современное программное обеспечение для проведения вычислительного эксперимента. / Колесов Ю.Б., Расторгуев И.В. // Вычислительные, измерительные и управляющие системы: Тр. СПбГТУ. № 468. СПб: Изд-во СП6ГТУД997. С. 95-98.
8. Сениченков Ю.Б. Свидетельство об официальной регистрации программ для ЭВМ «Model Vision Studium версия 3.0» І Инихов Д.Б., Колесов Ю.Б. № 990643- М.: Роспатент, 6.09.1999.
9. Сениченков Ю.Б. Объектно-ориентированный подход к моделированию сложных динамических систем. / Колесов Ю.Б. // Вычислительные, измерительные и управляющие системы: Тр. СПбГТУ. № 476. СПб: Изд-во СП6ГТУ,1998. С.19-23.
10. Senichenkov Yu. Test problems for Hybrid Simulators. I Kolesov Yu. II Recent Advances in Theoretical and Applied Mathematics. Singapore: World Scientific Publishing Co. Pte. Ltd., 2000. P. 214-220.
11. Senichenkov Yu. Object-Oriented Modeling in Model Vision Studium./ Kolesov Yu. II Recent Advances in Signal Processing and Computer Technologies. Singapore: World Scientific Publishing Co. Pte. Ltd., 2001. P. 413-418.
12. Сениченков Ю.Б. Современные подходы к компьютерному моделированию динамических систем. / Колесов Ю.Б. // Научно-технические ведомости СПбГТУ. -2002. - № 3. С. 93-102.
13. Сениченков Ю.Б. Компьютерное моделирование в научных исследованиях и образовании. / Колесов Ю.Б. // Exponenta_Pro. Математика в приложениях. - 2003. - № 1. С. 4-11.
14. Сениченков Ю.Б. Программная поддержка активного вычислительного эксперимента. / Колесов Ю.Б. // Научно-Технические ведомости. 2004. № 1.С. 177-182.
15. Сениченков Ю.Б. Синхронизация событий при использовании гибридных автоматов для численного моделирования сложных динамических систем. / Колесов Ю.Б. // Научно-Технические ведомости. 2004. № 1.С. 202-207.
16. Сениченков Ю.Б. Моделирование гибридных систем. // Научно-Технические ведомости. 2005. № 1. С. 198-207.
доклады на конференциях
17. Senichenkov Yu. Hybrid systems and numerical solution of ODE. I Kolesov Yu. II Differential equations and applications. The first International conference. St. Petersburg, 1996. P. 105-107.
18. Senichenkov Yu. Model Vision 3.0 for Windows 95/NT. - The graphical environment for complex dynamic system design. I Kolesov Yu. II ICI&C97: International conference on Informatics and Control. St. Petersburg, 1997. P. 764-768.
19. Senichenkov Yu. Visual Specification language intended for event-driven hierarchical dynamical systems with variable structure. / Kolesov Yu. // ICI&C97: International conference on Informatics and Control. St. Petersburg, 1997. P. 704-711.
20. Сениченков Ю.Б. Объектно-ориентированный подход к моделированию сложных динамических систем. / Колесов Ю.Б. // Фундаментальные исследования в технических вузах: Научно-техническая конференция. С.-Петербург, 1997. С. 107
21. Senichenkov Yu. Model Vision s 3.0 ODE Solver. I Kolesov Yu., Pariajskaj E. II Differential equations and applications: The second International conference. St. Petersburg, 1998. P. 122-124.
22. Senichenkov Yu. Model Vision 3.0 for WINDOWS - graphical environment for complex dynamic systems modeling. I Kolesov Yu. II COLOS-98. Maribor. 1998. P.34-41.
23. Сениченков Ю.Б. Учебные и методические материалы по теме «Моделирование»./ Бенькович Е.С., Лосева Е. А. // Информационные технологии в моделировании и управлении: II межд. конференция. С.Петербург. 2000. С. 65-67.
24. Сениченков Ю.Б. Семейство Model Vision. / Колесов Ю.Б. // Информационные технологии в моделировании и управлении: II межд. конференция, С.-Петербург, 2000. С. 188-190.
25. Сениченков Ю.Б. Применение MVS в химии и биологии. / Колесов Ю.Б. // Математические методы в технике и технологиях: ММТТ-2000. С.Петербург, 2000. С.154-157.
26. Senichenkov Yu. Java engine for UML based hybrid state machines. / Borshchev A., Kolesov Yu. II Proceedings of Winter Simulation Conference. Orlando, California, USA, 2000. P. 1888-1897.
27. Сениченков Ю.Б. Объектно-ориентированное моделирование в графической среде Model Vision Studium. I Колесов Ю.Б. II Математика, компьютер, образование: 8-я межд. конференция. Пущино, 2001. С.242-244.
28. Сениченков Ю.Б. Model Vision Studium - инструмент для объектно-ориентированного моделирование сложных динамических систем. / Колесов Ю.Б.// Гибридные системы. Model Vision Studium: 2-я межд. конференция. С.-Петербург, 2001. С.5-46.
29. Сениченков Ю.Б., Компьютерное моделирование-20ХХ. / Колесов Ю.Б. // Компьютерное моделирование 2003: 4-тая межд. конференция. СПб, 2003. С.4-6.
30. Senichenkov Yu. A composition of open hybrid automata. I Kolesov Yu. II EUROCON 2003: IEEE, Region 8, Slovenia section. Ljubljana, Slovenia, 2003. P 332-335. научно-методические публикации
31. Сениченков Ю.Б. Математическое моделирование и вычислительный эксперимент. // Компьютерные инструменты в образовании. -1998. - № 1. С.24-32.
32. Сениченков Ю.Б. Как быстро и качественно "приготовить" интерактивную модель динамической системы. / Колесов Ю.Б. //Компьютерные инструменты в образовании,- 1998.- №3-4. С. 21-30.
33. Сениченков Ю.Б. Математическое моделирование в картинках или рисуем поведение динамических систем с помощью "MODEL VISION". / Колесов Ю.Б. // Компьютерные инструменты в образовании.- 1998. - № 5. С. 17-24.
34. Ю.Б. Сениченков. Имитационное моделирование сложных динамических систем. / Колесов Ю.Б. // КомпьютерПресс. - 2000.- № 3. CD-приложение. 12с.
35. Сениченков Ю.Б. Model Vision Studium - компьютерная лаборатория для моделирования и исследования сложных динамических систем. / Колесов Ю.Б. // КомпьютерПресс- 2000. - № 3. CD-приложение. 24с.
36. Сениченков Ю.Б. Model Vision Studium - Виртуальный стенд для изучения и проектирования сложных динамических систем. Краткий обзор возможностей. / Колесов Ю.Б. // КомпьютерПресс. - 2000. - № 3. CD-приложение. -5с.
37. Сениченков Ю.Б. Компьютерные инструменты педагога. // Компьютерные инструменты в образовании. 2002. - № 2. С. 81-84.
38. Сениченков Ю.Б. Школа моделирования 2003. Урок 1. / Колесов Ю.Б. // Компьютерные инструменты в образовании. -2003.- № 1. С. 39-49.
39. Сениченков Ю.Б. Школа моделирования 2003. Урок 2. Моделирование движения объекта в среде MVS. / Макарова Н.В., Титова Ю.Ф. // Компьютерные инструменты в образовании. -2003.- №2. С. 75-83.
40. Сениченков Ю.Б. Школа моделирования 2003. Урок 3. Компьютерные Возможности компьютерного эксперимента в среде MVS. / Макарова Н.В., Титова Ю.Ф. // Компьютерные инструменты в образовании. -2003.-№ 3. С. 55-64.
41. Сениченков Ю.Б. Школа моделирования 2003. Урок 4. Моделирование систем. / Макарова Н.В., Титова Ю.Ф. // Компьютерные инструменты в образовании. -2003. -№ 4. С. 61-71.
42. Сениченков Ю.Б. Школа моделирования 2003. Урок 5. Имитационное моделирование. / Макарова Н.В., Титова Ю.Ф. // Компьютерные инструменты в образовании.- 2003. - № 5. С. 61-71.
43. Сениченков Ю.Б. Школа моделирования 2003. Урок 6. Графические возможности MVS. / Колесов Ю.Б., Макарова Н.В., Титова Ю.Ф. // Компьютерные инструменты в образовании.- 2003.- № 6. С. 65-71. Структура и объем работы
Работа состоит из введения, пяти глав, заключения и приложения. Объем работы - 308 стр., список цитированной литературы - 127 наименований, рисунков - 98, таблиц - 84. В приложение вынесен список статей зарубежных авторов, посвященных гибридным системам. Содержание работы
В первой главе приводится обзор работ, посвященных гибридным системам, зарубежных и отечественных авторов. Анализируются различные определения гибридных систем. Дается обзор современных программных средств для моделирования сложных динамических систем и предлагается классификация компьютерных моделей, положенная в основу последней версии пакета Model Vision 4.Х .
Отмечается, что существуют два подхода к исследованию гибридных систем. Первый подход базируется на обобщении конечных автоматов, сводящемуся к оснащению гибридного автомата различными моделями непрерывного времени. Этого подхода в основном придерживаются зарубежные ученые, предложившие термин «гибридные системы». Его можно рассматривать как качественную теорию гибридных систем, целью которой является разработка методов верификации. Несмотря на существующие успехи на этом пути, его практические возможности пока еще ограничены и могут быть использованы для анализа и верификации достаточно простых систем.
Второй подход основан на обобщении классических динамических систем. Этот подход давно уже развивается отечественными учеными (Лурье, Цыпкин, Бромберг, Андронов, Уткин, Емельянов, Филлипов, Глушков, Бусленко) и пригоден для исследования практически важных, сложных динамических систем. Приводится краткий обзор основных отечественных работ в области гибридных систем, больше известных в нашей стране как непрерывно-дискретные системы. Ценность этого обобщения заключается, прежде всего, в том, что появляется возможность применять методы исследования, присущие непрерывным системам. Помимо этого, графическое представление гибридных систем в виде гибридных автоматов, может быть положено в основу современных графических языков.
На сегодняшний день существует много различных программных средств для моделирования и исследования сложных динамических систем.
Среди пакетов можно выделить специализированные, направленные на решение конкретных прикладных задач, и универсальные, способные справиться практически с любой исследовательской задачей. Универсальные пакеты обычно лишены уникальных численных методов и библиотек моделей, специальной графики и средств поддержки больших проектов, что и отличает их от специализированных.
Семейство Model Vision, в котором воплощены предлагаемые в работе подходы, относится к универсальным пакетам.
Среди универсальных пакетов также существуют несколько групп, отличающиеся методами построения и типами моделей. Это математические пакеты, наиболее приспособленные для изучения изолированных классических динамических систем, и пакеты компонентного моделирования с блоками с входами выходами и с блоками с контактами, предназначенные для моделирования иерархических систем.
Новые оболочки семейства Model Vision объединяют в себе свойства как математических пакетов, так и пакетов компонентного моделирования. Программное обеспечение пакетов компонентного моделирования решает по сравнению с математическими пакетами другие математические и технические задачи. К новым математическим задачам относятся задачи:
автоматического синтеза совокупной, итоговой системы АДУ из уравнений отдельных компонент с учетом связей блоков, проверки корректности итоговой системы и преобразования ее форме, необходимой численному решателю;
автоматического выбора численного метода для воспроизведения поведения системы;
достоверного автоматического воспроизведения численного решения на всем промежутке наблюдения. К числу новых научно-технических задач относятся:
разработка современных языков моделирования и проведения вычислительного эксперимента;
создание новых средств визуализации поведения динамических систем;
создания библиотек инструментов для исследования свойств динамических систем.
Блоки, или компоненты, из которых строится модель, в современных пакетах могут быть различного типа, и от их типа и способа объединения зависит тип итоговой системы и методы ее решения.
В последней версии пакета Model Vision используется следующая классификация моделей, с которыми он способен работать:
однокомпонентные системы с непрерывным поведением, однокомпонентные системы с гибридным поведением, многокомпонентные системы с компонентами типа «вход-выход-состояние», многокомпонентные системы с компонентами, взаимодействующими через контакты, многокомпонентные системы с переменным числом компонентов.
Основной проблемой компонентного моделирования является автоматическое построение итоговой системы из блоков заданного типа, а необходимым условием успешного численного исследования построенных моделей - обеспечение нахождения решения с заданной точностью систем ДАУ с изменяющейся во времени структурой.
Во второй главе строятся основы теории открытых гибридных систем, систематизируется существующая теория изолированных систем, и разрабатывается • модель открытого гибридного автомата с синхронизацией во временной щели по непрерывному типу.
В современной литературе, посвященной гибридным системам, в основном изучаются однокомпонентные изолированные системы. Изолированные гибридные системы являются достаточно узким классом моделей, хотя и представляют большой теоретический интерес. Более широким является класс многокомпонентных моделей.
При моделировании многокомпонентных систем возникает несколько дополнительных проблем, не характерных для однокомпонентных. Основная проблема связана с автоматическим формированием итоговой системы из уравнений компонентов, с учетом связей и преобразованием их к виду, пригодному для численного интегрирования. И здесь становится важным, что следует понимать под поведением параллельно функционирующих отдельных компонентов, обменивающихся между собой информацией, или иными словами, что лежит в основе композиции открытых гибридных автоматов.
При моделировании компонентных систем, чья структура не меняется во времени, итоговая система оказывается системой алгебро дифференциальной и остается только указать решателю ее конкретный вид система алгебраических, дифференциальных, или алгебро-дифференциальных уравнений.
При моделировании систем, в которых происходит смена уравнений, и в эти моменты выполняются параллельные дискретные операции, композиция параллельно работающих компонентов может быть определена по-разному, в результате чего модель будет обладать различным поведением. Мгновенные процессы, происходящие во временной щели, можно считать последовательными и упорядочивать в произвольном порядке (синхронизация по дискретному типу), а можно считать одновременными (синхронизация по непрерывному типу).
В семействе Model Vision применяется последний тип синхронизации, но только для компонентов со связями по вещественным переменным, так как в противном случае возникают системы уравнений, численное решение которых может вызывать значительные трудности. До сих пор во всех пакетах по умолчанию применялась синхронизация по дискретному типу.
Во второй главе строятся необходимые для дальнейшего изложения определения гибридных систем их композиции:
- примитивного гибридного автомата;
- открытого примитивного автомата «вход-выход-состояние»;
- композиции примитивных открытых гибридных автоматов;
- открытого примитивного автомата с контактами;
- композиции открытых примитивных автоматов с контактами;
В третьей главе рассматриваются проблемы предварительного анализа структуры совокупной системы и проблемы продвижения модельного времени. Для структурного анализа уравнений предлагаются аналоги методов, используемых для решения систем больших разреженных систем линейных алгебраических уравнений. Приводятся используемые в пакете методы для поиска точки переключения для предикатов различного вида и предлагается формула, позволяющая строить различные модификации метода установления, применяемого для поиска точки переключения. Обсуждаются стратегия выбора шага для визуализации поведения.
При блочном моделировании достаточно сложно предсказать заранее, какую форму примет и какого типа окажется итоговая система уравнений. В тоже время от формы и типа уравнений во многом зависит эффективность решения. Анализом формы итоговой системы в MVS занимается блок предварительного анализа уравнений.
Требования к решению формируются при проведении вычислительного эксперимента - пользователь может потребовать максимально возможной скорости решения без визуализации поведения или детального графического воспроизведения решения. Эти задачи возложены на блок продвижения модельного времени, который содержит чрезвычайно важный для гибридных систем блок поиска точек смены поведения - точек переключения.
С практической точки зрения важно предоставить пользователю как можно больше свободы при описании поведения отдельных компонентов и не заставлять его использовать трудно воспринимаемые синтаксические формы, свойственные процедурным языкам программирования.
Под свободной формой, будем понимать форму, в которой уравнения первого порядка не разрешены относительно первых производных ds F(—,s,t) = 0. Ориентация на свободную форму оправдана еще и тем, что dt это не только удобная форма представления исходной информации, но и форма, естественным образом возникающая при «физическом» моделировании.
Свободная форма редко используется в программных реализациях численных методов. Более распространенной является форма ds A(s) — = f(s,t),c возможно вырожденной матрицей A(s).
В каждом конкретном случае систему, передаваемую решателю, следует автоматически проверять и приводить к наиболее простой форме. Эту работу в Model Vision Studium выполняет блок предварительного, структурного анализа уравнений. Структурному анализу можно подвергать как системы отдельного блока, так и всю, совокупную систему уравнений. Пакетом анализируются и преобразуются к нужному виду:
последовательности формул;
системы нелинейных алгебраических уравнений;
системы нелинейных алгебраических уравнений с подстановками;
системы дифференциальных уравнений. Для структурного анализа все типов уравнений предлагается использовать методы, используемые для структурного анализа больших разреженных систем линейных алгебраических уравнений.
Сформированная система передается решателю, задача которого найти численное решение в конкретной временной точке. Выбор этой конкретной точки определяется блоком продвижения модельного времени и зависит от режима работы пакета.
Таких режимов два - построение решения с визуализацией поведения и решения без визуализации. В первом случае требование качества визуализации накладывает ограничение на выбор возможной величины шага продвижения модельного времени, так как необходимо воспроизвести графики с учетом всех особенностей поведения, во втором -ограничений на величину шага не существует. Второй случай характерен для решения задач оптимизации и любых других расчетов большого числа вариантов с различными значениями параметров, когда нас интересуют не промежуточные, а конечные результаты. Особенность первого режима в пакете Model Vision заключается в том, что визуализация поведения осуществляется по ходу решения.
Как в первом, так и во втором случае возникает еще одно требование, связанное с моделированием гибридных систем - при численном интегрировании в любом режиме должны быть правильно определены точки смены поведения, или точки переключения.
К основным проблемам поиска точки переключения следует отнести:
- Построение надежного алгоритма локализации очередной точки переключения с заданной точностью (глобальный поиск).
- Построение быстрого алгоритма поиска локализованной точки (локальный поиск).
Первая проблема связана с выбором величины шага модельного времени. Решение второй проблемы зависит от того, какая информация о свойствах решения доступна численному алгоритму.
В гибридных системах поиск точки переключения может осложняться тем, что точка смены поведения может лежать на границе множества допустимых значений фазового вектора:
Предлагается использовать различные алгоритмы для поиска точки переключения.
Поиск в условиях, когда можно вычислить только значение предиката в окрестности точки переключения.
В данном случае в семействе Model Vision применяется метод деления отрезка пополам и в качестве нового значения модельного времени выбирается значение правой точки окончательного локализующего интервала.
Поиск в условиях, когда можно вычислить не только значение функции, определяющей точку переключения, но и ее производную.
В этом случае, после того как точка переключения локализована, вместо предикатов формируются уравнения, и применяются различные модификации метода Ньютона.
Поиск в условиях, когда точка переключения определяется как корень уравнения на решении, описывающем поведение.
Здесь используются те же алгоритмы, что и в предыдущем пункте, только теперь уравнения уже заданы, и формировать их не нужно.
Одним из способов поиска в условиях непродолжаемости решения за точку переключения является переход от поиска корня нелинейного алгебраического уравнения к поиску стационарного режима дифференциального уравнения, для которого положение равновесия является корнем исходного алгебраического уравнения. В вычислительной математике такой прием называется поиском корня методом установления. Очевидным достоинством этого приема является то, что автоматически обеспечивается невозможность перейти за точку переключения.
В четвертой главе приводится описание структуры библиотеки и структуры конкретных решателей.
Для решения каждой из основных задач (систем нелинейных алгебраических, дифференциальных и алгебро-дифференциальных уравнений), пользователю предлагается на выбор несколько программных реализаций численных методов. Указать заранее наиболее подходящий метод решения конкретной задачи удается редко, поэтому важной особенностью современных графических оболочек является простота процедуры смены численного метода. В MVS это можно делать даже в процессе решения. В тоже время существует значительная категория пользователей, которой безразлично, каким методом будет получено решение, лишь бы оно правильно отражало поведение объекта. Аналогичное отношение к численным методам наблюдается и на этапе отладки. При отладке, когда модель демонстрирует "необъяснимое" поведение, бывает важно просто "двигать" время вперед любым доступным способом и смотреть, что произойдет с ключевыми переменными. Программные реализации численных методов, гарантирующие получение решения с заданной точностью, не способны, как правило, справиться с задачами, возникающими при отладке, и приходится применять очень примитивные решатели, вплоть до методов с постоянным шагом.
В Model Vision Studium, пользователю предлагаются три вида программных реализаций численных методов.
1. Автоматические решатели. Их назначение - автоматически осуществить подбор наименее трудоемкой программной реализации численного метода для решения конкретной задачи, а в случае неудачи, предоставить пользователю максимально подробную информацию о встреченных трудностях. Анализируя поведение автоматического решателя, пользователь может затем выбрать конкретный метод.
2. Программные реализации для решения задач конкретного типа. Если пользователю известен тип решаемой задачи, то достаточно просто выбрать один из предлагаемых на выбор методов соответствующего класса. Однако и в этом случае, пользователь имеет дело не непосредственно с программной реализацией из соответствующей систематизированной коллекции, а с управляющей программой, анализирующей коды завершения вызываемой подпрограммы и, в случае необходимости, меняющей ее параметры так, чтобы обеспечить получение решения на всем интервале моделирования. Например, если профаммная реализация не может обеспечить получение решения с указанной пользователем точностью, то управляющая профамма сначала попытается изменить точность, а если это не поможет, то только тогда прекратит счет и выдаст аварийное сообщение.
3. Профаммные реализации для отладки. Цель этой фуппы методов продвигать модельное время вперед как можно дальше, чтобы дать возможность пользователю понять природу ошибок. К этой фуппе, для решения дифференциальных уравнений, относятся явный и неявный методы Эйлера с автоматическим выбором шага и метод Рунге-Кутта четвертого порядка с постоянным шагом.
Выбор конкретного метода осуществляется пользователем в диалоговом режиме, простейший вариант которого сводится к использованию "метода по умолчанию". В качестве "метода по умолчанию" предлагается автоматический решатель. Автоматический решатель в заданной последовательности перебирает включенные в него методы, чтобы обеспечить получение решения на всем временном промежутке.
Аварийная остановка любого метода сопровождается диагностическим сообщением. В случае аварийного завершения работы, можно попытаться сменить метод, но лучше устранить причину прекращения счета. "Плохие" численные задачи, конечно же, существуют, но практика показывает, что плохо сформулированных задач гораздо больше.
Эффективность созданных численных библиотек подтверждается результатами тестирования и многочисленными численными экспериментами, примеры которых приведены в конце главы.
Предлагается и иллюстрируется примерами новый способ построения тестовых примеров для проверки качества программных реализаций численных методов решения систем нелинейных алгебраических уравнений.
В пятой главе приводятся примеры, подтверждающие эффективность созданного программного обеспечения. Примеры условно разделены на две группы. В первую вошли работы научных коллективов, использовавших оболочку Model Vision для решения новых научных и инженерных задач, и опубликовавшие результаты своих исследования. Приводятся цитаты из этих работ, поясняющие, почему авторы использовали оболочку Model Vision вместо широко распространенных в нашей стране зарубежных графических оболочек. Во вторую группу, вошли коллективы, применившие оболочку Model Vision для учебных целей, и написавших свои руководства по ее использованию.
В заключении подводятся итоги работы, формулируются основные выводы и результаты.
В приложении приводится список зарубежных публикаций, посвященных гибридным системам.
Компьютерное моделирование динамических систем
Прежде всего, это математические макеты MAPLE, MATHEMATICA, MathCAD, MATLAB и любые другие, позволяющие решать системы обыкновенных дифференциальных уравнений (ОДУ) и алгебро-дифференциальных уравнений (АДУ). Именно системы АДУ в основном и характеризуют современные сложные динамические системы, однако не во всех перечисленных пакетах имеется возможность решать их. В тоже время возможность решения и визуализации решений ОДУ предусматривается в таких пакетах всегда. Математические пакеты лучше всего приспособлены для решения систем небольшой размерности, с достаточно гладкой правой частью, уравнения которые можно написать вручную. Такие системы можно классифицировать как изолированные, однокомпонентные динамические системы, с заданной в явном виде системой уравнений. Моделировать системы с разрывными правыми частями или переменной структуры, когда меняются не только правые части, но и число уравнений, в математических пакетах затруднительно по двум причинам. Во-первых, входные языки математических пакетов не имеют выразительных средств для описания систем этого типа, поэтому описание становится очень трудоемким процессом. Применяемые способы описания приводят к громоздким и трудно воспринимаемым пользователями текстам, что является потенциальной причиной многих ошибок. Во-вторых, что более важно, при наличии разрывов в системе или изменении структуры решаемого уравнения, точки, где это происходит, принято предварительно находить с разумной точностью и отдельно решать две системы - до точки разрыва и после нее. Чаще всего решать эти системы приходится различными численными методами, если при переходе через поверхность разрыва существенно меняются свойства системы. Реализовать такой подход в математических пакетах сложно, так как отсутствуют встроенные механизмы локализации разрывов, заданных уравнениями или предикатами, и автоматической смены численных методов. В тоже время математические пакеты прекрасно справляются с традиционными задачами моделирования: созданием и изучением новых моделей, базирующихся на системах ОДУ, и новых численных методов для их решения, если только пользователь обладает достаточными математическими знаниями и опытом программирования. 1.3.2 Многокомпонентные модели.
Пакеты компонентного моделирования, зарубежные: семейство надстроек над пакетом Matlab - Simulink, StateFlow, SimMechanics, SimPowerSystems, пакеты Dymola, Vissim, и отечественные: MBTY,
AnyLogic, Model Vision Studium, Stratum, позволяют автоматически создавать и исследовать иерархические модели. Учитывая, что исследуемые реальные объекты обычно имеют иерархическую структуру и, чаще всего, переменную, зависящую от происходящих событий, то основным инструментом их исследования становятся пакеты компонентного моделирования.
Системное программное обеспечение пакетов компонентного моделирования решает по сравнению с математическими пакетами другие математические и технические задачи. К новым математическим относятся задачи: - автоматического синтеза совокупной, итоговой АДУ из уравнений отдельных компонент с учетом связей блоков, проверки корректности итоговой системы и преобразования ее форме, необходимой численному решателю; - автоматического выбора численного метода для воспроизведения поведения системы; - достоверного автоматического воспроизведения численного решения на всем промежутке наблюдения.
К числу новых научно-технических задач относятся: - разработка современных языков моделирования и проведения вычислительного эксперимента; - создание новых средств визуализации поведения динамических систем; - создания библиотек инструментов для исследования свойств динамических систем.
Блоки, или компоненты, из которых строится модель, в современных пакетах могут быть различного типа, и от их типа и способа объединения зависит тип итоговой системы и методы ее решения.
Таким образом, основной проблемой компонентного моделирования становится автоматическое построение итоговой системы из блоков заданного типа, а необходимым условием успешного численного исследования построенных моделей - обеспечение нахождения решения систем ДАУ с изменяющейся во времени структурой с заданной точностью.
В современных пакетах используются блоки:
1) Предопределенные и произвольные блоки «вход-выход-состояние» или блоки с направленными связями. Графический язык функциональных схем и предопределенные блоки «вход-выход-состояние» пакетов Simulink, Vissim, МВТУ, восходит к схемам, применявшимся еще на аналоговых машинах. Использовать предопределенные блоки это типа выгодно, если структура модели проста и все необходимые блоки уже присутствуют в базовом наборе. Набирать же произвольную сложную систему уравнений с помощью интеграторов, сумматоров и усилителей подобно тому, как это делалось на аналоговой машине, неудобно. Графический образ модели становится ненаглядным и, главное, не отражает естественной структуры моделируемого объекта. Еще одна трудность возникает при создании новых базовых блоков, которые приходится конструировать, используя операторы «низкого уровня» традиционных процедурных языков, что, как показывает практика, оказывается непосильной задачей для большинства пользователей. Однако, несмотря на отмечаемые всеми недостатки, это подход развивается и его совершенствование связано, прежде всего, с моделированием гибридных систем. Примером может служить Simulink, который в последних версиях Matlab дополнен подсистемой Stateflow, позволяющей использовать карты состояния совместно с традиционными непрерывными блоками, и моделировать событийно-управляемые системы.
Траектории примитивного гибридного автомата
Траекторией гибридной системы будем называть либо конечное множество, либо последовательность решений S(T) = {(s(t),ter0),(sl(t),teTl),...} заданного алгебро дифференциального уравнения, обладающих требуемыми свойствами на всех промежутках временной последовательности тн.
Строя некоторый математический формализм мы стремимся в качестве его прототипа выбрать некоторый класс реальных объектов, свойства которых он должен воспроизводить. Примером содержательного поведения гибридного автомата может служить полет и отскок мячика. Характерными особенностями рассматриваемых нами реальных процессов и соответствующих им моделей являются их бесконечное развитие во времени и детерминированность. Возможность бесконечного движения системы и детерминированность свойственна естественно и классической динамической системе, что обеспечивается существованием и единственностью решения в окрестности начальной точки и его продолжаемостью на всю временную ось. Возникает вопрос, при каких условиях эти свойства будут и у траекторий гибридной системы. Очевидно, что в примитивном гибридном автомате бесконечное движение системы будет наблюдаться либо при бесконечном срабатывании перехода, либо при вырождении системы в некоторый момент времени в классическую динамическую систему. При очевидном условии, что инвариант будет истинным на решении с любым начальным условием, выбранным с помощью функции Init. В противном случае поведение автомата следует считать недопустимым, и он должен вырабатывать специальный символ, говорящий о невозможности дальнейшей работы. В этом случае, с точки зрения внешнего наблюдателя, происходит, как иногда говорят, блокировка автомата.
Для вырождения в классическую динамическую систему достаточно, чтобы на очередном временном промежутке при истинности инварианта на решении при выбранных начальных условиях никогда бы не стал истинным предикат, обеспечивающий очередное срабатывание перехода. Будем называть примитивный автомат реализуемым на множестве S0, если для любых начальных условий Vs0 є S0, вырабатываемых функцией Init, существует единственное решение задачи (1), удовлетворяющее заданным с помощью функции Inv свойствам. Или иначе, - функция Init вырабатывает только допустимые в указанном смысле начальные условия. Множество начальных условий S0 можно разбить на два непересекающихся подмножества SQd и S0c, называемых подобластями длительных (непрерывных) и вырожденных длительных состояний, таких что pred(SQd) = true и pred(S0c) = false. Существование непустого подмножества Sod может приводить к тому, в последовательности тн = {тк }Q может найтись номер N, начиная с которого / N все ті окажутся нулевыми, и автомат начнет демонстрировать чисто дискретное поведение. Для этого достаточно, чтобы в множестве S0d существовало инвариантное подмножество функции Init и одна из точек этого подмножества стала бы начальной в некоторый момент гибридного времени.
Пример 5.
Изолированный примитивный гибридный автомат с начальным дискретным поведением. Рассмотрим следующий примитивный гибридный автомат — = а У, dt 0=y-s; 5(0) = р 0;у(0) = у0 Ф р;р = \;а = -\; с предикатом pred(s(t),y(t)):s(t) c = 5 ,c р и функцией Init инициализации новых начальных условий после срабатывания перехода: post(s(t )) := pre(s{t )) + р. Этот автомат начинает свою работу в t = 0, сразу же обнаруживает, что предикат при заданных начальных условиях, истинен, и вычисляет новые начальные условия. Так продолжается до шестого такта гибридного времени, когда начальное значение post(s(tl)) .- 6 становится таким, что появляется возможность начать длительное поведение. С этого момента мы наблюдаем периодическое изменение переменной состояния s(t) (Рис. 7).
Как мы видим, примитивный гибридный автомат может демонстрировать, тем самым, как нетривиальное непрерывное поведение, так и нетривиальное дискретное, сводящееся не только к назначению новых начальных условий, но и поиску начальных условий, приводящих к новому длительному поведению. Несмотря на это замечание, мы, все равно непрерывное поведение автомата, связанное с решением дифференциальных уравнений, будем называть длительным. Во многих языках моделирования, для описания длительных и мгновенных действий применяются различные синтаксические конструкции: длительные поведения описываются функциональными зависимостями и различными уравнениями, а дискретные - алгоритмически.
Структурно невырожденные системы нелинейных алгебраических уравнений
Рассмотрим вектор s размерности п и вектор-функцию v(s) размерности т. Значение т не обязательно совпадает со значением п. Будем называть систему v(s) = 0 - формально определенной, если число уравнений равно числу неизвестных - п = т; переопределенной, если число уравнений больше числа уравнений - п т\ и недоопределенной, если число уравнений меньше числа неизвестных - п т. Переопределенные и недоопределенные системы назовем структурно вырожденными. Рассмотрим задачу об определении структурной невырожденности формально определенной системы уравнений v(s) = Q, где v вектор-функция размерности п.
Сопоставим формально определенной системе v(s) = 0 квадратную матрицу структуры Q, строкам которой соответствуют уравнения системы, а столбцам - компоненты вектора s. Пометим вхождение /-той компоненты вектора s в &-тое уравнение единицей в матрице структуры 7U=1, и нулем ее отсутствие - qkJ=0. Очевидно, что структурная невырожденность системы связана с рангом матрицы Q, и если rank(Q) = п, то система структурно не вырожденна.
Конструктивный способ определить структурную невырожденность системы заключается в возможности последовательно выражать компоненты вектора неизвестных S; = ,.(5,,..5.,,, ,,.... ,), / = l,/i, начиная с первого уравнения системы, и подставлять в оставшиеся у = / + 1,// (прямой ход процесса подстановки) до тех пор, пока не будет построено уравнение, зависящее только от одной переменной. Для определения структурной невырожденности необязательно уметь явно строить явно определенную подстановку 5,.= ,.(5,,..5,.,,, ,,...5,,), нужна только информация о вхождении неизвестных в соответствующее уравнение. Прямой ход процесса подстановки, можно описать последовательностью матриц 2,, і = 0,л-1; QQ =Q. Каждая из матриц, начиная с / = 1, совпадает по форме с матрицей, соответствующей исключению /-той неизвестной в методе Гаусса при решении систем линейных алгебраических уравнений. Единственным отличием процесса исключения в методе Гаусса и процесса проверки невырожденности является правило формирования новых строк в подматрице (/-1)х(/-1) на каждом шаге. При «подстановке» /-той неизвестной в оставшиеся j - і +1, п уравнения при проверке невырожденности, в новом уравнении число единиц может только увеличится - к уже существующим единицам у -той строки добавляются не совпадающие по положению единицы /-той строки. Этот процесс в точности эквивалентен процессу появления новых ненулевых элементов в методе Гаусса при использовании любого ненулевого элемента в столбце в качестве ведущего, что позволяет использовать для определения невырожденности уже существующее программное обеспечение. Таким образом, если существует матрица перестановок Рг такая что матрицу PXQ нелинейной алгебраической системы описанным выше алгоритмом формальной подстановки можно привести к верхней треугольной матрице, то система уравнений структурно невырождена. Пример 2 . Система уравнений и ее матрица структуры, где - х,у, z,w -неизвестные, с,-константы.
Обычно при записи уравнений часто используются формулы как подстановки. Подстановки вводит сам пользователь, но целесообразно их пытаться находить и автоматически, так это есть ничто иное, как оптимизация за счет однократного вычисления общих выражений. В языке MVL нет типа данных «уравнение» и «формула». Это объясняется следующим. Исходное представление пользователем выражений в виде уравнений и формул не всегда оказывается таким же в итоговой системе уравнений. Достаточно привести в качестве примера блок-схему кольца для двух блоков с формулами y = f(x), y = g(x), х1 -уг,хг У\- чтобы убедиться, в том, что в итоге возникает система нелинейных алгебраических уравнений. В некоторых пакетах, все формулы превращаются в уравнения, но это не целесообразно. Если все-таки формула в результате оказывается уравнением, формируется предупреждение о том, что желание пользователя не может быть удовлетворено, и необходимо либо проверить описание задачи, либо согласится «с мнением» компилятора.
Очевидно, что для нелинейных алгебраических уравнений с использованием подстановок, матрица структуры должна быть приводима к блочно-треугольной форме, где диагональный блок, соответствующий формулам, должен быть строго нижним треугольным, а блок, соответствующий искомым переменным - верхним треугольным. Для переопределенных систем пользователю может быть интересен список уравнений, которые следует удалить, для того чтобы оставшаяся формально определенная система максимально возможного ранга оставалась структурно невырожденной.
Системы нелинейных алгебраических уравнений
Решение системы нелинейных алгебраических уравнений, как основная задача, возникает при соответствующем способе описании поведения, и, как вспомогательная, при реализации неявных методов решения систем алгебро-дифференциальных уравнений. В том и другом случае, за исключением начальной точки, начальное приближение к решению можно считать достаточно хорошо известным, что позволяет ориентироваться в основном на различные модификации метода Ньютона. В начальный момент времени при смене поведения ситуация значительно усложняется, так как у пользователя может отсутствовать информация об удовлетворительном начальном приближении. Программы для решения нелинейных уравнений
Для решения систем нелинейных уравнений, возникающих при описании поведения, используются: 1. Fast Newton (newt_F) - "Быстрый" метод Ньютона, позволяющий не вычислять матрицу Якоби в очередной временной точке заново, а использовать сохраненное значение с предыдущей точки (пересчет матрицы Якоби через каждые пять итерации). 2. Modified Newton (newt_M) - Модифицированный метод Ньютона (пересчет матрицы Якоби через фиксированное число итераций или по мере уменьшения скорости сходимости). 3. Classical Newton (newt_G) - Классический вариант метода Ньютона (пересчет матрицы Якоби на каждой итерации). 4. Hybrid Powell method (powell)H6pHflHbm метод Пауэлла (MinPack) 5. Auto_NAE . Автомат пытается последовательно применять методы (1,2, 3, 4). Аварийная остановка автоматического решателя означает, что для данного начального приближения, взятого с предыдущего шага, ни один из методов не нашел удовлетворительного решения. Примечание. В скобках указаны имена подпрограмм, используемые в соответствующей .DLL Подпрограммы Newt_F, Newt_M, Newt_G являются управляющими для подпрограммы NTDF8.
Подпрограмма NTDF8 представляет собой традиционную реализацию метода Ньютона. На каждом шаге, с помощью подпрограмм из коллекции LINPACK, решается система линейных уравнений относительно приращения к решению, найденному на предыдущей итерации. Матрица Якоби вычисляется численно. Приближенное решение считается найденным с удовлетворительной точностью, если выполнено условие Ік+і-уЛфл+іІК+10ОЄм- Величина относительной погрешности етш задается пользователем. Абсолютная погрешность положена равной 100 є „. Напомним, что е„ - это минимальное машинное число, при сложении с единицей дающее результат отличный от единицы.
Задавая различные значения переменным подпрограммы NTDF8 ipr, inorm, nJc можно: вычислять матрицу Якоби заново в начальной точке или использовать уже известное значение (ipr); оценивать величину погрешности, опираясь на различные нормы решения (inorm); пересчитывать матрицу Якоби через заданное число итераций (njc). Все перечисленные методы ньютоновского типа получены из общей процедуры за счет выбора соответствующих значений этих переменных.
Переменные nfcnN, njacN, nitN общего блока common/stat/nfcnN, njacN, nitN хранят: nfcnN - общее число обращений к правой части; njacN - число вычислений матрицы Якоби; nitN- общее число итераций. Пользователь MVS доступа к этим переменным не имеет, они использовались при тестировании библиотеки.
Помимо методов ньютоновского типа, на практике часто применяют методы минимизации специально построенных функционалов, точка минимума которых совпадает с корнем исходного уравнения. К числу таких методов относится гибридный метод Пауэлла (MinPack). Это метод часто не требует знания хорошего начального приближения. В тоже время, возможно, что программа найдет не корень уравнения, а локальный минимум вспомогательного функционала. Если ваша система допускает нахождение решения различными методами, старайтесь это делать для проверки.
Сообщения об ошибках гибридного метода Пауэлла приведены в табл. 5. В табл. 6 даны краткие пояснения к сообщениям. Табл. 6 отличается от табл. 4 только одной строкой, соответсвующей коду ier = -2, поэтому она приводится в сокращении.
Управляющая подпрограмма AUTO_NAE последовательно вызывает сначала методы ньютоновского типа, а затем гибридный метод Пауэлла. В случае неудачи очередного метода, коды завершения игнорируются, и делается попытка применить следующий метод. На следующем временном шаге делается попытка вновь применить самый простой метод, а именно Fast Newton.
Переменная istart управляет только работой "быстрого" модифицированного варианта метода Ньютона (Fast Newton). Значение istart=0 требует вычисления матрицы Якоби в начальной точке. При успешном нахождении решения istart на выходе метода полагается равным единице и, при последующем обращении, перевычисления матрицы не происходит. При смене поведения, значение istart автоматически полагается равным нулю.
