ハウスホルダー変換

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

定義

変換として

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

行列として

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

性質

ハウスホルダー行列 テンプレート:Mvar は以下のような性質を満たす:

• テンプレート:Mvar はエルミート: $𝑷={𝑷}^{*}$ ，
• テンプレート:Mvar はユニタリ: ${𝑷}^{-1}={𝑷}^{*}$ ，
• テンプレート:Mvar はテンプレート:Ill2: ${𝑷}^2=𝑰$ 。
• ハウスホルダー行列の固有値は テンプレート:Math である。これを見るために、テンプレート:Mvar が鏡映を定めるベクトル テンプレート:Mvar に直交するならば テンプレート:Mvar であることに注意する。すなわち、テンプレート:Math は重複度 テンプレート:Math の固有値である（テンプレート:Mvar に直交する線型独立なベクトルは テンプレート:Math 本ある）。同様に、テンプレート:Mvar であり、したがって テンプレート:Math は重複度 テンプレート:Math の固有ベクトルとなる。
• ハウスホルダー鏡映の行列式は テンプレート:Math である。これは行列式が固有値の総乗に等しいことに注意すれば、前条より出る（テンプレート:Math）

応用

幾何光学

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

数値線形代数

ハウスホルダー変換はQR法の第一段階であり、QR分解を行うために、数値線形代数において広く用いられる。 同様に、対称行列のテンプレート:Ill2や非対称行列のテンプレート:Ill2にも広くもちいられる。

QR 分解

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

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

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

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

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

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

参考文献

• テンプレート:Cite journal
• テンプレート:Cite journal
• テンプレート:Cite journal
• テンプレート:Cite journal (Herein Householder Transformation is cited as a top 10 algorithm of this century)
• テンプレート:Cite book

外部リンク

• テンプレート:MathWorld
• テンプレート:PlanetMath