吉文斯旋转
在数值线性代数中,吉文斯旋转(Givens rotation)是在两个坐标轴所展开的平面中的旋转。吉文斯旋转得名于华莱士·吉文斯,他在 1950 年代工作于阿贡国家实验室时把它介入到数值分析中。
矩阵表示
吉文斯旋转表示为如下形式的矩阵
这里的 c = cos(θ) 和 s = sin(θ) 出现在第 i 行和第 j 行与第 i 列和第 j 列的交叉点上。就是说,吉文斯旋转矩阵的所有非零元定义如下::
乘积 G(i, j, θ)x 表示向量 x 在 (i,j)平面中的逆时针旋转 θ 弧度。
Givens 旋转在数值线性代数中主要的用途是在向量或矩阵中介入零。例如,这种效果可用于计算矩阵的 QR分解。超过Householder变换的一个好处是它们可以轻易的并行化,另一个好处是对于非常稀疏的矩阵计算量更小。
稳定计算
当一个吉文斯旋转矩阵 G(i,j,θ)从左侧乘另一个矩阵 A 的时候,GA 只作用于 A 的第 i 和 j 行。所以我们集中于下列问题。给出 a 和 b,找到 c = cos θ 和 s = sin θ 使得
明确计算出 θ 是没有必要的。我们转而直接获取 c, s 和 r。一个明显的解是
但是为了避免上溢出和下溢出,我们使用不同的计算,采用比率 b/a (它是 tan θ)或它的倒数(Golub & Van Loan 1996)。如 Edward Anderson (2000) 在改进 LAPACK 时发现的,前瞻数值考虑是连续性的。要完成它,我们要求 r 是正数。
if (b = 0) then {c ← copysign(1,a); s ← 0; r ← abs(a)} else if (a = 0) then {c ← 0; s ← -copysign(1,b); r ← abs(b)} else if (abs(b) > abs(a)) then t ← a/b u ← copysign(sqrt(1+t*t),b) s ← -1/u c ← -s*t r ← b*u else t ← b/a u ← copysign(sqrt(1+t*t),a) c ← 1/u s ← -c*t r ← a*u
这是依据 IEEE 754r copysign(x,y) 函数写成的,它提供了安全和廉价的方式复制 y 的符号到 x。如果不能获得它,使用符号函数的 x*sgn(y) 可作为替代。
注意这里的sgn定义为
而不是常用的
后者常在高级语言中作为标准库函数被提供,注意不要直接应用于本算法中。
参见
引用
- Golub, Gene H.; Charles F. Van Loan. Matrix Computations 3/e. Baltimore: Johns Hopkins University Press. 1996. )
- Anderson, Edward. (2000) Discontinuous Plane Rotations and the Symmetric Eigenvalue Problem (页面存档备份,存于互联网档案馆). LAPACK Working Note 150, University of Tennessee, UT-CS-00-454, December 4, 2000.
- D. Bindel, J. Demmel, W. Kahan, O. Marques. (2001) On Computing Givens rotations reliably and efficiently (页面存档备份,存于互联网档案馆). LAPACK Working Note 148, University of Tennessee, UT-CS-00-449, January 31, 2001.