gijyutsu-keisan.com

4．QR法

QR法は、対称、非対称、実数、複素数を問わず行列の固有値を求める方法です。 ただし、固有ベクトルについては別の方法（例えば逆反復法など）を用いて計算する必要があります。

4．1．シュア分解

ここでは、QR法の礎となるシュア分解について説明していきます。 シュア分解は、シューア分解、シュール分解などとも呼ばれます。 着目ポイントは次の3つです。
  1. 相似変換によって固有値は不変
  2. 上三角行列Rの対角要素はRの固有値
  3. 相似変換にユニタリ行列を用いることで、行列Aは上三角化できる

（1）相似変換によって固有値は不変

相似変換\( P^{-1} A P \)によってAの固有値が不変であることは、次で証明できます。
\[ \begin{eqnarray} & \det{ ( \lambda I - P^{-1} A P ) } \quad & = \det{ ( \lambda P^{-1} I P - P^{-1} A P ) } \\ & & = \det{ ( P^{-1} ( \lambda I - A ) P ) } \\ & & = \det{ ( P^{-1} ) }\det{ ( \lambda I - A ) }\det{ ( P ) } \\ & & = \det{ ( \lambda I - A ) } \tag{4.1-1} \end{eqnarray} \] \[ ( \because \det{ ( P^{-1} ) } = 1 / \det{ ( P ) } ) \]

（2）上三角行列Rの対角要素はRの固有値

これは次のようにして証明できます。
\( R = \begin{pmatrix} & r_{11} & * & \\ & \bf{o} & R_1 & \end{pmatrix} \) でブロック化すると、
\[ \begin{eqnarray} & \det{ ( \lambda I - R ) } \quad & = \begin{vmatrix} & \lambda - r_{11} & * & \\ & \bf{ o } & \lambda I_1 - R_1 & \end{vmatrix} \\ \\ & & = ( \lambda - r_{11} ) \det{ ( \lambda I_1 -R_1 ) } \\ \\ & & = ( \lambda - r_{11} ) \begin{vmatrix} & \lambda - r_{2} & * & \\ & \bf{ o } & \lambda I_2 - R_2 & \end{vmatrix} \\ \\ & & = ( \lambda - r_{11} )( \lambda - r_{22} ) \det{ ( \lambda I_2 -R_2 ) } \\ & & = \cdots \\ & & = ( \lambda - r_{11} ) \cdots ( \lambda - r_{nn} ) \end{eqnarray} \tag{4.1-2} \]
（1）、（2）の結果から、Aを相似変換によって上三角化さえできれば、Aの固有値は上三角行列の対角要素として求まります。

（3）相似変換にユニタリ行列を用いることで、行列Aは上三角化できる

相似変換にユニタリ行列を用いることで、行列を上三角化する操作をシュア分解と呼びます。
相似変換に用いるユニタリ行列Qは次の性質を持ちます。
  • \( Q^t = Q^{-1} \)（転置行列と逆行列が一致）
  • \( Q = ( \bf{q_1} , \cdots , \bf{ q_n } ) \)で表すとき、\( \bf{ q_i^t } \bf{ q_j } = \delta_{ij} \)（\( \delta_{ij} \)はクロネッカーのデルタ）
    （\( Q \)の各列ベクトルは大きさ1で、それぞれが直交する。）
ここで、次の関係を満たすベクトル\( \bf{ u_1 } \)を定義します。
  • \( ( A -\lambda_1 I ) \bf{ u_1 } = \bf{ o } \)
  • \( \bf{ u_1^t } \bf{ u_1 } = 1 \)
  • \( \bf{ u_1 } \)の第一成分\( u_{11} > 0 \)
