4.3.1.0.3 Householder 行列による三重対角化

$$\begin{eqnarray*} A_0 &=& A, \\ A_1&=&U_0 A_0 U_0 = \left[ \begin{array}{llll... ...t \end{array} \right], \quad U_{N-3} = I - 2 u_{N-3} u_{N-3}^T \end{eqnarray*}$$

のように $N-2$ 回の Householder 変換で三重対角化する。この $1$ ステッ プ ($A_{k-1}$ から $A_k$ を作るところ)を発見的に説明しよう。面倒なので $A_{k-1}$ を単に $A$ と書き、

$$A=\left[ \begin{array}{ccc} C & \vline & \begin{array}{... ... \ast \\ b \end{array} & \vline & B \end{array} \right]$$

とブロック分けしておく。$u=u_k$ の最初の $k$ 成分を $0$ とおく、すなわ ち

$$u=u_k=\left( \begin{array}{c} 0 \\ \vdots \\ 0 \\ \ast \\... ...rray}{c} 0 \\ \vdots \\ 0 \\ \\ v \\ \\ \end{array} \right)$$

とすると

$$U=I_N-2u u^T =\left[ \begin{array}{cc} I_k & O \\ O & Q \end{array} \right], \quad Q=I_{N-k}-2v v^T$$

となるので、

$$\mbox{新}A=U A U$$

とすると対応するブロックは

$$\begin{eqnarray*} \mbox{新}C &=& C, \\ \mbox{新}B &=& Q B Q, \\ \mbox{新}b &=& Q b \end{eqnarray*}$$

目標は

$$\mbox{新}b=Q b = \left( \begin{array}{c} s\\ 0 \\ \vdots \\ 0 \end{array} \right)$$

の形にすることである。補題 を考えると $s=\pm \Vert b\Vert$ とすればよい。

$$\mbox{$s$\ の符号}= \mbox{$-b$\ の第 $1$\ 成分 $(-b_1)$\ の符号}$$

となるように選ぶと桁落ちが起こりにくい。 まとめると

$$(\heartsuit_k)\quad \left\{ \begin{array}{lcl} s &=& -\s... ... $b$}\Vert}, \\ Q &=& I_{N-k} - 2 v v^T \end{array} \right.$$

全体としては

  for $k$ := $1$ to $N-2$ do 


begin 

第 $k$ 列の第 $k+1$ 成分以降を $b$ とする。 

$(\heartsuit_k)$ により $s$, 新 $b$, $v$, $Q$ を作る。 

新 $B=Q B Q$ を計算する。 


end

色々な工夫が可能である。まとめると

$$\left\{ \begin{array}{lcl} s &=& -\sign(b_1) \times \Vert... ...T \quad\mbox{(対称なので半分の計算で OK)} \end{array} \right.$$

注: この文書の過去の版で、$\Vert w\Vert^2$ の計算式の符号を間違えて

$$\Vert w\Vert^2=2\{s^2+(b\mbox{の第一成分})\times s\}$$

のようにしていました。ごめんなさい。