Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 192
Текст из файла (страница 192)
Таким образом, согласно лемме 28.3 из раздела 28.3 существуют обратные матрицы В ' и Я ', а согласно упр. Г.2.6 В ' и Я ' симметричны, так что (В ')т = В ' и (В ')т = Я '. Итак, мы можем вычислить подматрицы В, Т, У и И матрицы А з описанным далее способом (где все упоминаемые матрицы имеют размер и/2 х и/2). 1. Образуем подматрицы В, С, Ст и Р матрицы А. 2.
Рекурсивно вычислим обратную матрице В матрицу В '. 3. Вычислим произведение матриц И' = СВ ', а затем транспонируем его И~~, получив матрицу, эквивалентную В 1С (согласно упр. Г.1.2 и (В ) В '). 4. Вычислим сначала произведение матриц Х = Илс~, эквивалентное СВ ~с~, а затем — матрицу Я = Р— Х = Р— СВ 'С . 5. Рекурсивно вычислим обратную матрицу Я 1 и присвоим ее матрице И. для любого к > О. Таким образом, выбрав )с так, чтобы величина п + к была степенью 2, мы увеличиваем исходную матрицу до размера, представляющего собой степень 2, а искомую обратную матрицу А 1 получаем как часть обращенной матрицы большего размера. Первое условие регулярности М(п) гарантирует, что такое увеличение не вызовет увеличения времени работы более чем на постоянный множитель.
Предположим теперь, что матрица А имеет размер и х и и является симметричной и положительно определенной. Разобьем матрицу А и обратную к ней А ' на четыре подматрицы размером п/2 х и/2: ого Часть УП. Избранные тены б. Вычислим произведение матриц г' = Я 'Ис, равное Я ~СВ ', а затем транспонируем его Ут, что равно В зСтЯ с (согласно упр. Г.1.2 (В !)т = В ~ и (о' ) = Я ~).
Присвоим Т значение — У~, а !з — значение — г'. 7. Вычислим произведение матриц Я = И'~У, равное В 'С~Я 'СВ ~, и присвоим зт' значение В ~ + е . Таким образом, можно инвертировать симметричную положительно определенную матрицу размером п х и путем обращения двух матриц размером п/2 х и/2 в пп. 2 и 5, последующего выполнения четырех перемножений матриц размером п/2 х п/2 в пп. 3, 4, б и 7, а также выполнения дополнительных действий по извлечению подматриц из А, вставке подматриц в А ' ценой 0(пз), и константного количества сложений, вычитаний и транспоннрований матриц размером п/2 х и/2. В результате мы получаем следующее рекуррентное соотношение: Т(п) ( 27(п/2) + 4М(п/2) + 0(пз) = 27(п/2) + 9(М(п)) = 0(М(п)) . Вторая строка выполняется, поскольку из второго условия регулярности в формулировке теоремы вытекает, что 4М(п/2) ( 2М(п), и поскольку мы предполагаем, что М(п) = П(пз). Третья строка следует из того, что второе условие регулярности позволяет применить случай 3 основной теоремы (теоремы 4.!).
Остается доказать, что асимптотическое время умножения матриц может быть получено для обращения невырожденной матрицы А, которая не является симметричной и положительно определенной. Основная идея заключается в том, что для любой невырожденной матрицы А матрица АТА симметричная (согласно упр. Г.1.2) и положительно определенная (в соответствии с теоремой Гб). Все, что остается, — это привести задачу обращения матрицы А к задаче обращения матрицы АтА. Такое приведение основано на наблюдении, что если А является невырожденной матрицей размером и х и, то А-' = (АтА)-'Ат поскольку ((А А) ~А )А = (А А) ~(А А) = 1„, а обратная матрица единственна.
Следовательно, можно вычислить А ', сначала умножив Ат на А для получения симметричной положительно определенной матрицы АтА, а затем обратив эту матрицу с помощью описанного выше рекурсивного алгоритма и умножив полученный результат на Ат. Каждый из перечисленных шагов требует времени 0(М(п)), так что обращение любой невырожденной матрицы с действительными элементами может быть выполнено за время 0(М(п)).
Доказательство теоремы 28.2 наводит на мысль о том, каким образом можно решать систему уравнений Ах = 6 с невырожденной матрицей А с помощью Ы)-разложения, без выбора ведущего элемента. Для этого обе части уравнения нужно умножить на Ат, получив уравнение (АтА)х = Ато. Такое преобразова- 871 Глава 28. Работа о матрицами ние не влияет на х в силу обрашаемости матрицы Ат, а тот факт, что матрица АтА является симметричной положительно определенной матрицей, позволяет использовать для решения метод Ш-разложения.
После этого применение прямой и обратной подстановок с использованием правой части уравнения, равной АтЬ, дает решение х исходного уравнения. Хотя теоретически этот метод вполне корректен, на практике процедура 1Л)Р-Песоыроят1о~ч работает существенно лучше. Во-первых, она требует меньшего количества арифметических операций (отличающегося постоянным множителем от количества операций в описанном методе), а во-вторых, численная устойчивость 1ЛЗР-Пнсомроятюм несколько выше. Упражнения 2а.2.л Пусть М(п) — время, необходимое для умножения двух матриц размером и х и, а Я(п) — время, необходимое для возведения матрицы размером и х и в квадрат. Покажите, что умножение матриц и возведение матрицы в квадрат имеют одну и ту же сложность: из М(п)-алгоритма умножения матриц вытекает 0(М(п))- алгоритм возведения матрицы в квадрат, а э(п)-алгоритм возведения матрицы в квадрат дает 0(э(п))-алгоритм умножения матриц.
2В.2.2 Пусть М(ть) представляет собой время, необходимое для умножения двух матриц размером п х и. Покажите, что из существования алгоритма умножения матриц со временем работы М(п) вытекает существование алгоритма ШР-разложения со временем работы 0(М(п)), 2а.2.3 Пусть М(п) представляет собой время, необходимое для умножения двух матриц размером и х и, а через Р(п) обозначим время, необходимое для поиска детерминанта матрицы размером п х п.
Покажите, что умножение матриц и вычисление детерминанта, по сути, имеют одинаковую сложностзс из алгоритма умножения матриц со временем работы М(п) вытекает алгоритм поиска детерминанта за время 0(М(п)), а из алгоритма вычисления детерминанта за время Р(п) вытекает алгоритм умножения матриц за время 0(Р(п)). 2а.2.4 Пусть М(п) представляет собой время, необходимое для умножения двух булевых матриц размером и х и, а Т(п) — время, необходимое для поиска транзитивного замыкания булевой матрицы размером п х и.
(См, раздел 25.2.) Покажите, что нз алгоритма умножения булевых матриц со временем работы М(п) вытекает алгоритм поиска транзитивного замыкания со временем работы 0(М(п) 1к и), а из алгоритма поиска транзитивного замыкания со временем работы Т(п) вытекает алгоритм умножения булевых матриц за время 0(Т(п)). бэг Часть ИХ Избранные тены г8.г.5 Применим ли основанный на теореме 28.2 алгоритм обращения матриц к матри- цам над полем целых чисел по модулю 2? Поясните свой ответ.
28.2.6 * Обобщите алгоритм обращения матриц из теоремы 28.2 для матриц с комплексными числами и докажите корректность вашего обобщения. (Указание: вместо транспонирования матрицы А воспользуйтесь сонряженно-трансноннрованной (соп)пйаге ггапзрозе) матрицей А", которая получается из исходной путем транспонирования и замены всех элементов комплексно сопряженными числами. Вместо симметричных матриц рассмотрите эрннтовы (Негпнйал) матрицы, обладающие тем свойством, что А = А'.) 28.3. Симметричные положительно определенные матрицы и метод наимепыиих квадратов Симметричные положительно определенные матрицы обладают рядом интересных и полезных свойств.
Например, они невырождены и их Ш-разложение можно выполнить, не опасаясь столкнуться с делением на О. В этом разделе мы докажем ряд других важных свойств симметричных положительно определенных матриц и покажем их интересное применение — для получения приближений методом наименьших квадратов. Первое свойство, которое мы докажем, пожалуй, наиболее фундаментальное. Лемма 28.3 Любая симметричная положительно определенная матрица является невырожлен- ной.
Доказательство. Предположим, что матрица А вырожлена. Тогда согласно следствию Г.З имеется такой ненулевой вектор х, что Ах = О. Следовательно, хтАх = О, и А не может быть положительно определенной. Доказательство того факта, что Ш-разложение симметричных положительно определенных матриц можно выполнить, не опасаясь столкнуться с делением на О, более сложное. Начнем с доказательства свойств некоторых определенных подматриц А. Определим lс-ю главную нодматрнцу (!еагйп8 зпЬщаитх) А как матрицу Аы состоящую из пересечения (с первых строк и к первых столбцов А. л гад Если А представляет собой симметричную положительно определенную матрицу, то все ее главные подматрицы симметричные и положительно определенные. Доказательство.
То, что каждая главная подматрица Аь является симметричной, очевидно. Для доказательства того, что она положительно определенная, вос- Гаааа 2д Рабата с матрицами а 73 1„Вт (28.14) с подматрицами В (размером (и — й) х )с) и С (размером (и — )с) х (и — к)). Определим вектор х = ( хть О )т размером и„в котором после хь следуют и — и нулей.
Тогда х Ах=(х~б) В С О =(хГО) А" = хь Аьхь т <О, что противоречит условию, что матрица А положительно определенная. Теперь обратимся к некоторым важным свойствам дополнения Шура. Пусть А является симметричной положительно определенной матрицей, а Аь — главной подматрицей А размером )с х )с. Вновь разделим А на части, как в (28.14). Обобщим определение (28.9) для определения донолнення Шуро матрицы А относительно подматрицы Аь (ЯсЬиг сощр!ещепс оГ А вйл гезресг со Аь) как В = С вЂ” ВА„Вт (28.15) (Согласно лемме 28.4 Аь — симметричная положительно определенная матрица; следовательно, в соответствии с леммой 28.3 А,, ' существует, и дополнение Шура Я вполне определено.) Заметим, что прежнее определение (28.9) дополнения Шура согласуется с определением (28.15), если положить )с = 1.
Следующая лемма показывает, что дополнение Шура симметричной положительно определенной матрицы является симметричным положительно определенным. Этот результат используется в теореме 28.2, а следствие из него необходимо для доказательства корректности 1.()-разложения симметричных положительно определенных матриц. Лемме 38.5 ~Лемма о донолнении Шура) Если А представляет собой симметричную положительно определенную матрицу, а Аь — главная подматрица А размером )с х )с, то дополнение Шура Я матрицы А относительно подматрицы Аь является симметричным положительно определен- ным. пользуемся методом от противного. Если Аь не является положительно опреде- ленной, то существует вектор хь ф О размером /с, такой, что хтьАьхь < О.
Пусть матрица А имеет размер и х и и Часть рзз'. Избранные темы Доказввзеаьсвзвзх Поскольку матрица А симметрична, симметрична также подматрица С. Согласно упр. Г.2.6 произведение ВА гВт симметричное, так что в соответствии с упр. Г.1.! дополнение Шура Я также является симметричным. Остается показать, что дополнение Шура Я положительно определенное. Рассмотрим разделение А (28.14).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
