Применение алгебраических методов для анализа сложных систем тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Калинина, Елизавета Александровна

• Калинина, Елизавета Александровна
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Калинина, Елизавета Александровна

Оглавление

Введение

Глава 1. Устойчивость и D-устойчивость семейства вещественных полиномов

1.1. Введение

1.2. Необходимые результаты

1.2.1. Теория дифференцируемых отображений

1.2.2. Теория исключения

1.2.3. Отделение корней полинома

1.2.4. Устойчивость полинома

1.3. Вещественные корни семейства полиномов

1.4. Устойчивость семейства полиномов

1.5. D-устойчивость семейства полиномов

1.6. Направляемый автобус Daimler-Benz 0305

1.6.1. Предварительные сведения

1.6.2. Решение

1.7. Заключение

Глава 2. Собственные числа матриц

2.1. Предварительные результаты

2.2. Общие собственные числа двух матриц

2.2.1. Предварительные результаты

2.2.2. Алгоритм

2.2.3. Пример

2.3. Жорданова нормальная форма матрицы

2.3.1. Предварительные результаты

2.3.2. Основные результаты

2.3.3. Клетка Жордана максимального порядка

2.3.4. Описание алгоритма

Порядок максимальной клетки Жордана

Собственные числа, которым соответствуют максимальные клетки Жордана

2.3.5. Численный пример

2.3.6. Заключение

2.4. Кратные собственные числа

2.4.1. Предварительные результаты

2.4.2. Кратные собственные числа матрицы, зависящей от параметра

2.4.3. Алгоритм

2.4.4. Асимптотическая сложность алгоритма и точность вычислений

2.4.5. Численный пример

Глава 3. Графы и матрицы

3.1. Введение

3.2. Некоторые предварительные определения и результаты

3.2.1. Линейные пространства и ортогональность над полем ОГ(2)

3.2.2. Необходимые сведения из теории графов

3.2.3. Графы и линейные отображения

Линейные отображения

Паросочетания и реберные покрытия

3.3. Некоторые вспомогательные результаты

3.3.1. Матрица Грама над полем ОГ(2) и ее свойства

3.3.2. Факторизация матрицы над полем ОГ(2)

3.4. Теорема о циклах и разрезах

3.5. Задача распознавания реберного графа

3.5.1. Необходимые теоретические результаты

3.5.2. Описание алгоритма

3.5.3. Алгоритм

3.5.4. Примеры

Глава 4. Метод Эйлера

4.1. Локально оптимальный шаг метода Эйлера

4.2. Реализация метода

4.3. Численные примеры

4.4. Обсуждение полученных результатов

Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Применение алгебраических методов для анализа сложных систем»

Введение

Актуальность темы исследования. Теория сложных систем — это новая перспективная область исследований, изучающая, каким образом части системы влияют на поведение ее в целом, и как система взаимодействует с внешней средой. Сложные системы используются для моделирования процессов в информатике, биологии, экономике, физике, химии и многих других областях науки и человеческой деятельности (см., например, книгу [160] и статьи [47, 66, 122, 185]). В настоящее время более 50 институтов и исследовательских центров по всему миру ставят своей основной задачей изучение сложных систем.

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

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

Робастное управление [52] привлекло широкое внимание в конце 1970-х годов. Одним из первых важных результатов в этой области является теорема Харитонова для интервальных полиномов [38], опубликованная в 1978 г. Позже были получены другие значительные результаты, такие как вычисление

радиуса устойчивости в пространстве коэффициентов полинома (Soh, Berger и Dabke), обобщенная теорема Харитонова, высокоэффективные методы вычисления границ устойчивости, такие как годограф Цыпкина — Поляка, описанные в [28, 37, 116, 117, 118] и т.д.

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

Задача проверки устойчивости линейной стационарной системы дифференциальных уравнений сводится к проверке того, что все корни характеристического полинома ее матрицы лежат в левой полуплоскости комплексной плоскости. Другими словами, проверке того, что характеристический полином является гурвицевым. Необходимые и достаточные условия этого дает известная теорема Рауса — Гурвица. Однако во многих практических задачах необходимо гарантировать, что нули при изменениях параметров не сдвигаются слишком далеко от их исходных положений. Иначе говоря, корни характеристического полинома должны быть расположены в некоторой алгебраической области D комплексной плоскости. Это задача D-устойчивости (v. [40, 41]).

Задача о нахождении числа корней полинома в некоторой области комплексной плоскости известна с первой половины XIX века. Эта проблема возникла в трудах Ш. Эрмита, решением ее занимались такие математики, как И. Шур, А. Кон, B. N. Datta, J. Ackermann и R. Muench, Р. Е. Калман [9, 18, 29, 92]. Так, для того, чтобы установить, находятся ли все корни полинома внутри единичного круга комплексной плоскости, используется критерий Шура — Кона [6] (B. N. Datta обобщил критерии Рауса — Гурвица и Шура — Кона, используя матрицу безутианты [74]). В случае областей, границами которых являются уникурсальные (вещественно параметризуемые) кривые, можно использовать метод Эрмита (1854) [96]. Р. Е. Калман разработал еще один критерий, позволяющий определить, все ли нули полинома лежат в некоторой алгебраической

области комплексной плоскости [112]. Известен также метод D-разбиения [5], т. е. разбиения на области в пространстве параметров. Однако его применение затруднительно при большом количестве параметров.

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

f (x) = a0xn + a1xn-1 + ... + an e R[x], a0 = 0,n > 2

это полином относительно его коэффициентов

D(f) = D(ao,ai,... ,an).

Обращение в нуль дискриминанта является необходимым и достаточным условием того, что полином f (x) имеет кратные корни. Уравнение D = 0 определяет в пространстве коэффициентов Rn+1 поверхность, которая разделяет области, соответствующие полиномам f (x) с различными количествами вещественных корней. В книгах по классической алгебре 19-го века данная поверхность называется дискриминантной поверхностью [121, 181].

В общем случае проблема сводится к исследованию поведения нулей некоторой системы алгебраических уравнений в зависимости от параметров, которые в ней содержатся. Численные методы в данном случае малоэффективны, поскольку их применение возможно только при конкретных значениях параметров (см., например, работы Д. Уилкинсона [32]). Возникает необходимость разработки надежных аналитических символьных алгоритмов. Такие алгоритмы существуют для одномерного случая, и они широко реализованы в современных системах аналитических вычислений (Maple, Mathematica, MatLab и др.), позволяющих манипулировать аналитическими выражениями и производить вычисления с вещественными числами с мантиссой практически неограниченной длины. Большинство алгоритмов для алгебраических систем общего вида

в случае больших размерностей используют алгоритм Б. Бухбергера построения базисов Грёбнера [48, 55], однако его применение часто является весьма затратным. Так, объем памяти, требуемый для его работы, в общем случае экспоненциально зависит от числа переменных. Кроме того, для систем общего вида не получено оценок времени работы алгоритма.

Поскольку нахождение характеристического полинома матрицы само по себе достаточно сложно, то возникает необходимость исследования поведения собственных чисел матрицы в тех случаях, когда построение канонического представления ее характеристического полинома вычислительно затратно. Тем самым задача о локализации собственных значений матрицы является обобщением задачи локализации корней полинома. В последнее время довольно большое внимание привлекают задачи, связанные с существованием кратных собственных чисел матрицы, например, при определении структуры жордано-вой нормальной формы матрицы в зависимости от параметров. Такие задачи встречаются в физике (в том числе в квантовой механике и ядерной физике) [44, 95, 123], оптике [51], электротехнике [80]. Рассматриваются как малые возмущения матриц [57, 65, 113, 119, 140, 169], так и значения параметра, которые не являются малыми [101, 133, 142].

Еще одним подходом к исследованию сложных систем, получившим развитие в последнее время, является приложение методов теории графов. Это связано с тем, что процессы, встречающиеся в различных приложениях (в химической кинетике, химической технологии, биологии, марковских процессах) могут описываться дифференциальными уравнениями на графах. Тем самым при построении качественной теории дифференциальных уравнений и анализа их решений могут использоваться свойства графов (см. работы [4, 24, 25, 26, 27, 39, 131, 154, 165]). Графы применяются также в теории многоагентных систем (МАС), изучение которых связано с решением практических задач в сфере сетевых и мобильных технологий, в логистике, в графике, геоинформационных системах (см. работы [139, 149, 180]) и при исследовании систем с переклю-

чениями [61, 77, 153]. К исследованию графов применимы алгебраические методы. Так, известны теоремы, связывающие спектральные свойства матрицы смежности с другими свойствами графа (см., например, книгу [53]), известное неравенство Чигера, позволяющее оценить наименьший разрез графа посредством второго собственного значения матрицы Кирхгофа (это один из наиболее применимых в алгоритмических приложениях результатов) [98], теоремы, связывающие диаметр графа и собственные числа [42, 138], которые получены с помощью линейной алгебры. Стоит отметить, что задача об изоморфизме графов может быть также сформулирована как линейно-алгебраическая задача [85]. Во многих случаях решение задач теории графов упрощается, если известно, что граф является реберным (например, задача поиска максимального независимого множества). Поэтому разработка эффективных алгоритмов распознавания реберного графа и построения его корневого графа остается актуальной, несмотря на существование нескольких таких алгоритмов [76, 126, 129, 158].

При моделировании и симуляции биологических систем анализ может проводиться с помощью численного интегрирования систем обыкновенных дифференциальных уравнений. Во многих случаях для решения систем ОДУ, описывающих работу ионных каналов клеточных мембран, используется явный метод Эйлера [84, 120, 166, 172]. В режиме реального времени при одновременном проведении экспериментов каждый шаг вычислений должен быть выполнен за ограниченное время [62]. При очень большом количестве уравнений в каждый момент времени необходимо сделать огромное количество вычислений [62, 120].

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

