Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
ГЛАВА 3
ОРТОГОНАЛЬНОЕ РАЗЛОЖЕНИЕ ПОСРЕДСТВОМ ЭЛЕМЕНТАРНЫХ ОРТОГОНАЛЬНЫХ ПРЕОБРАЗОВАНИЙ
В гл. 2 показано, что задача НК может быть решена, если имеется ортогональное разложение т X л-матрицы А. В этой главе мы установим существование такого разложения для произвольной матрицы, используя явные ортогональные преобразования.
Два типа элементарных ортогональных преобразований,, которые нам понадобятся, представлены в следующих двух леммах.
Лемма 3.1. Пусть дан {ненулевой) m-вектор v. Существует ортогональная матрица Q такая, что
Qv = - а || v II е,, (3.2)
где
+ 1, если Ui > О, - 1, если v, <0, ,
a V\ - первая компонента вектора v. Доказательство. Положим
т
ии
u=v + o\\v\\ei, Q = lm-2~~. (3.3)
и и
Доказательство завершается прямой проверкой симметричности и ортогональности матрицы Q из (3.3) и остающейся части утверждения леммы 3.1.
Преобразование, определяемое формулой (3.3), использовалось Хаус-холдером [101] для решения некоторых задач на собственные значения. По этой причине матрица Q и соответствующее преобразование называются матрицей и преобразованием Хаусхолдера.
Это преобразование с геометрической точки зрения есть отражение в m — 1-мерном подпространстве 5, ортогональном к вектору и. Это значит, что Qu = - и и Qs=s для всех s е S.
В специальном случае, когда нужно преобразовать к нулю только один элемент вектора и, часто используют следующее преобразование Ги-
12
венса [69]. Так как это преобразование изменяет только две компоненты вектора, то достаточно изучить его действие на 2-вектор.
Лемма 3.4.Пусть дан 2-вектор v =(и,, и2 )т, причем v, Ф 0либо v2 =?0. Существует ортогональная 2 X 2-матрица
(3.5)
такая, что
c2+s2=l, (3.6)
О I (37)
Доказательство. Положим просто
"шш*- ¦ м
Легко показать, что матрица G из (3.5) ортогональна и удовлетворяет условию (3.7). Лемма 3.4 доказана.
Заметим еще, что G можно выбрать не только ортогональной, но и симметричной, полагая
Ч* -'.У- рло)
с и s те же, что и в формулах (3.8), (3.9).
Теорема 3.11. Пусть А - тХ п-матрица. Существует ортогональная m X m-матрица Q такая, что в матрице QA = R под главной диагональю стоят только нулевые элементы.
Выберем ортогональную m X т-магрицу Q в соответствии с леммой 3.1 так, чтобы первый столбец Q\A имел нулевые компоненты со 2-й по т-ю. Далее выбираем ортогональную (m - 1) X (m - 1) -матрицу Рг следующим образом. Будучи применена к т — 1 вектору, составленному из компонент со 2-й по m-ю второго столбца матрицы Q\A, она аннулирует компоненты с 3-й по m-ю этого вектора. Матрица преобразования
[о Рг\
ортогональна, и Q%Q\A имеет в первых двух столбцах нули под главной диагональю.
Продолжая таким образом, можно построить произведение, состоящее самое большее из п ортогональных преобразований, которое трансформирует А к верхней треугольной форме. Эти рассуждения можно, формализовать и получить доказательство теоремы 3.11 методом конечной индукции.
Алгоритмические детали построения указанных преобразований будут Даны в гл. 10. Полученное представление матрицы произведением ортогональной и верхней треугольной матриц называется QR-разложением. Оно
13
j у i ii ящт,[ линейной алгео-
ры [59,72].
Для случаев la и 2а рис. 1.1, где rank А = и, теорема (3.11) устанавливает существование ортогонального разложения А. Действительно, согласно теореме 3.11, можно написать
A=QTR =QTRI„; (3.12)
матрицы Q т, R, 1„ этого представления имеют свойства, требуемые в соответствии с теоремой (2.3) от сомножителей Н, R,KT ортогонального разложения матрицы А.
Если rank А = тп (см. За на рис. 1.1), то теорема 3.11 позволяет нам написать
AT = QTR, (3.13)
так что
A =RTQ = ImRTQ. (3.14)
В этом представлении Im,RT,Q имеют свойства, требуемые в соответствии с теоремой 2.3 от сомножителей Н, R, Кт ортогонального разложения матрицы ранга т.
Для случаев 1Ь, 2Ь и ЪЪ рис. 1.1 матрица R, полученная в теореме 3.11, необязательно имеет форму, требуемую ортогональным разложением.
Мы переходим к обсуждению дополнительных преобразований, которые позволяют получить ортогональное разложение и для этих случаев.
Теорема 3.15. Пусть А - m X п-матрица ранга к,причем к<п <w. Существуют ортогональная m X m-матрица Q и п X п-матрица перестановки Р такие, что
а»-[' т0]. (зле
где R - верхняя треугольная k X к-матрица ранга к.
Доказательство. Выберем матрицу перестановки Р таким образом, чтобы первые к столбцов матрицы АР были линейно независимы. Согласно теореме 3.11, найдется ортогональная m X /и-матрица Q такая, что QAP — верхняя треугольная. Поскольку первые к столбцов АР линейно независимы, это же будет верно для первых к столбцов QAP.
Все элементы матрицы QAP, стоящие на пересечении строк с номерами к + 1.....тп и столбцов с номерами к + 1,... ,п, будут нулями. В противном случае rank QAP > А:, что противоречит предположению rank А = к. Итак, QAP имеет форму, указанную правой частью (3.16). Теорема 3.15 доказана.
Подматрицу [R : Т] из правой части (3.16) можно теперь преобразовать к компактной форме, требуемой от матрицы R из теоремы 2.3. Это преобразование описывает следующая лемма.
