QR法(固有値)

同義語:QRアルゴリズムQR反復QR algorithmQR iteration

概要

QR法(固有値)(QR algorithm)とは、正方行列 $A$ から $A_0=A$ とし、$A_k$ の QR 分解 $A_k=Q_kR_k$ の因子を逆順に掛けて $A_{k+1}=R_kQ_k$ とおく反復で、$A$ にユニタリ行列で相似な行列を上三角行列に近づけ、対角成分から固有値を求める方法である。$Q_0\cdots Q_{k-1}$ の最初の列は冪乗法の、最後の列は逆反復のベクトルになる。固有値の絶対値が相異なれば、対角より下の成分は隣り合う固有値の比の冪で $0$ に近づく。実際には Hessenberg 化して 1 段の演算を減らし、Wilkinson シフト・分離・暗黙のシフトで速く収束させる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: QR分解, 固有値, Schurの三角化定理, Householder変換, 数値線形代数

QR法(固有値)(QR algorithm)とは、正方行列 $A$ から $A_0:=A$ とし、$A_k$ の QR分解 $A_k=Q_kR_k$ の因子を逆順に掛けて $A_{k+1}:=R_kQ_k$ とおく反復によって、$A$ にユニタリ行列で相似な行列の列を作り、それを上三角行列に近づけて対角成分から固有値を読み取る方法である。実際には、先に $A$ を上 Hessenberg 行列に変換し、シフトと分離を組み合わせて使う。

何を計算するか

密な $n$ 次正方行列の すべての固有値(と必要なら Schur 分解)を求める。特性多項式の係数を経由すると、係数のわずかな誤差で根が大きく動くことがあり、5 次以上では根の公式もない。QR 法はユニタリ行列による相似変換だけを繰り返すので、丸めの誤差が増幅されにくい。Arnoldi法 と Lanczos法 でも、小さな Hessenberg 行列・三重対角行列の固有値を求める段でこの方法を使う。
各段の $A_k$ は $A$ と同じ固有値をもち、$Q_0\cdots Q_{k-1}$ の最初の列は $A^ke_1$ の方向、つまり 冪乗法 のベクトルになる(数値線形代数 の定理「冪乗法の収束」)。QR 法は、冪乗法を $n$ 本のベクトルについて同時に、互いに直交させながら行うものとみなせる。この記事では、その収束を固有値の絶対値の比で述べた定理を証明し、計算を速くする Hessenberg 化・シフト・分離を、それぞれ何が成り立つから使えるのかとともに述べる。

定義と使える条件

以下、$\mathbb K$ は $\mathbb R$ または $\mathbb C$、$A\in M_n(\mathbb K)$、$\|\cdot\|$ はベクトルの 2 ノルムとそれから決まる行列のノルム、$e_j$ は標準基底のベクトルとする。正則な行列の QR 分解は、$R$ の対角成分を正にとるとただ 1 つである(QR分解 の定理「薄い QR 分解の一意性」の 2)。

QR 法

数の列 $\mu_0,\mu_1,\dots$(シフト)を選び、$A_0:=A$ から
$$ A_k-\mu_kI=Q_kR_k\quad(Q_k\text{ はユニタリ、}R_k\text{ は上三角}),\qquad A_{k+1}:=R_kQ_k+\mu_kI $$
で $A_1,A_2,\dots$ を作る。すべての $\mu_k=0$ のものを シフトなしの QR 法 という。$\widehat Q_k:=Q_0Q_1\cdots Q_{k-1}$、$\widehat R_k:=R_{k-1}\cdots R_1R_0$($\widehat Q_0=\widehat R_0=I$)とおく。

