Givens回転

同義語:ギブンス回転Givens rotationGivens変換Givens transformation

概要

Givens回転(Givens rotation)とは、単位行列の第 $i,j$ 行と第 $i,j$ 列の交点だけを $2\times2$ の回転に置き換えた行列で、ベクトルの第 $j$ 成分を第 $i$ 成分へまとめて $0$ にするものである。2 行しか変えないので、$0$ の多い行列の QR 分解や上三角行列の更新に向く。特殊直交群の元は高々 $n(n-1)/2$ 個の Givens 回転の積である。左右から掛けて非対角成分を減らす Jacobi の固有値法にも使う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: QR分解, 直交行列, 回転行列, 固有値

Givens 回転 は、単位行列の第 $i,j$ 行と第 $i,j$ 列の交点だけを $2\times2$ の回転に置き換えた行列で、第 $i$ 成分と第 $j$ 成分を混ぜて 1 つの成分を $0$ にする。Householder変換 が 1 回でベクトルの下の成分をまとめて消すのに対し、Givens 回転は 1 回に 1 成分だけを消す。その代わり 2 行(または 2 列)しか変えないので、すでに $0$ の成分の多い行列で無駄がない。
定義と QR分解 への使い方は QR分解 の定義「Householder 変換と Givens 回転」にあり、QR 分解全体の演算回数も同記事の命題「QR 分解の演算回数」にある。この記事では、$c,s$ の計算法と規約の違い、$SO(n)$ が Givens 回転で生成されること、上三角行列の更新、Hessenberg 行列の最小二乗問題、Jacobiの固有値法 の 1 歩と収束を扱う。連立 1 次方程式の反復解法である Jacobi法 とは別のものである。

定義と使える条件

Givens 回転

$(a,b)\in\mathbb{C}^2$、$(a,b)\ne(0,0)$ に対し、$r:=\sqrt{\lvert a\rvert^2+\lvert b\rvert^2}$、$c:=a/r$、$s:=b/r$ とし、
$$ G:=\begin{pmatrix}\bar c&\bar s\\-s&c\end{pmatrix} $$
とおくと、$G$ はユニタリで $G(a,b)^{\top}=(r,0)^{\top}$ である。$1\le i< j\le n$ について、単位行列の $(i,i),(i,j),(j,i),(j,j)$ 成分をこの $G$ の成分で置き換えた $n$ 次行列 $G(i,j)$ を Givens 回転(Givens rotation)という。

実の場合、$c=\cos\theta$、$s=\sin\theta$ と書けて
$$ G=\begin{pmatrix}c&s\\-s&c\end{pmatrix}=R(-\theta) $$
であり、$\det G=1$ である。ここで $R(\theta)$ は 回転行列 の反時計回りの回転で、$G$ は $(a,b)$ を第 1 軸へ時計回りに回す。$c^2+s^2=1$ の実数 $c,s$ はどれも $(a,b)=(c,s)$ から得られるので、この形の行列はすべて Givens 回転である。平面回転 はより広い語で、座標平面に限らない平面の回転も指す。
規約は文献で異なる。 次の表の違いは符号と共役だけだが、混ぜると結果の符号が変わる。

