ハウスホルダー変換

線型代数学におけるハウスホルダー変換（ハウスホルダーへんかん、英: Householder transformation）、ハウスホルダー鏡映 (Householder reflection) あるいは基本鏡映子 (elementary reflector) は、原点を含む平面または超平面に関する鏡映を記述する線型変換である。ハウスホルダー変換は A. S. Householder (1958) が導入した。一般の内積空間上にも対応するハウスホルダー作用素がある。

定義

変換として

鏡映を定める超平面は、それに直交する単位列ベクトル（長さ $1$ のベクトル） $v$ によって定義することができる。この超平面に関する点 $x$ の鏡像は線型変換 ${\boldsymbol {x}}':={\boldsymbol {x}}-2\langle {\boldsymbol {x}},{\boldsymbol {v}}\rangle {\boldsymbol {v}}={\boldsymbol {x}}-2{\boldsymbol {v}}({\boldsymbol {v}}^{*}{\boldsymbol {x}})$ で与えられる。この変換 $x \mapsto x'$ をハウスホルダー変換と呼ぶ。ただし、 $v *$ は $v$ のエルミート転置である。

行列として

ハウスホルダー変換の表現行列はハウスホルダー行列と呼ばれ、ベクトルの直積を用いて ${\boldsymbol {P}}:={\boldsymbol {I}}-2({\boldsymbol {v}}\otimes {\boldsymbol {v}})={\boldsymbol {I}}-2{\boldsymbol {v}}{\boldsymbol {v}}^{*}$ と書ける（ $I$ は単位行列）。

性質

ハウスホルダー行列 $P$ は以下のような性質を満たす:

$P$ はエルミート: ${\textstyle {\boldsymbol {P}}={\boldsymbol {P}}^{*}}$ ，
$P$ はユニタリ: ${\textstyle {\boldsymbol {P}}^{-1}={\boldsymbol {P}}^{*}}$ ，
$P$ は対合的（英語版）: ${\textstyle {\boldsymbol {P}}^{2}={\boldsymbol {I}}}$ 。
ハウスホルダー行列の固有値は $\pm1$ である。これを見るために、 $u$ が鏡映を定めるベクトル $v$ に直交するならば $Pu = u$ であることに注意する。すなわち、 $1$ は重複度 $n - 1$ の固有値である（ $v$ に直交する線型独立なベクトルは $n - 1$ 本ある）。同様に、 $Pv = - v$ であり、したがって $-1$ は重複度 $1$ の固有ベクトルとなる。
ハウスホルダー鏡映の行列式は $-1$ である。これは行列式が固有値の総乗に等しいことに注意すれば、前条より出る（ $1 n -1 \cdot(-1) 1 = -1$ ）

応用

幾何光学

幾何光学において、鏡面反射はハウスホルダー行列を用いて表せる。

数値線形代数

ハウスホルダー変換はQR法の第一段階であり、QR分解を行うために、数値線形代数において広く用いられる。同様に、対称行列の三重対角化や非対称行列のヘッセンベルク化（英語版）にも広くもちいられる。

QR 分解

ハウスホルダー鏡映はQR分解の計算に用いることができる: 「与えられた行列の第一列ベクトルを鏡映により標準基底ベクトルのスカラー倍へ写し、その変換行列を計算し、それをもとの行列に掛ける」という操作をさらにその行列の積の $(i, i)$ -小行列に対して再帰的に繰り返す。

三重対角化

→詳細は「三重対角化行列（英語版）」を参照

他のユニタリ変換との関係

→「回転 (数学)」も参照

