Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 174
Текст из файла (страница 174)
На рис. 28.1 показан процесс работы процедуры 1ЛЗ 1)нсомвоз!т!о!4. На рис. 28.1а показана исходная матрица, на рис. 28.1б-г — шаги рекурсии. Веду!ций элемент выделен черным цветом, а вычисляемые элементы матриц У и Ь— серым. На рис. 28.1д показан окончательный результат 1.1)-разложения. В приведенной реализации используется стандартная оптимизация, состоящая в том, что значащие элементы матриц У и 2 хранятся на месте элементов матрицы А, т.е. мы устанавливаем соответствие между каждым элементом а4 и либо 1!5 (если 1 > 7), либо и4 (если 1 < 2) и обновляем матрицу А так, что при выходе из процедуры она будет содержать значащие элементы матриц У и Ь. Для этого в псевдокоде достаточно заменить все обращения к и и 1 на обращения к а; нетрудно убедиться, что такое преобразование кода сохраняет его корректность.
Глава 28. Работа с матрицами матрицы А для того, чтобы избежать деления на О. Причем нежелательно не только деление на О, но и просто на малое число, даже если матрица А невырождена, поскольку в результате понижается численная устойчивость вычислений. В связи с этим в качестве ведущего элемента следует выбирать наибольший возможный элемент. Математические основы 1Л1Р-разложения аналогичны 1Л1-разложению.
Нам дана невырожденная матрица А размером п х и, и нам требуется найти матрицу перестановки Р, единичную нижне-треугольную матрицу Ь и верхне-треугольную матрицу У такие, что Р А = Ь Г/. Перед разделением матрицы А на части, как мы делали при вычислении 1Л)-разложения, мы перемещаем ненулевой элемент, скажем, аы, откуда-то из первого столбца матрицы в позицию (1, 1) (если первый столбец содержит только нулевые значения, то матрица вырождена, поскольку ее определитель равен О (см. теоремы 28А и 28.5)). Для сохранения множества исходных линейных уравнений мы меняем местами строки 1 и й, что эквивалентно умножению матрицы А на матрицу перестановки Я слева (см.
упражнение 28.1-5). Тогда мы можем записать ЯА как сА=(, ), где п = (азыазм...,аь маы,аь+м...,а„1) (1с-й элемент заменен первым), ю~ = (аьз, аьз,..., аь„), а А' — матрица размером (и — 1) х (и — 1). Поскольку ая1 ф О, мы можем выполнить те же преобразования, что и при 1Л1-разложении, не опасаясь деления на О: о А' и/аи 1„~ О А' — пиГ/аы Как мы видели в 1.П-разложении, если матрица А невырождена, то невы- рождено и дополнение Шура А' — сит/аы.
Таким образом, мы можем индуктивно найти его 1Л)р-разложение, дающее единичную нижне-треугольную матрицу К верхне-треугольную матрицу 1А' и матрицу перестановки Р' такие, что Р' (А' — сшт/и„,) = ~' У' Определим матрицу которая является матрицей перестановки в силу того, что она представляет собой произведение двух матриц перестановки (см. упражнение 28.1-5).
Мы имеем Часть Ч1!. Избранные темы 850 <'-') "= О Р' и/аьз 1„1 О А' — иихф/аы Р'и/аы Р' О А' — итит/аы < 10~(аы 7Ю Р'и/аы 1„~ О Е'У' Р'и/ам Ь' О У' РА = Ц ПРИг> 7', а; сн приз(з. ВЛЗР ВесОмРОБ!т!Он(А) 1 и ~ — гож ~А1 2 1огг — 1 1оп 3 до тг~г~ — г 4 1ог й - 1 1о и 5 бор -О б 1ог г' — й то и 7 оо 11(а;ь( > р что и дает нам искомое ШР-разложение. Поскольку Ь' — единичная нижне-треугольная матрица, такой же будет и Ь, и поскольку à — верхне-треугольная матрица, такой же будет и У. Заметим, что в отличие от 1Л7-разложения, и вектор-столбец и/аы, и дополнение Шура А' — июг/аы должны умножаться на матрицу перестановки Р'. Как и ранее, в псевдокоде 1.17Р-разложения рекурсия заменяется итерацией.
В качестве усовершенствования непосредственной реализации рассмотренной рекурсии матрицу перестановки Р мы представляем массивом и, где и [г] = 7 означает, что 1-я строка массива Р содержит 1 в столбце 7. Мы также реализуем код, который вычисляет Ь и У на месте матрицы А, т.е. по окончании работы процедуры Глава 28. Работа с матрицами 851 треп р — [ага[ Й' -г' 8 9 10 11 12 13 14 15 16 17 18 Ыр=О тпеп еггог "Матрица вырождена" Обмен к[к] + |т[й'] аког г' - 1 1о и до Обмен ам ~ ам; 1ог 1 - Й + 1 то п Йо а;» — агя/а~ 1ог 7 - /с+ 1 1о т1 йо а;~ об — а;ьаьу На рис.
28.2 продемонстрирована работа процедуры 1ЛР 13всомгоь171ои по разложению матрицы. На рнс. 28.2а показана исходная матрица с тождественной перестановюй строк (массив перестановок показан слева от матрицы). На рис. 28.2б показан выбор максимального ведущего элемента и соответствующий обмен строк. заштрихованные столбец и строка представляют с и иР. На рнс. 28.2в показано деление вектора с на ведущий элемент и вычисление дополнения Шура. Линии на рисунке делят матрицу на трн части: элементы У над линией, элементы Ь слева от линии и элементы дополнения Шура в правой нижней части. На рис.
28.2г-е показан второй шаг вычисления 1ЛЗР-разложения, а на рис. 28.2ж-и — третий шаг. На рис. 28.2к представлен окончательный результат 1Л)Р-разложения Р А = Ь У. Массив я инициализируется в строках 2-3 тождественной перестановюй. Внешний цикл 1ог, начинающийся в строке 4, реализует рекурсию. При каждом выполнении тела внешнего цикла в строках 5-9 определяется элемент амь с наибольшим абсолютным значением в текущем первом столбце (столбце й) матрицы размером (и — й+ 1) х (п — й+ 1), разложение которой должно быть найдено. Если все элементы текущего первого столбца нулевые, в строках 10-11 сообщается о вырожденности матрицы. Далее мы делаем амь ведущим элементом.
Для этого в строке 12 выполняется обмен элементов я [й] и и [й'] массива я, а в строках 13-14 — обмен й-ой и й'-ой строк матрицы А. (Мы выполняем обмен строк полностью, поскольку, как говорилось в изложении метода, на Р' умножается не только дополнение Шура А' — еюг/пы, но и вектор с/аы.) Наконец, в строках 15-18 вычисляется дополнение Шура (практически так же, как и в строках 4-9 процедуры 1Л1 ЭПСОМРОщтЮН, с тем отличием, что вычисленные значения заносятся в матрицу А, а не в отдельные матрицы Ь и У). В силу тройной вложенности циклов время работы процедуры Ы1Р 0псомюз171сяч равно О (пз), т.е.
оно точно такое же, как и в случае процедуры 1Л3 1)псом- гов1710Х. Следовательно, выбор ведущего элемента приводит к увеличению времени работы не более чем на постоянный множитель. Часть Ч2!. Избранные темы 852 з~~', " 0 2 00 ~4, —, .2 34 4! Р) © 522 '4'; .2' 3 ' 4 4 '2.' 0 2 00 3 ф 5' .',!':. П' Окб 0 04..2 04 -02 !4 ~:Н)32 - ! 4.2 436 О) ,'3) 5 4 11Т! 3: г~ 04 ф~ а4 ! )4 -02 ~ -1 42 -О4 о )31 5 5 4 ! ! '3 4 ~ ~02)Р,04..4-0,2 а4 ~ О.. еа -32 -О 2 ~ -') ': 4 2 0 б )3) 5 5 О4 ~ф~ 0.4 .:"0,2, )2) 00 .0',2 )Л -.3,2 .02 05 н ~3) 5 5 ! З4 1-2 04 04 0 1! -12 ~4' ,н!2 0.5 ф -0'" 4 5 4 )4) 2 0.-1Е -0.5 2 0 2 3 3 4 5 5 4 -1 -2 3.4 А О.б ! о о о -2 04 1 0 0 2 -0.2 0.5 ! 0 О.б 0 0.4 1 е к) Рис.
28.2. Работа процедуры П)Р ЭЕСОМРОЗ)Т10Н Упражнения 28.3-1. Решите при помощи прямой подстановки уравнение 1 О О 4 1 Π— 6 5 1 х! хз 28.3-2. Найдите Ш-разложение матрицы 0 0 1 0 1000 0001 0 1 0 0 4 -5 6 8 -6 7 12 -7 12 5 5 0 -2 0 0 0 0 4 2 0.4 -0.2 4 -0.5 0 -3 Глава 28. Работа с матрицами 853 28.3-3. Решите с помощью 1,1)Р-разложения систему линейных уравнений Х1 12 хз = 9 кз 5 1 5 4 2 О 3 5 8 2 28.3-4.
Как выглядит 1ЛЗР-разложение диагональной матрицы? 28.3-5. Как найти 1Л)Р-разложение матрицы перестановки? Докажите его единственность. 28.3-6. Покажите, что для всех п > 1 существует вырожденная матрица размером и х п, имеющая 1Л-разложение. 28.3-7. Необходимо ли выполнение тела внешнего цикла 1ог в процедуре 1Л) Пясомроятюн при ?с = п? А в процедуре 1ЛЗР 0нсомроятюн? 28.4 Обращение матриц На практике для решения систем линейных уравнений обращение матриц не используется, вместо этого применяются другие, численно более устойчивые методы, например, )Л1Р-разложение. Тем не менее, задача обращения матриц имеет как теоретический, так и сугубо практический интерес.
В этом разделе мы покажем, что для обращения матриц можно использовать уже рассмотренный нами метод 1.1)р-разложения. Мы также докажем, что умножение матриц и обращение матрицы — задачи одинаковой сложности, так что для решения одной задачи мы можем использовать алгоритм для решения другой, чтобы получить одинаювое асимптотическое время работы. В частности, мы можем применить алгоритм Штрассена для обращения матриц (к слову, в своей работе Штрассен преследовал цель ускорить решение систем линейных уравнений). Вычисление обратной матрицы из ЬЮР-разложения Предположим, что у нас имеется 1Л1Р-разложение матрицы А на три матрицы Т, У и Р такие, что РА = Т У. Используя процедуру 1Л)Р Боьчн, мы можем решить уравнение вида Ах = Ь за время 9 (пз).
Посюльку 1.11Р-разложение зависит толью от А, но не от Ь, мы можем использовать ту же процедуру для решения другой системы линейных уравнений вида Ах = Ь' за то же время 6 (пз). Обобщая, имея 1ЛЗР-разложение матрицы А, мы можем решить /с систем линейных уравнений с одной и той же матрицей А за время О (кпз). Уравнение АХ = Х„ (28.24) Часть Ч11. Избранные темы 854 можно рассматривать как множество из п различных систем линейных уравнений вида Ах = б. Эти уравнения позволяют найти матрицу Х, обратную матрице А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
