Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 176
Текст из файла (страница 176)
Определим 1с-ую главную нодматрицу (1еайп8 зпЬща~г)х) А как матрицу Ат состоящую нз пересечения й первых строк и й первых столбцов А. Лемма 28.10. Если А — симметричная положительно определенная матрица, то все ее главные подматрицы симметричные и положительно определенные. = х„Аьхь < О, т что противоречит условию, что матрица А положительно определенная. Теперь мы рассмотрим дополнение Шура. Пусть А — симметричная положительно определенная матрица, а Аь — главная подматрица А размера й х й. Разделим А на части следующим образом: А=( ) (28.28) Обобщим определение (28.23) для определения дополнения Шура матрицы А относительно подматрицы Аь (ЯсЬиг сощр1ещеп1 оГ А нчй гезрес1 1о Аь) следующим образом: Я = С вЂ” ВАь'В (28.29) Доказательство.
То, что каждая главная подматрица Аь является симметричной, очевидно. Для доказательства того, что она положительно определенная, воспользуемся методом от противного. Если Аь не является положительно определенной, то существует вектор хь ф О размером й такой, что хтьАьхь ( О. Пусть матрица А имеет размер и х и.
Определим вектор х = ( хт О )т размером и, в котором после хь следуют п — Й нулей. Тогда 860 Часть Ч1!. Избранные темы (В соответствии с леммой 28.10 Аь — симметричная положительно определенная матрица; следовательно, согласно лемме 28.9, А„з существует, и дополнение Шура Я вполне определено.) Заметим, что прежнее определение (28.23) дополнения Шура согласуется с определением (28.29), если принять й равным 1.
Следующая лемма показывает, что дополнение Шура симметричной положительно определенной матрицы является симметричным положительно определенным. Этот результат используется в теореме 28.8, а следствие из него необходимо для доказательства корректности )Л)-разложения симметричных положительно определенных матриц. Лемма 28.11 (Лемма о дополнении Шура). Если А — симметричная положительно определенная матрица, а Аь — главная подматрица А размером й х й, то дополнение Шура к подматрице Аь матрицы А является симметричным положительно определенным. Доказательство.
Поскольку матрица А симметрична, симметрична также подматрица С. Согласно упражнению 28.1-8, произведение ВАя гВт является симметричным, так что в соответствии с упражнением 28.1-1 дополнение Шура Я также является симметричным. Остается показать, что дополнение Шура положительно определенное. Рассмотрим разделение А (28.28). Для любого ненулевого вектора х в соответствии с тем, что А — положительно определенная матрица, выполняется соотношение хтАх ) О. Разобьем х на два подвектора у и х, совместимые с Аь и С соответственно.
В силу существования А. ~ имеем: хтАх т т т т ) ау+ ут 1„у+утВт + тВу+ тС (у+ А — ~Вт )тАь(у+ А-зВтз) + зт(С ВА-~Вт)х (28 30) (Корректность приведенного выражения можно проверить непосредственным вычислением.) Послелнее равенство соответствует выделению полного квадрата нз квадратичной форь,, (см. упражнение 28.5-2). Поскольку нер, венство хтАх > 0 выполняется для любого ненулевого х, для любого ненулевого з выберем у = — А, ~Втз, что удаляет первое слагаемое в (28.30), оставляя только т (С ВА-~Вт) — тс Глава 28. Работа с матрицами 861 в качестве значения всего выражения.
Итак, для любого г ф О мы имеем зт5з = хтАх > О, так что дополнение Шура является положительно определенным. а Следствие 28.12. 1.П-разложение симметричной положительно определенной матрицы никогда не приводит к делению на О. Доказательство. Пусть А — симметричная положительно определенная матрица. Докажем несколько более строгое угверждение, чем формулировка данного следствия: каждый ведущий элемент строго положителен. Первым ведущим элементом является аы. Этот элемент положителен по определению положительно определенной матрицы А, так как его можно получить с помощью единичного вектора е1 следующим образом: аы = е1гА ез ) О. На следующем шаге рекурсии Ы1-разложение применяется к дополнению Шура матрицы А относительно подматрицы А1 = (аы), которое в соответствии с леммой 28.11 является положительно определенным, так что по индукции все ведущие элементы в процессе Н1-разложения оказываются положительны.
Метод наименьших квадратов Подбор кривой для множества точек представляет собой важное применение симметричных положительно определенных матриц. Предположим, что нам дано множество из т точек где значения рл содержат ошибки измерений. Мы хотим найти функцию Г (х), такую что ошибки аппроксимации кд = г'(х1) — у; (28.31) малы при 1 = 1,2,..., т. Вид функции Е зависит от рассматриваемой задачи, и здесь мы будем считать, что она имеет вид линейной взвешенной суммы Г(х) = ~~~ с;~; (х), 1=1 где количество слагаемых п и набор базисных функныа(Ьаз1з Гппсцолз) Г выбираются на основе знаний о рассматриваемой задаче.
Зачастую в качестве базисных функций выбираются Д (х) = ху 1, т.е. функция Р представляет собой полипом степени и — 1: Р(х) = с1+сзх+сзх + +с„х" '. Часть Ч!1. Избранные темы 862 При и = ти можно найти функцию Е, которая удовлетворяет соотношению (28.31) с нулевыми погрешностями. Такой выбор функции Г не слишком удачен, так как помимо данных он учитывает и весь "шум", что приводит к плохим результатам при использовании Р для предсказания значения у для некоторого х, измерения для которого еще не выполнялись. Обычно гораздо лучшие результаты получаются при и значительно меньшем, чем п1, поскольку тогда есть надежда отфильтровать шум, вносимый ошибками измерений.
Для выбора значения и имеются определенные теоретические предпосылки, но данная тема лежит за пределами нашей книги. В любом случае, когда и выбрано, мы получаем переопределенную систему линейных уравнений, приближенное решение которой хотим найти. Сейчас мы покажем, каким образом это можно сделать. Пусть А — матрица значений базисных функций в заданных точках: 11(х1) ЯХ1) ... ЯХ1) 21(Х2) ,~2(хз) ... !д(Х2) ,~1(хтп) ~2(хти) ° ° ° !п(хт) т.е.
а," = Д (х;), и пусть с = (сь) — искомый вектор коэффициентов размером и. Тогда .Г1(Х1) 12(х1) ~~~(х1) с1 Е(х1) 21(х2) 22(хз) ... ~„(Х2) с2 Р(хз) Р(х„,) У1(хт) 22(хт) ° ° ° 1п(хт) ся представляет собой вектор размера т "предсказанных значений" у, а вектор т1 = = А с — у — вектор иввазок (арргохппайоп еггог) размера т. Для минимизации ошибок приближения мы будем минимизировать норму вектора ошибок 11, что отражено в названии "решение по методу иаимвиыиих квадратов" (1еав1-зсраге зо!пйоп): Поскольку 2 Ы~ = !(Ас — у!1~ = ~> ~1 а,~с — у; 1=1 2=1 Глава 28.
Работа с матрицами 863 мы можем минимизиРовать )Щ, диффеРенциРУЯ 5О8 по всем са и пРиРавниваЯ полученные производные к 0: — = ~> 2 ,'~ а,с — у, а;в=О. (И!' пса в=1 3=1 (28.32) и уравнений (28.32) эквивалентны одному матричному уравнению (А с — у) А = = О, которое эквивалентно (см. упражнение 28.1-2) уравнению Ат (А с — у) = О, откуда вытекает тАс= Ат (28.33) В математической статистике такое уравнение называется нормальным уравнением (поппа1 еопапоп). Согласно упражнению 28.1-2, матрица АтА симметрична, и если А имеет полный столбцовый ранг, то по теореме 28.6 матрица АтА положительно определенная. Следовательно, существует обратная матрица (АтА) и решение уравнения (28.33) имеет вид с= ((АтА)- Ат) у А+ А+ = ((АтА)-' Ат) (28.34) асевдообратнан (рзепдошчегзе) к А матрица.
Псевдообратная матрица является естественным обобщением обратной матрицы для случая, когда исходная матрица не является квадратной (сравните уравнение (28.34), дающее приближенное решение уравнения А с = у с точным решением А ~Ь уравнения А х = Ь), В качестве примера рассмотрим пять экспериментальных точек (хы уз) = (-1, 2), (хз, уз) = (1, 1), (хз,уз) = (2,1), (х4 У4) = (3,0), (хз>уз) = (5,3) которые показаны на рис. 28.3 черным цветом.
Мы хотим найти приближение экспериментальных данных квадратичным полиномом Г (х) = с1 + сзх + сзхз. Начнем с матрицы значений базисных функций: 1 х1 хз1 1 хз хзз хз хз 1 х4 х4 1 хз х~ 1 — 1 1 1 1 1 1 2 4 1 3 9 1 5 25 Часть ЧП. Избранные темы Рнс. 28З. Применение метода наименьших квадратов Псевдообратная к ней матрица равна 0.500 0.300 0.200 0.100 -0.100 А+ = -0.388 0.093 0.190 0.193 -0.088 0.060 -0.036 — 0.048 — 0.036 0.060 Умножая у на А+, мы получаем вектор юэффициентов 1.200 с = — 0.757 0.214 юторый дает нам квадратный полипом Г(х) = 1.200 — 0.757х+ 0.214хз в качестве наилучшего квадратичного приближения экспериментальных данных в смысле наименьших квадратов.
На практике нормальное уравнение (28.33) решается путем умножения Ату с последующим поисюм 1Л1-разложения АтА. Если матрица А имеет полный ранг, то матрица АтА гарантированно невырожденная, посюльку она симметричная и положительно определенная (см. упражнение 28.1-2 и теорему 28.6). Глава 28. Работа с матрицами 865 Упражнения Докажите, что все диагональные элементы симметричной положительно определенной матрицы положительны. Пусть А = (~ь,") — симметричная положительно определенная матрица размером 2 х 2. Докажите, что ее определитель ас — Ьз положителен, выделив полный квадрат так, как это было сделано в доказательстве леммы 28.11.
28.5-1. 28.5-2. 28.5-3. 28.5-4. 28.5-5. 28.5-6. 28.5-7. АА+А = А, А+АА+ = А+, (АА+)т АА+ (А+А)т А+А Задачи 28-1. Трехдиагональные системы линейных уравнений Рассмотрим трехдиагональную матрицу: 1 — 1 ΠΠΠ— 1 2 -1 ΠΠΠ— 1 2 — 1 ΠΠΠ— 1 2 — 1 ΠΠΠ— 1 2 а) Найдите 1Л3-разложение матрицы А.
б) Решите уравнение Ах = ( 1 1 1 1 прямой и обратной подстановки. тт 1 ) с использованием Докажите, что максимальный элемент симметричной положительно опре- деленной матрицы находится на ее диагонали. Докажите, что определитель каждой главной подматрицы симметричной положительно определенной матрицы положителен. Пусть Аь — й-я главная подматрица симметричной положительно опре- деленной матрицы А.
Докажите, что к-й ведущий элемент при 1 11-раз- ложении равен деФ (Аь)/дет (Аь 1) (полагаем дет (Ао) = 1). Найдите функцию вида Г (х) = с1+ сзх 18 х+ сзе*, являющуюся наилуч- шим приближением в смысле наименьших квадратов экспериментальных данных (1,1), (2,1), (3,3), (4,8). Покажите, что псевдообратная матрица А+ обладает следующими свой- ствами: Часть Ч11. Избранные темы в) Найдите обратную к А матрицу. г) Покажите, что для любой симметричной положительно определенной трехдиагональной матрицы А размером и х и и произвольного вектора Ь размером и уравнение Ах = Ь можно решить при помощи Ш-разложения за время 0 (и). Покажите, что любой другой алгоритм, основанный на обращении матрицы А, имеет асимптотически большее время работы в худшем случае. д) Покажите, что использование 1ЛР-разложения позволяет решить уравнение Ах = Ь, где А — невырожденная трехдиагональная матрица размером и х и, а Ь вЂ” произвольный вектор размером и, за время О (и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
