หลักคิดของวิธีการนี้คือการแยกตัวประกอบ (factors) ของ square matrix A ใดๆ ให้เป็นผลของ matrix product ของ lower triangular matrix (L) และ upper triangular matrix (U) ซึ่งเป็นที่มาของชื่อ LU decomposition
\[ A = L \cdot U \tag{1}\] ถ้า \(A \in \Re^{3 \times 3} \) จะได้ \[ \begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,1} & a_{3,2} & a_{3,3} \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ l_{2,1} & 1 & 0\\ l_{3,1} & l_{3,2} & 1 \end{bmatrix} \cdot \begin{bmatrix} u_{1,1} & u_{1,2} & u_{1,3} \\ 0 & u_{2,2} & u_{2,3}\\ 0 & 0 & l_{3,3} \end{bmatrix} \tag{2} \]
จาก (2) จะได้ค่าของ \(u_{1,1} , u_{1,2} , u_{1,3} \) ได้ทันทีคือ \[\begin{align*} u_{1,1} &= a_{1,1} \tag{3.1}\\ u_{1,2}&= a_{1,2} \tag{3.2}\\ u_{1,3}&=a_{1,3} \tag{3.3} \end{align*} \] และทราบว่า \[ \begin{align*} l_{2,1} u_{1,1} &= a_{2,1} \tag{4.1}\\ l_{2,1} u_{1,2} + u_{2,2} &= a_{2,2} \tag{4.2} \\ l_{2,1} u_{1,3} + u_{2,3} &= a_{2,3} \tag{4.3} \end{align*} \] และ \[ \begin{align*} l_{3,1} u_{1,1} &= a_{3,1} \tag{5.1}\\ l_{3,1} u_{1,2} + l_{3,2}u_{2,2} &= a_{3,2} \tag{5.2} \\ l_{3,1} u_{1,3} + l_{3,2}u_{2,3} +u_{3,3} &= a_{3,3} \tag{5.3} \end{align*} \] สมการ (3.1) ถึง (5.3) สามารถนำไปช่วยหา LU matrix ได้ ยกตัวอย่าง \( A = \begin{bmatrix}2&3&2\\1&3&2\\3&4&1\end{bmatrix}\)
\[ \begin{bmatrix}2&3&2\\1&3&2\\3&4&1\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ l_{2,1} & 1 & 0\\ l_{3,1} & l_{3,2} & 1 \end{bmatrix} \cdot \begin{bmatrix} u_{1,1} & u_{1,2} & u_{1,3} \\ 0 & u_{2,2} & u_{2,3}\\ 0 & 0 & l_{3,3} \end{bmatrix} \] \[ \therefore u_{1,1} =2 , u_{1,2} =3 , u_{1,3} =2 \] จาก (4.1) - (4.3) \[ \begin{align*} l_{2,1} (2) &= 1 \\ l_{2,1} (3) + u_{2,2} &= 3 \\ l_{2,1} (2) + u_{2,3} &= 2 \\\\ \therefore l_{2,1} &= \frac{1}{2},\\ u_{2,2} &= \frac{3}{2},\\ u_{2,3} &= 1\\ \end{align*} \] จาก (5.1) - (5.3) \[ \begin{align*} l_{3,1} (2) &= 3 \\ l_{3,1} (3) + l_{3,2}(\frac{3}{2}) &= 4 \\ l_{3,1} (2) + l_{3,2}(1) +u_{3,3} &= 1\\\\ \therefore l_{3,1} &= \frac{3}{2}, \\ l_{3,2} &= -\frac{1}{3}, \\ u_{3,3} &= -\frac{5}{3} \end{align*} \]
นำมารวมกันทั้งหมดจะได้ \[ \begin{align*} A &= LU \\ \begin{bmatrix}2&3&2\\1&3&2\\3&4&1\end{bmatrix} &= \begin{bmatrix}1&0&0 \\ \frac{1}{2}&1&0 \\ \frac{3}{2}&-\frac{1}{3}&1 \end{bmatrix} \cdot \begin{bmatrix}2&3&2 \\ 0 & \frac{3}{2} & 1 \\ 0&0&-\frac{5}{3} \end{bmatrix} \end{align*} \]
ถ้ามีสมการ polynomial \( x^2 + 2x + 1 = 0 \) เมื่อแยก factor จะได้รูปแบบที่ดูง่ายขึ้น \( (x+1)(x+1) = 0\) ผลดีที่ตามมาคือการแก้สมการง่ายขึ้น ทำนองเดียวกันกับการแยก factor ของ matrix ด้วย LU จะช่วยให้การแก้สมการ system linear equation ง่ายขึ้น ยกตัวอย่างเช่น
\[ \begin{align*} x_1 + x_2+x_3 &= 1\\ 4x_1+3x_2-x_3 &= 6 \\ 3x_1+5x_2+3x_3&=4 \end{align*} \] นำไปเขียนในรูป linear equation \[ \begin{align*} A \cdot X &= Y \\\\ \begin{bmatrix} 1 & 1 & 1\\ 4 & 3 &-1\\ 3 & 5 & 3 \end{bmatrix} \cdot \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} &= \begin{bmatrix} 1\\ 6\\ 4 \end{bmatrix} \end{align*} \] decompose matrix A เป็น LU \[ \begin{align*} A &= \begin{bmatrix}1&0&0\\4&1&0\\3&-2&1 \end{bmatrix} \cdot \begin{bmatrix}1&1&1\\0&-1&-5\\0&0&-10 \end{bmatrix} \\\\ \end{align*} \] นำ \(LU \)ไปแทน A จะได้ \[ LUX = Y \\ \] ถ้ากำหนดให้ \( UX = V = \begin{bmatrix} v_1\\v_2\\v_3\end{bmatrix}\) จะได้รูปแบบสมการใหม่เป็น \[ \begin{align*} LV & = Y \\\\ \begin{bmatrix}1&0&0\\4&1&0\\3&-2&1 \end{bmatrix} \cdot \begin{bmatrix} v_1\\v_2\\v_3\end{bmatrix} &= \begin{bmatrix} 1\\ 6\\ 4 \end{bmatrix} \\ v_1 &= 1\\ 4v_1 +v_2 &= 6\\ 3v_1-2v_2+v_3 &=4 \\ \therefore v_1 &= 1,\\ v_2 &= 2,\\ v_3&= 5 \end{align*} \] แต่เรากำหนดไว้ \( V = UX\) นั่นคือ \[ \begin{align*} \begin{bmatrix}1&1&1\\0&-1&-5\\0&0&-10 \end{bmatrix} \cdot \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} & = \begin{bmatrix} 1\\ 2\\ 5 \end{bmatrix}\\\\ \therefore x_1 &= 1,\\ x_2 &= \frac{1}{2},\\ x_3 &= -\frac{1}{2},\\ \end{align*} \\ \]
เอกสารอ้างอิง
[1] https://en.wikipedia.org/wiki/Triangular_matrix
[2] https://youtu.be/RgnWMBpQPXk
[3] https://en.wikipedia.org/wiki/LU_decomposition
ความคิดเห็น
แสดงความคิดเห็น