文献の形行列$r$ の符号複素の場合の $c$
この記事、QR分解$\begin{pmatrix}\bar c&\bar s\\-s&c\end{pmatrix}$$r\ge0$複素数
BDKM02$\begin{pmatrix}c&s\\-\bar s&c\end{pmatrix}$$c\ge0$ で、$a\ne0$ なら $\operatorname{sign}(a)\sqrt{\lvert a\rvert^2+\lvert b\rvert^2}$、$a=0$ なら $\lvert b\rvert$実数
回転行列$\begin{pmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{pmatrix}$実の場合のみ

BDKM02 によれば、$c,s,r$ が一意に決まらないため、LAPACK と BLAS のルーチンは数学的に同じ入力で大きく異なる値を返すことがある(p. 2)。
使える条件は次のとおりである。

  • $(a,b)=(0,0)$ なら何もしなくてよい($r=0$ で割らない)。
  • 複素の成分を消すには複素の $G$ が要る。実の回転だけでは $(1,i)$ の第 2 成分は消せない(ex-gvr-counterexamples)。
  • 消す順序を選ぶ。すでに作った $0$ の行と $0$ でない成分を混ぜると $0$ が埋まる。

公式の表

$a,b$ を実数とする。

式内容根拠
$r=\sqrt{a^2+b^2}$、$c=a/r$、$s=b/r$基本の公式。$(a,b)\ne(0,0)$def-gvr-main
$\lvert b\rvert\ge\lvert a\rvert$ で $t=a/b$、$u=\sqrt{1+t^2}$、$s=\operatorname{sgn}(b)/u$、$c=ts$あふれを防ぐ($\lvert a\rvert>\lvert b\rvert$ なら $a,b$ を入れ替えた式)$r=\lvert b\rvert u$
$g_i\leftarrow cg_i+sg_j$、$g_j\leftarrow-sg_i+cg_j$($g_i$ は第 $i$ 行、同時に更新)左からの更新。1 列あたり乗算 4 回と加算 2 回行列の積
$\operatorname{off}(GAG^{\top})^2=\operatorname{off}(A)^2-2a_{pq}^2$($A$ は実対称、$a_{pq}\ne0$)Jacobi の 1 歩thm-gvr-jacobi-step
残差 $=\beta\lvert s_1\cdots s_k\rvert$(副対角はすべて $0$ でない)Hessenberg 行列の最小二乗prop-gvr-hessenberg

主定理と証明

回転の積

回転の積による特殊直交群の表示

$Q\in SO(n)$ は、高々 $\frac{n(n-1)}2$ 個の実の Givens 回転の積である。$Q\in O(n)$ で $\det Q=-1$ なら、$Q$ はそのような積と $\operatorname{diag}(1,\dots,1,-1)$ の積である。

列ごとに消す

$Q\in O(n)$、$d:=\det Q=\pm1$ とする。$j=1,\dots,n-1$ の順に、各 $j$ で $i=j+1,\dots,n$ の順に、現在の行列の $(a,b):=(Q_{jj},Q_{ij})$ が $(0,0)$ でなければ、$(a,b)$ から定まる Givens 回転 $G(j,i)$ を左から掛ける。$r>0$ なので $b=0$ でも掛けられる($a< 0$ なら $2\times2$ の部分は $-I_2$ で、これも回転である)。
第 $j$ 列の処理の前に、第 $1,\dots,j-1$ 列が $e_1,\dots,e_{j-1}$ であるとする。行列は直交行列なので、第 $1,\dots,j-1$ 行も $e_1^{\top},\dots,e_{j-1}^{\top}$ であり、第 $j$ 列の第 $j$ 行以降の長さは $1$ である。$G(j,i)$ は第 $j$ 行と第 $i$ 行だけを変えるので、第 $1,\dots,j-1$ 列は変わらない。
$G(j,i)$ は $(i,j)$ 成分を $0$ にし、それ以後の第 $j$ 列の処理は第 $i$ 行を変えない。第 $j$ 列の長さが $1$ なので、$(a,b)\ne(0,0)$ の段が少なくとも 1 回ある。その段の後は $(j,j)$ 成分が $r>0$ で、以後の段でも正のままである。処理の後は下の成分がすべて $0$ で長さが $1$ なので、$(j,j)$ 成分は $1$ である。よって第 $j$ 列は $e_j$ になる。
最後の行列 $G_N\cdots G_1Q$ は第 $1,\dots,n-1$ 列が $e_1,\dots,e_{n-1}$ の直交行列なので、$\operatorname{diag}(1,\dots,1,e)$($e=\pm1$)であり、回転の行列式が $1$ なので $e=d$ である。$N\le\frac{n(n-1)}2$ である。各 $G_k^{-1}=G_k^{\top}$ もまた実の Givens 回転なので、
$$ Q=G_1^{\top}\cdots G_N^{\top}\operatorname{diag}(1,\dots,1,d) $$
である。$\square$

$\frac{n(n-1)}2$ は 特殊直交群 の次元に等しい。列を順に見る形の Euler 角の一般化である。

上三角行列の更新

行を 1 本足す更新

$R$ を $n$ 次上三角行列、$a\in\mathbb{C}^n$ とする。$\begin{pmatrix}R\\a^*\end{pmatrix}$ に、第 $1,\dots,n$ 行と最後の行の Givens 回転を順に掛けると、$\begin{pmatrix}R'\\0\end{pmatrix}$($R'$ は上三角)になり、$R'^*R'=R^*R+aa^*$ である。実の場合の演算回数の主要項は $3n^2$ である。

