查看“︁吉文斯旋转”︁的源代码

在[[数值线性代数]]中，'''吉文斯旋转'''（{{lang-en|Givens rotation}}）是在两个坐标轴所展开的平面中的旋转。吉文斯旋转得名于华莱士·吉文斯，他在1950年代工作于[[阿贡国家实验室]]时把它介入到数值分析中。

== 矩阵表示 ==
吉文斯旋转表示为如下形式的[[矩阵]]

:<math>G(i, j, \theta) = 
       \begin{bmatrix}   1   & \cdots &    0   & \cdots &    0   & \cdots &    0   \\
                      \vdots & \ddots & \vdots &        & \vdots &        & \vdots \\
                         0   & \cdots &    c   & \cdots &    -s   & \cdots &    0   \\
                      \vdots &        & \vdots & \ddots & \vdots &        & \vdots \\
                         0   & \cdots &   s   & \cdots &    c   & \cdots &    0   \\
                      \vdots &        & \vdots &        & \vdots & \ddots & \vdots \\
                         0   & \cdots &    0   & \cdots &    0   & \cdots &    1
       \end{bmatrix}</math>

这里的 ''c'' = cos(''&theta;'') 和 ''s'' = sin(''&theta;'') 出现在第 ''i'' 行和第 ''j'' 行与第 ''i'' 列和第 ''j'' 列的交叉点上。就是说，吉文斯旋转矩阵的所有非零元定义如下：:
:<math>\begin{align}
 g_{k\, k} &{}= 1 \qquad \text{for} \ k \ne i,\,j\\
 g_{i\, i} &{}= c \\
 g_{j\, j} &{}= c \\
 g_{i\, j} &{}= s \qquad \text{for} \ i > j \\
 g_{j\, i} &{}= -s \quad \text{for} \ i < j \\
\end{align}</math>


乘积 {{math|''G''(''i'', ''j'', ''θ'')'''x'''}} 表示向量 '''x''' 在 (''i'',''j'')平面中的逆时针旋转 &theta; 弧度。

Givens 旋转在[[数值线性代数]]中主要的用途是在向量或矩阵中介入零。例如，这种效果可用于计算矩阵的 [[QR分解]]。超过[[Householder变换]]的一个好处是它们可以轻易的并行化，另一个好处是对于非常稀疏的矩阵计算量更小。

== 稳定计算 ==
当一个吉文斯旋转矩阵 ''G''(''i'',''j'',&theta;)从左侧乘另一个矩阵 ''A'' 的时候，''GA'' 只作用于 ''A'' 的第 ''i'' 和 ''j'' 行。所以我们集中于下列问题。给出 ''a'' 和 ''b''，找到 ''c''&nbsp;= cos&nbsp;&theta; 和 ''s''&nbsp;= sin&nbsp;&theta; 使得
:<math> \begin{bmatrix} c & -s \\ s & c \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} r \\ 0 \end{bmatrix} . </math>
明确计算出 &theta; 是没有必要的。我们转而直接获取 ''c'', ''s'' 和 ''r''。一个明显的解是
:<math>\begin{align}
 r &{}\larr \sqrt{a^2 + b^2} \\
 c &{}\larr a / r \\
 s &{}\larr -b / r
\end{align}</math>
但是为了避免上溢出和下溢出，我们使用不同的计算，采用比率 ''b''/''a'' (它是 tan&nbsp;&theta;)或它的倒数(Golub &amp; Van Loan 1996)。如 Edward Anderson (2000) 在改进 [[LAPACK]] 时发现的，前瞻数值考虑是连续性的。要完成它，我们要求 ''r'' 是正数。

 if (b = 0) then {c &larr; copysign(1,a); s &larr; 0; r &larr; abs(a)}
 else if (a = 0) then {c &larr; 0; s &larr; -copysign(1,b); r &larr; abs(b)}
 else if (abs(b) > abs(a)) then
   t &larr; a/b
   u &larr; copysign(sqrt(1+t*t),b)
   s &larr; -1/u
   c &larr; -s*t
   r &larr; b*u
 else
   t &larr; b/a
   u &larr; copysign(sqrt(1+t*t),a)
   c &larr; 1/u
   s &larr; -c*t
   r &larr; a*u

这是依据 IEEE 754r <tt>copysign(x,y)</tt> 函数写成的，它提供了安全和廉价的方式复制 <tt>y</tt> 的符号到 <tt>x</tt>。如果不能获得它，使用[[符号函数]]的 <tt>x*sgn(y)</tt> 可作为替代。

注意这里的sgn定义为
:<math>\sgn x = \begin{cases}
  1 & :\ x \ge 0 \\
  -1 & :\ x < 0 \end{cases}</math>
而不是常用的
:<math>\sgn x = \begin{cases}
  1 & :\ x > 0 \\
  0 & :\ x = 0 \\
  -1 & :\ x < 0 \end{cases}</math>
后者常在高级语言中作为标准库函数被提供，注意不要直接应用于本算法中。

== 参见 ==
* [[雅可比旋转]]

== 引用 ==
* {{cite book
  | last = Golub
  | first = Gene H.
  | authorlink = 
  | coauthors = Charles F. Van Loan
  | title = Matrix Computations
  | edition = 3/e
  | publisher = Johns Hopkins University Press
  | date = 1996
  | location = Baltimore
  | id = ISBN 978-0-8018-5414-9 }}
* Anderson, Edward. (2000) ''[http://www.netlib.org/lapack/lawns/downloads/ Discontinuous Plane Rotations and the Symmetric Eigenvalue Problem] {{Wayback|url=http://www.netlib.org/lapack/lawns/downloads/ |date=20201112030940 }}''. LAPACK Working Note 150, University of Tennessee, UT-CS-00-454, December 4, 2000.
* D. Bindel, J. Demmel, W. Kahan, O. Marques. (2001) ''[http://www.netlib.org/lapack/lawns/downloads/ On Computing Givens rotations reliably and efficiently] {{Wayback|url=http://www.netlib.org/lapack/lawns/downloads/ |date=20201112030940 }}''. LAPACK Working Note 148, University of Tennessee, UT-CS-00-449, January 31, 2001.<!-- The paper itself says January 2001, but the LAWN site says October 2000. -->

[[Category:矩陣]]
[[Category:数值线性代数]]
[[Category:三维旋转]]