Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 172
Текст из файла (страница 172)
Рз + Р1 — Рз = ае + а,г" — се + йЬ = Вычитая дополнительное произведение Ру = АтВт = (а — с) (е+ У) = ае+ аг' — се — сг" = 838 Часть ЧП. Избранные темы мы получим и = Ра+Р1 Рз Рт = сУ+<~А= Таким образом, для вычисления произведения С = АВ можно использовать 7 произведений подматриц Ры Рз,..., Рт, что и завершает описание метода Штрассена. Обсуждение метода Алгоритм Штрассена редко применяется на практике по следующим причинам. 1. Постоянный множитель, скрытый во времени работы алгоритма Штрассена, превышает постоянный множитель во времени работы 9 (пз) простого алгоритма умножения. 2. В случае разреженных матриц имеются специализированные более эффек- тивные методы умножения. 3. Алгоритм Штрассена не настолько численно устойчив, как простой алго- ритм умножения матриц.
4. Построение подматриц на каждом шаге рекурсии приводит к повышенному расходу памяти. Последние две причины потеряли актуальность в 1990-х годах. Хайем (Н1811аш) (145] показал, что отличия в численной устойчивости преувеличены; хотя алгоритм Штрассена для ряда приложений действительно слишком численно неустойчив, его устойчивости все же вполне достаточно для большого количества приложений. Бейли (Ва(!еу) и др. в работе 130] рассмотрели методы снижения требующейся для работы алгоритма Штрассена памяти.
На практике реализации быстрого умножения плотных матриц с использованием алгоритма Штрассена имеют "точку пересечения" (в смысле размера перемножаемых матриц) с обычным алгоритмом умножения, и переключаются на использование простого алгоритма при перемножении матриц с размером, меньшим точки пересечения. Точное значение точки пересечения сильно зависит от реализации и используемой вычислительной системы.
Анализ, учитывающий количество операций и игнорирующий кэширование и конвейерную обработку, дает для точки пересечения различные оценки — 8 у Хайема [145] и 12 у Хасс-Ледермана (Низа-Ьедеппап) (163]. Эмпирические измерения обычно приводят к более высокой точке пересечения, обычно порядка 20 и выше. В каждой конкретной системе поиск точки пересечения лучше выполнять экспериментально. Глава 28. Работа с матрицами 839 Использование более сложных методов, изложение которых выходит за рамки книги, позволяет вычислять произведение матриц еще быстрее.
В настоящий момент наилучшая верхняя граница составляет примерно О (тРлта). Наилучшая нижняя граница, очевидно, равна П (пз) (ее очевидность вытекает из необходимости заполнения пз элементов матрицы), так что разрыв достаточно велик и точная граница в настоящий момент неизвестна. Упражнения 28.2-1.
Воспользуйтесь алгоритмом Штрассена для вычисления произведения ( ь~ зт ) ( а ~~э ). ПРиведнте пРомежУточные РезУльтаты. 28.2-2. Каким образом следует модифицировать алгоритм Штрассена для умножения матриц размером и х и, если и не является точной степенью 2? Покажите, что модифицированный алгоритм имеет время работы О (пвт). 28.2-3. Допустим, что мы можем перемножить матрицы размером 3 х 3 с использованием Й умножений (не используя коммутативности умножения). Чему равно наибольшее значение й, позволяющее перемножить матрицы размером и х п за время о (пакт)? Чему равно время работы алгоритма в этом случае? 28.2-4.
Имеется способ перемножения матриц размером 68 х 68 при помощи 132464 умножений чисел, матриц размером 70 х 70 за 143 640 умножений чисел и матриц размером 72 х 72 за 155 424 умножения. Какой метод дает лучшее асимптотическое время работы при использовании в алгоритме умножения матриц "разделяй н властвуй" ? Как это время работы соотносится со временем работы алгоритма Штрассена? 28.2-5. Как быстро можно умножить матрицу размером Ип х п на матрицу размером и х Мп, используя алгоритм Штрассена в качестве подпрограммы? А в случае перемножения матриц в обратном порядке? 28.2-6. Покажите, как можно перемножить два комплексных числа а+ Ьг и с+ +Ыг, используя только три действительных умножения. Алгоритм должен получать в качестве входных параметров числа а, Ь, с и Н, и давать на выходе действительную (ас — Ьо) и мнимую (Ы+Ьс) части произведения.
28.3 Решение систем линейных уравнений Решение систем линейных уравнений представляет собой фундаментальную задачу, возникающую в различных приложениях. Такую систему линейных уравнений можно записать как матричное уравнение, в котором каждый элемент матрицы или вектора принадлежит некоторому полю, обычно — полю действительных Часть Ч11. Избранные темы 840 чисел К. В этом разделе мы рассмотрим решение систем линейных уравнений с использованием метода, называемого Шр-разложением.
НаЧНЕМ С СИСТЕМЫ ЛИНЕЙНЫХ ураВНЕНИй С т1 НЕИЗВЕСТНЫМИ Х1, Х2,..., Хп. аых1 + ащхз + . + а1пхп = Ь1, а21х1 + аззх2 + . + азпхп = Ь2, (28.16) Яп1х1 + оп2х2 + ' ' + оппхп = Ь Множество значений х1, х2,..., хп, одновременно удовлетворяющее всем уравнениям в (28.16), называется решением (зо!убоп) этих уравнений. В данном разделе мы рассмотрим только случай, когда у нас имеется ровно и уравнений для п неизвестных.
Мы можем для удобства переписать уравнения (28.16) в виде матрично-векторного уравнения Ь Х1 ам а12 .. а1п П21 О22 ' ' ' О2п Хг Оп1 Оп2 ' ' ' Опп хп Ьп или, вводя обозначения А = (а;у), х = (х;) и Ь = (Ь;), в виде Ах = Ь. (28.17) Если матрица А невырождена, то можно найти обратную к ней матрицу А 1 и найти решение системы линейных уравнений следующим образом: х=А 'Ь. (28.18) Можно легко доказать, что х является единственным решением уравнения (28.17). Пусть имеется два решения — х и х'. Тогда Ах = Ах' = Ь и х= (А 1А)х=А 1(Ах) =А ~(Ах') =(А 1А)х'=х'. В этом разделе мы будем иметь дело в основном с системами линейных уравнений, матрица А которых невырождена, или, что в соответствии с теоремой 28.1 то же, ранг матрицы А равен количеству неизвестных в системе линейных уравнений п.
Имеются и другие ситуации, с которыми мы вкратце познакомимся. Если количество уравнений меньше количества неизвестных (или, говоря более общенно, ранг матрицы А меньше и), такая система линейных уравнений называется Глава 28. Работа с матрицами 841 педооєределенной (илдеп3е1епп(пей). Недоопределенные системы линейных уравнений обычно имеют бесконечно много решений, хотя решение вообще может не существовать, если уравнения несовместимы друг с другом.
Если же количество уравнений превышает количество неизвестных, такая система линейных уравнелпй на.-.»~лается иереоиределенной (очетде1епп(пей), и может не иметь решений. Поиск хорошего приближенного решения переопределенных систем линейных уравнений представляет собой важную задачу, которая рассматривается в разделе 28.5. Вернемся к нашей задаче решения системы линейных уравнений Ах = Ь из п уравнений с п неизвестными. Одним из путей решения системы является поиск обратной матрицы А " и умножение на нее обеих частей уравнения, что даст нам А 1Ах = А 1Ь, или х = А 1Ь. Такой подход на практике отвергается в первую очередь из-за его численной неустойчивости.
К счастью, другой способ решения — 1ЛЗР-разложение — численно устойчив и быстрее работает. Обзор 1А)Р-разложения Идея, лежащая в основе ШР-разложения, состоит в поиске трех матриц Т„(7 и Р размером и х и, таких что РА=ГУ, (28.19) где ° Т вЂ” единичная нижне-треугольная матрица, ° У вЂ” верхне-треугольная матрица, ° Р— матрица перестановки. Матрицы Т, (7 и Р, удовлетворяющие уравнению (28.19), называются ьс7Рразложением (1Л)Р десотрозйюп) матрицы А. Мы докажем, что всякая невырожденная матрица А допускает такое разложение. Преимущество вычисления Ы1Р-разложения матрицы А основано на том, что система линейных уравнений решается гораздо легче, если ее матрица треугольна, что и выполняется в случае матриц Ь и У. Найдя 1Л)Р-разложение матрицы А, мы можем решить уравнение (28.17) Ах = Ь путем решения треугольной системы линейных уравнений, как показано далее.
Умножая обе части уравнения А х = Ь на Р, мы получим эквивалентное уравнение Р А х = Р Ь, которое в соответствии с упражнением 28.1-5 эквивалентно перестановке уравнений из (28.16). Используя разложение (28.19), получаем Ьих = РЬ. Теперь мы можем решить полученное уравнение, решая две треугольные системы линейных уравнений. Обозначая у = (7х, где х — решение исходной системы Часть Ч]1.
Избранные темы линейных уравнений, мы сначала решаем нижне-треугольную систему линейных уравнений Тулл~ Ь, (28.20) находя неизвестный вектор у с помо1цью "прямой подстановки". После этого, имея вектор у, мы решаем верхне-треугольную систему линейных уравнений (28.21) Ух=у, находя х при помощи "обратной подстановки".
Вектор х и есть решение исход- ной системы линейных уравнений Ах = Ь, поскольку матрица перестановки Р обращаема (см. упражнение 28.1-5): Ах=Р ~1Ух=Р ~1У=Р 1РЬ=Ь. Теперь рассмотрим, как работают прямая и обратная подстановки, а затем приступим к задаче вычисления Шр-разложения.
Прямая и обратная подстановки = ь.]й, ь 121 Ьл]з] ~ У1 121У1 + У2 131У1 + 132У2 + Уз 1 1У1 + 1лзуз + 1ьзуз + ''' + Ул = Ь ]л] Мы можем найти значение у1 непосредственно, поскольку первое уравнение гласит, что у1 = ь 11]. зная У1, мы можем подставить его во второе уравнение и найти У2 Ьл]2! 121 У1 Теперь мы можем подставить в третье уравнение два найденных значения — у1 и уз и получить Уз = Ьл]з] (121У1 + 1ззуз) ° Прямая подстановка (1опчап] зпьз1]щ1]оп) позволяет решить нижне-треугольную систему линейных уравнений (28.20) для данных Ь, Р и Ь за время с1 1пз).
Для удобства мы представим перестановку Р в компактной форме при помощи массива н [1..п]. Элемент я 11] при г = 1, 2,..., и указывает, что Р; ];] = 1 и Р," = = 0 для 1 ф я ]г]. Таким образом, в матрице РА на пересечении 1-ой строки и т'-го столбца находится элемент а 1;], а 1-ым элементом РЬ является Ь„];]. Поскольку Т, — единичная нижне-треугольная матрица, уравнение (28.20) можно переписать следующим образом: Глава 28.
Работа с матрицами 843 В общем случае для поиска у; мы подставляем найденные значения уы у2,..., у; 1 в г-е уравнение и находим Обратная лодслгоновка (Ьаск япЬзй1цйоп) аналогична прямой. Для данных У и у мы сначала решаем и-ое уравнение, а затем идем в обратном направлении к первому уравнению.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
