QR分解

同義語:QR decompositionQR factorization

概要

QR分解(QR decomposition)とは、行数が列数以上の行列 $A$ を、ユニタリ行列(実数なら直交行列)$Q$ と上三角行列 $R$ の積 $A=QR$ に分けることである。$Q$ の列を $A$ の列数だけ残した薄い形では、列が 1 次独立なら $R$ の対角成分を正にする条件で分解はただ 1 つに定まり、Gram–Schmidt の直交化の結果と一致する。計算には Householder 変換や Givens 回転を使う。ユニタリ行列を掛けても長さが変わらないので、連立 1 次方程式や列が 1 次独立な最小二乗問題を、条件数を悪化させずに上三角の方程式へ直せる。

$$\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}} $$

前提知識: 正規直交基底, 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$ 列の行列を、正方でなくても 上三角 という。

QR 分解

$A\in M_{m,n}(F)$、$m\ge n$ とする。

  1. $A=QR$($Q\in M_m(F)$ は $Q^*Q=I_m$ を満たし、$R\in M_{m,n}(F)$ は上三角)を $A$ の 完全 QR 分解(full QR decomposition)という。
  2. $A=Q_1R_1$($Q_1\in M_{m,n}(F)$ は $Q_1^*Q_1=I_n$ を満たし、$R_1\in M_n(F)$ は上三角行列)を $A$ の 薄い QR 分解(thin QR decomposition)という。

完全 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 種類のユニタリ行列を定める。

Householder 変換と Givens 回転
  1. $0$ でない $v\in F^k$ について、$H_v:=I_k-\dfrac{2}{v^*v}vv^*\in M_k(F)$ を Householder 変換(Householder reflection)という。
  2. $(a,b)\in F^2$、$(a,b)\ne(0,0)$ について $r:=\sqrt{\lvert a\rvert^2+\lvert b\rvert^2}$、$c:=a/r$、$s:=b/r$ とおき、$G:=\begin{pmatrix}\bar c&\bar s\\-s&c\end{pmatrix}$ を $(a,b)$ の Givens 回転(Givens rotation)という。$G$ を単位行列の第 $i,j$ 行・第 $i,j$ 列($i< j$)の位置に埋めた行列も Givens 回転といい、$G(i,j)$ と書く。

$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}$ は回転の行列である。
使える条件をまとめる。

  1. 完全 QR 分解の存在(thm-qrd-exist):$m\ge n$ であればよい。階数の条件は要らない。
  2. 一意性(thm-qrd-unique):列が 1 次独立で、薄い分解で、$R_1$ の対角成分が正であること。どれか 1 つを外すと一意性が成り立たなくなる(節「使える条件と反例」)。
  3. 最小二乗解の公式(prop-qrd-ls):列が 1 次独立であること。
  4. 丸めのある計算:Gram–Schmidt の手順は、列が 1 次従属に近いと直交性を失う(ex-qrd-orthogonality)。

公式の表

演算の回数は実行列での主要項である。$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

主定理と証明

Householder 変換の性質

Householder 変換の性質

$0$ でない $v\in F^k$ について、次が成り立つ。

  1. $H_v^*=H_v$、$H_v^2=I_k$ であり、$H_v$ はユニタリ行列である。$H_vv=-v$ であり、$v^*w=0$ なら $H_vw=w$ である。
  2. $x,y\in F^k$ が $\|x\|=\|y\|$、$x\ne y$ を満たし、$y^*x$ が実数なら、$v:=x-y$ について $H_vx=y$ である。
  3. 逆に、ある $v$ で $H_vx=y$ なら、$y^*x$ は実数である。
  4. $x\ne0$、$\sigma$ を $x_1=\sigma\lvert x_1\rvert$、$\lvert\sigma\rvert=1$ を満たす数($x_1=0$ なら $\sigma=1$)とし、$v:=x+\sigma\|x\|e_1$ とおくと、$H_vx=-\sigma\|x\|e_1$ であり、$v^*v=2\|x\|(\|x\|+\lvert x_1\rvert)\ge2\|x\|^2$ である。
