Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
Дополняя матрицу V до ортогональной матрицы V порядка т2, а также окаймляя 5 нулевыми строками и столбцами до m2 X n-матрицы S, по-, лучим Y= VS. Это позволяет переписать (5) в виде
%13*
195
где X = R'lW. Это и есть обобщенное сингулярное разложение пары (А, В), причем C = DA, S=DB.
Способ устойчивого вычисления CS-разложения (6), использующий модификацию метода вращений Якоби, описан в [61*].
Сингулярное разложение пары матриц оказалось полезным средством исследования задач с ограничениями. Некоторые другие его приложения, а также другой способ обобщения понятия сингулярного числа указаны в [64*].
Анализ чувствительности обобщенных сингулярных чисел и сомножителей обобщенного сингулярного разложения к возмущениям элементов данной матричной пары проведен в [39*]. В частности, получены "обобщенные" варианты классических теорем Вейля-Лидского и Хоффмана-Ви-ландта.
Глава 5. Более точный по сравнению с теоремой 5.7 анализ возмущений сингулярных чисел выполнен в [60*]. В обозначениях гл.5 справедливо равенство .^ „ ,
0? = fa+&)2 +4?, 1-1.....*, . • (7)
причем .
I *, I < II РЕ II. inf || (/ - Р)Ех || < ц. < || (/- Р)Е И.
II X II = 1
Здесь Р - ортогональный проектор (проекционная матрица) на образ А.
Если а; велико относительно || Е ||, то вторым квадратом в (7) можно пренебречь, т.е. ft * а,- + {/.Поскольку
I*, I < || ГС || < IIЕ ||, (8)
то теорема 5.7 содержится в (7). Однако (8) сильнее, поскольку \\РЕ\\ может оказаться существенно меньше, чем IIЕ ||. В особенности зто вероятно при к < т, т.е. когда размерность образа А много меньше размерности т пространства.
Для малых а,, когда оба квадрата в (7) сравнимы по величине, второе слагаемое т?2 имеет тенденцию увеличивать значение сингулярного числа. Поэтому для плохо обусловленных матриц малые возмущения чаще приводят к улучшению обусловленности, а не к ее ухудшению.
В [62*] получены точные выражения для членов первого и второго порядка в асимптотическом разложении младшего сингулярного числа возмущенной матрицы.
Глава 6. Пусть вычислено ортогонально-треугольное разложение т X л-матрицы А из задачи НК, причем у треугольной л X л-матрицы R все диагональные элементы не равны нулю. Следует ли отсюда, что в пределах той точности, с какой ведутся вычисления, R не вырождена? Дадим эквивалентные постановки этого вопроса. Насколько мало младшее сингулярное число R1 Насколько велика норма матрицы R , т.е. если считать R нормированной, насколько велико ее число обусловленности? 196
Теорема 6.13 показывает, что даже для треугольной матрицы того типа, что строится в алгоритме HFTI (т.е., в частности, имеющей монотонно убывающие диагональные элементы), младший диагональный элемент может не давать правильного представления о величине наименьшего сингулярного числа. В [41*] предложен метод вычисления верхней оценки для WR'1 \\р, требующий 0{п) операций. Он основан на том, что для треугольной матрицы р с теми же диагональными элементами, что и у Л (которые в алгоритме HFTI всегда положительны), и отрицательными надднагональными элементами, определяемыми формулой
Рц = -а, = -max / = 1,.... и — 1,
справедливо неравенство IIR 1 У < Hp"1 llf. При этом
\\p-l\\2F = ? U,/rb, I = 1
а коэффициенты /и,- вычисляются рекурсивно: /и, = 1,
щ = (1 +с,_ i)2/u,_, -2с,_,, / = 2,3.....и;
ct = Фи. i - 1,2,... ,и - 1.
Многие современные программы решения линейных систем содержат блок оценки числа обусловленности матрицы. В случае треугольной матрицы R такой блок реализует один шаг обратной итерации для RTR при специально выбираемом начальном приближении [21*, 22*].
Глава 7. Существует необозримая литература о разных типах обобщенных обратных матриц. Так, в посвященной этому предмету книге [49*] библиография содержит 1775 названий.
Пусть / - произвольное подмножество множества {1, 2, 3, 4). Матрица X называется обобщенной обратной для А типа / (и обозначается А1), если для X выполнены все условия Пенроуза с номерами из /. В частности, ^{1,2,3,4} - а* . Для нетривиальных же подмножеств / множества обобщенных обратных матриц типа / в общем случае бесконечны.
Запись многих фактов, связанных с задачей НК, не требует именно псевдообратной матрицы: ее могут заменять более слабые обобщенные обратные. Так, формулу из упражнения 7.22, описывающую все псевдорешения задачи Ах — Ь, можно заменить на
х = A^-3h+(I-A^A)y.
Псевдообратная матрица А* введена в теоремах 7.1, 7.3 как матрица, дающая при фиксированной т X n-матрице А и произвольном m-векторе Ь решение минимальной длины (= нормальное псевдорешение) задачиЛх— Ь. Можно поставить более общую задачу: найти
min ||jtHi, F ={х\ \\Ax-b\\„ = min}, (9)
* e f
197
-ГIV II' 111, II • \\м - ^ШИпМидальНыё полунормы
II* Hi = Hi* И, \\у\\м - IIAfyll.
Эта задача рассматривалась рядом авторов, в частности в [28*, 47*].
Положим Р = / - (МА)* МА, т.е. Р — проектор на ядро МА. Общее реше ние (9) записывается формулой
х = (/ - (LP) *L) (МА) *МЬ + P(I - (LP)*LP)z, (10)
где z - произвольный вектор из R". Решение задачи (9) будет единствен ным в том и только том случае, когда