Цель работы заключается в разработке конструктивных алгебраических

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

Научная новизна. Выносимые на защиту результаты являются новыми и получены лично автором.

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

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

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

1) повысить достоверность и точность выполняемых расчетов,

2) сократить время вычислений,

3) проанализировать свойства системы в зависимости от параметров.

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

Основные положения, выносимые на защиту:

1. Разработанный для задач робастной устойчивости и управления алгоритм проверки устойчивости и ^-устойчивости семейства вещественных поли-

номов с коэффициентами, полиномиально зависящими от параметров.

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

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

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

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

Результаты исследования прошли апробацию на следующих конференциях: International Student's Conference in Mathematics (г. Прага, Чехословакия, 1989), XXXIV научная конференция "Процессы управления и устойчивость" (г. Санкт-Петербург, 2003), I международная конференция "Stability and Control Processes", посвященная 75-летию со дня рождения В.И. Зубова, SCP 2005 (г. Санкт-Петербург, 2005), XXXVII научная конференция "Процессы управления и устойчивость" (г. Санкт-Петербург, 2006), XXXVIII научная конференция "Процессы управления и устойчивость" (г. Санкт-Петербург, 2007), 10-я международная конференция "Computer Science and Information Technologies", CSIT 2013 (г. Ереван, Армения, 2013), 13-я международная конференция "International Conference of Numerical Analysis and Applied Mathematics", ICNAAM 2015 (г. Родос, Родос, Греция, 2015), III международная конференция "Stability and Control Processes", посвященная 85-летию со дня рождения В.И. Зубова, SCP 2015 (г. Санкт-Петербург, 2015), 18-я международная конференция

"The 18th International Workshop on Computer Algebra in Scientific Computing", CASC 2016 (г. Бухарест, Румыния, 2016), 12-я международная конференция "Computer Science and Information Technologies", CSIT 2017 (г. Ереван, Армения, 2017), а также на семинарах факультета прикладной математики — процессов управления Санкт-Петербургского государственного университета.

Публикации. По теме диссертационной работы опубликовано 20 печатных работ, в том числе 12 статей в журналах, рекомендованных ВАК РФ.

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и библиографического списка, включающего 187 наименований. Общий объем работы составляет 199 страниц.

Приведем краткое содержание работы.

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

Первая глава диссертационной работы посвящена локализации корней вещественного семейства полиномов.

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

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

С помощью теории исключения задача решения системы алгебраических уравнений от нескольких переменных может быть сведена к одномерному случаю. Практически это можно сделать с использованием современных пакетов символьных вычислений, либо с помощью алгоритма Бухбергера построения базиса Грёбнера, либо с помощью аппарата многомерных результантов. Тем самым задача анализа свойств множества решений такой системы сводится к аналогичной задаче для одного алгебраического уравнения относительно одной переменной. В частности, таким образом может быть решена задача определения количества вещественных решений, а также задача их локализации (в том числе в конкретной алгебраической области вещественной или комплексной плоскости). В развитие метода Ш. Эрмита может быть реализована процедура построения многомерного аналога системы полиномов Штурма. В диссертации данная идеология применется к задачам устойчивости и ^-устойчивости семейства вещественных полиномов.

Рассматривается вещественный полином f (г,д1,д2,... ,Дк) с коэффициентами, полиномиально зависящими от параметров д1, ...,д. Параметры изменяются в многомерном вещественном параллелепипеде:

В = {(Д1,Д2, . . . , Дк)\Д < Д1 < Д1,Д2 < Д2 < Д25 . . . ,Дк < Дк < Дк}.

Решена следующая задача.

Задача ^-устойчивости. Найти условия, необходимые и достаточные для того, чтобы каждый полином семейства

Р = {/(г,Д1,Д2,...,Дк)\ (Д1,...,Дк) е В} (1)

был ^-устойчивым, т.е. все его нули принадлежали данной алгебраической области комплексной плоскости Д.

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

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

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

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

В работе приведены численные примеры, иллюстрирующие работу предложенных алгоритмов.

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

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

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

В этой главе диссертации решены следующие задачи:

1) задача нахождения всех общих собственных чисел двух квадратных матриц А = [а^}^=1 и В = ]т-=1 с комплексными элементами. Предложен алгоритм, который позволяет построить полином, корнями которого являются общие собственные числа данных матриц.

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

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

Работа всех предложенных в работе алгоритмов показана на численных примерах.

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

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

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

С этой целью рассмотрены линейные пространства над полем Галуа характеристики 2 (ОГ(2)), т. е. множества векторов размерности п с компонентами 0 или 1 с операцией сложения по модулю 2 и умножением на 0 и 1. Доказаны некоторые результаты из теории графов, такие как теорема о циклах и разрезах, рассмотрены специфические особенности скалярного произведения векторов, связь между задачей распознавания линейного графа и задачей факторизации матрицы над ОГ(2). Также предложен новый матричный алгоритм распознавания реберного графа и построения его корневого графа.

Приводятся примеры, показывающие работу алгоритма.

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

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

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

стандартной процессорной арифметике с плавающей точкой. Поэтому вопрос точности метода Эйлера при таких вычислениях довольно важен.

Рассмотрена задача Коши для систем обыкновенных дифференциальных уравнений вида

дьХ

Ил

= ¥ (г,х), X (*о) = Хо,

(2)