QR 法の基本性質
  1. $A_{k+1}=Q_k^*A_kQ_k$、$A_k=\widehat Q_k^*A\widehat Q_k$ である。とくに $A_k$ の固有値は重複度を込めて $A$ の固有値と等しい。
  2. $\psi_k(t):=\prod_{j=0}^{k-1}(t-\mu_j)$ とおくと $\psi_k(A)=\widehat Q_k\widehat R_k$ である。
  3. $(\widehat R_k)_{11}\widehat Q_ke_1=\psi_k(A)e_1$ である。$\psi_k(A)$ が正則なら、$\widehat Q_ke_n$ は $\psi_k(A)^{-*}e_n$($\psi_k(A)^{-*}:=(\psi_k(A)^{-1})^*$)の定数倍である。
帰納法
証明を開く

1:$R_k=Q_k^*(A_k-\mu_kI)$ なので $A_{k+1}=Q_k^*(A_k-\mu_kI)Q_k+\mu_kI=Q_k^*A_kQ_k$ である。これを繰り返すと $A_k=\widehat Q_k^*A\widehat Q_k$ である。

2:$k$ についての帰納法による。$k=0$ は明らかである。1 から $\widehat Q_kA_k=A\widehat Q_k$ なので、$\widehat Q_{k+1}\widehat R_{k+1}=\widehat Q_kQ_kR_k\widehat R_k=\widehat Q_k(A_k-\mu_kI)\widehat R_k=(A-\mu_kI)\widehat Q_k\widehat R_k=(A-\mu_kI)\psi_k(A)=\psi_{k+1}(A)$ である。

3:$\widehat R_k$ は上三角なので $\widehat R_ke_1=(\widehat R_k)_{11}e_1$ であり、2 に右から $e_1$ を掛ければよい。$\psi_k(A)$ が正則なら $\widehat R_k$ も正則で、$\psi_k(A)^{-*}=\widehat Q_k\widehat R_k^{-*}$ である。$\widehat R_k^{-*}$ は下三角なので $\widehat R_k^{-*}e_n=\overline{(\widehat R_k)_{nn}}^{\,-1}e_n$ であり、$\psi_k(A)^{-*}e_n=\overline{(\widehat R_k)_{nn}}^{\,-1}\widehat Q_ke_n$ である。$\square$

3 の前半は、$\widehat Q_k$ の最初の列が $e_1$ に $\psi_k(A)$ を掛けたもの(シフトなしなら冪乗法)であることを、後半は、最後の列が $e_n$ に $(A^*-\overline{\mu_j}I)^{-1}$ を次々に掛けたもの(逆反復)であることを言う。シフトを固有値に近く選ぶと、後半の逆反復が速く収束する。これがシフトの働きである。
使える条件。

  • (i) シフトなしの収束には、固有値の絶対値が相異なることが要る(thm-qra-conv)。絶対値の等しい固有値があると、その部分は三角にならないことがある(反例の表)。
  • (ii) 実行列を実数の計算で扱うと、共役な複素固有値の組は三角にならず、$2\times2$ の塊として残る(ex-qra-real)。
  • (iii) 1 段に QR 分解を 1 回使うので、密な行列のままでは 1 段に $n^3$ の程度の演算が要る。先に Hessenberg 化する(prop-qra-hessenberg)。

公式の表

公式使える条件根拠
$A_{k+1}=Q_k^*A_kQ_k$、$A_k=\widehat Q_k^*A\widehat Q_k$なしprop-qra-basic
$\prod_{j< k}(A-\mu_jI)=\widehat Q_k\widehat R_k$なしprop-qra-basic
$\Vert A_k-D_k^*TD_k\Vert\le C\rho^k$、$\rho=\max_i\lvert\lambda_{i+1}/\lambda_i\rvert$シフトなし、$\lvert\lambda_1\rvert>\dots>\lvert\lambda_n\rvert>0$、$X^{-1}$ が LU 分解をもつthm-qra-conv
$A_k$ が上 Hessenberg なら $A_{k+1}$ も。Hermite な三重対角も保たれるGivens 回転で分解するprop-qra-hessenberg
$\mu$ が固有値なら $h'_{n,n-1}=0$、$h'_{nn}=\mu$非簡約な上 Hessenberg 行列prop-qra-deflate
$\lvert\varepsilon'\rvert=\dfrac{\lvert b\rvert\varepsilon^2}{(a-c)^2+\varepsilon^2}$$2\times2$ の実行列、シフト $\mu=c$prop-qra-2x2
1 段の演算は $n^2$ の程度(三重対角なら $n$ の程度)Hessenberg 化してあるprop-qra-hessenberg

