QR分解とは:シュミットの直交化法による求め方

どうも、木村(@kimu3_slime)です。

今回は、QR分解とは何か、シュミットの直交化法による求め方を紹介します。

 

QR分解とは

QR分解(QR decomposition)とは、行列\(A\)を\(A=QR\)、\(Q\)は直交行列、\(R\)は上三角行列という積の形に分解することです。

 

行列\(A\)を構成する列ベクトル\(a_1,\dots,a_n\)がすべて線形独立ならば、シュミットの直交化法によって必ずQR分解をすることができます。

まずは簡単な例で具体的にやってみましょう。

\[A= \begin{pmatrix} 0 &1\\1&1 \end{pmatrix}\]

の列ベクトルから、シュミットの直交化法によって正規直交基底\(q_1,q_2\)を作ります。\(q_1=(0,1),q_2=(1,0)\)となります。

そこで、

\[\begin{eqnarray}  Q&=&  \begin{pmatrix} q_1 &q_2 \end{pmatrix}\\& =&\begin{pmatrix} 0 &1 \\1 &0 \end{pmatrix}\end{eqnarray}\]

\[\begin{eqnarray} 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{eqnarray}\]

と置きましょう。シュミットの直交化法から、\(q_2\)は\(a_1\)と直交するように選んだことに注意。

すると、\(Q\)は直交行列、\(R\)は上三角行列です。直交行列の性質から、\(Q Q^\top =I\)なので、

\[\begin{eqnarray} QR &=&QQ^\top A \\&=& A\end{eqnarray}\]

と分解できました。

 

このアルゴリズムは一般化できます。

\(A\)の列ベクトル\(a_1,\dots,a_n\)からシュミットの直交化法で、正規直交基底\(q_1,\dots,q_n\)を作ります。そして、

\[\begin{eqnarray}  Q&=&  \begin{pmatrix} q_1 &\cdots & q_n\end{pmatrix}\end{eqnarray}\]

\[\begin{eqnarray} 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{eqnarray}\]

と置くと、\(Q\)は直交行列、\(R\)は上三角行列です。直交化法から、\(i>j\)ならば\(\langle q_i ,a_j\rangle=0\)となることに注意。

\(QQ^\top =I\)なので、

\[\begin{eqnarray} QR &=&QQ^\top A \\&=& A\end{eqnarray}\]

と分解できました。

 

QR分解の応用

行列をQR分解できると、何が嬉しいのでしょうか。

例として、最小二乗法を考えます。非正方行列\(A\)により定まる正規方程式

\[A^\top Ax =A^\top c\]

を解くことがポイントでした。一般に、サイズが大きくなると線形方程式を解くのにも時間がかかってきますが、その計算の簡略化にQR分解が役立ちます。

\(A=QR\)と分解すると、\(A^\top =R^\top Q^\top\)、\(A^\top A =R^\top Q^\top QR = R^\top R\)なので、正規方程式は

\[R^\top R x = R^\top Q^\top c\]

\[Rx = Q^\top c\]

となります。\(R\)は上三角行列なので、これを解くのはかなり簡単になり、後退代入していけば良いです。

今回はシュミットの直交化法によるQR分解を紹介しましたが、ハウスホルダー変換と呼ばれる方法を使うとより速いようです。

また、このQR分解は行列の固有値を数値的に求める手法:QR法にも応用されています。

参考:その3 固有値と固有ベクトルを数値解析で求める – ○×(まるぺけ)つくろーどっとコム

 

以上、QR分解とは何か、シュミットの直交化法による求め方を紹介してきました。

直交化法を知っていれば、理屈としては簡単だったと思います。LU分解対角化のように、行列を計算しやすい形に変形するという考え方は面白いですね。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

明解演習 線形代数 (明解演習シリーズ)
平治, 小寺(著)
共立出版 (1982-07-09T00:00:01Z)
5つ星のうち4.0
¥788 (中古品)

 

世界標準MIT教科書 ストラング:線形代数イントロダクション
ギルバート ストラング(著), 松崎 公紀(翻訳), 新妻 弘(翻訳)
近代科学社 (2015-12-22T00:00:01Z)
5つ星のうち4.6
¥14,721 (コレクター商品)

 

基礎数学1線型代数入門

基礎数学1線型代数入門

posted with AmaQuick at 2021.05.20
齋藤正彦(著)
東京大学出版会 (2019-03-08T00:00:00.000Z)
5つ星のうち4.3
¥1,870

 

こちらもおすすめ

直交ベクトルの線形独立性、正規直交基底、直交行列について解説

上三角、下三角行列の性質:積、逆行列、固有値について

シュミットの直交化法とは:正規直交基底の具体的な求め方

最小二乗法とは:最小二乗解の求め方、正規方程式、射影による理解

線形方程式の解き方:ガウスの消去法と基本変形・ランク、LU分解

行列の対角化可能性と同値な条件とは:証明、判定法