吉文斯旋转-白红宇

吉文斯旋转

阅读量：4673 次

发布时间：2019-06-09

本文共 1071 字，大约阅读时间需要 3 分钟。

在中，吉文斯旋转（Givens rotation）是在两个坐标轴所展开的平面中的旋转。吉文斯旋转得名于华莱士·吉文斯，他在 1950 年代工作于时把它介入到数值分析中。

矩阵表示

吉文斯旋转表示为如下形式的

$G(i, k, \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 行和第k 行与第 i 列和第 k 列的交叉点上。就是说，吉文斯旋转矩阵的所有非零元定义如下：:

$\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 \\ g_{j\, i} &{}= s\end{align}$

乘积 G(i,k,θ)^Tx 表示向量 x 在 (i,k)平面中的逆时针旋转 θ 弧度。

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

稳定计算

当一个吉文斯旋转矩阵 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{align} r &{}\larr \sqrt{a^2 + b^2} \\ c &{}\larr a / r \\ s &{}\larr -b / r\end{align}$

但是为了避免上溢出和下溢出，我们使用不同的计算，采用比率 b/a (它是 tan θ)或它的倒数(Golub & Van Loan 1996)。如 Edward Anderson (2000) 在改进时发现的，前瞻数值考虑是连续性的。要完成它，我们要求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*uelse  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定义为

$\sgn x = \begin{cases} 1 & :\ x \ge 0 \\ -1 & :\ x < 0 \end{cases}$

而不是常用的

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

后者常在高级语言中作为标准库函数被提供，注意不要直接应用于本算法中。

转载于:https://www.cnblogs.com/cl1024cl/p/6205233.html

你可能感兴趣的文章

技术胖Flutter第四季-19导航父子页面的跳转返回

目录

矩阵表示

稳定计算