最後の行の成分を左から順に消す

要点:第 $i$ 段は第 $i$ 行と最後の行の第 $i$ 列以降だけを変える。

詳しい証明を開く

第 $i$ 段の前に、最後の行の第 $1,\dots,i-1$ 列は $0$ で、第 $i$ 行の第 $i$ 列より左も $0$ である。よって回転は第 $i$ 列より左を変えず、最後の行の第 $i$ 成分を $0$ にする。

左からユニタリ行列 $W$ を掛けても $M^*M$ は変わらないので、$R'^*R'=\begin{pmatrix}R^*&a\end{pmatrix}\begin{pmatrix}R\\a^*\end{pmatrix}=R^*R+aa^*$ である。第 $i$ 段の演算は $6(n-i+1)$ 回で、和は $3n^2$ の主要項をもつ。$\square$

$A=QR$ が分かっているときに行を 1 本足した行列の $R$ を、$A$ に戻らずに $O(n^2)$ 回で得られる。最小二乗法の逐次更新に使う。

Hessenberg 行列の最小二乗

上 Hessenberg 行列の最小二乗

$\bar H$ を $(k+1)\times k$ の上 Hessenberg 行列で副対角成分がすべて $0$ でないとし、$\beta>0$ とする。第 $i$ 段に第 $(i,i+1)$ 行の Givens 回転 $G_i$(係数 $c_i,s_i$)を順に掛けて $\bar H$ を上三角化すると、$\min_y\|\beta e_1-\bar Hy\|=\beta\lvert s_1\cdots s_k\rvert$ である。演算は $O(k^2)$ 回である。

右辺も回す

要点:$G:=G_k\cdots G_1$ を右辺にも掛けると、最後の成分が残差になる。

詳しい証明を開く

$G\bar H=\begin{pmatrix}R\\0\end{pmatrix}$ で、$R$ は $k$ 次上三角である。副対角が $0$ でないので各段の $b\ne0$ で $s_i\ne0$ であり、$R$ の対角成分 $r_i>0$ なので $R$ は正則である。

$g:=G(\beta e_1)$ とおく。第 $i$ 段は第 $i,i+1$ 成分だけを変え、そのときの第 $i+1$ 成分は $0$ である。第 $i$ 成分を $g_i^{(i)}$ とすると、第 $i+1$ 成分は $-s_ig_i^{(i)}$ になるので、$\lvert g_{k+1}\rvert=\beta\lvert s_1\cdots s_k\rvert$ である。

$\|\beta e_1-\bar Hy\|^2=\|g_{1:k}-Ry\|^2+\lvert g_{k+1}\rvert^2$ で、$Ry=g_{1:k}$ により第 1 項を $0$ にできる。$\square$

Krylov部分空間法 の定理「GMRES の公式と単調性」の計算はこの形で、各段で $s_k$ が分かるので、解を作らずに残差を監視できる。

Jacobi の固有値法

実対称行列 $A=(a_{ij})$ について $\operatorname{off}(A)^2:=\sum_{i\ne j}a_{ij}^2$ とおく。$a_{pq}\ne0$($p< q$)に対して $\tau:=(a_{pp}-a_{qq})/(2a_{pq})$、$t:=\operatorname{sgn}(\tau)/(\lvert\tau\rvert+\sqrt{1+\tau^2})$($\operatorname{sgn}0:=1$)、$c:=1/\sqrt{1+t^2}$、$s:=tc$ とし、$G$ を第 $(p,q)$ の実の Givens 回転とする。

Jacobi の 1 歩

$B:=GAG^{\top}$ は実対称で、$b_{pq}=0$、$b_{pp}=a_{pp}+ta_{pq}$、$b_{qq}=a_{qq}-ta_{pq}$、$\lvert t\rvert\le1$ であり、
$$ \operatorname{off}(B)^2=\operatorname{off}(A)^2-2a_{pq}^2 $$
である。

