Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 171
Текст из файла (страница 171)
Следовательно, матрица АтА положительно определенная. И Прочие свойства положительно определенных матриц рассматриваются в разделе 28.5. Упражнения 28.1-1. Покажите, что если А и  — симметричные матрицы размером и х и, то симметричными будут их сумма и разность. 28.1-2. Докажите,что1АВ) = В А ичтоА Авсегдаявляетсясимметричной матрицей. Часть ЧП. Избранные темы х" 1 хо хо хо г 1 х1 х, г х" 1 1 У(хо,х1,...,х„1) = 28.1-3. Докажите единственность обратной матрицы, т.е. что если В и С— обратные к А матрицы, то В = С. 28.1-4. Докажите, что произведение двух нижне-треугольных матриц дает нижне-треугольную матрицу.
Докажите, что определитель нижне-треугольной или верхне-треугольной матрицы равен произведению диагональных элементов. Докажите, что если существует матрица, обратная к нижне- треугольной матрице, то она также является нижне-треугольной. 28.1-5. Докажите, что если Р— матрица перестановок размером и х и, а А— матрица размером п х п, то РА можно получить из А путем перестановки ее строк, а АР— путем перестановки столбцов А. Докажите, что произведение двух матриц перестановки является матрицей перестановки. Докажите, что если Р— матрица перестановки, то Р обращаема, причем обратной к Р является матрица Рт, которая также является матрицей перестановки. 28.1-6.
Пусть А и  — матрицы размером и х и такие, что АВ = 1. Докажите, что если А' получена из А путем прибавления к строке 1 строки 1, то обратную к А' матрицу В' можно получить, вычитая в матрице В столбец 1 из столбца у. 28.1-7. Пусть А — невырожденная матрица размером и х п с комплексными элементаь(и. Покажите, что все элементы А 1 вещественны тогда и только тогда, когда вещественны все элементы А. 28.1-8. Покажите, что если А — невырожденная симметричная матрица размером и х п, то матрица А ' симметрична.
Покажите, что если В— произвольная матрица размером тп х и, то матрица размером т х т, получающаяся в результате умножения ВАВт, симметрична. 28.1-9. Докажите теорему 28.2, т.е. покажите, что матрица А имеет полный столбцовый ранг тогда и только тогда, когда из Ах = 0 следует х = О.
(Указание: запишите условие линейной зависимости одного столбца от остальных в виде матрично-векторного уравнения.) 28.1-10. Докажите, что для любых двух совместимых матриц А и В гппй (А В) < < тт (гатй (А), гапй (В)), причем равенство достигается если либо А, либо  — невырожденная квадратная матрица. (Указание: воспользуйтесь альтернативным определением ранга матрицы.) 28.1-11. Докажите, что определитель матрицы Вандермонда (Уапдеппопс1е ша1пх) Глава 28.
Работа с матрицами 833 равен о<з<ьб -з (Указание: умножьте столбец 1 на — хо и прибавьте к столбцу 1 + 1 для 1 = и — 1, и — 2,..., 1, а затем примените индукцию.) 28.2 Алгоритм умножения матриц Штрассена В этом разделе представлен замечательный рекурсивный алгоритм умножения матриц размера и х и, разработанный Штрассеном (81газзеп).
Время его работы равно О (и'Я т) = О (из а1). При достаточно больших значениях и этот алгоритм работает быстрее алгоритма МАтих Моьт~рьу из раздела 25.1, время работы ко- О (из) Обзор алгоритма Алгоритм Штрассена можно рассматривать как применение уже знакомой нам технологии декомпозиции "разделяй и властвуй". Предположим, что мы хотим вычислить произведение С = АВ, где каждая из матриц имеет размер и х и. Считая, что и является точной степенью 2, поделим каждую из матриц на четыре матрицы размером и/2 х и/2 и перепишем уравнение С = АВ следующим образом: (28.8) (В упражнении 28.2-2 рассматривается ситуация, когда и не является точной сте- пенью 2.) Уравнение (28.8) соответствует четырем уравнениям: Каждое из этих четырех уравнений требует двух умножений матриц размера и/2 х х и/2 и сложения получившихся произведений.
Используя эти уравнения как определение простейшего рекурсивного алгоритма, мы получим следующее рекуррентное соотношение для времени его работы при умножении матриц размера ихи: Т (и) = 8Т (и/2) + О (из) . (28.13) с1ет(У(хо,хы...,х„1)) = П (хь — х ) . т = ае+Ьд, а = а/+ЬЬ, 1=се+ад, и = с,~+ сй. (28.9) (28.10) (28.11) (28.12) Часть ЧП. Избранные темы 834 К сожалению, рекуррентное соотношение (28.13) имеет решение Т (и) = О (пз), так что этот метод получается не быстрее, чем обычное стандартное умножение матриц. Штрассен разработал рекурсивный алгоритм, который требует только 7 умножений матриц размером и/2 х и/2 и 9 (пз) скалярных сложений и умножений, что приводит к рекуррентному соотношению Т(п) = 7Т(п/2)+ 9 (пз), (28.14) юторое имеет решение Т(и) = 9 (ия') = О (пзаз).
Метод Штрассена состоит из четырех шагов. 1. Разделяем матрицы А и В на подматрицы размером и/2 х и/2, как показано в 28.8. 2. Используя 9 (пз) скалярных сложений им умножений, вычисляем 14 матриц Аы Вм Аг, Вз,..., Ат, Вт, каждая из которых имеет размер и/2 х п/2. 3. Рекурсивно вычисляем семь матричных произведений Р, = А;В, для 1 = = 1,2,...,7. 4.
Вычисляем подматрицы г, а, г и и результирующей матрицы С путем сложения и/или вычитания различных юмбинаций матриц Р; с использованием 6 (пз) скалярных сложений и вычитаний. Описанная процедура удовлетворяет рекуррентному соотношению (28.14). Все, что осталось сделать, — изложить опущенные детали. Определение произведений подматриц Не совсем понятно, как именно Штрассен нашел необходимые подматрицы, которые следует перемножать.
Давайте попытаемся воспроизвести один из возможных способов разработки алгоритма. Предположим, что каждое матричное произведение Р; можно записать в виде Р; = А;В; = (аца+ ало+ оязс+ сц4п) (рце+ Дв/+ Дзд+ 13мй), (28.15) где коэффициенты снз и 13; принимают значения из множества ( — 1, О, Ц. Т.е. мы предполагаем, что каждое произведение вычисляется при помощи сложения или вычитания некоторых из подматриц А, сложения или вычитания некоторых из подматриц В, и перемножения получающихся результатов. Хотя, естественно, можно искать более общий вид произведения Р;, описанного вида произведения оказывается достаточно для разработки алгоритма.
Если использовать описанный вид произведения, то мы можем использовать его рекурсивно без оглядки на неюммутативность умножения матриц, так как Глава 28. Работа с матрицами 835 в каждом произведении все подматрицы А оказываются слева, а подматрицы В— справа. Для удобства представления линейных комбинаций произведений подматриц воспользуемся матрицами размером 4 х 4. Например, мы можем записать уравнение (28.9) как г=ае+Ьд= +1 О О О О О +1 О О О О О О О О О =(аЬс а) е г д а а + Ь + Последнее выражение использует сокращенную запись, где каждый "+" представляет +1, "." представляет О, а "-" — — 1.
Кроме того, далее мы опускаем метки строк и столбцов. Используя данные обозначения, мы получим следующие уравнения для остальных подматриц, составляющих результирующую матрицу С: а = аг'+ Ьй = Часть Ч11. Избранные темы 836 Начнем наш поиск алгоритма быстрого перемножения матриц со следующего наблюдения: подматрицу в можно вычислить как в = Р1 + Рг, где матрицы Р1 и Рг вычисляются с использованием одного матричного произведения каждая: Р1 = А1В1 = а ° (~ — Ь) = а~ — ай = Рг = АгВг = (а + б) ° Ь = ай + бй = Матрица 1 может быль вычислена как т = Рз + Р4, где Рз = АзВз = (с + с1) .
е = се + Ие = и Р4 = А4В4 = и (д — е) = Ыд — де = Определим существенное слагаемое (еззепйа! Гепп) как один из восьми членов, появляющихся в правой части уравнений (28.9)-(28.12). Мы использовали 4 произведения для вычисления двух подматриц в и г, существенными слагаемыми которых являются а~, бй, се и Нд. Заметим, что Р1 вычисляет существенное слагаемое аг", Рг вычисляет существенное слагаемое бй, Рз вычисляет существенное слагаемое се, а Р4 вычисляет существенное слагаемое г)д.
Таким образом, нам остается вычислить две оставшиеся подматрицы г и и, чьими существенными слагаемыми являются ае, бд, с г' и Нй, с использованием не более чем трех дополнительных произведений. Попробуем вычислить Рз по-новому, чтобы охватить два существенных слагаемых одновременно: Рз = АзВз — — (а + с1) (е + Ь) = ае+ ай + Не + ~й = Глава 28. Работа с матрицами В дополнение к существенным слагаемым ае и сй Рз вычисляет несущественные слагаемые аЬ и Ые, которые требуется каким-то образом сократить. Мы можем воспользоваться для этого произведениями Рз и Р4, но при этом появятся новые несущественные слагаемые: Рз + Р4 — Рз = ае + пЬ + Нд — ЬЬ = Прибавляя дополнительное произведение Рв = А В = (Ь вЂ” Ы) (д+ Ь) = Ьд+ Ы вЂ” ад — аЬ = мы получим: г = Рз+ Р4 — Рз+ Рв = ае+ Ьд = Мы можем получить и аналогичным способом из Рз с использованием Р1 и Рз для удаления несущественных слагаемых из Рз..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
