Диссертация (1145311)
Текст из файла
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиКАЛИНИНА Елизавета АлександровнаПрименение алгебраических методов дляанализа сложных систем05.13.01 – Системный анализ, управление и обработка информацииДИССЕРТАЦИЯна соискание ученой степенидоктора физико-математических наукНаучный консультантд.
ф.-м. н., проф.Утешев Алексей ЮрьевичСанкт-Петербург – 20162ОглавлениеВведение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Глава 1.5Устойчивость и D-устойчивость семейства веществен-ных полиномов . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . .191.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . .191.2. Необходимые сведения из алгебры и теории дифференцируемыхотображений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .221.2.1.Отделение корней полиномов . . . . . . .
. . . . . . . . .22Теоремы Якоби и Эрмита — Сильвестра . . . . . . . . . .27Результаты Кронекера . . . . . . . . . . . . . . . . . . . .37Безутианта . . . . . . . . . . . . . . . . . . . . . . . . . . .41Параметры Маркова . . . . . . . . . . . . . . . . . . . . .44Теория исключения. Случай двух переменных . . . . . .45Теория исключения.
Случай нескольких переменных . . .47Известные результаты . . . . . . . . . . . . . . . . . . . .55Устойчивость полиномов . . . . . . . . . . . . . . . . . . .78Теория дифференцируемых отображений . . . . . . . . .801.3. Вещественные корни семейства полиномов . . . . . . . . . . . . .811.4. Устойчивость семейства полиномов . . . . . . .
. . . . . . . . . .891.5. D-устойчивость семейства полиномов . . . . . . . . . . . . . . . .921.2.2.1.6. Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103Глава 2.Собственные числа матриц . . . . . . . . . . . . . . . . . . 1042.1. Вспомогательные результаты . . . . .
. . . . . . . . . . . . . . . . 1052.2. Общие собственные числа двух матриц . . . . . . . . . . . . . . . 1092.2.1.Предварительные результаты . . . . . . . . . . . . . . . . 1092.2.2.Алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . 11532.2.3.Пример . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . 1162.3. Число обусловленности Гёльдера . . . . . . . . . . . . . . . . . . 1182.3.1.Предварительные результаты . . . . . . . . . . . . . . . . 1182.3.2.Максимальный порядок клетки Жордана . . . . .
. . . . 1212.3.3.Собственные числа, которым соответствуют максимальные клетки Жордана . . . . . . . . . . . . . . . . . . . . . 1362.3.4.Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1372.4. Кратные собственные числа матрицы . . . . . . . . . . . . . . . . 1392.4.1.Алгоритм . . . . . . . . . .
. . . . . . . . . . . . . . . . . 1422.4.2.Асимптотическая сложность алгоритмаи повышение точности вычислений . . . . . . . . . . . . . 1432.4.3.Глава 3.Численный пример . . . . . . . . . . . . . . . . . . . . . . 145Графы и матрицы . . . . . . . . . . . . . . .
. . . . . . . . . 1483.1. Линейные пространства над полем GF(2) . . . . . . . . . . . . . . 1503.1.1.Теорема о циклах и разрезах . . . . . . . . . . . . . . . . 1643.1.2.Факторизация матрицы над полем GF (2) . . . . . . . . . 1693.2. Графы как линейные отображения . . . . .
. . . . . . . . . . . . 1753.3. Паросочетания и реберные покрытия . . . . . . . . . . . . . . . . 1773.4. Распознавание реберного графа . . . . . . . . . . . . . . . . . . . 1803.4.1.Необходимые сведения из теории графов . . . . . . . . . . 1803.4.2.Описание алгоритма . . . .
. . . . . . . . . . . . . . . . . 1833.4.3.Алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . 1853.4.4.Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1863.4.5.Оценка асимптотической сложности алгоритма . . . . . . 190Глава 4.Метод Эйлера . . . . . . . .
. . . . . . . . . . . . . . . . . . 1924.1. Предварительные результаты. Ошибки округления . . . . . . . . 1934.1.1.Абсолютная и относительная погрешности . . . . . . . . . 1934.1.2.Арифметика с плавающей точкой . . . . . . . . . . . . . . 19544.2. Локально оптимальный шаг метода Эйлера . . . . . . . . . . . . 1994.3.
Реализация метода . . . . . . . . . . . . . . . . . . . . . . . . . . 2054.4. Численные примеры . . . . . . . . . . . . . . . . . . . . . . . . . . 2104.5. Оптимальное число шагов метода Эйлера . . . . . . . . . . . . . 2194.5.1.Вычислительный алгоритм . . . . . . . . . . . .
. . . . . 2264.6. Обсуждение полученных результатов . . . . . . . . . . . . . . . . 235Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238Список литературы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2405ВведениеАктуальность темы исследования. В последние десятилетия в науке наблюдается интенсивное развитие теории сложных систем.
Такие системыиспользуются для моделирования процессов в информатике, биологии, экономике, физике, химии и многих других областях (см., например, книгу [157] истатьи [50, 68, 180]). В настоящее время более 50 институтов и исследовательских центров по всему миру занимаются изучением сложных систем.Основным методом исследования сложных систем является математическое моделирование, при котором процессы функционирования сложной системы формализуются, а затем строится ее математическое описание. Характеристиками такой системы являются ее структура и поведение.
Для описанияструктуры сложной системы и связей между ее элементами применяются графы, а сами эти элементы во многих случаях представляют собой динамическиесистемы.Принципиально важно изучить реакции таких систем на изменения параметров, от которых она зависит. С помощью линейного анализа устойчивостивыясняется, при каких значениях параметров однородное состояние равновесия системы теряет устойчивость и в системе возникают неоднородности (см.,например, [2, 12]).
В диссертационной работе рассматриваются алгебраическиеметоды, позволяющие в некоторых случаях провести данный анализ.При линейном анализе устойчивости появляется необходимость исследовать спектр результирующей матрицы коэффициентов. При этом возникает проблема локализации нулей полинома от одной переменной или полиномиальнойсистемы уравнений относительно нескольких переменных.Для проверки того, что все собственные числа результирующей матрицы лежат в левой полуплоскости комплексной плоскости, к ее характеристическому полиному может быть применен критерий Рауса — Гурвица.
Однаков практических задачах довольно часто требуется проверка выполнения более6сильного условия: необходимо, чтобы все корни характеристического полиноманаходились внутри определенной алгебраической области D комплексной плоскости. Возникает более общая задача D-устойчивости (см., например, [43, 44]).Решением задачи о числе корней полинома в некоторой области комплексной плоскости, известной с первой половины XIX века, занимались такие математики, как Ш. Эрмит, И.
Шур, А. Кон, B. N. Datta, J. Ackermann и R. Muench,Р. Е. Калман [10, 20, 30, 94]. Так, для того, чтобы установить, находятся ли всекорни полинома внутри единичного круга комплексной плоскости, используетсякритерий Шура — Кона [7] (B. N. Datta обобщил критерии Рауса — Гурвица иШура — Кона, используя матрицу безутианты [76]). В случае областей, границами которых являются уникурсальные (вещественно параметризуемые) кривые,можно использовать метод Эрмита (1854) [98]. Р. Е. Калман разработал ещеодин критерий, позволяющий определить, все ли нули полинома лежат в некоторой алгебраической области комплексной плоскости [113].
Известен такжеметод D-разбиения [6], т. е. разбиения на области в пространстве параметров.Однако его применение затруднительно при большом количестве параметров.В пространстве коэффициентов полинома границы областей, соответствующихполиномам с одинаковым числом вещественных корней, задаются дискриминантной поверхностью. При этом каждая точка дискриминантной поверхностисоответствует полиному с кратными корнями.В общем случае проблема сводится к исследованию поведения нулей некоторой системы алгебраических уравнений в зависимости от параметров, которые в ней содержатся.
Численные методы в данном случае малоэффективны,поскольку их применение возможно только при конкретных значениях параметров (см., например, работы Д. Уилкинсона [35]). Возникает необходимость разработки надежных аналитических символьных алгоритмов. Такие алгоритмысуществуют для одномерного случая, и они широко реализованы в современных системах аналитических вычислений (Maple, Mathematica, MatLab и др.),позволяющих манипулировать аналитическими выражениями и производить7вычисления с вещественными числами с мантиссой практически неограниченной длины.
Большинство алгоритмов для алгебраических систем общего видав случае бо́льших размерностей используют алгоритм Б. Бухбергера построения базисов Грёбнера [51, 58], однако его применение часто является весьмазатратным. Так, объем памяти, требуемый для его работы, в общем случае экспоненциально зависит от числа переменных. Кроме того, для систем общеговида не получено оценок времени работы алгоритма.Поскольку нахождение характеристического полинома матрицы само посебе достаточно сложно, то возникает необходимость исследования поведениясобственных чисел матрицы в тех случаях, когда построение каноническогопредставления ее характеристического полинома вычислительно затратно.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
