ハウスホルダ―変換(Householder transform)は繰り返し繰り返すことで対称行列を三重対角行列に、また非対称行列をヘッセンベルク行列に変換する相似変換の一種。相似変換は行列の固有値を変えないので、主に行列の固有値を求める問題で利用される。

\(u\in\mathbb{R}^n\)として、このベクトルが次の条件を満たしているとする。

\[ (u,u)=1\tag{1}\]

このベクトルによって行列\(P\)を次のように構成する。

\[ P=I-2uu^\mathrm{T}\tag{2}\]

この行列は対称行列で、かつ直行行列である。このことは次のようにして示せる。

\[ P^\mathrm{T}=(I-2uu^\mathrm{T})^\mathrm{T}\\= I^\mathrm{T}-2(u^\mathrm{T})^\mathrm{T}u^\mathrm{T}= I-2uu^\mathrm{T}=P\]

\[ P^\mathrm{T}P=PP=(I-2uu^\mathrm{T})(I-2uu^\mathrm{T})\\= I-2uu^\mathrm{T}-2uu^\mathrm{T}+4u(u,u)u^\mathrm{T}\\= I-4uu^\mathrm{T}+4uu^\mathrm{T}=I\]

このような\(u\)から構成される行列を基本直交行列といって、基本直交行列\(P\)による線形変換をハウスホルダ―変換という。あるベクトル\(x,y\)について\(y=Px\)とすると

\[ y=Px=(I-2uu^\mathrm{T})x=x-2uu^\mathrm{T}x\\= x-2(u,x)u\]

と表せる。これは\(u\)を法線ベクトルとする平面で\(x\)を鏡のように折り返す変換とも見れるので鏡映変換ともいわれる。 \(P\)は直交行列なので\(x,y\)は

\[ (x,x)=(y,y)\]

を満たしている。このような\(x,y\)が与えられたとき\(u\)は次のようにして求められる。

\[ u=\frac{x-y}{2(u,x)}\\ (u,u)=\frac{(x-y,x-y)}{4(u,x)^2}=1\\ \therefore (u,x)^2=\frac{4}{(x-y,x-y)}\\ u=\pm\frac{x-y}{\sqrt{(x-y,x-y)}}\]

以上のような性質を使って行列\(P\)の積\(B=AP\)について考える。このとき、行列\(P\)を構成するベクトル\(u\)として、第\(k\)成分までが全て0であるようなものを選べば行列\(B\)の第\(k\)列までと行列\(A\)の第\(k\)列までが等しくなる。

（行列の形を書いて説明すればわかりやすいけどとりあえず省略する。）

行列\(A\)の第\(k\)列までを変化させずに\(k+1\)列の\(k+2\)行より下をゼロにするように\(u\)のゼロでない成分を選べば積の結果はヘッセンベルク行列に近づいくことがわかる。実際、このような操作を行列の次数分だけ繰り返せばヘッセンベルク行列が得られる。特別な場合として行列\(A\)が対称である場合には\(B=PAP\)を繰り返すことで三重対角行列が得られる。

以下では行列\(A\)が対称行列であるとしてそのような\(u\)を構成する方法について説明する。 行列\(A,B\)の成分を\(A=(a_{ij}),B=(b_{ij})\)と表す。また\(u=(0,\cdots,0,u_{k+1},\cdots,u_n)^\mathrm{T}\)である。

このように\(u\)を取った時点で行列\(A\)の第\(k\)列までが変化しないことはわかっているのでここからは\(A,B\)の第\(k+1\)列に注目する。上に挙げた\(x,y\)の関係式より\((x,x)=(y,y)\)なる\(x,y\)を与えれば\(u\)は決まるから、まず行列\(B\)の第\(k+1\)列を次のように定める。

\[ b_{k+1}=(b_{1j},\cdots,b_{k+1,j},0\cdots,0)^\mathrm{T}\]

ただし、\(b_{k+1}\)は行列\(P\)の第\(k+1\)列を抜き出した列ベクトルを表している。

つづく...