2 行 2 列の部分と Frobenius ノルム

$\begin{pmatrix}a&d\\d&b\end{pmatrix}:=\begin{pmatrix}a_{pp}&a_{pq}\\a_{pq}&a_{qq}\end{pmatrix}$ と書く。$2\times2$ の積を計算すると
$$ b_{pq}=(c^2-s^2)d+cs(b-a)=c^2\bigl((1-t^2)d+t(b-a)\bigr)=-c^2d\,(t^2+2\tau t-1) $$
である。$t$ は $t^2+2\tau t-1=0$ の絶対値の小さい方の根なので(根の積が $-1$ なので $\lvert t\rvert\le1$)、$b_{pq}=0$ である。実際 $t=-\tau+\operatorname{sgn}(\tau)\sqrt{1+\tau^2}=\operatorname{sgn}(\tau)/(\lvert\tau\rvert+\sqrt{1+\tau^2})$ である。
次に $(b-a)=(t^2-1)d/t$($t\ne0$)を使うと、
$$ b_{pp}-a=c^2a+2csd+s^2b-a=s^2(b-a)+2csd=c^2t\,d\,(t^2-1+2)=td $$
である。トレースは保たれるので $b_{qq}=b-td$ である。
$i\ne p,q$ の成分について、$(b_{ip},b_{iq})$ は $(a_{ip},a_{iq})$ の回転なので $b_{ip}^2+b_{iq}^2=a_{ip}^2+a_{iq}^2$ である。$\{p,q\}$ に含まれない添字の成分は変わらない。$2\times2$ の部分の Frobenius ノルムは保たれるので、$b_{pp}^2+b_{qq}^2=a^2+b^2+2d^2$ である。全体の Frobenius ノルムは保たれるので、非対角の 2 乗和は $2d^2$ だけ減る。$\square$

最大成分を選ぶ Jacobi 法の収束

$A_0$ を $n$ 次実対称行列($n\ge2$)とする。各段で $\lvert a_{pq}\rvert$ が最大の $(p,q)$($p< q$)を選んで thm-gvr-jacobi-step の $G_k$ を作り、$A_{k+1}:=G_kA_kG_k^{\top}$ とする($\operatorname{off}(A_k)=0$ なら止める)。このとき
$$ \operatorname{off}(A_k)^2\le\Bigl(1-\frac2{n(n-1)}\Bigr)^k\operatorname{off}(A_0)^2 $$
であり、$A_k$ の対角成分は収束し、その極限を並べたものは重複度を込めて $A_0$ の固有値である。

等比数列で抑える

非対角の成分は $n(n-1)$ 個あり、$a_{pq}^2$ は最大なので $2a_{pq}^2\ge\frac2{n(n-1)}\operatorname{off}(A_k)^2$ である。thm-gvr-jacobi-step から不等式を得る。
$\rho:=(1-\frac2{n(n-1)})^{1/2}< 1$ とおく。1 歩で対角成分は $\lvert ta_{pq}\rvert\le\lvert a_{pq}\rvert\le\operatorname{off}(A_k)\le\rho^k\operatorname{off}(A_0)$ しか動かない。この上界の和は収束するので、対角成分は Cauchy 列であり、極限 $D=\operatorname{diag}(\lambda_1,\dots,\lambda_n)$ をもつ。$\operatorname{off}(A_k)\to0$ なので $A_k\to D$ である。$A_k$ は $A_0$ と相似なので固有多項式は等しく、固有多項式の連続性から $\prod_i(x-\lambda_i)$ は $A_0$ の固有多項式である。$\square$

正定値の実対称行列について組を順に回す形の Jacobi の手順は DV92 §3、Algorithm 3.1 にある(そこでは回転の符号の規約が逆である)。固有ベクトルの収束はこの記事では証明しない(固有値が分離していて $\operatorname{off}$ が十分小さいときの順に回す形の 2 次収束は Jacobiの固有値法 の定理「掃引の 2 次収束」、止めたときの誤差は同記事の命題「固有値・固有ベクトルの誤差」にある)。計算では許容誤差 $\varepsilon$ を決め、$\operatorname{off}(A_k)\le\varepsilon\bigl(\sum_{i,j}(a_{ij}^{(0)})^2\bigr)^{1/2}$($a_{ij}^{(0)}$ は $A_0$ の成分)になったら止める。
左は (a,b) を第 1 軸へ回す Givens 回転の幾何、右は Jacobi の方法で非対角部分が定理の上界より速く減る様子 左は (a,b) を第 1 軸へ回す Givens 回転の幾何、右は Jacobi の方法で非対角部分が定理の上界より速く減る様子

