世帯主の変革

線型代数学において、ハウスホルダー変換（ハウスホルダー反射または基本反射とも呼ばれる）は、原点を含む平面または超平面の周りの反射を記述する線型変換である。ハウスホルダー変換は、1958年にアルストン・スコット・ハウスホルダーによって発表された論文で使用された。^[1]

一般の内積空間における類似物はハウスホルダー演算子です。

反射超平面は、その法線ベクトル、つまり超平面に直交する単位ベクトル （長さ のベクトル）によって定義できます。この超平面に関する点の反射は、線形変換です。 ${\textstyle v}$${\textstyle 1}$ ${\textstyle x}$

${\displaystyle x-2\langle x,v\rangle v=x-2v\left(v^{*}x\right),}$

ここで、 は共役転置を持つ列単位ベクトルとして与えられます。 ${\textstyle v}$ ${\textstyle v^{\textsf {*}}}$

この変換から構築された行列は、外積で次のように表すことができます。

${\displaystyle P=I-2vv^{*}}$

はハウスホルダー行列として知られ、 は単位行列です。 ${\textstyle I}$

ハウスホルダー行列には次の特性があります。

• それはエルミートです: 、${\textstyle P=P^{*}}$
• それは単一です：、${\textstyle P^{-1}=P^{*}}$
• したがってそれは帰納的である。${\textstyle P=P^{-1}}$
• ハウスホルダー行列には固有値 があります。これを確認するには、が反射器の作成に使用されたベクトルに直交している場合、に直交する独立したベクトルが存在するため、、つまりは重複度 の固有値であることに注目してください。また、 にも注目してください。したがって は重複度 の固有値です。${\textstyle \pm 1}$${\textstyle u}$${\textstyle v}$${\textstyle Pu=u}$${\textstyle 1}$${\textstyle n-1}$${\textstyle n-1}$${\textstyle v}$${\textstyle Pv=-v}$${\textstyle -1}$${\textstyle 1}$
• ハウスホルダー反射子の行列式は です。これは、行列の行列式はその固有値の積であり、この場合、そのうちの 1 つはで、残りは であるからです(前の点と同様)。${\textstyle -1}$${\textstyle -1}$${\textstyle 1}$

幾何光学では、鏡面反射はハウスホルダー行列で表現できます（鏡面反射 § ベクトル定式化を参照）。

ハウスホルダー変換は数値線形代数で広く使われており、例えば行列の主対角線の下の要素を消滅させたり、^[2] QR分解を実行したり、 QRアルゴリズムの最初のステップで使われます。また、ヘッセンベルク形式への変換にも広く使われています。対称行列やエルミート行列の場合、対称性は保たれ、三重対角化が行われます。^[3]

ハウスホルダー反射は、行列の 1 つの列を標準基底ベクトルの倍数に反射し、変換行列を計算し、それを元の行列と乗算し、その積のマイナーを再帰的に下っていくことで、QR 分解を計算するために使用できます。これを実現するには、複素ベクトルx を複素ベクトルeの複素倍数にするエルミート ユニタリ行列Qを求めます。QR 分解では、e は単位座標ベクトル、つまり k 番目の座標になります。 u * u = 2 でQ = I - uu *という形式の複素行列Q は、エルミート ユニタリであるという望ましい特性を持ちます。ここで、 * は共役転置を表します。関係するベクトルはxとe の2 つだけなので、ベクトルu はu = a x + b eという形式にする必要があります。ここで、 a と b は決定する複素係数です。 uの全体的な位相係数は重要ではないので、係数 a は正の実数に選択できます。ここで、Q x = x (1 – a ( u * x )) - e (b ( u * x )) です。ベクトルxの係数が 0 になるためには、u * xの 2 つの項が 180 度の倍数内で同じ位相を持つ必要があるため、180 度の倍数内で arg(b) = arg( e * x ) である必要があります。180 度の偶数倍と奇数倍のどちらを選択するかによって、2 つの解があります。したがって、ベクトルxの複素係数が 0 になるためには、a と b を法とする 2 つの線形方程式を解く必要があります。a と b の位相はすでに決定されています。eをk 番目の単位座標ベクトルとすると、e * e = 1、x _k = e * xとなり、| x |= sqrt( x * x ) となります。すると、a と b は、単に a =1/sqrt (| x | (| x |+ |x _k |)) および b = a | x |と表すことができます。exp(i*arg(x _k )) または =1/sqrt (| x | (| x |- |x _k${\textstyle (i,i)}$ |)) かつ b = - a | x | exp(i*arg(x _k ))です。eの乗数はどちらの解でも -b/a です。分母が | x | に比べてゼロに近くなることはないので、最初の解の方が優れています。

