Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 193
Текст из файла (страница 193)
Для любого ненулевого вектора х в соответствии с предположением о том, что А яапяется положительно определенной матрицей, выполняется соотношение х1Ах > О. Разобьем х на два подвектора, у и з, совместимые с Аь и С соответственно. В силу существования А,, ~ имеем хтАх=( утят ) В С т т 1е Аьу+ Втх ) Ву+ Сз / = утА~у+ утВтг+ хтВу+ х гСх + 1 — гВт )т 1 ( + 1 — ~Вт ) + т~С ВА — 1Вт) (28 16) (Корректность приведенного выражения можно проверить непосредственным вычислением.) Последнее равенство соответствует выделению полного квадрига из квадратичной формы (см. упр. 28.3.2). Поскольку неравенство хтАх > О выполняется для любого ненулевого вектора х, выберем произвольный ненулевой х и выберем у = — А 'Втх, что удаляет первое слагаемое в (28.16), оставляя только хт(С ВА-'Вт)х = хтВз в качестве значения всего выражения.
Итак, для любого х ф О мы имеем хтЯг = хтАх > О, так что дополнение Шура В является положительно определенным. ° Следсвзвие 28.6 Ы1-разложение симметричной положительно определенной матрицы никогда не приводит к делению на О. Доквзавсельсвсаа. Пусть А представляет собой симметричную положительно определенную матрицу.
Докажем несколыю более строгое утверждение, чем формулировка данного следствия: каждый ведущий элемент строго положителен. Первым ведущим элементом является ам. Зтот элемент положителен по определению положительно определенной матрицы А, так как его можно получить с помощью единичного вектора ез следукнцим образом: аы = ет1Ае1 > О. Поскольку на следующем шаге рекурсии П1-разложение применяется к дополнению Шура матрицы А относительно подматрицы Аз = (аы), из леммы 28.5 по индукции следует, что все ведущие элементы положительны. Метод наименьших квадратов Одним из важных приложений симметричных положительно определенных матриц является подбор кривой для заданного множества экспериментальных то- 875 Глава 2К Работа с матрааама чек.
Предположим, что дано множество из т точек (Х1, у1), (Х2, у2),..., (Хт у|о) ~ где значения у; содержат ошибки измерений. Нужно найти функцию Г(х), такую, что ошибки аппроксимации ил = Г(х1) — у1 (28.17) макы при 1 = 1,2,...,т. Вид функции Г зависит от рассматриваемой задачи, и здесь мы будем считать, что она имеет вид линейной взвешенной суммы Г(х) = ~~ с Д (х), ,1=1 где количество слагаемых и и набор базисны» 4ункцнй (Ьаа)з бшсйопа) У выбираются на основе знаний о рассматриваемой задаче. Зачастую в качестве базисных функций выбираются Л(х) = ху ', т.е.
функция Г представляет собой полипом степени и — 1 ог х: Г(Х) = С1 + С2Х + С3Х + ' ' ' + СоХ Таким образом, для заданных т экспериментальных точек (х1, у1), (хз, уз),..., (х, у ) необходимо вычислить и коэффициентов с1,сз,..., с„, минимизирующих ошибки приближения 711, 712,..., 71 . Выбрав и = т, можно точно вычислить все у, в (28.17).
Выбор такой функции Г с высокой степенью не слишком удачен, так как, помимо данных, он учитывает и весь "шум", что приводит к плохим результатам при использовании Г для предсказания значения у для некоторого х, измерения для которого еще не выполнялись. Обычно гораздо лучшие результаты получаются при и, значительно меньшем, чем т, поскольку тогда есть надежда выбрать такие коэффициенты с,, которые позволят отфильтровать шум, вносимый ошибками измерений.
Для выбора значения и имеются определенные теоретические предпосылки, но данная тема лежит за пределами нашей книги. В любом случае, когда выбрано и, меньшее, чем т, мы получаем переопределенную систему линейных уравнений, приближенное решение которой хотим найти. Покажем, каким образом это можно сделать. Пусть л1(Х1) У2(Х1) . Уо(»1) 71(хз) 72(хз) .. ~„(хз) (1(х ) 72(х~) ... ~„(х ) обозначает матрицу значений базисных функций в заданных точках, т.е. а12 —— Д(Х1), н пусть с = (сь) обозначает искомый вектор коэффициентов размером и. Часть Р11.
Избранные вены 81б Тогда 11(Х1) 12(Х1) ... 1„(х1) с1 11(Х2) 12(Х2) ... зи(Х2) С2 Ас = 11(х ) У2(х ) ° ° ° 1и(х ) Е(х1 ) Е(хз) Р'(Х-) представляет собой вектор размером т "предсказанных значений" у, а вектор 11=Ас — у является вектором невязок (ошибок приближения — арргохппайоп епог) размером гп. Для минимизации невязок будем минимизировать норму вектора ошибок и, что отражено в названии "решение методом нанменьшшс квадратов" (1еаз1-зе!ваге зо!п11оп), так как Поснэльку зи п 2 (!11()~ = ))Ас — у!)~ = ~~ ~ а;.с — у, з=1 1=1 можно минимизировать (Щ, дифференцировав (Щ по всем сь и приравняв по- лученные производные к О: ~й~' Г- 2 зи а с — у; аеь=О.
11сь 1=1,=1 (28.! 8) и уравнений (28.18) с )с = 1, 2,..., и эквивалентны одному матричному уравнению (Ас у)тА = О, или, что то же самое (см. упр. Г.1,2), Ат(Ас — у) = О, откуда вьпекает АтАс = Ату (28.19) 377 Глава 23. Работа с матрицами Рнс. 28.3. Применение метода наименьших квадратов для получения приближения плти экспериментальных точек ((-1,2),(1, 1),(2, 1), (3,0),(3,3)) квадратичным пвтиномом. Черным цветом показаны экспериментальные точки, а белым — значениа, предсказываемые квадратичным полиномом Р(х) = 1.2 — 0.737х+0.214х', минимизирующим сумму квадратов невязок.
Сермми линиями увязаны невязки длл каждой точки данных. В математической статистике такое уравнение называется нормальным уроаненнам (поппа! ейпайоп). Согласно упр. Г.1.2 матрица АтА симметрична, и если А имеет полный столбцовый ранг, то по теореме Г.б матрица АтА положительно определенная. Следовательно, существует обратная матрица (АтА) ', и решение уравнения (28.19) имеет вид с = ((АтА)-1 4т) у = Ату, (28.20) где матрица А+ = ((АтА) 1Ат) является нсеодообрннлной (рзепйозпуегзе) к матрице А.
Псевдообратная матрица является естественным обобщением обратной матрицы для случая, когда исходная матрица не является квадратной (сравните уравнение (28.20), дающее приближенное решение уравнения Ас = у, с точным решением А 'Ь уравнения Ах = Ь).
В качестве примера рассмотрим пять экспериментальных точек, (хт,у1) = (-1,2), (хз, уз) = (1, 1), (хз,уз) = (2,1), (х4,у4) = (3,0), (хм уз) = (5 3) Часть рц. Избранные тены В7В которые показаны на рис. 28.3 черным цветом. Необходимо найти приближение экспериментальных данных квадратичным полнномом р(Х) =с1+с2Х+сзХ Начнем с матрицы значений базисных функций: Ее псевдообратная матрица имеет вид 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 Умножив у на А+, получаем вектор коэффициентов с = — 0.757 г'(х) = 1.200 — 0.757х + 0.214хз, который представляет собой наилучшее квадратичное приближение экспериментальных данных в смысле наименьших квадратов.
На практике нормальное уравнение (28.19) решается путем умножения у на Ат с последующим поиском Ш-разложения АтА. Если матрица А имеет полный ранг, то матрица АтА гарантированно невырожденная, поскольку она симметричная и положительно определенная (см. упр. Г.1.2 и теорему Г.б). Уцрвкн енин 28.3.1 Докажите, что все диагональные элементы симметричной положительно опреде- ленной матрицы положительны.
газ.г Пусть А = (аб ь) является симметричной положительно определенной матрицей размером 2 х 2. Докажите, что ее детерминант ас — 52 положителен, выделив полный квадрат так, как это было сделано в доказательстве леммы 28.5. 1 Хз х21 1 Хз Х22 1 хз хз 2 1 Х4 Х4 1 хз хз 2 соответствующий квадратичному полиному 1 — 1 1 1 1 1 1 2 4 1 3 9 1 525 В79 Глава га Рабана с лиииричами газ.з Докажите, что максимальный элемент симметричной положительно определен- ной матрицы находится на ее диагонали. газ.д Докажите, что детерминант каждой главной подматрицы симметричной положи- тельно определенной матрицы положителен. 28.з.з Обозначим через Ав к-ю главную подматрицу симметричной положительно опре- деленной матрицы А.
Докажите, что /с-й ведущий элемент при 122-разложении равен бе1(Ав)/бе1(Ав 1) (полагаем, что с)еС(Ао) = 1). га.З.б Найдите функцию вида г (х) = с1 + сзх18х+ сзе*, являющуюся наилучшим приближением в смысле наименьших квадратов экспериментальных данных (1,1),(2,1),(3,3),(4,8) . га.З.7 Покажите, что псевдообратная матрица А+ удовлетворяет четырем следующим уравнениям: А, А+, АА+, А+А .
Задачи 28.1. Трехдиаеаналвные системы линейных ураанений Рассмотрим трехдиагональную матрицу 1 — 1 Π— 1 2 — 1 Π— 1 2 ΠΠ— 1 О О О а. Найдите Ш-разложение А. АА+А А+АА+ (,4А+)т (А+А)т ΠΠΠΠ— 1 О 2 — 1 — 1 2 ввб Чаете емт Избранные темы й. Решитеуравнение Ах = ( 1 1 1 1 1 ) с применением прямой и обратной подстановок.
в. Найдите матрицу, обратную матрице А. г. Покажите, как для любой симметричной положительно определенной трех- диагональной матрицы А размером и х п и произвольного вектора Ь размером и можно решить уравнение Ах = Ь с помощью Ш-разложения за время 0(п). Докажите, что любой другой алгоритм, основанный на обращении матрицы А, имеет асимптотически большее время работы в худшем случае. д. Покажите, как использование ШР-разложения позволяет решить уравнение Ах = Ь, где А — невырожденная трехдиагональная матрица размером и х и, а Ь вЂ” произвольный вектор размером и, за время О(п).
2В.2. Сплайны Один из практических методов интерполяции набора точек с помощью кривых заключается в использовании кубических снлайнов (спЬ1с зр!1пез). Пусть задано множество ((х,, у,): 1 = О, 1,..., и) из п+ 1 пары "точка-значение", причем хо < х1 « х„. Необходимо провести через эти точки кусочно-кубическую кривую (сплайн) г"(х). Кривая Дх) состоит из и кубических полиномов Гз(х) = а; + Ь,х + с,хз + е(;х (1 = О, 1,..., п — 1). Когда х находится в диапазоне х; < х < хз~.м значение кривой вычисляется как Г(х) = Ях — х,).
Точки хь в которыя "состыковываются" кубические полиномы, называются узлами ()що[а). Для простоты будем считать, что х; = в для( = 0,1,...,и. Чтобы обеспечить непрерывность г'(х), потребуем выполнения условий 1(х,) = ),(0) = у,, ,1(хи1) = Л(1) = уз ь для 1 = О, 1,..., п — 1. Чтобы функция г"(х) была достаточно гладкой, мы также потребуем непрерывности первой производной в каждом узле: г"'(х,+1) = ф1) = Д„1(0) для е = 0,1,...,п — 2. а Предположим, что нам даны не только пары ((х;, у,)), но и значения первых производных Р, = ~'(хз) в каждом узле 1 = 0,1,..., и. Выразите коэффициенты а„Ьз, с; и ез; через у„у,.„м Р, и Р,~.1 (напомним, что х, = 1), Сколько времени потребуется для вычисления 4п коэффициентов при таких условиях? Остается вопрос о вычислении первой производной г(х) в узлах. Один из методов ик определения состоит в том, чтобы обеспечить в узлах непрерывность второй производной )н(х;з.1) = Я'(1) = Я+1(0) Глава лв.
Работа с матрицами 88! 6. Используя непрерывность второй производной, покажите, что для | = 1, 2,..., и — 1, Р, | + 4Р, + Р|+| = 3(у,л.| — у| |) . (28.21) в. Покажите, что 2Ро+ Р| = 3(у| — уо), Р„| + 2Р„= 3(у„— у„|) (28.22) (28.23) к Перепишите уравнения (28.21)-(28.23) в матричном виде с использованием вектора неизвестных Р = (Ро, Р|, ..., Р„). Какими свойствами обладает матрица вашего уравнения? д. Докажите, что множество из п + 1 пар "точка-значение" может быть интерполировано с помощью естественного кубического сплайна за время 0(п) (см. задачу 28.1). е. Покажите, как построить естественный кубический сплайн, который интер- полирует множество из п+ 1 точек (х;,у|), где хо с х| < < х„и где значения х, не обязательно равны |. Какое матричное уравнение для этого нужно решить и сколько времени для этого потребуется? Заключительные замечания Имеется множество превосходных работ, в которых вопросы числовых и научных вычислений рассматриваются более детально, чем в данной книге.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