主定理と証明

シフトなしの QR 法の収束

シフトなしの QR 法の収束

$A\in M_n(\mathbb C)$ の固有値が $\lvert\lambda_1\rvert>\lvert\lambda_2\rvert>\dots>\lvert\lambda_n\rvert>0$ を満たすとし、$\Lambda:=\operatorname{diag}(\lambda_1,\dots,\lambda_n)$、$A=X\Lambda X^{-1}$ とする。$X^{-1}=LU$($L$ は対角成分が $1$ の下三角行列、$U$ は上三角行列)と LU 分解できると仮定する。$X=Q_XR_X$ を QR 分解とし、$T:=R_X\Lambda R_X^{-1}$ とおく。$T$ は対角成分が $\lambda_1,\dots,\lambda_n$ の上三角行列である。
$R_k$ の対角成分を正にとったシフトなしの QR 法の $A_k$ について、$\rho:=\max_{1\le i< n}\lvert\lambda_{i+1}/\lambda_i\rvert< 1$ とおくと、定数 $C$ と対角ユニタリ行列 $D_k$ があって、すべての $k$ で
$$ \|A_k-D_k^*TD_k\|\le C\rho^k $$
である。とくに $A_k$ の対角より下の成分は $C\rho^k$ 以下で $0$ に近づき、$(A_k)_{ii}\to\lambda_i$ である。

$A^k$ の 2 通りの QR 分解を比べる

