吉文斯旋轉

在數值線性代數中，吉文斯旋轉（英語：Givens rotation）是在兩個坐標軸所展開的平面中的旋轉。吉文斯旋轉得名於華萊士·吉文斯，他在1950年代工作於阿貢國家實驗室時把它介入到數值分析中。

矩陣表示

吉文斯旋轉表示為如下形式的矩陣

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}}

這裡的 c = cos(θ) 和 s = sin(θ) 出現在第 i 行和第 j 行與第 i 列和第 j 列的交叉點上。就是說，吉文斯旋轉矩陣的所有非零元定義如下：:

{\begin{aligned}g_{k\,k}&{}=1\qquad {\text{for}}\ k\neq 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{aligned}}

乘積 $G (i, j, θ) x$ 表示向量 x 在 (i,j)平面中的逆時針旋轉 θ 弧度。

Givens 旋轉在數值線性代數中主要的用途是在向量或矩陣中介入零。例如，這種效果可用於計算矩陣的 QR分解。超過Householder變換的一個好處是它們可以輕易的並行化，另一個好處是對於非常稀疏的矩陣計算量更小。

穩定計算

當一個吉文斯旋轉矩陣 G(i,j,θ)從左側乘另一個矩陣 A 的時候，GA 只作用於 A 的第 i 和 j 行。所以我們集中於下列問題。給出 a 和 b，找到 c = cos θ 和 s = sin θ 使得

{\begin{bmatrix}c&-s\\s&c\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}r\\0\end{bmatrix}}.

明確計算出 θ 是沒有必要的。我們轉而直接獲取 c, s 和 r。一個明顯的解是

{\begin{aligned}r&{}\leftarrow {\sqrt {a^{2}+b^{2}}}\\c&{}\leftarrow a/r\\s&{}\leftarrow -b/r\end{aligned}}

但是為了避免上溢出和下溢出，我們使用不同的計算，採用比率 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定義為

\operatorname {sgn} x={\begin{cases}1&:\ x\geq 0\\-1&:\ x<0\end{cases}}

而不是常用的

\operatorname {sgn} x={\begin{cases}1&:\ x>0\\0&:\ x=0\\-1&:\ x<0\end{cases}}

後者常在高級語言中作為標準庫函數被提供，注意不要直接應用於本算法中。

參見

雅可比旋轉

引用

Golub, Gene H.; Charles F. Van Loan. Matrix Computations 3/e. Baltimore: Johns Hopkins University Press. 1996. ISBN 978-0-8018-5414-9.
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.