Householder変換

同義語:ハウスホルダー変換Householder transformationHouseholder reflectionHouseholder reflectorHouseholder行列Householder matrix

概要

Householder変換(Householder transformation)とは、$0$ でないベクトル $v$ に対し $I-2vv^*/(v^*v)$ で定まるユニタリかつ Hermite な行列で、$v$ に垂直な超平面についての鏡映である。行列全体を作らず $v$ だけで掛けられ、ベクトルの下の成分をまとめて消せる。左右から同じ変換を掛ける相似変換では、一般の正方行列は上 Hessenberg 行列に、Hermite 行列は三重対角行列になり、固有値は保たれる。左右に別の変換を掛けると長方形の行列を二重対角行列にでき、特異値は保たれる。

$$\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分解, ユニタリ行列, 直交行列, 固有値

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 分解の演算回数」に任せる。一般の形式の鏡映は 対称双線形形式 の定義「鏡映」である。

定義と使える条件

Householder 変換

$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$ の行列である。
使える条件は次のとおりである。

  • $x\ne y$ を $H_v$ で移すには $\| x\|=\| y\|$ かつ $y^*x$ が実数であることが必要十分である(QR分解 の補題「Householder 変換の性質」の 2、3)。
  • 固有値を保つ縮約では、左から $Q^*$、右から $Q$ を掛ける。$Q$ の作り方は第 $k$ 列の第 $k+2$ 行以下を消す形に限る(thm-hht-tridiag)。

公式の表

$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

主定理と証明

特徴づけ

Householder 変換の特徴づけ
  1. $H_v$ の固有値は $-1$(重複度 $1$)と $1$(重複度 $n-1$)で、$\det H_v=-1$ である。
  2. $U\in\mathbb{C}^{n\times n}$ がユニタリかつ Hermite で $\operatorname{rank}(I-U)=1$ なら、$U=H_v$ となる $v\ne0$ がある。
  3. $x\ne y$ で $H_vx=y$ なら、$v$ は $x-y$ の定数倍である。
固有空間と射影で調べる

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)。

両側からの更新

Hermite 行列の両側更新

$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 つの積の更新を半分の成分で済ませられる。

三重対角化

Hessenberg 化と三重対角化

$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$ の固有値と等しい。

下を 1 段残して消す

$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$ 列以降だけが変わる。よって:

  • 第 $1,\dots,k-1$ 列:左からの作用は第 $k+1$ 行以下の成分だけを混ぜる。第 $j$ 列($j\le k-1$)の第 $k+1$ 行以下はすでに $0$ なので($j+2\le k+1$)、$0$ のままである。右からの作用はこれらの列を変えない。
  • 第 $k$ 列:左からの作用で第 $k+2$ 行以下が $0$ になる。右からの作用は第 $k$ 列を変えない。
    これが帰納法の結論である。$k=n-2$ まで終えると $A_{n-2}=Q^*AQ$ は上 Hessenberg 行列である。
    各 $U_k$ は $e_1$ を動かさないので $Qe_1=e_1$ である。$Q$ はユニタリなので $Q^*AQ$ は $A$ と相似で、固有値は重複度を込めて等しい。$A$ が Hermite なら $Q^*AQ$ も Hermite で、下三角部分の形から上三角部分の形が従い、三重対角である。$\square$

左右から同じ $H$ を掛けるのが要点である。上の証明で右から掛けても第 $k$ 列が変わらないのは、$H^{(k)}$ を第 $k+1$ 行以下に作用させたからである。第 $k$ 行から消そうとすると、右から掛けたときに第 $k$ 列全体が埋まる(ex-hht-counterexamples)。対角より下の成分を全部消す QR分解 と違い、対角の 1 段下を残すのはこのためである。
実の場合はすべて実数の範囲で動く。複素の Hermite の場合に副対角の成分は一般に複素数だが、対角のユニタリ行列を掛ければ実数にできる。
Householder 変換による実対称行列の三重対角化で零の形が進む様子と、v の第 1 成分の 2 通りの計算の相対誤差 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 変換のベクトルの計算を除き、乗算と加減算を合わせた回数の主要項は次のとおりである。

  1. 実対称行列の三重対角化:$\frac43n^3$
  2. 一般の実行列の Hessenberg 化:$\frac{10}3n^3$
  3. $m\ge n$ の実行列の二重対角化:$4mn^2-\frac43n^3$
段ごとに足す

要点:$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)。

計算の手順

  1. $v$ を作る:$x$ の第 $2$ 成分以下がすべて $0$ なら何もしない。そうでなければ $\| x\|_{\infty}$ で割ってから 2 ノルムをとる(途中のあふれを防ぐ)。$v=x+\operatorname{sgn}(x_1)\| x\| e_1$($x_1=0$ なら $\operatorname{sgn}(x_1):=1$)、$\beta=2/v^{\top}v$ とする。$v^{\top}v$ は $2\| x\|(\| x\|+\lvert x_1\rvert)$ で計算できる。
  2. 三重対角化(実対称の $A$):$k=1,\dots,n-2$ について、第 $k$ 列の第 $k+1$ 行以下を $x$ として $v$ を作る。右下の $(n-k)\times(n-k)$ の部分を $B$ とする。$p=\beta Bv$、$K=\frac\beta2v^{\top}p$、$w=p-Kv$ を計算し、$B\leftarrow B-vw^{\top}-wv^{\top}$ とする。第 $k$ 列の下は $(\alpha,0,\dots,0)^{\top}$($\alpha=-\operatorname{sgn}(x_1)\| x\|$)とする。
  3. $Q$ が要るとき:$v$ を保存しておき、$Q=U_1\cdots U_{n-2}$ を $U_{n-2}$ の側から順に掛けて作る。$U_{n-2}$ の側からだと、まだ単位行列の部分が多く、演算が少ない。
  4. 次の段:三重対角行列の固有値は QR 法などで求め(QR分解 の注意「QR 法」)、$A$ の固有ベクトルは $T$ の固有ベクトルに $Q$ を掛けて得る。

例題

3 次の対称行列の三重対角化

$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$ と同じである。

4 次の対称行列の三重対角化

$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$ で一致する。

非対称な行列の Hessenberg 化

$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$ と合う。

Hermite にならない鏡映

$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$ が Hermiteex-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回転 である。

Krylov 部分空間の基底

Arnoldi の過程の正規直交化を Householder 変換で行うこともできる(Saa03 §6.3、Algorithm 6.3、p. 163)。演算は修正 Gram–Schmidt より多いが、基底の直交性がよい。Krylov部分空間法 を参照。

文献

Householder 変換の定義、更新式 $(I-2ww^{\top})X=X-wv^{\top}$ は Saa03 §1.7(pp. 12–15)にある。LAPACK の $H=I-\tau vv^*$ の表現と $\tau$ の範囲、三重対角化と二重対角化の位置づけは LUG99 にある。この記事の定理の証明と演算回数の計算は、記事の中で完結している。

関連項目

参考文献

[1]
Yousef Saad, Iterative Methods for Sparse Linear Systems, Second Edition, SIAM, 2003, §1.7(pp. 12–15)、§6.3 Algorithm 6.3(p. 163)
[2]

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