Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 39
Текст из файла (страница 39)
Произвольно малые изменения (например, ошибки округлений) в матрице недостаточного ранга могут сделать все ее сингулярные числа ненулевыми и, следовательно, породить матрицу, формально имеющую полный ранг. На практике мы имеем дело с вффгктивньш рангом — количеством сингулярных чисел, ббльпшх некой предписанной границы, которая отражает точность данных. Это также разрывная функция, но ее разрывы менее многочисленны и неприятны, чем у теоретического ранга.
Большим преимуществом при использовании ЯЛЭ для определения ранга матрицы является то, что решения относительно возможного отбрасывания нужно вьшосить лишь в отношении отдельных чисел — малых сингулярных чисел,— но не векторов пли систем векторов. Мы можем теперь определить точно упомянутую раньше меру независимости.
Число обусловленности матрицы А полного ранга есть отношение сопд (А) == — "'", оты где о,„и а.ыщ — наибольшее и наименьшее сингулярные числа А. Если А имеет недостаточный ранг, то о ы=-0 и говорят, что число сопд(А) бесконечно. Число обусловленности, определенное в гл. 3 и оцениваемое подпрограммой ОЕСОМР, основано на другой векторной норме, и потому его значения могут отличаться от значений определяемого здесь числа обусловленности. Число обусловленности из К НАИМЕНЬШИЕ КВАДРАТЫ гл, 3 легче вычислять, но зато оно не имеет стольких удобных свойств. Обычно, однако, оба числа обусловленности имеют сравнимую величину.
Ясно, что сопс1(А))1. Если сопд(А) близко к 1, то столбцы А очень независимы, Если сопд(А) велико, то столбцы А почти зависимы. Если матрица А — квадратная, то таким терминам, как почти вырожденная или далеко не вырожденная, можно придать совершенно точное значение. Матрица А считается более вырожденной, чем матрица В, если сон!1(А))сопд(В). Если матрица А — ортогональная, то сопд(А)=1, так что столбцы ортогональной матрицы настолько независимы, насколько это вообще возможно. Обратно, если,сопд(А)==1, то оказывастси, что Л лишь чнсловьги множителем отличается от ортогональной матрицы.
Длина или норма вектора определяется как (хтх) Ыч Отношение 11Ах1д!1х11 измеряет степень, в которой А растягивает х. Как изменяется коэффициент растяжения 11Ах~1Ях~~, когда х пробегает все (ненулевые) векторы? Пусть А =01'Р'г и д=-Ргх. '! ак как ортогональные матрицы сохраняют длину, то !)д)1=-!1х11 и ," Лх) =-) УХУ'х,')=-) Хд~'. Поскольку Х вЂ” диагональная матрица, ясно, что о„;„) д ) (!, 'х:д ), ~ о,„'1 д !!. Следовательно, 1, 'Ах) о.ы~ '„х1, (о „„.
Сингулярные числа можно интерпретировать геометрически. Матрица А отображает единичную сферу, т. е. множество векто- Рис. 9.!. 9 Х ПРИЛОЖЕНИЯ ров, для которых йх~~=1, в множество векторов Ь=-Ах с различными длинами. Это множество-образ является в действительности й-мерным эллипсоидом, вложенным в т-мерное пространство.
Ситуация для тг и=-'я=-2 показана на рис. 9.1. Сингулярные числа суть длины разных осей эллипсоида. Крайние сингулярные числа а,„и а;„— это длины наибольшей и наименьшей оси. Число обусловленности связано с эксцентрисвтетом эллипсоида, причем большие числа обусловленности соответствуют очень вытянутым эллипсоидам. Норму матрицы можно определить как максимальный коэффициент растяжения, т. е.
попросту как (', А '1 =- о,„. Читатель, возможно, вспомнит, что в гл. 3 мы использовали другое определение для 11А!1 Определенную там норму гораздо легче вычислять, чем и,„, однако она не столь хорошо приспособлена к задачам того типа, с которым мы имеем дело в этой главе. Ф.З. Приложения В этом параграфе будут описаны еще несколько применекий сингулярного разложения. Решение произвольной системы линейных уравнений Пусть А — заданная тхп-матрица, причем пе. и, а Ь— заданный вектор размерности и. Нужно найти все векторы х, для которых Ах =- Ь.
Заметим, что важный случай, когда матрица А квадратная, но, возможно, вырожденная, включается сюда. Эта задача связана с такими вопросами: Совместны ли уравнения? Существук;т ли решения? Единственна ли решение? Имеет лн система Ах==О ненулевые решения? Каков общий внд решения? Теоретически имеется много различных алгоритмов, которые отвечают на эти вопросы. Но в вычислительной практике с ее неточными данными и неточной арифметикой ВЧ0 по существу является единственным известным методом, на надежность которого можно положиться. Используя сингулярное разложение матрицы А, линейную систему Ах=Ь можно переписать в виде итт =Ь, 9. НАИМЕНЬШНЕ КВАДРАТЫ 228 откуда где г=Р'х и д= УТЬ.
Система уравнений Хг=г/ диагональная и, следовательно, легко может быть решена. Она может распадаться на дае нли три подсистемы в зависимости от значений размерностей и/ и п и ранга й, т. е. количества ненулевых сингулярных чисел: /<и и о/ФО, /<а и а,.=-О, / ) и. если если если Вторая подсистема пуста, если /Е=п; третья пуста, если п=гп. Уравнения совместны н решение существует в том и только том случае, когда г//=-О всякий раз, когда о/=О или /)и.
Если я(и, то неизвестному е;, отвечающему нулевому о/, можно придать произвольное значение, и все равно получится решение системы. После возвращения к исходным координатам посредством преобразования х= гг эти произвольные компоненты г позволяют параметризовать пространство всех возможных решений х. Обозначим через и/ и и/ столбцы матриц У и Р. Тогда разложение А =УХ'г'г можно записать так: Ао/ — — о/иь /'=1, ..., и. (Поскольку в основном уравнении, вводящем сингулярное разложение, мы снабдили матрицу ~/ индексом Т, то теперь в уравнение входят столбцы обеих матриц У и Ъ', а не строки одной и столбцы другой.) Ядро матрицы Л есть множество векторов х, для которых Ах=-О, а область значенцй А — это множество векторов Ь, для которых система Ах — — Ь имеет решение.
Если о/=О, то Ао/=О и о/ принадлежит ядру Л; если же о/~О, то и/ принадлежит области значений А. Исходя из этого, мы можем получить полное описание ядра и области значений следующим образом. Пусть Р, — система столбцов оь для которых о/=О, а $~, — система остальных столбцов о;. Пусть У, — система столбцов ип для которых о/~ВО, а ӄ— система прочих столбцов иь включая те, для которых /' и. В системе г', имеется и — Ь столбцов, в $', — /9 столбцов и столько же в У„наконец, в У„имеется т — /г столбцов.
Кроме того, Е 1/, — ортонормнрованньш базис для ядра А . 2. //, — ортонормированный базис для ортогонального дополнения ядра А. 3. У, — ортонормированный базис для области значений А.. 4. У, — ортонормированный базис для ортогонального дополнения области значений А. 9.Х ПРИЛОЖЕНИЯ Указанная ранее матрица 1 б 11 2 7 12 3 8 13 4 9 14 5 10 15 5 5 5 5 5 Тогда 11.071 — 1.561 0 0 о Д вЂ”. 17гЬ = Последние три компоненты вектора А — нули; следовательно, столбец Ь был линейной комбинацией первых двух столбцов 17, система Ах=Ь, равно как и система Хг=-д, совместна. Эта по. следняя имеет внд 35.127г, — 11.071, 2.465г,, =- — 1.561, Ог, =-О. Ее решение— г, =0,315, г, = — 0.633, г, произвольно.
имеет недостаточный ранг. Ее средний столбец есть полусумма двух других. Это отражается в том факте, что в последнем столбце матрицы г', равном (0.408,— 0.816, 0.408)т, компоненты находятся в отношении 1: — 2: 1. Система Ах= — Ь имеет решение тогда и только тогда, когда Ь есть линейная комбинация первых двух столбцов 17. Если решение существует, то к нему можно добавить произвольное кратное последнего столбца К. Например, возьмем а нАименьшие кеАДРАты Беря г9=0 и вычисляя х — — Уг, получаем -Г.'.:) Легко видеть, что х=( — ",„О, '/,)г в самом деле является решением системы Ах=Ь. С другой стороны, взяв х9=1.225, находим х= 1.002 — 0.001 и х=( — 1, 1, 0)г — также решение.
В действительности мы можем, используя последний столбец У, получить общее решение. 4 5 Ь= 5 5 ь5 Тогда ' 10.7!6 — 0.872 — 0.541 — 0.193 — 0 265А д= игь= Так как три последние компоненты 4 не равны нулю, то система Ах=Ь не имеет решений. Другими словами, Ь не принадлежит области значений А.
Выбор г9=0 имеет особый смысл. Он приводит к решению ( — '/„О, '/,)г, имеющему среди всех возможных решений наименьшую длину. В качестве другого примера возьмем ЗЗ, ПРИЛОЖЕНИЯ 231 Линейная задача наименьших квадратов Это обобщение предыдущей задачи, но теперь ищутся и-мерные векторы х, для которых Ах лишь приближенно равно Ь, именно, в том смысле, что длина невязки минимальна. Под невязкой здесь понимается и-мерный вектор г=Ах — Ь.
Итак, задача состоит в том, чтобы выбрать х, который минимизирует йг(Р=Х",.,г';. (Минимизация квадрата длины равносильна минимизации самой длины.) Эта задача на языке статистиков называется задачей линейной регрежии. Матрица А обычно обозначается через Х и именуется иатрицей плана. Правую часть Ь обычно обозначают через у и называют вектором данных. Разумеется, зто та же задача, которая рассматривалась в 5 9А. Теперь используется лишь больше матричной терминологии. Если А имеет полный ранг, то решение х единственно и может быть устойчиво вычислено несколькими различными алгоритмами, из которых некоторые быстрее, чем ВЧП. Но ВЧ0 справляется и со случаем недостаточного ранга и, за исключением очень больших задач, ненамного более трудоемко, чем прочие устойчивые методы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