この手順は、BurdenとFairesによるNumerical Analysisで紹介されています。この手順では、 をわずかに変更した関数を使用します。^[4]最初のステップでは、各ステップでハウスホルダー行列を形成するために、 と を 決定する必要があります。これらは次のようになります。 ${\displaystyle \operatorname {sgn} }$${\displaystyle \operatorname {sgn} (0)=1}$${\textstyle \alpha }$${\textstyle r}$

${\displaystyle {\begin{aligned}\alpha &=-\operatorname {sgn} \left(a_{21}\right){\sqrt {\sum _{j=2}^{n}a_{j1}^{2}}};\\r&={\sqrt {{\frac {1}{2}}\left(\alpha ^{2}-a_{21}\alpha \right)}};\end{aligned}}}$

とからベクトル を構築します。 ${\textstyle \alpha }$${\textstyle r}$${\textstyle v}$

${\displaystyle v^{(1)}={\begin{bmatrix}v_{1}\\v_{2}\\\vdots \\v_{n}\end{bmatrix}},}$

ここで、、、および ${\textstyle v_{1}=0}$${\textstyle v_{2}={\frac {a_{21}-\alpha }{2r}}}$

${\displaystyle v_{k}={\frac {a_{k1}}{2r}}}$それぞれ${\displaystyle k=3,4\ldots n}$

次に計算します:

${\displaystyle {\begin{aligned}P^{1}&=I-2v^{(1)}\left(v^{(1)}\right)^{\textsf {T}}\\A^{(2)}&=P^{1}AP^{1}\end{aligned}}}$

見つけて計算したら、次のようにプロセスを繰り返します。 ${\textstyle P^{1}}$${\textstyle A^{(2)}}$${\textstyle k=2,3,\ldots ,n-2}$

${\displaystyle {\begin{aligned}\alpha &=-\operatorname {sgn} \left(a_{k+1,k}^{k}\right){\sqrt {\sum _{j=k+1}^{n}\left(a_{jk}^{k}\right)^{2}}}\\[2pt]r&={\sqrt {{\frac {1}{2}}\left(\alpha ^{2}-a_{k+1,k}^{k}\alpha \right)}}\\[2pt]v_{1}^{k}&=v_{2}^{k}=\cdots =v_{k}^{k}=0\\[2pt]v_{k+1}^{k}&={\frac {a_{k+1,k}^{k}-\alpha }{2r}}\\v_{j}^{k}&={\frac {a_{jk}^{k}}{2r}}{\text{ }}j=k+2,\ k+3,\ \ldots ,\ n\\P^{k}&=I-2v^{(k)}\left(v^{(k)}\right)^{\textsf {T}}\\A^{(k+1)}&=P^{k}A^{(k)}P^{k}\end{aligned}}} の場合$

この方法を続けると、三角対称行列が形成されます。

^{この例では、バーデンとフェアーズ[4]}によれば、与えられた行列はハウスホルダー法を用いて 相似な三角行列_{A3に変換される。}

${\displaystyle \mathbf {A} ={\begin{bmatrix}4&1&-2&2\\1&2&0&1\\-2&0&3&-2\\2&1&-2&-1\end{bmatrix}},}$

ハウスホルダー法のこれらの手順に従うと、次のようになります。

最初のハウスホルダーマトリックス:

${\displaystyle {\begin{aligned}Q_{1}&={\begin{bmatrix}1&0&0&0\\0&-{\frac {1}{3}}&{\frac {2}{3}}&-{\frac {2}{3}}\\0&{\frac {2}{3}}&{\frac {2}{3}}&{\frac {1}{3}}\\0&-{\frac {2}{3}}&{\frac {1}{3}}&{\frac {2}{3}}\end{bmatrix}},\\A_{2}=Q_{1}AQ_{1}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&1&{\frac {4}{3}}\\0&1&{\frac {5}{3}}&-{\frac {4}{3}}\\0&{\frac {4}{3}}&-{\frac {4}{3}}&-1\end{bmatrix}},\end{aligned}}}$