準備。 $A$ は正則なので $A_k$ も正則で、$R_k$ の対角成分を正にとれば $\widehat R_k$ の対角成分も正である。prop-qra-basic の 2 により $A^k=\widehat Q_k\widehat R_k$ である。また、上三角なユニタリ行列 $W$ は対角行列である($W^{-1}=W^*$ が上三角かつ下三角)。
手順 1(固有値の比を取り出す)。 $A^k=X\Lambda^kLU=X(\Lambda^kL\Lambda^{-k})\Lambda^kU$ である。$E_k:=\Lambda^kL\Lambda^{-k}-I$ の $(i,j)$ 成分は、$i>j$ で $l_{ij}(\lambda_i/\lambda_j)^k$、それ以外で $0$ であり、$\lvert\lambda_i/\lambda_j\rvert\le\rho$ だから $\|E_k\|\le c_1\rho^k$($c_1:=n\max_{i,j}\lvert l_{ij}\rvert$)である。$F_k:=R_XE_kR_X^{-1}$ とおくと
$$ A^k=Q_X(I+F_k)R_X\Lambda^kU,\qquad\|F_k\|\le c_2\rho^k $$
である($c_2:=c_1\|R_X\|\|R_X^{-1}\|$)。
手順 2(単位行列の近くの QR 分解)。 $I+F_k=\widetilde Q_k\widetilde R_k$ を $\widetilde R_k$ の対角成分が正の QR 分解とする。$\|F_k\|\to0$ のとき $\|\widetilde Q_k-I\|\le c_3\|F_k\|$($k$ が十分大きいとき)を示す。$\widetilde R_k^*\widetilde R_k=(I+F_k)^*(I+F_k)=I+G_k$、$G_k:=F_k+F_k^*+F_k^*F_k$ であり、$\widetilde R_k^*$ は正定値行列 $I+G_k$ の Cholesky 分解の因子である(Cholesky分解 の定理「Cholesky 分解の存在と一意性」)。その成分は、同記事の定義「Cholesky の漸化式」により、$I+G_k$ の成分から四則と、正の数の平方根で順に作られる。$G=0$ では因子は $I$ で、途中の平方根の中身はすべて $1$ なので、これらは $G=0$ の近くで連続微分可能な関数であり、定数 $c_4$ があって $\|G\|$ が十分小さければ $\|\widetilde R-I\|\le c_4\|G\|$ である。$\|G_k\|\le3\|F_k\|$($\|F_k\|\le1$ のとき)なので $\|\widetilde R_k-I\|\le3c_4\|F_k\|$ で、$\|\widetilde R_k^{-1}\|\le2$ としてよい。よって
$$ \|\widetilde Q_k-I\|=\|(I+F_k-\widetilde R_k)\widetilde R_k^{-1}\|\le2(1+3c_4)\|F_k\| $$
である。
手順 3(比べる)。 手順 1・2 から $A^k=(Q_X\widetilde Q_k)(\widetilde R_kR_X\Lambda^kU)$ で、右の因子は正則な上三角行列である。$W_k:=(Q_X\widetilde Q_k)^*\widehat Q_k=\widetilde R_kR_X\Lambda^kU\widehat R_k^{-1}$ はユニタリかつ上三角なので対角行列であり、$D_k:=W_k$ とおけば $\widehat Q_k=Q_X\widetilde Q_kD_k$ である。$Q_X^*AQ_X=Q_X^*X\Lambda X^{-1}Q_X=R_X\Lambda R_X^{-1}=T$ なので、prop-qra-basic の 1 から
$$ A_k=\widehat Q_k^*A\widehat Q_k=D_k^*\widetilde Q_k^*T\widetilde Q_kD_k $$
である。$\widetilde Q_k^*T\widetilde Q_k-T=(\widetilde Q_k-I)^*T\widetilde Q_k+T(\widetilde Q_k-I)$ のノルムは $2\|T\|\|\widetilde Q_k-I\|\le2\|T\|c_3c_2\rho^k$ 以下である。$D_k$ はユニタリなので、十分大きい $k$ で $\|A_k-D_k^*TD_k\|\le2c_2c_3\|T\|\rho^k$ である。残りの有限個の $k$ では $\|A_k-D_k^*TD_k\|\le\|A\|+\|T\|$ なので、$C$ を大きくとり直せばよい。$D_k^*TD_k$ は対角より下が $0$ で対角成分が $\lambda_i$ なので、最後の主張が従う。$\square$

上の証明は、$A^k$ の QR 分解を、$X^{-1}$ の LU 分解と比べることで書き下ろしたものである。$\widehat Q_k$ の最初の $j$ 列の張る空間は $A^k\operatorname{span}\{e_1,\dots,e_j\}$ であり(prop-qra-basic の 2)、QR 法は全空間の旗に対する部分空間反復でもある。部分空間反復が Schur ベクトルの張る空間に収束することは Saa11 Theorem 5.1(pp. 116–117)にある。収束の速さは隣り合う固有値の絶対値の比で決まるので、比が $1$ に近いと遅い。これをシフトで改める。

Hessenberg 形の保存

$A$ はユニタリ行列による相似変換で上 Hessenberg 行列($i>j+1$ で $(i,j)$ 成分が $0$)にでき、$A$ が Hermite 行列なら三重対角行列にできる(Householder変換 の定理「Hessenberg 化と三重対角化」)。上 Hessenberg 行列 $H$ の QR 分解は、第 $(i,i+1)$ 行の Givens回転 $G_i$ を $i=1,\dots,n-1$ の順に左から掛けて $R=G_{n-1}\cdots G_1(H-\mu I)$ を作れば得られ、$Q:=G_1^*\cdots G_{n-1}^*$ は上 Hessenberg 行列である(Arnoldi法 の「Givens 回転によるシフト付き QR の 1 段」と同じ操作)。

Hessenberg 形の保存

