Содержание к диссертации
Введение
Глава 1. Устойчивость и D-устойчивость семейства вещественных полиномов 19
1.1. Постановка задачи 19
1.2. Необходимые сведения из алгебры и теории дифференцируемых отображений 22
1.2.1. Отделение корней полиномов 22
Теоремы Якоби и Эрмита — Сильвестра 27
Результаты Кронекера 37
Безутианта 41
Параметры Маркова 44
Теория исключения. Случай двух переменных 45
Теория исключения. Случай нескольких переменных 47
Известные результаты 55
Устойчивость полиномов 78
1.2.2. Теория дифференцируемых отображений 80
1.3. Вещественные корни семейства полиномов 81
1.4. Устойчивость семейства полиномов 89
1.5. D-устойчивость семейства полиномов 92
1.6. Заключение 103
Глава 2. Собственные числа матриц 104
2.1. Вспомогательные результаты 105
2.2. Общие собственные числа двух матриц
2.2.1. Предварительные результаты 109
2.2.2. Алгоритм 115
2.2.3. Пример 116
2.3. Число обусловленности Гёльдера 118
2.3.1. Предварительные результаты 118
2.3.2. Максимальный порядок клетки Жордана 121
2.3.3. Собственные числа, которым соответствуют максимальные клетки Жордана 136
2.3.4. Пример 137
2.4. Кратные собственные числа матрицы 139
2.4.1. Алгоритм 142
2.4.2. Асимптотическая сложность алгоритма и повышение точности вычислений 143
2.4.3. Численный пример 145
Глава 3. Графы и матрицы 148
3.1. Линейные пространства над полем GF(2) 150
3.1.1. Теорема о циклах и разрезах 164
3.1.2. Факторизация матрицы над полем GF(2)
3.2. Графы как линейные отображения 175
3.3. Паросочетания и реберные покрытия 177
3.4. Распознавание реберного графа
3.4.1. Необходимые сведения из теории графов 180
3.4.2. Описание алгоритма 183
3.4.3. Алгоритм 185
3.4.4. Примеры 186
3.4.5. Оценка асимптотической сложности алгоритма 190
Глава 4. Метод Эйлера 192
4.1. Предварительные результаты. Ошибки округления 193
4.1.1. Абсолютная и относительная погрешности 193
4.1.2. Арифметика с плавающей точкой 195
4.2. Локально оптимальный шаг метода Эйлера 199
4.3. Реализация метода 205
4.4. Численные примеры 210
4.5. Оптимальное число шагов метода Эйлера 219
4.5.1. Вычислительный алгоритм 226
4.6. Обсуждение полученных результатов 235
Заключение 238
Список литературы
- Теория исключения. Случай нескольких переменных
- Предварительные результаты
- Графы как линейные отображения
- Локально оптимальный шаг метода Эйлера
Введение к работе
Актуальность темы исследования. В последние десятилетия в науке наблюдается интенсивное развитие теории сложных систем. Понятие сложной системы используется в информатике, биологии, экономике, физике, химии и многих других областях (см. книгу H. Sayama, статьи Y. Bar-Yam, G. Chapouthier, J. M. Zayed и др.) В настоящее время более 50 институтов и исследовательских центров по всему миру занимаются изучением сложных систем.
Основным методом исследования сложных систем является математическое моделирование, при котором процессы функционирования сложной системы формализуются, а затем строится ее математическое описание. Характеристиками такой системы являются ее структура и поведение. Для описания структуры сложной системы и связей между ее элементами применяются графы, а сами эти элементы во многих случаях представляют собой динамические системы.
Принципиально важно изучить реакции таких систем на изменения параметров, от которых она зависит. С помощью линейного анализа устойчивости выясняется, при каких значениях параметров однородное состояние равновесия системы теряет устойчивость и в системе возникают неоднородности. В диссертационной работе рассматриваются алгебраические методы, позволяющие в некоторых случаях провести данный анализ.
При линейном анализе устойчивости появляется необходимость исследования спектра результирующей матрицы коэффициентов. При этом возникает проблема локализации нулей полинома от одной переменной или полиномиальной системы уравнений относительно нескольких переменных.
Для проверки того, что все собственные числа результирующей матрицы лежат в левой полуплоскости комплексной плоскости, к ее характеристическому полиному может быть применен критерий Рауса — Гурвица. Однако в практических задачах довольно часто требуется проверка выполнения более
сильного условия: необходимо, чтобы все корни характеристического полинома находились внутри определенной алгебраической области D комплексной плоскости. Возникает более общая задача D-устойчивости.
Решением задачи о числе корней полинома в некоторой области комплексной плоскости, известной с первой половины XIX века, занимались такие математики, как Ш. Эрмит, И. Шур, А. Кон, B. N. Datta, J. Ackermann и R. Muench, Р. Е. Калман. Так, для того, чтобы установить, находятся ли все корни полинома внутри единичного круга комплексной плоскости, используется критерий Шура — Кона (B. N. Datta обобщил критерии Рауса — Гурвица и Шура — Кона, используя матрицу безутианты). В случае областей, границами которых являются уникурсальные (вещественно параметризуемые) кривые, можно использовать метод Эрмита (1854). Р. Е. Калман разработал еще один критерий, позволяющий определить, все ли нули полинома лежат в некоторой алгебраической области комплексной плоскости. Известен также метод D-разбиения, т. е. разбиения на области в пространстве параметров. Однако его применение затруднительно при большом количестве параметров. В пространстве коэффициентов полинома границы областей, соответствующих полиномам с одинаковым числом вещественных корней, задаются дискриминантной поверхностью. При этом каждая точка дискриминантной поверхности соответствует полиному с кратными корнями.
В общем случае проблема сводится к исследованию поведения нулей некоторой системы алгебраических уравнений в зависимости от параметров. Численные методы в данном случае малоэффективны, поскольку их применение возможно только при конкретных значениях параметров (см., например, работы Д. Уилкинсона). Возникает необходимость разработки надежных аналитических символьных алгоритмов. Такие алгоритмы существуют для одномерного случая, и они широко реализованы в современных системах аналитических вычислений (Maple, Mathematica, MatLab и др.), позволяющих манипулировать аналитическими выражениями и производить вычисления с вещественными
числами с мантиссой практически неограниченной длины. Большинство алгоритмов для алгебраических систем общего вида в случае больших размерностей используют алгоритм Б. Бухбергера построения базисов Грёбнера, однако его применение часто является весьма затратным. Так, объем памяти, требуемый для его работы, в общем случае экспоненциально зависит от числа переменных. Кроме того, для систем общего вида не получено оценок времени работы алгоритма. Применение методов теории исключения позволяет разработать конструктивные реализуемые на ЭВМ алгоритмы локализации нулей системы алгебраических уравнений.
Поскольку построение канонического представления характеристического полинома матрицы большого порядка само по себе достаточно сложно, то возникает необходимость исследования поведения собственных чисел матрицы без нахождения ее характеристического полинома. Тем самым задача о локализации собственных значений матрицы является обобщением задачи локализации корней полинома. В последнее время довольно большое внимание привлекают задачи, связанные с существованием кратных собственных чисел матрицы, например, при определении структуры жордановой нормальной формы матрицы в зависимости от параметров. Такие задачи встречаются в физике (в том числе в квантовой механике и ядерной физике), оптике, электротехнике. Рассматриваются как малые возмущения матриц (см. работы J. V. Burke, A. S. Lewis и M. Overton, M. Karow, D. Kressner, M. J. Pelaez, и J. Moro, J. Sun), так и значения параметра, которые не являются малыми (работы E. Jarlebring, S. Kvaal, W. Michiels, А. А. Майлыбаева, A. Muhic и B. Plestenjak).
Процессы, встречающиеся в различных приложениях (в химической кинетике, химической технологии, биологии), марковские процессы описываются дифференциальными уравнениями на графах. Тем самым при анализе сложных систем используются свойства графов (см. работы А. И. Вольперта, J. Maidens, D. Siegel и D. MacLean, С. Л. Подвального и В. В. Провоторова, книгу Д. Д. Ши-льяка и др.). Графы применяются в теории многоагентных систем (МАС),
изучение которых связано с решением практических задач в сфере сетевых и мобильных технологий, в логистике, в графике, геоинформационных системах (см. работы N. Monshizadeh, Shuo Zhang, и M. Kanat Camlibel, K.-K. Oh, K. L. Moore и H.-S.K. Ahn, J. Wang, Z. Liu и X. Hu) и при исследовании систем с переключениями (M. Delgado и H. Sira-Ramirez, M. Poyraz, Y. Demir, A. Gulten и M. Koksal, W. Borutzky, G. Dauphin-Tanguy, и J.U. Thoma). К исследованию графов применимы алгебраические методы. Так, известны теоремы, связывающие спектральные свойства матрицы смежности с другими свойствами графа (см. книгу N. Biggs), неравенство Чигера, позволяющее оценить наименьший разрез графа посредством второго собственного значения матрицы Кирхгофа, теоремы, связывающие диаметр графа и собственные числа, полученные с помощью линейной алгебры. Стоит отметить, что задача об изоморфизме графов может быть также сформулирована как линейно-алгебраическая задача. Во многих случаях решение задач теории графов упрощается, если известно, что граф является реберным (например, задача поиска максимального независимого множества). Поэтому разработка эффективных алгоритмов распознавания реберного графа и построения его корневого графа остается актуальной, несмотря на существование нескольких таких алгоритмов (Ph. G. H. Lehot, N. D. Roussopoulos, D. G. Degiorgi и K. Simon, D. Liu, S. Trajanovski и P. Van Mieghem).
При моделировании и симуляции биологических систем анализ может проводиться с помощью численного интегрирования систем обыкновенных дифференциальных уравнений. Во многих случаях для решения систем ОДУ, описывающих работу ионных каналов клеточных мембран, используется явный метод Эйлера (см. работы C. P. Fall и J. Rinzel, T. Korhonen и P. Tavi, J. Sneyd и J.-F. Dufour, K.H.W.J. Ten Tusscher и др.). В режиме реального времени при одновременном проведении экспериментов каждый шаг вычислений должен быть выполнен за ограниченное время. При очень большом числе уравнений в каждый момент времени необходимо сделать огромное количество вычислений. Поэтому необходимы численные методы, позволяющие найти решение задачи Ко-
ши с минимальной возможной погрешностью (с учетом ошибок округления, возникающих при выполнении арифметических операций в реальной арифметике с плавающей точкой, которая используется при вычислении на компьютере), для чего уместным оказывается применение алгебраического подхода.
Цель диссертационной работы заключается в разработке конструктивных алгебраических методов и алгоритмов, применимых для анализа сложных систем и в применении этих алгоритмов к конкретным задачам, требующим исследования динамики и устойчивости таких систем.
Основные положения, выносимые на защиту: 1. Разработанный для исследования линейной устойчивости сложных систем конструктивный алгоритм проверки устойчивости и D-устойчивости семейства вещественных полиномов с коэффициентами, полиномиально зависящими от параметров.
-
Разработанный для анализа мультикомпонентных систем алгоритм нахождения общих собственных чисел набора матриц, составляющих систему.
-
Применимый для исследования динамики зависящих от параметра сложных систем, изучаемых в физике, оптике, электротехнике, алгоритм определения структуры жордановой нормальной формы матрицы с комплексными элементами.
-
Матричный алгоритм распознавания реберного графа, позволяющий упростить описание структуры и исследование свойств систем с переключениями и многоагентных систем.
-
Применимый для имитационного моделирования биологических систем, в том числе и в режиме реального времени, эффективный алгоритм численного интегрирования систем ОДУ, позволяющий получить максимально точное решение задачи Коши в арифметике с плавающей точкой.
Научная новизна. Выносимые на защиту результаты являются новыми и получены лично автором.
Теоретическая и практическая ценность. Результаты, изложенные в диссертации, позволяют упростить анализ устойчивости и D-устойчивости
сложных систем, а также получить максимально точные решения этих систем в арифметике с плавающей точкой в режиме реального времени.
Предложенные алгоритмы являются достоверными и эффективными, что позволяет использовать их в механике, теории управления, биофизике и химической кинетике. Простота и вычислительная эффективность позволяют в ряде случаев применять их для моделирования процессов в сложных системах в реальном времени.
Практическая ценность результатов диссертации состоит в том, что при моделировании и анализе сложных систем они позволяют:
-
повысить достоверность и точность выполняемых расчетов,
-
сократить время вычислений,
-
проанализировать свойства системы в зависимости от параметров.
Методы исследования. В диссертационной работе используются методы системного анализа, классической высшей алгебры (теория исключения, теория ганкелевых квадратичных форм), теории дифференцируемых отображений и алгебраической теории графов, оценка погрешностей в арифметике с плавающей точкой.
Результаты исследований прошли апробацию на следующих конференциях: 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 Scientifc Computing”, CASC 2016 (г. Бухарест, Румыния, 2016), а также на семинарах факультета прикладной математики — процессов управления Санкт-Петербургского государственного университета.
Публикации. По теме диссертационной работы опубликовано 20 печатных работ, в том числе 12 статей в журналах, рекомендованных ВАК РФ.
Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Подготовка к публикации полученных результатов проводилась совместно с соавторами, причем вклад диссертанта был определяющим. Все представленные в диссертации результаты получены лично автором.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и библиографического списка, включающего 182 наименования. Общий объем работы составляет 257 страниц.
Теория исключения. Случай нескольких переменных
Частным случаем данной задачи, имеющим довольно много практических приложений, является задача об устойчивости данного семейства полиномов. Она состоит в нахождениии необходимых и достаточных условий того, что нули всех полиномов семейства (1.1) лежат в левой полуплоскости комплексной плоскости.
Для решения задачи D-устойчивости используются результаты классической высшей алгебры: теория исключения переменных (для систем нелинейных уравнений относительно двух и нескольких переменных), условия устойчивости семейства полиномов с коэффициентами, непрерывно зависящими от параметров, теория ганкелевых квадратичных форм, а также теория дифференцируемых отображений.
Для решения поставленной задачи в диссертации рассматривается более общая задача. Приводится алгоритм построения необходимых и достаточных условий, при которых семейство полиномов с вещественными коэффициентами, полиномиально зависящими от параметров, не имеет вещественных корней.
В работе приведены численные примеры, иллюстрирующие работу предложенных алгоритмов.
Вторая глава диссертационной работы посвящена вопросам отделения собственных чисел матрицы, которые также имеют большое значение в исследовании устойчивости сложных систем.
Действительно, во многих случаях (особенно тогда, когда элементы матрицы зависят от параметров), построение характеристического полинома является довольно сложной и вычислительно затратной задачей. Поэтому требуются эффективные алгоритмы, позволяющие исследовать спектр матрицы, не вычисляя коэффициентов ее характеристического полинома.
В этой главе диссертации решаются следующие задачи: 1) задача нахождения всех общих собственных чисел двух квадратных матриц А = [dij\1ij=i и В = [&y]?-=i с комплексными элементами. Предложен алгоритм, который позволяет построить полином, корнями которого являются общие собственные числа данных матриц. 2) задача нахождения максимального порядка клетки Жордана квадратной матрицы и всех собственных чисел этой матрицы, которым соответствуют клетки Жордана максимального порядка. Решение данной задачи позволяет упростить вычисление числа обусловленности Гёльдера, которое является мерой изменения кратных собственных чисел матрицы. 3) задача нахождения кратных собственных чисел матрицы, элементы которой полиномиально зависят от параметра. Предложенный алгоритм позволяет построить полином, корнями которого являются все значения параметра, при которых данная матрица имеет кратные собственные числа. Работа всех предложенных в работе алгоритмов показана на численных примерах. В третьей главе диссертационной работы рассматриваются некоторые задачи теории графов и их решение с помощью методов линейной алгебры.
Для структурного анализа сложных систем применяют методы теории графов. Графы используются в теории многоагентных систем (МАС), при исследовании систем с переключениями, а также при анализе любых процессов, которые моделируются дифференциальными уравнениями на графах (например, процессы, которые изучает химическая кинетика, химическая технология, биология и др.). Тем самым для анализа сложных систем требуется изучение графов, для исследования свойств которых применимы алгебраические методы.
С этой целью рассмотрены линейные пространства над полем вычетов по модулю 2. Вводятся понятия 1-зависимости системы (0, 1)-векторов и минимальной 1-зависимой системы. Предложен конструктивный метод разложения 1-зависимой системы векторов на минимальные 1-зависимые подсистемы. Также рассмотрена связь фундаментальной системы решений однородной системы линейных уравнений с единственностью разбиения столбцов матрицы A системы уравнений на 1-зависимые минимальные подсистемы.
Кроме того, показано, как связаны задачи распознавания реберного графа и факторизации матрицы, а также приводится новый матричный алгоритм распознавания реберного графа, построенный с помощью линейно-алгебраического подхода. Приводятся примеры, показывающие работу алгоритма.
В четвертой главе диссертационной работы предлагается эффективный численный алгоритм, позволяющий в арифметике с плавающей точкой построить решение задачи Коши для системы нелинейных дифференциальных уравнений, имеющее наименьшую полную погрешность (сумму погрешности метода и ошибок округления). Данный метод может применяться при имитационном моделировании сложных систем, в частности, для анализа биологических систем.
Для численного решения систем обыкновенных дифференциальных уравнений существуют и более эффективные методы, чем метод Эйлера. Однако явный метод Эйлера часто используется в задачах моделирования и симуляции биологических систем. Так, обычно с помощью обыкновенных дифференциальных уравнений описывается работа ионных каналов клеточных мембран. Преимущества явного метода Эйлера интегрирования систем дифференциальных уравнений хорошо известны: это его простая реализация и скорость. В некоторых случаях, например, при расчете в режиме реального времени (особенно для систем с большим количеством уравнений) эти особенности метода интегрирования очень важны. Кроме того, часто вычисления производятся в стандартной процессорной арифметике с плавающей точкой. Поэтому вопрос точности метода Эйлера при таких вычислениях довольно важен.
Предварительные результаты
В случае, когда в данном ряду встречаются несколько подряд идущих нулей, можно воспользоваться правилом Кронекера — Хатендорфа: 1 nrr \j\x) = 0 а х Ь\ = - {sign {Hk-\{b)Hk\b)) — sign {Hk-\{a)Hk{a))\. k=i Таким образом, система полиномов {Hi(t)}ri=l играет роль системы полиномов Штурма для полинома f(x). В отличие от классической системы полиномов Штурма, построенной с помощью алгоритма Евклида, здесь степени полиномов Hi(t) возрастают при возрастании . Нахождение определителей Hj(t) является вычислительно затратным. Однако существует рекуррентное соотношение, связывающее три последовательных определителя Hk-2{t),Hk-\{t) и Hk(t) [171], которое позволяет упростить вычисления. Следующая теорема принадлежит Якоби и Йоахимшталю. Теорема 9. Любые три последовательных ганкелевых полинома связаны следующим равенством )(Hi_2{t) + ($)thi-i7i — S)i-ihii — $)e$)e_it)He_i(t) + S)i_iHi(t) = 0. (1.14) Соотношение (1.14) может быть переписано (t) = hf-ifit + hf-i t + ... + he-ij-в более симметричной форме: Следствие 4. Если $)ц Ф 0,із -і ф 0, то равенство (1.14) может быть записано следующим образом: Hi_2\t) — t 1 He_i{t) -\ tti{t) = 0. (1.15) Равенство (1.14) позволяет получить рекурсивный способ нахождения ган-келевых полиномов Hi(t). В самом деле, предположим, что выражения для Hi_2{t) и Hi_i(t) найдены, причем Hi_ii, где hf-ifi = S)i-\.
Тогда в формуле (1.14) известны все постоянные члены за исключением Sje и ha, для которых имеются только их представления в виде определителей s2 s3 so Si Si S2 so Si $—2 S Si S2 $—1 s +i S —2 S —1 $2—4 S2 —2 S —1 se . $2—3 $2— S— 1 Si ftt и ha = $—2 $—1 $ ... S i—3 S —1 Si Sf-\-\ . . . S i—2 Данные определители отличаются от транспонированного определителя, представляющего Hi(t), только последними столбцами. Раскладывая их по элементам последнего столбца, получаем одни и те же множители, равные алгебраическим дополнениям этих элементов, и, соответственно, следующие формулы: IL&) %} S—liL—l,—l г —1,—2 г г S i—2 —1,0? ГЬЦ — \$ —1,—1 г Sl-\-\ill—\ l—2 г г S2—\ib—\fi), (1.16) которые позволяют найти hgo и ha по известным коэффициентам Hi_\{t). Однако приведенный рекурсивный алгоритм вычисления Hi(t) не работает в случае, когда fie-i = 0. В этом случае применим модифицированный алгоритм [171]. Теорема 10. Пусть Пц-ч ф 0, Пц-\ = 0. Если /і _ід = 0, то Hi_i(t) = и ТТ J2 ТТ / I2(t) = H_2\t). и—2 Если h(-\ i 0, то ТТ Л -1Д ТТ Л fi He_i{t) = Hi_2\t) 2 и и2 0 S)i hi{t) = W" j—2 ij—l,lfl—3\t) fi —2,1 "0—2 v iLil iL—2,2 l —2,l и—2 2 t2 t 1 0 2 Тем самым, для нахождения ганкелева полинома Hi(t) нет необходимости вычислять определитель. Этот полином можно построить, если известны ганкелевы полиномы Hi_\{t) и H it).
Наряду с полиномом f(z) рассмотрим полином g(z) = bozm + b\zm + + bm (6j GK,j = 0,l,...,m;&o 0). Предположим, что полиномы f(z) и g(z) не имеют общих корней (т. е. 7Z(f\g) 0). Построим ганкелеву квадратичную форму п—1 H{Y,Y) = 2 j к=о з+кУзУк п—Ъ T = Y т L"n—\ Y = Y [tj-\-k] Q Y = Y TCY, Т"п—\ Т"п Т 2п—2 где tp = boSp+m + bisp+m-i Н h bmsp, Sj — сумма Ньютона полинома f(z). Замечание 3. [173] ТС = "m "m—1 "О U U О 6ТО . . . &1 6о ... О U U ... Ото Qm—\ ... OQ So Si Sn—1 Si 52 Sn $п—1 Sn S ln— l Sn Sn+1 . . . $2п— Sn+m—1 Sn+m 2n+m—2 (В первой матрице n строк). Теорема Эрмита — Сильвестра позволяет найти число вещественных корней полинома, удовлетворяющих алгебраическому неравенству: Теорема 11. Уравнение f(z) = О имеет п+(ТС) — q различных вещественных корней таких, что g(Xj) 0 и ri-(7i) — q вещественных корней таких, что g{\j) 0. Здесь q — число различных пар комплексно-сопряженных корней уравнения f(z) = 0. Следующий результат [173] может быть полезен в вычислениях, использующих теоремы 7 и 11 Теорема 12. а) Sn = detS = V(f)/aln 2; б) Имеем Нп = det ТС = 4f,9Wf) a 2п-\-т—2 0 Для определения числа вещественных корней полинома f(z), удовлетворяющих неравенствам G1(z) 0, G2(z) 0, . . . , Gk(z) 0. при выполнении условий R(gj,f) = 0 (j = 1,k) справедлива следующая формула [134]: Теорема 13. nrr {/ = 0Gi 0,..., Gk 0} =;—г (1 — 2 )nrr j / = 0\ + nrr\f= OG,, (H 1 Л + nrr {/ = 0\Gj1Gj2 0} (1.17) l jl J2 & + nrr {/ = OlG G Gjg 0} l jl J2 J3 k + + nrr {/ = 0GiG2... Gk 0}] Каждое слагаемое в правой части равенства (1.17) мы можем вычислить, используя теорему 11. Результаты Кронекера В этом параграфе мы покажем, как решаются задачи теории исключения с использованием параметров Маркова. Часто бывает удобнее использовать именно параметры Маркова, поскольку это позволяет понизить размерность рассматриваемых определителей.
Графы как линейные отображения
Рассмотрим матрицу М(Л), элементы которой полиномиально зависят от параметра Л, или Л-матрицу. Пусть ее ранг равен г. Обозначим через Dj(X) (j = 1, 2,..., г) наибольший общий делитель всех миноров порядка j матрицы М(Л).
Справедлива следующая теорема [7]. Теорема 38. В ряду Do (А) = 1, Di(A),..., Dr_i(A), Dr(X) каждый многочлен делится без остатка на предыдущий. 106 Обозначим полученные в результате этого деления частные через Еім( ), 2м(А), ..., Егм{ ) Di(X) (А) Рассмотрим две квадратные матрицы А = [йу]"-=1 и В = [&jj]?-=i с комплексными элементами. В дальнейшем важную роль будет играть определение кронекеровского произведения двух квадратных матриц Апхп и Втхт. Определение 18. Кронекеровским произведением матриц А и В называется матрица а\\В ауїВ ... а\пВ CL2\B CL22B ... а,2ПВ [А В]птхпт = ап\В аП2-В ... а-ппВ Нам понадобится следующие свойства кронекеровского произведения матриц [104]: Sp (А S В) = SpA-SpB (2-2) (A B)(C D) = (AC) S (BD). (2-3) Обозначим через CAB следующую квадратную матрицу порядка тп: CAB = А Етт — Епп В. 107 Здесь Етхт и Епхп — единичные матрицы порядков тип соответственно. В случае, когда В = А, получаем матрицу СА СА = А Е — Е А. (2.4) Здесь Е — единичная матрица того же порядка, что и матрица А (размерности п х п). Известны следующие теоремы [128], связывающие собственные числа матриц А и В и нулевые собственные числа матрицы CAB: Теорема 39. Матрицы А и В имеют хотя бы одно общее собственное число тогда и только тогда, когда det CAB = 0. Теорема 40. Собственные числа матрицы CAB равны Xj— ik, где j = 1, 2,..., п, к = 1, 2,... ,ш. Следствие. Собственные числа матрицы СА равны Aj — \j, где i,j = 1, 2,... ,n.
Следствие. Матрица А имеет кратные собственные числа тогда и только тогда, когда кратность собственного числа 0 больше, чем п. Матрица А не имеет кратных собственных чисел тогда и только тогда, когда кратность ее собственного числа 0 равна п.
Далее мы будем предполагать, что матрицы Аи В имеют по крайней мере одно общее собственное число. Рассмотрим собственные векторы матрицы CAB, соответствующие собственному числу 0. Каждый из этих векторов имеет тп компонент. Если его координаты разбить на т частей, в каждой из которых п компонент, и последовательно поставить по столбцам, то получится матрица X размерности п х т, удовлетворяющая уравнению АХ = ХВ.
Данное уравнение было исследовано Ф. Чечиони [65] и Ф.Г. Фробениу-сом [88]. Известны следующие теоремы [128]: Число линейно независимых решений уравнения АХ = ХВ равно ejk, где ejk — степень наибольшего общего делителя инвариантного множителя EJA(\) матрицы А — ХЕ и инвариантного множителя в(Л) матрицы В — ХЕ. Замечание 13. Сумма берется по всем парам инвариантных множителей EJA{X) и Екв{ Х) (j = 1, 2,..., п, к = 1,2,..., т).
Теперь наряду с матрицей А рассмотрим возмущенную матрицу А + єВ, где В — произвольная матрица, а є — число, достаточно близкое к нулю. Известно [138], что каждое собственное число и каждый собственный вектор возмущенной матрицы допускают разложение по дробным степеням параметра є, в котором коэффициент при є в нулевой степени есть соответственно собственное число или собственный вектор невозмущенной матрицы А.
Важную роль в исследовании спектра возмущенных матриц играют теоремы, опубликованные В. Б. Лидским в 1966 г. [23]. В статье [138] приведены точные формулы для старших членов в разложении собственных чисел и собственных векторов возмущенной матрицы по степеням параметра є. Для анализа собственных чисел возмущенной матрицы используется число обусловленности Гёльдера [66, 138].
Локально оптимальный шаг метода Эйлера
Алгебраический подход позволяет получить многие теоретические и практические результаты теории графов. Идея приложения методов линейной алгебры к задачам теории графов была предложена в книге [81]. Мы рассматриваем особенности линейных пространств над полем Галуа характеристики 2. Эти особенности важны для исследования графов методами линейной алгебры. Также мы вводим линейные отображения, связанные с каждым обыкновенным связным графом с n вершинами и исследуем свойства матриц этих отображений. Данный подход позволяет получить новые, более простые доказательства некоторых известных теорем теории графов, получить некоторые результаты для реберных покрытий и независимых множеств, а также разработать новый матричный алгоритм распознавания реберного графа и построения его корневого графа.
Проблема построения максимального паросочетания имеет различные приложения к задаче о назначениях и планированию при выполнении задач. Индекс Хосойи [101], который определяется через независимые множества, используется в разработках вычислительной химии и математической химии для органических соединений. Существуют также приложения задачи о независимых множествах в вычислительной линейной алгебре (см., например, статьи [83, 149, 153]). Таким образом, изучение реберных покрытий и паросочетаний представляет как теоретический, так и практический интерес. Известно достаточно много алгоритмов, позволяющих построить максимальное паросочетание или решить связанную с данной задачей проблему построения наименьшего реберного покрытия (например, [74, 84, 139, 142]).
В диссертации приводится новое доказательство известной теоремы о наименьшем реберном покрытии и наибольшем паросочетании (теорема 64) и доказывается новая теорема 63.
Еще одна задача, которая рассматривается в диссертации, — задача о распознавании реберного графа. Эта проблема важна, поскольку некоторые практические задачи теории графов для реберных графов решаются значительно проще [78]. Имеется несколько различных алгоритмов распознавания реберного графа [78, 124, 127, 155], причем алгоритм, предложенный в статье [127] разработан совсем недавно. В статье [127] приводится обзор существующих алгоритмов. Так, алгоритм Roussopoulos основан на следующей теореме: граф является реберным тогда и только тогда, когда можно разбить его на клики так, чтобы каждая вершина принадлежала не более чем двум кликам и любые две клики имели не более одной общей вершины. Алгоритм Lehot использует следующий принцип: граф является реберным тогда и только тогда, когда он не содержит полного двудольного графа K1,3 в качестве порожденного подграфа, и если любые два нечетных треугольника имеют общее ребро, то подграф, порожденный их вершинами, является полным графом K4. Динамический алгоритм, представленный в [78], основан на модификации конструктивного доказательства Оре теоремы Уитни о том, что если два связных графа на четырех и более вершинах реберно изоморфны, то существует ровно один вершинный изоморфизм, который порождает данный реберный изоморфизм. Данный алгоритм позволяет за линейное время проверить, сохраняет ли добавление или удаление врешины или ребра свойство реберности или нет. Представленный в диссертации алгоритм использует разбиение графа на клики аналогично алгоритму Roussopoulos. Он, как и алгоритм Degiorgi и Simon, позволяет во многих случаях не перестраивать всю матрицу корневого графа при добавлении или удалении вершин или ребер рассматриваемого графа. Это может сократить время работы алгоритма, особенно для разреженных матриц.
В диссертации представлен линейно алгебраический подход к решению данной задачи. Предлагается достаточно простой алгоритм ее решения, который легко программируется. Используются только матрицы, связанные с данным графом.
Линейная алгебра изучает среди прочего общие свойства векторных пространств над произвольными полями. Необходимость отдельного изучения векторных пространств над полем Галуа характеристики два продиктована широким использованием этих пространств в теории обыкновенных графов [32, 34, 80], теории кодирования [72, 160], математической логике [11] и других областях знания [22, 75]. Приведем здесь результаты, представленные в работе [18].
Поскольку мы собираемся ограничиться n-мерными (n конечно и произвольно) пространствами над полем вычетов по модулю два, то можем рассматривать только одно изоморфное им всем n-мерное координатное пространство, т. е. пространство упорядоченных наборов из n элементов (координат), каждый из которых может принимать только два значения: 0 или 1.
Так как упорядоченные наборы из одного и того же числа элементов легче всего представлять себе в виде строк или столбцов, то в дальнейшем будем называть такие наборы столбцами или строками. А поскольку элементами столбцов (строк) будут только 0 или 1, то будем называть их (0, 1)-столбцами или (0, 1)-строками. Мы будем чаще употреблять в качестве названия такого упорядоченного набора обозначение (0, 1)-столбец (координатный столбец). Поле вычетов по модулю два будем, как принято, обозначать через GF(2), а элементы поля GF(2) 0 или 1 называть числами.
Очевидно, что множество (0, 1)-столбцов из n элементов (что будем подразумевать в дальнейшем, не оговаривая специально) относительно операции сложения столбцов и умножения столбцов на числа из GF(2) (частный случай сложения матриц и умножения матриц на числа) образует векторное пространство. Будем обозначать его через V. Очевидно также, что размерность этого пространства равна п. Столбцы n-мерного пространства будем иногда называть n-столбцами. Базисом пространства n-столбцов, если не оговорено противное, будем считать столбцы единичной матрицы порядка п. Отметим, что элементы любого векторного пространства называются векторами. Потому для (0,1)-столбцов часто будем использовать также термин “вектор”, подчеркивая тем самым, что мы рассматриваем (0,1)-столбец как элемент векторного пространства.