Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 191
Текст из файла (страница 191)
В строках 3 и 4 выполняется инициализация массива х, который после этого представляет тождественную перестановку. Внешний цикл 1ог, начинающийся в строке 5, реализует рекурсию. При каждой итерации внешнего цикла строки б-1О определяют элемент аь ь с наибольшим абсолютным значением в текущем первом столбце (столбец х) матрицы размером (и — х + 1) х (и — Iс + 1), 1Л)Р-разложение которой мы ищем. Если все элементы в текущем первом столбце нулевые, строки 11 и 12 сообщают о вырожденности матрицы.
Чтобы получить ведущий элемент, мы обмениваем х[)с'] с х[х] в строке 13, а также обмениваем строки 1с и )с' матрицы А в строках 14 и 15 процедуры, тем самым делая ведущим элемент оьы (Обмен строк выполняется полностью, поскольку в выводе данного метода выше на Р' умножается не только А' — осот/аы, но и о/аы.) Наконец в строках 16-19 вычисляется дополнение Шура, практически так же, как и в стро- Глава 28.
Рабата с матрицами 865 1 2 0 2 06 3 (()),!гб'':::,"::4!;:'::й;" 3 ()));~:~";:,';4!::"'-"!~, 2 3 3 4 -2 2 ("3:' 3 4 -2 2:фйУ 0 1.6 -3.2 3 (ьв 5 4 2 1 ".2:!, 0 2 0.6 1 (фй'" -2 0.4 —.2 4 -1 — 2 3.4 — 1 4,43.;;.( -2 3.4 — 1 4 зэ):22( -1 4.2 -4).6 (в) (а) 5 5 4 2 5 5 4 2 5 5 4 2 0.4 (Я(1) .ф,'Ф' '~(й.т 0.6 !",,;-'О..:: 1.6 -3.2 -0.2~,3! 4.2 -0.6 2 0.6 0 1.6 -3.2 1 0.4 (а)) 0.4 -0.2 4 -0.2 -1 4.2 -0.6 0.4 ®:(34:,;:.-;.6~2, 0.6 ~„';ОУ. 1.6 -3.2 -0.2 .'!Ой: 4 -05 (г) (ж) (н) (к) Рис. 28.2.
Работа процедуры (Л)Р-Овсомгоэ(тюн. (в) Входная матрица А с тождественной перестаневкой строк слева. Шаг 1 алгоритма находит, что элемент б (в черном круге в третьей строке) является ведущим лля первого столбца. (6) Выполнтотся обмен строк 1 и 3 и обновление матрицы перестановки. Зашгрихованные столбец н строка представляют е и тт. (в) Вектор е заменяется на с/6. и нюкняя правая час(ь матрицы заменяема дополнением Шура. Линии делят матрицу на три области: элементы (1 (вверху), элементы Ь (слева) и элементы дополнения Шура (внизу справа).
(г)-(е) Шаг 2. (ш)-(и» Шаг 3. На шаге 4 (последнем) не происходит никаких изменений. (к) ь()Р-разложение РА = 2(). ках 7 — ) 2 процедуры (ЛЗ-РВСОЫРО5(тЮЫ, с тем отличием, что здесь результаты работы записываются в матрицу А, без привлечения дополнительной памяти. В силу тройной вложенности циклов время работы процедуры )ЛЗРОесомро51т1ох равно е)(пз), т.е. оно точно такое же, как и в случае процедуры (Л)-()Всомрой)тюн. Следовательно, выбор веду(пего элемента приводит к увеличению времени работы не более чем на постоянный множитель.
гв згк зггв 3 5 5 4 2 1 0.4 -2 0.4 -0.2 2 0.6 0 1.6 -3.2 4 -0.2 05 (9 -05 5 5 4 2 0.4 -2 0.4 -0.2 -0.2 0.5 9 ((();5 0.6 0 (21(й):: -3.2 5 5 4 2 1 0.4 -2 0.4 -0.2 -О.2 ОЛ (((» Ву(й 0.6 0 ",ВА1 -3 Вбб Часть 171 Избранные темы Упражнении 28.1.1 Решите систему линейных уравнений с помощью прямой подстановки. 28.1.2 Найдите ЬП-разложение матрицы 12 -7 12 28.1.3 Решите систему линейных уравнений 203 хз = 9 с помощью Шр-разложения. 28.1.4 Как выглядит ШР-разложение диагональной матрицы? 28.1.5 Как найти ШР-разложение матрицы перестановки? Докажите его единственность. 28.1.
б Покажите, что для всех и > 1 существует вырожденная матрица размером и х и, имеющая Ш-разложение. 28.1. 7 Необходимо ли выполнение тела внешнего цикла 1ог в процедуре ШВвсомроз1т1оы при к = и? А в процедуре ШР-1Эвсомроштюм? 28.2. Обращение матриц Хотя на практике для решения систем линейных уравнений обращение матриц обычно не используется, а вместо этого применяются другие, численно более яб7 Глава 7а Рабоеа с матрицами устойчивые, методы, например ШР-разложение, иногда все же требуется вычислить обратную матрицу.
В этом разделе мы покажем, что для обращения матриц можно использовать уже рассмотренный нами метод ШР-разложения. Мы также докажем, что умножение матриц и обращение матрицы — задачи одинаковой сложности, так что для решения одной задачи мы можем использовать алгоритм для решения другой, получив прн этом одинаковое асимптотическое время работы. В частности, для обращения матриц мы можем применить алгоритм Штрассена из раздела 4.2 (к слову, в своей работе Штрассен преследовал цель ускорить решение систем линейных уравнений). Вычисление обратной матрицы из ШР-разложении Предположим, что имеется ШР-разложение матрицы А на три матрицы, Б, (7 и Р, такие, что РА = 1(7. Используя процедуру ШР-Боьус, мы можем решить уравнение вида Ах = Ь за время 9(пз).
Поскольку ШР-разложение зависит только ог А, но не от Ь, мы можем использовать ту же процедуру ШР-Яоьчп для решения другой системы линейных уравнений вида Ах = Ь' за дополнительное время 9(пз). Обобщая, имея ШР-разложение матрицы А, мы можем решить к систем линейных уравнений Ах = Ь, отличающихся только свободными членами Ь, за время 9(/спз). Уравнение АХ=1„ (28.10) определяющее матрицу Х, обратную А, можно рассматривать как множество из и различных систем линейных уравнений вида Аэ = Ь.
Эти уравнения позволяют найти матрицу Х, обратную матрице А. Более строго, обозначим 1-й столбец Х через Х, и вспомним, что 1-м столбцом матрицы 1„является единичный вектор еь Мы можем найти Х в уравнении (28.10), использовав ШР-разложение для решения набора уравнений АХ, = е; для каждого Х; в отдельности. При наличии ШР-разложения поиск каждого столбца Х, требует времени с1(пз), так что полное время вычисления обратной матрицы Х на основе ШР-разложения исходной матрицы А требует времени 9(пз). Поскольку ШР-разложение А также вычисляется за время сз(пз), задача вычисления обратной к А матрицы А з решается за время сз(пз).
Умножение матриц и обращение матрицы Теперь покажем, каким образом можно использовать ускоренное умножение матриц для ускорения обращения матрицы (это ускорение имеет скорее теоретический интерес, чем практическое применение). В действительности мы докажем более строгое утверждение — умножение матриц эквивалентно обращению матрицы в следующем смысле.
Если обозначить через М(п) время, необходимое для умножения двух матриц размером и х и, то можно обратить невырожденную матрицу размером и х п за время 0(М(п)). Кроме того, если обозначить через 1(п) время, необходимое для обращения матрицы размером и х и, то можно лба Часть Ьтд Избранные темы перемножить две матрицы размером и х и за время 0(Х(и)).
Мы докажем зги утверждения как две отдельные теоремы. Теорема 28.1 ХУмножение не сложнее обращения) Если можно обратить матрицу размером и х и за время 1(и), где 1(и) = П(из) и удовлетворяет условию регулярности 1(Зи) = 0(1(и)), то две матрицы размером и х и можно перемножить за время 0(1(и)). Доказательство. Пусть А и В представляют собой матрицы размером и х и, произведение которых С необходимо вычислить. Определим матрицу Р размером Зи х Зи как О Х„В Обратной к матрице Р является Р~= О 1„— В так что мы можем вычислить произведение АВ, просто взяв верхнюю правую подматрицу размером и х и из матрицы Р 1. Матрицу Р можно построить за время 6(из), которое представляет собой 0(Х(и)), поскольку мы считаем, что 1(и) = П(из), и обратить ее за время О(1(Зи)) = 0(1(и)) согласно условию регулярности, накладываемому на 1(и).
Таким образом, М(и) = О(1(и)). Заметим, что 1(и) = тз(и'18~и) удовлетворяет условию регулярности лри любых константах с > О и с1 > О. Доказательство того, что обращение матрицы не сложнее умножения, опирается на некоторые свойства симметричных положительно определенных матриц, которые мы докажем в разделе 28.3. Теорема 28.2 (Обращение не сложнее умножения) Предположим, что мы можем умножить две действительные матрицы размером и х и за время М(и), где М(и) = П(и~) и, кроме того, удовлетворяет условиям регулярности М(и+ и) = 0(М(и)) для произвольного О < я < и и М(и/2) < сМ(и) для некоторой константы с < 1/2. В таком случае мы можем обратить любую действительную невырожденную матрицу размером и х и за время О(М(и)). Доказательсзиво.
Здесь данная теорема доказывается для действительных чисел. В упр. 28.2.6 предлагается обобщить ее для комплексных матриц. Глава 2б. Работа с матрицами бб9 Можно считать, что п является точной степенью 2, поскольку мы имеем А О А з О А=( ) л'=( ). (28.11) Обозначив через В=Р— СВ 'С" (28.! 2) дополнение Шура матрицы А по отношению к подматрице В (ннформацию об этом виде дополнений Шура можно найти в разделе 28.3), имеем В т ~ / В '+В 'С В 'СВ ' — В 'С В (1 И / 1, -В-'СВ-' В-' / ' поскольку АА ' = Т„, как вы можете убедиться, перемножив матрицы. Матрица А симметрична и положительно определена, поэтому из лемм 28.4 и 28.5 из раздела 28.3 вытекает, что и В, и Я симметричны и положительно определены.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
