Автореферат (1145310), страница 4

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

Текст из файла (страница 4)

0 ... Sk2 −k Sk2 −k−2 Sk2 −k−4 . . . S2 = 0.(12)(k 2 −k)/2×(k 2 −k)/2Здесь через Sp обозначен след p-й степени матрицы CD (CD = D ⊗ E − E ⊗ D).Этот алгоритм позволяет построить полином, корнями которого являютсявсе значения параметра λ, при которых матрица D имеет кратные собственныечисла.Алгоритм допускает обобщение на случай матрицы D(λ), элементы которой являются полиномами от λ степени выше первой, т.

е. матричного полиномаD(λ) = A0 λm + A1 λm−1 + . . . + Am ,где Aj j = 0, 1, . . . , m — квадратная матрица k-го порядка с комплекснымиэлементами.В третьей главе диссертационной работы рассмотрены задачи теорииграфов, решение которых позволяет упростить структурный анализ сложныхсистем. Графы используются в теории многоагентных систем (МАС), при исследовании систем с переключениями, а также при анализе любых процессов, которые моделируются дифференциальными уравнениями на графах (например,19процессы, которые изучают химическая кинетика, химическая технология, биология и др.). Во многих случаях для исследования свойств графов применимыалгебраические методы.Параграф 3.1 посвящен изучению особенностей линейных пространств надполем Галуа характеристики 2.

Вводятся понятия 1-зависимости системы (0, 1)векторов и минимальной 1-зависимой системы, необходимые для исследованиясвойств графов:Определение. Система ненулевых (0, 1)-столбцов A1 , A2 , . . . , Am , для коmXторой выполняется условиеAi = 0 называется 1-зависимой (все коэффициi=1енты линейной зависимости равны 1).Если 1-зависимая система (0, 1)-столбцов A1 , A2 , . . . , Am не содержит 1-зависимой подсистемы, отличной от самой системы, то она называется минимальной 1-зависимой системой (0,1)-столбцов.Доказана теорема:Теорема55.1-зависимаясистемаразличных(0, 1)-столбцовA1 , A2 , . .

. , Am m > 2 либо является минимальной 1-зависимой системой, либо разбивается на непересекающиеся минимальные 1-зависимые подсистемы.Предложен конструктивный метод разложения 1-зависимой системы векторов на минимальные 1-зависимые подсистемы.Также рассмотрена однородная система линейных уравнений AX = 0.В случае, когда столбцы матрицы A 1-зависимы, данная система уравненийимеет решение X = I, где I — столбец из единиц.

В этом случае столбцыматрицы A разбиваются на минимальные 1-зависимые подсистемы столбцов:A1 , A2 , . . . , Ak . Тогда существует такая матрица перестановки P , что AP =(A1 , A2 , . . . , Ak ) = Ã. Поскольку AX = (AP )(P T X) = ÃY , то вместо системы уравнений AX = 0 можно рассматривать эквивалентную ей системуÃY = 0.

Причем система уравнений ÃY = 0 также допускает решение Y = I,так как P T I = I. Решение Y = I может быть представлено в виде I T =20(I1T , I2T , . . . , IkT ), где Aj Ij = 0 (j = 1, 2, . . . , k; Ij — столбец соответствующей размерности, состоящий из единиц). Если ввести столбцы Y1 = (I1T , 0T2 , . . . , 0Tk )T ,Y2 = (0T1 , I2T , .

. . , 0Tk )T , . . . , Yk = (0T1 , . . . , 0Tk−1 , IkT )T , то столбцы Y1 , Y2 , . . . , Ykбудут решениями системы уравнений ÃY = 0, так как ÃYj = Aj Yj = 0.В работе доказана следующая теорема:Теорема 57. Пусть столбцыY1 = (I1T , 0T2 , . . . , 0Tk )T , Y1 = (0T1 , I2T , . . . , 0Tk )T , . . . ,Yk = (0T1 , .

. . , 0Tk−1 , IkT )T(13)являются решениями системы уравнений ÃY = 0. Они образуют фундаментальную систему решений системы ÃY = 0 тогда и только тогда, когдаопределяемое этими решениями разбиение столбцов матрицы Ã = (A1 , A2 , . . .,Ak ) на 1-зависимые подсистемы A1 , A2 , . . . , Ak единственно и сами подсистемы минимальные.Далее приведены новые доказательства теоремы о циклах и разрезах иконструктивное доказательство теоремы о минимальной факторизации симметричной (0, 1)-матрицы.В работе использовано следующее определение:Определение.

