序
$\mathbb{C}$を複素数全体のなす集合とする。
n次元ベクトル$u$について、以下の性質が成り立つものとする。
※なおベクトル,行列の複素共役をHであらわすものとする。
\begin{eqnarray}
u = \left(
\begin{array}{}
u_{1}\\
u_{2} \\
\vdots \\
u_{n}
\end{array}
\right) \in \mathbb{C^{n×1}}
\end{eqnarray}
||u||_{2}=(u_{1}+u_{2}+...+u_{n})^{1/2}=1\\
このベクトル$u$と,$n×n$単位行列$I_{n}$より次のような行列$H \in \mathbb{C^{n×n}}$を生成しよう。
この行列をハウスホルダー行列という。
H=I_{n}-2uu^{H}\\
以下に示す通り、ハウスホルダー行列はエルミート性とユニタリー性の二つの性質がある。
\begin{align}
H^{H}&=(I_{n}-2uu^{H})^{H}\\&=I_{n}-2(u^{H})^{H}u^{H}\\&=I_{n}-2uu^{H}\\
\Leftrightarrow H^{H}&=H\\
\\
H^{H}H&=(I_{n}-2uu^{H})^{H}(I_{n}-2uu^{H})\\
&=I_{n}-4uu^{H}+4u(u^{H}u)u^{H}\\
&=I_{n}\\
\end{align}
このハウスホルダー行列の応用が本記事の趣旨となる。
以後、行列$A$を次のような行列とする。
\begin{eqnarray}
A = \left(
\begin{array}{cccc}
a_{ 11 } & a_{ 12 } & \ldots & a_{1,n}\\
a_{ 21 } & a_{ 22 } & \ldots & a_{2,n}\\
\vdots & \vdots & \ddots & \vdots \\
a_{n,1} & a_{n,2} & \ldots & a_{n,n} \\
\end{array}
\right) \in \mathbb{C^{n×n}}
\end{eqnarray}
1.三重対角行列,ヘッセンベルグ行列への変換
行列$A$より以下のようなベクトル$x_{1},y_{1,}u_{1}$,と$u_{1}$からなるハウスホルダー行列$\tilde{H_{1}} $,$H_{1}$を生成しよう。
※$\tilde{H_{1}} \in \mathbb{C^{n-1×n-1}}$ , $H_{1} \in \mathbb{C^{n×n}}$
\begin{eqnarray}
x_{1} = \left(
\begin{array}{}
a_{21}\\
a_{31} \\
\vdots \\
a_{n,1}
\end{array}
\right) ,
y_{1} = \left(
\begin{array}{}
β_{1} \\
0 \\
\vdots \\
0
\end{array}
\right)
\end{eqnarray}
β_{1}=sgn(Re(a_{21})) (\sum_{j=2}^{n}|a_{j,1}|^2)^{1/2} \\
||x_{1}-y_{1}||_{2}=(|a_{21}-β_{1}|^2+...+|a_{n-1,1}|^2+|a_{n,1}|^2)^{1/2} \\
u_{1}=\frac{x_{1}-y_{1}}{||x_{1}-y_{1}||_{2}} \\
\tilde{H_{1}}=I_{n-1}-2u_{1}u^{H}_{1}\\
H_{1}=\begin{pmatrix}
I_{1} & 0 \\
0 & \tilde{H_{1}}
\end{pmatrix}
そしてこの$H_{1}$を行列$A$の両辺にかけたものを$A^{(1)}$とすると$A^{(1)}$は次のような行列になる。
\begin{align}
A^{(1)}=H_{1}AH_{1}&=
\begin{pmatrix}
I_{1} & 0 \\
0 & \tilde{H_{1}}
\end{pmatrix}
\begin{pmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{pmatrix}
\begin{pmatrix}
I_{1} & 0 \\
0 & \tilde{H_{1}}
\end{pmatrix}\\
&=\begin{pmatrix}
A_{11} & A_{12}\tilde{H_{1}} \\
\tilde{H_{1}}A_{21} & \tilde{H_{1}}A_{22}\tilde{H_{1}}
\end{pmatrix}\\
\Leftrightarrow A^{(1)}&=\begin{pmatrix}
A^{(1)}_{11} & A^{(1)}_{12} \\
A^{(1)}_{21} & A^{(1)}_{22}
\end{pmatrix}
\end{align}
\begin{eqnarray}
A^{(1)}_{11} = \left(
\begin{array}{cccc}
a_{ 11 } & a^{(1)}_{ 12 }\\
a_{ 21 } & a^{(1)}_{ 22 }\\
\end{array}
\right) ,
A^{(1)}_{12} = \left(
\begin{array}{cccc}
a^{(1)}_{ 13 } & a^{(1)}_{ 14 } & \ldots & a^{(1)}_{1,n}\\
a^{(1)}_{ 23 } & a^{(1)}_{ 24 } & \ldots & a^{(1)}_{2,n}\\
\end{array}
\right) \\
A^{(1)}_{21} = \left(
\begin{array}{cccc}
0 & a^{(1)}_{ 32 }\\
\vdots & \vdots \\
0 & a^{(1)}_{ n2 }\\
\end{array}
\right) ,
A^{(1)}_{22} = \left(
\begin{array}{cccc}
a^{(1)}_{33} & a^{(1)}_{ 34 }& \ldots & a^{(1)}_{3,n}\\
\vdots & \vdots & \ddots & \vdots \\
a^{(1)}_{n,3} & a^{(1)}_{ n,4 } & \ldots & a^{(1)}_{n,n}\\
\end{array}
\right)
\end{eqnarray}
続いて$A^{(1)}$より先ほどと同様にベクトル$x_{2},y_{2},u_{2}$と、$u_{2}$より生成したハウスホルダー行列$\tilde{H_{2}}$,$H_{2}$を$A^{(1)}$の両辺にかけよう。これを$A^{(2)}$とすれば、
\begin{eqnarray}
x_{2} = \left(
\begin{array}{}
a^{(1)}_{32} \\
a^{(1)}_{42} \\
\vdots \\
a^{(1)}_{n,2}
\end{array}
\right) ,
y_{2} = \left(
\begin{array}{}
β_{2} \\
0 \\
\vdots \\
0
\end{array}
\right)
\end{eqnarray}
β_{2}=sgn(Re(a^{(1)}_{32})) (\sum_{j=3}^{n}|a_{j,2}|^2)^{1/2} \\
||x_{2}-y_{2}||_{2}=(|a^{(1)}_{32}-β_{2}|^2+...+|a^{(1)}_{n-1,2}|^2+|a^{(1)}_{n,2}|^2)^{1/2} \\
u_{2}=\frac{x_{2}-y_{2}}{||x_{2}-y_{2}||_{2}} \\
\tilde{H_{2}}=I_{n-2}-2u_{2}u^{H}_{2}\\
H_{2}=\begin{pmatrix}
I_{2} & 0 \\
0 & \tilde{H_{2}}
\end{pmatrix}
\begin{align}
A^{(2)}=H_{2}A^{(1)}H_{2}&=
\begin{pmatrix}
I_{2} & 0 \\
0 & \tilde{H_{2}}
\end{pmatrix}
\begin{pmatrix}
A^{(1)}_{11} & A^{(1)}_{12} \\
A^{(1)}_{21} & A^{(1)}_{22}
\end{pmatrix}
\begin{pmatrix}
I_{2} & 0 \\
0 & \tilde{H_{2}}
\end{pmatrix}\\
&=\begin{pmatrix}
A^{(1)}_{11} & A^{(1)}_{12}\tilde{H_{2}} \\
\tilde{H_{2}}A^{(1)}_{21} & \tilde{H_{2}}A^{(1)}_{22}\tilde{H_{2}}
\end{pmatrix}\\
\Leftrightarrow A^{(2)}&=\begin{pmatrix}
A^{(2)}_{11} & A^{(2)}_{12} \\
A^{(2)}_{21} & A^{(2)}_{22}
\end{pmatrix}
\end{align}
\begin{eqnarray}
A^{(2)}_{11} = \left(
\begin{array}{cccc}
a_{ 11 } & a^{(1)}_{ 12 } & a^{(2)}_{13}\\
a_{ 21 } & a^{(1)}_{ 22 } & a^{(2)}_{23}\\
0 & a^{(1)}_{ 32 } & a^{(2)}_{33}\\
\end{array}
\right) ,
A^{(1)}_{12} = \left(
\begin{array}{cccc}
a^{(2)}_{ 14 } & a^{(2)}_{ 15 } & \ldots & a^{(2)}_{1,n}\\
a^{(2)}_{ 24 } & a^{(2)}_{ 25 } & \ldots & a^{(2)}_{2,n}\\
a^{(2)}_{ 34 } & a^{(2)}_{ 35 } & \ldots & a^{(2)}_{3,n}\\
\end{array}
\right) \\
A^{(2)}_{21} = \left(
\begin{array}{cccc}
0 & 0 & a^{(2)}_{ 43 }\\
\vdots & \vdots & \vdots \\
0 & 0 & a^{(2)}_{ n3 }\\
\end{array}
\right) ,
A^{(2)}_{22} = \left(
\begin{array}{cccc}
a^{(2)}_{44} & a^{(2)}_{ 45 }& \ldots & a^{(2)}_{4,n}\\
\vdots & \vdots & \ddots & \vdots \\
a^{(2)}_{n,4} & a^{(2)}_{ n,5 } & \ldots & a^{(2)}_{n,n}\\
\end{array}
\right)
\end{eqnarray}
が得られる。また、$(t=3,...,n-2)$について、同様の手順を踏まえることで、
\begin{eqnarray}
x_{t} = \left(
\begin{array}{}
a^{(t-1)}_{t+1,t} \\
\vdots \\
a^{(t-1)}_{n,t}
\end{array}
\right) ,
y_{t} = \left(
\begin{array}{}
β_{t} \\
\vdots \\
0
\end{array}
\right)
\end{eqnarray}
β_{t}=sgn(Re(a^{(t-1)}_{t+1,t})) (\sum_{j=t+1}^{n}|a_{j,t}|^2)^{1/2} \\
||x_{t}-y_{t}||_{2}=(|a^{(t-1)}_{t+1,t}-β_{t}|^2+...+|a^{(t-1)}_{n,t}|^2)^{1/2} \\
u_{t}=\frac{x_{t}-y_{t}}{||x_{t}-y_{t}||_{2}} \\
\tilde{H_{t}}=I_{n-t}-2u_{t}u^{H}_{t}\\
H_{t}=\begin{pmatrix}
I_{t} & 0 \\
0 & \tilde{H_{t}}
\end{pmatrix}
\begin{align}
A^{(t)}=H_{t}A^{(t-1)}H_{t}&=
\begin{pmatrix}
I_{t} & 0 \\
0 & \tilde{H_{t}}
\end{pmatrix}
\begin{pmatrix}
A^{(t-1)}_{11} & A^{(t-1)}_{12} \\
A^{(t-1)}_{21} & A^{(t-1)}_{22}
\end{pmatrix}
\begin{pmatrix}
I_{t} & 0 \\
0 & \tilde{H_{t}}
\end{pmatrix}\\
&=\begin{pmatrix}
A^{(t-1)}_{11} & A^{(t-1)}_{12}\tilde{H_{t}} \\
\tilde{H_{t}}A^{(t-1)}_{21} & \tilde{H_{t}}A^{(t-1)}_{22}\tilde{H_{t}}
\end{pmatrix}\\
\Leftrightarrow A^{(t)}&=\begin{pmatrix}
A^{(t)}_{11} & A^{(t)}_{12} \\
A^{(t)}_{21} & A^{(t)}_{22}
\end{pmatrix}
\end{align}
\begin{eqnarray}
A^{(t)}_{11} = \left(
\begin{array}{cccc}
a_{ 11 } & a^{(1)}_{ 12 } & a^{(2)}_{13} & \ldots & a^{(t-1)}_{1,t} & a^{(t)}_{1,t+1}\\
a^{(1)}_{ 21 } & a^{(1)}_{ 22 } & a^{(2)}_{23} & \ldots & a^{(t-1)}_{2,t} & a^{(t)}_{2,t+1}\\
0 & a^{(1)}_{ 32 } & a^{(2)}_{33}& \ldots & a^{(t-1)}_{3,t} & a^{(t)}_{3,t+1}\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & \ldots & a^{(t-1)}_{t+1,t} & a^{(t)}_{t+1,t+1}
\end{array}
\right) ,
A^{(t)}_{12} = \left(
\begin{array}{cccc}
a^{(t)}_{ 1,t+2 } & \ldots & a^{(t)}_{1,n}\\
\vdots & \ddots & \vdots \\
a^{(t)}_{ t+1,t+2 } & \ldots & a^{(t)}_{t+1,n}\\
\end{array}
\right) \\
A^{(t)}_{21} = \left(
\begin{array}{cccc}
0 & \ldots & a^{(t)}_{ t+2,t+1 }\\
\vdots & \ddots & \vdots \\
0 & \ldots & a^{(t)}_{ n,t+1 }\\
\end{array}
\right) ,
A^{(t)}_{22} = \left(
\begin{array}{cccc}
a^{(t)}_{t+2,t+2} & \ldots & a^{(t)}_{t+2,n}\\
\vdots & \ddots & \vdots \\
a^{(t)}_{n,t+2} & \ldots & a^{(t)}_{n,n}\\
\end{array}
\right)
\end{eqnarray}
が得られる。ここで$t=n-2$の場合を考えよう。すると$A^{(n-2)}$は以下のような行列となっている。
\begin{eqnarray}
A^{(n-2)} =H_{n-2}...H_{1}AH_{1}...H_{n-2}= \left(
\begin{array}{cccc}
a_{ 11 } & a^{(1)}_{ 12 } & a^{(2)}_{13} & \ldots & a^{(n-3)}_{1,n-2} & a^{(n-2)}_{1,n-1} & a^{(n-2)}_{1,n}\\
a^{(1)}_{ 21 } & a^{(1)}_{ 22 } & a^{(2)}_{23} & \ldots & a^{(n-3)}_{2,n-2} & a^{(n-2)}_{2,n-1} & a^{(n-2)}_{2,n}\\
0 & a^{(1)}_{ 32 } & a^{(2)}_{33} & \ldots & a^{(n-3)}_{3,n-2} & a^{(n-2)}_{3,n-1} & a^{(n-2)}_{3,n}\\
0 & 0 & a^{(2)}_{43} & \ldots & a^{(n-3)}_{4,n-2} & a^{(n-2)}_{4,n-1} & a^{(n-2)}_{4,n}\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & 0 & \ldots & a^{(n-3)}_{n-1,n-2} & a^{(n-2)}_{n-1,n-1} & a^{(n-2)}_{n-1,n} \\
0 & 0 & 0 & \ldots & 0 & a^{(n-2)}_{n,n-1} & a^{(n-2)}_{n,n}
\end{array}
\right)
\end{eqnarray}
この行列をヘッセンベルグ行列(上ヘッセンベルグ行列)という。
特に$A$が対称の場合、以下の行列となる。これを三重対角行列という。
\begin{eqnarray}
A^{(n-2)} = \left(
\begin{array}{cccc}
a_{ 11 } & a^{(1)}_{ 12 } & 0 & 0 & \ldots & 0 & 0 & 0\\
a^{(1)}_{ 21 } & a^{(1)}_{ 22 } & a^{(2)}_{23} & 0 & \ldots & 0 & 0 & 0\\
0 & a^{(1)}_{ 32 } & a^{(2)}_{33} & a^{(3)}_{34} & \ldots & 0 & 0 & 0\\
0 & 0 & a^{(2)}_{43} & a^{(3)}_{44} & \ldots & 0 & 0 & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & 0 & 0 & \ldots & a^{(n-3)}_{n-1,n-2} & a^{(n-2)}_{n-1,n-1} & a^{(n-2)}_{n-1,n} \\
0 & 0 & 0 & 0 & \ldots & 0 & a^{(n-2)}_{n,n-1} & a^{(n-2)}_{n,n}
\end{array}
\right)
\end{eqnarray}
三重対角行列,ヘッセンベルグ行列はともに行列$A$の固有値計算の前処理として利用される行列でもある。
2.QR分解
ハウスホルダー行列はユニタリ行列でもあるのだった。
そこで、行列$A$についてハウスホルダー行列$H_{1} \in \mathbb{C^{n×n}}$を$A$の左からかける。かけたものを$A_{1}$としよう。
||u_{1}||_{2}=(|a_{11}|^{2}+...+|a_{n,1}|^{2})^{1/2}=1\\
H_{1}=I_{n}-2u_{1}u^{H}_{1} \\
\begin{eqnarray}
A_{1} =H_{1}A = \left(
\begin{array}{cccc}
a^{(1)}_{ 11 } & a^{(1)}_{ 12 } & a^{(1)}_{13} & \ldots & a^{(1)}_{1,n}\\
0 & a^{(1)}_{ 22 } & a^{(1)}_{23} & \ldots & a^{(1)}_{2,n}\\
0 & a^{(1)}_{ 32 } & a^{(1)}_{33} & \ldots & a^{(1)}_{3,n}\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & a^{(1)}_{ n2 } & a^{(1)}_{n3} & \ldots & a^{(1)}_{n,n}\\
\end{array}
\right)
\end{eqnarray}
次に$A_{1}$の左から$\tilde{H_{2}}$をブロック行列とした行列$H_{2}$をかけよう。かけたものを$A_{2}$とする。
||u_{2}||_{2}=(|a^{(1)}_{22}|^{2}+...+|a^{(2)}_{n,2}|^{2})^{1/2}=1\\
\tilde{H_{2}}=I_{n-1}-2u_{2}u^{H}_{2} \\
H_{2}=\begin{pmatrix}
I_{1} & 0 \\
0 & \tilde{H_{2}}
\end{pmatrix}
\begin{eqnarray}
A_{2} =H_{2}A_{1} =H_{2}H_{1}A = \left(
\begin{array}{cccc}
a^{(1)}_{ 11 } & a^{(1)}_{ 12 } & a^{(1)}_{13} & \ldots & a^{(1)}_{1,n}\\
0 & a^{(2)}_{ 22 } & a^{(2)}_{23} & \ldots & a^{(2)}_{2,n}\\
0 & 0 & a^{(2)}_{33} & \ldots & a^{(2)}_{3,n}\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & a^{(2)}_{n3} & \ldots & a^{(2)}_{n,n}\\
\end{array}
\right)
\end{eqnarray}
$(t=3,...,n-1)$について、同様の手順を繰り返そう。
||u_{t}||_{2}=(|a^{(t-1)}_{t,t}|^{2}+...+|a^{(t-1)}_{n,t}|^{2})^{1/2}=1\\
\tilde{H_{t}}=I_{n-t+1}-2u_{t}u^{H}_{t} \\
H_{t}=\begin{pmatrix}
I_{t-1} & 0 \\
0 & \tilde{H_{t}}
\end{pmatrix}
\begin{eqnarray}
A_{t} =H_{t}A_{t-1} =H_{t}...H_{1}A = \left(
\begin{array}{cccc}
a^{(1)}_{ 11 } & a^{(1)}_{ 12 } & a^{(1)}_{13} & \ldots a^{(1)}_{1,t} & \ldots & a^{(1)}_{1,n}\\
0 & a^{(2)}_{ 22 } & a^{(2)}_{23} & \ldots a^{(2)}_{2,t} & \ldots & a^{(2)}_{2,n}\\
0 & 0 & a^{(3)}_{33} & \ldots a^{(3)}_{3,t} & \ldots & a^{(3)}_{3,n}\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \ldots a^{(t)}_{t,t} & \ldots & a^{(t)}_{t,n}\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \ldots a^{(t)}_{n,t} & \ldots & a^{(t)}_{n,n}\\
\end{array}
\right)
\end{eqnarray}
$t=n-1$について、$A_{n-1}$が以下のような上三角行列になっていること。
\begin{eqnarray}
A_{n-1} = \left(
\begin{array}{cccc}
a^{(1)}_{1,1} & a^{(1)}_{1,2} & \ldots & a^{(1)}_{1,n}\\
0 & a^{(2)}_{2,2} & \ldots & a^{(2)}_{2,n} \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \ldots & a^{(n-1)}_{n,n} \\
\end{array}
\right)
\end{eqnarray}
また、$H_{n-1}...H_{1}$がユニタリー行列となっていることにそれぞれ着目しよう。
そこで、$A_{n-1}=R$,$Q^{H}=H_{n-1}...H_{1}$と置くことで、
Q^{H}A=R \\
\Leftrightarrow A=QR \\
が得られる。これをQR分解という。
この$QR分解$を繰り返すことで行列$A$の固有値の数値計算を求める方法がある。
これをQR法という。
3.シューア分解
行列$A$の固有値について、次のような固有値$λ$,固有ベクトル$u_{1}$について、以下が成り立っているとしよう。
Au_{1}=λ_{1}u_{1} \\
\begin{eqnarray}
u_{1} = \left(
\begin{array}{}
u_{11}\\
u_{21} \\
\vdots \\
u_{n,1}
\end{array}
\right) \in \mathbb{C^{n×1}}
\end{eqnarray} , ||u_{1}||_{2}=1 \\
この$u_{1}$から生成したハウスホルダー行列を$H_{1}$として、$A$,$H$より行列$A^{(1)}$を次のように定めよう。
H_{1}=I_{n}-2u_{1}u^{H}_{1} \\
AH_{1}=H_{1}
\begin{pmatrix}
λ_{1} & A^{(1)}_{12} \\
0 & A^{(1)}_{22}
\end{pmatrix}\\
\Leftrightarrow A^{(1)}=H^{H}_{1}AH_{1}
=\begin{pmatrix}
λ_{1} & A^{(1)}_{12} \\
0 & A^{(1)}_{22}
\end{pmatrix}\\ \\
\begin{eqnarray}
A^{(1)}_{12} = \left(
\begin{array}{cccc}
a^{(1)}_{ 12 } & \ldots & a^{(1)}_{1,n}\\
\end{array}
\right) ,
A^{(1)}_{22} = \left(
\begin{array}{cccc}
a^{(1)}_{ 22 } & \ldots & a^{(1)}_{2,n}\\
\vdots & \ddots & \vdots \\
a^{(1)}_{n,2} & \ldots & a^{(1)}_{n,n} \\
\end{array}
\right)
\end{eqnarray}
続いて$A^{(1)}_{22}$の固有値とその固有ベクトルに対して以下が成り立っているとしよう。
A^{(1)}_{22}u_{2}=λ_{2}u_{2} \\
\begin{eqnarray}
u_{2} = \left(
\begin{array}{}
u_{22}\\
u_{32} \\
\vdots \\
u_{n,2}
\end{array}
\right) \in \mathbb{C^{n-1×1}}
\end{eqnarray} , ||u_{2}||_{2}=1 \\
この固有ベクトル$u_{2}$よりハウスホルダー行列$\tilde{H_{2}}$,$H_{2}$,そして$A^{(1)}$より行列$A^{(2)}$を次のように定める。
\tilde{H_{2}}=I_{n-1}-2u_{2}u^{H}_{2} \\
H_{2}=\begin{pmatrix}
I_{1} & 0 \\
0 & \tilde{H_{2}}
\end{pmatrix}\\
A^{(1)}H_{2}=H_{2}
\begin{pmatrix}
A^{(2)}_{11} & A^{(2)}_{12} \\
0 & A^{(2)}_{22}
\end{pmatrix}\\
\Leftrightarrow A^{(2)}=H^{H}_{2}A^{(1)}H_{2}
=\begin{pmatrix}
A^{(2)}_{11} & A^{(2)}_{12} \\
0 & A^{(2)}_{22}
\end{pmatrix}\\ \\
\begin{eqnarray}
A^{(2)}_{11} = \left(
\begin{array}{cccc}
λ_{1} & a^{(2)}_{1,2}\\
0 & λ_{2} \\
\end{array}
\right) ,
A^{(2)}_{12} = \left(
\begin{array}{cccc}
a^{(2)}_{ 13 } & \ldots & a^{(2)}_{1,n}\\
a^{(2)}_{ 23 } & \ldots & a^{(2)}_{2,n}\\
\end{array}
\right) ,
A^{(2)}_{22} = \left(
\begin{array}{cccc}
a^{(2)}_{ 33 } & \ldots & a^{(2)}_{3,n}\\
\vdots & \ddots & \vdots \\
a^{(2)}_{n,3} & \ldots & a^{(2)}_{n,n} \\
\end{array}
\right)
\end{eqnarray}
同様の手順を踏まえて、$(t=3,...,n-1)$について、
A^{(t-1)}_{22}u_{t}=λ_{t}u_{t} \\
\begin{eqnarray}
u_{t} = \left(
\begin{array}{}
u_{t,t}\\
\vdots \\
u_{n,t}
\end{array}
\right) \in \mathbb{C^{(n-t+1)×1}}
\end{eqnarray} , ||u_{t}||_{2}=1 \\
\tilde{H_{t}}=I_{n-t+1}-2u_{t}u^{H}_{t} \\
H_{t}=\begin{pmatrix}
I_{t-1} & 0 \\
0 & \tilde{H_{t}}
\end{pmatrix}\\
A^{(t-1)}H_{t}=H_{t}
\begin{pmatrix}
A^{(t)}_{11} & A^{(t)}_{12} \\
0 & A^{(t)}_{22}
\end{pmatrix}\\
\Leftrightarrow A^{(t)}=H^{H}_{t}A^{(t-1)}H_{t}
=\begin{pmatrix}
A^{(t)}_{11} & A^{(t)}_{12} \\
0 & A^{(t)}_{22}
\end{pmatrix}\\
\begin{eqnarray}
A^{(t)}_{11} = \left(
\begin{array}{cccc}
λ_{1} & a^{(t)}_{1,2} & \ldots & a^{(t)}_{1,t}\\
0 & λ_{2} & \ldots & a^{(t)}_{2,t} \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \ldots & λ_{t} \\
\end{array}
\right) ,
A^{(t)}_{12} = \left(
\begin{array}{cccc}
a^{(t)}_{ 1,t+1 } & \ldots & a^{(t)}_{1,n}\\
a^{(t)}_{ 2,t+1 } & \ldots & a^{(t)}_{2,n}\\
\vdots & \ddots & \vdots \\
a^{(t)}_{ t,t+1 } & \ldots & a^{(t)}_{t,n}\\
\end{array}
\right) ,
A^{(t)}_{22} = \left(
\begin{array}{cccc}
a^{(t)}_{ t+1,t+1 } & \ldots & a^{(t)}_{t+1,n}\\
\vdots & \ddots & \vdots \\
a^{(t)}_{n,t+1} & \ldots & a^{(t)}_{n,n} \\
\end{array}
\right)
\end{eqnarray}
が得られる。そして、$A^{(n)}$は下三角行列になる。この行列を$S$としよう。
\begin{eqnarray}
S=A^{(n)} = \left(
\begin{array}{cccc}
λ_{1} & a^{(n)}_{1,2} & \ldots & a^{(n)}_{1,n}\\
0 & λ_{2} & \ldots & a^{(n)}_{2,t} \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \ldots & λ_{n} \\
\end{array}
\right)
\end{eqnarray}
さて、ユニタリー行列の積はユニタリー行列であることから、
Q=H_{1}...H_{n} \\
とすれば、
S=H^{H}_{n}...H^{H}_{1}AH_{1}...H_{n} \\
\Leftrightarrow S=Q^{H}AQ \\
\Leftrightarrow A=QSQ^{H} \\
が得られる。これを$シューア分解(シューア標準形)$という。
固有値の数値計算法の一つ、$QR法$はこのシューア分解の性質を利用している。
appendix.正規行列と対角化
$A^{H}A=AA^{H}$を満たす行列を正規行列という。$A$が正規行列であれば対角化ができる。
$A$のシューア分解$S$について次のように定めよう。
\begin{eqnarray}
S=Q^{H}AQ =\left(
\begin{array}{cccc}
λ_{1} & α_{1,2} & \ldots & α_{1,n}\\
0 & λ_{2} & \ldots & α_{2,t} \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \ldots & λ_{n} \\
\end{array}
\right) \\
S^{H}=Q^{H}A^{H}Q= \left(
\begin{array}{cccc}
\bar{λ_{1}} & 0& \ldots & 0\\
\bar{α_{1,2} } & λ_{2} & \ldots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
\bar{α_{1,n}} & \bar{α_{2,n}} & \ldots &\bar{ λ_{n}} \\
\end{array}
\right)
\end{eqnarray}
ここで、
AA^{H}=A^{H}A \\
\Leftrightarrow SS^{H}=S^{H}S \\
となる。両辺の各成分について比較すれば、
\begin{eqnarray}
SS^{H}=S^{H}S = \left(
\begin{array}{cccc}
|λ_{1} |^{2} & 0 & \ldots & 0\\
0 & | λ_{2} |^{2} & \ldots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \ldots & |λ_{n}|^{2} \\
\end{array}
\right)\\
\Leftrightarrow S= \left(
\begin{array}{cccc}
λ_{1} & 0 & \ldots & 0\\
0 & λ_{2} & \ldots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \ldots & λ_{n}\\
\end{array}
\right)\\
\end{eqnarray}
が導かれる。
参考文献
・新井仁之「線形代数 基礎と応用」(日本評論社)
・柳井春夫,竹内啓「射影行列・一般逆行列・特異値分解<新装版>」(東京大学出版会)
・森正武,杉原正顕,室田一雄「岩波講座 応用数学 方法2 線形計算」 (岩波書店)