Дж. Деммель - Вычислительная линейная алгебра, страница 28

и„], так что А = ЮЕЪ т = зги,иТ (сумма матприц ранга 1). Тогда ближайшей к А (в смысле нормы ][ [Ц матрицей ранга Й < п являетпся матрица Аъ = 2, о,итит, причем ~]А — Аз[[а = оъ+т. Для матрицы Аъ справедливо также представление Аг = ПЕъ 1'т, где Еъ = тйаб(оы..., о ъ, О,..., О), Доказательстпво. 1. Это утверждение вытекает из определения Б'ЛЭ.

2. АзА = Ъ'ЕУтУЕЪ" = ЪтЕгЪ'т. Это равенство представляет собой спек- тральное разложение матрицы АтА, причем собственными векторами являются столбцы матрицы Ъ', а собственными значениями — диагональные элементы матрицы Ег. 3. Выберем матрицу П размера т х (т — и) так, чтобы квадратная матрица [У, У] была ортогональной. Тогда можем написать ААт ПЕЪттЪтЕттт ттЕгттт [тт тт] [П Ят (Ег О1 -т О О ~ Это спектральное разложение матрицы ААт . 4. См.

вопрос 3.14. 122 Глава 3, Линейные задачи наименыиих квадратов 'ОАх — ЬЦ = ОУЕ1ттх — Ь|'гг. Поскольку А — матрица полного ранга, то же самое верно для Е, т. е. Е обратима. Пусть, как и выше, ~17, 17) — квадратная ортогональная матрица. Тогда 17т ~ г Уж1 т* — Ь|Я = ~ ~, ~ (17ЕРт — Ь) Е1~т ~тЬ =ОЕР * — и Ь1!,+ОЬ7 Ь!!. Эта сумма минимальна, когда первое ее слагаемое равно нулю, т.е. при *= \/Е 1Ь7тЬ. Из определения очевидно, что 2-норма диагональной матрицы равна наибольшему из модулей диагональных элементов.

Используя утверждение 3 леммы 1Л, имеем йА()г = !)У~Ак"вг = 'ОЕвг = о1 и ОА ~)(г = Й1т~А Ц(г = !1Е-'Ог — 0.„-1, Снова выберем т х (т — и)-матрипу 17 таким образом, чтобы т х т-матрица У = ~17,17) была ортогональной. Поскольку 17 и 1т — невырожденные матЕвхо рицы, А имеет тот же ранг, что и матрица О~АЬ' = ~„, о~„„= Е, т.е. в силу нашего предположения о Е, ранг г. Так как равенство Ав = О эквивалентно равенству 17тАЪ'(к'тв) = О, то вектор и тогда и только тогда принадлежит ядру матрицы А, когда Ити принадлежит ядру матрицы Ь1тАЪ' = Е. Очевидно, что ядро матрицы Е натянуто на столбцы единичной матрицы 1„с номерами от т+ 1 до и, поэтому произведения этих столбцов с матрицей И, т.е.

векторы в„+1 и„, составляют базис в ядре матрицы А. Аналогичное рассуждение показывает, что образ матрицы А получается умножением матрицы У на образ матрицы Ь7тА)т = Е, т. е. умножением У на первые т столбцов матрицы 1 . Эти произведения суть векторы и1,... и„. «Построим» множество АЯ Яо ', применяя к 5" 1 поочередно сомножнтели разложения А = 17ЕРт. На рисунке этот процесс проиллюстрирован для матрицы .4= 1 З 2-11г 2 11г 4 О 2-11г 2 Для простоты, предположим, что А — квадратная невырожденная матрица. Так как матрица И ортогональна, т.е. отображает одни нормированные векторы в другие, то Гт я" 1 = я" ". далее, включение н Е я" ' равносильно условию Овйг = 1, поэтому и й ЕЯв 1 в том и только в том случае, если ОЕ 1го)(г = 1, или 2',". (го1/о1)г = 1. Это соотношение определяет эллипсоид с главными осями огеп где е; есть гьй столбец единичной 123 3.2.

Матричные разложения матрицы. Наконец, умножение всех векторов ю = Еи на матрицу У попросту поворачивает эллипс. При этом векторы е, переходят в столбцы и; матрицы У. 8( 8"1 ) Ч"8 -2 О 2 4 -2 О 2 4 8!дага'Ч'*8 -2 О 2 4 -4 -2 О 2 4 9. По построению, матрица Аь имеет ранг 2 и О оа» г '9А — Аь'лг — — ~~~ о;и;и~ т= а+ 1 Остается показать, что не существует матрицы ранга й, более близкой к А.

Пусть  — произвольная матрица ранга 2, тогда ее ядро имеет размерность п — й. Подпространство, натянутое на векторы еы..., наты имеет размерность )е + 1. Поскольку для суммы размерностей выполняется неравенство (п — Й) + (Й+ 1) > п, указанные подпространства должны иметь нетривиальное пересечение. Пусть Ь вЂ” нормированный вектор из этого пересечения. Тогда )(А — ВП > )((А — В)Ц~ ~= )(АЦ~ ~= )(УЕЪ'~ Ь()~~ ~~Ц1 тР,)~~г > т' )~~" /~()' г = оа„,. П Пример 3.4. Проиллюстрируем последнюю часть теоремы 3.3, использовав ее для сжатия изображения.

Такой иллюстрацией послужат малоранговые 124 Глава 3. Линейные задачи неименыоих квадратов аппроксимации изображения клоуна. Изображение размера т х п — это попросту ти х п-матрица, элемент (г, 1) которой интерпретируется как яркость точки (пиксела) (г, у). Другими словами, элементы матрицы, изменяющиеся, скажем, от 0 до 1, интерпретируются как точки с окраской от черной (что соответствует О) до белой (соответствует 1) с различными промежуточными степенями серого цвета. (Возможна и цветная окраска.) Вместо того чтобы хранить илн передавать все т и элементов матрицы, представляющей изображение, часто бывает предпочтительным сжатие этого изображения, т. е. хранение гораздо меньшего массива чисел, с помощью которых исходный образ все же может быть приближенно восстановлен.

