QR Decomposition หรืออาจเรียกว่า QR Factorization คือการแยกเมตริกซ์ M ออกสองส่วนตามสมการ
\[ M = QR \tag{1} \]
เมื่อ
M เป็นเมตริกซ์ขนาด \( n \times d \) เมื่อ \( n \gt d \)
Q เป็น orthogonal matrix
R เป็น upper triangular matrix
มีหลาย algorithm ที่ใช้หา QR แต่ในข้อเขียนนี้จะใช้ algorithm เรียกว่า Gram-Shmidt process
Algorithm
การทำงานของ Gram-Shmidt จะต้องทั้งหมด n ขั้นตอน เมื่อ n คือจำนวน column vectors ของเมตริกซ์ M
\[
M = [ \, m_1 | m_2 | m_3 | ... | m_n ] \,
\]
เมื่อ \( m_n \) คือ column vector ของ M ขั้นตอนการทำงานคือ
1. ให้ \( e_1 = m_1 \) และคำนวณ \( \hat{e}_1 = \frac{e_1}{\| e_1\|} \)
2. ให้ \( e_2 = m_2 - (m_2 \cdot \hat{e}_1)\hat{e}_1 \) และคำนวณ \( \hat{e}_2 = \frac{e_2}{\| e_2\|} \)
3. ให้ \( e_3 = m_3 - (m_3 \cdot \hat{e}_1)\hat{e}_1 - (m_3 \cdot \hat{e}_2)\hat{e}_2 \) และคำนวณ \( \hat{e}_3 = \frac{e_3}{\| e_3\|} \)
\( \vdots \)
n. ให้ \( e_n = m_n - (m_n \cdot \hat{e}_1)\hat{e}_1 - (m_n \cdot \hat{e}_2)\hat{e}_2 ... (m_n \cdot \hat{e}_{n-1}) \hat{e}_{n-1}\) และคำนวณ \( \hat{e}_n = \frac{e_n}{\| e_n\|} \)
สุดท้ายแล้วจะได้
\[
\begin{align*}
M &= [ m_1 | m_2 | m_3 | ... | m_n ] \\\\
&= [ \, \hat{e_1} | \hat{e_2} | \hat{e_3} | ... | \hat{e_n} ] \, \cdot
\begin{bmatrix}
m_1\hat{e_1} & m_2\hat{e_1} & m_3\hat{e_1} & \cdots & m_n\hat{e_1} \\
0 & m_2\hat{e_2} & m_3\hat{e_2} & \cdots & m_n\hat{e_2} \\
0 & 0 & m_3\hat{e_3} & \cdots & m_n\hat{e_3} \\
\vdots & \vdots & \vdots & \cdots & \vdots \\
0 & 0 & 0 & \cdots & m_n\hat{e_n} \\
\end{bmatrix} \\\\
&= QR
\end{align*}
\]
ตัวอย่าง
\( M = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} \)
จะได้
\( m_1 = \begin{bmatrix} 1\\1\\0 \end{bmatrix} ,
m_2 = \begin{bmatrix} 1\\0\\1 \end{bmatrix} ,
m_3 = \begin{bmatrix} 0\\1\\1 \end{bmatrix} \)
คำนวณหา QR
\[
\begin{align*}
e_1 &= m_1 \\
\hat{e_1} &= \frac{e_1}{\|e_1 \|} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1\\1\\0 \end{bmatrix} \\\\
e_2 &= m_2 - (m_2 \cdot \hat{e}_1)\hat{e}_1 \\
&= \begin{bmatrix} 1\\0\\1 \end{bmatrix} - (\begin{bmatrix} 1\\0\\1 \end{bmatrix} \cdot
\begin{bmatrix}
\frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}}\\0
\end{bmatrix} )
\begin{bmatrix}
\frac{1}{\sqrt{2}}\\
\frac{1}{\sqrt{2}}\\
0
\end{bmatrix}\\\\
&= \begin{bmatrix}
\frac{1}{2}\\
-\frac{1}{2}\\
1
\end{bmatrix}\\\\
\hat{e_2} &= \frac{e_2}{\|e_2 \|} \\\\
&= \begin{bmatrix}
\frac{1}{\sqrt{6}} \\
-\frac{1}{\sqrt{6}} \\
\frac{2}{\sqrt{6}}
\end{bmatrix} \\\\
e_3 &= m_3 - (m3 \cdot \hat{e_1})\hat{e_1} - (m3 \cdot \hat{e_2})\hat{e_2} \\
&= \begin{bmatrix}
0\\1\\1
\end{bmatrix} -
\frac{1}{\sqrt{2}}
\begin{bmatrix}
\frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}} \\0
\end{bmatrix} -
\frac{1}{\sqrt{6}}
\begin{bmatrix}
\frac{1}{\sqrt{6}} \\
-\frac{1}{\sqrt{6}} \\
\frac{2}{\sqrt{6}}
\end{bmatrix} \\\\
&= \begin{bmatrix}
-\frac{1}{\sqrt{3}} \\
\frac{1}{\sqrt{3}} \\
\frac{1}{\sqrt{3}}
\end{bmatrix}\\\\
\hat{e_3} &= \frac{e_3}{\|e_3 \|} \\
&= \begin{bmatrix}
-\frac{1}{\sqrt{3}} \\
\frac{1}{\sqrt{3}} \\
\frac{1}{\sqrt{3}}
\end{bmatrix}\\\\
\end{align*}
\]
ดังนั้น
\[
\begin{align*}
Q &= \begin{bmatrix}
\hat{e_1} | \hat{e_2} | \hat{e_3}
\end{bmatrix} =
\begin{bmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{3}} \\
\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{6}} & \frac{1}{\sqrt{3}} \\
0 & \frac{2}{\sqrt{6}} & \frac{1}{\sqrt{3}}
\end{bmatrix} \\\\
R &= \begin{bmatrix}
m_1\hat{e_1} & m_2\hat{e_1} & m_3\hat{e_1} \\
0 & m_2\hat{e_2} & m_3\hat{e_2} \\
0 & 0 & m_3\hat{e_3}
\end{bmatrix} =
\begin{bmatrix}
\frac{2}{\sqrt{2}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\
0 & \frac{3}{\sqrt{6}} & \frac{1}{\sqrt{6}} \\
0 & 0 & \frac{2}{\sqrt{3}}
\end{bmatrix}
\end{align*}
\]
Python implementation
การหา QR ด้วยภาษา Python มีหลายทางได้แก่ numpy.linalg.qr, scipy.linalg.qr หรือ sympy.Matrix
Numpy /Scipy :
import numpy as np
M = np.array([[1,1,0],[1,0,1],[0,1,1]])
Q,R = np.linalg.qr(M)
Sympy :
from sympy import Matrix
from sympy.interactive.printing import init_printing
init_printing(use_unicode=False, wrap_line=False)
# create sympy matrix from numpy matrix
X = Matrix(M)
# print Q and R matrix
X.QRdecomposition()
เอกสารอ้างอิง
[1] https://en.wikipedia.org/wiki/QR_decomposition
[2] https://smarter-machine.blogspot.com/2021/03/basic-linear-algebra-orthogonal-matrix.html
[3] https://smarter-machine.blogspot.com/2021/03/basic-linear-algebra-lu-matrix.html
[4] https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process#Numerical_stability
ความคิดเห็น
แสดงความคิดเห็น