長さをそろえれば内積の比が 1/2 になる

要点: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\|$ が保証される。

完全 QR 分解の存在

完全 QR 分解の存在

$m\ge n$ とする。任意の $A\in M_{m,n}(F)$ は完全 QR 分解 $A=QR$ をもち、$R$ の対角成分をすべて $0$ 以上の実数にとれる。$Q$ は高々 $n$ 個の Householder 変換の積と、対角のユニタリ行列の積で書ける。$F=\mathbb{R}$ なら $Q$ は実の直交行列、$R$ は実行列である。

列を 1 本ずつ鏡映で消す

$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$

一意性と Gram–Schmidt との一致

薄い QR 分解の一意性

$m\ge n$ とし、$A\in M_{m,n}(F)$ の列 $a_1,\dots,a_n$ が 1 次独立であるとする。

  1. 薄い QR 分解 $A=Q_1R_1$ の $R_1$ は、どの分解でも正則である。
  2. $R_1$ の対角成分がすべて正である薄い QR 分解は、ただ 1 つ存在する。
  3. この分解の $Q_1$ の列を $q_1,\dots,q_n$ とすると、各 $k$ で $\operatorname{span}\{q_1,\dots,q_k\}=\operatorname{span}\{a_1,\dots,a_k\}$ である。とくに $q_1,\dots,q_n$ は $A$ の像の正規直交基底であり、$Q_1Q_1^*$ は $A$ の像への直交射影である。
  4. $a_1,\dots,a_n$ に Gram–Schmidt の正規直交化を施した結果を $e_1,\dots,e_n$、途中のベクトルを $w_1,\dots,w_n$ とすると、$q_j=e_j$、$r_{jj}=\|w_j\|$、$r_{ij}=q_i^*a_j$($i< j$)である。
上三角かつユニタリなら対角行列
  1. $R_1x=0$ なら $Ax=Q_1R_1x=0$ であり、列が 1 次独立なので $x=0$ である。
  2. 存在:thm-qrd-exist の完全 QR 分解の最初の $n$ 列と $n$ 行をとると、対角成分が $0$ 以上の薄い分解が得られる。1 により $R_1$ は正則なので、対角成分は $0$ でなく、正である。
    一意性:$A=Q_1R_1=P_1S_1$ がともに対角成分の正な薄い分解であるとする。$T:=S_1R_1^{-1}$ は上三角行列で、対角成分は正である(三角行列 の定理「正則な三角行列」)。$Q_1=P_1T$ なので $I_n=Q_1^*Q_1=T^*P_1^*P_1T=T^*T$、すなわち $T^*=T^{-1}$ である。左辺は下三角、右辺は上三角なので $T$ は対角行列であり、$T^*T=I_n$ から対角成分の絶対値は $1$、正なので $1$ である。よって $T=I_n$、すなわち $S_1=R_1$、$P_1=Q_1$ である。
  3. $a_k=\sum_{i\le k}r_{ik}q_i$ から左辺は右辺を含み、どちらも $k$ 次元なので等しい。$P:=Q_1Q_1^*$ は $P^*=P$、$P^2=Q_1(Q_1^*Q_1)Q_1^*=P$ を満たす。$P$ の像は $Q_1$ の像、すなわち $A$ の像である。
  4. Gram–Schmidtの直交化 の定理「Gram–Schmidtの直交化の基本定理」により $e_1,\dots,e_n$ は正規直交系で、$a_j=\|w_j\|e_j+\sum_{i< j}\langle a_j,e_i\rangle e_i$、$\|w_j\|>0$ である。$e_j$ を列とする行列と、この係数を並べた上三角行列は、対角成分の正な薄い分解を与える。2 の一意性により、これは $Q_1,R_1$ に等しい。$\square$

列が 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 で変わらない

$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$ 成分の長さが残差である。

Gram 行列・条件数・行列式

$A$ の列が 1 次独立なとき、$\kappa_2(A):=\max_{\|x\|=1}\|Ax\|\big/\min_{\|x\|=1}\|Ax\|$ を $A$ の条件数という(正方行列なら 条件数 の Euclid ノルムの場合と同じ)。