計算の手順

  1. $c,s$ を計算する:$(a,b)=(0,0)$ なら $c=1,s=0$(何もしない)。そうでなければ、絶対値の大きい方で割る公式であふれを防ぐ。
  2. 更新する:第 $i,j$ 行のうち、$0$ でない列だけを更新する。$Q$ が要らないなら $c,s$ は使い捨てでよい。
  3. 消す順を決める:第 $k$ 列を消すときは第 $k$ 列より左がすべて $0$ の行どうしを組み合わせる。Hessenberg 行列なら $(1,2),(2,3),\dots$ の順である。
  4. $c,s$ を保存する:次の命題の 1 つの数 $z$ にまとめて、消した成分の場所に入れられる。
1 つの数への保存

実数 $(a,b)\ne(0,0)$ について、$\sigma$ を絶対値の大きい方の符号($\lvert a\rvert>\lvert b\rvert$ なら $\operatorname{sgn}a$、それ以外は $\operatorname{sgn}b$)、$r:=\sigma\sqrt{a^2+b^2}$、$c:=a/r$、$s:=b/r$ とする。$\lvert a\rvert>\lvert b\rvert$ なら $z:=s$、そうでなく $c\ne0$ なら $z:=1/c$、$c=0$ なら $z:=1$ とおく。$z$ から $(c,s)$ は次のように戻せる:$z=1$ なら $(0,1)$、$\lvert z\rvert< 1$ なら $(\sqrt{1-z^2},z)$、$\lvert z\rvert>1$ なら $(1/z,\sqrt{1-1/z^2})$。

場合分け

要点:$r$ の符号の選び方で、大きい方の係数が正になる。

詳しい証明を開く

$\lvert a\rvert>\lvert b\rvert$ のとき:$c=\lvert a\rvert/\sqrt{a^2+b^2}>0$、$\lvert s\rvert< 1$ なので $\lvert z\rvert< 1$ で $c=\sqrt{1-z^2}$ である。

$\lvert a\rvert\le\lvert b\rvert$、$c\ne0$ のとき:$s=\lvert b\rvert/\sqrt{a^2+b^2}>0$、$0< \lvert c\rvert\le s$ なので $\lvert c\rvert\le1/\sqrt2$、$\lvert z\rvert\ge\sqrt2>1$ である。$c=1/z$、$s=\sqrt{1-c^2}$ である。

$c=0$ のとき:$a=0$、$s=1$ である。$\square$

例題

基本の回転とあふれ

$(3,4)$ と $(3\cdot10^{200},4\cdot10^{200})$ の第 2 成分を消す。
使う公式:表の第 1、2 行
答え:どちらも $c=3/5$、$s=4/5$ で、$r=5$ と $r=5\cdot10^{200}$。

途中の計算を開く

$G=\frac15\begin{pmatrix}3&4\\-4&3\end{pmatrix}$、$G(3,4)^{\top}=(5,0)^{\top}$ である。

2 つ目では倍精度の $a^2+b^2$ はあふれる。$t=a/b=3/4$、$u=\sqrt{1+9/16}=5/4$、$s=4/5$、$c=3/5$、$r=bu=5\cdot10^{200}$ である。

三角行列に行を足す

$R=\begin{pmatrix}3&4\\0&3\end{pmatrix}$ に行 $(4,12)$ を足した行列を上三角にする。
使う公式:prop-gvr-update
答え:$R'=\begin{pmatrix}5&12\\0&5\end{pmatrix}$。

途中の計算を開く

第 1 行と第 3 行に $(3,4)$ の回転:$(3,4)\to(5,12)$、$(4,12)\to(0,4)$ である。

