QR 分解とは｜グラム・シュミットとハウスホルダー変換

行列を直交行列 $Q$ と上三角行列 $R$ の積に書き直すのが QR 分解です。

$$A=QR$$

$Q$ の列は正規直交系なので、長さも角度も変えません。$R$ は上三角なので、方程式は後退代入だけで解けます。

作り方は 2 通りあります。列を順に正規直交化していくグラム・シュミット法と、鏡映を重ねて成分を消していくハウスホルダー法です。

<svg viewBox="0 0 460 220" width="100%" style="max-width:460px;display:block;margin:0 auto">
	<text x="230" y="20" font-size="11" fill="#9a9a9a" text-anchor="middle">列を順に正規直交化すると、そのまま Q と R が出ます</text>
	<line x1="140" y1="175" x2="280" y2="105" stroke="#9a9a9a" stroke-width="1"></line>
	<polygon points="284,103 274,101 277,109" fill="#9a9a9a"></polygon>
	<line x1="140" y1="175" x2="215" y2="45" stroke="#9a9a9a" stroke-width="1"></line>
	<polygon points="217,41 210,49 219,51" fill="#9a9a9a"></polygon>
	<line x1="140" y1="175" x2="210" y2="140" stroke="#1b81e0" stroke-width="2"></line>
	<polygon points="214,138 204,136 207,144" fill="#1b81e0"></polygon>
	<line x1="140" y1="175" x2="118" y2="130" stroke="#1b81e0" stroke-width="2"></line>
	<polygon points="116,126 113,136 122,133" fill="#1b81e0"></polygon>
	<line x1="215" y1="45" x2="252" y2="119" stroke="#c8c8c8" stroke-width="1" stroke-dasharray="3 3"></line>
	<circle cx="140" cy="175" r="2.5" fill="#1f1f1f"></circle>
	<text x="292" y="102" font-size="12" fill="#9a9a9a">a1</text>
	<text x="219" y="38" font-size="12" fill="#9a9a9a">a2</text>
	<text x="214" y="158" font-size="12" fill="#1b81e0">q1</text>
	<text x="96" y="124" font-size="12" fill="#1b81e0">q2</text>
	<text x="262" y="128" font-size="11" fill="#9a9a9a">a1 方向の成分を引く</text>
	<text x="230" y="208" font-size="11" fill="#9a9a9a" text-anchor="middle">引いた量が R の成分、残った向きが Q の列になります</text>
</svg>

QR 分解とは

$m\times n$ の実行列 $A$ に対して、列が正規直交系である $Q$ と、上三角行列 $R$ を見つけて $A=QR$ と書くことを QR 分解といいます。

正方行列なら $Q$ は直交行列で、$Q^{\top }Q=Q{Q}^{\top }=I$ を満たします。転置がそのまま逆行列になる、扱いやすい行列です。

LU 分解が消去の記録だったのに対して、QR 分解は正規直交化の記録です。同じ「三角行列に落とす」でも、途中で使う変換の種類が違います。

縦長の行列では縮小版を使う

$m>n$ の縦長の行列では、$Q$ の取り方に 2 通りあります。

完全版では $Q$ を $m\times m$ の直交行列にします。このとき $R$ は $m\times n$ で、下の $m-n$ 行はすべて $0$ です。

縮小版では $Q_1$ を $m\times n$、$R_1$ を $n\times n$ に取ります。余分な零行を持たないぶん、計算にも記憶にも無駄がありません。

縮小版の $Q_1$ は $Q_1^{\top }{Q}_1=I_n$ を満たしますが、$Q_1{Q}_1^{\top }$ は単位行列になりません。こちらは列空間への射影行列です。

グラム・シュミットで作る

$A$ の列を $a_1,\dots ,a_n$ とします。第 1 列は正規化するだけです。

$$q_1=\frac{a_1}{\Vert a_1\Vert }$$

第 $j$ 列からは、すでに作った $q_1,\dots ,q_{j-1}$ の方向の成分を引き、残りを正規化します。

$$v_j=a_j-\sum _{i<j}⟨q_i,a_j⟩q_i,q_j=\frac{v_j}{\Vert v_j\Vert }$$

このとき $a_j$ は $q_1,\dots ,q_j$ だけで書けます。係数を集めた行列が上三角になるのは、そのためです。

$R$ の成分は内積そのもので、$r_{ij}=⟨q_i,a_j⟩$、対角は $r_{jj}=\Vert v_j\Vert$ です。新しい量を計算しているわけではありません。

例：2 次の行列をグラム・シュミットで分解する

次の行列を分解します。

$$A=\left(\begin{array}{cc}3& 1\\ 4& 7\end{array}\right)$$

第 1 列は $(3,4)$ で長さが $5$ です。$q_1=(3/5,4/5)$、$r_{11}=5$ になります。

第 2 列 $(1,7)$ との内積は $r_{12}=3/5+28/5=31/5$ です。この分を引きます。

$$v_2=(1,7)-\frac{31}{5}\left(\frac{3}{5},\frac{4}{5}\right)=\left(-\frac{68}{25},\frac{51}{25}\right)$$

