1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 55
Текст из файла (страница 55)
Алгоритм 6.2 можно реализовать за Ода(пэ/[ода) операций с двоичными вектор ми. Д о к а з а т е л ь с т в о. Для того чтобы узнавать, когда надо увеличить й, используется счетчик. Вначале значение счетчика равно 1, а Я=О. Всякий раз, когда 1 увеличивается, счетчик уменьшается на 1, если его значение было отлично от 1; а в последнем случае значение счетчика полагается равным новому значению /, а й увеличивается на 1.
Присваивания в строках 2 и 5 рис. 6.6 занимают постоянное время. Следовательно, цикл в строках 3 — 5 имеет сложность Одв(п). Поскольку в РАМ двоичный вектор представляется целым числом '), иа вычисление ЧИС(аг) в строке 6 не уходит время, так что каждую строку матрицы С, можно найти за фиксированное число операций над двоичными векторами и строка б имеет сложность Одв(п).
Поэтому цикл в строках 1 — 6 занимает время Одв(па/[ои л); такое же время тратится и на строку 7. С) УПРАЖНЕНИЯ 6.!. Покажите, что целые числа по модулю п образуют кольцо, т. е. что Մ— кольцо ((О, 1,..., л — 1), +,, О, 1), где а+Ь и а Ь вЂ” обычные сложение и умножение по модулю л.
6.2. Покажите, что (ими)-матрицы с элементами из некоторого кольца /с образуют кольцо, ') можно обойти ту деталь, что чис(аг) соответствует не самому вектору аг, а перестановке его элементов в обратном порядке, если в качестве /-Е строки катрины В взять /-ю строку снизу, а не сверку, как мм делали раньше. гл. в. гмножяниз млтэиц 6.3. Приведите пример, показывающий, что произведение матриц некоммутативно, даже если нх элементы берутся нз кольца с коммутатнвным умножением.
6.4. Примените алгоритм Штрассена для вычисления произведения 3 4 7 8 6.6. Еще один вариант алгоритма Штрассена использует для вычисления произведения двух (2х2)-матрнц равенства ЭЬ = авв + авв* т» = Звэа, 1а = Пав+ тв» з,=з,— агп та=а„й„, 1, 1,+т,. за=ам — а„, т,=а„эм, э,=а„— з„ та = заз» ('11 ('11 ть з1эь за ('вв зь» та за(ьвв» зв йвв 1111» па» аввэа» зв = за — ов1 Элементы произведения получаются так: с„= т,+т„с„=1,— т„ с„=1,+т,+т„с„=1,+и,.
Покажите, что этн элементы равны соответствующим элементам нз (6А). Заметьте, что было сделано только 7 умножений н (5 сложений. 6.6. Докажите следующие соотношения для (пхп)-матриц А, ВиС: (а) если АВ=1 н АС=1, то В=С, (в) (АВ)-'=В-'А-', (д) де((АВ)=а(е((А) де((В). 6.7. Теорема 6.2 показывает, что невырожденную верхнюю треугольную матрицу можно обратить за сив" арифметических операций, где с — постоянная. Найдите эту постоянную с в предположении, что матрицы умножаются по алгоритму Штрассена н и— степень числа 2.
6.8. Представим матрицу перестановки массивом Р, для которого РИ=1 тогда и только тогда, когда в 1-м столбце на 1-й строке стоит !. Пусть Р, и Р,— такие представления (ихл)-матриц перестановки. (а) Докажите, что Р,Р,И=Р,[Р,И1. (б) Постройте алгоритм, вычисляющий Р,' за время 0(п). УПРАЖНЕНИЯ (с) Измените описанное представление так, чтобы Р(()=( тогда и только тогда, когда на (-й строке в 1ьм столбце стоит 1.
Напишите правильную формулу для Р,Р, и постройте алгоритм для вычисления Р-,'. 6.9. Примените алгоритм 6.1, чтобы найти НВП-разложение матрицы 0 0 1 2 0 0 3 0 1 — 1 0 1 2 0 — 1 3 6.10. Мы показали, что нахождение НВП-разложения, обращение матрицы„вычисление определителя и решение системы линейных уравнений имеют сложность ОА(п'"'). Найдите наилучшие мультипликативные постоянные для каждой из этих задач в предположении, что матрицы умножаются по алгоритму Штрассеиа, п — степень числа 2 и применяется техника алгоритма 6.1 и теорем 6.4 — 6.7.
6.11, Для матрицы М из упр. 6.9 найдите (а) обратную и (б) определитель, используя технику втой главы. 6.12. С помощью НВП-разложения решите систему х,+ 2х,=7 Зх, =9 Ха — Хя + Хе=3 2х, — х,+Зх,=10. 6.13. Покажите, что каждая перестановка либо четна, либо нечетна, но не то и другое одновременно. 6.14.
Вычислите произведение булевых матриц 10000100 0 0 ! 1 1 1 0 0 10011010 0 О 1 О 0 0 0 1 применяя (а) метод теоремы 6.9 и (б) алгоритм четырех русских. 6.16. Закончите доказательство теоремы 6.3, показав, что верны взаимосвязи, изображенные на рис. 6.2 и 6.3. "*6.16. Рассмотрим поле ') Р, целых чисел по модулю 2. Найдите алгоритм умножения (и Х и)-матриц над Р, с асимптотической сложностью не более 0(па аа/(1ойп)е '). Указание: Разбейте матрицы на блоки размера )Г!ой ПХ'р' 1од и. а! Определение поля ем, в равд.!2.1, ГЛ.
К УМНОЖЕНИИ МАТРИЦ 6.17. Оцените значение и, начиная с которого и* " меньше иэ11ой и. "6.18. Пусть 1.(п) — время умножения двух нижних треугольных (пхи)-матриц, а Т(и) — время умножения двух произвольных матриц. Докажите, что найдется такая постоянная с, что Т(п)( (с1. (и). 6.19. Докажите, что матрица, обратная к верхней (нижней) треугольной, является верхней (нижней) треугольной, "6.20. Пусть 1(п) — число шагов, необходимое для Обращения (и х и)-матрицы, а (1 (и) — для обращения верхней треугольной матрицы. Докажите, что найдется такая постоянная с, что 1(и)( =с(1(п) д и "*6.21.
Чтобы вычислить произведение матриц С=АВ, можнобыло бы определить сначала 0=(РАЯ (Я-'ВЯ), а затем С=Р-'0й-'. Если Р, 9 и Я вЂ” специальные матрицы, например матрицы перестановок, то вычисление произведений РАЯ, Я-'В11 и Р-'0К ' не требует умножения элементов кольца. Воспользуйтесь этой идеей, чтобы найти другой метод перемножения (2х2)-матриц за 7 умножений элементов кольца. 6.22.
Докажите, что НВ-разложение невырожденной матрицы А, если оио существует, единственно. Указание: Пусть А=А,(1,= =1.,(1,. Покажите, что 1. ', 1,=(1,(1 ',=1. 6.23. Докажите, что если матрица А невырожденна и каждая ее главная подматрица невырожденна, то А имеет НВ-разложение. 6.24. Может ли вырожденная матрица обладать НВП-разложением? **6.25. Пусть А будет (ихт)-матрицей с вещественными элементами.
Матрица А называется положительно определенной, если для каждого ненулевого вектора-столбца х выполнено неравенство хгАх)0. (а) Покажите, что лемму 6.5 можно применить для обращения произвольной невырожденной симметричной положительно определенной матрицы. (б) Покажите, что если матрица А невырожденна, то матрица ААг положительно определена и симметрична. (в) Используя (а) и (б), постройте алгоритм сложности ОА (М (и)) для обращения любой невырожденной матрицы с вещественными элементами. (г) Будет ли ваш алгоритм для (в) работать в случае поля целых чисел по модулю 27 *6.26. Матрица А размера пхи называется теилицееоа, если А Ь, 1)=А [1 — 1, 1 — 1), 2(1, 1(и.
(а) Найдите представление теплицевых матриц, при котором сумму двух теплицевых матриц можно найти за 0(и) шагов. 2З2 злмпчлния по литенлтнж (б) С помощью приема "разделяй и властвуй" постройте алгоритм умножения теплицевой (и ха)-матрицы на вектор-столбец. Сколько арифметических операций он требует? Указание; С помощью приема "разделяй и властвуй" можно получить алгоритм сложности 0(н'").
В гл. 7 будет развита техника, которую можно будет применить для улучшения этого результата. (в) Постройте асимптотически эффективный алгоритм умножения двух теплицевых (ахя)-матриц. Сколько арифметических операций он требует? Заметьте, что произведение теплицевых матриц может не быть теплицевой матрицей. Проблемы для исследования 6.27. Естественно попытаться непосредственно улучшить метод Штрассена. Хопкрофт, Керр !1971] показали, что для вычисления произведения (2 х 2)-матриц над произвольным кольцом необходимы семь умножений.
Однако рекурсивный алгоритм может быть основан на умножении матриц какого-нибудь другого небольшого размера. Например, можно было бы улучшить порядок алгоритма Штрассена, если суметь перемножать (ЗХЗ)-матрицы за 21 умножение или (4х4)-матрицы за 48 умножений. 8.28. Можно ли находить кратчайшие пути меньше, чем за 0(п') щагову Алгоритм Штрассена неприменим к замкнутым полукольцам, состоящим из неотрицательных вещественных чисел и +ею, но, может быть, удастся свести операции в этом замкнутом полукольце к операциям в некотором кольце, как это было сделано для булевых матриц. Замечания по литературе Алгоритм Штрассена заимствован из работы Штрассена [1969].
Виноград [1973] уменьшил число необходимых сложений до 15, что улучшило мультипликативную постоянную, но не порядок сложности (см. упр.6.5). Штрассен 119691 такхсе описал методы сложности 0(из аз) для обращения матриц, вычисления определителей и решения систем линейных уравнений в предположении, что каждая матрица, встречающаяся в цропессе вычислений, невырожденна. Банч, Хопкрофт [19741 показали, что НВП разложение можно сделать за 0(изм) шагов при единственном предположении, что исходная матрица невырожденна.
Шенхаге независимо показал, что обращение любой невы- рожденной матрицы над упорядоченным полем можно найти зз 0(лам! шагов (упр. 6.25). Результат о том, что умножение матриц не сложнее обращения матрицы, получен Виноградом [197061. Алгоритм сложности Од (язем) для умножения бу. левых матриц построен фишером, Мейером [1971], а алгоритм четырех русских— Арлазаровым, Дннипем, Кронродом, Фараджевым 11970].
Валиант [1974] применил алгоритм штрассена для расйознавзння бесконтекстиых языков о (и'з'1. Дополнительные сведения по теории матриц можно найти у Хопа [1956]. Алгебраические понятия, такие, как кольцо, изложены в книге Маклейна, Бнрк. гофа [19671. Решение упр.
6.13 приведено Биркгофом, Барти [1970), упр. 6.16 принзкчежит Хопкрофту. 2аэ 7 БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ЕГО ПРИЛОЖЕНИЯ Преобразование Фурье естественно возникает во многих задачах теоретического и прикладного характера, и потому имеетсмысл изучить эффективный алгоритм его вычисления. Вездесущность преобразования Фурье будет в дальнейшем продемонстрирована его применимостью к построению эффективных алгоритмов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
