Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
Пусть Р„хп — проекционная матрица, к собственных значений которой равны единице. Пусть Т есть А;-мерное собственное подпространство Р, относящееся к собственному значению единица. Подпространство Т - это (единственное) подпространство, ассоциированное с проекционной матрицей Р, а Р — (единственная) проекционная матрица, ассоциированная с подпространством Т. Подпространство Т является одновременно пространством строк и пространством столбцов для ассоциированной с ним проекционной матрицы Р и характеризуется свойством
7= {х: Рх = х) .
Если Р - проекционная матрица с ассоциированным подпространством Т и ||Ле || = ||дс И, то Рх = х и х € Т. Кроме того, ||Ле || < ||х || для х & Т, н, следовательно, \\Р\\ = 1, если РФ 0.
Для произвольной матрицы АтХп матрица А*А есть проекционная п X л-матрица, ассоциированная с пространством строк А; (I - А*А) -проекционная матрица, ассоциированная с ядром А; А А* — проекционная матрица, ассоциированная с образом (пространством столбцов) А.
Для любого я-вектора х существует единственное представление вида х = t + и, где t е Т, а и € Т1. При этом г = Рх, и = (/ - Р) х. Вектор г - это ближайший к х вектор в Тв том смысле, что \\х-1II =min {||дс- u|| :и?Г}. Вектор t называется проекцией х на Т.
Обсуждение свойств проекционных операторов и доказательство большей части высказанных выше утверждений о них читатель найдет в кии-ге [12].
Произвольная матрица АтХп допускает сингулярное разложение А ~ ^тХт^тХп х л > где ^и ^ ~ ортогональные матрицы, a S - диагональная матрица с неотрицательными диагональными элементами. Диагональные элементы S (sw, /' = 1,А:, где А: = min (m, л)) называются сингулярными числами А. Это множество чисел однозначно определяется матрицей А. Число ненулевых сингулярных чисел равно рангу А. Кроме того,
М || = max {*¦„), \\ A \\F = (Д sj,)1/2,
что дает простое доказательство двух правых неравенств (А.З).
Пусть А = USVT - сингулярное разложение матрицы АтХп. Тогда спектральными разложениями матриц АТА и ААТ будут соответственно АТА = V(STS) VthAAt = U(SST) UT.
Сингулярное разложение дает информацию, полезную при практическом анализе задач линейной алгебры. Его свойства и приложения обсуждаются в гл. 4,5,18,25,26.
ПРИЛОЖЕНИЕ В
ДОКАЗАТЕЛЬСТВО ГЛОБАЛЬНОЙ КВАДРАТИЧНОЙ СХОДИМОСТИ QR-АЛГОРИТМ А
Назначение этого приложения — дать доказательство теоремы 18.5. Приводимое нами доказательство является более подробным вариантом того, что содержится в [194, 195]. Утверждение а) теоремы 18.5 вынесено в упражнение 18.46.
Лемму В.1 вместе с доказательством можно найти в книге [7].
Лемма В.1. Пусть А - симметричная трехдиагональная л X п-матрица с диагональными элементами ах,...,ап и наддиагональными (поддиаго-нальными) элементами Ьг.....Ь„, причем все bt ненулевые. В таком случае А имеет п различных собственных значений.
Нам понадобится также следующая простая лемма, доказательство которой вынесено в упр. В.52. Мы используем обозначения, введенные в тексте и уравнениях гл. 18 (от начала идо (18.4)).
Лемма В.2. Для всех k = 1, 2,... элементы матриц Ак и сдвиги ок ограничены по модулю величиной \\А\\, а элементы матриц Ак — ак1„ и Rk ограничены по модулю величиной 2\\А \\.
Мы должны исследовать основные операции QR-алгоритма со сдвигами, чтобы установить свойства некоторых промежуточных величин и в конечном счете оценить величину некоторых внедиагональных элементов матриц Ак.
Обозначим диагональные элементы сдвинутой матрицы Ак — ок/„ через J/** -.<*>- ок,
1 = 1,..., л. .
Согласно правилу выбора ок (см. (18.4)), то собственное значение нижней угловой 2 X 2-подматрицы в матрвявт {Ак - ак1п), которое ближе к а^к\ равно нулю. Поэтому
(В.4)
(В.З)
Ортогональная матрица Qk представляется произведением
где каждая матрица , есть вращение в плоскости, определяемой / - 1 -й
186
и /-й координатными осями. Она имеет вид
/(*) =
'i-2
о о
О О />/*> О
, i=2,п.
(В.6)
где — матрица двумерного вращения, определяемая, как и в (3.5),
соответствующими числами су ' и s
(*) „Л*)
После того как матрица Ак — ак /„ умножена слева на первые i - 2 матриц вращений, имеем
К*)
"'/-2,1-1
о №
_(*)
^2
р(*)
1
х(к) 1-1
Ь(к) I
г(*) 1-2
у(*)
/+1
п - 1
и -1 я
п п
(В.7)
Умножая обе части (В.7) слева на J^}^,, выводим, используя формулы (3.7) -(3.9), следующие рекуррентные соотношения:
р<Д\ = [(*(*_>,)* + (6<*))ll •/*, / = 2,и, (В.8)
р<*> =*<*>, (в.9)
f(*) =
i = 2,я,
i = 2,n.
<>--*<*>*<*_>, + c<*>6<*>, /-2, ....и,
,(*> =-,(*)/*> + t-<*>J<*>, / = 2... I / i—i / i
,(*> = *<*>*<*>• ' =2,...,и-1.
я,
(B.10)
(В.П)
(B.12) (B.13) (B.14)
187
Подобное преобразование завершается построением матрицы
Ak+x-Wl +ak{n =**0Г ••• (^1,,„)Г +okI„. (В.15)
В этом процессе новые внедиагональные элементы вычисляются по формулам
+ =, s(*)p(*) , / = 2.....л. (В.16)
Мы хотим проанализировать поведение последовательности {bjf *1Ц при к
В формулах (В.17)-(В.19) мы опустим верхний индекс к, но сохраним индекс к + 1. Начиная с (В.16) при / = л, имеем