$\Vert v_2\Vert =17/5$ なので $q_2=(-4/5,3/5)$、$r_{22}=17/5$ です。並べると分解ができあがります。

$$Q=\left(\begin{array}{cc}\frac{3}{5}& -\frac{4}{5}\\ \frac{4}{5}& \frac{3}{5}\end{array}\right),R=\left(\begin{array}{cc}5& \frac{31}{5}\\ 0& \frac{17}{5}\end{array}\right)$$

この $Q$ は行列式が $1$ で、回転を表します。

分解が一通りに決まる条件

$A$ の列が一次独立なら、$R$ の対角成分を正に取るという約束のもとで分解は一意です。

約束がなければ自由が残ります。$q_j$ の符号を反転し、同時に $R$ の第 $j$ 行の符号も反転すれば、別の分解ができるからです。

列が一次従属だと $v_j=0$ が起き、$R$ の対角に $0$ が現れます。このときは一意性も崩れます。

ハウスホルダー変換は鏡映である

$0$ でないベクトル $v$ に対して、次の行列をハウスホルダー行列といいます。

$$H=I-\frac{2v{v}^{\top }}{v^{\top }v}$$

これは $v$ に垂直な超平面に関する鏡映です。$v$ 方向の成分だけが符号を変え、垂直な成分はそのまま残ります。

$x$ を $\Vert x\Vert e_1$ に写したいなら、$v=x-\Vert x\Vert e_1$ と取ります。$x$ と行き先の差が、そのまま鏡の向きになります。

<svg viewBox="0 0 460 220" width="100%" style="max-width:460px;display:block;margin:0 auto">
	<text x="230" y="20" font-size="11" fill="#9a9a9a" text-anchor="middle">鏡で折り返すと、第 1 成分だけが残ります</text>
	<line x1="69" y1="190" x2="266" y2="92" stroke="#9a9a9a" stroke-width="1" stroke-dasharray="4 3"></line>
	<line x1="150" y1="150" x2="290" y2="150" stroke="#e5e5e5" stroke-width="1"></line>
	<line x1="150" y1="150" x2="222" y2="54" stroke="#1b81e0" stroke-width="2"></line>
	<polygon points="225,50 216,54 223,60" fill="#1b81e0"></polygon>
	<line x1="150" y1="150" x2="264" y2="150" stroke="#1b81e0" stroke-width="2"></line>
	<polygon points="270,150 260,146 260,154" fill="#1b81e0"></polygon>
	<line x1="270" y1="150" x2="226" y2="62" stroke="#1f1f1f" stroke-width="1"></line>
	<polygon points="223,56 223,66 231,61" fill="#1f1f1f"></polygon>
	<circle cx="150" cy="150" r="2.5" fill="#1f1f1f"></circle>
	<text x="232" y="48" font-size="12" fill="#1b81e0">x</text>
	<text x="276" y="166" font-size="12" fill="#1b81e0">Hx</text>
	<text x="256" y="102" font-size="12" fill="#1f1f1f">v</text>
	<text x="80" y="182" font-size="11" fill="#9a9a9a">鏡（v に垂直）</text>
	<text x="230" y="210" font-size="11" fill="#9a9a9a" text-anchor="middle">長さは変わらないので、行き先は必ず x と同じ長さになります</text>
</svg>

ハウスホルダー行列の性質

定義から直ちに $H^{\top }=H$ が分かります。$v{v}^{\top }$ が対称だからです。

直交性も計算すれば出ます。$H^{\top }H=H^2=I$ となり、2 回かければもとに戻ります。鏡映を 2 回するのだから当然です。

固有値は $1$ が $n-1$ 個と $-1$ が 1 個で、行列式は $-1$ です。向きを裏返す変換であることが、この符号に表れています。

例：同じ行列をハウスホルダー変換で分解する

さきほどの $A$ の第 1 列 $(3,4)$ を $(5,0)$ に写します。$v=(3,4)-(5,0)=(-2,4)$ です。

$v^{\top }v=20$ を使って $H$ を組み立てます。

$$H=I-\frac{2}{20}\left(\begin{array}{cc}4& -8\\ -8& 16\end{array}\right)=\left(\begin{array}{cc}\frac{3}{5}& \frac{4}{5}\\ \frac{4}{5}& -\frac{3}{5}\end{array}\right)$$

$H$ を $A$ に掛けると、第 1 列の下が消えて上三角になります。

$$HA=\left(\begin{array}{cc}5& \frac{31}{5}\\ 0& -\frac{17}{5}\end{array}\right)$$

$H$ は 2 回かけると単位行列に戻るので、$A=H(HA)$ です。つまり $Q=H$、$R=HA$ が分解になります。

2 つの答が食い違って見える理由

グラム・シュミットでは $R$ の対角が $5$ と $17/5$、ハウスホルダーでは $5$ と $-17/5$ になりました。

食い違いは符号だけです。$Q$ の第 2 列と $R$ の第 2 行の符号を同時に変えれば、一方から他方へ移ります。積は変わりません。

