Householder変換(Householder transformation)とは、$0$ でないベクトル $v$ に対し $I-2vv^*/(v^*v)$ で定まるユニタリかつ Hermite な行列で、$v$ に垂直な超平面についての鏡映である。行列全体を作らず $v$ だけで掛けられ、ベクトルの下の成分をまとめて消せる。左右から同じ変換を掛ける相似変換では、一般の正方行列は上 Hessenberg 行列に、Hermite 行列は三重対角行列になり、固有値は保たれる。左右に別の変換を掛けると長方形の行列を二重対角行列にでき、特異値は保たれる。
Householder 変換 は、ベクトル $v$ に垂直な超平面についての鏡映を $H=I-\beta vv^*$ と書いた行列である。行列全体を作らなくても、$v$ と $\beta$ だけで $HB=B-\beta v(v^*B)$ と掛けられ、1 本のベクトルの下の成分をまとめて消せる。QR分解 はこの変換を左からだけ掛けて上三角行列を作る。この記事の主題はその先である:固有値を保つには左右から同じ $H$ を掛ける必要があり、そのとき上三角までは届かず、三重対角行列・Hessenberg 行列 で止まる。
この記事では、$H$ の特徴づけ、左右から掛ける更新式、三重対角化と二重対角化の定理と演算回数、いくつもの $H$ の積をまとめるブロック表現を扱う。鏡映の基本性質、$x$ を $y$ へ送る条件、符号の選び方、QR 分解の演算回数は QR分解 の補題「Householder 変換の性質」と命題「QR 分解の演算回数」に任せる。一般の形式の鏡映は 対称双線形形式 の定義「鏡映」である。
$v\in\mathbb{C}^n$、$v\ne0$ に対し
$$
H_v:=I_n-\beta vv^*,\qquad\beta:=\frac2{v^*v}
$$
を $v$ の定める Householder 変換(Householder 行列、Householder reflection)という。$w:=v/\| v\|_2$ とすると $H_v=I_n-2ww^*$ であり、$H_v$ は $v$ の定数倍で変わらない。$v$ を Householder ベクトル という。実の場合は $v\in\mathbb{R}^n$ で $H_v=I-\beta vv^{\top}$ である。
$\|\cdot\|$ はベクトルの 2 ノルムとする。$v$ に垂直な超平面の元は $H_v$ で動かず、$v$ は $-v$ に移る。
三重対角行列 とは $\lvert i-j\rvert>1$ の成分がすべて $0$ の正方行列であり、上 Hessenberg 行列 とは $i>j+1$ の成分がすべて $0$ の正方行列である。上二重対角行列 とは対角と 1 つ上の対角のほかが $0$ の行列である。
使える条件は次のとおりである。
$H=H_v$、$\beta=2/v^*v$、$B$ は $p\times q$ 行列、$v\in\mathbb{C}^p$ とする。
| 式 | 内容 | 根拠 |
|---|---|---|
| $H^*=H$、$H^2=I$、$H^*H=I$ | Hermite かつユニタリ | QR分解 の補題「Householder 変換の性質」の 1 |
| 固有値 $-1$(重複度 1)、$1$(重複度 $n-1$)、$\det H=-1$ | $v^{\perp}$ は $1$ の固有空間 | thm-hht-char の 1 |
| $HB=B-\beta v(v^*B)$ | 左更新。実の場合の演算 $4pq$ 回程度 | 分配法則 |
| $BH=B-\beta(Bv)v^*$ | 右更新。$B$ が $q\times p$ なら同じ回数 | 分配法則 |
| $HAH=A-vw^*-wv^*$ | $A$ が Hermite のときの両側更新 | prop-hht-two-sided |
| $v=x+\operatorname{sgn}(x_1)\Vert x\Vert e_1$ | 実の $x$ の下を消す(第 2 成分以下が $0$ でないとき、$\operatorname{sgn}0:=1$)。$Hx=-\operatorname{sgn}(x_1)\Vert x\Vert e_1$ | QR分解 の補題「Householder 変換の性質」の 4 |
| $\tau=1+\lvert x_1\rvert/\Vert x\Vert\in[1,2]$ | 実の $x$、$x_1\ne0$ で $v_1=1$ に正規化したときの係数 | prop-hht-normal |
| $x_1-\Vert x\Vert=-\dfrac{x_2^2+\dots+x_n^2}{x_1+\Vert x\Vert}$ | 実の $x$、$x_1>0$ で $Hx=\Vert x\Vert e_1$ としたいときの、$v_1$ の桁落ちしない式 | 分子の有理化 |
| $H_1\cdots H_k=I-VTV^*$ | ブロック表現。$T$ は上三角 | prop-hht-block |
1:$H_vv=-v$ で、$u\perp v$ なら $H_vu=u$ である。$\mathbb{C}^n=\mathbb{C}v\oplus v^{\perp}$ なので固有値はこれで尽きる。
2:$P:=\frac12(I-U)$ とおく。$U^2=U^*U=I$ から $P^2=\frac14(2I-2U)=P$、$U^*=U$ から $P^*=P$ なので、$P$ は階数 $1$ の直交射影である。その像を張る $v$ をとると $P=vv^*/v^*v$ で、$U=I-2P=H_v$ である。
3:$y=H_vx=x-\beta(v^*x)v$ より $x-y=\beta(v^*x)v$ である。$x\ne y$ なので $\beta v^*x\ne0$ で、$v$ は $x-y$ の定数倍である。$\square$
3 により、$x$ を $y$ に送る Hermite な鏡映は高々 1 つである。とくに $y^*x$ が実数でないときは、$H_{x-y}$ では送れない。このとき Hermite をあきらめる。
$\| w\|=1$、$\tau\in\mathbb{C}$ とし、$G:=I-\tau ww^*$ とおく。$G$ がユニタリであることと $\lvert1-\tau\rvert=1$ は同値である。$\| x\|=\| y\|$、$x\ne y$、$a:=\| x\|^2$、$c:=y^*x$ とする。$w:=(x-y)/\| x-y\|$、$\tau:=(2a-2\operatorname{Re}c)/(a-c)$ とおくと $Gx=y$ で $G$ はユニタリであり、$1-\tau=-(a-\bar c)/(a-c)$ である。
$G^*G=I-(\tau+\bar\tau-\lvert\tau\rvert^2)ww^*$ で、$\tau+\bar\tau-\lvert\tau\rvert^2=1-\lvert1-\tau\rvert^2$ である。これで最初の主張を得る。
$c=a$ なら $\| x-y\|^2=2a-2\operatorname{Re}c=0$ となるので $a\ne c$ である。$w^*x=(a-c)/\| x-y\|$ より
$$
Gx=x-\tau\frac{a-c}{\| x-y\|^2}(x-y)=x-(x-y)=y
$$
である。さらに $1-\tau=\dfrac{a-c-2a+c+\bar c}{a-c}=-\dfrac{a-\bar c}{a-c}$ で、$a$ は実数なので絶対値は $1$ である。$\square$
LAPACK は複素の場合にこの形を使い、$\tau$ は複素数になり、$H$ は Hermite でない(LUG99 §5.4)。
$A$ を Hermite とし、$p:=\beta Av$、$K:=\frac\beta2v^*p$、$w:=p-Kv$ とおく。$K$ は実数で、$HAH=A-vw^*-wv^*$ である。
要点:$HAH$ を展開して $p$ で書く。
$K=\frac{\beta^2}2v^*Av$ は実数である。$v^*A=p^*/\beta$ なので $HAH=A-vp^*-pv^*+\beta(v^*p)vv^*$ である。一方 $vw^*+wv^*=vp^*+pv^*-2Kvv^*=vp^*+pv^*-\beta(v^*p)vv^*$ である。$\square$
$p$ の計算は行列とベクトルの積 1 回で、Hermite 性を使えば 2 つの積の更新を半分の成分で済ませられる。
$A\in\mathbb{C}^{n\times n}$($n\ge3$)に対し、高々 $n-2$ 個の Householder 変換 $H^{(k)}$ と $U_k:=\operatorname{diag}(I_k,H^{(k)})$($1\le k\le n-2$)があり、$Q:=U_1U_2\cdots U_{n-2}$ について $Q^*AQ$ は上 Hessenberg 行列である。さらに $Qe_1=e_1$ である。$A$ が Hermite なら $Q^*AQ$ は Hermite な三重対角行列である。とくに $Q^*AQ$ の固有値は重複度を込めて $A$ の固有値と等しい。
$A_0:=A$ とし、$k=1,\dots,n-2$ の順に $A_k:=U_k^*A_{k-1}U_k$ を作る。帰納法の仮定は「$A_{k-1}$ の第 $1,\dots,k-1$ 列は、第 $j$ 列の第 $j+2$ 行以下がすべて $0$」である($k=1$ では条件なし)。
$x\in\mathbb{C}^{n-k}$ を $A_{k-1}$ の第 $k$ 列の第 $k+1,\dots,n$ 行とする。$x$ の第 $2$ 成分以下がすべて $0$ なら $U_k:=I$ とする。そうでなければ、$\sigma:=x_1/\lvert x_1\rvert$($x_1=0$ なら $\sigma:=1$)、$v:=x+\sigma\| x\| e_1$ とおくと、QR分解 の補題「Householder 変換の性質」の 4 により $H_vx=-\sigma\| x\| e_1$ である。$H^{(k)}:=H_v$ とする。
$U_k$ は最初の $k$ 個の座標を動かさない。したがって、左から $U_k^*$ を掛けると第 $k+1$ 行以下だけが変わり、右から $U_k$ を掛けると第 $k+1$ 列以降だけが変わる。よって:
左右から同じ $H$ を掛けるのが要点である。上の証明で右から掛けても第 $k$ 列が変わらないのは、$H^{(k)}$ を第 $k+1$ 行以下に作用させたからである。第 $k$ 行から消そうとすると、右から掛けたときに第 $k$ 列全体が埋まる(ex-hht-counterexamples)。対角より下の成分を全部消す QR分解 と違い、対角の 1 段下を残すのはこのためである。
実の場合はすべて実数の範囲で動く。複素の Hermite の場合に副対角の成分は一般に複素数だが、対角のユニタリ行列を掛ければ実数にできる。
Householder 変換による実対称行列の三重対角化で零の形が進む様子と、v の第 1 成分の 2 通りの計算の相対誤差
$A\in\mathbb{C}^{m\times n}$、$m\ge n$ とする。高々 $n$ 個の Householder 変換の積 $U$(ブロックを単位行列で埋めたもの)と高々 $n-2$ 個の積 $V$ があり、$U^*AV$ の上の $n\times n$ の部分は上二重対角行列で、残りの行は $0$ である。$U^*AV$ の特異値は $A$ の特異値と等しい。
$k=1,\dots,n$ の順に、次の 2 段を行う。
左:第 $k$ 列の第 $k$ 行以下を $x$ とし、$H$ で $\alpha e_1$ に送り、$\operatorname{diag}(I_{k-1},H)$ を左から掛ける。第 $1,\dots,k-1$ 列の第 $k$ 行以下はすでに $0$ なので零のままである。
右($k\le n-2$):第 $k$ 行の第 $k+1$ 列以降を行ベクトル $r$ とする。$r^*$ を $H'$ で $e_1$ の定数倍に送り、$\operatorname{diag}(I_k,H')$ を右から掛けると、$H'$ は Hermite なので第 $k$ 行の第 $k+2$ 列以降が $0$ になる。この右掛けは第 $k+1$ 列以降だけを変える。第 $1,\dots,k$ 列は変わらない。第 $j\le k-1$ 行の第 $k+1$ 列以降はすべて $0$ なので、$0$ のままである。
特異値は左右からユニタリ行列を掛けて変わらない。$\square$
この定理の左と右の $Q$ は別々でよいので、対角より下を 1 段残す必要がない。特異値の計算の最初の段に使う(LUG99 の節 Singular Value Decomposition)。
Householder 変換のベクトルの計算を除き、乗算と加減算を合わせた回数の主要項は次のとおりである。
要点:$p\times q$ の更新は $4pq$ 回で、それを足し上げる。
左更新は $v^*B$ に $2pq$ 回、$B-\beta vu^*$ に $2pq$ 回である。
1:第 $k$ 段で $p=n-k$ とする。$\beta Av$ に $2p^2$ 回、$w$ に $O(p)$ 回、対称な $A-vw^{\top}-wv^{\top}$ の下半分に $2p^2$ 回で、計 $4p^2$ 回である。$\sum_{k=1}^{n-2}4(n-k)^2\sim\frac43n^3$ である。
2:左更新 $4(n-k)^2$ 回($(n-k)\times(n-k+1)$ の主要項)、右更新 $4n(n-k)$ 回で、$\sum4(n-k)^2+\sum4n(n-k)\sim\frac43n^3+2n^3=\frac{10}3n^3$ である。
3:第 $k$ 段の左右の更新はそれぞれ $4(m-k)(n-k)$ 回の主要項をもち、$8\sum_{k=1}^n(m-k)(n-k)\sim4mn^2-\frac43n^3$ である。$\square$
$H_1\cdots H_k$ を 1 個ずつ掛ける代わりにまとめて掛けると、行列の積のルーチンを使える。
$H_j=I-\beta_jv_jv_j^*$($1\le j\le k$)、$V_k:=(v_1,\dots,v_k)$ とする。上三角行列 $T_k$ で $H_1\cdots H_k=I-V_kT_kV_k^*$ となるものが、$T_1=(\beta_1)$、
$$
T_k=\begin{pmatrix}T_{k-1}&z\\0&\beta_k\end{pmatrix},\qquad z:=-\beta_kT_{k-1}V_{k-1}^*v_k
$$
で得られる。
$k-1$ まで成り立つとする。$(I-V_{k-1}T_{k-1}V_{k-1}^*)(I-\beta_kv_kv_k^*)=I-V_{k-1}T_{k-1}V_{k-1}^*-\beta_kv_kv_k^*+\beta_kV_{k-1}T_{k-1}V_{k-1}^*v_kv_k^*$ である。最後の項は $-V_{k-1}zv_k^*$ なので、全体は $I-V_kT_kV_k^*$ である。$\square$
$x\in\mathbb{R}^n$、$x_1\ne0$、$v:=x+\operatorname{sgn}(x_1)\| x\| e_1$ とする。$u:=v/v_1$ とすると $H_v=I-\tau uu^{\top}$、$u_1=1$、$\tau=1+\lvert x_1\rvert/\| x\|\in[1,2]$ である。
$v^{\top}v=2\| x\|(\| x\|+\lvert x_1\rvert)$、$v_1^2=(\| x\|+\lvert x_1\rvert)^2$ で、$\tau=2/u^{\top}u=2v_1^2/v^{\top}v$ である。$\square$
$u_1=1$ と分かっているので、$x$ の第 $2$ 成分以下の場所に $u$ の第 $2$ 成分以下を入れ、$\tau$ を別に持てばよい。LAPACK の表現はこの形である(LUG99 §5.4)。
$A=\begin{pmatrix}1&3&4\\3&1&2\\4&2&1\end{pmatrix}$ を三重対角化する。
使う公式:thm-hht-tridiag、$v=x+\operatorname{sgn}(x_1)\| x\| e_1$
答え:
$$
T=\begin{pmatrix}1&-5&0\\-5&73/25&14/25\\0&14/25&-23/25\end{pmatrix}.
$$
$x=(3,4)$、$\| x\|=5$ より $v=(8,4)$、$(2,1)$ に取り替えてよい。$H=I_2-\frac25\begin{pmatrix}4&2\\2&1\end{pmatrix}=\begin{pmatrix}-3/5&-4/5\\-4/5&3/5\end{pmatrix}$、$Hx=(-5,0)$ である。右下の $B=\begin{pmatrix}1&2\\2&1\end{pmatrix}$ について $HBH=\begin{pmatrix}73/25&14/25\\14/25&-23/25\end{pmatrix}$ である。
トレースは $1+\frac{50}{25}=3$ で $A$ と同じである。
$A=\begin{pmatrix}4&1&-2&2\\1&2&0&1\\-2&0&3&-2\\2&1&-2&-1\end{pmatrix}$ を三重対角化する。
使う公式:thm-hht-tridiag を 2 回
答え:
$$
T=\begin{pmatrix}4&-3&0&0\\-3&10/3&-5/3&0\\0&-5/3&-33/25&68/75\\0&0&68/75&149/75\end{pmatrix}.
$$
1 回目:$x=(1,-2,2)$、$\| x\|=3$ より $v=(4,-2,2)$、第 1 列の下は $(-3,0,0)$ になる。
2 回目:このときの第 2 列の第 3、4 行を $x$ とすると $\| x\|=5/3$ で、$v=(8/3,4/3)$ となり、第 2 列の下は $(-5/3,0)$ になる。
固有値は約 $-2.1975$、$1.0844$、$2.2685$、$6.8446$ で、$A$ と $T$ で一致する。
$A=\begin{pmatrix}1&2&3\\4&5&6\\3&0&1\end{pmatrix}$ を上 Hessenberg 行列にする。
使う公式:thm-hht-tridiag の前半
答え:$Q^*AQ=\begin{pmatrix}1&-17/5&6/5\\-5&161/25&-48/25\\0&102/25&-11/25\end{pmatrix}$。$(1,3)$ 成分は $0$ にならない。
$x=(4,3)$ より $v=(9,3)$、$(3,1)$ に取り替えて $H=\begin{pmatrix}-4/5&-3/5\\-3/5&4/5\end{pmatrix}$、$U=\operatorname{diag}(1,H)$ である。トレースはどちらも $7$ である。
$A=\begin{pmatrix}1&2&1\\2&0&1\\2&1&0\end{pmatrix}$ を上二重対角にする。
使う公式:thm-hht-bidiag
答え:対角 $-3$、$-\sqrt{689}/15\approx-1.7499$、$-25\sqrt{689}/689\approx-0.9524$、その 1 つ上 $5/3$、$-66\sqrt{689}/3445\approx-0.5029$。特異値はどちらも約 $3.5619$、$1.5924$、$0.8815$ である。
左 1 回目:$x=(1,2,2)$ より $v=(4,2,2)$ で、$H_1A=\begin{pmatrix}-3&-4/3&-1\\0&-5/3&0\\0&-2/3&-1\end{pmatrix}$ である。
右 1 回目:第 1 行の $(-4/3,-1)$ に $v=(-3,-1)$ を使うと、$\begin{pmatrix}-3&5/3&0\\0&4/3&1\\0&17/15&-2/5\end{pmatrix}$ になる。
左 2 回目:第 2 列の $(4/3,17/15)$ を消す。
対角の積の絶対値は $3\cdot1.7499\cdot0.9524\approx5$ で、$\lvert\det A\rvert=5$ と合う。
$x=(i,0)$ を $y=(1,0)$ へ送るユニタリな反射子を求める。
使う公式:prop-hht-complex
答え:$\tau=1+i$、$ww^*=\operatorname{diag}(1,0)$ で $G=\operatorname{diag}(-i,1)$。
$a=1$、$c=y^*x=i$ なので $\tau=2/(1-i)=1+i$、$1-\tau=-i$ である。$G$ は Hermite でない。$y^*x=i$ は実数でないので、$H_v$ では送れない。
$v_1=(1,1)$、$v_2=(1,0)$ のとき、$H_1H_2$ を $I-VTV^{\top}$ の形に書く。
使う公式:prop-hht-block
答え:$V=\begin{pmatrix}1&1\\1&0\end{pmatrix}$、$T=\begin{pmatrix}1&-2\\0&2\end{pmatrix}$ で、$H_1H_2=\begin{pmatrix}0&-1\\1&0\end{pmatrix}$。
$\beta_1=1$、$\beta_2=2$、$z=-\beta_2\beta_1v_1^{\top}v_2=-2$ である。$VTV^{\top}=\begin{pmatrix}1&1\\-1&1\end{pmatrix}$ なので $I-VTV^{\top}$ は答えの行列に等しい。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $\Vert x\Vert=\Vert y\Vert$ | $x=(3,4)$、$y=(1,0)$ | $H_vx=y$ となる $v$ の存在 |
| $y^*x$ が実数 | $x=(i,0)$、$y=(1,0)$ | $H_vx=y$ となる $v$ の存在 |
| $x\ne y$ | $x=y=e_1$ | $v$ の一意性($v\perp x$ ならどれでも) |
| 第 $k+1$ 行以下に作用 | $A=\begin{pmatrix}1&2\\2&1\end{pmatrix}$ を第 1 行から消す | 右から掛けても零が残ること |
| 左右から掛ける | 同じ $A$ で $HA$ だけ | 固有値の保存 |
| $A$ が Hermite | ex-hht-hessenberg の $A$ | 三重対角になること |
| 符号 $\operatorname{sgn}(x_1)$ | $x=(1,t)$、$t=10^{-9}$ で $v_1=x_1-\Vert x\Vert$ を引き算のまま計算する | 倍精度の $v_1$ の精度 |
第 1、2 行:$H_v$ はユニタリなので長さを保ち、$\| x\|\ne\| y\|$ なら送れない。$x=(i,0)$ では thm-hht-char の 3 により $v$ は $e_1$ の定数倍で、$H_{e_1}x=(-i,0)\ne y$ である。
第 3 行:$x=e_1$ なら $v=e_2$ でも $H_vx=x$ である。
第 4 行:$v=(1+\sqrt5,2)$ なら $HA=\begin{pmatrix}-\sqrt5&-4\sqrt5/5\\0&-3\sqrt5/5\end{pmatrix}$ で $(2,1)$ 成分は消えるが、$HAH=\begin{pmatrix}13/5&6/5\\6/5&-3/5\end{pmatrix}$ で埋まる。第 $1$ 列が右からの $H$ で混ざるからである。
第 5 行:$A$ の固有値は $3,-1$、上の $HA$ の固有値は $-\sqrt5$、$-3\sqrt5/5$ である。
第 6 行:答えの $(1,3)$ 成分は $6/5\ne0$ である。
第 7 行:倍精度では $\sqrt{1+t^2}=1$ と丸められ、計算した $v_1$ は $0$ になる。正しい値は約 $-5\times10^{-19}$ である。$v_1=0$ なら $v=(0,t)$ で $H_v=\operatorname{diag}(1,-1)$ となり、$x$ は $e_1$ の定数倍へ移らない。失われるのは引き算で求めた $v_1$ の精度で、符号を逆にしても公式の表の有理化の式なら $v_1$ は精度よく求まる。
| 誤り | 正しくは | なぜ |
|---|---|---|
| $H$ を $n\times n$ の行列として作って掛ける | $v,\beta$ だけ持ち $B-\beta v(v^*B)$ で更新する | 公式の表の左更新の行 |
| 固有値を求めるのに QR 分解の $H$ を左からだけ掛ける | 相似変換のために左右から掛け、対角の 1 段下を残す | ex-hht-counterexamples の第 4、5 行 |
| $Q^*AQ$ の $Q$ を $A$ の固有ベクトルの行列と思う | $Q$ は三重対角化の行列で、$Q^*AQ$ は対角行列ではない | ex-hht-three の $T$ |
| 複素の場合も $H_{x-y}$ で必ず送れると思う | $y^*x$ が実数でなければ、$y$ に位相を掛けるか prop-hht-complex を使う | ex-hht-complex |
| Hermite形式 の直交基底を作るのと三重対角化を混同する | 三重対角化はユニタリ相似で、対角化はしない | thm-hht-tridiag |
実の直交行列はいくつかの鏡映の積である。直交行列 の定理「鏡映の積への分解」を参照。thm-hht-char の 1 により、鏡映の積の行列式は $(-1)^{\text{個数}}$ である。平面の回転で同じことをするのが Givens回転 である。
Arnoldi の過程の正規直交化を Householder 変換で行うこともできる(Saa03 §6.3、Algorithm 6.3、p. 163)。演算は修正 Gram–Schmidt より多いが、基底の直交性がよい。Krylov部分空間法 を参照。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する