2,464
个编辑
更改
跳到导航
跳到搜索
第477行：
第477行： − + − + − +
→数值方法
* <math>\mathbf{M}</math>的非零奇异值（在<math>\mathbf{\Sigma}</math>的对角线上）等于<math>\mathbf{M}^{*}\mathbf{M}</math>和<math>\mathbf{M}\mathbf{M}^{*}</math>的非零特征值的平方根。
* <math>\mathbf{M}</math>的非零奇异值（在<math>\mathbf{\Sigma}</math>的对角线上）等于<math>\mathbf{M}^{*}\mathbf{M}</math>和<math>\mathbf{M}\mathbf{M}^{*}</math>的非零特征值的平方根。
通常，我们通过两步计算矩阵<math>\mathbf{M}</math>的SVD。第一步将矩阵简化为双对角矩阵（bidiagonal matrix），假设<math>m \geq n</math>，需要<math>O(mn^{2})</math>次浮点运算（flop）。第二步计算双对角矩阵的SVD，只能通过迭代方法完成。实际上，计算到机器精度就足够了。如果将这个精度视为常数，第二步需要<math>O(n)</math>次迭代，每次迭代花费<math>O(n)</math>次flop。因此，第一步耗时更长，总体成本为<math>O(mn^{2})</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>。
通常，我们通过两步计算矩阵<math>\mathbf{M}</math>的SVD。第一步将矩阵简化为双对角矩阵（bidiagonal matrix），假设<math>m \geq n</math>，需要<math>O(mn^{2})</math>次浮点运算（flop）。第二步计算双对角矩阵的SVD，只能通过迭代方法完成。实际上，计算到机器精度就足够了。如果将这个精度视为常数，第二步需要<math>O(n)</math>次迭代，每次迭代花费<math>O(n)</math>次flop。因此，第一步耗时更长，总体成本为<math>O(mn^{2})</math>次flop<ref name = "source2">{{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>。
如果只需计算奇异值，第一步可用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 name = "source2"/>。
第二步可用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"/>例程。
第二步可用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 name = "source2"/>。
还有一种不显式使用特征值分解的替代方法<ref>{{cite web |title=Simple SVD |url=https://mathworks.co.kr/matlabcentral/fileexchange/12674-simple-svd |website=MATLAB Central File Exchange }}</ref>。通常，我们将矩阵<math>\mathbf{M}</math>的奇异值问题转换为等价的对称特征值问题，如<math>\mathbf{M}\mathbf{M}^{*}</math>，<math>\mathbf{M}^{*}\mathbf{M}</math>，或 <math> \begin{bmatrix}\mathbf{0} &\mathbf{M} \\\mathbf{M}^{*}&\mathbf{0} \end{bmatrix}. </math>
还有一种不显式使用特征值分解的替代方法<ref>{{cite web |title=Simple SVD |url=https://mathworks.co.kr/matlabcentral/fileexchange/12674-simple-svd |website=MATLAB Central File Exchange }}</ref>。通常，我们将矩阵<math>\mathbf{M}</math>的奇异值问题转换为等价的对称特征值问题，如<math>\mathbf{M}\mathbf{M}^{*}</math>，<math>\mathbf{M}^{*}\mathbf{M}</math>，或 <math> \begin{bmatrix}\mathbf{0} &\mathbf{M} \\\mathbf{M}^{*}&\mathbf{0} \end{bmatrix}. </math>