Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 175
Текст из файла (страница 175)
Обозначим через Х; 1-ый столбец Х, и вспомним, что 1-ым столбцом матрицы 1„является единичный вектор е,. Мы можем найти Х в уравнении (28.24), использовав ШР-разложение для решения набора уравнений АХ; = е; для каждого Х; в отдельности. Поиск каждого столбца Х; требует времени 9 (пз), так что полное время вычисления обратной матрицы Х на основе Н1Р-разложения исходной матрицы А требует времени 9 (пз). Поскольку 1ЛР-разложение А также вычисляется за время 6 (пз), задача обращения матрицы решается за время 9 (пз) Умножение матриц и обращение матрицы Теперь мы покажем, каким образом можно использовать ускоренное умножение матриц для ускорения обращения матрицы (это ускорение имеет скорее теоретический интерес, чем практическое применение).
В действительности мы докажем более строгое утверждение — что умножение матриц эквивалентно обращению матрицы в следующем смысле. Если обозначить через М(п) время, необходимое для умножения двух матриц размером и х п, то имеется способ обратить матрицу размером и х п за время О (М (и)). Кроме того, если обозначить через 1 (и) время, необходимое для обращения матрицы размером п х и, то имеется способ перемножит две матрицы размера п х и за время О (1(п)). Мы докажем эти утверждения по отдельности. Теорема 28.7 (Умножение не сложнее обращения).
Если мы можем обратить матрицу размером п х и за время 1 (и), где 1 (и) = Й (пз) и 1 (и) удовлетворяет условию регулярности 1(Зп) = О (1(п)), то мы можем умножить две матрицы размера и х п за время О (1 (и)). Доказательство. Пусть А и  — матрицы размером и х и, произведение которых С мы хотим найти. Определим матрицу Р размером Зп х Зп следующим образом: 1„А О Р= О 1 В О О 1„ Обратная к Р матрица имеет следующий вид: 1„-А АВ Р ~= О 1„-В О О 1 Глава 28.
Работа с матрицами 855 так что мы можем вычислить произведение АВ как верхнюю правую подматрицу размера и х т1 матрицы Р '. Матрицу В мы можем построить за время 9 (пз) = 0 (1 (и)), а обратить ее— за время 0 (1(Зт1)) = 0 (1(т1)) в соответствии с условием регулярности 1 (и). Таким образом, мы получаем М (п) = 0 (1(п)). Н Заметим, что 1(и) = 0 (и'18 п) удовлетворяет условию регулярности при любых константах с > О и Н > О. Доказательство того, что обращение матрицы не сложнее умножения, опирается на неюторые свойства симметричных положительно определенных матриц, которые мы докажем в разделе 28.5. Теорема 28.8 (Обращение не сложнее умножения).
Предположим, что мы можем умножить две действительные матрицы размером т1 х и за время М (т1), где М (и) = й (т1з) и, кроме того, удовлетворяет условию регулярности М (и + Й) = = 0(М(п)) для произвольного О < )с < и, а также М(т1/2) < сМ(т1) для некоторой константы с < 1/2. В таком случае мы можем обратить любую действительную невырожденную матрицу размером т1 х и за время О (М (т1)). Таким образом, выбрав 1с так, чтобы величина и+ й была степенью 2, мы увеличиваем исходную матрицу до размера, представляющего собой степень 2, а обратную матрицу А ' получаем как часть обращенной матрицы большего размера. Первое условие регулярности М (11) гарантирует, что такое увеличение не вызовет увеличения времени работы более чем на постоянный множитель.
Предположим теперь, что матрица А размером и х п симметрична и положительно определенная. Разделим А на четыре матрицы размером т1/2 х т1/2: А= ( (28.25) Обозначив через Я дополнение Шура подматриць1 В в матрице А Я= — СВ 'С (28.2б) мы получим В-'+В-1СТВ-1СВ-1 -В-1СтВ-1 1 А '= (28.27) -Я 'СВ 1 в-1 Доказа1иеиьстао. Мы можем считать, что т1 — точная степень 2, посюльку для любого к > О Часть Ч11. Избранные темы 856 поскольку А А ' = 1„.
Приведенное выражение легко проверить непосредственным матричным умножением. Согласно леммам 28.9, 28.10 и 28.11 из раздела 28.5, если матрица А — симметричная положительно определенная, то существуют и матрицы В ' и Я 1, поскольку и В, и Я вЂ” симметричные положитель, т но определенные матрицы. Согласно упражнению 28.1-2, В 1Ст = (СВ 1) и В 1СтЯ 1 = (Я 'СВ 1) . Уравнения(28.26) и (28.27) могугтаким образом быть использованы для определения рекурсивного алгоритма, требующего четыре умножения матриц размером и/2 х и/2: С.В ', (СВ-1) . Ст Я' (СВ'), (СВ ')т. (Я 'СВ ') .
Таким образом, для обращения симметричной положительно определенной матрицы размером и х и надо инвертировать две матрицы размером и/2 х и/2 (В и Я), выполнить четыре указанных умножения матриц размером и/2 х и/2 (это умножение можно осуществить при помощи алгоритма умножения матриц размером п х п)„а также выполнить дополнительные действия по извлечению подматриц из А (стоимость О (пз)) и некоторое постоянное количество сложений и вычитаний матриц размером и/2 х и/2.
В результате мы получаем следующее рекуррентное соотношение: Х (и) < 21 (и/2) + 4М (и) + О (и ) = 21 (и/2) + 9 (М (и)) = О (М (и)) . Первое равенство в приведенном соотношении выполняется в силу того, что М (и) = Й (пз), а второе получается потому, что второе условие регулярности, накладываемое в теореме на М (и), позволяет нам использовать случай 3 теоремы 4.1. Нам остается доказать, что асимптотическое время умножения матриц может быть получено для обращения невырожденной матрицы А, которая не является симметричной и положительно определенной.
Основная идея заключается в том, что для любой невырожденной матрицы А матрица Ат А симметричная (согласно упражнению 28.1-2) и положительно определенная (в соответствии с теоремой 28.6). Все, что остается — это привести задачу обращения матрицы А к задаче обращения матрицы Ат А. Такое приведение основано на наблюдении„что если А — невырождениая матрица размера и х и, тогда .4-1 = (Ат.4) ' Ат Глава 28. Работа с матрицами 857 поскольку ((Ат ~) 'Ат) ~ (АтА)-~ ( ~т ~) а обратная матрица единственна. Следовательно, мы можем вычислить А 1, сначала находя Ат для получения симметричной положительно определенной матрицы АтА, затем обращая эту матрицу с помощью описанного выше рекурсивного алгоритма, а затем умножая полученный результат на Ат.
Каждый из перечисленных шагов требует 0 (М (и)) времени, так что обращение любой невырожденной матрицы с действительными элементами может бьггь выполнено за время 0 (М (и)). Доказательство теоремы 28.8 наводит на мысль о том, каким образом можно решать систему уравнений Ах = Ь с невырожденной матрицей А при помощи Ш-разложения, без выбора ведущего элемента. Для этого обе части уравнения нужно умножить на Ат, получая уравнение (АтА) х = АтЬ.
Такое преобразование не влияет на х в силу обращаемости матрицы Ат, а тот факт, что матрица АтА является симметричной положительно определенной, позволяет использовать для решения метод Ш-разложения. После этого применение прямой и обратной подстановки с использованием правой части уравнения, равной АтЬ, даст нам решение х исходного уравнения. Хотя теоретически этот метод вполне корректен, на практике процедура ШР ПисОмвоыт1он работает существенно лучше.
Вопервых, она требует меньшего количества арифметических операций (отличающееся постоянным множителем от количества операций при описанном методе), и во-вторых, численная устойчивость ШР ПесОмгОз|ткзн несколько выше. Упражнения 28.4-1. Пусть М(п) — время, необходимое для умножения двух матриц размером п х и, а Я(п) — время, необходимое для возведения матрицы размером и х и в квадрат. Покажите, что умножение матриц и возведение матрицы в квадрат имеют одну и ту же сложность: из М(п)- алгоритма умножения матриц вытекает О (М (и))-алгоритм возведения матрицы в квадрат, а о' (и)-алгоритм возведения матрицы в квадрат дает О (Я (и))-алгоритм умножения матриц. 28.4-2. Пусть М (и) — время, необходимое для умножения двух матриц размером п х и, а Ь (и) — время, необходимое для ШР-разложения матрицы того же размера. Покажите, что умножение матриц и ШР-разложение имеют одинаковую сложность, т.е.
что из М (и)-алгоритма умножения матриц вытекает 0 (М (и))-алгоритм ШР-разложения, а Т (и)-алгоритм ШР-разложения дает 0 (Е (и))-алгоритм умножения матриц. 858 Часть ЧП. Избранные темы 28.4-3. Пусть М (и) — время, необходимое для умножения двух матриц размером и х и, а Р (и) — время, необходимое для вычисления определителя матрицы того же размера. Покажите, что умножение матриц и вычисление определителя имеют одинаковую сложность, т.е. что из М (и)-алгоритма умножения матриц вытекает О (М (и))-алгоритм вычисления определителя, а Р (и)-алгоритм вычисления определителя дает О (Р (и))-алгоритм умножения матриц. 28.4-4. Пусть М (и) — время, необходимое для умножения двух булевых матриц размером и х и, а Т (и) — время, необходимое для поиска транзитивного замыкания булевой матрицы размером и х п (см.
раздел 25.2). Покажите, что М (п)-алгоритм умножения булевых матриц дает О (М (и) 18 п)-алгоритм поиска транзитивного замыкания, а Т (п)-алгоритм поиска транзитивного замыкания приводит к О (Т (и))-алгоритму умножения булевых матриц. 28.4-5. Применим ли основанный на теореме 28.8 алгоритм обращения матриц к матрицам над полем целых чисел по модулю 2? Поясните свой ответ. *28.4-6. Обобщите алгоритм обращения матриц из теоремы 28.8 для матриц с комплексными числами, и докажите корректность вашего обобщения. (Указание: вместо транспонирования матрицы А воспользуйтесь сопряженно-транснонированной (соп)пйате вальрозе) матрицей А', которая получается из исходной путем транспонирования и замены всех элементов комплексно сопряженными числами.
Вместо симметричных матриц рассмотрите эрнитовы (Неппй1ап) матрицы, обладающие тем свойством, что А = А*.) 28.5 Симметричные положительно определенные матрицы и метод наименьших квадратов Симметричные положительно определенные матрицы обладают рядом интересных и полезных свойств. Например, они невырождены и их Ш-разложение можно выполнить, не опасаясь столкнуться с делением на О. В этом разделе мы докажем ряд важных свойств симметричных положительно определенных матриц и покажем их применение для получения приближений методом наименьших квадратов.
Первое свойство, которое мы докажем, пожалуй, наиболее фундаментальное. Лемма 28.9. Любая симметричная положительно определенная матрица является невырожденной. Глава 28. Работа с матрицами 859 Доказательство. Предположим, что матрица А вырождена. Тогда, согласно след- ствию 28.3, имеется такой ненулевой вектор х, что Ах = О. Следовательно, хтА х = О, и А не может быть положительно определенной. Доказательство того факта, что 1Л)-разложение симметричных положительно определенных матриц можно выполнить, не опасаясь столкнуться с делением на О, более сложное. Мы начнем с доказательства свойств некоторых определенных подматриц А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
