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

$$A_0 = A,$$

$$A_1 = U_0 A_0 U_0 = \left[ \begin{array}{lllll} \ast & \ast & 0 & \c... ...\ast & \ast & \cdots & \ast \end{array} \right], \quad U_0 = I - 2 u_0 u_0^T,$$

$$A_2 = U_1 A_1 U_1 = \left[ \begin{array}{llllll} \ast & \ast & 0 & 0... ...\ast & \ast & \cdots & \ast \end{array} \right], \quad U_1 = I - 2 u_1 u_1^T,$$

$$\cdots\cdots\cdots$$

$$A_{N-2} = U_{N-3} A_{N-3} U_{N-3} = \left[ \begin{array}{ccccccccc} \ast... ... 0 & \ast & \ast \end{array} \right], \quad U_{N-3} = I - 2 u_{N-3} u_{N-3}^T$$

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

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

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

$$u=\left( \begin{array}{c} 0 \\ \vdots \\ 0 \\ \ast \\ \vdots \\... ...} 0 \\ \vdots \\ 0 \\ \\ v \\ \\ \end{array} \right), \quad v\in \R^{N-k}$$

とすると

$$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$$

となるので、

   新$$A=U A U$$

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

$$C = C,$$

$$B = Q B Q,$$

$$b = Q b$$

目標は

   新$$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 &=& -\sign(b_... ...Vert b-\mbox{新 $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 b\Ver... ... q w^T \quad\mbox{(対称なので半分の計算で OK)} \end{array} \right.$$

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

$$\Vert w\Vert^2=2\{s^2+(b$$の第1成分$$)\times s\}$$   (この式は間違っている！)

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