4.4 QR迭代法 QR迭代法的基本思想是通过不断的正交相似变换，使得 A A A
算法4.5. QR迭代法 (QRIteration) 1: Set A 1 = A A_{1} = A A 1 = A k = 1 k = 1 k = 1 [ Q k , R k ] = Q R ( A k ) % Q R [Q_k, R_k] = \mathsf{QR}(A_k) \quad \% \quad \mathsf{QR} [ Q k , R k ] = QR ( A k ) % QR A k + 1 = R k Q k A_{k + 1} = R_kQ_k A k + 1 = R k Q k k = k + 1 k = k + 1 k = k + 1
在该算法中, 我们有
A k + 1 = R k Q k = ( Q k ⊤ Q k ) R k Q k = Q k ⊤ ( Q k R k ) Q k = Q k ⊤ A k Q k . A _ {k + 1} = R _ {k} Q _ {k} = \left(Q _ {k} ^ {\top} Q _ {k}\right) R _ {k} Q _ {k} = Q _ {k} ^ {\top} \left(Q _ {k} R _ {k}\right) Q _ {k} = Q _ {k} ^ {\top} A _ {k} Q _ {k}. A k + 1 = R k Q k = ( Q k ⊤ Q k ) R k Q k = Q k ⊤ ( Q k R k ) Q k = Q k ⊤ A k Q k . 由这个递推关系可得
A k + 1 = Q k T A k Q k = Q k T Q k − 1 T A k − 1 Q k − 1 Q k = ⋯ = Q k T Q k − 1 T … Q 1 T A Q 1 … Q k − 1 Q k . A _ {k + 1} = Q _ {k} ^ {\mathsf {T}} A _ {k} Q _ {k} = Q _ {k} ^ {\mathsf {T}} Q _ {k - 1} ^ {\mathsf {T}} A _ {k - 1} Q _ {k - 1} Q _ {k} = \dots = Q _ {k} ^ {\mathsf {T}} Q _ {k - 1} ^ {\mathsf {T}} \dots Q _ {1} ^ {\mathsf {T}} A Q _ {1} \dots Q _ {k - 1} Q _ {k}. A k + 1 = Q k T A k Q k = Q k T Q k − 1 T A k − 1 Q k − 1 Q k = ⋯ = Q k T Q k − 1 T … Q 1 T A Q 1 … Q k − 1 Q k . 记 Q ~ k = Q 1 ⋯ Q k − 1 Q k = [ q ~ 1 ( k ) , q ~ 2 ( k ) , … , q ~ n ( k ) ] \tilde{Q}_k = Q_1\cdots Q_{k-1}Q_k = \left[\tilde{q}_1^{(k)}, \tilde{q}_2^{(k)}, \ldots, \tilde{q}_n^{(k)}\right] Q ~ k = Q 1 ⋯ Q k − 1 Q k = [ q ~ 1 ( k ) , q ~ 2 ( k ) , … , q ~ n ( k ) ]
A k + 1 = Q ~ k T A Q ~ k , (4.1) A _ {k + 1} = \tilde {Q} _ {k} ^ {\mathsf {T}} A \tilde {Q} _ {k}, \tag {4.1} A k + 1 = Q ~ k T A Q ~ k , ( 4.1 ) 即 A k + 1 A_{k + 1} A k + 1 A A A
4.4.1 QR迭代与幂迭代的关系 记 R ~ k = R k R k − 1 ⋯ R 1 \tilde{R}_k = R_k R_{k-1} \cdots R_1 R ~ k = R k R k − 1 ⋯ R 1
Q ~ k R ~ k = Q ~ k − 1 ( Q k R k ) R ~ k − 1 = Q ~ k − 1 ( A k ) R ~ k − 1 = Q ~ k − 1 ( Q ~ k − 1 T A Q ~ k − 1 ) R ~ k − 1 = A Q ~ k − 1 R ~ k − 1 , \tilde {Q} _ {k} \tilde {R} _ {k} = \tilde {Q} _ {k - 1} (Q _ {k} R _ {k}) \tilde {R} _ {k - 1} = \tilde {Q} _ {k - 1} (A _ {k}) \tilde {R} _ {k - 1} = \tilde {Q} _ {k - 1} (\tilde {Q} _ {k - 1} ^ {\mathsf {T}} A \tilde {Q} _ {k - 1}) \tilde {R} _ {k - 1} = A \tilde {Q} _ {k - 1} \tilde {R} _ {k - 1}, Q ~ k R ~ k = Q ~ k − 1 ( Q k R k ) R ~ k − 1 = Q ~ k − 1 ( A k ) R ~ k − 1 = Q ~ k − 1 ( Q ~ k − 1 T A Q ~ k − 1 ) R ~ k − 1 = A Q ~ k − 1 R ~ k − 1 , 由此递推下去, 即可得
Q ~ k R ~ k = A k − 1 Q ~ 1 R ~ 1 = A k − 1 Q 1 R 1 = A k . (4.2) \tilde {Q} _ {k} \tilde {R} _ {k} = A ^ {k - 1} \tilde {Q} _ {1} \tilde {R} _ {1} = A ^ {k - 1} Q _ {1} R _ {1} = A ^ {k}. \tag {4.2} Q ~ k R ~ k = A k − 1 Q ~ 1 R ~ 1 = A k − 1 Q 1 R 1 = A k . ( 4.2 ) 故
Q ~ k R ~ k e 1 = A k e 1 , \tilde {Q} _ {k} \tilde {R} _ {k} e _ {1} = A ^ {k} e _ {1}, Q ~ k R ~ k e 1 = A k e 1 , 这说明QR迭代与幂迭代有关
假设 ∣ λ 1 ∣ > ∣ λ 2 ∣ ≥ ⋯ ≥ ∣ λ n ∣ |\lambda_1| > |\lambda_2| \geq \dots \geq |\lambda_n| ∣ λ 1 ∣ > ∣ λ 2 ∣ ≥ ⋯ ≥ ∣ λ n ∣ k k k A k e 1 A^k e_1 A k e 1 A A A λ 1 \lambda_1 λ 1 Q ~ k \tilde{Q}_k Q ~ k q ~ 1 ( k ) \tilde{q}_1^{(k)} q ~ 1 ( k ) λ 1 \lambda_1 λ 1 k k k A q ~ 1 ( k ) → λ 1 q ~ 1 ( k ) A\tilde{q}_1^{(k)} \to \lambda_1\tilde{q}_1^{(k)} A q ~ 1 ( k ) → λ 1 q ~ 1 ( k ) A k + 1 A_{k+1} A k + 1
A k + 1 ( : , 1 ) = Q ~ k T A q ~ 1 ( k ) → λ 1 Q ~ k T q ~ 1 ( k ) = λ 1 e 1 , A _ {k + 1} (:, 1) = \tilde {Q} _ {k} ^ {\mathsf {T}} A \tilde {q} _ {1} ^ {(k)} \rightarrow \lambda_ {1} \tilde {Q} _ {k} ^ {\mathsf {T}} \tilde {q} _ {1} ^ {(k)} = \lambda_ {1} e _ {1}, A k + 1 ( : , 1 ) = Q ~ k T A q ~ 1 ( k ) → λ 1 Q ~ k T q ~ 1 ( k ) = λ 1 e 1 , 即 A k + 1 A_{k + 1} A k + 1 λ 1 \lambda_1 λ 1 ∣ λ 2 / λ 1 ∣ \left|\lambda_2 / \lambda_1\right| ∣ λ 2 / λ 1 ∣
4.4.2 QR迭代与反迭代的关系 下面观察 Q ~ k \tilde{Q}_k Q ~ k
A Q ~ k = Q ~ k A k + 1 = Q ~ k Q k + 1 R k + 1 = Q ~ k + 1 R k + 1 , A \tilde {Q} _ {k} = \tilde {Q} _ {k} A _ {k + 1} = \tilde {Q} _ {k} Q _ {k + 1} R _ {k + 1} = \tilde {Q} _ {k + 1} R _ {k + 1}, A Q ~ k = Q ~ k A k + 1 = Q ~ k Q k + 1 R k + 1 = Q ~ k + 1 R k + 1 , 所以有
Q ~ k + 1 = A Q ~ k R k + 1 − 1 . \tilde {Q} _ {k + 1} = A \tilde {Q} _ {k} R _ {k + 1} ^ {- 1}. Q ~ k + 1 = A Q ~ k R k + 1 − 1 . 由于 Q ~ k + 1 \tilde{Q}_{k + 1} Q ~ k + 1 Q ~ k \tilde{Q}_k Q ~ k
Q ~ k + 1 = ( Q ~ k + 1 T ) − 1 = ( ( R k + 1 − 1 ) T Q ~ k T A T ) − 1 = ( A T ) − 1 Q ~ k R k + 1 T . \tilde {Q} _ {k + 1} = \left(\tilde {Q} _ {k + 1} ^ {\mathsf {T}}\right) ^ {- 1} = \left(\left(R _ {k + 1} ^ {- 1}\right) ^ {\mathsf {T}} \tilde {Q} _ {k} ^ {\mathsf {T}} A ^ {\mathsf {T}}\right) ^ {- 1} = \left(A ^ {\mathsf {T}}\right) ^ {- 1} \tilde {Q} _ {k} R _ {k + 1} ^ {\mathsf {T}}. Q ~ k + 1 = ( Q ~ k + 1 T ) − 1 = ( ( R k + 1 − 1 ) T Q ~ k T A T ) − 1 = ( A T ) − 1 Q ~ k R k + 1 T . 观察等式两边矩阵的最后一列，可得
q ~ n ( k + 1 ) = c 1 ( A T ) − 1 q ~ n ( k ) , \tilde {q} _ {n} ^ {(k + 1)} = c _ {1} \left(A ^ {\mathsf {T}}\right) ^ {- 1} \tilde {q} _ {n} ^ {(k)}, q ~ n ( k + 1 ) = c 1 ( A T ) − 1 q ~ n ( k ) , 其中 c 1 c_{1} c 1
q ~ n ( k + 1 ) = c ( A T ) − k q ~ n ( 1 ) , \tilde {q} _ {n} ^ {(k + 1)} = c \left(A ^ {\mathsf {T}}\right) ^ {- k} \tilde {q} _ {n} ^ {(1)}, q ~ n ( k + 1 ) = c ( A T ) − k q ~ n ( 1 ) , 其中 c c c A A A ∣ λ 1 ∣ ≥ ∣ λ 2 ∣ ≥ ⋯ ≥ ∣ λ n − 1 ∣ > ∣ λ n ∣ > 0 |\lambda_1| \geq |\lambda_2| \geq \dots \geq |\lambda_{n-1}| > |\lambda_n| > 0 ∣ λ 1 ∣ ≥ ∣ λ 2 ∣ ≥ ⋯ ≥ ∣ λ n − 1 ∣ > ∣ λ n ∣ > 0 λ n − 1 \lambda_n^{-1} λ n − 1 ( A T ) − 1 \left(A^{\mathsf{T}}\right)^{-1} ( A T ) − 1 q ~ n ( k + 1 ) \tilde{q}_n^{(k+1)} q ~ n ( k + 1 ) ( A T ) − 1 \left(A^{\mathsf{T}}\right)^{-1} ( A T ) − 1 λ n − 1 \lambda_n^{-1} λ n − 1 k k k
( A T ) − 1 q ~ n ( k + 1 ) → λ n − 1 q ~ n ( k + 1 ) . \left(A ^ {\mathsf {T}}\right) ^ {- 1} \tilde {q} _ {n} ^ {(k + 1)} \rightarrow \lambda_ {n} ^ {- 1} \tilde {q} _ {n} ^ {(k + 1)}. ( A T ) − 1 q ~ n ( k + 1 ) → λ n − 1 q ~ n ( k + 1 ) . 所以
A T q ~ n ( k + 1 ) → λ n q ~ n ( k + 1 ) . A ^ {\mathsf {T}} \tilde {q} _ {n} ^ {(k + 1)} \to \lambda_ {n} \tilde {q} _ {n} ^ {(k + 1)}. A T q ~ n ( k + 1 ) → λ n q ~ n ( k + 1 ) . 由(4.1)可知， A k + 1 T A_{k + 1}^{\mathsf{T}} A k + 1 T
A k + 1 T ( : , n ) = Q ~ k T A T q ~ n ( k ) → λ n Q ~ k T q ~ n ( k ) = λ n e n , A _ {k + 1} ^ {\mathsf {T}} (:, n) = \tilde {Q} _ {k} ^ {\mathsf {T}} A ^ {\mathsf {T}} \tilde {q} _ {n} ^ {(k)} \rightarrow \lambda_ {n} \tilde {Q} _ {k} ^ {\mathsf {T}} \tilde {q} _ {n} ^ {(k)} = \lambda_ {n} e _ {n}, A k + 1 T ( : , n ) = Q ~ k T A T q ~ n ( k ) → λ n Q ~ k T q ~ n ( k ) = λ n e n , 即 A k + 1 A_{k + 1} A k + 1 λ n \lambda_{n} λ n ∣ λ n / λ n − 1 ∣ \left|\lambda_{n} / \lambda_{n - 1}\right| ∣ λ n / λ n − 1 ∣
4.4.3 QR迭代与正交迭代的关系 下面的定理给出了QR迭代法与正交迭代法(取 Z 0 = I Z_{0} = I Z 0 = I
定理4.2 设正交迭代法4.4和QR算法4.5中所涉及的QR分解都是唯一的。设 A k A_{k} A k Z k Z_{k} Z k Z 0 = I Z_{0} = I Z 0 = I
A k + 1 = Z k T A Z k . A _ {k + 1} = Z _ {k} ^ {\mathsf {T}} A Z _ {k}. A k + 1 = Z k T A Z k . (板书)
证明. 我们用归纳法证明该结论
当 k = 0 k = 0 k = 0 A 1 = A A_{1} = A A 1 = A Z 0 = I Z_{0} = I Z 0 = I
设 A k = Z k − 1 T A Z k − 1 A_{k} = Z_{k - 1}^{\mathsf{T}}AZ_{k - 1} A k = Z k − 1 T A Z k − 1 Z k − 1 Z_{k - 1} Z k − 1
Z k R ^ k = Y k = A Z k − 1 = ( Z k − 1 Z k − 1 T ) A Z k − 1 = Z k − 1 A k = ( Z k − 1 Q k ) R k , Z _ {k} \hat {R} _ {k} = Y _ {k} = A Z _ {k - 1} = (Z _ {k - 1} Z _ {k - 1} ^ {\mathsf {T}}) A Z _ {k - 1} = Z _ {k - 1} A _ {k} = (Z _ {k - 1} Q _ {k}) R _ {k}, Z k R ^ k = Y k = A Z k − 1 = ( Z k − 1 Z k − 1 T ) A Z k − 1 = Z k − 1 A k = ( Z k − 1 Q k ) R k , 即 Z k R ^ k Z_{k}\hat{R}_{k} Z k R ^ k ( Z k − 1 Q k ) R k (Z_{k - 1}Q_k)R_k ( Z k − 1 Q k ) R k Y k Y_{k} Y k Z k = Z k − 1 Q k , R ^ k = R k Z_{k} = Z_{k - 1}Q_{k},\hat{R}_{k} = R_{k} Z k = Z k − 1 Q k , R ^ k = R k
Z k ⊤ A Z k = ( Z k − 1 Q k ) ⊤ A ( Z k − 1 Q k ) = Q k ⊤ A k Q k = Q k ⊤ ( Q k R k ) Q k = R k Q k = A k + 1 , Z _ {k} ^ {\top} A Z _ {k} = \left(Z _ {k - 1} Q _ {k}\right) ^ {\top} A \left(Z _ {k - 1} Q _ {k}\right) = Q _ {k} ^ {\top} A _ {k} Q _ {k} = Q _ {k} ^ {\top} \left(Q _ {k} R _ {k}\right) Q _ {k} = R _ {k} Q _ {k} = A _ {k + 1}, Z k ⊤ A Z k = ( Z k − 1 Q k ) ⊤ A ( Z k − 1 Q k ) = Q k ⊤ A k Q k = Q k ⊤ ( Q k R k ) Q k = R k Q k = A k + 1 , 即 A k + 1 = Z k ⊤ A Z k A_{k + 1} = Z_k^\top A Z_k A k + 1 = Z k ⊤ A Z k
4.4.4 QR迭代的收敛性 定理4.3 设 A = V Λ V − 1 ∈ R n × n A = V\Lambda V^{-1} \in \mathbb{R}^{n \times n} A = V Λ V − 1 ∈ R n × n Λ = d i a g ( λ 1 , λ 2 , … , λ n ) \Lambda = \mathrm{diag}(\lambda_1, \lambda_2, \dots, \lambda_n) Λ = diag ( λ 1 , λ 2 , … , λ n ) ∣ λ 1 ∣ > ∣ λ 2 ∣ > ⋯ > ∣ λ n ∣ > 0 |\lambda_1| > |\lambda_2| > \dots > |\lambda_n| > 0 ∣ λ 1 ∣ > ∣ λ 2 ∣ > ⋯ > ∣ λ n ∣ > 0 V − 1 V^{-1} V − 1 V − 1 V^{-1} V − 1 A k A_k A k
证明. 设 V = Q v R v V = Q_{v}R_{v} V = Q v R v V V V V − 1 = L v U v V^{-1} = L_{v}U_{v} V − 1 = L v U v V − 1 V^{-1} V − 1 L v L_{v} L v
A k = V Λ k V − 1 = Q v R v Λ k L v U v = Q v R v ( Λ k L v Λ − k ) Λ k U v . A ^ {k} = V \Lambda^ {k} V ^ {- 1} = Q _ {v} R _ {v} \Lambda^ {k} L _ {v} U _ {v} = Q _ {v} R _ {v} \left(\Lambda^ {k} L _ {v} \Lambda^ {- k}\right) \Lambda^ {k} U _ {v}. A k = V Λ k V − 1 = Q v R v Λ k L v U v = Q v R v ( Λ k L v Λ − k ) Λ k U v . 注意到矩阵 Λ k L v Λ − k \Lambda^k L_v\Lambda^{-k} Λ k L v Λ − k ( i , j ) (i,j) ( i , j )
( Λ k L v Λ − k ) ( i , j ) = { 0 , i < j , 1 , i = j , L v ( i , j ) λ i k / λ j k , i > j . \left(\Lambda^ {k} L _ {v} \Lambda^ {- k}\right) (i, j) = \left\{ \begin{array}{l l} 0, & i < j, \\ 1, & i = j, \\ L _ {v} (i, j) \lambda_ {i} ^ {k} / \lambda_ {j} ^ {k}, & i > j. \end{array} \right. ( Λ k L v Λ − k ) ( i , j ) = ⎩ ⎨ ⎧ 0 , 1 , L v ( i , j ) λ i k / λ j k , i < j , i = j , i > j . 由于当 i > j i > j i > j ∣ λ i / λ j ∣ < 1 \left|\lambda_i / \lambda_j\right| < 1 ∣ λ i / λ j ∣ < 1 k k k λ i k / λ j k \lambda_i^k /\lambda_j^k λ i k / λ j k Λ k L v Λ − k \Lambda^k L_v\Lambda^{-k} Λ k L v Λ − k
Λ k L v Λ − k = I + E k , \Lambda^ {k} L _ {v} \Lambda^ {- k} = I + E _ {k}, Λ k L v Λ − k = I + E k , 其中 E k E_{k} E k lim k → ∞ E k = 0. \lim_{k\to \infty}E_k = 0. lim k → ∞ E k = 0.
A k = Q v R v ( I + E k ) Λ k U v = Q v ( I + R v E k R v − 1 ) R v Λ k U v . (4.3) A ^ {k} = Q _ {v} R _ {v} \left(I + E _ {k}\right) \Lambda^ {k} U _ {v} = Q _ {v} \left(I + R _ {v} E _ {k} R _ {v} ^ {- 1}\right) R _ {v} \Lambda^ {k} U _ {v}. \tag {4.3} A k = Q v R v ( I + E k ) Λ k U v = Q v ( I + R v E k R v − 1 ) R v Λ k U v . ( 4.3 ) 对矩阵 I + R v E k R v − 1 I + R_{v}E_{k}R_{v}^{-1} I + R v E k R v − 1 I + R v E k R v − 1 = Q E k R E k I + R_{v}E_{k}R_{v}^{-1} = Q_{E_{k}}R_{E_{k}} I + R v E k R v − 1 = Q E k R E k E k → 0 E_{k}\to 0 E k → 0 Q E k → I , Q_{E_k}\rightarrow I, Q E k → I , R E k → I . R_{E_k}\rightarrow I. R E k → I . ( \ref e q : 2 ) (\ref{eq:2}) ( \ref e q : 2 )
A k = Q v Q E k R E k R v Λ k U v = Q v Q E k D k ( D k − 1 R E k R v Λ k U v ) , (4.4) A ^ {k} = Q _ {v} Q _ {E _ {k}} R _ {E _ {k}} R _ {v} \Lambda^ {k} U _ {v} = Q _ {v} Q _ {E _ {k}} D _ {k} \left(D _ {k} ^ {- 1} R _ {E _ {k}} R _ {v} \Lambda^ {k} U _ {v}\right), \tag {4.4} A k = Q v Q E k R E k R v Λ k U v = Q v Q E k D k ( D k − 1 R E k R v Λ k U v ) , ( 4.4 ) 其中 D k D_{k} D k D k − 1 R E k R v Λ k U v D_{k}^{-1}R_{E_{k}}R_{v}\Lambda^{k}U_{v} D k − 1 R E k R v Λ k U v A k A^{k} A k A k = Q ~ k R ~ k A^{k} = \tilde{Q}_{k}\tilde{R}_{k} A k = Q ~ k R ~ k
Q ~ k = Q v Q E k D k , R ~ k = D k − 1 R E k R v Λ k U v . \tilde {Q} _ {k} = Q _ {v} Q _ {E _ {k}} D _ {k}, \qquad \tilde {R} _ {k} = D _ {k} ^ {- 1} R _ {E _ {k}} R _ {v} \Lambda^ {k} U _ {v}. Q ~ k = Q v Q E k D k , R ~ k = D k − 1 R E k R v Λ k U v . 所以由 (4.1) 可知
A k + 1 = Q ~ k T A Q ~ k = ( Q v Q E k D k ) ⊺ V Λ V − 1 Q v Q E k D k = D k ⊤ Q E k ⊤ Q v ⊤ Q v R v Λ R v − 1 Q v − 1 Q v Q E k D k = D k ⊤ Q E k ⊤ R v Λ R v − 1 Q E k D k . \begin{array}{l} A _ {k + 1} = \tilde {Q} _ {k} ^ {\mathsf {T}} A \tilde {Q} _ {k} \\ = \left(Q _ {v} Q _ {E _ {k}} D _ {k}\right) ^ {\intercal} V \Lambda V ^ {- 1} Q _ {v} Q _ {E _ {k}} D _ {k} \\ = D _ {k} ^ {\top} Q _ {E _ {k}} ^ {\top} Q _ {v} ^ {\top} Q _ {v} R _ {v} \Lambda R _ {v} ^ {- 1} Q _ {v} ^ {- 1} Q _ {v} Q _ {E _ {k}} D _ {k} \\ = D _ {k} ^ {\top} Q _ {E _ {k}} ^ {\top} R _ {v} \Lambda R _ {v} ^ {- 1} Q _ {E _ {k}} D _ {k}. \\ \end{array} A k + 1 = Q ~ k T A Q ~ k = ( Q v Q E k D k ) ⊺ V Λ V − 1 Q v Q E k D k = D k ⊤ Q E k ⊤ Q v ⊤ Q v R v Λ R v − 1 Q v − 1 Q v Q E k D k = D k ⊤ Q E k ⊤ R v Λ R v − 1 Q E k D k . 由于 Q E k → I Q_{E_k} \to I Q E k → I k → ∞ k \to \infty k → ∞ A k + 1 A_{k+1} A k + 1
max 1 ≤ i < n ∣ λ i + 1 λ i ∣ \max _ {1 \leq i < n} \left| \frac {\lambda_ {i + 1}}{\lambda_ {i}} \right| 1 ≤ i < n max λ i λ i + 1 的大小. □需要指出的是，由于 D k D_{k} D k A k + 1 A_{k + 1} A k + 1
（不含对角线）的元素不一定收敛, 但这不妨碍 A k + 1 A_{k+1} A k + 1 A A A A k + 1 A_{k+1} A k + 1
例4.3 QR迭代法演示.设
A = X [ 9 5 3 1 ] X − 1 , A = X \left[ \begin{array}{c c c c} 9 & & & \\ & 5 & & \\ & & 3 & \\ & & & 1 \end{array} \right] X ^ {- 1}, A = X 9 5 3 1 X − 1 , 其中 X X X
在迭代过程中, 对于 A k A_{k} A k tol \text{tol} tol
a i j ( k ) = 0 i f i > j a n d ∣ a i j ( k ) ∣ < t o l . a _ {i j} ^ {(k)} = 0 \quad \text {i f} \quad i > j \text {a n d} | a _ {i j} ^ {(k)} | < t o l. a ij ( k ) = 0 i f i > j a n d ∣ a ij ( k ) ∣ < t o l . 这里我们取 t o l = 10 − 6 max 1 ≤ i , j ≤ n { ∣ a i j ( k ) ∣ } . tol = 10^{-6}\max_{1\leq i,j\leq n}\{|a_{ij}^{(k)}|\} . t o l = 1 0 − 6 max 1 ≤ i , j ≤ n { ∣ a ij ( k ) ∣ } .
4.4.5 带位移的QR迭代法 为了加快 QR 迭代的收敛速度, 我们可以采用位移策略和反迭代思想.
算法4.6.带位移的QR迭代法(QRIterationwithshift)
1: Set A 1 = A A_{1} = A A 1 = A k = 1 k = 1 k = 1 σ k \sigma_{k} σ k [ Q k , R k ] = Q R ( A k − σ k I ) % Q R [Q_k, R_k] = \mathsf{QR}(A_k - \sigma_k I) \quad \% \quad \mathsf{QR} [ Q k , R k ] = QR ( A k − σ k I ) % QR A k + 1 = R k Q k + σ k I A_{k + 1} = R_kQ_k + \sigma_kI A k + 1 = R k Q k + σ k I k = k + 1 k = k + 1 k = k + 1
与不带位移的QR迭代一样，我们有
A k + 1 = R k Q k + σ k I = ( Q k T Q k ) R k Q k + σ k I = Q k T ( A k − σ k I ) Q k + σ k I = Q k T A k Q k A _ {k + 1} = R _ {k} Q _ {k} + \sigma_ {k} I = (Q _ {k} ^ {\mathsf {T}} Q _ {k}) R _ {k} Q _ {k} + \sigma_ {k} I = Q _ {k} ^ {\mathsf {T}} (A _ {k} - \sigma_ {k} I) Q _ {k} + \sigma_ {k} I = Q _ {k} ^ {\mathsf {T}} A _ {k} Q _ {k} A k + 1 = R k Q k + σ k I = ( Q k T Q k ) R k Q k + σ k I = Q k T ( A k − σ k I ) Q k + σ k I = Q k T A k Q k 所以, 带位移的 QR 算法中所得到的矩阵 A k A_{k} A k A 1 = A A_{1} = A A 1 = A
在带位移的QR迭代法中, 一个很重要的问题就是位移 σ k \sigma_{k} σ k A k + 1 ( n , n ) A_{k + 1}(n,n) A k + 1 ( n , n ) A A A σ k \sigma_{k} σ k A A A A k − σ k I A_{k} - \sigma_{k}I A k − σ k I
法迭代一步就收敛.此时
A k + 1 = R k Q k + σ k I = [ A k + 1 ( n − 1 ) × ( n − 1 ) ∗ 0 σ k ] . A _ {k + 1} = R _ {k} Q _ {k} + \sigma_ {k} I = \left[ \begin{array}{c c} A _ {k + 1} ^ {(n - 1) \times (n - 1)} & * \\ 0 & \sigma_ {k} \end{array} \right]. A k + 1 = R k Q k + σ k I = [ A k + 1 ( n − 1 ) × ( n − 1 ) 0 ∗ σ k ] . 如果需要计算 A A A A k + 1 ( n − 1 ) × ( n − 1 ) A_{k+1}^{(n-1) \times (n-1)} A k + 1 ( n − 1 ) × ( n − 1 )
通常, 如果 σ k \sigma_{k} σ k A A A A k ( n , n ) A_{k}(n,n) A k ( n , n ) A A A σ k = A k ( n , n ) \sigma_{k} = A_{k}(n,n) σ k = A k ( n , n )
例4.4带位移的QR迭代法演示.所有数据和设置与例4.3相同，在迭代过程中，取 σ k = A k ( n , n ) \sigma_{k} = A_{k}(n,n) σ k = A k ( n , n ) A k ( n , n ) A_{k}(n,n) A k ( n , n ) σ k = A k ( n − 1 , n − 1 ) \sigma_{k} = A_{k}(n - 1,n - 1) σ k = A k ( n − 1 , n − 1 )