吉文斯旋轉(Givens rotation)
/ GIV-enz /
吉文斯旋轉是一把外科手術刀:豪斯霍爾德反射一次清掉整行,而吉文斯旋轉只把「一個」分量歸零。它在某一對座標所在的平面上,恰好旋轉所需的角度,把某個選定的數轉到零,其餘一切都不動。它是數值線性代數的精密鑷子——當矩陣已近乎三角、你只需修掉少數幾個零散分量時,再完美不過。
在座標 i 與 j 上,吉文斯旋轉是 2×2 矩陣,第一列為 (c, s)、第二列為 (-s, c),其中 c = cos(theta)、s = sin(theta) 選成使它作用在 (a, b)^T 上時產生 (r, 0)^T,其中 r = sqrt(a^2 + b^2)。你直接算 c = a/r 與 s = b/r——不需要三角函數。把它嵌入較大的單位矩陣中,它只觸及第 i 與第 j 列。和任何旋轉一樣它保持長度,因此數值穩定;對每個對角線下方的分量串接一次旋轉就把矩陣三角化,給出 QR 分解,和豪斯霍爾德一樣,只是逐項進行。
吉文斯旋轉在它的選擇性能帶來回報時最為出色:在 QR 特徵值演算法中把近三角(Hessenberg)矩陣那些孤零零的次對角分量歸零、在一列資料到來或離開時更新 QR 分解(串流式最小平方),以及在稀疏矩陣上——你不希望一次反射填掉你費心造出的零。對於從零開始的稠密矩陣,豪斯霍爾德整體上更便宜;但當你只需鎖定少數幾個待修分量時,吉文斯勝出——而且它平行性好,因為不重疊的旋轉可以同時進行。
要把行 (a, b)^T = (3, 4)^T 中的 b 歸零,取 r = 5、c = 3/5、s = 4/5;則各列為 (c, s) 與 (-s, c) 的旋轉把 (3, 4)^T 送到 (5, 0)^T。只有這一個分量被消去,周圍矩陣也只有兩列發生變化。
一次平面旋轉恰好把一個分量歸零——相對於豪斯霍爾德整行掃除的精準替代方案。
用 c = a/r、s = b/r(其中 r = sqrt(a^2 + b^2),並以 hypot 防溢位)來計算 c 與 s,而不是用顯式的反正切——呼叫三角函數既慢又較不準確。