next up previous contents
Next: 5.3.0.0.2 ステップ2 Up: 5.3 QR 法の原理 Previous: 5.3 QR 法の原理

5.3.0.0.1 ステップ1
($ A^{k+1}$ の QR 分解) まず
主張1
$ P_k:= Q_0Q_1\cdots Q_{k-1}Q_k$ とおくと

(10) $\displaystyle A_k=P_{k-1}^\ast A P_{k-1}.$

実際、

    $\displaystyle A_1$ $\displaystyle =R_0 Q_0=(Q_0^\ast A)Q_0=Q_0^\ast A Q_0,$
    $\displaystyle A_2$ $\displaystyle =R_1 Q_1=(Q_1^\ast A_1)Q_1=Q_1^\ast (Q_0^\ast A Q_0)Q_1= Q_1^\ast Q_0^\ast A Q_0 Q_1,$
    $\displaystyle A_2$ $\displaystyle =R_2 Q_2=(Q_2^\ast A_2)Q_2=Q_2^\ast (Q_1^\ast Q_0^\ast A Q_0Q_1)Q_2= Q_2^\ast Q_1^\ast Q_0^\ast A Q_0 Q_1 Q_2,$
    $\displaystyle \cdots$
    $\displaystyle A_{k}$ $\displaystyle = R_k Q_k=(Q_k^\ast A_{k-1})Q_k =Q_k^\ast(Q_{k-1}^\ast\cdots Q_1^\ast Q_0^\ast A Q_0 Q_1\cdots Q_{k-1})Q_k,$
    $\displaystyle \cdots$

となる (帰納法で証明すべきかもしれないが)。
主張2
$ U_k:=R_k R_{k-1}\cdots R_1 R_0$ とおくと $ A^{k+1}=P_k U_k$ であり、 これは $ A^{k+1}$ の QR 分解である。
まず

    $\displaystyle P_k U_k$ $\displaystyle =(Q_0 Q_1\cdots Q_{k-1}Q_k)(R_k R_{k-1}\cdots R_1 R_0) =(Q_0 Q_1\cdots Q_{k-1})(Q_kR_k) (R_{k-1}\cdots R_1 R_0)$
      $\displaystyle =P_{k-1}A_k U_{k-1}$

で、主張1より $ P_{k-1}A_k=A P_{k-1}$ だから、

$\displaystyle P_k U_k=A P_{k-1} U_{k-1}.
$

この式を再帰的に用いて、

$\displaystyle P_k U_k= A P_{k-1} U_{k-1}
= A (A P_{k-1} U_{k-2})
\cdots
= A^k P_0 U_0
= A^k Q_0 R_0
= A^k A =A^{k+1}.
$

一方、$ P_k$ は unitary 行列の積であるから unitary 行列、$ U_k$ は 対角線分が正である上三角行列の積であるから対角成分が正である上三角行列で ある。ゆえに $ A^{k+1}=P_k U_k$ $ A^{k+1}$ の QR 分解である。
next up previous contents
Next: 5.3.0.0.2 ステップ2 Up: 5.3 QR 法の原理 Previous: 5.3 QR 法の原理
桂田 祐史
2015-12-22