Gram 行列・条件数・行列式との関係

$A=Q_1R_1$ を薄い QR 分解とする。

  1. $A^*A=R_1^*R_1$ である。$A$ の列が 1 次独立で $R_1$ の対角成分が正なら、$R_1^*$ は正定値行列 $A^*A$ の Cholesky分解 の因子である。
  2. $A$ の列が 1 次独立なら $\kappa_2(R_1)=\kappa_2(A)$ である。
  3. $m=n$ なら $\lvert\det A\rvert=\prod_j\lvert r_{jj}\rvert$ であり、$\lvert r_{jj}\rvert\le\|a_j\|$ である。
長さと行列式を比べる

要点:$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分解 の命題「分解と代入の演算回数」と同じ)。

QR 分解の演算回数

$A\in M_{m,n}(\mathbb{R})$ を密な行列とし、$m\ge n$ とする。演算の回数の主要項は次のとおりである。

  1. Householder 変換で $R$ を作るには $2mn^2-\frac23n^3$ 回である。$Q$ を行列として作らず、$v$ を保存して $Q^*b$ を計算するのは $4mn-2n^2$ 回である。
  2. 古典的な手順でも修正した手順でも、Gram–Schmidt の直交化で $Q_1,R_1$ を作るには $2mn^2$ 回である。
  3. Givens 回転で $R$ を作るには $3mn^2-n^3$ 回である。$m=n$ で $A$ が上 Hessenberg 行列($i>j+1$ で $a_{ij}=0$)なら、$n-1$ 回の回転で足り、$3n^2$ 回である。
段ごとに数える

要点:第 $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 の証明の手順)

  1. $k=1,\dots,\min(n,m-1)$ について次を行う。第 $k$ 列の第 $k$ 行以下を $x$ とし、第 2 成分以降がすべて $0$ なら次の $k$ へ進む。
  2. $\sigma$ を $x_1$ の偏角の因子として $v_k:=x+\sigma\|x\|e_1$、$\beta_k:=2/(v_k^*v_k)$ とする(lem-qrd-householder の 4)。
  3. 第 $k+1$ 列から第 $n$ 列までの第 $k$ 行以下の各列 $c$ を $c-\beta_kv_k(v_k^*c)$ に置き換える。$H$ の行列は作らない。
  4. $r_{kk}:=-\sigma\|x\|$ とし、第 $k$ 列の第 $k+1$ 行以下を $0$ とする。$v_k$ は別に保存する。
  5. $Ax=b$ や最小二乗問題では、$b$ に同じ順で鏡映を掛けて $Q^*b$ を作り、その最初の $n$ 成分を右辺として $R_1$ の方程式を後退代入で解く(prop-qrd-ls)。

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 の直交性の失われ方 左:Householder 変換が x を同じ長さの y へ写す鏡映。右:条件数を変えた行列で計算した Q の直交性の失われ方
右の図は、$m=50$、$n=20$、特異値が $1$ から $1/\kappa$ まで等比に並ぶ行列を倍精度で計算した結果である。縦軸の $\|I-\hat Q^*\hat Q\|_2$ は、計算した $\hat Q$ が正規直交からどれだけずれたかを表す。

例題

Householder 変換で分解して最小二乗問題を解く

$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$ が残差である。

修正 Gram–Schmidt の手順

$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$。

上 Hessenberg 行列と QR 法の 1 歩

$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–SchmidtHouseholder
$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 法

固有値の数値計算で広く使われる 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 変換の帰納法から直接組み立てた。

関連項目

参考文献

[2]
Sheldon Axler, Linear Algebra Done Right, 4th ed., Springer, 2024, 7.58(p. 264)、7.60(p. 265)、p. 266、9.66(p. 365)
[4]
Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003, §1.7(pp. 12–15、Algorithm 1.3)、§6.3.2(p. 163)、§6.5.3(pp. 174–175)、§6.5.9(p. 193)

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