Sturm 列による二分法

$T$ の固有値を小さい順に $\mu_1 \le \cdots \le \mu_n$ とし、$1 \le k \le n$ を固定する。$a_0 < b_0$ が $N(a_0) \le k - 1$、$N(b_0) \ge k$ を満たすとする（たとえば Gershgorin の円板 定理 2.2［行列の固有値評価と不等式］ から $a_0 = \min_i(\alpha_i - |\beta_{i-1}| - |\beta_i|)$ とし、$b_0$ をその最大より大きくとる。$\beta_0 = \beta_n = 0$）。$j = 0, 1, \ldots$ について $c_j = (a_j + b_j)/2$ とし、$N(c_j) \ge k$ なら $(a_{j+1}, b_{j+1}) = (a_j, c_j)$、そうでなければ $(a_{j+1}, b_{j+1}) = (c_j, b_j)$ とする（各 $c_j$ で Sturm 列は定義されているとする）。このとき

1. すべての $j$ で $a_j \le \mu_k < b_j$、$b_j - a_j = (b_0 - a_0)/2^j$ であり、$|c_j - \mu_k| \le (b_0 - a_0)/2^{j+1}$。
2. 幅を $\tau > 0$ 以下にするのに要する反復は $\lceil\log_2((b_0 - a_0)/\tau)\rceil$ 回で、全体の演算量は $O(n\log_2((b_0 - a_0)/\tau))$ である。