Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
\\ А ||/г = ( 2 *?),/2. i-l
4.26. Пусть А * USV - сингулярное разложение А. Показать, что столбцы V суть
т
собственные векторы симметричной матрицы/4Л .
ГЛАВА 5
ТЕОРЕМЫ О ВОЗМУЩЕНИЯХ СИНГУЛЯРНЫХ ЧИСЕЛ
Сингулярные числа матрицы очень устойчивы к изменению ее злементов. Возмущения злементов матрицы приводят к возмущениям той же или меньшей величины в ее сингулярных числах. Цель данной главы - представить теоремы 5.7 и 5.10, которые дают точные формулировки этой устойчивости, и теорему 5.12, указывающую оценки возмущений сингулярных чисел при удалении из матрицы столбца или строки.
Эти теоремы являются прямыми следствиями соответствующих теорем об устойчивости собственных значений симметричной матрицы. Вначале мы сформулируем три относящиеся сюда теоремы о собственных значениях.
Теорема 5.1. Пусть В, А, Е, - симметричные п X п-матрицы и В - А = = Е. Обозначим собственные значения этих матриц, упорядоченные по не-
21
возрастанию, соответственно через 0,, 07, е/, i = 1,...., л. Тогда е„ <0, - а, <е,, i = 1,... ,п.
Часто бывает полезно более слабое неравенство, которое требует зато менее детальной информации относительно Е:
|0,-а,|<тах|е;| = ||?1, 1 = 1_____л.
Теорема 5.2 (Виландта - Хофмана). В условиях теоремы 5.1
2 03,-а,)2< 2 е?з 2 е^НЯ II2,.
Теорема 5.3. Дусгь А - симметричная п X п-матрица с собственными значениями а, > . .. > а„. Пусть к - целое число, 1 <и. Яусгь Я - симметричная матрица порядка п - 1, полученная удалением из А k-й строки и k-го столбца. Тогда собственные значения 0, матрицы В, также занумерованные в порядке невозрастания, разделяют собственные значения А:
а, >0i >а2 >02 > ... >0„_, >ая.
Обсуждение и доказательства этих трех теорем, равно как и минимаксной теоремы Куранта-Фишера, которую используют теоремы 5.1 и 5.3, читатель может найти в книге [7]. Теорема 5.2 впервые опубликована в [100]; ее обобщение обсуждается в [196].
Чтобы вывести из этих теорем о возмущениях собственных значений теоремы о возмущениях сингулярных чисел, мы воспользуемся связью, существующей между сингулярным разложением матрицы А и спектральным разложением симметричной матрицы
с =
Ат 0 J
(5.4)
Если А - квадратная и имеет сингулярное разложение А • t/SK**, то легко проверить, что С имеет спектральное разложение
с-\° -!].[' 01 - Г ?'
[v vl L о - s J L -
(S.S)
гГ уТ
}Т уТ
где U = 2~42U и V = 2~1I2V.
Если m X п-матрица А (т> л) имеет сингулярное разложение
Sn*n ].VT п ' пХя»
U(m-n)Xn .
то матрица С, определенная формулой (5.4), имеет спектральное разложение
л iuт X л ит х(т
где
e-[v V о ]¦
?(1)=2-1/2^(1) ^=2-1/2K
Ясно, что аналогичные результаты справедливы в случае тп < п. Для последующих ссыпок мы сформулируем теорему 5.6, вытекающую из вышесказанного.
Теорема 5.6. Пусть А - m X п-матрица и к = min (тп, и). Пусть С симметричная матрица порядка тп + п, определенная формулой (5.4). ?1сли S], ..., I* - сингулярные числа А, то собственные значения С суть Si, • • ¦. s*> _ si.....- s* u нуль, повторенный \ m - n \ раз.
Мы можем теперь сформулировать три теоремы, относящиеся к возмущениям сингулярных чисел.
Теорема 5.7. Пусть В, А, Е - m X п-матрицы и В -А=Е. Обозначим сингулярные числа этих матриц, упорядоченные по невозрастанию, соответственно через fih at, е/, /' = 1,... ,k; k = min(m, и). Тогда
|0,-о,|<е, з||Е||, « = 1.....к. (5.8)
Доказательство. Введем симметричные матрицы
Е
Ет О
~ Г О В] ~ Г О АЛ ~ Г О
(5.9)
Тогда В - А = Е. Связь собственных значений этих матриц с сингулярными числами В, А и Е указана в теореме 5.6. Применяя к матрицамВ.АчЕтеорему 5.1, получим неравенства 5.8.
Теорема 5.10. В условиях теоремы 5.7 справедливо неравенство
к к m п
2 (0,-а,)2< 2 ej= 2 2 ej»s||?|?. (5.11)
Доказательство. Вводя те же матрицы (5.9) и используя теоремы 5.6 и 5.2, получим
2 2 03,-o4)2<HF||Jr = 2||?||Jr, i = i
что эквивалентно неравенству (5.11).
Теорема 5.12. Пусть А - m X п-матрица. Пусть к - целое число, 1 < к < и. Пусть В - m X (и - 1)-матрице, полученная из А удалением к-го столбца. Если занумеровать сингулярные числа 0, матрицы В в порядке невозрастания, то они будут разделять сингулярные числа а, матрицы А следующим образом:
1) тп >п:
а, >&1>а1>&1> ... >0„_1>«Я>О; (5.13)
2) тп<п:
°4>01>а2>р2> ... >*m>0m>O- (5-14)
23
Доказательство. Неравенства (5.13) и (5.14) получаются прямым применением теоремы 5.3 к симметричным матрицам А = АТА и Ё = = В В. В случае 1) собственными значениями А и В будут соответственно числа a2, i = 1,.... л, и fif, i = 1,.... и - 1. В случае 2) собственные значения А суть a2, i = 1, ..., тп, и нуль, повторенный п - тп раз, а собственные значения Ё - р*2, i = 1, ..., тп, и нуль, повторенный л - 1 - тп раз.
Упражнении
5.15. Задача [51 ]. Даны m х л-матрица/! ранта к и неотрицательное целое число г, г <к. Найти m х л-матрицу В ранта г, минимизирующую II В - А II р.
т
Решение. Пусть А = USV - сингулярное разложение А с упорядоченными сингулярными числами J, > ... > > 0. Пусть 5 получена из S заменой чисел »г+|,... ..., 1д- нулями. Показать, что матрица В Г US V решает поставленную задачу, и выразить II В - А II р через сингулярные числа А.