既に述べた通り、ハウスホルダー変換は、単位法ベクトル $v$ を持つ超平面に関する鏡映である。 $N \times N$ ユニタリ変換 $U$ は $UU * = I$ を満たす。左辺の行列式（これは固有値の幾何平均の $N$ 乗である）とトレース（これは固有値の算術平均に比例する）をとることにより、 $U$ の固有値 $λ i$ が絶対値 $1$ であることが確認できる。すなわち、 ${\frac {1}{N}}\operatorname {Tr} {\boldsymbol {U}}{\boldsymbol {U}}^{*}={\frac {1}{N}}\sum _{j=1}^{N}{\mathopen {|}}\lambda _{j}{\mathclose {|}}^{2}=1,\quad \operatorname {det} {\boldsymbol {U}}{\boldsymbol {U}}^{*}=\prod _{j=1}^{N}{\mathopen {|}}\lambda _{j}{\mathclose {|}}^{2}=1$ となるが、算術平均と幾何平均が等しいのは平均をとったすべての値が相等しいときに限るから、すべての絶対値が $1$ とわかる。

成分が実数であるときのユニタリ行列は直交行列 ( $UU ⊤ = I$ ) となる。容易に分かることとして、任意の直交行列はギヴンス回転と呼ばれる $2 \times 2$ 回転行列とハウスホルダー鏡映たちの積に分解することができる。ベクトルに直交行列を掛けることはベクトルの長さを保つこと、およびベクトルの長さを保つ幾何学的操作全体の成す集合は回転と鏡映によって尽くされることから、このような分解があることは直観的にも不思議はない。

ハウスホルダー変換はユニタリ行列の成す群の標準的な剰余類分解との一対一の関係性を持ち、非常に効果的な仕方でユニタリ作用素をパラメタ表示するものとしてハウスホルダー変換を用いることができる^[1]。

個々のギヴンス変換と異なり、単独のハウスホルダー変換は行列の任意の列に作用することができることに注意する。そのことは、QR分解や三重対角化の計算コストの低さにも表れてくる。もちろん、このような「計算量的最適性」("computational optimality") のツケは、ハウスホルダー変換を深く効果的にパラメタ付けすることができないこととして表れてくる。ハウスホルダー変換は逐次処理計算機 (sequential machine) 上の密行列に適しており、一方でギヴンス変換は並列処理計算機 (parallel machine) や疎行列に適している。

脚注

[脚注の使い方]

出典

^ Renan Cabrera; Traci Strohecker; Herschel Rabitz (2010). “The canonical coset decomposition of unitary matrices through Householder transformations”. Journal of Mathematical Physics 51 (8). arXiv:1008.2477. Bibcode: 2010JMP....51h2101C. doi:10.1063/1.3466798.

参考文献

Householder, A. S. (1958). “Unitary Triangularization of a Nonsymmetric Matrix”. Journal of the ACM 5 (4): 339–342. doi:10.1145/320941.320947. MR 0111128.
LaBudde, C.D. (1963). “The reduction of an arbitrary real square matrix to tridiagonal form using similarity transformations”. Mathematics of Computation (American Mathematical Society) 17 (84): 433–437. doi:10.2307/2004005. JSTOR 2004005. MR0156455.
Morrison, D.D. (1960). “Remarks on the Unitary Triangularization of a Nonsymmetric Matrix”. Journal of the ACM 7 (2): 185–186. doi:10.1145/321021.321030. MR0114291.
Cipra, Barry A. (2000). The Best of the 20th Century: Editors Name Top 10 Algorithms. 33. p. 1. (Herein Householder Transformation is cited as a top 10 algorithm of this century)
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). “Section 11.3.2. Householder Method”. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8

外部リンク

Laurie, Dirk; Weisstein, Eric W. "Householder Matrix". mathworld.wolfram.com (英語).
Householder transformation - PlanetMath.（英語）

[1] Renan Cabrera; Traci Strohecker; Herschel Rabitz (2010). “The canonical coset decomposition of unitary matrices through Householder transformations”. Journal of Mathematical Physics 51 (8). arXiv:1008.2477. Bibcode: 2010JMP....51h2101C. doi:10.1063/1.3466798.

[1]