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