行列式を見ると違いがはっきりします。グラム・シュミットの $Q$ は $\det Q=1$ の回転、ハウスホルダーの $Q$ は $\det Q=-1$ の鏡映です。

どちらも正しい分解です。対角を正にそろえたければ、符号を調整すれば済みます。

符号の選び方と桁落ち

$v=x-\Vert x\Vert e_1$ は、$x$ がもともと $e_1$ に近い向きだと引き算で桁が落ちます。差がほとんど $0$ になるからです。

そこで実際の計算では、$x$ の第 1 成分と同じ符号を使って $v=x+\mathrm{sign}(x_1)\Vert x\Vert e_1$ と取ります。

行き先が $-\Vert x\Vert e_1$ に変わるだけで、鏡映であることは変わりません。数値計算では、こちらが標準です。

大きな行列では鏡映を繰り返す

1 回目の鏡映で第 1 列の 2 行目以下が消えます。2 回目は右下の小さい行列に対して同じことをします。

第 1 行と第 1 列に触らない形で鏡映を組めば、消した成分が復活することはありません。$n-1$ 回（縦長なら $n$ 回）で上三角になります。

$Q$ は使った鏡映の積です。方程式を解くだけなら $Q$ を陽に組み立てず、鏡映を順に作用させれば足ります。

1 成分ずつ消すギブンス回転という方法もあります。手数は増えますが、消したい成分が少ない疎な行列や、並列計算では有利です。

グラム・シュミットは数値的に弱い

古典的なグラム・シュミット法は、丸め誤差で直交性が崩れていきます。後ろの列ほど誤差が積もり、$Q$ の列が直交から外れます。

引く順序を変えた修正グラム・シュミット法を使うと、誤差の出方がずっとおとなしくなります。厳密な計算では同じ式ですが、有限桁では違います。

ハウスホルダー法はどの段階も直交変換なので、誤差が拡大しません。数値計算で QR 分解といえば、ふつうこちらを指します。

連立方程式を解く

$Ax=b$ に $A=QR$ を入れると $QRx=b$ です。両辺に $Q^{\top }$ を掛けます。

$$Rx=Q^{\top }b$$

$Q$ の逆行列は転置なので、逆行列を求める手間がありません。あとは後退代入だけで解けます。

例：QR 分解で連立方程式を解く

さきほどの $A$ に対して、右辺を $b=(5,18)$ とします。グラム・シュミットで求めた $Q$ を使います。

$Q^{\top }b$ を計算すると $(87/5,34/5)$ です。

後退代入に移ります。第 2 式は $\frac{17}{5}{x}_2=\frac{34}{5}$ なので $x_2=2$ です。

第 1 式は $5x_1+\frac{31}{5}\cdot 2=\frac{87}{5}$ となり、$x_1=1$ が出ます。$Ax$ を計算すると $(5,18)$ に戻ります。

最小二乗法とのつながり

行が列より多い過剰決定系では、$Ax=b$ をぴったり満たす $x$ はふつう存在しません。かわりに $\Vert Ax-b\Vert$ を最小にする $x$ を探します。

直交行列は長さを変えないので、$\Vert Ax-b\Vert =\Vert Q^{\top }(Ax-b)\Vert$ が成り立ちます。この右辺を書き下すと、上の $n$ 行だけが $x$ に依存します。

したがって $R_{1}x=Q_1^{\top }b$ を解けば最小になります。正規方程式を作る方法より、数値の面で有利です。詳しい議論は直交補空間と直交分解定理の記事にあります。

行列式は R の対角の積

$\det Q$ は $\pm 1$ なので、行列式は $R$ の対角から求まります。

$$|\det A|=|r_{11}{r}_{22}\cdots r_{nn}|$$

さきほどの例で確かめます。グラム・シュミットでは $\det Q=1$、対角の積が $5\times \frac{17}{5}=17$ です。

ハウスホルダーでは $\det Q=-1$、対角の積が $-17$ なので、掛け合わせるとやはり $17$ になります。符号の付き方が違うだけで、結果は一致します。

計算量と LU 分解の比較

ハウスホルダー法による QR 分解は $4n^3/3$ 回程度の演算で終わります。LU 分解の $2n^3/3$ に対して、およそ 2 倍です。

倍のコストを払う理由は安定性です。直交変換は長さを変えないので、途中で値が暴れず、誤差も拡大しません。

正方の連立方程式を素早く解きたいなら LU 分解が有利です。最小二乗法や固有値計算のように、精度が問われる場面では QR 分解を選びます。

他の話題とのつながり

固有値を求める QR 法は、この分解を繰り返し使います。$A=QR$ と分解して $RQ$ を作る操作は $Q^{\top }AQ$ と同じで、相似変換を重ねながら上三角に近づけていきます。

グラム・シュミット法そのものは、正規直交基底を作る手続きです。QR 分解は、その過程を行列の積として書き留めたものにあたります。

$Q$ の性質はユニタリ行列と直交行列の記事に、正規直交基底の意味は正規直交基底の記事にあります。特異値分解でも、前処理として QR 分解が使われます。

よくある誤り

参考文献