ハウスホルダー行列を表現するには、単一のベクトルの要素のみが必要であり、行列全体（ほとんどのアルゴリズムでは明示的に作成されることはない）は必要ないため、必要なストレージとメモリ参照を最小限に抑えることができます。
QR分解 ハウスホルダー変換は、 QR分解を 計算するために使用できます。列まで上三角化された正方行列を考えます。私 − 1 {\displaystyle i-1}
A （ 私 ） = [ 1 11 1 12 ⋯ 1 1 n 0 1 22 ⋯ 1 1 n ⋮ ⋱ ⋮ 0 ⋯ 0 x 1 = 1 私 私 ⋯ 1 私 n 0 ⋯ 0 ⋮ ⋮ 0 ⋯ 0 x n + 1 − 私 = 1 n 私 ⋯ 1 n n ] {\displaystyle A^{(i)}={\begin{bmatrix}a_{11}&a_{12}&\cdots &&&a_{1n}\\0&a_{22}&\cdots &&&a_{1n}\\\vdots &&\ddots &&&\vdots \\0&\cdots &0&x_{1}=a_{ii}&\cdots &a_{in}\\0&\cdots &0&\vdots &&\vdots \\0&\cdots &0&x_{n+1-i}=a_{ni}&\cdots &a_{nn}\end{bmatrix}}}
マトリックスA （ 私 ） {\displaystyle A^{(i)}}
A （ 私 ） = [ T 私 − 1 U * 0 P v ] {\displaystyle A^{(i)}={\begin{bmatrix}T_{i-1}^{U}&*\\0&P_{v}\end{bmatrix}}}
ご了承くださいA （ n ） {\displaystyle A^{(n)}} R {\displaystyle R} Q R {\displaystyle Q\,R} T 私 − 1 U {\displaystyle T_{i-1}^{U}} P v {\displaystyle P_{v}} A （ 私 ） {\displaystyle A^{(i)}}
もしx 1 = 1 私 私 {\displaystyle x_{1}=a_{ii}} 1 j 私 {\displaystyle a_{ji}} 1 j 私 = 0 {\displaystyle a_{ji}=0}
もしx 1 = 1 私 私 {\displaystyle x_{1}=a_{ii}} x 1 = r 1 e 私 ϕ 1 {\displaystyle x_{1}=r_{1}e^{i\phi _{1}}} r 1 、 ϕ 1 {\displaystyle r_{1}{\text{,}}\,\phi _{1}} U 私 私 = e − 私 ϕ 1 {\displaystyle U_{ii}=e^{-i\phi _{1}}} x 1 {\displaystyle x_{1}} ⟨ x 、 e → 1 ⟩ = ⟨ e → 1 、 x ⟩ = x 1 {\displaystyle \langle \mathbf {x} ,{\vec {e}}_{1}\rangle \,=\,\langle {\vec {e}}_{1},\mathbf {x} \rangle \,=\,x_{1}} e → 1 {\displaystyle {\vec {e}}_{1}}
させてe 1 、 e 2 、 ... 、 e n {\displaystyle \mathbf {e} _{1}{\text{,}}\,\mathbf {e} _{2}{\text{,}}\,{\text{...}}{\text{,}}\,\mathbf {e} _{n}} A （ 私 ） {\displaystyle A^{(i)}} e → 1 、 e → 2 、 ... 、 e → n − 私 + 1 {\displaystyle {\vec {e}}_{1}{\text{,}}\,{\vec {e}}_{2}{\text{,}}\,{\text{...}}{\text{,}}\,{\vec {e}}_{n-i+1}} e 私 、 e 私 + 1 、 ... 、 e n {\displaystyle \mathbf {e} _{i}{\text{,}}\,\mathbf {e} _{i+1}{\text{,}}\,{\text{...}}{\text{,}}\,\mathbf {e} _{n}}
もし私たちが見つけることができればv → {\displaystyle {\vec {v}}} P v x → = α e → 1 {\displaystyle P_{v}{\vec {x}}=\alpha {\vec {e}}_{1}} v {\displaystyle \mathbf {v} } { e 私 、 e 私 + 1 、 ... 、 e n } {\displaystyle \{\mathbf {e} _{i}{\text{,}}\,\mathbf {e} _{i+1}{\text{,}}\,{\text{...}}{\text{,}}\,\mathbf {e} _{n}\}} x {\displaystyle \mathbf {x} } x 1 {\displaystyle x_{1}} α {\displaystyle \alpha }
ある定数に対してα {\displaystyle \alpha } v → ∝ x → − α e → 1 。 {\displaystyle {\vec {v}}\propto {\vec {x}}-\alpha {\vec {e}}_{1}{\text{.}}} v → {\displaystyle {\vec {v}}}
には 2 つの可能な値があることがわかりますα {\displaystyle \alpha } ‖ x → − α e → 1 ‖ 2 {\displaystyle \|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}}
ここで、式（2 1 x → − α e → 1 = 2 ⟨ x → 、 x → − α e → 1 ‖ x → − α e → 1 ‖ 2 ⟩ x → − α e → 1 ‖ x → − α e → 1 ‖ 2 {\displaystyle {\vec {x}}-\alpha {\vec {e}}_{1}=2\left\langle {\vec {x}},{\frac {{\vec {x}}-\alpha {\vec {e}}_{1}}{\|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}}}\right\rangle {\frac {{\vec {x}}-\alpha {\vec {e}}_{1}}{\|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}}}} x → − α e → 1 {\displaystyle {\vec {x}}-\alpha {\vec {e}}_{1}} ‖ x → − α e → 1 ‖ 2 2 = 2 ⟨ x → 、 x → − α e 1 ⟩ 。 {\displaystyle \|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}^{2}=2\langle {\vec {x}},{\vec {x}}-\alpha e_{1}\rangle {\text{.}}} x 1 {\displaystyle x_{1}} ‖ x → ‖ 2 2 − 2 α x 1 + α 2 = 2 （ ‖ x → ‖ 2 2 − α x 1 ） {\displaystyle \|{\vec {x}}\|_{2}^{2}-2\alpha x_{1}+\alpha ^{2}=2(\|{\vec {x}}\|_{2}^{2}-\alpha x_{1})} α = ± ‖ x → ‖ 2 {\displaystyle \alpha =\pm \|{\vec {x}}\|_{2}} x 1 {\displaystyle x_{1}} α {\displaystyle \alpha } ‖ x → ‖ 2 2 − α x 1 * − α * x 1 + | α | 2 = 2 （ ‖ x → ‖ 2 2 − α * x 1 ） {\displaystyle \|{\vec {x}}\|_{2}^{2}-\alpha \,x_{1}^{*}-\alpha ^{*}\,x_{1}+|\alpha |^{2}\,=\,2(\|{\vec {x}}\|_{2}^{2}-\alpha ^{*}\,x_{1})} | α | 2 = ‖ x → ‖ 2 2 + （ α x 1 * − α * x 1 ） {\displaystyle |\alpha |^{2}\,=\,\|{\vec {x}}\|_{2}^{2}+(\alpha \,x_{1}^{*}-\alpha ^{*}\,x_{1})} | α | = ‖ x → ‖ 2 {\displaystyle |\alpha |=\|{\vec {x}}\|_{2}} 引数 （ α ） = 引数 （ x 1 ） {\displaystyle \arg(\alpha )\,=\,\arg(x_{1})} π {\displaystyle \pi }
これで構築は完了ですが、実際には式（2 ）で壊滅的な相殺 を避けたいものです。実際にそれを行うにはx 1 {\displaystyle x_{1}} [ 5 ] α {\displaystyle \alpha } α = − サイン （ R e （ x 1 ） ） ‖ x → ‖ 2 {\displaystyle \alpha =-\operatorname {sgn}(\mathrm {Re} (x_{1}))\|{\vec {x}}\|_{2}} x 1 {\displaystyle x_{1}} α {\displaystyle \alpha } α = − e 私 引数 （ x 1 ） ‖ x ‖ 2 {\displaystyle \alpha =-e^{i\,\arg(x_{1})}\,\|x\|_{2}} 私 {\displaystyle i} − 1 {\displaystyle -1} α {\displaystyle \alpha } x 1 {\displaystyle x_{1}} ‖ x → − α e → 1 ‖ 2 {\displaystyle \|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}} | x 1 | 〜 ‖ x ‖ 2 {\displaystyle |x_{1}|\ll \|x\|_{2}}
ハウスホルダー変換は、正方でない長方形の複素行列にも同様に適用できます。ただし、その分解方法は若干異なります。
実対称行列 この手順は、BurdenとFairesによる実対称行列の数値解析に関する著書で紹介されている。非対称行列の場合でも、同様の手順でヘッセンベルグ行列が得られるため、この手順は依然として有用である。
少し変更されたサイン {\displaystyle \operatorname {sgn} } サイン （ 0 ） = 1 {\displaystyle \operatorname {sgn} (0)=1} [ 10 ] α {\textstyle \alpha } r {\textstyle r}
α = − サイン （ 1 21 ） ∑ j = 2 n 1 j 1 2 ; r = 1 2 （ α 2 − 1 21 α ） ; {\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 } r {\textstyle r} v {\textstyle v}
v → （ 1 ） = [ v 1 v 2 ⋮ v n ] 、 {\displaystyle {\vec {v}}^{(1)}={\begin{bmatrix}v_{1}\\v_{2}\\\vdots \\v_{n}\end{bmatrix}},} どこv 1 = 0 {\textstyle v_{1}=0} v 2 = 1 21 − α 2 r {\textstyle v_{2}={\frac {a_{21}-\alpha }{2r}}}
v k = 1 k 1 2 r {\displaystyle v_{k}={\frac {a_{k1}}{2r}}} k = 3 、 4 … n {\displaystyle k=3,4\ldots n} 次に計算します。
P 1 = 私 − 2 v → （ 1 ） （ v → （ 1 ） ） T A （ 2 ） = P 1 A P 1 {\displaystyle {\begin{aligned}P^{1}&=I-2{\vec {v}}^{(1)}\left({\vec {v}}^{(1)}\right)^{\textsf {T}}\\A^{(2)}&=P^{1}AP^{1}\end{aligned}}} 以来P 1 {\displaystyle P^{1}} 対合 変換）であり、相似変換 です。P 1 {\textstyle P^{1}} A （ 2 ） {\textstyle A^{(2)}} k = 2 、 3 、 … 、 n − 2 {\textstyle k=2,3,\ldots ,n-2}
α = − サイン （ 1 k + 1 、 k k ） ∑ j = k + 1 n （ 1 j k k ） 2 r = 1 2 （ α 2 − 1 k + 1 、 k k α ） v 1 k = v 2 k = ⋯ = v k k = 0 v k + 1 k = 1 k + 1 、 k k − α 2 r v j k = 1 j k k 2 r のために j = k + 2 、 k + 3 、 … 、 n P k = 私 − 2 v → （ k ） （ v → （ k ） ） T A （ k + 1 ） = P k A （ k ） P k {\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{ for }}j=k+2,\ k+3,\ \ldots ,\ n\\P^{k}&=I-2{\vec {v}}^{(k)}\left({\vec {v}}^{(k)}\right)^{\textsf {T}}\\A^{(k+1)}&=P^{k}A^{(k)}P^{k}\end{aligned}}} この手順を続けると、三重対角かつ実対称な行列が形成される。各ハウスホルダー反射は相似 変換であるため、全体の変換も相似変換となる。
エルミート行列 ハウスホルダー変換はエルミート行列 も変換できる。A {\displaystyle A} エルミート三重対角行列に変換します。コネチカット大学の論文[ 11 ]
まず最初に
A = （ 1 11 1 → 1 * 1 → 1 A 1 ） {\displaystyle A=\left({\begin{array}{c|c}a_{11}&{\vec {a}}_{1}^{*}\\\hline {\vec {a}}_{1}&A_{1}\end{array}}\right)}
になるn × n {\displaystyle n\times n} 1 11 {\displaystyle a_{11}} 1 × 1 {\displaystyle 1\times 1} 1 → 1 {\displaystyle {\vec {a}}_{1}} （ n − 1 ） × 1 {\displaystyle (n-1)\times 1} 1 → 1 * {\displaystyle {\vec {a}}_{1}^{*}} エルミート共役で あり、1 × （ n − 1 ） {\displaystyle 1\times (n-1)} A 1 {\displaystyle A_{1}} （ n − 1 ） × （ n − 1 ） {\displaystyle (n-1)\times (n-1)} エルミート部分行列 。ハウスホルダー変換行列をP 1 {\displaystyle P_{1}}
P 1 = （ 1 0 → * 0 → H 1 ） {\displaystyle P_{1}=\left({\begin{array}{c|c}1&{\vec {0}}^{*}\\\hline {\vec {0}}&H_{1}\end{array}}\right)}
どこ0 → {\displaystyle {\vec {0}}} 1 × （ n − 1 ） {\displaystyle 1\times (n-1)} 0 → * {\displaystyle {\vec {0}}^{*}} （ n − 1 ） × 1 {\displaystyle (n-1)\times 1} H 1 = 私 − 2 v → v → * {\displaystyle H_{1}=I\,-\,2\,{\vec {v}}\,{\vec {v}}^{*}} 私 {\displaystyle I} （ n − 1 ） × （ n − 1 ） {\displaystyle (n-1)\times (n-1)} v → * {\displaystyle {\vec {v}}^{*}} 共役 またはエルミート共役の 行列転置 です。v → {\displaystyle {\vec {v}}} H 1 {\displaystyle H_{1}} はユニタリ エルミート 対合 行列である。
P 1 A P 1 * = （ 1 11 （ H 1 1 1 ） * H 1 1 1 H 1 A 1 H 1 * ） {\displaystyle P_{1}\,A\,P_{1}^{*}=\,\left({\begin{array}{c|c}a_{11}&(H_{1}\,a_{1})^{*}\\\hline H_{1}\,a_{1}&H_{1}\,A_{1}\,H_{1}^{*}\end{array}}\right)}
以来H 1 {\displaystyle H_{1}} P 1 {\displaystyle P_{1}} H 1 = H 1 * = H 1 − 1 P 1 = P 1 * = P 1 − 1 {\displaystyle {\begin{aligned}H_{1}&=H_{1}^{*}=H_{1}^{-1}\\P_{1}&=P_{1}^{*}=P_{1}^{-1}\end{aligned}}} ユニタリ 相似 行列変換である。
もし私たちが H 1 1 → 1 = α 1 e → 1 {\displaystyle H_{1}{\vec {a}}_{1}\,=\,\alpha _{1}\,{\vec {e}}_{1}}
それから P 1 A P 1 * = （ 1 11 α 1 * 0 → * α 1 1 22 （ 1 ） 1 → 2 * 0 → 1 → 2 A 2 ） {\displaystyle P_{1}\,A\,P_{1}^{*}\,=\,\left({\begin{array}{c|c|c}a_{11}&\alpha _{1}^{*}&{\vec {0}}^{*}\\\hline \alpha _{1}&a_{22}^{(1)}&{\vec {a}}_{2}^{*}\\\hline {\vec {0}}&{\vec {a}}_{2}&A_{2}\end{array}}\right)} （ n − 2 ） × （ n − 2 ） {\displaystyle (n-2)\times (n-2)} A 2 {\displaystyle A_{2}} 0 → {\displaystyle {\vec {0}}} （ n − 2 ） × 1 {\displaystyle (n-2)\times 1} 0 → * {\displaystyle {\vec {0}}^{*}} 1 × （ n − 1 ） {\displaystyle 1\times (n-1)} 1 → 2 {\displaystyle {\vec {a}}_{2}} （ n − 2 ） × 1 {\displaystyle (n-2)\times 1} 1 → 2 * {\displaystyle {\vec {a}}_{2}^{*}} 1 × （ n − 2 ） {\displaystyle 1\times (n-2)} H 私 {\displaystyle H_{i}}
このプロセスを合計で繰り返します。n − 2 {\displaystyle n-2} n > 2 {\displaystyle n>2} 例 4 × 4 {\displaystyle 4\times 4} 3 × 3 {\displaystyle 3\times 3} 1 × 1 {\displaystyle 1\times 1} 2 × 2 {\displaystyle 2\times 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{ for }}j=k+2,\ k+3,\ \ldots ,\ n\\P^{k}&=I-2{\vec {v}}^{(k)}\left({\vec {v}}^{(k)}\right)^{\textsf {T}}\\A^{(k+1)}&=P^{k}A^{(k)}P^{k}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/890694ee2badbbd40a3842402590390a8ee11c15)
