Главная Промышленная автоматика.

УПРАЖНЕНИЯ

(с) Измените описанное представление так, чтобы PU]=j тогда и только тогда, когда на 1-й строке в /-м столбце стоит 1. Напишите правильную формулу для PiPa и постройте алгоритм для вычисления Р~\.

6.9. Примените алгоритм 6.1, чтобы найти НВП-разложение матрицы

6.10. Мы показали, что нахождение НВП-разложения, обращение матрицы, вычисление определителя и решение системы линейных уравнений имеют сложность Оа(п). Найдите наилучшие мультипликативные постоянные для каждой из этих задач в предположении, что матрицы умножаются по алгоритму Штрассена, п - степень числа 2 и применяется техника алгоритма 6.1 и теорем 6.4-6.7.

6.11. Для матрицы М из упр. 6.9 найдите (а) обратную и (б) определитель, используя технику этой главы.

6.12. С помощью НВП-разложения решите систему

2х, = 7 Здгз =9

•«1 - 2 + х = 3

21 -Xs + 3x,= l0.

6.13. Покажите, что каждая перестановка либо четна, либо нечетна, но не то и другое одновременно.

6.14. Вычислите произведение булевых матриц

применяя (а) метод теоремы 6.9 и (б) алгоритм четырех русских.

6.15. Закончите доказательство теоремы 6.3, показав, что верны взаимосвязи, изображенные на рис. 6.2 и 6.3.

**6.16. Рассмотрим поле *) Fa целых чисел по модулю 2. Найдите алгоритм умножения (пХп)-матриц над Fa с асимптотической сложностью не более О (п"-"/(log «)"•*). Указание: Разбейте матрицы на блоки размера KlognxKlogn.

) Определение поля см. в разд. 12.1,



6.17. Оцените значение п, начиная с которого n-i меньше raVlogn.

*6.18. Пусть L(n) -время умножения двух нижних треугольных (п X п)-матриц, аТ{п) - время умножения двух произвольных матриц. Докажите, что найдется такая постоянная с, что Г(пХ <cL (п).

6.19. Докажите, что матрица, обратная к верхней (нижней) треугольной, является верхней (нижней) треугольной.

*6.20. Пусть / (п) - число шагов, необходимое для обращения (пХ«)-матрицы, а U (п) - для обращения верхней треугольной матрицы. Докажите, что найдется такая постоянная с, что / («)< <с£/ (п) для всех п

**6.21. Чтобы вычислить произведение матриц С=АВ, можно было бы определить сначала D= (PAQ) (Q-BR), а затем C=P-R--. Если Р, Q и R - специальные матрицы, например матрицы перестановок, то вычисление произведений PAQ, Q-BR и P-DR" не требует умножения элементов кольца. Воспользуйтесь этой идеей, чтобы найти другой метод перемножения (2х2)-матриц за 7 умножений элементов кольца.

6.22. Докажите, что НВ-разложение невырожденной матрицы А, если оно существует, единственно. Указание: Пусть A=LiUi= =L2Ui. Покажите, что L-\ Li=UiU-\=I.

6.23. Докажите, что если матрица А невырожденна и каждая ее главная подматрица невырожденна, то А имеет НВ-разложение.

6.24. Может ли вырожденная матрица обладать НВП-разложе-нием?

**6.25. Пусть А будет (пХт)-матрицей с вещественными элементами. Матрица А называется положительно определенной, если для каждого ненулевого вектора-столбца х выполнено неравенство хМх>0.

(а) Покажите, что лемму 6.5 можно применить для обращения произвольной невырожденной симметричной положительно определенной матрицы.

(б) Покажите, что если матрица А невырожденна, то матрица А А положительно определена и симметрична.

(в) Используя (а) и (б), постройте алгоритм сложности Од (М («)) для обращения любой невырожденной матрицы с вещественными элементами.

(г) Будет ли ваш алгоритм для (в) работать в случае поля целых чисел по модулю 2?

*6.26. Матрица А размера пХп называется тёплицевой, если А [i,/]=Л [i-1, /-II, 2<t, /<п.

(а) Найдите представление тёплицевых матриц, при котором сумму двух тёплицевых матриц можно найти за 0{п) шагов.



(б) С помощью приема "разделяй и властвуй" постройте алгоритм умножения тёплицевой (« X п)-матрицы на вектор-столбец. Сколько арифметических операций он требует? Указание: С помощью приема "разделяй и властвуй" можно получить алгоритм сложности О(«*•»). В гл. 7 будет развита техника, которую можно будет применить для улучшения этого результата.

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

Проблемы для исследования

6.27. Естественно попытаться непосредственно улучшить метод Штрассена. Хопкрофт, Керр [1971] показали, что для вычисления произведения (2 х2)-матриц над произвольным кольцом необходимы семь умножений. Однако рекурсивный алгоритм может быть основан на умножении матриц какого-нибудь другого небольшого размера. Например, можно было бы улучшить порядок алгоритма Штрассена, если суметь перемножать (ЗхЗ)-матрицы за 21 умножение или (4 X 4)-матрицы за 48 умножений.

6.28. Можно ли находить кратчайшие пути меньше, чем за О шагов? Алгоритм Штрассена неприменим к замкнутым полукольцам, состоящим из неотрицательных вещественных чисел и -foo, но, может быть, удастся свести операции в этом замкнутом полукольце к операциям в некотором кольце, как это было сделано для булевых матриц.

Замечания по литературе

Алгоритм Штрассена заимствован из работы Штрассена [1969]. Виноград [1973] уменьшил число необходимых сложений до 15, что улучшило мультипликативную постоянную, но не порядок сложности (см. упр. 6.5).

Штрассен [1969] также описал методы сложности 0(п**) для обращения матриц, вычисления определителей и решения систем линейных уравнений в предположении, что каждая матрица, встречающаяся в процессе вычислений, невырожденна. Банч, Хопкрофт [1974] показали, что НВП-разложение можно сделать за 0(п<) шагов при единственном предположении, что исходная матрица невырожденна. Шёнхаге независимо показал, что обращение любой невырожденной матрицы над упорядоченным полем можно найти за ©(п.Ч шагов (упр. 6.25).

Результат о том, что умножение матриц не сложнее обращения матрицы, получен Виноградом [19706]. Алгоритм сложности Од {r?fi) для умножения булевых матриц построен Фишером, Мейером [1971], а алгоритм четырех русских - Арлазаровым, Диницем, Кронродом, Фараджевым [1970]. Валиант [1974] применил алгоритм Штрассена для распознавания бесконтекстных языков О (п").

Дополнительные сведения по теории матриц можно найти у Хоиа [1958]. Алгебраические понятия, такие, как кольцо, изложены в книге Маклейна, Бирк-гофа 1967]. Решение упр. 6.13 приведено Биркгофом, Барти [1970], упр. 6.16 принадлежит Хопкрофту.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 [90] 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.006