2,464
个编辑
更改
跳到导航
跳到搜索
第458行：
第458行： − + 第468行：
第468行： − 双边雅可比SVD算法是[[雅可比特征值算法 Jacobi eigenvalue algorithm]]的推广，它通过迭代将方阵转换为对角矩阵。对于非方阵，我们先进行QR分解，然后对<math>R</math>矩阵应用此算法。其基本迭代步骤如下：先用Givens旋转使一对非对角元素对称，再用[[雅可比变换 Jacobi transformation]]使它们归零，+ 第484行：
第484行： − + 第502行：
第502行： − +
→计算奇异值分解（SVD）
===单边雅可比算法 One-sided Jacobi algorithm===
===单边雅可比算法 One-sided Jacobi algorithm===
单边雅可比算法是一种迭代算法<ref>{{cite journal |last1=de Rijk |first1=P.P.M. |title=A one-sided Jacobi algorithm for computing the singular value decomposition on a vector computer |journal=SIAM J. Sci. Stat. Comput. |volume=10 |pages=359 |year=1989 }}</ref>，它通过反复转换使矩阵列正交化。其基本迭代步骤由[[雅可比旋转 Jacobi rotation]]给出：
单边雅可比算法是一种迭代算法<ref>{{cite journal |last1=de Rijk |first1=P.P.M. |title=A one-sided Jacobi algorithm for computing the singular value decomposition on a vector computer |journal=SIAM J. Sci. Stat. Comput. |volume=10 |pages=359 |year=1989 }}</ref>，它通过反复转换使矩阵列正交化。其基本迭代步骤由雅可比旋转（Jacobi rotation）给出：
<math> M \leftarrow MJ(p,q,\theta), </math>
<math> M \leftarrow MJ(p,q,\theta), </math>
===双边雅可比算法 Two-sided Jacobi algorithm===
===双边雅可比算法 Two-sided Jacobi algorithm===
双边雅可比SVD算法是雅可比特征值算法（Jacobi eigenvalue algorithm）的推广，它通过迭代将方阵转换为对角矩阵。对于非方阵，我们先进行QR分解，然后对<math>R</math>矩阵应用此算法。其基本迭代步骤如下：先用Givens旋转使一对非对角元素对称，再用雅可比变换（Jacobi transformation）使它们归零，
<math> M \leftarrow J^{T}GMJ </math>
<math> M \leftarrow J^{T}GMJ </math>
3. <math>\mathbf{M}</math>的非零奇异值（在<math>\mathbf{\Sigma}</math>的对角线上）等于<math>\mathbf{M}^{*}\mathbf{M}</math>和<math>\mathbf{M}\mathbf{M}^{*}</math>的非零特征值的平方根。
3. <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讲）。
如果只需计算奇异值，第一步可用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讲）。
如果只需计算奇异值，第一步可用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讲）。
解析<math>2\times 2</math>，我们可以找到矩阵的奇异值。设矩阵为<math>\mathbf{M} =z_{0}\mathbf{I} +z_{1}\sigma_{1}+z_{2}\sigma_{2}+z_{3}\sigma_{3}</math>
解析<math>2\times 2</math>，我们可以找到矩阵的奇异值。设矩阵为<math>\mathbf{M} =z_{0}\mathbf{I} +z_{1}\sigma_{1}+z_{2}\sigma_{2}+z_{3}\sigma_{3}</math>
其中<math>z_{i}\in \mathbb{C}</math>是参数化矩阵的复数，<math>\mathbf{I}</math>是单位矩阵，<math>\sigma_{i}</math>表示[[泡利矩阵 Pauli matrices]]。那么它的两个奇异值由以下给出：
其中<math>z_{i}\in \mathbb{C}</math>是参数化矩阵的复数，<math>\mathbf{I}</math>是单位矩阵，<math>\sigma_{i}</math>表示泡利矩阵（Pauli matrices）。那么它的两个奇异值由以下给出：
<math> \begin{aligned}
<math> \begin{aligned}