Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
?" = [?,, : ?,2 ], m, n-m,
положим
6.2 =(ЛГ,)-1?Г1, E12=E12-Q?2Ri2. (39)
Введем еще матрицу (2гг порядка т2 - ортогональный Сомножитель
6Л-разложения ?i2:
G"?l2= L О J) т-п '
/я = /Я| +Я1д .
Матрицу размера (и - m,) X т2, обраэо: ми 622 > обозначим через 622- Полагая
(40)
я- ЯН строка»
Л= Lo R22\ * запишем соотношения (38) - (40) в форм» МЯТрИЧИОГО рВвШгяа
П-f* IV
bJ iqL qL\
т.
Векторы x, g и последующие векторы той же размерности н будем пре&етав-
пять в виде
- ["1!"' . ["Г' •
Умножая нижнюю блочную строку системы (36) слева на R , полагая Rg =г и выполняя замену переменных .у =Rx, получим (см. (41))
" 0 0 еГ. 0
0 -7 qL ~ Т Q22
Qt 1 Qi2 0 0
0 Q22 0 " 0
У1
Уг
d f
'2 J
(42)
Пользуясь ортогональностью Qn, находим yt из верхней 210
строки (42):
Ун = Qnh-Построим вспомогательный т2-вектор s:
[s, 1}л - те, L s2 J }т - л
Последняя блочная строка (42) Qiir ~ h показывает, что верхние л — т, компонент вектора Q22'' образуют ^вектор t2. Из второй же блочной стро-
ки -r + GnJ'i +622^2 =/ следует
622Г = s + йггЩгУг- (Я)
Поскольку произведение Q22Q22 имеет вид
Q22QL
• [г] ¦
равенство (43) означает, что последние /я— л компонент 622'' составляют
Г ч
вектор s2. Итак, Q22r = J 1 откуда в силу ортогональности Q22
r = Q22 | J . То же равенство (43) позволяет определить у2: у2 = t2 —fy.
Наконец, X находим из третьей блочной строки (42) X = еГ,(г, -6.2г).
Алгольная процедура описанного процесса для случая, когда необходимые ортогонально-треугольные разложения выполняются методом отражений, приведена в [17*]. Во второй части работы [14*] дана программа этого же процесса, в которой для разложений используется модифицированный метод Грама—Шмидта.
Глава 22. Введенный в комментарии к гл. 7 аппарат взвешенных псевдообратных матриц очень облегчает доказательство сходимости метода взвешивания [28]. Прежде всего, если система Сх = d совместна, то решение минимальной длины задачи (32) выражается формулой
х = c;Ed + (ЕРС)У.
Здесь Рс - проектор на ядро С: Рс = I — С*С. Вектор х тогда и только тогда будет единственным решением (32), когда ker Cnker? = {0). Будем считать это условие выполненным.
Решение хе задачи
а
можно определить из нормальной системы
(СтС + е2ЕтЕ)х = CTd + e2ETf, т. е.
хе = (СГС + e2ETE)~i (CTd + e2ETf ).
Применяя к первому слагаемому правой часта формулу (13), а ко второму
формулу (14), получим
lim хе = С*Ed + (EPc)*f = х. е -» О
Вычислительные трудности, возникающие при реализации метода взвешивания, анализируются (посредством обобщенного сингулярного разложения) в [65 * ]. Там же описаны два приема - экстраполяция и итерационное уточнение, позволяющие во многих случаях получить приемлемое приближение к решению задачи (32) при не слишком малых значениях весового параметра е.
Глава 23. Для задачи
min || ?х - Я1. F = {x\Gx>h) (44)
F
анализ чувствительности решения к возмущениям входных данных проводится в [44*]. Численным методам для задачи (44) посвящены работы [58 *, 45 * ]. Во второй из них рассматривается случай ограничений специального вида: С{ <дс; i = 1, ...,к; xt >с,, i = к + 1,...,/.
Главы 24, 27. Устойчивость методов перестройки ?>7?-разложения, предполагающих хранение ортогонального сомножителя, анализируется в [54 * ]. Вот итоги этого анализа.
Как отмечено в гл. 15 (см., в частности, формулы (15.39), (15.40)),
матрица Ак+\, полученная в результате применения к m X n-матрице А последовательности к левых преобразований Хаусхолдера, может быть представлена в виде
A~k + \=Qk..Qx{A+Hk) = Q{A+Hk), (45)
Q = Qk- Q\, Ai = А.
Таким образом, Ак+1 можно рассматривать как продукт точного ортогонального преобразования возмущенной матрицы А + Нк. Для нормы матрицы эквивалентного возмущения Нк выполняется оценка
\\Hk\\F < 0(n)\\A\\F. (46)
Вид коэффициента при 17, приведенный в (15.40), для нас сейчас не важен. Такого же типа оценки справедливы и для других видов ортогональных
212
преобразований - последовательностей левых, правых или двусторонних отражений либо вращений.
Алгоритмы, дающие результат, являющийся точным преобразованием слабо возмущенной исходной матрицы, в вычислительной линейной алгебре принято считать устойчивыми. Как показано в [54* ], методы перестройки QR-разложения из гл. 24 устойчивы именно в этом смысле. Некоторую особенность составляет случай удаления строки.
Для простоты будем считать, что т > л и rank А = л. Пусть Q и R дают приближенное ортогонально-треугольное разложение матрицы А, т.е.
где Р — ортогональная матрица, a R — невырожденная верхняя треугольная матрица. Таким образом, матрица Q не предполагается точно ортогональной, но должна быть близка к некоторой ортогональной матрице Р.
Пусть А - матрица, полученная из А удалением какой-либо строки. Первый метод модификации из § 5 гл. 27 приводит к построению почти-ортогональной матрицы Q порядка т - 1 и новой треугольной л X л-матрицы R. Почти-ортотональность Q означает существование ортогональной матри-цы Р такой, что Нб-^Н <0(г)); при этом можно показать, что