$A_k$ が上 Hessenberg 行列で、QR 分解を上の Givens 回転で作るとき、$A_{k+1}$ も上 Hessenberg 行列である。$A_k$ が Hermite な三重対角行列で $\mu_k$ が実数なら、$A_{k+1}$ も Hermite な三重対角行列である。1 段の演算は、上 Hessenberg 行列では $n^2$ の程度、三重対角行列では $n$ の程度である。

積の零の位置
証明を開く

$(R_kQ_k)_{il}=\sum_r(R_k)_{ir}(Q_k)_{rl}$ で、$(R_k)_{ir}\ne0$ には $i\le r$、$(Q_k)_{rl}\ne0$ には $r\le l+1$ が要るので、$i>l+1$ なら $0$ である。$\mu_kI$ を足しても変わらない。Hermite の場合は、prop-qra-basic の 1 から $A_{k+1}=Q_k^*A_kQ_k$ も Hermite で、Hermite な上 Hessenberg 行列は三重対角である。演算の数え方は QR分解 の注意「QR 法」と同じで、回転 $n-1$ 個をそれぞれ $2$ 行・$2$ 列に当てる。三重対角なら各回転が触れる非零成分は定数個である。$\square$

シフトと分離

$A_k$ が上 Hessenberg 行列で副対角成分 $(A_k)_{j+1,j}$ が $0$ になれば、$A_k$ はブロック上三角になり、固有値の問題は左上の $j$ 次と右下の $n-j$ 次の 2 つに分かれる(分離)。実際には $\lvert(A_k)_{j+1,j}\rvert$ が丸めの程度に小さくなったら $0$ とみなす。とくに右下で $(A_k)_{n,n-1}\approx0$ なら $(A_k)_{nn}$ が固有値で、残りは $n-1$ 次の問題になる。

厳密なシフトによる分離

$H$ を非簡約な(副対角成分がすべて $0$ でない)$n$ 次の上 Hessenberg 行列とし、$\mu$ を $H$ の固有値とする。Givens 回転によるシフト付き QR の 1 段 $H'=RQ+\mu I$ では、$R$ の第 $n$ 行が $0$ であり、$h'_{n,n-1}=0$、$h'_{nn}=\mu$ である。

階数を数える

$H-\mu I$ の最初の $n-1$ 列は、第 $2$ 行から第 $n$ 行の部分が対角成分 $h_{21},\dots,h_{n,n-1}\ne0$ の上三角行列なので 1 次独立である。$R=G(H-\mu I)$($G$ はユニタリ)の最初の $n-1$ 列も 1 次独立で、上三角行列の最初の $n-1$ 列が 1 次独立であることは $r_{11},\dots,r_{n-1,n-1}\ne0$ と同値である。$H-\mu I$ は正則でないので $\det R=r_{11}\cdots r_{nn}=0$ から $r_{nn}=0$ であり、$R$ の第 $n$ 行は $0$ である。よって $RQ$ の第 $n$ 行も $0$ で、$H'$ の第 $n$ 行は $\mu e_n^{\mathsf T}$ である。$\square$

固有値は分からないので、近い値をシフトにする。最も簡単なのは Rayleigh シフト $\mu_k:=(A_k)_{nn}$ で、prop-qra-basic の 3 から $\widehat Q_ke_n$ が逆反復のベクトルであることに対応する。$2\times2$ の場合に収束の速さを正確に計算できる。

$2\times2$ の行列の Rayleigh シフト

$a,b,c,\varepsilon$ を実数、$\varepsilon\ne0$、$H=\begin{pmatrix}a&b\\\varepsilon&c\end{pmatrix}$ とし、シフト $\mu=c$ で Givens 回転によるシフト付き QR の 1 段を行う。新しい副対角成分 $\varepsilon'$ は
$$ \varepsilon'=-\frac{b\,\varepsilon^2}{(a-c)^2+\varepsilon^2} $$
である。とくに $H$ が対称($b=\varepsilon$)なら $\lvert\varepsilon'\rvert=\lvert\varepsilon\rvert^3/((a-c)^2+\varepsilon^2)$ である。

