5.5 对分法和反迭代法 对分法 (Bisection) 的基本思想是利用惯性定理来计算所需的部分特征值.
定义5.1 设 A A A
Inertia ( A ) = ( ν , ζ , π ) \operatorname {I n e r t i a} (A) = (\nu , \zeta , \pi) Inertia ( A ) = ( ν , ζ , π ) 其中 ν , ζ , π \nu, \zeta, \pi ν , ζ , π A A A
定理 5.11 (Sylvester 惯性定理) 设 A ∈ R n × n A \in \mathbb{R}^{n \times n} A ∈ R n × n X ∈ R n × n X \in \mathbb{R}^{n \times n} X ∈ R n × n X ⊤ A X X^{\top}AX X ⊤ A X A A A
利用LU分解可得 A − z I = L D L T A - zI = LDL^{\mathsf{T}} A − z I = L D L T L L L D D D
Inertia ( A − z I ) = Inertia ( D ) . \operatorname {I n e r t i a} (A - z I) = \operatorname {I n e r t i a} (D). Inertia ( A − z I ) = Inertia ( D ) . 由于 D D D Inertia ( D ) \operatorname{Inertia}(D) Inertia ( D )
设 α ∈ R \alpha \in \mathbb{R} α ∈ R ( A , α ) (A, \alpha) ( A , α ) α \alpha α A A A
Negcount ( A , α ) = # ( λ ( A ) < α ) . \operatorname {N e g c o u n t} (A, \alpha) = \# (\lambda (A) < \alpha). Negcount ( A , α ) = # ( λ ( A ) < α ) . 设 α 1 < α 2 \alpha_{1} < \alpha_{2} α 1 < α 2 A A A [ α 1 , α 2 ) [\alpha_{1}, \alpha_{2}) [ α 1 , α 2 )
Negcount ( A , α 2 ) − Negcount ( A , α 1 ) . \operatorname {N e g c o u n t} (A, \alpha_ {2}) - \operatorname {N e g c o u n t} (A, \alpha_ {1}). Negcount ( A , α 2 ) − Negcount ( A , α 1 ) . 如果 α 2 − α 1 < t o l \alpha_{2} - \alpha_{1} < tol α 2 − α 1 < t o l t o l ≪ 1 tol \ll 1 t o l ≪ 1 A A A [ α 1 , α 2 ) [\alpha_{1}, \alpha_{2}) [ α 1 , α 2 ) [ α 1 , α 2 ) [\alpha_{1}, \alpha_{2}) [ α 1 , α 2 ) A A A
算法5.8.对分法：计算 A A A [ a , b ) [a,b) [ a , b ) 1: Let t o l tol t o l n a = N e g c o u n t ( A , a ) n_a = \mathrm{Negcount}(A, a) n a = Negcount ( A , a ) n b = N e g c o u n t ( A , b ) n_b = \mathrm{Negcount}(A, b) n b = Negcount ( A , b ) n a = n b n_a = n_b n a = n b ( a , n a , b , n b ) (a, n_a, b, n_b) ( a , n a , b , n b ) ( l o w , n l o w , u p , n u p ) (low, n_{low}, up, n_{up}) ( l o w , n l o w , u p , n u p ) % \% % n l o w , u p , n u p n_{low}, up, n_{up} n l o w , u p , n u p ( u p − l o w ) < t o l (up - low) < tol ( u p − l o w ) < t o l n u p − n l o w n_{up} - n_{low} n u p − n l o w mid = ( low + up ) / 2 \text{mid} = (\text{low} + \text{up}) / 2 mid = ( low + up ) /2 n m i d = N e g c o u n t ( A , m i d ) n_{mid} = \mathrm{Negcount}(A, mid) n mi d = Negcount ( A , mi d ) ( n m i d > n l o w ) (n_{mid} > n_{low}) ( n mi d > n l o w )
16: put (low, n l o w n_{low} n l o w n m i d n_{mid} n mi d ( n u p > n m i d ) (n_{up} > n_{mid}) ( n u p > n mi d ) n m i d n_{mid} n mi d n u p n_{up} n u p
显然，对分法的主要运算量集中在计算 N e g c o u n t ( A , z ) \mathrm{Negcount}(A,z) Negcount ( A , z ) A A A A − z I A - zI A − z I L D L T \mathrm{LDL}^{\mathrm{T}} LDL T
A − z I = [ a 1 − z b 1 b 1 ⋱ ⋱ ⋱ ⋱ b n − 1 b n − 1 a n − z ] = [ 1 l 1 ⋱ ⋱ ⋱ l n − 1 1 ] [ d 1 ⋱ ⋱ d n ] [ 1 l 1 ⋱ ⋱ ⋱ l n − 1 1 ] ≜ L D L T . \begin{array}{l} A - z I = \left[ \begin{array}{c c c c} a _ {1} - z & b _ {1} & & \\ b _ {1} & \ddots & \ddots & \\ & \ddots & \ddots & b _ {n - 1} \\ & & b _ {n - 1} & a _ {n} - z \end{array} \right] \\ = \left[ \begin{array}{c c c c} 1 & & & \\ l _ {1} & \ddots & & \\ & \ddots & \ddots & \\ & & l _ {n - 1} & 1 \end{array} \right] \left[ \begin{array}{c c c c} d _ {1} & & & \\ & \ddots & & \\ & & \ddots & \\ & & & d _ {n} \end{array} \right] \left[ \begin{array}{c c c c} 1 & l _ {1} & & \\ & \ddots & \ddots & \\ & & \ddots & l _ {n - 1} \\ & & & 1 \end{array} \right] \triangleq L D L ^ {\mathsf {T}}. \\ \end{array} A − z I = a 1 − z b 1 b 1 ⋱ ⋱ ⋱ ⋱ b n − 1 b n − 1 a n − z = 1 l 1 ⋱ ⋱ ⋱ l n − 1 1 d 1 ⋱ ⋱ d n 1 l 1 ⋱ ⋱ ⋱ l n − 1 1 ≜ L D L T . 利用待定系数法, 可以得到下面的递推公式
d 1 = a 1 − z , d i = ( a i − z ) − b i − 1 2 d i − 1 , i = 2 , 3 , … , n . (5.8) d _ {1} = a _ {1} - z, \quad d _ {i} = \left(a _ {i} - z\right) - \frac {b _ {i - 1} ^ {2}}{d _ {i - 1}}, \quad i = 2, 3, \dots , n. \tag {5.8} d 1 = a 1 − z , d i = ( a i − z ) − d i − 1 b i − 1 2 , i = 2 , 3 , … , n . ( 5.8 ) 用上面的公式计算 d i d_{i} d i 4 n 4n 4 n
注意这里没有选主元, 但针对对称三对角矩阵, 该算法是非常稳定的, 即使当 d i d_{i} d i
定理5.12 [30]利用公式(5.5)计算所得的 d i d_{i} d i A ^ \hat{A} A ^ d ^ i \hat{d}_i d ^ i A ^ \hat{A} A ^ A A A
A ^ ( i , i ) = a i , A ^ ( i , i + 1 ) = b i ( 1 + ε i ) , \hat {A} (i, i) = a _ {i}, \quad \hat {A} (i, i + 1) = b _ {i} (1 + \varepsilon_ {i}), A ^ ( i , i ) = a i , A ^ ( i , i + 1 ) = b i ( 1 + ε i ) , 其中 ∣ ε i ∣ ≤ 2.5 ε + O ( ε 2 ) |\varepsilon_i| \leq 2.5\varepsilon + \mathcal{O}(\varepsilon^2) ∣ ε i ∣ ≤ 2.5 ε + O ( ε 2 ) ε \varepsilon ε
由于单独调用一次 Negcount 的运算量为 4 n 4n 4 n k k k O ( k n ) \mathcal{O}(kn) O ( kn )
当特征值计算出来后, 我们可以使用带位移的逆迭代来计算对应的特征向量. 通常只需迭代 1 至 2 次即可, 由于 A A A O ( n ) \mathcal{O}(n) O ( n )
当特征值紧靠在一起时，计算出来的特征向量可能会失去正交性，此时需要进行再正交化，可通过MGS的QR分解来实现.