5,443
个编辑
更改
跳到导航
跳到搜索
第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 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>。
通常，我们通过两步计算矩阵<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 name = "source2"/>。
如果只需计算奇异值，第一步可用[[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"/>。