第 2 行と第 3 行に $(3,4)$ の回転:$(0,3)\to(0,5)$、$(0,4)\to(0,0)$ である。

$R'^{\top}R'=\begin{pmatrix}25&60\\60&169\end{pmatrix}=R^{\top}R+aa^{\top}$ である。

Hessenberg 行列の最小二乗

$\bar H=\begin{pmatrix}3&10\\4&5\\0&12\end{pmatrix}$、$\beta=5$ のとき、$\min_y\|\beta e_1-\bar Hy\|$ を求める。
使う公式:prop-gvr-hessenberg
答え:$48/13$($y=(307/845,\,20/169)$)。

途中の計算を開く

1 回目:$(3,4)$ で $c_1=3/5$、$s_1=4/5$、$\bar H\to\begin{pmatrix}5&10\\0&-5\\0&12\end{pmatrix}$、右辺 $\to(3,-4,0)$ である。

2 回目:$(-5,12)$ で $c_2=-5/13$、$s_2=12/13$、$\bar H\to\begin{pmatrix}5&10\\0&13\\0&0\end{pmatrix}$、右辺 $\to(3,20/13,48/13)$ である。

残差は $5\cdot\frac45\cdot\frac{12}{13}=\frac{48}{13}$ で、右辺の最後の成分に一致する。

3 次の回転の分解

$Q=\frac13\begin{pmatrix}2&-1&2\\2&2&-1\\-1&2&2\end{pmatrix}\in SO(3)$ を単位行列まで消す。
使う公式:thm-gvr-product
答え:$G(1,2)$($45^{\circ}$)、$G(1,3)$($\approx-19.47^{\circ}$)、$G(2,3)$($45^{\circ}$)の 3 回で $G_3G_2G_1Q=I_3$。

途中の計算を開く

1 回目:$(2/3,2/3)$ で $c=s=1/\sqrt2$ である。第 1 列は $(2\sqrt2/3,0,-1/3)$ になる。

2 回目:$(2\sqrt2/3,-1/3)$ で $c=2\sqrt2/3$、$s=-1/3$ である。第 1 列は $e_1$ になり、右下は $\frac1{\sqrt2}\begin{pmatrix}1&-1\\1&1\end{pmatrix}$ である。

3 回目:$(1/\sqrt2,1/\sqrt2)$ で $c=s=1/\sqrt2$ である。

Jacobi の方法の計算

$A=\begin{pmatrix}2&1&0\\1&2&1\\0&1&2\end{pmatrix}$ に最大成分を選ぶ Jacobi 法を当てる。固有値は $2-\sqrt2,\,2,\,2+\sqrt2$ である。最大の成分が同点のときは、行番号と列番号の小さい組を選ぶ。
使う公式:thm-gvr-jacobi-step
答え:$\operatorname{off}^2$ は $4,\,2,\,1,\,0.2113,\,0.0580,\,5.70\times10^{-4},\,8.31\times10^{-6}$ と減り、対角は $3.41421356$、$0.58578644$、$2.00000000$ へ近づく。

途中の計算を開く

1 歩目:$(p,q)=(1,2)$ で $\tau=0$、$t=1$、$c=s=1/\sqrt2$ である。$A_1=\begin{pmatrix}3&0&1/\sqrt2\\0&1&1/\sqrt2\\1/\sqrt2&1/\sqrt2&2\end{pmatrix}$ で、$(1,3)$ 成分が埋まる。

2 歩目:$(p,q)=(1,3)$ で $\tau=1/\sqrt2$、$t=2/(\sqrt2+\sqrt6)\approx0.5176$ である。対角は $3+t/\sqrt2\approx3.3660$ と $2-t/\sqrt2\approx1.6340$ になる。

使える条件と反例

