2,464
个编辑
更改
跳到导航
跳到搜索
第481行：
第481行： − +
→数值方法
如果只需计算奇异值，第一步可用Householder反射以<math>4mn^{2}-4n^{3}/3</math>次flop完成。当<math>m</math>远大于<math>n</math>时，先用QR分解将矩阵<math>\mathbf{M}</math>简化为三角矩阵，再用Householder反射进一步简化为双对角形式更有优势；总成本为<math>2mn^{2}+2n^{3}</math>次flop<ref>{{cite book |last1=Trefethen |first1=Lloyd N. |last2=Bau |first2=David III |title=Numerical Linear Algebra |publisher=Society for Industrial and Applied Mathematics |year=1997 |location=Philadelphia |isbn=978-0-89871-361-9}}</ref>。
如果只需计算奇异值，第一步可用Householder反射以<math>4mn^{2}-4n^{3}/3</math>次flop完成。当<math>m</math>远大于<math>n</math>时，先用QR分解将矩阵<math>\mathbf{M}</math>简化为三角矩阵，再用Householder反射进一步简化为双对角形式更有优势；总成本为<math>2mn^{2}+2n^{3}</math>次flop<ref>{{cite book |last1=Trefethen |first1=Lloyd N. |last2=Bau |first2=David III |title=Numerical Linear Algebra |publisher=Society for Industrial and Applied Mathematics |year=1997 |location=Philadelphia |isbn=978-0-89871-361-9}}</ref>。
第二步可用QR算法的变体完成，该变体由Golub & Kahan<ref>{{cite journal |last1=Golub |first1=Gene H. |last2=Kahan |first2=William |title=Calculating the singular values and pseudo-inverse of a matrix |journal=Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis |volume=2 |issue=2 |pages=205–224 |year=1965 |doi=10.1137/0702016 |jstor=2949777 |bibcode=1965SJNA....2..205G}}</ref>首次描述。LAPACK子程序DBDSQR<ref>{{cite web |title=Netlib.org |url=http://www.netlib.org/ }}</ref>实现了这种迭代方法，并针对奇异值非常小的情况进行了改进<ref>{{cite journal |last1=Demmel |first1=James |last2=Kahan |first2=William |title=Accurate singular values of bidiagonal matrices |journal=SIAM Journal on Scientific and Statistical Computing |volume=11 |issue=5 |pages=873–912 |year=1990 |doi=10.1137/0911052 |citeseerx=10.1.1.48.3740}}</ref>。结合使用Householder反射的第一步和适当情况下的QR分解，构成了计算奇异值分解的DGESVD<ref>{{cite web |title=Netlib.org |url=http://www.netlib.org/ }}</ref>例程。
第二步可用QR算法的变体完成，该变体由Golub & Kahan<ref>{{cite journal |last1=Golub |first1=Gene H. |last2=Kahan |first2=William |title=Calculating the singular values and pseudo-inverse of a matrix |journal=Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis |volume=2 |issue=2 |pages=205–224 |year=1965 |doi=10.1137/0702016 |jstor=2949777 |bibcode=1965SJNA....2..205G}}</ref>首次描述。LAPACK子程序DBDSQR<ref name="source1">{{cite web |title=Netlib.org |url=http://www.netlib.org/ }}</ref>实现了这种迭代方法，并针对奇异值非常小的情况进行了改进<ref>{{cite journal |last1=Demmel |first1=James |last2=Kahan |first2=William |title=Accurate singular values of bidiagonal matrices |journal=SIAM Journal on Scientific and Statistical Computing |volume=11 |issue=5 |pages=873–912 |year=1990 |doi=10.1137/0911052 |citeseerx=10.1.1.48.3740}}</ref>。结合使用Householder反射的第一步和适当情况下的QR分解，构成了计算奇异值分解的DGESVD<ref name="source1"/>例程。
GNU科学库（GSL）也实现了相同算法，并提供了一种替代方法，在第2步中使用单边雅可比正交化<ref>{{cite web |url=https://www.gnu.org/software/gsl/doc/html/|title=§14.4 Singular Value Decomposition |author=GSL Team |year=2007 |work=GNU Scientific Library Reference Manual}}</ref>。这种方法通过求解一系列<math>2\times 2</math>的SVD问题来计算双对角矩阵的SVD，类似于雅可比特征值算法求解一系列<math>2\times 2</math>的特征值问题<ref>{{cite book |last1=Golub |first1=Gene H. |last2=Van Loan |first2=Charles F. |title=Matrix Computations |edition=3rd |publisher=Johns Hopkins |year=1996 |isbn=978-0-8018-5414-9}}</ref>。第2步的另一种方法借鉴了分治特征值算法（divide-and-conquer eigenvalue algorithms）的思想<ref>{{cite book |last1=Trefethen |first1=Lloyd N. |last2=Bau |first2=David III |title=Numerical Linear Algebra |publisher=Society for Industrial and Applied Mathematics |year=1997 |location=Philadelphia |isbn=978-0-89871-361-9}}</ref>。
GNU科学库（GSL）也实现了相同算法，并提供了一种替代方法，在第2步中使用单边雅可比正交化<ref>{{cite web |url=https://www.gnu.org/software/gsl/doc/html/|title=§14.4 Singular Value Decomposition |author=GSL Team |year=2007 |work=GNU Scientific Library Reference Manual}}</ref>。这种方法通过求解一系列<math>2\times 2</math>的SVD问题来计算双对角矩阵的SVD，类似于雅可比特征值算法求解一系列<math>2\times 2</math>的特征值问题<ref>{{cite book |last1=Golub |first1=Gene H. |last2=Van Loan |first2=Charles F. |title=Matrix Computations |edition=3rd |publisher=Johns Hopkins |year=1996 |isbn=978-0-8018-5414-9}}</ref>。第2步的另一种方法借鉴了分治特征值算法（divide-and-conquer eigenvalue algorithms）的思想<ref>{{cite book |last1=Trefethen |first1=Lloyd N. |last2=Bau |first2=David III |title=Numerical Linear Algebra |publisher=Society for Industrial and Applied Mathematics |year=1997 |location=Philadelphia |isbn=978-0-89871-361-9}}</ref>。