Как вычисляется SVD матрицы на практике

11

Как MATLAB, например, вычисляет SVD данной матрицы? Я предполагаю, что ответ, вероятно, включает в себя вычисление собственных векторов и собственных значений A*A'. Если это так, я также хотел бы знать, как он вычисляет их?

olamundo
источник
4
На самом деле, нет, это не связано с вычислением собственных векторов и значений ! Это значительно снизит точность результата. A*AT
Майкл Грант

Ответы:

11

AAT

Увидеть

Г.Х. Голуб и С. Рейнш. Решения разложения по сингулярным числам и наименьших квадратов. Numerische Mathematik 14: 403-420, 1970.

Этот материал обсуждается во многих учебниках по числовой линейной алгебре.

Брайан Борхерс
источник
13

Помимо (ныне классической) статьи Голуба-Рейнша, которую Брайан отмечает в своем ответе (я связал ее с версией статьи в Справочнике ), а также (также уже классической) предшествующей статьи Голуб-Кахана , было несколько важных событий в области вычисления SVD с тех пор. Во-первых, я должен подвести итог, как работает обычный метод.

Идея вычисления SVD матрицы качественно аналогична методу, используемому для вычисления собственного разложения симметричной матрицы (и, как отмечено в OP, между ними существует тесная связь). В частности, один этап состоит из двух этапов: преобразование в двухдиагональную матрицу и затем нахождение SVD двухдиагональной матрицы. Это полностью аналогично процедуре сначала приведение симметричной матрицы к трехдиагональной форме, а затем вычисление собственного разложения получающейся трехдиагональной.

Для вычисления SVD бидиагональной матрицы одним особенно интересным прорывом была статья Джима Деммеля и Вельвела Кахана , которая продемонстрировала, что можно вычислять даже крошечные сингулярные значения бидиагональной матрицы с хорошей точностью, соответствующим образом модифицируя метод, первоначально предложенный в Голуб-Reinsch. Затем это последовало (ре?) Открытие в DQD алгоритма , который является потомком старого фактор-разностного алгоритма Rutishauser. (Бересфорд Парлетт дает хорошее обсуждение здесь.) Если память служит, то теперь это предпочтительный метод, используемый внутри LAPACK. Кроме того, всегда можно было получить SVD-версии разработок в решении симметричных собственных задач; например, существует версия SVD «разделяй и властвуй», а также версия SVD старого алгоритма Якоби (который может быть более точным в некоторых обстоятельствах).

Что касается бидиагонализации, в статье Барлоу был изложен один улучшенный метод , который требует немного больше работы, чем первоначальная процедура Голуба и Рейнша, но дает более точные бидиагональные матрицы.

JM
источник
1
@ Джек, ты видел это случайно?
JM
Удивительно, но я этого не сделал!
Джек Полсон