二分法

 ハウスホルダ変換の結果として行列Aと相似な三重対角行列 A~が得られる。

  A の固有値は方程式
     det(λI - A~) = 0 --------------------------------------------[1]
  の解として与えられる。この方程式は一般的にn次の方程式で、直接解を求めるのは困
  難であるため、以下に示すような二分法を用いて解く。

  まず、
   
   g1(λ) = λ -  α1
   for k=2,3,...,n
	if gk-1(λ)=0
		gk(λ) > 0, gk+1 = λ - αk+1
	else
		gk(λ) = λ - αk - βk-12 / gk-1(λ)

   を実行し、n 個の数値
    g1(λ),g2(λ),....,gn(λ)  ------------------[2]
   を計算する。Sturm定理によれば、[2]の内の0または負であるものの個数 N(λ)が
    λより大きいA~の固有値の個数に等しい。
   またGeschgorin定理よると、行列 A~ の全ての固有値は次式で与えられる区間 (a,b)
   内に存在する。
     -a = b = Max{ |αi| + |βi| + |βi-1| } --------[3]
   従って、次のようなアルゴリズムによって、固有値を含む区間 (a,b) を狭くしてい
   き,固有値λkを求めることができる。(λkはA~の小さい方から数えたk番目の固
   有値である、つまり
    λ1(λ) < λ2(λ) < ... < λk < ... < λn(λ)  )

      a と b の初期値を [3]で決める。
      c = (a + b)/2;
      N(c)を計算する;
      for(i=0; i < R; i++ )
         if ( N(c) > n-k )
	    a = c; /* cはλkより小さい */
         else
	    b = c; /* cはλkより大きい */
      λk = c;

  ここでは、Rは繰り返す回数である。倍精度浮動小数点数の場合,上記の計算を
  R=50回繰り返せば十分に小さい誤差で固有値が求まる。