Диссертация (1145311), страница 19
Текст из файла (страница 19)
Метод допускает обобщение на случай матрицы D(λ), элементы которой являются полиномами от λ степени выше первой, т. е. матричного полиномаD(λ) = A0 λm + A1 λm−1 + . . . + Am ,143где Aj j = 0, 1, . . . , m — квадратная матрица k-го порядка с комплекснымиэлементами. В данном случае алгоритм усложняется при нахождения суммНьютона характеристического полинома матрицы D(λ). Все остальные егошаги не изменяются. (Обзор различных задач, связанных с собственными числами матрицы, и методов их решения см. книгу [35].)2.4.2.
Асимптотическая сложность алгоритмаи повышение точности вычисленийСамая вычислительно затратная операция, используемая в предлагаемомалгоритме, — матричное умножение. Асимптотическая сложность перемножения двух квадратных матриц пордяка n равна O(n3 ), если умножение производится по определению. В настоящее время из известных алгоритмов матричногоумножения с асимптотической сложностью O(np ) наименьшее значение степениp имеет обобщенный алгоритм Копперсмита — Винограда (1990) [73], которыйимеет асимптотическую сложность O(n2.3728639 ). Асимптотическая сложностьалгоритма Штрассена равна O(nlog2 7 ) ≈ O(n2.807 ).
Для вычисления степенейматриц Ap , B p (p = 1, 2, . . . , k 2 − k − 1) необходимо выполнить 2(k 2 − k − 2)матричных умножений (всего O(k 5 ) операций), затем требуется вычислить следы матриц Ap B q , p, q ∈ {0, 1, 2, . . . , k 2 − k}, p + q ≤ k 2 − k — приблизительноO(k 6 ) операций всего. Следовательно, суммарно нужно выполнить O(k 6 ) операций без учета нахождения корней полинома (2.21).Все комплексные корни полинома от одной переменной степени k с относительной погрешностью не большей можно найти за O(k 2 log k(log k + log(1/))3арифметических операций [147].
Для = 1/(10k ) это составляет O(k 6 ) операций. Таким образом, предложенный алгоритм имеет асимптотическую сложность O(k 6 ).Достаточно сложно оценить, сколько раз во время работы алгоритма, описанного в статье [140], необходимо найти сингулярное разложение (SVD) матриц.
Однако с учетом того, что асимптотическая сложность нахождения сингу-144лярного разложения квадратной матрицы порядка n равна O(n2 ) [92], асимптотическая сложность алгоритма, предложенного в работе [140], не менее O(k 6 ).Следовательно, асимптотические сложности двух алгоритмов, которые упоминаются выше, сопоставимы.Матричное умножение является основной операцией для предлагаемогоалгоритма. В связи с этим хотелось бы уменьшить вычислительные ошибки,которые возникают при произведении этой операции при вычислении на компьютере.
В арифметике с плавающей точкой точность вычислений может бытьповышена без каких-либо значительных затрат с помощью результата, представленного в книге [61]. Для этого при вычислении каждого скалярного произведения все операции выполняются с двойной точностью, а полученный результат округляется до числа, записанного с одинарной точностью. Для двухвекторов U и V (k × 1) предположим, что |U T ||V | ≤ υ|U T V |, где |U |, |V | —векторы, компоненты которых равны абсолютным значениям соотвествующихкомпонент векторов U, V .
Тогда для скалярного произведения U T V вычисленное значение почти столь же точно, как и правильно округленный точный результат. Граница скалярного произведения U T V следующая:|f l(f le (U T V )) − U T V | < υ|U T V | +kυe(1 + υ)|U T ||V |.1 − kυe /2Здесь υ (“unit roundoff”) — максимальное значение относительной погрешности, υ = ε/2 (например, для float (4 байта) ε ≈ 1.19 · 10−7 , для double (8 байт)ε ≈ 2.22 · 10−16 , для long double (10 или 12 байт в зависимости от системы)ε ≈ 1.08 · 10−19 ). Значения ε могут быть взяты из стандартного включенногофайла float.h для C-компилятора для архитектуры x86.
Через f l(a) обозначенрезультат вычислений с одинарной точностью (с t двоичными цифрами), через f le (a) — результат вычислений с расширенной точностью (с 2t двоичнымицифрами), υe — соответствующее значение относительной погрешности.Замечание 24. В одинарной точности условие |U T ||V | ≤ υ|U T V | выполняет-145ся для скалярных произведений с абсолютными значениями, большими0.1862645142 · 10−8 k. Например, для k = 4000 абсолютное значение скалярногопроизведения должно быть больше, чем 0.7450580568 · 10−5 .Замечание 25.
Существует прямой способ решения поставленной задачи,Можно вычислить характеристический полином матрицы D = A + λB, азатем найти значения параметра, соответствующие его кратным корням.Однако этот подход является значительно более затратным. Коэффициенты характеристического полинома являются полиномами от λ. Максимальная возможная степень такого коэффициента равна k.
Для нахождения требуемых значений λ необходимо вычислить дискриминант характеристического полинома, т. е. определитель полиномиальной матрицы размерности(k 2 − k) × (k 2 − k). Согласно результату, приведенному в статье [91], вычислительная сложность данного подхода не может быть менее, чем O(k 7 ).2.4.3. Численный примерРассмотрим задачу из статьи [140].
Даны матрицы1 −2 31 −1 1A = −1 1 2 ,B = 1 1 3 .1 1 −1−1 1 1Требуется найти все значения параметра λ, при которых матрица D = A + λBимеет кратные корни.Вычислим суммы Ньютона характеристического полинома матрицы A +λB:s1 = 3λ + 1;s2 = 5λ2 + 6λ + 17;s3 = 21λ3 + 33λ2 + 30λ − 8;146s4 = 65λ4 + 124λ3 + 82λ2 + 4λ + 117;s5 = 173λ5 + 415λ4 + 485λ3 + 285λ2 + 240λ − 134;s6 = 473λ6 + 1386λ5 + 2121λ4 + 1620λ3 + 522λ2 − 324λ + 890.Cуммы Ньютона характеристического полинома матрицы CA :S2 = 12λ2 + 24λ + 100;S4 = 186λ4 + 504λ3 + 1980λ2 + 2424λ + 4234;S6 = −11280λ6 − 33840λ5 − 35904λ4 + 6480λ3 + 36282λ2 ++42300λ + 64058.Находим коэффициенты:A2 = −S2 /2 = −6λ2 − 12λ − 50 ;A4 = −(S4 + A2 S2 )/4 = −57/2λ4 − 54λ3 − 123λ2 − 6λ + 383/2 ;A6 = −(S6 + a2 S4 + A4 S2 )/6 == 2123λ6 + 6738λ5 + 11459λ4 + 10908λ3 + 21226λ2 + 20952λ + 64246/3 .Корни уравнения A6 = 0:−2, 333069484; −1, 401818975 ± 0, 6190045476i ,0, 2836993683 ± 0, 1543575855i , 1, 933794680.Данные значения λ отличаются от приведенных в работе [140] уже в первомзнаке после запятой:1, 5628; −2, 2078; −1, 1690 ± 0, 8436i ; 0, 2735 ± 0, 0988i .Сравним собственные числа матрицы A + λB, при λ = −2, 333069484 и приλ = −2, 2078.Для λ = −2, 333069484 получаем собственные числа:−0, 257071186441648280, −0, 257116318877424144,147−5, 48502094668092610.Мы видим, что первые два собственные числа совпадают до тысячных.Для λ = −2, 2078 получаем собственные числа0, 567197754532772214; −1, 01664058066736440; −5, 17395717386540620.Здесь все собственные числа различны.Как справедливо замечают авторы работы [140], их метод дает довольнобольшую погрешность в связи с тем, что необходимо находить численный рангматриц.
В связи с этим они предлагают применять его лишь для матриц малыхпорядков. Однако мы видим, что даже в этом случае погрешность может бытьдовольно велика.148Глава 3Графы и матрицыАлгебраический подход позволяет получить многие теоретические и практические результаты теории графов. Идея приложения методов линейной алгебры к задачам теории графов была предложена в книге [81].
Мы рассматриваемособенности линейных пространств над полем Галуа характеристики 2. Эти особенности важны для исследования графов методами линейной алгебры. Такжемы вводим линейные отображения, связанные с каждым обыкновенным связным графом с n вершинами и исследуем свойства матриц этих отображений.Данный подход позволяет получить новые, более простые доказательства некоторых известных теорем теории графов, получить некоторые результаты дляреберных покрытий и независимых множеств, а также разработать новый матричный алгоритм распознавания реберного графа и построения его корневогографа.Проблема построения максимального паросочетания имеет различные приложения к задаче о назначениях и планированию при выполнении задач.
Индекс Хосойи [101], который определяется через независимые множества, используется в разработках вычислительной химии и математической химии для органических соединений. Существуют также приложения задачи о независимыхмножествах в вычислительной линейной алгебре (см., например, статьи [83,149, 153]). Таким образом, изучение реберных покрытий и паросочетаний представляет как теоретический, так и практический интерес.
Известно достаточномного алгоритмов, позволяющих построить максимальное паросочетание илирешить связанную с данной задачей проблему построения наименьшего реберного покрытия (например, [74, 84, 139, 142]).В диссертации приводится новое доказательство известной теоремы о наименьшем реберном покрытии и наибольшем паросочетании (теорема 64) и до-149казывается новая теорема 63.Еще одна задача, которая рассматривается в диссертации, — задача о распознавании реберного графа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
