1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 52
Текст из файла (страница 52)
Это увеличит порядок матриц не более чем вдвое и, значит, постоянную увеличит не более чем в 7 раз. Таким образом, Т(п) есть 0(п"е') для всех иЪ1, П В теореме 6.1 нас интересовал только порядок роста функции Т(и). Но для того, чтобы выяснить, для каких значений п алгоритм Штрассена работает быстрее обычного алгоритма, надо найти соответствующую мультипликативную постоянную. Однако если п не является степенью числа 2, то простое вложение каждой исходной матрицы в матрицу, порядок которой равен степени числа 2, ближайшей к п сверху, даст слишком большую постоянную. Вместо этого можно вложить каждую матрицу в матрицу порядка 2гг для некоторого небольшого числа г и р раэ применить лемму 6.4, умножая (гхг)-матрицы обычным 0(г')-методом.
Или, действуя иначе, можно было бы написать более общий рекурсивный алгоритм, который при четном п расщеплял бы каждую матрицу на четыре подматрицы, как и раньше, а при нечетном и сначала увеличивал бы порядок матриц на 1. Гл. а умножения мАтРиц Следует подчеркнуть, что„вычислив мультипликативную постоянную, мы найдем границу только на число арифметических операций.
Чтобы сравнить метод Штрассена с обычным методом умножения матриц, надо также учесть дополнительную сложность процедур, связанных с поиском элементов матриц. 6.3. ОБРАЩЕНИЕ МАТРИЦ В данном разделе мы покажем, что задачу обращения матриц из определенного класса можно свести к задаче умножения матриц. Этот класс включает все обратимые треугольные матрицы, но не все обратимые матрицы вообще. В дальнейшем мы обобщим полученный результат на произвольные обратимые матрицы. В данном разделе и в равд. 6А и 6.5 рассматриваются матрицы с элементами из некоторого поля. Лемма 6.6.
Пусть матрица А разбита пюкг 11 13 Предположим, чгпо существует А,,', Обозначим А„— А„А;,' А„ через Ь и допустим, что Ь-' существует. Тогда А,,'+А,,'А„Ь 'А„А,,' — А,,'А„Ь ' 1 й $1 11 Д о к а з а т е л ь с т'в о. С помощью очевидных алгебраических преобразований можно показать, что откуда О(ВЬ' — АА,,' А,,'+А,,'А„Ь 'А„А,,' — А,,'А„Ь '1 В В 5 Лемму 6.5 нельзя применять ко всем невырожденным матрицам. Например, (ихп)-матрица перестановки А, у которой А [1, ))=1, если 1=п — 1+1, и А 11, 1)=0 в противном случае, невырожденна, но де1(А11)=0 для любой главной подматрипы А„.
Тем ие менее лемма 6.5 применима ко всем невырожденным нижним и верхним треугольным матрицам. Ень ИВП-РАЗЛОЖЕИИЕ МАТРИцы Лемма 6.6. Если А — невырожденная верхняя (нижнял) треугольная матрица, то матрицы А„и Ь из леммы 6.5 обратимы и являются верхними (нижними) треугольными. Д о к а э а т е л ь с т в о. Допустим, что А — верхняя треугольная матрица. Для случая нижней треугольной матрицы доказательство аналогично. Очевидно, что А „— невырожденная верхняя треугольная матрица и, значит, А,,' существует. Далее заметим, что А„=О. Поэтому Ь=Азз — Аю А„' А„=А„— невырожденная верхняя треугольная матрица. П Теорема 6.2.
1!усть М(п) — время, требуемое для умножения двух (пхп)-матриц. Если 8М(т))М(2т))4М(т) для всех т, то найдется такая постоянная с, что обращение любой невырожденной верхней (нижней) треугольной (пхп)матрицы А можно вычислить за время сМ (и). Д ока з а тел ь с та о. Докажем теорему для случая, когда п — степень числа 2. Очевидно, что в противном случае можно вложить А в матрицу вида [. ~.1 где т+п(я 2п) является степенью числа 2.
Тем самым, увеличив постоянную с не более чем в 8 раз, мы установим наш результат для произвольного и '). Если и — степень числа 2, можно разбить А на четыре ((п/2)гс х(п/2))-подматрипы и рекурсивно применить формулу (6.3). Заметим, что Ам=О, так что А=А„. Следовательно, для обращения треугольных матриц А„и Л требуется 2Т(п/2) времени, для двух нетривиальных умножений еще 2М (и/2) времени и, для того чтобы поставить минус в правом верхнем углу, еще пз/4 операций. Из условия теоремы и неравенства М(1))1 выводим, что пз/4(М(п/2). Таким образом, Т (1) = 1, Т(п)~(2Т ( — )+ ЗМ Я для и) 2. (6А) Легко доказать, что из (6.4) следует Т(п)(ЗМ (и)/2. П 6.4.
НВП-РАЗЛОЖЕНИЕ МАТРИЦЫ Один из эффективных методов решения системы линейных урав. ненни состоит в применении так называемого НВП-разложения. ') И опять более тщательный анализ дает для произвольного л постоянную с, несильно отличающуюся от наилучшей известной постоянной для случая, когда л — степень числа 2. Гл. е. умножв ниц млтпиц Определение.
НВ-разложениелс ') (тхи)-матрицы А, т(п, называется представление ее в виде А =Т,У, где  — нормированная нижняя треугольная (тхт)-матрица, а У вЂ” верхняя треугольная (т Х п)-матрица. Уравнение Ах=Ь, где А — это (и)сп)-матрица, х — п-мерный вектор-столбец неизвестных, а Ь вЂ” п-мерный вектор-столбец, можно решить, сначала НВ-разложив А в произведение Ш в предположении, что это возможно.
Затем представим Ах=Ь в виде Т,Ух= Ь. Чтобы получить решение х, решим сначала (.у Ь относительно у, а затем Ух=у относительно х. Трудность применения этого метода заключается в том, что у матрицы А может не быть НВ-разложения, даже если она невырожденна. Например, матрица [1 о1 невырожденна, но у нее нет НВ-разложения. Однако если матрица А невырожденна, то найдется такая матрица перестановки Р, что АР-' имеет НВ-разложение. Изложим алгоритм, который по любой невырожденной матрице А находит такие матрицы Ь, У и Р, что А =1,УР.Матрицы Т„У и Р образуют НВП-разложение *) матрицыА. Алгоритм 6.1. НВП-разложение Вход. Невырожденная (пхп)-матрица М, п — степень числа 2.
Выход. Матрицы 1„У и Р, для которых М=1 УР, причем Т.— нормированная нижняя треугольная матрица, У вЂ” верхняя треугольная и Р— матрица перестановки. Метод. Вызываем процедуру МНОЖИТЕЛЬ(М, и, п), где МНОЖИТЕЛЬ вЂ” рекурсивная процедура, показанная на рис. 6.4. При описании втой процедуры используются диаграммы на рис. 6.!в 6.3, где затемненная область матрицы представляет ту ее часть, о которой известно, что она состоит из одних нулей. Каждый рекурсивный вызов процедуры МНОЖИТЕЛЬ происходит на (тхр)-подматрице А (пуси)-матрицы М.
При каждом вызоне т есть степень числа 2 и т(р(п. Выходом этой процедуры являются три матрицы Т., У и Р, показанные на рис. 6.1. П Пример 6.3. Найдем НВП-разложение матрицы О О О 1 О О 2 О О 3 О О 4 О О О ') По первым буквам слов «нижняя» и «верхняя».— Прим. иерее. ') По первым буквам слов «нижняя», «верхняя» и «перестановка».— Прим. я«р«е. 2Ь4 е.а ннп-Рхзложенне ИАтРнцзи и щ А т ° т Г/ л Рис. 6,1.
Выход процедуры МНОЖИТЕЛЬ. т/2 2 т/2 р-и/2 р т/2 т/2 е Рис. 6.2. Шаги процедуры МНОЖИТЕЛЬ: а — начальное разбиение матрицы А; б — разложение матрицы А после первого вызова процедуры; в — разбиение матриц (/т и 0; г — обнуление нижнего левого угла матрицы О. (Отметим, что .'можно рассматривать как нормированную нижнюю(или верхнюю) треугольную матрицу.) Н т/2 Г т/2 ГГ' ~/ и/2 б т/2 С и/2 1 днтакаги, Е т/2 р ! Осшаатшд ГЛ. Е.
ММИОЖЕНИЕ МАТРИЦ т/2 р-т/2 т/2 р- /г т/2 р-т/2 Р т/2 т/2 Р т/2 т/2 И т/2 / т/г И , /г С т/2 С и. р- /г Рис. 6.3. Завершение процедуры МНОЖИТЕЛЬ: а — построение матрицы РМ б — разложение матриц г/, и й; в — разложение матрицы Л. Начнем с вызова процедуры МНОЖИТЕЛЬ (М, 4, 4), которая сразу же вызывает МНОЖИТЕЛЬ О 2, 4 . Взяв в качестве матрицы А первый аргумент этого вызова, вызываем МНОЖИТЕЛЬ ([О О О 1], 1, 4). В результате получаем О О О 1 Ь,= Щ и, =~1 О О О), О ! О О 1 О О О последняя матрица переставляет столбцы 1 и 4. вл. ивп.влзложянив млтгнцы 1.
2. 10. 11. 12. 13. ргосебиге МНОЖИТЕЛЬ(А, я, Р): И и=1 1Ьеп Ьей!п пусть г,=!1] (т. е. Ь вЂ” нормированная (1х1)-матрица; найти, если можно, столбец с матрицы А с ненулевым элементом, и пусть Р будет (рхр)-матрицей, переставляющей столбцы 1 и с; сопппеп1 Заметьте, что Р=Р ', пусть У =АР; ге(цгп (1., У, Р) епд е1зе Ьей(п разбить А на ((т~2)ХР)-матрицы В и С, как показано на рис. 6.2,а; вызвать МНОЖИТЕЛЬ(В,т/2, р), чтобы получить Тч, Уо Р;, вычислить 0=СР,', сопппеп1 В данный момент А можно записать как произведение трех матриц, показанных иа рис. 6.2,6; пусть Е и Р†перв т/2 столбцов соответственно матриц У, и 0 (рис.
6.2,г); вычислить 0=0 — ГЕ 'У;, сопппеп1 Заметьте, что первые т(2 столбцов матрицы 6 состоят из одних нулей. Матрицу А можно записать в виде произведения матриц, показанных на рис. 6.2,г; пусть С' — самые правые р — лп2 столбцов матрицы б; вызвать МНОЖИТЕЛЬ(6', т~2, р — ги/2) и получить ь„ У,ир,; пусть Р, будет(рхр)-матрицей перестановки, у которой в левом верхнем углу стоит 1 по а в правомнижнем Р, (рис. 6.3,а) ь Н=О,Р,", сопппеп1 В зто время матрицу, составленную из и, и о, можно записать так, как показано на рис. 6.3,б. Если в рис.
6.2,г подставить правую часть равен. ства иа рис. 6.3,6, то получится представление Гл. е. умиожвиив ИАтРИц матрицы А в виде произведения пяти матриц. Первые две из них — нормированные нижние треугольные, третья — верхняя треугольная, а последние две — матрицы перестановок. Умножим первые дае и последние две, чтобы получить искомое разложение матрицы А; пусть Š†э (пэхт)-матрица, состоящая из 7.„ О ~„ РЕ-' и 1,э (рис. 6.3,в); пусть У вЂ” зто (лтх р)-матрица, у которой в верхней части стоит Н, а в нижней 0 м и У, (рис. 6.3,а); пусть Р— произведение Р,Р;, ге1цгп (Ь, У, Р) епб 16.
17, рис. ели Процедура МНОЖИТЕЛЬ. В строке 7 вычисляем ') 0001 Р02ЧОО О=Я 0100 1000 В строке 8 имеем Е= [11 и Р= [0), так что после выполнения строки 9 6=0 = [0 О 2 0). Строка 10 дает 6'= [О 2 0]; следовательно, после строки 11 будет 6,=[Ц, У,=[2 О 01, В строке 12 1000 0010 0100 0001 а в строке 13 1 0 и =У,Р-, =[! О О 01 0 0 0 0 0 0 = ~! 0 0 0~.
1 0 0 ! т! В втом примере все матрицы перестаиовок окавывакмси равиыми своим обратиым. ае нвп.РАзложенне мАтРицы Таким образом, МНОЖИТЕЛЬ ! ! О 0 О~, 2, 4) выдает ~ГО О 011 ООО! 01'0200'''0100 1ООО Теперь возвращаемся к вызову МНОЖИТЕЛЬ ГМ, 4, 4) в строке Б, причем роль Г.ц У, и Р, играютсоответственноГ.,У и Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