1 回の回転

$r:=\sqrt{(a-c)^2+\varepsilon^2}$、$\gamma:=(a-c)/r$、$\sigma:=\varepsilon/r$、$G:=\begin{pmatrix}\gamma&\sigma\\-\sigma&\gamma\end{pmatrix}$ とおくと
$$ R=G(H-cI)=\begin{pmatrix}r&\gamma b\\0&-\sigma b\end{pmatrix},\qquad Q=G^{\mathsf T}=\begin{pmatrix}\gamma&-\sigma\\\sigma&\gamma\end{pmatrix} $$
であり、$RQ$ の $(2,1)$ 成分は $0\cdot\gamma+(-\sigma b)\sigma=-\sigma^2b=-b\varepsilon^2/r^2$ である。$cI$ を足しても変わらない。$\square$

$a-c$ が $0$ から離れていれば、副対角成分は 1 段で $2$ 乗(対称なら $3$ 乗)の程度に小さくなる。逆に $a=c$ だと、対称な場合 $\lvert\varepsilon'\rvert=\lvert\varepsilon\rvert$ で進まない(反例の表)。そこで、右下の $2\times2$ 部分の固有値のうち $(A_k)_{nn}$ に近いほうをシフトにする Wilkinson シフト が使われる。上の反例では、このシフトは固有値そのものなので、prop-qra-deflate により 1 段で分離する。

暗黙のシフトと実行列

Arnoldi法 の系「暗黙の $Q$ の定理」により、非簡約な上 Hessenberg 行列 $H$ に対して $Z^*HZ$ が上 Hessenberg 行列で非簡約になるユニタリ行列 $Z$ は、最初の列 $Ze_1$ だけで対角ユニタリ行列の違いを除いて決まる。シフト付き QR の 1 段の $Q$ の最初の列は $(H-\mu I)e_1$ の定数倍なので、その列をもつ回転を 1 つ当て、Hessenberg 形でなくなった行列を最初の列に触れない回転で順に Hessenberg 形へ戻せば、$H-\mu I$ を作らずに、$H'$ が非簡約なら対角ユニタリ行列による相似の違いを除いて同じ $H'$ が得られる(暗黙のシフト)。
実行列 $A$ が共役な複素固有値 $\lambda,\overline\lambda$ をもつと、実数の計算では $A_k$ は実の上三角行列にはなりえず、対角に $2\times2$ の塊が残る。複素数のシフトを使えば複素の上三角行列に収束させられる(ex-qra-real)。実数のまま進めるには、$\mu$ と $\overline\mu$ の 2 段をまとめ、$(H-\mu I)(H-\overline\mu I)$ の最初の列から暗黙のシフトを始める。これは 二重シフト と呼ばれ、Francis が QR 法に使った(Fra61、Fra62。Saa11 p. 196)。

計算の手順

入力は $n$ 次の正方行列 $A$ と許容誤差 $\varepsilon$(たとえば丸めの単位の数倍)である。

  1. Hessenberg 化:Householder 変換で $H:=Q_0^*AQ_0$ を上 Hessenberg 行列にする(Hermite なら三重対角)。演算は $n^3$ の程度で、1 度だけ行う。
  2. 分離の判定:$\lvert h_{j+1,j}\rvert\le\varepsilon(\lvert h_{jj}\rvert+\lvert h_{j+1,j+1}\rvert)$ となる副対角成分を $0$ に置き換え、問題を非簡約な対角ブロックに分ける。
  3. シフト:処理中のブロックの右下 $2\times2$ 部分から Wilkinson シフト $\mu$ を選ぶ(実数で計算するなら共役な組で二重シフト)。
  4. 1 段:Givens 回転で $H-\mu I$ の QR 分解を作り $H\leftarrow RQ+\mu I$ とする(または暗黙のシフト)。Schur 分解が欲しければ回転を $Q_0$ に掛けていく。
  5. 右下の副対角成分が分離されたら、その対角成分(または $2\times2$ の塊の固有値)を固有値として取り出し、ブロックを縮めて手順 2 へ戻る。

