Basic Linear Algebra : QR Decomposition

QR Decomposition หรืออาจเรียกว่า QR Factorization คือการแยกเมตริกซ์ M ออกสองส่วนตามสมการ

\begin{matrix} (1) & M = Q R \end{matrix}

เมื่อ

M เป็นเมตริกซ์ขนาด

n \times d

เมื่อ

n > 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} ‖}

⋮

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{aligned} M & = [m_{1} | m_{2} | m_{3} | . . . | m_{n}] \\ = [\hat{e_{1}} | \hat{e_{2}} | \hat{e_{3}} | . . . | \hat{e_{n}}] \cdot [\begin{array}{c} m_{1} \hat{e_{1}} & m_{2} \hat{e_{1}} & m_{3} \hat{e_{1}} & \dots & m_{n} \hat{e_{1}} \\ 0 & m_{2} \hat{e_{2}} & m_{3} \hat{e_{2}} & \dots & m_{n} \hat{e_{2}} \\ 0 & 0 & m_{3} \hat{e_{3}} & \dots & m_{n} \hat{e_{3}} \\ ⋮ & ⋮ & ⋮ & \dots & ⋮ \\ 0 & 0 & 0 & \dots & m_{n} \hat{e_{n}} \end{array}] \\ = Q R \end{aligned}

ตัวอย่าง

M = [\begin{matrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix}]

จะได้

m_{1} = [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}], m_{2} = [\begin{matrix} 1 \\ 0 \\ 1 \end{matrix}], m_{3} = [\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}]

คำนวณหา QR

\begin{aligned} e_{1} & = m_{1} \\ \hat{e_{1}} & = \frac{e_{1}}{‖ e_{1} ‖} = \frac{1}{\sqrt{2}} [\begin{array}{c} 1 \\ 1 \\ 0 \end{array}] \\ e_{2} & = m_{2} - (m_{2} \cdot {\hat{e}}_{1}) {\hat{e}}_{1} \\ = [\begin{array}{c} 1 \\ 0 \\ 1 \end{array}] - ([\begin{array}{c} 1 \\ 0 \\ 1 \end{array}] \cdot [\begin{array}{c} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\ 0 \end{array}]) [\begin{array}{c} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\ 0 \end{array}] \\ = [\begin{array}{c} \frac{1}{2} \\ - \frac{1}{2} \\ 1 \end{array}] \\ \hat{e_{2}} & = \frac{e_{2}}{‖ e_{2} ‖} \\ = [\begin{array}{c} \frac{1}{\sqrt{6}} \\ - \frac{1}{\sqrt{6}} \\ \frac{2}{\sqrt{6}} \end{array}] \\ e_{3} & = m_{3} - (m 3 \cdot \hat{e_{1}}) \hat{e_{1}} - (m 3 \cdot \hat{e_{2}}) \hat{e_{2}} \\ = [\begin{array}{c} 0 \\ 1 \\ 1 \end{array}] - \frac{1}{\sqrt{2}} [\begin{array}{c} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\ 0 \end{array}] - \frac{1}{\sqrt{6}} [\begin{array}{c} \frac{1}{\sqrt{6}} \\ - \frac{1}{\sqrt{6}} \\ \frac{2}{\sqrt{6}} \end{array}] \\ = [\begin{array}{c} - \frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{3}} \end{array}] \\ \hat{e_{3}} & = \frac{e_{3}}{‖ e_{3} ‖} \\ = [\begin{array}{c} - \frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{3}} \end{array}] \end{aligned}

ดังนั้น

\begin{aligned} Q & = [\begin{array}{c} \hat{e_{1}} | \hat{e_{2}} | \hat{e_{3}} \end{array}] = [\begin{array}{c} \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{array}] \\ R & = [\begin{array}{c} 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{array}] = [\begin{array}{c} \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{array}] \end{aligned}

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

Smarter Machine

ค้นหาบล็อกนี้

Basic Linear Algebra : QR Decomposition

ความคิดเห็น

แสดงความคิดเห็น