更改

奇异值分解（SVD） (查看源代码)

2024年10月25日 (五) 09:18的版本

添加1,227字节、 2024年10月25日 (星期五)

第479行：第479行：

* <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（Trefethen & Bau III ~~1997，第31讲）。~~

+

通常，我们通过两步计算矩阵<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（Trefethen & Bau III 1997，第31讲）<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（Trefethen & Bau III 1997，第31讲）。

−

第二步可用QR算法的变体完成，该变体由Golub & ~~Kahan（1965）首次描述。LAPACK子程序DBDSQR~~<ref>{{cite web |title=Netlib.org |url=http://www.netlib.org/ }}</ref>实现了这种迭代方法，并针对奇异值非常小的情况进行了改进（Demmel & Kahan ~~1990）。结合使用Householder反射的第一步和适当情况下的QR分解，构成了计算奇异值分解的DGESVD~~<ref>{{cite web |title=Netlib.org |url=http://www.netlib.org/ }}</ref>例程。

+

第二步可用QR算法的变体完成，该变体由Golub & Kahan（1965）<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>实现了这种迭代方法，并针对奇异值非常小的情况进行了改进（Demmel & Kahan 1990）<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>例程。

−

GNU科学库（GSL）也实现了相同算法，并提供了一种替代方法，在第2步中使用单边雅可比正交化（GSL Team ~~2007）。这种方法通过求解一系列~~<math>2\times 2</math>的SVD问题来计算双对角矩阵的SVD，类似于雅可比特征值算法求解一系列<math>2\times 2</math>的特征值问题（Golub & Van Loan 1996，§8.6.~~3）。第2步的另一种方法借鉴了分治特征值算法（divide~~-and-conquer eigenvalue algorithms）的思想（Trefethen & Bau III 1997，第31讲）。

+

GNU科学库（GSL）也实现了相同算法，并提供了一种替代方法，在第2步中使用单边雅可比正交化（GSL Team 2007）<ref>{{cite web |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>的特征值问题（Golub & Van Loan 1996，§8.6.3）<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）的思想（Trefethen & Bau III 1997，第31讲）。

还有一种不显式使用特征值分解的替代方法<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>，或

相信未来

2,464

个编辑