例題

対称な $2\times2$ の行列

$A=\begin{pmatrix}2&1\\1&2\end{pmatrix}$(固有値 $3,1$)にシフトなしの QR 法を当てる。
使う公式:prop-qra-basic、thm-qra-conv。
答え:
$$ A_k=\begin{pmatrix}3-\dfrac2{9^k+1}&\dfrac{2\cdot3^k}{9^k+1}\\[2mm]\dfrac{2\cdot3^k}{9^k+1}&1+\dfrac2{9^k+1}\end{pmatrix} $$
で、副対角成分は $k=1,2,3,4$ で $0.6$、$0.219512$、$0.073973$、$0.024688$ と、1 段ごとにおよそ $\lvert\lambda_2/\lambda_1\rvert=\frac13$ 倍になる。

途中の計算を開く

$A^k=\frac12\begin{pmatrix}3^k+1&3^k-1\\3^k-1&3^k+1\end{pmatrix}$ である。prop-qra-basic の 2 から $A^k=\widehat Q_k\widehat R_k$ で、$\widehat Q_k$ の最初の列は $(\gamma,\sigma)^{\mathsf T}:=(3^k+1,3^k-1)^{\mathsf T}/N$($N^2=2(9^k+1)$)、$\det A^k>0$ なので第 2 列は $(-\sigma,\gamma)^{\mathsf T}$ である。$A_k=\widehat Q_k^{\mathsf T}A\widehat Q_k$ の $(1,1)$ 成分は $2+2\gamma\sigma=3-\frac2{9^k+1}$、$(2,1)$ 成分は $\gamma^2-\sigma^2=\frac{2\cdot3^k}{9^k+1}$ である。

Rayleigh シフトの速さ

$H=\begin{pmatrix}1&1\\0.1&3\end{pmatrix}$ と $H_{\mathrm s}=\begin{pmatrix}1&0.1\\0.1&3\end{pmatrix}$ に Rayleigh シフトの QR 法を当てる。
使う公式:prop-qra-2x2。
答え:

段$1$$2$$3$右下の成分の極限
$H$ の $\lvert\varepsilon\rvert$$2.4938\times10^{-3}$$1.2659\times10^{-6}$$3.278\times10^{-13}$$2+\sqrt{1.1}\approx3.048809$
$H_{\mathrm s}$ の $\lvert\varepsilon\rvert$$2.4938\times10^{-4}$$3.8387\times10^{-12}$$1.4002\times10^{-35}$$2+\sqrt{1.01}\approx3.004988$

表の値は丸めの影響が出ない精度で計算したものである(倍精度では $10^{-16}$ の程度より先は見えない)。1 段目は公式どおり $0.01/4.01$ と $0.001/4.01$ である。指数が段ごとにほぼ $2$ 倍(対称なら $3$ 倍)になる。

複素固有値をもつ実行列

$A=\begin{pmatrix}3&0&5\\4&5&0\\0&4&3\end{pmatrix}$(QR分解 の例と同じ行列。上 Hessenberg 行列)の固有値は $8.089023$ と $1.455488\pm3.651656i$ である。
使う公式:thm-qra-conv、Wilkinson シフト。
答え:シフトなしの実数の QR 法では $A_1$ の対角成分は $(6.2,1.8,3)$ で、

$k$$10$$20$$30$$40$
$\lvert(A_k)_{21}\rvert$$7.901\times10^{-3}$$5.172\times10^{-6}$$4.228\times10^{-9}$$3.557\times10^{-12}$
$\lvert(A_k)_{32}\rvert$$3.754$$4.729$$3.820$$2.912$

