どうも、木村（@kimu3_slime）です。
今回は、QR分解とは何か、シュミットの直交化法による求め方を紹介します。
QR分解とは
QR分解（QR decomposition）とは、行列\(A\)を\(A=QR\)、\(Q\)は直交行列、\(R\)は上三角行列という積の形に分解することです。
行列\(A\)を構成する列ベクトル\(a_1,\dots,a_n\)がすべて線形独立ならば、シュミットの直交化法によって必ずQR分解をすることができます。
まずは簡単な例で具体的にやってみましょう。
\[ \begin{aligned}A= \begin{pmatrix} 0 &1\\1&1 \end{pmatrix}\end{aligned} \]
の列ベクトルから、シュミットの直交化法によって正規直交基底\(q_1,q_2\)を作ります。\(q_1=(0,1),q_2=(1,0)\)となります。
そこで、
\[ \begin{aligned} Q&= \begin{pmatrix} q_1 &q_2 \end{pmatrix}\\&= \begin{pmatrix} 0 &1 \\1 &0 \end{pmatrix}\end{aligned} \]
\[ \begin{aligned} R&=Q^\top A\\&= \begin{pmatrix} q_1^\top \\q_2^\top \end{pmatrix} \begin{pmatrix} a_1 &a_2 \end{pmatrix}\\ &= \begin{pmatrix} \langle q_1,a_1\rangle & \langle q_1,a_2 \rangle \\ \langle q_2,a_1\rangle& \langle q_2,a_2\rangle \end{pmatrix}\\&= \begin{pmatrix} \langle q_1,a_1\rangle & \langle q_1,a_2 \rangle \\ 0& \langle q_2,a_2\rangle \end{pmatrix}\\&= \begin{pmatrix} 1 &1 \\0 &1 \end{pmatrix} \end{aligned} \]
と置きましょう。シュミットの直交化法から、\(q_2\)は\(a_1\)と直交するように選んだことに注意。
すると、\(Q\)は直交行列、\(R\)は上三角行列です。直交行列の性質から、\(Q Q^\top =I\)なので、
\[ \begin{aligned} QR &=QQ^\top A \\&= A\end{aligned} \]
と分解できました。
このアルゴリズムは一般化できます。
\(A\)の列ベクトル\(a_1,\dots,a_n\)からシュミットの直交化法で、正規直交基底\(q_1,\dots,q_n\)を作ります。そして、
\[ \begin{aligned} Q&= \begin{pmatrix} q_1 &\cdots & q_n\end{pmatrix}\end{aligned} \]
\[ \begin{aligned} R&=Q^\top A\\&= \begin{pmatrix} q_1^\top \\\vdots \\ q_n^\top \end{pmatrix} \begin{pmatrix} a_1 &\cdots & a_n\end{pmatrix}\\ &= \begin{pmatrix} \langle q_1,a_1\rangle & \langle q_1,a_2 \rangle &\cdots & \langle q_1,a_n \rangle \\ \langle q_2,a_1\rangle& \langle q_2,a_2\rangle& \cdots & \langle q_2,a_n \rangle \\ \vdots &&\vdots \\ \langle q_n,a_1\rangle& \langle q_n,a_2\rangle& \cdots & \langle q_n,a_n \rangle \end{pmatrix} \\ &= \begin{pmatrix} \langle q_1,a_1\rangle & \langle q_1,a_2 \rangle &\cdots & \langle q_1,a_n \rangle \\ 0& \langle q_2,a_2\rangle& \cdots & \langle q_2,a_n \rangle \\ \vdots &&\vdots \\ 0& 0& \cdots & \langle q_n,a_n \rangle \end{pmatrix}\end{aligned} \]
と置くと、\(Q\)は直交行列、\(R\)は上三角行列です。直交化法から、\(i>j\)ならば\(\langle q_i ,a_j\rangle=0\)となることに注意。
\(QQ^\top =I\)なので、
\[ \begin{aligned} QR &=QQ^\top A \\&= A\end{aligned} \]
と分解できました。
QR分解の応用
行列をQR分解できると、何が嬉しいのでしょうか。
例として、最小二乗法を考えます。非正方行列\(A\)により定まる正規方程式
\[ \begin{aligned}A^\top Ax =A^\top c\end{aligned} \]
を解くことがポイントでした。一般に、サイズが大きくなると線形方程式を解くのにも時間がかかってきますが、その計算の簡略化にQR分解が役立ちます。
\(A=QR\)と分解すると、\(A^\top =R^\top Q^\top\)、\(A^\top A =R^\top Q^\top QR = R^\top R\)なので、正規方程式は
\[ \begin{aligned}R^\top R x = R^\top Q^\top c\end{aligned} \]
\[ \begin{aligned}Rx = Q^\top c\end{aligned} \]
となります。\(R\)は上三角行列なので、これを解くのはかなり簡単になり、後退代入していけば良いです。
今回はシュミットの直交化法によるQR分解を紹介しましたが、ハウスホルダー変換と呼ばれる方法を使うとより速いようです。
また、このQR分解は行列の固有値を数値的に求める手法：QR法にも応用されています。
参考：その３ 固有値と固有ベクトルを数値解析で求める – ○×（まるぺけ）つくろーどっとコム
以上、QR分解とは何か、シュミットの直交化法による求め方を紹介してきました。
直交化法を知っていれば、理屈としては簡単だったと思います。LU分解や対角化のように、行列を計算しやすい形に変形するという考え方は面白いですね。
木村すらいむ（@kimu3_slime）でした。ではでは。
共立出版 (1982-07-09T00:00:01Z)
￥788 (中古品)
世界標準MIT教科書 ストラング:線形代数イントロダクション
近代科学社 (2015-12-22T00:00:01Z)
￥14,721 (コレクター商品)
東京大学出版会 (2019-03-08T00:00:00.000Z)
￥1,870
こちらもおすすめ
直交ベクトルの線形独立性、正規直交基底、直交行列について解説
最小二乗法とは：最小二乗解の求め方、正規方程式、射影による理解
線形方程式の解き方：ガウスの消去法と基本変形・ランク、LU分解
