ハウスホルダー変換

ハウスホルダー変換（- へんかん、Householder transformation）は直交変換の一種であり、行列のQR分解に用いられる。鏡映変換、基本直交変換ともいう。ハウスホルダーが1958年に発表した。

定義[編集]

n 次元ユークリッド空間のノルムが等しい2つの列ベクトル x, y に対し、変換

$z \mapsto (I-\frac{2(x-y)(x-y)^\mathrm{T} }{||x-y||^2}) z$

は x を y に、y を x に移すような、ベクトルのノルムを変えない線形変換（直交変換）になっている。ただし、 I は n 次単位行列である。一般に、ベクトル u に対し行列

$H = I-\frac{2uu^\mathrm{T} }{||u||^2}$

をu に関するハウスホルダー行列といい、 $H$ で表される線形変換をハウスホルダー変換あるいは鏡映という。 $H_u$ は u に直交する超平面に関する鏡映を表す。

上の式で $uu^\mathrm{T}$ となっている部分は u が列ベクトルなのでこのままでは計算できないが、ベクトル $z$ に作用させるときには内積により $uu^\mathrm{T} z = u (u, z)$ となることに注意。行列の具体的な成分については鏡映を参照のこと。

ハウスホルダー行列 $H$ の転置行列は $H^\mathrm{T}=H^{-1}=H$ を満たすので対称行列かつ直交行列である。これらの性質から $H^2=I$ となるのでハウスホルダー変換は対合である。幾何的には鏡映を2回繰り返すと元に戻ることに対応している。

QR分解の計算にハウスホルダー変換が使われることがある。

Alston S. Householder, Unitary Triangularization of a Nonsymmetric Matrix, Journal ACM, 5 (4), 1958, 339-342. DOI:10.1145/320941.320947