где ¥ = [/^ (Ь,Х)\т=1 вещественный вектор т х 1, элементы которого — данные функции,

X (*) =

( и\ \

\

Хо =

/

о

X1

х0

т

/

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

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

В заключении перечислены основные результаты, полученные в диссертации.

Обозначения

В диссертации использованы следующие обозначения:

1. Cn = -¡~w—'7 \ 1 — биномиальный коэффициент;

k'(n - k)'

~ . dx

2. x означает —;

dt

3. j = 1,n означает, что j принимает все целые значения от 1 до n;

4. R — множество вещественных чисел; C — множество комплексных чисел;

5. для вещественного числа x:

|_xj — наибольшее целое, не превосходящее x; [x] — наименьшее целое, не меньшее x; sign x — знак x;

/

1, x > 0, sign x = ^ 0, x = 0, -1, x < 0;

6. если x комплексное число, то x — комплексно-сопряженное к x;

7. знак T означает транспонирование;

8. если X = (xi,x2,..., xn), то ||X|| = |xi| + |x2| + ... + |xn|;

9. если f (z),g(z) — полиномы, то degf — степень полинома f (z),

Sj — суммы Ньютона полинома f,

gcd(f, g) — наибольший общий делитель полиномов f и g;

nr {f (z)|g(z) > 0} [nrr {f (z)|g(z) > 0}] — число [вещественных] корней полинома f, удовлетворяющих условию g > 0;

10. обозначения D(f) и R(f, g) вводятся в разделе 1 главы 1.2;

11. если A(X, X) — квадратичная форма, то A — ее (симметричная) матрица; n+(A) [или n_(A)], r(A) и a(A) — число положительных [или отрицательных] квадратов (индекс инерции), ранг и сигнатура соответственно;

12. для произвольной квадратной матрицы A: det A — ее определитель,

Sp (A) — след,

Список литературы диссертационного исследования кандидат наук Калинина, Елизавета Александровна, 2018 год

Список литературы

1. Арнольд, В. И., Варченко, А. Н., Гусейн-Заде, С. М. Особенности дифференцируемых отображений. Том 1 / В. И. Арнольд. — М.: МЦНМО, 2009.

— 672 с.

2. Бахвалов, Н. С., Жидков, Н. П., Кобельков, Г. М. Численные методы / Н. С. Бахвалов. — М.: Издательство «Бином. Лаборатория знаний», 2008. — 640 с.

3. Бохер, М. Введение в высшую алгебру / М. Бохер. — М.: УРСС, 2008. — 292 с.

4. Вольперт, А. И. Дифференциальные уравнения на графах / А. И. Воль-перт // Матем. сб. — 1972. — Т. 88(130), № 4(8). С. 578-588.

5. Воронов, А. А. Теория автоматического управления: в 2 т. Т. 1 / А. А. Воронов. — М.: Высшая школа, 1986. — 367 с.

6. Гантмахер, Ф. Р. Теория матриц / Ф. Р. Гантмахер. — М.: Наука, 1966. — 576 с.

7. Годунов, С. К. Лекции по современным аспектам линейной алгебры / С. К. Годунов. — Новосибирск: Науч. книга, 2002. — 216 с.

8. Горушкина, Е. А. (КаНшпа Е.А.) О знакоопределенности однородного полинома при ограничениях в виде однородных полиномиальных уравнений и неравенств / Е. А. Горушкина. — Л., 1990. Депон. в ВИНИТИ №3786-В90 от 09.07.90 — 27 с.

9. Джури, Э. И. Инноры и устойчивость динамических систем / Э. И. Джури.

— М.: Наука, 1967. — 300 с.

10. Жегалкин, И. И. Арифметизация символической логики / И. И. Жегалкин // Матем. сб. — 1928. — Т. 35, № 3-4. С. 311-377; 1929. — Т. 36, № 3-4. С. 205-338.

11. Калинина, Е. А. О числе обусловленности Гёльдера / Е. А. Калинина. — Вестник СПбГУ. Серия 10: прикладная математика, информатика, процес-

сы управления. — 2013. — Т.2. — С. 46-54.

12. Калинина, Е. А. Общие собственные числа двух матриц / Е. А. Калинина // Дальневост. матем. журн. — 2013. — Т. 13, № 1. С. 52-60.

13. Калинина, Е. А. Использование алгебраических методов при анализе поведения решений дифференциальных уравнений: дисс. канд. физ.-мат. наук: 01.01.07 / Елизавета Александровна Калинина; С.-Петербург. гос. ун-т. — СПб., 1996. — 104 л.

14. Калинина, Е. А., Самарина, О. Н. Минимизация полной погрешности метода Эйлера для систем линейных дифференциальных уравнений с постоянными коэффициентами / Е. А. Калинина // Вестник СПбГУ. Серия 10: прикладная математика, инфор-матика, процессы управления. — 2009. — Т.4. — С. 95-103.

15. Калинина, Е. А., Самарина, О. Н. Вычислительная погрешность метода Эйлера при вычислениях в арифметике с плавающей точкой / Е. А. Калинина // Сибирский журнал индустриальной математики. — 2011. — Т. 14, № 3. — С. 37-49.

16. Калинина, Е. А., Хитров, Г. М. Особенности векторного пространства упорядоченных (0, 1)-наборов из п элементов над полем по модулю 2 / Е. А. Калинина // Вестник СПбГУ. Серия 10: прикладная математика, информатика, процессы управления. — 2014. — Т.1. — С. 62-71.

17. Калинина, Е. А. Кратные собственные числа матрицы с элементами, полиномиально зависящими от параметра / Е. А. Калинина // Вестник СПбГУ. Серия 10: прикладная математика, информатика, процессы управления. — 2016. — Т.2. — С. 26-33.

18. Крейн, М., Неймарк, М. Метод симметрических и эрмитовых форм в теории отделения корней алгебраических уравнений / М. Крейн // Х.: АНТ-ВУ, 1938. — 257 с.

19. Кудрявцев, Л. Д. Курс математического анализа. Т. 2 / Л. Д. Кудрявцев. — М.: Дрофа, 2004. — 720 с.

20. Лидл, Р., Нидеррайтер, Г. Конечные поля. В 2-х т. Т.1 / Р. Лидл. — М.: Мир, 1988. — 430 с.

21. Лидский, В. Б. К теории возмущений несамосопряженных операторов / В. Б. Лидский // Журн. вычисл. математики и матем. физики. — 1966. — Т. 6 №1. — С. 52-60.

22. Марков, А. А. О функциях, получаемых при обращении рядов в непрерывные дроби / А. А. Марков // Избранные труды. — М., Л.: ОГИЗ ГИТТЛ, 1948. — с. 76-105.

23. Ортега, Дж., Пул, У. Введение в численные методы решения дифференциальных уравнений / Дж. Ортега. — М.: Наука, 1986. — 288 с.

24. Подвальный, С. Л., Провоторов, В.В. Граничное управление дифференциальной системой с распределенными параметрами на графе / С. Л. Подвальный // Вестник Тамбовского университета. Серия: Естественные и технические науки. — 2015. — Т. 20, № 5. — С. 1374-1378.

25. Подвальный, С. Л., Провоторов, В.В. Стартовое управление параболической системой с распределенными параметрами на графе / С. Л. Подвальный // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления. — 2015. — № 3. — С. 126-142.

26. Подвальный, С. Л., Провоторов, В.В. Управляемость дифференциальной системы параболического типа с распределенными параметрами на графе / С. Л. Подвальный // Вестник Воронежского государственного технического университета. — 2015. — Т. 11, № № 3. — С. 49-56.

27. Подвальный, С. Л., Провоторов, В.В. Задача оптимизации параболической системы с запаздыванием и распределенными параметрами на графе / С. Л. Подвальный // Вестник Воронежского государственного технического университета. 2015. Т. 11. № 5. С. 18-27.

28. Поляк, Б. Т., Щербаков, П. С. Робастная устойчивость и управление / Б. Т. Поляк/ — М.: Наука, 2002. — 303 с.

29. Постников, М. М. Устойчивые многочлены / М. М. Постников. — М.: Наука, 1981. — 176 с.

30. Свами, М., Тхуласираман, К. Графы, сети и алгоритмы / М. Свами. — М.: Мир, 1984. — 454 с.

31. Тараканов, В. Е. Комбинаторные задачи и (0,1)-матрицы / В. Е. Тараканов. — М.: Наука, 1985. — 192 с.

32. Уилкинсон, Дж. Х. Алгебраическая проблема собственных значений / Дж. Х. Уилкинсон. — М.: Наука, 1970. — 564 с.

33. Утешев, А.Ю. Использование символьных методов локализации решений для анализа полиномиальных систем: дисс. докт. физ.-мат. наук: 05.13.18 / Алексей Юрьевич Утешев; С.-Петербург. гос. ун-т. — СПб., 1998. — 275 л.

34. Утешев, А. Ю. Использование однородных форм в качестве функций Ляпунова / А. Ю. Утешев — Л., 1987. Депон. в ВИНИТИ №2942-В87 от 24.04.87 — 13 с.

35. Фаддеев, Д. К. Лекции по алгебре / Д. К. Фаддеев. — М.: Наука, 1984. — 416 с.

36. Фаддеев, Д. К., Фаддеева, В. Н. Вычислительные методы линейной алгебры / Д. К. Фаддеев. — М.: ГИФМЛ, 1960. — 656 с.

37. Харитонов, В. Л. Об асимптотической устойчивости положения равновесия семейства систем линейных дифференциальных уравнений / В. Л. Харитонов // Дифференциальные уравнения. — 1978. — Т. 14, № 11. — С. 2086-2088.

38. Харитонов, В. Л. Об обобщении критерия устойчивости / В. Л. Харитонов // Изв. АН КазССР. Сер. физ.-мат. — 1978. — № 1. — С. 53-57.

39. Шильяк, Д. Д. Децентрализованное управление сложными системами / Д. Д. Шильяк. — М.: Мир, 1994. — 575 с.

40. Ackermann, J. Sampled-data control systems / J. Ackermann. — Berlin: Springer-Verlag, 1985. — 596 p.

41. Ackermann, J., Muench, R., Robustness analysis in a plant parameter plane / J. Ackermann // IFAC 10th Triennial World Congress, Munich, FRG. — 1987.

— P. 205-209.

42. Alan, N., Milman, V. D. Ai, Isoperimetric Inequalities for Graphs, and Superconcentrators / N. Alan // J. of Combin. Theory, Ser. B. — 1985. — № 38. — P. 73-88.

43. Albert, A. A. Symmetric and alternate matrices in an arbitrary field / A. A. Albert // Trans. Amer. Math. Soc. — 1938. — № 43. — P. 923-957.

44. Antoniou, I. E., Gadella, M., Hernandez, E., Jauregui, A., Melnikov, Yu., Mondragon, A. and Pronko G. P. Gamow vectors for barrier wells / I. E. Antoniou // Chaos, Solitons and Fractals. — 2001. — №. 12. — P. 2719-2736.

45. Babai, L., Frankl, P. Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science. Preliminary version 2 (September 1992) / L. Babai. — The University of Chicago, 1992. — 216 p.

46. Barnett, S. Polynomials and Linear Control Systems / S. Barnett. — New York: Dekker, 1983. — 452 p.

47. Bar-Yam, Y. General Features of Complex Systems [Electronic resource] / Y. Bar-Yam // Encyclopedia of Life Support Systems (EOLSS UNESCO Publishers, Oxford, UK). — 2002. — Режим доступа: http://www.eolss.net/sample-chapters/c15/E1-29-01-00.pdf, свободный.

— Загл. с экрана.

48. Becker, T., Weispfenning, V. Grobner Bases — A Computational Approach to Commutative Algebra. — New York: Springer, 1993. — 576 p.

49. Beineke, LW., Characterizations of derived graphs / LW. Beineke // Journal of Combinatorial Theory. — 1970. — Vol. 9, № 2. — P. 129-135.

50. Berman, A., Xu, Ch. (0, Incompletely positive matrices / A. Berman // Linear Algebra Appl. — 2005. — № 399. — P. 35-51.

51. Berry, M. V., Dennis, M. R. The optical singularities of birefringent dichroic chiral crystals / M. V. Berry // Proc. Roy. Soc. Lond. A. — 2003. — №. 459.

— P. 1261-1292.

52. Bhattacharyya, S. P., Chapellat, H., Keel, L. H. Robust Control: The Parametric Approach / S.P. Bhattacharyya. — New York: Prentice Hall PTR, Englewood Cliffs, 1995. — 648 p.

53. Biggs, N. Algebraic Graph Theory (2nd ed.). — Cambridge: Cambridge University Press, 1993. — 205 p.

54. Bikker, P., Uteshev, A. Yu. On the Bezout Construction of the Resultant / P. Bikker //J. Symbolic Computation. — 1999. — № 28. — P. 45-88.

55. Buchberger, B. Grobner bases: an algorithmic method in polynomial ideal theory. In Bose, N. K., ed., Multidimensional Systems Theory, pp. 184-232. Dodrecht, Reidel.

56. Burke, J. V., Lewis, A. S., and Overton, M. Optimal stability and eigenvalue multiplicity / J. V. Burke // Found. Comput. Math. — 2001. — Vol. 1, №. 2.

— P. 205-225.

57. Burke, J. V., Lewis, A. S., and Overton, M. Optimization and pseudospectra, with applications to robust stability / J. V. Burke // SIAM J. Matrix Anal. Appl. — 2003. — Vol. 25, № 1. — P. 80-104.

58. Burnside, W. Theory of groups of finite order. — Cambridge: Cambridge University Press, 1897. — 430 p.

59. Bjork, A., Dahlquist, G. Numerical mathematics and scientific computations / A. Bjork. — Philadelphia: SIAM, 2008. — Vol. 1, 482 p.

60. Borges, C. F., Discretization vs. Rounding Error in Euler's Method / C. F. Borges // The College Mathematical Journal. — 2011. — Vol. 42, № 5. — P. 396-399.

61. Borutzky, W., Dauphin-Tanguy, G., Thoma, J. U. Advances in bond graph modelling: theory, software, applications / W. Borutzky // Mathematics and Computers in Simulation. — 1995. — Vol. 39, № 5-6. — P. 465-475.

62. Butera, R. J., McCarthy, M. L. Analysis of real-time numerical integration methods applied to dynamic clamp experiments / R. J. Butera // J. Neural

Eng. — 2004. — № 1. — P. 187-194.

63. Cecioni, F. Sulle equazioni fra matrici AX = XB,Xm = A /F. Cecioni // Atti Accad. naz. Lincei, Rend. — 1909. — Vol. 5, № 18. — P. 556-571.

64. Chatelin, F. Eigenvalues of Matrices / F. Chatelin. — New York: John Wiley, 1993. — 458 p.

65. Chaitin-Chatelin, F., Harrabi, A. and Ilahi, A. About H^der condition numbers and the stratication diagram for defective eigenvalues / F. Chaitin-Chatelin // Math. Comput. Simulation. — 2000. — №. 54. — P. 397-402.

66. Chapouthier, G. Mosaic structures — a working hypothesis for the complexity of living organisms [Electronic resource] / G. Chapouthier // E-Logos (Electronic Journal for Philosophy). — 2009. — Vol. 17. — Режим доступа: http://nb.vse.cz/kfil/elogos/biocosmology/chapouthier09.pdf, свободный.

— Загл. с экрана.

67. Chen, W. K. On vector spaces associated with a graph / W. K. Chen // SIAM J. Appl. Math. — 1971. — Vol. 20 № 3. — P. 526-529.

68. Cheng, J. J., Hwang, C. Value sets of polynomial families with coefficients depending nonlinearly on perturbed parameters / J. J. Cheng // IEEE Proc., Control Theory Appl. — 1998. — Vol. 145, № 1. — P. 73-82.

69. Cohn, A., Uber die Anzahl der Wurzeln einer algebraischen Gleichung in Einem Kreise / A. Cohn // Math. Z. — 1922. — № 14. — P. 110-148.

70. Coppersmith, D. Solving linear equations over GF(2): block Lanczos algorithm / D. Coppersmith // Linear Algebra and its Applications. — 1993. — Vol. 192.

— P. 33-60.

71. Coppersmith, D. Matrix multiplication via arithmetic progressions / D. Coppersmith, Sh. Winograd // J. Symbolic Computation 9(3), 251-280 (1990)

72. Cormen, Th. H., Leiserson, Ch. E., Rivest, R. L., Stein, C. Introduction to Algorithms / Th. H. Cormen. — Cambridge, Massachusetts: MIT Press, 1990.

— 1292 p.

73. Couceiro, M., Foldes, S. Definability of Boolean function classes by linear

equations over GF(2) / M. Couceiro // Discrete Applied Mathematics. — 2004. — Vol. 142, issues 1-3. — P. 29-34.

74. Datta, B. N. On the Routh — Hurwitz — Fujiwara and the Shur — Cohn — Fujiwara Theorems fot the Root-Separation Problem / B. N. Datta // Linear Algebra and its Applications. — 1978. — Vol. 22. — P. 235-245.

75. Datta, A., Ho, M.-T., Bhattacharyya, S. P. Structure and Synthesis of PID Controllers / A. Datta. — London: Springer Verlag, 2003. — 233 p.

76. Degiorgi, D. G., Simon K. A dynamic algorithm for line graph recognition / D. G. Degiorgi // Lecture Notes in Comput. Sci. — 1995. — Vol. 1017. — P. 37-48.

77. Delgado, M., Sira-Ramirez, H. A bond graph approach to the modeling and simulation of switch regulated DC-to-DC power supplies / M. Delgado // Simulation Practice and Theory. — 1998. — Vol. 6, №7. — P. 631-646.

78. Deo, N. Graph Theory with Applications to Engineering and Computer Science / N. Deo. — New Jork: Prentice-Hall, 1974. — 478 p.

79. Diestel R. Graph Theory Fourth Edition / R. Diestel. — Heidelberg: SpringerVerlag, 2010. — 451 p.

80. Dobson, I., Zhang, J., Greene, S., Engdahl, H. and Sauer, P. W. Is strong modal resonance a precursor to power system oscillations? / I. Dobson // IEEE Transactions On Circuits And Systems I: Fundamental Theory And Applications. — 2001. — №. 48. — P. 340-349.

81. Duff, I. S., Reid, J. K., Algorithm 529: Permutations to Block Triangular Form [F1] / I. S. Duff // ACM Trans. Math. Softw. — 1978. — Vol. 4, № 2. — P. 189-192.

82. Edmonds, J. Paths, trees, and flowers / J. Edmonds // Canad. J. Math. — 1965. — № 17. — P. 449-467.

83. Realtime Simulation of Detailed Vehicle and Powertrain Dynamics, SAE 2004 World Congress & Exhibition / H. Elmqvist [et al.] // SAE Paper 2004-01-0768. — 2004.

84. Fall, C. P., Rinzel, J. An intracellular Ca2+ subsystem as a biologically plausible source of intrinsic conditional bistability in a network model of working memory / C. P. Fall // J. Comput. Neurosci. — 2006. — № 20. — P. 97-107.

85. Friedland, Sh. Quadratic Forms and the Graph lsomorphism Problem. / Sh. Friedland // Linear Algebra Appl. — 1991. — № 150. — P. 423-442.

86. Frobenius, F. G. Uber die mit einer Matrix vertauschbaren Matrizen / F. G. Frobenius // Berlin Sitzb. — 1910. — P. 3-15.

87. Garloff, J., Zettler, M. Robustness Analysis of Polynomials with Polynomial Parameter Dependency Using Bernstein Expansion / J. Garloff // IEEE Trans. Automat. Control. — 1998. — № 43. — P. 425-431.

88. Gelfand, I. M., Kapranov, M. M., Zelevinsky, A. V. Discriminants, Resultants and Multidimensional Determinants / I. M. Gelfand. — Boston: Birkhäuser, 1994. — 532 p.

89. Giorgi, P. On the complexity of polynomial matrix computations / P. Giorgi [et al.] // ISSAC'03. — New York: ACM Press, 2003. — pp. 135-142.

90. Golub, G. H., Van Loan, Ch.F. Matrix Computations / Golub, G. H., Van Loan, Ch.F. — Baltimore and London: The Johns Hopkins University Press, 1996. — 694 p.

91. Golub, G. H., Ortega, J. M. Scientific Computing and Differential Equations / G.H. Golub. — San Diego, California: Academic Press, 1992. — 337 p.

92. Gutman, S. Root Clustering in Parameter Space / S. Gutman. — Berlin: Springer-Verlag, 1990. — 120 p.

93. Halmos, P. R. Finite-dimensional vector spaces. Undergraduate Texts in Mathematics / P. R. Halmos. — New York: Springer-Verlag, 1993. — 202 p.

94. Harary, F. Graph Theory / F. Harary. — Addison-Wesley, Reading, MA, 1969. — 274 p.

95. Heiss W. D. Exceptional points - their universal occurrence and their physical significance / W. D. Heiss // Czech. J. Phys. — 2004. — №. 54. — P. 1091-1099.

96. Hermite, C. Extrait d'une lettre de Mr. Ch. Hermite de Paris 'a Mr. Borchardt

de Berlin, sur le nombre des racines d'une 'equation alg'ebrique comprises entre des limits don'ees / C. Hermite // J. Reine Angew. Math. — 1856. — № 52. — P. 39-51.

97. Higham, N. J. Accuracy and stability of numerical algorithms / N. J. Higham.

— Philadelphia: SIAM, 1996. — 688 p.

98. Hoory, S., Linial, N., Widgerson, A. Expander graphs and their applications / S. Hoory // Bulletin (New series) of the American Mathematical Society. — 2006. — Vol. 43, № 4. — P. 439-561.

99. Hosoya H. Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons / H. Hosoya // Bulletin of the Chemical Society of Japan. — 1971. — Vol. 44, № 9. — P. 2332-2339.

100. Janusz, G. J. Parametrization of self-dual codes by orthogonal matrices / G. J. Janusz // Finite Fields Appl. — 2007. — № 13. — P. 450-491.

101. Jarlebring, E., Kvaal, S., Michiels, W. Computing all pairs (A; such that A is a double eigenvalue of A + ^B / E. Jarlebring // SIAM J. Matrix Anal. Appl.

— 2011. — № 32. — P. 902-927.

102. Horn, R.A., Johnson, Ch.R.: Matrix Analysis / R. A. Horn. — New York: Cambridge University Press, 2013. — 651 p.

103. Horn, R. A., Johnson, Ch. R. Topics in matrix analysis / R. A. Horn. — New York: Cambridge University Press, 1991. — 607 p.

104. Hurwitz, A. On the conditions under which an equation has only roots with negative real parts / A. Hurwitz // Selected Papers on Mathematical Trends in Control Theory / ed. by R. Bellman, R. Kalaba. — Dover, New York, 1964.

— P. 72-82.

105. Kahaner, D., Moler, C., Nash, S. Numerical Methods and Software / D. Kahaner. — Englewood Cliffs, New Jersey: Prentice-Hall, 1989. — 495 p.

106. Kalinina, E. Stability and D-stability of the family of real polynomials / E. Kalinina // Linear Algebra and Its Applications. — 2013. — № 438. —

P. 2635-2650

107. Kalinina, E., The most precise computations using Euler's method in standard floating-point arithmetic applied to modelling of biological systems / E. Kalinina // Computer Methods and Programs in Biomedicine. — 2013. — Vol. 111, № 2. — P. 471-479.

108. Kalinina, E. A., Uteshev, A. Yu. Determination of the Number of Roots of a Polynomial Lying in a Given Algebraic Domain / E. A. Kalinina // Linear algebra and its applications. — 1993. — № 185. — P. 61-81.

109. Kalinina, E.A. On Multiple Eigenvalues of a Matrix Dependent on a Parameter / E. A. Kalinina // Proc. of the 18th Intern. Workshop, CASC 2016. LNCS 9890, pp. 305-314.

110. Kalinina, E., Pogozhev, S., Khitrov, G.Edge covers and independence: algebraic approach // Proceedings of the International Conference on Numerical Analysis and Applied Mathematics 2015 (ICNAAM-2015). AIP Publishing, 2016. AIP Conf. Proc. 1738.

111. Kalinina, E., Pogozhev, S., Khitrov, G. Linear algebra methods in graph theory // "Stability and Control Processes"in Memory of V.I. Zubov (SCP), 2015 International Conference. — P. 570-572.

112. Kalman, R. E. Algebraic characterization of polynomials whoes zeroz lie in certain algebraic domain / R. E. Kalman // Proc. of the National Academie of the U.S.A. — 1969. — Vol. 64., № 3. — P. 818-823.

113. Karow, M. Eigenvalue condition numbers and a formula of Burke, Lewis and Overton / M. Karow // Electron. J. Linear Algebra. — 2006. — № 15. — P. 143-153.

114. Kato, T. Perturbation Theory for Linear Operators / T. Kato. — Berlin: Springer, 1980. — 619 p.

115. Keel, L. H., Bhattacharyya, S. P. Robust Stability via Sign-Definite Decomposition / L.H. Keel // IEEE Trans. Automat. Control. — 2011. — Vol. 56, №1. — P. 140-145.

116. Kharitonov, V. L. Interval srability of quasipolynomials / V. L. Kharitonov //In Control of Uncertain Dynamical Systems, S.P. Bhattacharyya and L.H. Keel, Eds. CRC Press, Littleton, MA. — 1991. — P. 436-446.

117. Kharitonov, V. L. Robust stability of nested polynomial families / V. L. Kharitonov // Nech. rep., institut für Dynamische Systeme, Universitat Bremen, Germany. — May, 1994. — Report №. 306

118. Kharitonov, V. L., Torres-Munoz, J. A., Ortiz-Moctezuma, M. B. Polytopic families of quasipolynomials: vertex-type stability conditions / V. L. Kharitonov // Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on [see also Circuits and Systems I: Regular Papers, IEEE Transactions on]. — 2003. — Vol. 50, № 11. — P 1413-1420.

119. Kressner, D., Pelaez, M. J., and Moro, J. Structured Holder condition numbers for multiple eigenvalues / D. Knesser // SIAM J. Matrix Anal. Appl. — 2009.

— Vol. 31, № 1. — P. 175-201.

120. Korhonen, T., Tavi, P. Automatic time-step adaptation of the forward Euler method in simulation of models of ion channels and excitable cells and tissue / T. Korhonen // Simulation Modelling Practice and Theory. — 2008. — № 16.

— P. 639-644.

121. Kronecker, L. Zur Theorie der Elimination einer Variabeln aus zwei Algebraischen Gleichungen (1881) / L. Kronecker // Leopold Kronecker's Werke. — Leipzig: Teubner, 1897. — Bd. 2. — P. 113-192.

122. Ladyman, J., Lambert, J., Wiesner, K. What is a Complex System? J. Ladyman // European Journal for Philosophy of Science. — 2013. — №. 3.

— P. 33-67.

123. Latinne, O., Kylstra, N. J., Dorr, M., Purvis, J., Terao-Dunseath, M., Jochain, C. J., Burke, P. G. and Noble, C. J. Laser-induced degeneracies involving autoionizing states in complex atoms / O. Latinne // Phys. Rev. Lett. — 1995. — №. 74. — P. 46-49.

124. Laurent, H. L'Elimination. In Scientia, Phys.-Mathematique, volume 7 /

Y. Laurent — Paris: Gauthier-Villars, 1900. —

125. Lehnigk, S. H. Stability Theory for Linear Motions ns with an Introduction to Liapunov's Direct Method / S. H. Lehngik. — New York: Prentice-Hall, 1966. — 251 p.

126. Lehot, Ph. G. H. An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph / Ph. G. H. Lehot // J. ACM. — 1974. — Vol. 21, № 4. — P. 569-575.

127. Lempel, A. Matrix Factorization over GF(2) and Trace-Orthogonal Bases of GF(2n) / A. Lempel // SIAM J. Comput. — 1975. — Vol. 4, № 2. — P. 175-186.

128. Littlewood, D. E. The theory of group characters and matrix representations of groups / D. E. Littlewood. — Oxford: Oxford University Press, 1950. — 310 p.

129. Liu, D., Trajanovski, S., Van Mieghem, P. ILIGRA: An Efficient Inverse Line Graph Algorithm / D. Liu // Journal of Mathematical Modelling and Algorithms in Operations Research. — 2015. — Vol. 14, № 1. — P. 13-33.

130. MacDuffee, C. C. The Theory of Matrices / C .C. MacDaffee. — New York: Chelsea Publishing Company, 1956. — 110 p.

131. Maidens, J. Global Lyapunov functions and a hierarchical control scheme for networks of robotic agents / J. Maidens // American Control Conference (ACC). — 2013. — P. 4050-4055.

132. MacWilliams, J. Orthogonal matrices over finite fields / J. MacWilliams // Amer. Math. Monthly. — 1969. — № 76. — P. 152-164.

133. Mailybaev A. A. Computation of multiple eigenvalues and generalized eigenvectors for matrices dependent on parameters / A. A. Mailybaev // Linear Algebra Appl. — 2006. — № 13. — P. 419-436.

134. Macaulay, F. S. On some formulae in elimination / F. S. Macaulay // Proc. London Math. Soc. — 1903. — Vol. 35. — P. 3-27.

135. Marenich, E. E. Factorization properties of (n x n) Boolean matrices / E. E. Marenich // J. Math. Sci. (N. Y.). — 2009. — Vol. 163, № 6. — P. 732-738.

136. Markoff, A. On the determination of the number of roots of an algebraic

equation, situated in a given domain / A. Markoff // Математический сборник. — 1940. — Т. 7 (49), № 1. — С. 3-6.

137. The Math Libraries [Электронный ресурс]. — Режим доступа: http://docs.oracle.com/cd/E19957-01/806-3568/ncg_lib.html, свободный. — Загл. с экрана.

138. Mohar, B., Eigenvalues, Diameter, and Mean Distance in Graphs / B. Mohar // Graphs Combin. — 1991. — № 7. — P. 53-64.

139. Monshizadeh, N., Zhang, Sh., Kanat Camlibel, M. Disturbance decoupling problem for multi-agent systems: A graph topological approach / N. Monshizadeh // Systems & Control Letters. — 2015. — Vol. 76. — P. 35-41.

140. Moro, J., Burke, J. V., Overton, M. L. On the Lidskii-Vishik-Lyusternik Perturbation Theory for Eigenvalues of Matrices with Arbitrary Jordan Structure / J. Moro // SIAM J. Matrix Anal. Appl. — 1997. — Vol. 18, № 4.

— P. 793-817.

141. Mucha, M., Sankowski, P. Maximum Matchings via Gaussian Elimination / M. Mucha // Proc. 45th IEEE Symp. Foundations of Computer Science. — 2004. — P. 248-255.

142. Muhic, A., Plestenjak, B. A method for computing all values A such that A+AB has a multiple eigenvalue / A. Muhica // Linear Algebra Appl. — 2014. — № 440. — P. 345-359.

143. Netto, E. Vorlesungen über Algebra, Bd. 2. / E. Netto. — Leipzig: Teubner, 1900. — 531 s.

144. Norman, R. Z., Rabin M. O. An Algorithm for a Minimum Cover of a Graph / R. Z. Norman // Proc. Amer. Math. Soc. — 1959. — Vol. 10, № 2. P. 315-319.

145. Olshevsky, A., Olshevsky, V. Kharitonov's theorem and Hermite's criterion / A.Olshevsky // Linear Algebra and Its Applications. — 2005. — Vol. 399, № 1.

— P. 285-297.

146. Ostrowski, A. M. Solution of Equations and Systems of Equations / A. M. Ostrowski. — New York: Academic Press, 1960. — 202 p.

147. Seroussi, G., Lempel, A. Factorization of symmetric matrices and trace-orthogonal bases in finite fields / G. Seroussi // SIAM J. Comput. — 1980.

— № 9. — P. 758-767.

148. Leverrier, U.J.J. Sur les variations seculaires des elements des orbites pour les sept planetes principales / U. J. J. Leverrier // J. de Math. — 1840. — № 1(5).

— P. 220-254. (1840)

149. Oh, K.-K., Moore, K. L., Ahn, H.-S. Disturbance attenuation in a consensus network of identical linear systems: An H^ approach / K.-K. Oh // IEEE Transactions on Automatic Control. — 2014. — Vol. 59 (8), № 6701156. — P. 2164-2169.

150. Pan, V. Algebraic complexity of computing polynomial zeros / V. Pan // Comput. Math. Appl. — 1987. — Vol. 14, № 4. — P. 285-304.

151. Pemmaraju, S., Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica / S. Skiena. — Cambridge: Cambridge University Press, 2003. — 480 p.

152. Pothen, A., Fan, C. Computing the block triangular form of a sparse matrix / A. Pothen // ACM Trans. Math. Softw. — 1990. — Vol. 16, № 4. — P. 303-324.

153. Poyraz, M., Demir, Y., Gulten, A., Koksal, M. Analysis of switched systems using the bond graph methods / M. Poyraz // Journal of the Franklin Institute.

— 1999. — Vol. 336, № 3. — P. 379-386.

154. Provotorov, V.V. Boundary control of a parabolic system with distributed parameters on a graph in the class of summable functions / V. V. Provotorov // Automation and Remote Control. — 2015. — Vol. 76, № 2. — P. 318-322.

155. Ptak V. Explicit Expressions for Bezoutiants / V. Ptak // Linear Algebra and its Applications. — 1984. — Vol. 59. — P. 43-54.

156. Ramnath, S., Sunder, S. On two-processor scheduling and maximum matching in permutation graphs. — 1996. — Vol. 50, № 6. — P. 321-327.

157. Roth, W. E. On direct product matrices / W. E. Roth // Bull. Amer. Math. Soc. — 1934. — № 40. — P. 461-468.

158. Roussopoulos, N. D. A max{m,n} algorithm for determining the graph H from its line graph G / N. D. Roussopoulos // Inform. Process. Lett. — 1973.

— Vol. 2, № 4. — P. 108-112.

159. Routh, E. J. A Treatise on the Stability of a Given State of Motion: Particularly Steady Motion / E.J. Routh. — London: Macmillan and co., 1877. — 108 p.

160. Introduction to the Modeling and Analysis of Complex Systems / H. Sayama.

— New York: Open SUNY Textbooks, 2015. — 498 p.

161. Schlüfli, L. Über die Resultante eines Systemes mehrerer algebraischer Gleichungen. / L. Schlafli //In Gesammelte Mathematische Abhandlungen.

— Basel: Birkhauser, 1953. — Vol. 2. — P. 9-112.

162. Schur, I. Uber potenzreihen, die im Innern des Einheitskreises beschrankt sind / I. Schur // J. fur Mathematik. — 1917 and 1918. — 147 and 148. — P. 205--232 and 122--145; English Transl. in: J. Schur Methods in Operator Theory and Signal Processing (Operator Theory: Advances and Applications, OT 18, Basel: Birkhauser-Verlag. — 1986. — P. 31--88).

163. Seelinger, G., Sissokho, P., Spence, L., Vanden Eynden, C. Partitions of finite vector spaces over GF(2) into subspaces of dimensions 2 and s / G. Seelinger // Finite Fields and Their Applications. — 2012. — Vol.18, № 6. — P. 1114-1132.

164. Serret, J.-A. Cours d'Algebre Superieur, volume 1 / J.-A. Serret. — Paris: Gauthier-Villars, 1866. — 643 p.

165. Siegel, D., MacLean, D. Global stability of complex balanced mechanisms / D. Siegel // Journal of Mathematical Chemistry. — 2000. — Vol. 27, №. 1. — P. 89-110.

166. Sneyd, J., Dufour, J-F. A dynamic model of the type-2 inositol triphosphate receptor / J. Sneyd // Proc. Natl. Acad. Sci. USA. — 2002. — № 99. — P. 2398-2403.

167. Strassen, V. Gaussian Elimination is not Optimal / V. Strassen // Numerische Mathemetik. — 1969. — № 13. — P. 354-356.

168. Schucan, T. H. and Weidenmüller H. A. Perturbation theory for the effective

interaction in nuclei / T. H. Schucan // Ann. Physics. — 1973. — № 76. — P. 483-501.

169. Sun, J. On condition numbers of a nondefective multiple eigenvalue /J. Sun // Numer. Math. — 1992. — №. 61. — P. 265-275.

170. Thom, M. R. Sur la theorie des enveloppes, J. de mathematiques pures et appliquees / M. R. Thom. — Paris: Gauthier-Villars, 1962. — T. 41, № 2. — P. 177-192.

171. Thulasiraman, K., Swamy, M. N. S. Graphs: Theory and Algorithms / K. Thulasiraman. — Wiley, 1992.

172. A model for human ventricular tissue / K.H.W.J. Ten Tusscher [et al.] // Am. J. Physiol. Heart Circ. Physiol. — 2004. — № 286. — H1573-H1589.

173. Uspensky, J. V. Theory of Equations / J.V. Uspensky. — New York: McGraw-Hill, 1948. — 353 p.

174. Uteshev, A. Yu., Baravy, I. Solution of interpolation problems via the Hankel polynomial construction. arXiv: cs.SC/1603.08752.2016

175. Uteshev, A. Yu., Cherkasov, T. M. On the search of the maximum of a polynomial / A. Yu. Uteshev // RISC-LINZ Report series. — 1995. — № 95-16. — 18 p.

176. Uteshev, A. Yu., Shulyak, S. G. Hermite's Method of Separation of Solutions of Systems of Algebraic Equations and its Applications / A. Yu. Uteshev // Linear Algebra and its Applications. — 1992. — Vol. 177. — P. 49-88.

177. Wang, M., Lee, F. B., Boley, D. Matrix Pencil and Matrix Measure Methods for Robust Stability in Real Parameter Spaces / M. Wang // Proceedings of the 30th Conference on Control. England. — 1991. — P. 411-415.

178. Victorri, B. [et al.] Numerical integration in the reconstruction of cardiac action potentials using the Hodgkin — Hucksley model / B. Victorri // Computers and Biomed Res. — 1985. — № 18. — P. 10-23.

179. Wayland, H. Expansion of determinantal equations into polynomial form / H. Wayland // Quart. Appl. Math. — 1945. — Vol. 2, № 4. — P. 277-305.

180. Wang, J., Liu, Z., Hu, X. Consensus control design for multi-agent systems using relative output feedback / J. Wang // Journal of Systems Science and Complexity. — 2014. — Vol. 27, № 2. — P. 237-251.

181. Weber, H. Lehrbuch der Algebra. Bd.I / H. Weber. — Braunschweig: F. Vieweg & Sohn Verlag, 1898. — 653 p.

182. Whitney, H. Congruent graphs and the connectivity of graphs / H. Whitney // American Journal of Mathematics. — 1932. — Vol. 54 № 1. — P. 150-168.

183. Williams, T. W., Maxwell, L. M. The decomposition of the graph and the introduction of the new class of subgraphs / T. W. Williams // SIAM J. Appl. Math. — 1971. — Vol. 20, № 3. — P. 385-389.

184. Yeh, D. T. [et al.] Numerical Methods for Simulation of Guitar Distortion Circuits / D. T. Yeh // Computer Music J. — 2008. — Vol. 32, № 2. — P. 23-42.

185. Zayed, J. M. Chemical Complexity — supramolecular self-assembly of synthetic and biological building blocks in water / J. M. Zayed, N. Nouvel, U. Rauwald, O. A. Scherman // Chemical Society Reviews, 2010. — Vol. 39. — P. 2806-2816.

186. Zhong, J. Binary ranks and binary factorizations of nonnegative integer matrices / J. Zhong // Electron. J. Linear Algebra. — 2012. — No 23. — P. 540-552.

187. Zhu, H. [et al.] Facilitating arrhythmia simulation: the method of quantitative cellular automata modeling and parallel running / H. Zhu // BioMedical Engineering OnLine. — 2004. — Vol. 3, № 29.

SAINT-PETERSBURG STATE UNIVERSITY

As Manuscript

Elizaveta Kalinina

Applying algebraic methods for the complex

systems analysis

05.13.01 - System analysis, information control and processing (in applied mathematics and processes of control)

Doctoral Dissertation

Scientific Consultant

Professor

A.Yu. Uteshev

Saint Petersburg - 2018

202

Contents

Introduction...................................205

Chapter 1. Stability and D-stability of the family of real polynomials218

1.1. Introduction...............................218

1.2. Preliminaries..............................220

1.2.1. Theory of differentiable maps.................220

1.2.2. Elimination theory.......................221

1.2.3. Separation of polynomial roots................226

1.2.4. Stability of a polynomial....................237

1.3. Real roots of polynomial families ...................239

1.4. Stability of polynomial families ....................245

1.5. D-stability of polynomial families...................248

1.6. Track-guided bus Daimler-Benz 0305 ..................................251

1.6.1. Preliminaries..........................251

1.6.2. Solution ..........................................................258

1.7. Conclusion ..............................................................265

Chapter 2. Eigenvalues of matrices.....................266

2.1. Preliminary results...........................266

2.2. Common eigenvalues of two matrices ..................................270

2.2.1. Preliminaries..........................270

2.2.2. The algorithm ..................................................275

2.2.3. Example............................276

2.3. Jordan normal form of a matrix....................278

2.3.1. Preliminaries..........................279

2.3.2. Main results..........................282

2.3.3. The largest Jordan block ......................................296

2.3.4. Description of the algorithm..................297

Order of the largest Jordan block...............297

Eigenvalues corresponding to the largest Jordan blocks . . . 298

2.3.5. A numerical example......................300

2.3.6. Conclusion...........................301

2.4. Multiple eigenvalues ..........................301

2.4.1. Preliminaries..........................302

2.4.2. Multiple eigenvalues of a matrix dependent on a parameter . 304

2.4.3. The Algorithm.........................308

2.4.4. Asymptotic complexity of the algorithm and accuracy of computations ....................................................309

2.4.5. A numerical example......................311

Chapter 3. Graphs and matrices......................313

3.1. Introduction...............................313

3.2. Some preliminary definitions and results ...............314

3.2.1. Vector spaces and orthogonality over GF(2).........314

3.2.2. Necessary information about graphs .............316

3.2.3. Graphs and linear maps....................320

Linear maps..........................320

Matchings and edge coverings.................322

3.3. Some auxiliary results ..................................................324

3.3.1. The Gram matrix over GF(2) and its properties.......324

3.3.2. Matrix factorization over GF(2) ...............325

3.4. The theorem on graph circuits and cut-sets..............331

3.5. Problem of line graph recognition ......................................332

3.5.1. Theoretical preliminaries ...................332

3.5.2. Algorithm description.....................334

3.5.3. The algorithm.........................336

3.5.4. Examples............................337

Chapter 4. Euler's method..........................342

4.1. Introduction...............................342

4.2. The local optimal step size for Euler's method............344

4.3. Practical implementation of the method................348

4.4. Numerical examples ....................................................353

4.5. Discussion and conclusions.......................361

Conclusion....................................363

References....................................365

205

Introduction

Motivation of the research. Complex systems theory is an exciting new research area studying how parts of a system give rise to the collective behaviors of the system, and how the system interacts with its environment. Complex systems are used to model processes in computer science, biology, economics, physics, chemistry and many other fields (v., e.g., book [159], papers [46, 64, 121, 184]). Nowadays there are over 50 institutes and research centers focusing on complex systems all over the world.

The traditional approach to deal with complex systems is modelling. A mathematical model is a simplified version of the real situation, it can be considered as the formal description of an object that can be studied mathematically. Functional models describe processes concerned with the functioning of the object. They are usually in the form of a system of equations, frequently nonlinear dynamical system. Structural models reflect the structural properties of the object. They can take form of graphs, matrices and so on.

It is important to study the responses of dynamical systems dependent on parameters to the variations of these parameters. Certain essential properties of the system must remain unchanged under perturbations. Thus, the problems of robust stability and control under parameter uncertainty originate. In this work, some algebraic methods allowing us to solve these problems in certain cases are presented.

The subject of robust control [51] received worldwide attention in the late 1970's. One of the first important results in this area is Kharitonov's Theorem for interval polynomials [37] published in 1978. Then there were other significant developments such as calculation of the radius of the stability ball in the space of coefficients of a polynomial by Soh, Berger and Dabke, the Generalized Kharitonov Theorem, highly efficient computational techniques of determining stability margins, such as the Tsypkin — Polyak locus described in [27, 36, 114, 115, 116] and so on.

For the problem of robust stability, it is necessary to study the spectrum of a certain matrix describing the system. Thus, we need in methods of zeros localization for a univariate polynomial or for a system of algebraic equations dependent on several variables.

The problem of checking the stability of linear autonomous system reduces to the determination of whether or not the roots of the characteristic polynomial of the system lie strictly in the left half-plane of the complex plane, that is whether or not the characteristic polynomial is a Hurwitz polynomial. For a polynomial, the necessary and sufficient condition to be Hurwitz the well-known Routh — Hurwitz theorem gives. However, in many practical problems it is necessary to guarantee that zeros do not move too far from their nominal positions under the influence of parameter perturbations. In the other words, the roots of a characteristic polynomial must be situated in some algebraic domain D of the complex plane. This is the problem of D-stability (v. [39, 40]).

The problem of determination of the number of polynomial zeros lying in some domain of the complex plane is known from the first half of the XlX-th century. This problem originated in the work by Ch. Hermite and was studied by I. Schur, P. Cohn, B. N. Datta, J. Ackermann and R. Muench, R. E. Calman and others [9, 28, 90, 119]. For instance, to determine whether or not all the roots of the polynomial lie strictly within the unit disk the Schur — Cohn criterion is used [6] (B. N. Datta generalized the criterions of Routh — Hurwitz and Schur — Cohn using bezoutiant [72]). In the case of domains with bounds prescribed by unicursal (real-valued parametrized) curves, the Hermite method (1854) [94] can be used. The Calman criterion allows us to determine whether or not all the roots of a polynomial belong to a certain algebraic domain in the complex plane [110]. Another approach to the problem of stability based on concepts from sign-definite decomposition, i.e., decomposition in the parameter space can be found in [5]. But it is difficult to use this approach when

In classic algebra it is known that in the space of polynomial coefficients the bounds of domains corresponding to the polynomials with the same number of real

roots, are defined by the discriminant manifold. The number of real zeros of the univariate polynomial depends crucially on a special function of its coefficients, namely the discriminant. For the polynomial

f (x) = a0xn + a1xn-1 + ... + an e R[x], a0 = 0,n > 2

it is a polynomial in the coefficients

D(f) = D(ao,ai,..., an)

whose vanishement provides the necessary and sufficient conditions for the existence of multiple zeros for f (x). The equation D = 0 defines in Rn+1 (space of coefficients) the manifold separating the domains corresponding to polynomials f(x) with distinct numbers of real zeros. In classical Algebra textbooks of the 19-th century this manifold is known as the discriminant surface [120, 180].

In general case, the problem reduces to studying the location of zeros of a certain system of algebraic equations dependent on parameters. For this purpose, numerical methods are ineffective because they can be used only for particular values of variables (v., e.g., works of D. Wilkinson [31]). Therefore we need in reliable symbolic algorithms. For one-dimensional case such algorithms are known, and they are widely represented in contemporary computer algebra systems (Maple, Mathematica, MATLAB and others) that allow us to manipulate symbolic expressions and use software floating-point arithmetic of arbitrary precision. The most methods for general case use the Buchberger algorithm to construct Grobner basis [47, 54], but often it is computationally expensive. It is known that in general case the exponential increase of the required memory space will follow the increase of the number of the variables. Besides, the run-time complexity of this algorithm could not be estimated.

The problem of computation of the characteristic polynomial of a matrix is computationally expensive in itself. Thus, it is important to study the localization of matrix spectrum in the case when we do not know its characteristic polynomial. This is a generalization of a problem of localization of polynomial roots. Recently, multiple

eigenvalues became of great interest in physics, including quantum mechanics and nuclear physics [43, 93, 122], optics [50], and electrical engineering [78]. In most applications, multiple eigenvalues appear through the introduction of parameters. Both small matrix perturbations [56, 63, 111, 117, 139, 168] and perturbations when parameters take values not small enough [99, 132, 141] are under consideration.

There is one more approach to the complex systems studying. Many methods of graph theory can be applied to the description of such systems. Different processes considered in various applications (e.g., in chemical kinetics, chemical technology, biology, Markov processes) can be modelled by differential equations on graphs. Considering qualitative properties of differential equations and analyzing their solutions, we can use methods of graph theory (v. works [4, 23, 24, 25, 26, 38, 130, 153, 164]). Graphs are used in theory of multi-agent systems (M.A.S.) originated in practical problems of network and mobile technologies, logistics, graphics, geographic information systems [138, 148, 179] and switched systems [59, 75, 152]. Graphs can be studied with the help of algebra [77]. For example, the theorems relating spectral properties of the adjacency matrix to other graph properties (see, e.g., [52]), the famous Cheeger's inequality approximating the sparsest cut-set (one of the most useful facts in algorithmic applications) [96], the theorems relating graph diameter and eigenvalues [41, 137] are proven applying linear algebra methods. It is worth mentioning that the well-known graph isomorphism problem can be treated as a linear algebra problem too [83]. In many cases, the solution of graph problems becomes simpler if a graph under consideration is a line one. For example, this is true for the maximum independent set problem. Thus, we need in new effective methods of line graph recognizing and constructing its root graph despite existence of several known algorithms [74, 125, 128, 157].

In most cases, numerical integration is used to find the numerical approximation for the solution of systems of ordinary differential equations (ODE) originated in modelling and simulating of biological systems. For ordinary differential equations describing the function of the ion channels of the cell membrane, in many cases

the explicit Euler's method is employed [82, 118, 165, 171]. In real-time simulations coupled with experiments, there is a fixed limit on computational time per every time step of integration [60]. And it is very important to do every integration step as rapidly as possible because of the great number of computations per every time step [60, 118].

Therefore, we need in numerical methods that work fast and allow us to find the solution of initial-value problem with minimum error (taking into account the rounding errors [2, 22, 35] because in most cases the computations are made in standard processor floating-point arithmetic). For this purpose the algebraic approach turned out to be useful.

The goal of the work consists in developing algebraic methods and algorithms that can be used for the complex systems analysis and applying these algorithms to certain problems where dynamics and stability analysis of such systems depending on parameters is required.

Scientific originality. All the results are new and are obtained by the author.

Theoretical and practical value. The results presented in the dissertation allow us to simplify the analysis of robust stability and D-stability of complex systems, and compute solutions of such systems with minimum error (taking into account the rounding errors) in standard floating-point arithmetic.

The proposed algorithms are effective and reliable. Thus, they can be used in mechanics, theory of control, biophysics and chemical kinetics. Their simplicity and computational effectiveness make possible to use them for real-time modelling processes in complex systems.

Practical value of the results is that in complex systems modelling and analyzing they make it possible

1) to increase reliability and accuracy of computations;

2) to speed up computations;

3) to analyze the properties of a system depending on parameters.

Methods of research. In the dissertation the methods of system analysis,

classic algebra of polynomials (Elimination Theory for systems of algebraic equations, theory of Hankel quadratic forms for problems concerning localization of the solutions of such systems), theory of differentiable maps and algebraic graph theory, errors estimating in standard floating-point arithmetic are used.

The main results are:

1. An algorithm for checking of stability and D-stability of the family of real polynomials with coefficients polynomially dependent on parameters is presented. This algorithm can be applied for robust stability and control problems.

2. For the multicomponent systems analysis, an algorithm of computation of common eigenvalues of several matrices — components of such a system, is proposed;

3. For the analysis of dynamics of complex systems dependent on a parameter studied in physics, optics, electrotechnics, an algorithm of finding the structure of a Jordan normal form of a complex matrix is developed;

4. A matrix algorithm to recognize a line graph and construct its root graph that allows us to simplify the description of structure and studying features of switched systems and multi-agent systems is proposed;

5. A new effective numerical algorithm that allows us to compute a solution of initial-value problem for the system of ordinary differential equations with minimum total error (taking into account the rounding errors) is presented. This algorithm can be applied in real-time calculations in standard floating-point arithmetic.

The results of the work were presented on the conferences: International Student's Conference in Mathematics (Prague, Czechoslovakia, 1989), XXXIV scientific conference "Control Processes and Stability" (Saint-Petersburg, 2003), I international conference "Stability and Control Processes" in memory of V.I. Zubov, SCP 2005 (Saint-Petersburg, 2005), XXXVII scientific conference "Control Processes and Stability" (Saint-Petersburg, 2006), XXXVIII scientific conference "Control Processes and Stability" (Saint-Petersburg, 2007), 10-th international conference "Computer Science and Informati Technologies", CSIT 2013 (Yerevan, Armenia, 2013), 13-th international conference "International Conference of Numerical Analysis and Applied Mathematics", ICNAAM

2015 (Rhodes, Rhodes, Greece, 2015), III international conference "Stability and Control Processes" in memory of V.I. Zubov, SCP 2015 (Saint-Petersburg, 2015), 18-th international conference "The 18th International Workshop on Computer Algebra in Scientific Computing", CASC 2016 (Bucharest, Romania, 2016), 12-th international conference "Computer Science and Information Technologies", CSIT 2017 (Yerevan, Armenia, 2017), and at the seminars of Faculty of Applied Mathematics and Control Processes of Saint-Petersburg State University.

Publications. There are 21 published papers on the subject of the work including 12 articles in scientific journals recommended by Higher Attestation Commission of Russian Federation.

Author's personal contribution. The matter of dissertation and main results presented in it highlight the personal contribution of the author to the published works. The articles were prepared together with co-authors but the contribution of the author is the largest. All the presented results are obtained personally by the author.

Structure and length of the work. The dissertation consists of Introduction, four chapters, Conclusion and References containing 187 works. Total length of the is 182 pages.

The work is organized as follows.

In Introduction we make some motivational remarks describing the problems considered in the dissertation, we point out the goal and scientific originality of the study. Also main results proved in the dissertation are presented. Next, a brief sketch of classical and modern results concerning the features of the solutions of the systems of ODE and numerical methods of their calculation is included.

The first chapter of the work is devoted to the localization of the roots of a real polynomial family.

Different practical processes such as population dynamics, price variance, epidemics transmission, the behavior of electromechanical systems, chemical reactions in cells an so on are modelled by systems of nonlinear differential equations. In many

practical applications it is necessary to study certain qualitative global properties of the solutions. In these circumstances, one of the most important questions is a question of robust stability of control system that can be reduced to the analysis of the spectrum of some matrix, i.e., to the localization of the roots of its characteristic polynomial.

With the help of Elimination Theory, the problem of solving simultaneous algebraic equations with several variables can be reduced to the one-dimensional case. This can be done using modern computer algebra systems or Buchberger's algorithm for computing Grobner bases, or multivariate resultant technique. Thus, the problem of analyzing the features of the system under consideration lead to the analogous problem for one algebraic equation depending on one variable. Particularly, in such a way we can define the number of real solutions and solve the problem of localization of the solution (including consideration a certain algebraic region in the real plane or the complex plane). Developing the method suggested by Ch. Hermite a method of constructing a multivariate analogue of Sturm's polynomial system can be represented. In the dissertation this ideology is applied to the problems of stability and D-stability of a family of polynomials with real coefficients.

Consider now the real polynomial f (z, Mi,M2,..., Mk) with coefficients polynomially dependent on parameters Mi,...,Mk. We treat the domain of variations of these parameters to be a real box

B = {(^1,^2, . . . ,Mk)!м1 < Ml < Ml,M2 < M2 < Д2, . . . < Mk < Mk}.

The following problem is solved.

D-stability problem. Find the conditions for every polynomial from the family

p = { f (z,mi,M2,.. .,Mk)! (mi, .. .,Mk) e B} (1.1)

to be D-stable, i.e. all its roots lie in a certain algebraic domain D in the complex plane.

In practical applications, the domain D usually is symmetric about the real axis in the complex plane. We assume that it is defined by the condition g(x, y) < 0, where g(x,y) = G(x,y2) for some polynomial G(x,Y) with real coefficients.

A particular case of this problem that has many applications is a problem of stability of given polynomial family. This problem consists in finding necessary and sufficient conditions for the polynomials of the family (1.1) to have all their zeros in the left half-plane of the complex plane.

For the problem of D-stability, the results of classic algebra such as Elimination Theory (for the systems of algebraic equations depending on two and several variables), theory of differentiable maps are used.

First, more general problem is considered. For a family of polynomials with coefficients polynomially depending on parameters, an algorithm of obtaining necessary and sufficient conditions to have no real roots.

In the dissertation, numerical examples of using the proposed algorithms are presented.

The second chapter of the dissertation is devoted to the problems of localization of matrix eigenvalues. These issues are of great importance for the robust stability of parametrized matrix families where matrix elements polynomially depend on a parameter.

Really, in many cases (especially, when we consider matrices depending on parameters or large matrices) constructing of characteristic polynomial is very difficult and computationally expensive. Therefore effective algorithms are needed to study matrix spectrum without knowing the coefficients of its characteristic polynomial.

In this chapter the following problems are solved:

1) the problem of finding all common eigenvalues of two square complex matrices A = [aij]nj=1 and B = [bijjjAn algorithm to construct a polynomial with roots coinciding to all of the common eigenvalue of these matrices is developed.

2) the problem of finding the size of the largest Jordan block of a square matrix and all the eigenvalues associated with the largest Jordan blocks. An algorithm to