外す条件反例成り立たなくなること
$(a,b)\ne(0,0)$$(0,0)$$c=a/r$ の定義
複素の $G$ を使う$(1,i)$ と実の回転第 2 成分を消せること
第 $k$ 列より左が $0$ の行どうしを使う$\begin{pmatrix}5&7/5\\0&1\\0&-1/5\end{pmatrix}$ の $(3,2)$ 成分を第 1、3 行で消す第 1 列の $0$ が残ること
$\det Q=1$$\operatorname{diag}(1,\dots,1,-1)$回転の積であること
片側から掛けるex-gvr-jacobi の 2 歩目作った $0$ が残ること($\operatorname{off}$ は減る)
$t$ は小さい方の根$\begin{pmatrix}1&\varepsilon\\\varepsilon&0\end{pmatrix}$ で大きい根を使う対角の動きが小さいこと
最大成分を選ぶex-gvr-jacobi の $A$ で $(1,2)$ を選び続ける$\operatorname{off}\to0$
反例の確かめ

表の各行の確かめは次のとおりである。

各行の確かめを開く

第 2 行:実の $c,s$ で $-s\cdot1+c\cdot i=0$ なら実部と虚部から $s=c=0$ となり、$c^2+s^2=1$ に反する。

第 3 行:第 1、3 行の回転は $(7/5,-1/5)$ から定まり、$(3,1)$ 成分は $-s\cdot5=\sqrt2/2\ne0$ となる。第 2、3 行を使えば第 1 列は変わらない。

第 4 行:回転の行列式は $1$ である。

第 5 行:Jacobi の 1 回は左右から掛けるので、第 $p,q$ 行と第 $p,q$ 列が変わり、1 歩目に作った $(1,2)$ 成分の $0$ は 2 歩目で $s/\sqrt2\ne0$ に埋まる。それでも $\operatorname{off}^2$ は減る。

第 6 行:$\tau=1/(2\varepsilon)$、大きい根は $t'=-1/t\approx-1/\varepsilon$ である。$b_{pq}=0$ だが、$b_{pp}=1+t'\varepsilon\approx0$ で対角が入れ替わり、$\varepsilon$ が小さくても対角の変化が $1$ 程度になる。

第 7 行:1 回で $(1,2)$ 成分は $0$ になり、2 回目からは $a_{pq}=0$ で何も変わらない。$\operatorname{off}^2=2$ のままである。

よくある誤り

誤り正しくはなぜ
$\sqrt{a^2+b^2}$ をそのまま計算する大きい方で割ってからあふれを防ぐex-gvr-basic
$\begin{pmatrix}c&s\\-s&c\end{pmatrix}$ を反時計回りの回転と読む$(a,b)$ を第 1 軸へ回す向き($R(-\theta)$)である$(a,b)$ が $(r,0)$ に移る
ライブラリどうしで $c,s$ の符号が同じと思う$r$ の符号の規約が異なる$c,s,r$ は一意に決まらない(BDKM02 p. 2)
密行列の QR 分解に Givens 回転を使う演算回数は Householder 変換より多い(QR分解 の命題「QR 分解の演算回数」)。$0$ の多い行列で使うrem-gvr-compare
Jacobi の固有値法と連立方程式の Jacobi法 を混同する別の方法である。固有値法は回転で対角化するthm-gvr-jacobi は相似変換の反復である

補足

Householder 変換との使い分け

密行列の $m\times n$ の QR 分解は Householder 変換で $2mn^2-\frac23n^3$ 回、Givens 回転で $3mn^2-n^3$ 回である。上 Hessenberg 行列なら Givens 回転 $n-1$ 個で $3n^2$ 回で済む。帯行列を三重対角や二重対角に縮約するときも LAPACK は Givens 回転を使う(LUG99 の節 Symmetric Eigenproblems、節 Singular Value Decomposition)。

反復法の中の回転

平面回転で Hessenberg 行列を三角化する手順は Saa03 §6.5.3(pp. 174–175)にある。Jacobi の方法は QR 法より遅いことが多いが、正定値行列で高い相対精度をもつことが DV92 で調べられている。$c,s$ の計算の注意は BDKM02 にある。

関連項目

参考文献

[1]
David Bindel, James Demmel, William Kahan, Osni Marques, On computing Givens rotations reliably and efficiently, ACM Transactions on Mathematical Software, 2002, pp. 206–238(LAPACK Working Note 148 の pp. 1–2)
[2]
James Demmel, Krešimir Veselić, Jacobi's method is more accurate than QR, SIAM Journal on Matrix Analysis and Applications, 1992, pp. 1204–1245(LAPACK Working Note 15 の §3 Algorithm 3.1)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する