Симметричная (0, 1)-матрица A порядка n факторизуема,если существует матрица B такая, что A = BB T . Если при этом матрица B имеет наименьшее возможное число столбцов, то такая факторизация называетсяминимальной.Подчеркнем, что рассмотрено специальное разложение матрицы, отличноеот наиболее часто используемых, таких как LU-разложение, разложение Холецкого, QR-разложение и др.Каждой элементарной операции метода Гаусса над полем GF (2) сопоставлена парная элементарная операция. Если элементарная операция выполняетсянад i-й и j-й строками, то аналогичная операция должна быть выполнена надi-м и j-м столбцами. Это значит, что каждый шаг вычислений состоит из пары21элементарных операций.Определение.

Такие пары операций называются двойными элементарыми операциями.Последовательность элементарных операций над строками матрицы может быть рассмотрена как умножение данной матрицы слева на некоторуюневырожденную матрицу P . Тогда последовательность соответствующих элементарных операций над столбцами — это умножение данной матрицы справана матрицу P T .Для любой элементарной операции над полем GF (2) существует обратнаяэлементарная операция, причем элементарные матрицы для прямой и обратнойопераций совпадают.Определение.

Две квадратные (0, 1)-матрицы n-го порядка A и C будемназывать конгруэнтными над полем GF (2) если существует невырожденная(0, 1)-матрица P такая, что C = P T AP .В работе доказана теорема:Теорема 61. Любая симметричная (0, 1)-матрица A конгруэнтна блочнодиагональной матрице видаAe = diag(L1 , L2 , .

. . , Lq , l1 , l2 , . . . , lp , 0, 0, . . . , 0)где lj (j = 1, 2, . . . , p) единичный блок размерности 1 × 1, Lk (k = 1, 2, . . . , q)0 1, и p + 2q = rank A.— матрица 2 × 2 вида 1 0Матрица Ae может быть факторизована следующим образом.Если на главной диагонали матрицы Ae находятся только q блоков вида0 1, тогда1 0Ae = QQT ,22гдеQ=IO...OOH H ...

H H J I H ... H H J .O O ... I H J O O ... O L JЗдесьI=1 00 1,L = 0 11 0,H = 1 11 1,J = 11и число столбцов в Q равно 2q + 1. Если r = rank A < n, к матрице Q добавляются n − r нулевых строк.Если на главной диагонали матрицы Ae стоят q блоков вида 0 11 0иpединиц, тогдаAe = QQT ,гдеQ=IOH H ... H H J 0 0 ... 0I H ... H H J 0 0 ... 0...O O O ... I H J 0 0 ...

0O O O ... O L J 0 0 ... 0O O O ... O O 1 0 0 ... 0O O O ... O O 0 1 0 ... 0...O O O ... O O 0 0 0 ... 1o2q − 2 rows2 rows.p rowsЗдесь O = (0, 0) и 0 = (0, 0)T . Если r < n, к матрице Q добавляются всего n − rнулевых строк.Тем самым получаем следующее равенство:A = CAe C T = CQQT C T .23Это означает, что матрица A представима в виде A = BB T , где B = CQ.В диссертационной работе доказано, что полученная факторизация A = BB Tявляется минимальной.В параграфе 3.4 показано, как связаны задачи распознавания реберногографа и факторизации матрицы, а также приведен новый матричный алгоритмраспознавания реберного графа, построенный с помощью линейно-алгебраического подхода.Как известно, реберным графом обыкновенного графа H называется графG = L(H) такой, что каждая вершина L(H) соответствует ребру H, и двевершины L(H) смежны тогда и только тогда, когда соответствующие ребра Hимеют общую вершину.

Граф H называется корневым графом графа G.В предложенном алгоритме использованы только стандартные матричныеоперации над полем по модулю 2. Алгоритм основан на следующей теореме,доказанной в диссертации:Теорема 67. Граф G является реберным графом некоторого графа Hтогда и только тогда, когда существует (0, 1)-матрица B такая, что D =B T B, содержащая в каждом своем столбце ровно две единицы.

Более того,данная матрица B является матрицей инцидентности графа H.Связь задачи распознавания реберного графа с задачей о факторизациисимметричной матрицы дается следующим следствием, доказанным в работе:Следствие. Пусть граф G с матрицей смежности D является ребернымграфом некоторого графа H с матрицей инцидентности B, D = B T B. Тогдасуществует разбиение строк матрицы B T на группы так, что соответствующиеподграфы графа G = L(H) с матрицей D являются кликами, удовлетворяющими условию теоремы 67.Приведены примеры, показывающие работу алгоритма.В четвертой главе диссертационной работы предложен эффективныйчисленный алгоритм, позволяющий в арифметике с плавающей точкой построить решение задачи Коши для системы нелинейных дифференциальных урав-24нений, имеющее наименьшую полную погрешность (сумму погрешности методаи ошибок округления).

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

Характеристики

Список файлов диссертации