construct a polynomial with roots coinciding to the required eigenvalues is developed. The solution of this problem helps to simplify the computation of Holder condition number that estimates variations of multiple eigenvalues of the matrix.

3) the problem of finding all multiple eigenvalues of a complex matrix with elements polynomially dependent on a parameter. An algorithm to construct a polynomial with roots coinciding to all the values of parameter corresponding to the matrices with multiple eigenvalues.

In this chapter, numerical examples demonstrating the work of all the algorithm proposed are presented.

In the third chapter of the dissertation the applications of linear algebra methods to graph theory problems is considered.

It is known that graph theory provides powerful tools to reflect interactions among network components and their effects that cannot be understood by studying network elements in isolation. Graphs are used for the structure analysis of different complex systems. Methods of graph theory are useful studying theory of multi-agent systems (M.A.S.), switched systems and analyzing any processes that are modelled by means of differential equations on graphs (e.g., processes examined in chemical kinetics, chemical technology, biology and so on). Hence, the graph approach allows us to describe the structure of many complex systems, and here we use linear algebra methods to study graphs.

For this purpose, we consider n-dimensional vector spaces over Galois Field of characteristic 2 (GF(2)), i.e., the sets of vectors of dimension n whose components are 0 or 1 with usual addition followed by reduction modulo 2 and scalar multiplication by 0 and 1. We prove some results in graph theory, such as theorem on graph circuits and cut-sets, consider some specific features of the standard inner product of two vectors, the connection between the problem of line graph recognition and the problem of matrix factorization over GF(2). Also a new matrix algorithm to recognize a line graph and construct its original graph is presented.