まず\( \bf{ u_1 } \neq \bf{ e_1 } \)のとき、\( \bf{ u_1 } \)を第一列とするユニタリ行列\( U \)（ハウスホルダー行列）が存在します（証明略）。 これを\( U_1 = ( \bf{ u_1 } , \cdots , \bf{ u_n } ) \)とするとき、AのUによる相似変換は次のようになります。
\[ \begin{eqnarray} & U_1^{-1} A U_1 & = U_1^{t} ( A \bf{ u_1 } , \cdots , A \bf{ u_n } ) \\ \\ & & = \left( \begin{array}{c} \bf{ u_1^t } \\ \vdots \\ \bf{ u_n^t } \end{array} \right) ( \lambda_1 \bf{ u_1 } , \cdots , A \bf{ u_n } ) \\ \\ & & = \begin{pmatrix} & \lambda_1 \bf{ u_1^t } \bf{ u_1 } & \bf{ u_2^t } A \bf{ u_1 } & \cdots & \\ & \vdots & \vdots & \\ & \lambda_1 \bf{ u_1^t } \bf{ u_n } & \bf{ u_2^t } A \bf{ u_n } & \cdots & \end{pmatrix} \\ \\ & & = \begin{pmatrix} & \lambda_1 & \bf{ u_2^t } A \bf{ u_1 } & \cdots & \\ & \vdots & \vdots & \\ & 0 & \bf{ u_2^t } A \bf{ u_n } & \cdots & \end{pmatrix} \\ \\ & & = \begin{pmatrix} & \lambda_1 & \bf{ * } & \\ & \bf{ o} & B_1 & \end{pmatrix} \end{eqnarray} \tag{4.1-3} \]
あるいは、\( \bf{ u_1 } = \bf{ e_1 } \)のとき、\( A \bf{ e_1 } = \lambda_1 \bf{ e_1 } \)なので、\( U_1 = I \)ととれば（4.1-3）式を満たします。 以上から、（4.1-3）式の固有多項式は次のようになります。
\[ \begin{eqnarray} & \det{ ( \lambda I - A ) } \quad & = \det{ ( \lambda I - U_1^{-1} A U_1 ) } \\ & & = ( \lambda - \lambda_1 ) \det{ ( \lambda I_1 - B_1 ) } \end{eqnarray} \tag{4.1-4} \]
\( B_1 , I_1 \)はn-1次正方行列であり、今度は\( B_1 , I_1 \)に対して先ほどと同様に\( \bf{ u_2 } \)を決め、
  • \( ( B_1 -\lambda_2 I_1 ) \bf{ u_2 } = \bf{ o } \)
  • \( \bf{ u_2^t } \bf{ u_2 } = 1 \)
  • \( \bf{ u_2 } \)の第一成分\( u_{22} > 0 \)
行列式を計算します。
\[ \begin{eqnarray} & \det{ ( \lambda I_1 - B_1 ) } \quad & = \det{ ( \lambda I_1 - U_2^{-1} B_1 U_2 ) } \\ & & = ( \lambda - \lambda_2 ) \det{ ( \lambda I_2 - B_2 ) } \end{eqnarray} \tag{4.1-5} \]
この（4.1-5）式を（4.1-4）式に代入すれば、
\[ \det{ ( \lambda I - A ) } \quad = ( \lambda - \lambda_1 )( \lambda - \lambda_2 ) \det{ ( \lambda I_2 - B_2 ) } \tag{4.1-6} \]
が得られます。
また、 \( Q_1 = U_1 , Q_2 = \begin{pmatrix} & 1 & \bf{ * } & \\ & \bf{ o } & U_2 & \end{pmatrix} \) とおけば、
\[ \begin{eqnarray} & Q_2^t Q_1^t A Q_1 Q_2 & = Q_2^t \begin{pmatrix} & \lambda_1 & * & \\ & \bf{ o } & B_1 & \end{pmatrix} Q_2 \\ \\ & & = \begin{pmatrix} & 1 & \bf{ * } & \\ & \bf{ o } & U_2^t & \end{pmatrix} \begin{pmatrix} & \lambda_1 & * & \\ & \bf{ o } & B_1 & \end{pmatrix} \begin{pmatrix} & 1 & \bf{ * } & \\ & \bf{ o } & U_2 & \end{pmatrix} \\ & & = \begin{pmatrix} & \lambda_1 & * & * & \\ & 0 & \lambda_2 & * & \\ & \bf{ o } & \bf{ o } & U_2^t B_2 U_2 & \end{pmatrix} \end{eqnarray} \tag{4.1-7} \]
となります。
このとき、ユニタリ行列の積もまたユニタリ行列になります。 従って、これをn回繰り返せば、ユニタリ行列を用いた相似変換によってAは上三角化できます。
\[ Q_n^t \cdots Q_1^t A Q_1 \cdots Q_n = \begin{pmatrix} & \lambda_1 & * & * & \\ & & \ddots & * & \\ & O & & \lambda_n & \\ \end{pmatrix} \]

参考文献

▲