Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
кег (МА)П кет L ={0). (11)
Слагаемые формулы (10) ортогональны, поэтому, даже если (11) не выполнено,вектор
х = (I-(LP)*L)(MA)*Mb (12)
является (уже однозначно определенным) решением (9), имеющим минимальную евклидову длину. Это мотивирует следующее определение.
Матрица Am,l = С - (LP)* L) (МА)* М называется ML-взвешенной псевдообратной для А [28*]. Формула (12) принимает вид
* = AbjLb.
Матрица A^,l принадлежит к числу обобщенных обратных для А типа {2}. Ряд ее свойств обобщает соответствующие свойства псевдообратных матриц Мура—Пенроуза. Известно, например, что
А* = lim (АТА +6ГУ1АТ. 6 -* о
Этому отвечает такое свойство взвешенной псевдообратной матрняы:
lim В(\) = lim [(МА)ТМА +\2LTL) *(МА)ТМ = Afo L. (13)
\ — о \ о
Отметим еще формулу ,. н, , ,
lim В(К) = (MAPL)*M, s< v.- - (14)
\ -» +°°
где PL = I-L*L.
Подобно тому как сингулярное разложение матрицы А упрощает вычисление псевдообратной матрицы (см. формулу (7.11)), обобщенное сингулярное разложение пары (А, В) позволяет определить взвешенные псевдообратные АЦ, ВЦ. Именно в обозначениях формул (1), (2) справедливо:
Ai.b - XD*AUT, ВЦ = XDlVT.
Глава 9. Вопрос о том, насколько реалистичны оценки возмущений нормального псевдорешения нз теоремы 9.7, разбирается в [59*]. При этом наряду с возмущениями исходных данных такого типа, как в названной теореме, т.е. характеризуемых наличием малого положительного е, для которого
||F|| < с || 4 II, || <fe|| < е|| 6 II,
рассматриваются и возмущения, вносящие малую относительную погреш-198
ность в каждый столбец Айв правую часть задачи. Если ?*; (Ж^) обозначает /'-й столбец Е(А), то возмущения этого типа описываются неравенствами .,
И Я/II < е\\А)\\, / = 1.....п. \\db\\ < е||й ||.
Будем говорить соответственно о возмущениях класса I и класса II.
Приведем несколько важных результатов этой работы. Пусть s, > > s2 > . . .> s„> 0 — сингулярные числа т X n-матрицы А, и пусть ц = - ек = е || А || || А* ||< 1. Найдутся возмущения Et, (db) i класса 1 такие, что
н j и ~* е Г Ik II IIЬ II
\\dx\\>—\ —-— +---2
sn L s„(l -и2) 1 — ц
и возмущения Ег, (db)2 класса I, для которых ИЛИ >~ [5,11*11 + Ц611].
Учитьшая, что в рассматриваемом случае - матрица А имеет полный столбцовый ранг — четвертый член в правой части (9.9) (см. теорему 9.7) отсутствует, видим, что остальные три члена действительно должны входить в любую верхнюю оценку возмущений псевдорешения для возмущений исходных данных класса I.
В случае возмущений класса II ситуация более сложная. Положим о = = || A \\F, и = eo/s„, и пусть и < 1. Для^произвольной невырожденной диагональной п X л-матриды D положим А = AD; пусть o,sn,(l определены по отношению к А так же, как a, s„, ц по отношению к А. Рассматриваем только такие матрицыD, для которых ц < 1. Оказывается, что для любого возмущения класса II
о Ik II ollxll II6 ||
ИЛИ <¦
(15)
Гя(1 -Д2) 1-/и 1-/
Главное отличне (15) от оценки (9.9) теоремы 9.7 заключается в том, что коэффициент d/s„ при г заменяет прежний коэффициент s, /s„. Это значит, что если масштабированием столбцов можно существенно уменьшить число обусловленности А (выполнять это масштабирование на самом деле необязательно), то верхняя оценка для II dx \\ в действительности зависит лишь от первой степени \\А * ||. Так будет, если столбцы А имеют сильно различающиеся длины, но хорошо разделенные направления.
Представляет интерес и следующее замечание из [59*]. Будем рассматривать возмущения класса I. Введем угол у между правой частью b н образом матрицы А. Существуют такие возмущения Е, db, что для относительной погрешности решения выполняется нижняя оценка
\dx\\ . _1 1 -Д
> ек2 tg<p--- . (16)
Предположим, что и = ек < 1, но правая часть (16) больше 1. В этом случае вектор х = х + dx не имеет какой-либо цены как приближение к х. Тем
199
не МИНИе оН ШДИрЖЯТ в сеое некоторую информацию об исходной задаче. Так, для не слишком малых у можно показать, что r(x) ^ 1,005г. т.е. вектор х почти минимизирует длину невязки. Для углов <р, не слишком близких к я/2, вектор х позволяет определить проекцию b на образ А с малой относительной погрешностью. Это следует из приближенного равенства || Adx ||/|| Ах || » u tg tp.
Глава 13. Относительная погрешность приближенного решения минимальной длины (= нормального решения) , вычисленного алгоритмом НВТ - HS2, будет (в наихудшем случае) зависеть от первой степени числа обусловленности, а не от второй, как было бы для несовместной системы. Этот вывод можно сделать, проводя для алгоритма обратный анализ погрешностей округлений в духе гл. 15-17 и применяя теорему 9.18. К тому же заключению приводит и прямой анализ погрешностей [38*].
Вместо алгоритма НВТ — HS2 нормальное решение можно искать так. Первым шагом, как и прежде, является ортогонально-треугольное разложение матрицы А:
AQ = [L:0),
где L - нижняя треугольная матрица. Будем искать НОрМВЛьнО#Т)ешение
в виде ы
х = ATw. (17)
Подставляя (17) в систему Ах = Ъ, получим
AATw = LLTw = b. , "'J" ; .' (18)