There are some examples demonstrating the work of the algorithm proposed.

In the fourth chapter of the dissertation a new effective numerical method to compute a solution of the initial-value problem for the system of non-linear ordinary differential equations is suggested. This method allows us to calculate the solution in the standard floating-point arithmetic with minimum total error (i.e., the sum of the error of the method and rounding errors). It can be used for modelling and simulating of complex systems, particularly, for the biology systems analysis.

For the solution of simultaneous differential equations, there exist several more efficient numerical methods, but the explicit Euler's method is widely used in different models and simulations, e.g, in cell models.

The advantages of this method such as its simple implementation and rapidity of calculations are well-known. In many cases, for instance, in real-time computations (especially considering the systems with large number of equations) these properties of technique in operations are quite important. Besides, the computations are often performed in standard floating-point arithmetic. Therefore the question of accuracy of such computation is very important.

The initial-value problem for the following system of ordinary differential equations is considered

dX

"d7

= F (t,X), X (to) = Xo,

(1.2)

where F = [f(t,X)]m= x is a real vector m x 1 whose elements are given functions,

X (t) =

( u\ \

V

xm (t)

Xo =

/

o

Xi

y Xm J

In the dissertation, an algorithm allowing us to compute a solution of initial-value problem for a system of ordinary differential equations with maximal accuracy (taking into account the rounding errors connected with numerical integration) is proposed. This algorithm makes it possible to choose step size of Euler's method for computations with minimum total error.

In this work, several numerical examples showing the work of the proposed

algorithm are presented. For these examples, the proposed algorithm was compared with known methods (Rosenbrock's classical method, Runge — Kutta's method, Euler's method with constant step size). The examples (including stiff systems and the system with discontinuous right-hand sides) show that the proposed method is faster and more accurate than the other methods.

In Conclusion the main results obtained in the work are presented.

Notations

We use the following notations: . n!

1. Cn = ——,-— — binomial coefficient;

n k!(n - k)!

2. X stands for ^;

dt

3. j = 1,n mean that j takes on all integer values from 1 to n;

4. R — the set of real numbers; C — the set of complex numbers;

5. for a real number x: |_xj stands for the largest integer not greater than x; |"x] stands for the smallest integer not less than x;

sign x — sign function of x;

/

1, x > 0, sign x = 0, x = 0, -1, x < 0;

6. for a complex number x: x stands for the complex-conjugate of x;