QR分解(QR decomposition)とは、行数が列数以上の行列 $A$ を、ユニタリ行列(実数なら直交行列)$Q$ と上三角行列 $R$ の積 $A=QR$ に分けることである。$Q$ の列を $A$ の列数だけ残した薄い形では、列が 1 次独立なら $R$ の対角成分を正にする条件で分解はただ 1 つに定まり、Gram–Schmidt の直交化の結果と一致する。計算には Householder 変換や Givens 回転を使う。ユニタリ行列を掛けても長さが変わらないので、連立 1 次方程式や列が 1 次独立な最小二乗問題を、条件数を悪化させずに上三角の方程式へ直せる。
前提知識: 正規直交基底, Gram–Schmidtの直交化, ユニタリ行列, 三角行列
$m$ 行 $n$ 列の行列 $A$ と $b\in\mathbb{R}^m$ について、$\|Ax-b\|$ を最小にする $x$ を求めたいとする。$A^{\top}Ax=A^{\top}b$ を解く方法は、行列を掛け合わせるところで条件数が 2 乗になる(最小二乗法 の命題「正規方程式の条件数」)。ところがユニタリ行列 $Q$ を掛けても長さは変わらず、$\|Ax-b\|=\|Q^*Ax-Q^*b\|$ である。そこで $Q^*A$ が上三角になる $Q$ を見つければ、問題は上三角の方程式に変わり、長さも条件数も悪くならない。
行列を $A=QR$($Q$ はユニタリ行列、$R$ は上三角行列)と分けることを QR 分解 という。LU分解 が消去の記録なら、QR 分解は直交化の記録である。この記事では、行数が列数以上のどの行列にも完全な QR 分解があることを Householder 変換で証明し、列が 1 次独立なら対角成分を正にした薄い分解がただ 1 つで、Gram–Schmidt の直交化の結果と一致することを示す。続いて演算の回数と、Householder 変換・Givens 回転・Gram–Schmidt の使い分けを扱う。正則な正方行列の場合の Gram–Schmidt による証明は 正規直交基底 の定理「正則行列のQR分解の存在と一意性」にある。
以下、$F$ は $\mathbb{R}$ または $\mathbb{C}$ とする。$F^m$ の元は列ベクトルとし、$\|x\|:=\sqrt{x^*x}$、$x^*$ は共役転置である($F=\mathbb{R}$ なら転置)。標準内積は $\langle x,y\rangle=y^*x$ である。$m\ge n$ とし、$A\in M_{m,n}(F)$ の列を $a_1,\dots,a_n$ と書く。$i>j$ で $r_{ij}=0$ となる $m$ 行 $n$ 列の行列を、正方でなくても 上三角 という。
$A\in M_{m,n}(F)$、$m\ge n$ とする。
完全 QR 分解を $Q=(Q_1\ Q_2)$、$R=\begin{pmatrix}R_1\\0\end{pmatrix}$($Q_1$ は最初の $n$ 列、$R_1$ は最初の $n$ 行)と区分けすると、$A=Q_1R_1$ は薄い QR 分解である。$m=n$ なら 2 つは同じである。列が 1 次独立な $A$ について、$R_1$ の対角成分を正にした薄い分解を単に QR 分解と呼ぶ文献も多い(最小二乗法 の節「QR 分解による解法」)。$F=\mathbb{R}$ なら $Q$ は直交行列である。
計算に使う 2 種類のユニタリ行列を定める。
$H_v$ は超平面 $v^{\perp}$ に関する鏡映であり(lem-qrd-householder)、$G$ は $G^*G=I_2$、$\det G=1$、$G\begin{pmatrix}a\\b\end{pmatrix}=\begin{pmatrix}r\\0\end{pmatrix}$ を満たす(第 2 成分は $(-ba+ab)/r=0$)。$F=\mathbb{R}$ なら $G=\begin{pmatrix}c&s\\-s&c\end{pmatrix}$ は回転の行列である。
使える条件をまとめる。
演算の回数は実行列での主要項である。$H_k$ は第 $k$ 段の鏡映(節「計算の手順」)を表し、第 $k$ 行以下に働く。
| 計算 | 公式 | 使える条件 | 演算の回数 | 根拠 |
|---|---|---|---|---|
| 第 1 成分以外を消す鏡映 | $v=x+\sigma\Vert x\Vert e_1$、$H_vx=-\sigma\Vert x\Vert e_1$ | $x\ne0$、$\sigma=x_1/\lvert x_1\rvert$($x_1=0$ なら $\sigma=1$) | $2k$($x\in F^k$) | lem-qrd-householder |
| 鏡映を行列に掛ける | $H_vB=B-\beta v(v^*B)$、$\beta=2/(v^*v)$ | $v\ne0$ | $4pq$($B$ が $p$ 行 $q$ 列) | prop-qrd-flops |
| 2 成分の一方を消す回転 | $G(a,b)^{\top}=(r,0)^{\top}$ | $(a,b)\ne(0,0)$ | 行の組に列 1 本あたり $6$ | def-qrd-reflectors |
| QR 分解(Householder) | $H_n\cdots H_1A=R$ | $m\ge n$ | $2mn^2-\frac23n^3$ | thm-qrd-exist、prop-qrd-flops |
| QR 分解(Gram–Schmidt) | $r_{ij}=q_i^*a_j$、$r_{jj}=\Vert w_j\Vert$ | 列が 1 次独立 | $2mn^2$ | thm-qrd-unique、prop-qrd-flops |
| QR 分解(Givens) | $\prod G(i,j)\cdot A=R$ | $m\ge n$ | $3mn^2-n^3$ | prop-qrd-flops |
| 上 Hessenberg 行列の QR 分解 | $G(n-1,n)\cdots G(1,2)A=R$ | $m=n$、$i>j+1$ で $a_{ij}=0$ | $3n^2$ | prop-qrd-flops |
| 連立 1 次方程式 | $Rx=Q^*b$ | $m=n$、$A$ が正則 | 後退代入 $n^2$ | prop-qrd-ls |
| 最小二乗解と残差 | $R_1\hat x=Q_1^*b$、$\min\Vert Ax-b\Vert=\Vert Q_2^*b\Vert$ | 列が 1 次独立 | $Q^*b$ は $4mn-2n^2$ | prop-qrd-ls |
| 像への直交射影 | $Q_1Q_1^*$ | 列が 1 次独立 | — | thm-qrd-unique |
| Gram 行列 | $A^*A=R_1^*R_1$ | 薄い分解があること | — | prop-qrd-gram |
| 条件数 | $\kappa_2(R_1)=\kappa_2(A)$ | 列が 1 次独立 | — | prop-qrd-gram |
| 行列式の絶対値 | $\lvert\det A\rvert=\prod_j\lvert r_{jj}\rvert$ | $m=n$ | — | prop-qrd-gram |
$0$ でない $v\in F^k$ について、次が成り立つ。
要点:2 は $v^*v=2(\|x\|^2-y^*x)$、$v^*x=\|x\|^2-y^*x$ から $\frac{2v^*x}{v^*v}=1$ となることによる。
1. $(vv^*)^*=vv^*$ と $v^*v$ が正の実数であることから $H_v^*=H_v$ である。$H_v^2=I_k-\frac{4}{v^*v}vv^*+\frac{4}{(v^*v)^2}v(v^*v)v^*=I_k$ なので、$H_v^*H_v=I_k$ である。$H_vv=v-2v=-v$ であり、$v^*w=0$ なら $H_vw=w$ である。
2. $y^*x$ が実数なので $x^*y=\overline{y^*x}=y^*x$ である。よって $v^*v=\|x\|^2-x^*y-y^*x+\|y\|^2=2(\|x\|^2-y^*x)$、$v^*x=\|x\|^2-y^*x$ であり、$x\ne y$ より $v^*v>0$ である。したがって $H_vx=x-\frac{2v^*x}{v^*v}v=x-v=y$ である。
3. $y^*x=(H_vx)^*x=x^*H_vx$ であり、$H_v$ は Hermite 行列なので、この値は実数である。
4. $y:=-\sigma\|x\|e_1$ とおくと $\|y\|=\|x\|$、$y^*x=-\bar\sigma\|x\|x_1=-\|x\|\lvert x_1\rvert$ は実数である。$v=x-y$ の第 1 成分は $\sigma(\lvert x_1\rvert+\|x\|)\ne0$ なので $x\ne y$ であり、2 が使える。$v^*v$ の値は 2 の式から得られる。$\square$
条件「$y^*x$ が実数」は複素数の場合に効く。$F=\mathbb{R}$ では自動的に成り立つが、$F=\mathbb{C}$ では $y=\|x\|e_1$ を狙っても鏡映では届かないことがある(ex-qrd-complex)。4 の $\sigma$ は、$v$ の第 1 成分で打ち消しが起きないように選んだものであり、$\|v\|\ge\sqrt2\|x\|$ が保証される。
$m\ge n$ とする。任意の $A\in M_{m,n}(F)$ は完全 QR 分解 $A=QR$ をもち、$R$ の対角成分をすべて $0$ 以上の実数にとれる。$Q$ は高々 $n$ 個の Householder 変換の積と、対角のユニタリ行列の積で書ける。$F=\mathbb{R}$ なら $Q$ は実の直交行列、$R$ は実行列である。
$A^{(0)}:=A$ とおく。$k=1,\dots,n$ について、ユニタリ行列 $U_k\in M_m(F)$ を次のように定め、$A^{(k)}:=U_kA^{(k-1)}$ とおく。$A^{(k-1)}$ の第 $k$ 列の第 $k$ 成分から第 $m$ 成分までを並べたベクトルを $x\in F^{m-k+1}$ とする。$x$ の第 2 成分以降がすべて $0$ なら $U_k:=I_m$ とする。そうでなければ $x\ne0$ なので、lem-qrd-householder の 4 の $v\in F^{m-k+1}$ をとり、
$$
U_k:=\begin{pmatrix}I_{k-1}&0\\0&H_v\end{pmatrix}
$$
とする。lem-qrd-householder の 1 により $U_k$ はユニタリ行列である。
$k$ についての帰納法で、$A^{(k)}$ の第 $j$ 列($j\le k$)の第 $j+1$ 行以下が $0$ であることを示す。$U_k$ は第 $1$ 行から第 $k-1$ 行を変えない。$j< k$ のとき、$A^{(k-1)}$ の第 $j$ 列は第 $k$ 行以下が $0$ なので、$H_v$ を掛けても $0$ のままである。第 $k$ 列は、$U_k=I_m$ なら初めから、そうでなければ lem-qrd-householder の 4 により、第 $k+1$ 行以下が $0$ である。
よって $T:=A^{(n)}=U_n\cdots U_1A$ は上三角である。$D:=\operatorname{diag}(d_1,\dots,d_m)$ を、$j\le n$ で $\lvert d_j\rvert=1$、$d_jt_{jj}=\lvert t_{jj}\rvert$($t_{jj}=0$ なら $d_j=1$)、$j>n$ で $d_j=1$ と定める。$R:=DT$ は上三角で対角成分は $0$ 以上の実数である。$Q:=U_1^*\cdots U_n^*D^*$ はユニタリ行列の積なのでユニタリ行列であり、$QR=U_1^*\cdots U_n^*T=A$ である。
$H_v^*=H_v$ なので、$U_k^*=U_k$ は($U_k\ne I_m$ なら)$F^m$ の Householder 変換である($v$ の前に $0$ を $k-1$ 個並べたベクトルの $H$ にあたる)。$F=\mathbb{R}$ なら $v$ と $D$ は実なので、すべて実の行列である。$\square$
$m\ge n$ とし、$A\in M_{m,n}(F)$ の列 $a_1,\dots,a_n$ が 1 次独立であるとする。
列が 1 次独立なら、丸めのない計算では Householder 変換の結果も、対角の符号を thm-qrd-exist の $D$ で直せば、Gram–Schmidt の結果と同じ $Q_1,R_1$ になる。修正 Gram–Schmidt 法も同じである(Gram–Schmidtの直交化 の命題「修正 Gram–Schmidt 法は同じ結果を与える」)。手順の違いは、丸めのある計算でだけ現れる。
$A\in M_{m,n}(F)$、$m\ge n$ の列が 1 次独立であるとし、$A=QR$ を完全 QR 分解、$Q=(Q_1\ Q_2)$、$R=\begin{pmatrix}R_1\\0\end{pmatrix}$ とする。すべての $x\in F^n$、$b\in F^m$ について
$$
\|Ax-b\|^2=\|R_1x-Q_1^*b\|^2+\|Q_2^*b\|^2
$$
である。したがって $\|Ax-b\|$ を最小にする $x$ は $R_1\hat x=Q_1^*b$ のただ 1 つの解であり、最小値は $\|Q_2^*b\|$ である。とくに $m=n$ なら、$Ax=b$ は $Rx=Q^*b$ と同値である。
$Q^*$ はユニタリ行列なので $\|Ax-b\|=\|Q^*(Ax-b)\|=\|Rx-Q^*b\|$ である。$Rx-Q^*b$ の最初の $n$ 成分は $R_1x-Q_1^*b$、残りは $-Q_2^*b$ なので、等式を得る。thm-qrd-unique の 1 により $R_1$ は正則なので、第 1 項は $R_1\hat x=Q_1^*b$ のときだけ $0$ になる。第 2 項は $x$ によらない。$\square$
実数の場合の同じ結論は、最小二乗法 の定理「QR 分解による最小二乗解」が正規方程式から示している。Householder 変換を $b$ に順に掛けて $Q^*b$ を作れば、その後ろの $m-n$ 成分の長さが残差である。
$A$ の列が 1 次独立なとき、$\kappa_2(A):=\max_{\|x\|=1}\|Ax\|\big/\min_{\|x\|=1}\|Ax\|$ を $A$ の条件数という(正方行列なら 条件数 の Euclid ノルムの場合と同じ)。
$A=Q_1R_1$ を薄い QR 分解とする。
要点:$Q_1^*Q_1=I_n$ を代入し、$\|Ax\|=\|R_1x\|$ を使う。
1. $A^*A=R_1^*Q_1^*Q_1R_1=R_1^*R_1$ である。$x\ne0$ なら $x^*A^*Ax=\|Ax\|^2>0$ なので $A^*A$ は正定値である。$R_1^*$ は対角成分が正の下三角行列なので、Cholesky分解 の定理「Cholesky 分解の存在と一意性」により因子そのものである。
2. $\|Ax\|^2=x^*R_1^*Q_1^*Q_1R_1x=\|R_1x\|^2$ なので、最大値と最小値は同じである。
3. $\lvert\det Q_1\rvert=1$ なので $\lvert\det A\rvert=\lvert\det R_1\rvert=\prod_j\lvert r_{jj}\rvert$ である。第 $j$ 列の長さを比べると、$Q_1$ が長さを保つので $\lvert r_{jj}\rvert^2\le\sum_i\lvert r_{ij}\rvert^2=\|a_j\|^2$ である。$\square$
3 を掛け合わせると $\lvert\det A\rvert\le\prod_j\|a_j\|$ を得る(Hadamardの不等式(行列式)。Axl24 9.66、p. 365 の証明もこの道筋である)。
加減乗除 1 回を 1 回の演算と数える(LU分解 の命題「分解と代入の演算回数」と同じ)。
$A\in M_{m,n}(\mathbb{R})$ を密な行列とし、$m\ge n$ とする。演算の回数の主要項は次のとおりである。
要点:第 $k$ 段の Householder 変換は長さ $p=m-k+1$ の列 $q=n-k$ 本に各 $4p$ 回の演算をし、$\sum_k4pq$ の主要項が $2mn^2-\frac23n^3$ である。
1. 長さ $p$ の列 $c$ に $H_v$ を掛ける式 $c-\beta(v^{\top}c)v$ は、内積 $2p-1$ 回、スカラー倍 $p+1$ 回、減法 $p$ 回の計 $4p$ 回である。第 $k$ 段では $q=n-k$ 本の列を更新し、$v$ と $\beta$ を作るのは $O(p)$ 回である。$j=n-k$ とおくと $\sum_{j=0}^{n-1}4(m-n+1+j)j=2(m-n)n^2+\frac43n^3+O(mn+n^2)=2mn^2-\frac23n^3+O(mn+n^2)$ である。$b$ への適用は $\sum_{k=1}^n4(m-k+1)=4mn-2n^2+O(m+n)$ 回である。
2. $i< j$ の組ごとに、内積 $2m-1$ 回と、スカラー倍と減法 $2m$ 回の計 $4m-1$ 回である。組は $\frac{n(n-1)}2$ 個なので $2mn^2$ が主要項であり、列の正規化は $O(mn)$ 回である。
3. 実の回転は、2 つの行の組に列 1 本あたり乗法 4 回と加法 2 回の計 6 回である。第 $k$ 列の第 $k+1$ 行以下の $m-k$ 個を消すのに、右の $n-k$ 列を更新するので、$\sum_{k=1}^n6(m-k)(n-k)=3mn^2-n^3+O(mn+n^2)$ 回である。上 Hessenberg 行列では第 $k$ 列で消す成分は 1 個なので $\sum_{k=1}^{n-1}6(n-k)=3n(n-1)$ 回である。$\square$
正方行列の主要項は Householder が $\frac43n^3$ で、LU分解 の $\frac23n^3$ の 2 倍である。
Householder 変換による QR 分解($A$ は上書きする。thm-qrd-exist の証明の手順)
Gram–Schmidt の手順($j=1,\dots,n$ について $u:=a_j$ から始める)
| 手順 | 第 $i$ 段($i=1,\dots,j-1$) | 最後に |
|---|---|---|
| 古典的 | $r_{ij}:=q_i^*a_j$(元の $a_j$ で)をまとめて求め、$u\leftarrow u-\sum_ir_{ij}q_i$ | $r_{jj}:=\Vert u\Vert$、$q_j:=u/r_{jj}$ |
| 修正 | $r_{ij}:=q_i^*u$(途中の $u$ で)、$u\leftarrow u-r_{ij}q_i$ を 1 つずつ | 同じ |
Givens 回転:第 $j$ 列の $a_{ij}$($i>j$)を、$(a_{jj},a_{ij})$ の回転 $G(j,i)$ を左から掛けて消す。
止める判定と失敗:丸めのある計算では、$\lvert r_{kk}\rvert\le\tau\|A\|$($\tau$ は計算機精度の数倍から $m$ 倍程度に決める)となったら列が数値的に 1 次従属とみなし、$R_1$ で割らない。列を入れ替える分解(rem-qrd-pivoting)か 特異値分解 に切り替える。
| 手順 | 演算の回数 | 計算した $Q$ の直交性 | 向く場面 |
|---|---|---|---|
| Householder | $2mn^2-\frac23n^3$ | 条件数によらず計算機精度の程度(図) | 密な行列の標準の方法 |
| Givens | $3mn^2-n^3$ | Householder と同じ程度(ex-qrd-orthogonality) | 上 Hessenberg 行列、疎な行列、1 成分ずつ消す更新 |
| 修正 Gram–Schmidt | $2mn^2$ | 条件数に比例する程度に失う(図の数値例) | $q_j$ を 1 本ずつ作る反復法(Krylov部分空間法 の Arnoldi の手順) |
| 古典 Gram–Schmidt | $2mn^2$ | 条件数の 2 乗の程度に失う(図の数値例) | 手計算、理論 |
左:Householder 変換が x を同じ長さの y へ写す鏡映。右:条件数を変えた行列で計算した Q の直交性の失われ方
右の図は、$m=50$、$n=20$、特異値が $1$ から $1/\kappa$ まで等比に並ぶ行列を倍精度で計算した結果である。縦軸の $\|I-\hat Q^*\hat Q\|_2$ は、計算した $\hat Q$ が正規直交からどれだけずれたかを表す。
$A=\begin{pmatrix}3&0\\4&5\\0&4\end{pmatrix}$、$b=(5,0,5)^{\top}$ とする。
使う公式:lem-qrd-householder の 4、prop-qrd-ls。
答え:$Q_1=\begin{pmatrix}3/5&-12/25\\4/5&9/25\\0&4/5\end{pmatrix}$、$R_1=\begin{pmatrix}5&4\\0&5\end{pmatrix}$、$Q_2=(16/25,-12/25,3/5)^{\top}$。最小二乗解は $\hat x=(\frac{43}{125},\frac8{25})^{\top}=(0.344,0.32)^{\top}$、残差は $\|A\hat x-b\|=\frac{31}5=6.2$。
第 1 段:$x=(3,4,0)^{\top}$、$\|x\|=5$、$\sigma=1$、$v_1=(8,4,0)^{\top}$、$\beta_1=2/80$。第 2 列 $c=(0,5,4)^{\top}$ は $v_1^{\top}c=20$ なので $c-\frac{20}{40}v_1=(-4,3,4)^{\top}$ となり、$H_{v_1}A=\begin{pmatrix}-5&-4\\0&3\\0&4\end{pmatrix}$ である。
第 2 段:$x=(3,4)^{\top}$ で同じ鏡映を第 2 行以下に使うと第 2 列は $(-4,-5,0)^{\top}$ になる。$T=\begin{pmatrix}-5&-4\\0&-5\\0&0\end{pmatrix}$ である。
対角を正にする:$D=\operatorname{diag}(-1,-1,1)$ として $R=DT$。$Q=H_1H_2D^*$ から上の $Q_1,Q_2$ を得る。
$Q_1^{\top}b=(3,\frac85)^{\top}$ なので、後退代入で $5\hat x_2=\frac85$、$5\hat x_1+4\hat x_2=3$。$Q_2^{\top}b=\frac{16}5+3=\frac{31}5$ が残差である。
$A=\begin{pmatrix}1&-1&4\\1&4&-2\\1&4&2\\1&-1&0\end{pmatrix}$ の薄い QR 分解を求める。
使う公式:節「計算の手順」の修正の行、thm-qrd-unique の 4。
答え:$Q_1=\frac12\begin{pmatrix}1&-1&1\\1&1&-1\\1&1&1\\1&-1&-1\end{pmatrix}$、$R_1=\begin{pmatrix}2&3&2\\0&5&-2\\0&0&4\end{pmatrix}$。
$r_{11}=\|a_1\|=2$、$q_1=\frac12(1,1,1,1)^{\top}$。第 2 列:$r_{12}=q_1^{\top}a_2=3$、$u=a_2-3q_1=\frac52(-1,1,1,-1)^{\top}$、$r_{22}=5$、$q_2=\frac12(-1,1,1,-1)^{\top}$。第 3 列:$r_{13}=q_1^{\top}a_3=2$、$u=a_3-2q_1=(3,-3,1,-1)^{\top}$、$r_{23}=q_2^{\top}u=-2$、$u\leftarrow u+2q_2=(2,-2,2,-2)^{\top}$、$r_{33}=4$、$q_3=\frac12(1,-1,1,-1)^{\top}$。
$A=\begin{pmatrix}3i&1\\4&i\end{pmatrix}$ とする。
使う公式:lem-qrd-householder の 2〜4、prop-qrd-gram の 3。
答え:第 1 列 $x=(3i,4)^{\top}$ は、$\sigma=i$ の鏡映 $H_v$($v=(8i,4)^{\top}$)で $y=(-5i,0)^{\top}$ に写る。一方 $y'=(5,0)^{\top}$ には $\|y'\|=\|x\|$ でも写せない($y'^*x=15i$ は実数でない)。対角成分の正な分解は $Q=\frac15\begin{pmatrix}3i&4\\4&3i\end{pmatrix}$、$R=\begin{pmatrix}5&i/5\\0&7/5\end{pmatrix}$ で、$\lvert\det A\rvert=7=5\cdot\frac75$ である。
$y^*x=\overline{(-5i)}\cdot3i=5i\cdot3i=-15$ は実数である。$H_{x-y}=\begin{pmatrix}-3/5&-4i/5\\4i/5&3/5\end{pmatrix}$ で、$H_{x-y}x=y$。Gram–Schmidt では $r_{11}=5$、$q_1=x/5$、$r_{12}=q_1^*a_2=-\frac{3i}5+\frac{4i}5=\frac i5$、$a_2-r_{12}q_1=\bigl(\frac{28}{25},\frac{21i}{25}\bigr)^{\top}$、$r_{22}=\frac75$、$q_2=\bigl(\frac45,\frac{3i}5\bigr)^{\top}$。$\det A=-3-4=-7$。
$A=\begin{pmatrix}3&0&5\\4&5&0\\0&4&3\end{pmatrix}$ を 2 回の Givens 回転で上三角にする。
使う公式:def-qrd-reflectors、prop-qrd-flops の 3。
答え:$G(1,2)$($c=\frac35$、$s=\frac45$)と $G(2,3)$($c=\frac35$、$s=\frac45$)で $R=\begin{pmatrix}5&4&3\\0&5&0\\0&0&5\end{pmatrix}$。$\det A=125$ は対角成分の積に等しい。掛ける順を逆にした $A_1:=RQ=\begin{pmatrix}6.2&1.44&3.08\\4&1.8&-2.4\\0&4&3\end{pmatrix}$ も上 Hessenberg 行列で、跡 $11$ と固有多項式は $A$ と同じである(rem-qrd-qr-algorithm)。
$G(1,2)A=\begin{pmatrix}5&4&3\\0&3&-4\\0&4&3\end{pmatrix}$。続いて第 2・3 行の $(3,4)$ を消すと $R$ を得る。$Q=G(1,2)^{\top}G(2,3)^{\top}=\begin{pmatrix}3/5&-12/25&16/25\\4/5&9/25&-12/25\\0&4/5&3/5\end{pmatrix}$。
$\varepsilon=10^{-8}$、$A=\begin{pmatrix}1&1\\\varepsilon&0\\0&\varepsilon\end{pmatrix}$、$b=(2,\varepsilon,\varepsilon)^{\top}$ とする。厳密な解は $x=(1,1)^{\top}$、$\kappa_2(A)=\sqrt{2+\varepsilon^2}/\varepsilon\approx1.414\times10^8$ である。
使う公式:prop-qrd-ls。
答え:倍精度の計算では $1+\varepsilon^2$ が $1$ に丸められ、$A^{\top}A=\begin{pmatrix}1+\varepsilon^2&1\\1&1+\varepsilon^2\end{pmatrix}$ は全成分が $1$ の特異な行列になる。正規方程式はここで解けなくなる(Cholesky分解 も止まる)。一方、倍精度の Householder の QR 分解で解くと、$x$ の各成分の誤差は約 $2\times10^{-16}$ である。
$n$ 次の Hilbert 行列 $A=(1/(i+j-1))$ を倍精度で分解し、$\|I-\hat Q^{\top}\hat Q\|_2$ を比べる。どの手順でも $\hat Q\hat R$ は $A$ を計算機精度の程度で再現するが、$\hat Q$ の直交性は大きく違う。
| $n$ | $\kappa_2(A)$ | 古典 Gram–Schmidt | 修正 Gram–Schmidt | Householder |
|---|---|---|---|---|
| $4$ | $1.6\times10^{4}$ | $3\times10^{-11}$ | $3\times10^{-13}$ | $9\times10^{-16}$ |
| $6$ | $1.5\times10^{7}$ | $3\times10^{-4}$ | $3\times10^{-10}$ | $7\times10^{-16}$ |
| $8$ | $1.5\times10^{10}$ | $1.0$ | $3\times10^{-7}$ | $1\times10^{-15}$ |
| $10$ | $1.6\times10^{13}$ | $3.0$ | $4\times10^{-5}$ | $8\times10^{-16}$ |
Givens 回転で計算しても、どの $n$ でも Householder と同じ程度である。Hilbert 行列の条件数については 条件数 の例「Hilbert 行列の条件数」を見よ。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 列が 1 次独立 | $A=\begin{pmatrix}1&1\\0&0\end{pmatrix}$ | $Q=I_2$ でも $Q=\operatorname{diag}(1,-1)$ でも $R=A$ で対角成分は $0$ 以上。分解は一意でない |
| $R_1$ の対角成分が正 | $A=I_2$ | $(Q,R)=(I_2,I_2)$ と $(\operatorname{diag}(1,-1),\operatorname{diag}(1,-1))$ の 2 つがある |
| 薄い分解($m>n$ の完全な分解にする) | $A=(1,0)^{\top}$ | $R=(1,0)^{\top}$ は同じで、$Q=I_2$ でも $Q=\operatorname{diag}(1,-1)$ でもよい。$Q_2$ は一意でない |
| $m\ge n$ | $A=(1\ \ 1)$ | $F^1$ に正規直交な 2 本の列はないので薄い分解がない($m< n$ なら列は 1 次独立でない) |
| $y^*x$ が実数 | $x=(i,0)^{\top}$、$y=(1,0)^{\top}$ | 長さは同じだが $y^*x=i$ は実数でなく、$H_vx=y$ となる $v$ はない |
| 符号 $\sigma$ の選び方 | 倍精度で $x=(1,10^{-9})^{\top}$、$v=x-\Vert x\Vert e_1$ と計算 | 下の ex-qrd-counter の打ち消しで $x$ の第 2 成分が消えない |
表の最後の 2 行を確かめる。
$y^*x$ が実数:lem-qrd-householder の 3 により、$H_vx=y$ となる $v$ があれば $y^*x$ は実数である。$x=(i,0)^{\top}$、$y=(1,0)^{\top}$ では $y^*x=i$ なので、そのような $v$ はない。
符号の選び方:$x=(1,10^{-9})^{\top}$ では $\|x\|=\sqrt{1+10^{-18}}$ が倍精度で $1$ に丸められる。$\|x\|$ を引く形の $v=x-\|x\|e_1$ の第 1 成分は、正しくは $-5\times10^{-19}$ の程度なのに $0$ になり、$v=(0,10^{-9})^{\top}$ から $H_vx=(1,-10^{-9})^{\top}$ となる。第 2 成分は消えていない。lem-qrd-householder の 4 の $v=x+\sigma\|x\|e_1=(2,10^{-9})^{\top}$ なら $H_vx=(-1,0)^{\top}$ である。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 長方の $Q_1$ で $Q_1Q_1^*=I_m$ とする | $Q_1^*Q_1=I_n$ で、$Q_1Q_1^*$ は像への直交射影 | thm-qrd-unique の 3 |
| Householder の行列 $H$ を作って掛ける | $c-\beta v(v^*c)$ で更新し、$v$ だけを保存する | 行列を作ると $m$ の次数が上がる(prop-qrd-flops) |
| $v=x-\Vert x\Vert e_1$ と計算する | $\sigma$ を付けて $v=x+\sigma\Vert x\Vert e_1$ | 打ち消しが起きる(ex-qrd-counter) |
| 計算ソフトの $R$ の対角成分は正だと思う | 符号は手順で決まる。必要なら thm-qrd-exist の $D$ で直す | 例では鏡映の対角は $-5$(ex-qrd-householder) |
| 複素行列で $Q^{\top}$ を掛ける | 共役転置 $Q^*$ を掛ける | $Q^{-1}=Q^*$ |
| 最小二乗解を $(A^*A)^{-1}A^*b$ で計算する | $R_1\hat x=Q_1^*b$ を後退代入で解く | $\kappa_2(A^*A)=\kappa_2(A)^2$(ex-qrd-normal) |
固有値の数値計算で広く使われる QR 法は、$A_0:=A$ から $A_k=Q_kR_k$ と分解し、$A_{k+1}:=R_kQ_k=Q_k^*A_kQ_k$ とおく反復である(QR 分解が主な道具であることは Axl24 p. 264)。$A_{k+1}$ は $A_k$ にユニタリ行列で相似なので、固有値は変わらない。$A_k$ が上 Hessenberg 行列なら、$Q_k$ は回転 $G(i,i+1)^*$($i=1,\dots,n-1$)の積で、これを $R_k$ に右から順に掛けても第 $i+1$ 行第 $i$ 列の成分が増えるだけなので、$A_{k+1}$ も上 Hessenberg 行列であり、1 回の反復が $n^2$ の程度の演算で済む(prop-qrd-flops の 3)。収束はこの記事では扱わず、QR法(固有値) で扱う。
各段で、残りの列のうち第 $k$ 行以下の長さが最大のものを第 $k$ 列と入れ替えると、置換行列 $P$ について $AP=QR$、$\lvert r_{11}\rvert\ge\lvert r_{22}\rvert\ge\cdots$ となる(次の段の列の長さは第 $k$ 行を除いた分だけ短いので、$\lvert r_{kk}\rvert$ を超えない)。丸めのない計算で $A$ の階数が $r$ なら、第 $r+1$ 段で残りの列はすべて $0$ になるので、階数の判定に使える。
正方行列の場合の存在と一意性は Axl24 7.58(p. 264)、計算例は 7.60(p. 265)、$Rx=Q^*b$ による解法は p. 266 にある。長方の行列の QR 分解と Gram–Schmidt の関係は VMLS18 §10.4(p. 190)に、Gram–Schmidt の演算の回数は §5.4(p. 102)に、最小二乗への応用は Algorithm 12.1(p. 232)にある。Householder の手順と符号の選び方、$H$ を行列として作らないことは Saa03 §1.7(Algorithm 1.3、pp. 12–15)、平面の回転は §6.5.3(pp. 174–175)、複素の回転は §6.5.9(p. 193)にあり、同書の p. 163 は Householder の手順が直交化の中で信頼性が高いことを述べている。Householder の演算の回数は BV04 §C.5(p. 682)の $2p^2(n-p/3)$ と一致する。この記事の一意性の証明は三角行列の計算から、存在の証明は Householder 変換の帰納法から直接組み立てた。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する