である。$(A_k)_{21}$ は 10 段ごとにおよそ $0.486^{10}$ 倍($0.486\approx\lvert\lambda_2\rvert/\lvert\lambda_1\rvert$)になるが、右下の $2\times2$ の塊は三角にならず、その固有値が $1.455488\pm3.651656i$ に収束する。複素数の Wilkinson シフトを使うと、$\lvert h_{32}\rvert$ は $4,5,3.58,1.97,0.116,1.44\times10^{-4},2.33\times10^{-10}$ と 6 段で分離し、$h_{33}\approx1.4554885-3.6516563i$ になる(図 1)。

シフトなしの QR 法の副対角成分と、Wilkinson シフトの副対角成分を段数に対して片対数で描いたもの シフトなしの QR 法の副対角成分と、Wilkinson シフトの副対角成分を段数に対して片対数で描いたもの

使える条件と反例

外す条件反例成り立たなくなること
固有値の絶対値が相異なる$A=\begin{pmatrix}0&1\\1&0\end{pmatrix}$(固有値 $\pm1$)すべての $k$ で $A_k=A$ で、副対角成分が $0$ に近づかない(thm-qra-conv)
実数の計算で固有値が実数回転行列 $\begin{pmatrix}\cos t&-\sin t\\\sin t&\cos t\end{pmatrix}$($0< t< \pi$)$A_k=A$ で上三角にならない
$X^{-1}$ が LU 分解をもつ$A=\operatorname{diag}(1,2)$$A_k=A$ で、$(A_k)_{11}=1$ は絶対値の大きい固有値 $\lambda_1=2$ に近づかない(thm-qra-conv)
Rayleigh シフトで $a\ne c$$\begin{pmatrix}0&1\\1&0\end{pmatrix}$、$\mu=0$$\lvert\varepsilon'\rvert=\lvert\varepsilon\rvert$ で進まない(prop-qra-2x2)
反例の確認
確認の計算を開く

絶対値:$A$ は直交行列なので $A=A\cdot I$ が対角成分が正の QR 分解で、$A_1=IA=A$ である。シフト $\mu=0$ で Givens 回転を使うと $R=\operatorname{diag}(1,-1)$、$A_1=-A$ で、$\lvert\varepsilon'\rvert=\lvert\varepsilon\rvert$ である。

実数:回転行列も直交行列で、同じく $A_1=A$ である。固有値 $e^{\pm it}$ は実数でない。

LU 分解:$\Lambda=\operatorname{diag}(2,1)$ と並べると $X=X^{-1}=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ で、$(1,1)$ 成分が $0$ なので LU 分解をもたない。$A$ は上三角で対角成分が正なので $A=I\cdot A$ が QR 分解で、$A_1=A$ である。

よくある誤り

誤り正しくはなぜ
$A$ の QR 分解の $R$ の対角成分が固有値固有値は反復の極限で現れるthm-qra-conv
QR 法の 1 段には常に $n^3$ の演算が要るHessenberg 化すれば $n^2$、三重対角なら $n$ の程度prop-qra-hessenberg
Rayleigh シフトならいつも速く収束する対称な行列で止まる例がある。Wilkinson シフトを使う反例の表
実行列の QR 法は実の上三角行列に収束する複素固有値の組は $2\times2$ の塊で残るex-qra-real

補足

戸田格子。 戸田格子の Lax 行列 $L(t)$ について、$e^{L(t)}$ を整数の時刻で見た列は $e^{L(0)}$ から始めた QR 法の列である(戸田格子 の系「QR 法との一致」、Tom15 §5)。QR 法の 1 段は可積分な流れの時刻 $1$ の写像になっている。
Lyapunov 指数の計算との違い。 Lyapunov指数 の命題「QR 法の和」の QR 法は、行列の積を QR 分解で順に直交化して拡大率を測る別の手法であり、この記事の相似変換の反復とは異なる。
歴史。 QR 法は Francis による(Fra61、Fra62)。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する