形成に 使用${\textstyle A_{2}}$

${\displaystyle {\begin{aligned}Q_{2}&={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&-{\frac {3}{5}}&-{\frac {4}{5}}\\0&0&-{\frac {4}{5}}&{\frac {3}{5}}\end{bmatrix}},\\A_{3}=Q_{2}A_{2}Q_{2}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&-{\frac {5}{3}}&0\\0&-{\frac {5}{3}}&-{\frac {33}{25}}&{\frac {68}{75}}\\0&0&{\frac {68}{75}}&{\frac {149}{75}}\end{bmatrix}},\end{aligned}}}$

ご覧のとおり、最終結果は元の行列に似た三角対称行列です。プロセスは 2 つのステップで終了します。

ハウスホルダー変換は、前述のように、単位法線ベクトル を持つ超平面に関する鏡映変換です。 - 行 -列のユニタリ変換はを満たします。ユニタリ行列の行列式 (幾何平均の - 乗) とトレース (算術平均に比例) を取ると、その固有値が単位係数を持つことがわかります。これは、次のように直接かつ迅速に確認できます。 ${\textstyle v}$${\textstyle N}$${\textstyle N}$ ${\textstyle U}$${\textstyle UU^{*}=I}$${\textstyle N}$${\textstyle \lambda _{i}}$

${\displaystyle {\begin{aligned}{\frac {\operatorname {Trace} \left(UU^{*}\right)}{N}}&={\frac {\sum _{j=1}^{N}\left|\lambda _{j}\right|^{2}}{N}}=1,&\operatorname {det} \left(UU^{*}\right)&=\prod _{j=1}^{N}\left|\lambda _{j}\right|^{2}=1.\end{aligned}}}$

変数が定数である場合、算術平均と幾何平均は等しいため (算術平均と幾何平均の不等式を参照)、単位係数の主張が成立します。

実数値のユニタリ行列の場合、直交行列、が得られます。任意の直交行列は、ギブンズ回転、およびハウスホルダー反射と呼ばれる 2 x 2 回転の積に分解できることは明らかです (直交行列 を参照) 。ベクトルに直交行列を乗算するとベクトルの長さが保存され、回転と反射によってベクトルの長さを不変にする一連の (実数値の) 幾何学的演算が使い尽くされるため、これは直感的に魅力的です。 ${\textstyle UU^{\textsf {T}}=I}$

ハウスホルダー変換は、群論で定義されたユニタリ行列の標準剰余類分解と一対一の関係にあることが示されており、これを使ってユニタリ演算子を非常に効率的にパラメータ化することができる。^[5]

最後に、単独のギブンズ変換とは異なり、単一のハウスホルダー変換は行列のすべての列に作用することができ、QR 分解と三角化の計算コストが最も低くなることに注意してください。この「計算の最適性」のデメリットは、もちろん、ハウスホルダー操作をそれほど深くまたは効率的に並列化できないことです。そのため、ハウスホルダーはシーケンシャル マシン上の密行列に適しており、ギブンズ変換は疎行列や並列マシンに適しています。

• ブロックリフレクター
• ギブンズローテーション
• ヤコビ回転

• LaBudde, CD (1963). 「相似変換を用いた任意の実正方行列の三角形式への縮約」.計算数学. 17 (84). アメリカ数学会: 433–437. doi :10.2307/2004005. JSTOR  2004005. MR  0156455.
•  モリソン、 DD (1960)。 「非対称行列のユニタリ三角形化に関する考察」。Journal of the ACM。7 ( 2): 185–186。doi : 10.1145 / 321021.321030。MR 0114291。S2CID 23361868  。
• Cipra, Barry A. ( 2000)。「20世紀のベスト: 編集者が選ぶトップ10アルゴリズム」。SIAM News。33 ( 4): 1。（ここではハウスホルダー変換が今世紀のトップ10アルゴリズムとして挙げられています）
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)。「セクション 11.3.2. ハウスホルダー法」。数値レシピ: 科学計算の技法(第 3 版)。ニューヨーク: Cambridge University Press。ISBN 978-0-521-88068-8. 2011年8月11日時点のオリジナルよりアーカイブ。2011年8月13日閲覧。