Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
Лемма В. 33 означает, что -*¦ 0 при /->«>; зто составляет утверждение Ь) теоремы 18.5. Так как ->0и неравенство (В. 50) выполняется для всех достаточно больших к, то установлена также и квадратичная сходимость, которую гарантирует последнее утверждение с) этой теоремы.
Закончим данное приложение следующими замечаниями.
1. Нет необходимости явным образом вычитать сдвиги ак из диагональных элементов Ак при построении матрицы Ак + 1. Этот тезис в применении к вычислению сингулярного разложения обсуждается в гл. 18.
2. На практике вычисление собственного значения заканчивается, когда элемент становится "нулем с рабочей точностью". Что под этим понимать, можно определять по-разному. Один из возможных критериев указан в гл. 18 в связи с численными аспектами сингулярного разложения.
3. Доказательство, которое мы привели, относится к случаю п > 3. Если и = 2 и
то, как легко видеть, одно ДО-преобрятоваНие со сдвигом,
в соответствии с (18.1) — (18.4) , даст
я<2> М2)
А2 = '
U22) «*а) J*
где b$2^ = 0. Таким образом, Aj — диагональная матрица, и собственные значения А вычислены.
4. Более общо, если вместо ак из (18.4) в качестве сдвига используется точное собственное значение X матрицы А, то матрица Ак+1 распадает-
192
ся в результате следующего QR-imrz. В самом деле.Т^^^^ГиТЦ^^^Т!
Чтобы убедиться в этом, заметим, что вследствие вырожденности матрицы А* - Х/„ по крайней мере один из диагональных элементов треугольной матрицы Rk должен быть нулем. Согласно (В. 8), > 0 для i = = 1,. . . , и - 1, и, следовательно, нулем должен быть элемент pW . Завершая подобное преобразование и восстанавливая сдвиг в соответствии с (В. 15), видим, используя (В. 17), что = sn**/>»*) =0 и потому
= Х.
п
Упражнение
В. 5 2. Доказать лемму В. 2.
ЫЗ.Ч.Лоусоя
ПОСЛЕСЛОВИЕ
Х.Д. Икрамов
Ниже приведен комментарий к ряду глав прочитанной вами книги. В нем кратко прореферированы важнейшие работы, относящиеся к сквозной теме книги - прямым методам для линейных задач наименьших квадратов. В основном это публикации 1974 г. н более поздних лет, и их отсутствие в книге понятно. В то же время в нескольких случаях работы, включенные в список литературы книги, в основном тексте не упоминаются. Так произошло, например, с циклом статей Бьорка по итерационному уточнению и работой Пейджа [50*]. Комментарий заканчивается собственным списком литературы, и ссылки здесь даются к этому дополнительному списку.
Глава 4. Понятия сингулярного числа и сингулярного разложения перенесены в [64*] на случай пары матриц с одинаковым числом столбцов; при этом строчные размеры могут не совпадать. Пусть А - тх X п-матрица, а В - nti X п-матрица. Если матричный пучок АТА - \ВТВ несингулярен, т.е. характеристический многочлен det(ATA - \ВТВ) не равен нулю тождественно по X, то конечные собственные значения пучка неотрицательны. Арифметические корни из них называются (обобщенными) сингулярными числами пары матриц (А, В). Если В = /„ - единичная n X п-матрица, то приходим к стандартному определению сингулярных чисел.
Предположим (имея в виду приложения к анализу задач с ограничениями) , что nil > п. Тогда [64*] существуют ортогональные mi X mi-матрица t/ и m2 Xmj -матрица V, а также невырожденная и X п-матрица X такие, что *)
Соотношения (1), (2) вместе с условиями (3) называются (обобщенным) сингулярным разложением пары (А, В). При этом отношения ty/ft, / = 1,..., г, суть сингулярные числа этой пары.
Остроумное доказательство этого факта, упрощающее доказательство Ван Лоана и опирающееся на (неявно) введенное еще в [25] понятие
*) Запись diagOy,.....yt), t = min (/и, л), обозначает m X л-матрицу, у которой
элементы главной диагонали равны числам у/, а все прочие элементы равны нулю.
UTAX = DA = diag (а,,..., а„), а, > О,
VTBX - Dg — diag(0,.....ft), ft > 0, s = min(m2, n),
ft > ... > 0, > 0, ft + , = ... = ft = 0, r = rank B.
(1) (2) (3)
194
CS-разложения ортонормальнои матрицы, дано в |55J. Пр^Шпилижим для простоты, что ранг (ги, + тг) X «матрицы
равен п. Пусть
F = QR = | | R (4)
Qb
есть ортогонально-треугольное разложение F, где R - невырожденная верхняя треугольная матрица, а блочное разбиение ортонормальнои (ту + тг) X п-матрицы Q индуцировано аналогичным разбиением F. Если QA = UCWT - сингулярное разложение QA, то в матрице
G =
верхний блок диагональный. Сингулярное разложение неоднозначно, и мы будем считать, что С выбрана так, что сингулярные числа, равные единице (если таковые имеются), занимают последние диагональные позиции С:
С =
С О О /,
о о
}m, - п
Таким образом, 0 < cb < 1, i = 1, 2,. . ., и - t.
Поскольку столбцы С имеют единичную длину, последние t столбцов Y должны быть нулевыми:
Y = [ Y :0]. n-tt
Так как GTG = /„, то, в частности, СТС + Y1"? = 1„ , т.е. матрица К7К диагональная, и, следовательно, столбцы Р попарно ортогональны. Поэтому Y можно представить в виде Y = VS, где V — тг X (л - г)-матрица с ортонормированными столбцами, S — диагональная матрица порядка и - г, диагональными элементами которой служат длины столбцов Y. Из сказанного заодно вытекает, что и - г = г = rank В.