Мы покажем сейчас,что для этой цели можно применить утверждение 9 теоремы 3.3. Рассмотрим изображение на рис. 3.3(а). Это изображение размера 320 х 200 соответствует матрице А того же размера. Пусть А = УХ)тт есть ЯУ)) этой матрицы. Согласно утверждению 9 теоремы 3.3, матрица Ае = 2,, о;иее7 е есть наилучшее приближение ранга и матрицы А в том смысле, что она реализует минимум ае.е~ величины ЙА — Ае()з. Заметим, что для восстановления матрицы Ае требуются лишь тп и+и й = (т+и) й слов памяти, в которых хранятся векторы иы..., ие и о е не,..., овны В то же время для хранения А (или той же матрицы Аы но в явном виде) нужны т и слов, т.

е. гораздо болыпая память при малом й. Итак, будем рассматривать Ае как сжатое изображение, хранимое с помощью (т+ п) . и слов памяти. Эти приближенные изображения для различных значений )е показаны на рис. 3.3; указаны также относительные ошибки а~~.е/о~ и коэффициенты сжатия (т + п) й/(т и) = 520 ° й/64000 )е/123.

Эти картинки были получены посредством следующих команд (изображение клоуна и некоторые другие изображения можно создать в МаВаЬ'е, пользуясь демонстрационными файлами визуализации; выясните, где находятся эти файлы в вашей локальной инстоляции Ма11аЪ'а): 1оа4 с1ояп.шаг; [0,Я,Ч)=вне)(Х); со1огшар ('йгау'); 1шайеЯ(:,1гй)еБ(1:)с,1:)с)еЧ(:,1:)с) ') Имеется множество других, более дешевых, чем ЯУ1), методов сжатия изображений (189, 152). О Позднее мы увидим, что при т » п стоимость решения задачи наименьших квадратов с использованием ЯЪ'П примерно такая же, как в методе ЯК; для меньших ти она составляет приблизительно 4пттп — 1~из + 0(пз) операций. Точное сравнение стоимостей методов цй и ЯЪЧ) зависит, кроме того, от используемого компьютера.

По поводу деталей см. раздел 3.6. 3.3. Теория возмущений для задачи наименьших квадратов 127 Определение 3.1. Пусть А — маторица размера т хи, причем т ) п. Пусть А — матрица полного ранга и А = СгВ = ПЕЪ'т суть ее чЯ-разложение и ОЪ'Р. Матрица Ат = (АтА) — 'Ат — у — 'дт — 1тЕ-тттт назмваетсл псевдообратной (Мура — Пенроуза) для А. При т < п полагаем А+ = Ат(ААт) Псевдообратная матрица позволяет записать решение полноранговой переопределенной задачи наименьших квадратов простой формулой х = А+Ь. Если А — квадратная невырожденная матрица, то эта формула, как и следовало ожидать, принимает вид х = А 'Ь.

В Мас1аЬ'е псевдообратная для матрицы А вычисляется посредством функции ртпч(А) . Для А, не имеющей полного ранга, псевдообратная матрица вводится определением 3.2 в разд. 3.5. 3.3. Теория возмущений для задачи наименьших квадратов Для неквадратной матрицы А число обусловленности в смысле 2-нормы определяется как кг(А) = о,„(А)/о ы(А).

Это определение в случае квадратной матрицы А сводится к обычному. Следующая теорема обосновывает это новое определение. Теорема 3.4. Пустпь А — полноранговал т х п-матрица, где т ) и. Предположим, что вектор х минимизирует ЙАх — ЬЙг и т = Ах — Ь есть соответствутотцал нев зка. Пустпь вектор х минимизирует ~((А + бА)х — (Ь+ бЬНг. Предположим, что е = тпах ( ~~Гл~~-',-'у~~~" ) < -„--(л( = — -'-"-~л). Тогда )!х — х!)г Г 2. кг(А) — <е ~ +Свб кг(А) +0(е ) =е ксз+0(е ), г ~ИЬ ~ сов О где сбпО = ~-"-~-'-. Другими словами, О есть угол между векторами Ь и Ах; гь1.

он измеряет, велика или мала норма невлзки ()гиг (т, е., соответственно, '3г((г близка к йЬ|)г или О). Символ ксз обозначает число обусловленностпи длл задачи на меньших квадратов. Иабросок доказательства. Разложим вектор х = ((А+бА)т(А+бА)) т(А+ бА)т(Ь+ бб) по степеням величин бА и бЬ, а затем отбросим все, кроме членов, линейных по бА и бЬ. П Условие екг(А) < 1 играет ту же роль, что и прн выводе оценки (2.4) для возмущенного решения квадратной системы линейных уравнений Ах = Ь: оно гарантирует, что матрица А+ бА имеет полный ранг, поэтому вектор х определен однозначно. Полученную оценку можно интерпретировать следующим образом: если угол О очень мал или равен нулю, то мала и невязка. В этом случае эффективное число обусловленности равно примерно 2кг(А), т.

е. примерно тому же, что и при решении обычной системы линейных уравнений. Если О не мал, но и не близок к т/2, то невязка умеренно велика, и эффективное число обусловленности может быть много больше, чем в первом случае, а именно равно 128 Глава 3. Линейные задачи наименьших квадратов к~~(А). Если е близок к х/2, так что точное решение почти вырождается, то эффективное число обусловленности становится неограниченным даже при малом кг(А).