Basic Linear Algebra : LU Matrix Decomposition

หลักคิดของวิธีการนี้คือการแยกตัวประกอบ (factors) ของ square matrix A ใดๆ ให้เป็นผลของ matrix product ของ lower triangular matrix (L) และ upper triangular matrix (U) ซึ่งเป็นที่มาของชื่อ LU decomposition

$$\begin{array}{}\text{(1)}& A=L\cdot U\end{array}$$ ถ้า $A\in {\mathrm{\Re }}^{3\times 3}$ จะได้ $$\begin{array}{}\text{(2)}& \left[\begin{array}{ccc}{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{array}\right]=\left[\begin{array}{ccc}1& 0& 0\\ l_{2,1}& 1& 0\\ l_{3,1}& l_{3,2}& 1\end{array}\right]\cdot \left[\begin{array}{ccc}{u}_{1,1}& u_{1,2}& u_{1,3}\\ 0& u_{2,2}& u_{2,3}\\ 0& 0& l_{3,3}\end{array}\right]\end{array}$$

จาก (2) จะได้ค่าของ $u_{1,1},u_{1,2},u_{1,3}$ ได้ทันทีคือ $$\begin{array}{}\text{(3.1)}& u_{1,1}& =a_{1,1}\text{(3.2)}& u_{1,2}& =a_{1,2}\text{(3.3)}& u_{1,3}& =a_{1,3}\end{array}$$ และทราบว่า $$\begin{array}{}\text{(4.1)}& l_{2,1}{u}_{1,1}& =a_{2,1}\text{(4.2)}& l_{2,1}{u}_{1,2}+u_{2,2}& =a_{2,2}\text{(4.3)}& l_{2,1}{u}_{1,3}+u_{2,3}& =a_{2,3}\end{array}$$ และ $$\begin{array}{}\text{(5.1)}& l_{3,1}{u}_{1,1}& =a_{3,1}\text{(5.2)}& l_{3,1}{u}_{1,2}+l_{3,2}{u}_{2,2}& =a_{3,2}\text{(5.3)}& l_{3,1}{u}_{1,3}+l_{3,2}{u}_{2,3}+u_{3,3}& =a_{3,3}\end{array}$$ สมการ (3.1) ถึง (5.3) สามารถนำไปช่วยหา LU matrix ได้ ยกตัวอย่าง $A=\left[\begin{array}{ccc}2& 3& 2\\ 1& 3& 2\\ 3& 4& 1\end{array}\right]$

$$\left[\begin{array}{ccc}2& 3& 2\\ 1& 3& 2\\ 3& 4& 1\end{array}\right]=\left[\begin{array}{ccc}1& 0& 0\\ l_{2,1}& 1& 0\\ l_{3,1}& l_{3,2}& 1\end{array}\right]\cdot \left[\begin{array}{ccc}{u}_{1,1}& u_{1,2}& u_{1,3}\\ 0& u_{2,2}& u_{2,3}\\ 0& 0& l_{3,3}\end{array}\right]$$ $$\therefore u_{1,1}=2,u_{1,2}=3,u_{1,3}=2$$ จาก (4.1) - (4.3) $$\begin{array}{rl}{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{array}$$ จาก (5.1) - (5.3) $$\begin{array}{rl}{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{array}$$

นำมารวมกันทั้งหมดจะได้ $$\begin{array}{rl}A& =LU\\ \left[\begin{array}{ccc}2& 3& 2\\ 1& 3& 2\\ 3& 4& 1\end{array}\right]& =\left[\begin{array}{ccc}1& 0& 0\\ \frac{1}{2}& 1& 0\\ \frac{3}{2}& -\frac{1}{3}& 1\end{array}\right]\cdot \left[\begin{array}{ccc}2& 3& 2\\ 0& \frac{3}{2}& 1\\ 0& 0& -\frac{5}{3}\end{array}\right]\end{array}$$

ถ้ามีสมการ polynomial $x^2+2x+1=0$ เมื่อแยก factor จะได้รูปแบบที่ดูง่ายขึ้น $(x+1)(x+1)=0$ ผลดีที่ตามมาคือการแก้สมการง่ายขึ้น ทำนองเดียวกันกับการแยก factor ของ matrix ด้วย LU จะช่วยให้การแก้สมการ system linear equation ง่ายขึ้น ยกตัวอย่างเช่น

$$\begin{array}{rl}{x}_1+x_2+x_3& =1\\ 4x_1+3x_2-x_3& =6\\ 3x_1+5x_2+3x_3& =4\end{array}$$ นำไปเขียนในรูป linear equation $$\begin{array}{rl}A\cdot X& =Y\\ \\ \left[\begin{array}{ccc}1& 1& 1\\ 4& 3& -1\\ 3& 5& 3\end{array}\right]\cdot \left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]& =\left[\begin{array}{c}1\\ 6\\ 4\end{array}\right]\end{array}$$ decompose matrix A เป็น LU $$\begin{array}{rl}A& =\left[\begin{array}{ccc}1& 0& 0\\ 4& 1& 0\\ 3& -2& 1\end{array}\right]\cdot \left[\begin{array}{ccc}1& 1& 1\\ 0& -1& -5\\ 0& 0& -10\end{array}\right]\\ \end{array}$$ นำ $LU$ไปแทน A จะได้ $$LUX=Y$$ ถ้ากำหนดให้ $UX=V=\left[\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right]$ จะได้รูปแบบสมการใหม่เป็น $$\begin{array}{rl}LV& =Y\\ \\ \left[\begin{array}{ccc}1& 0& 0\\ 4& 1& 0\\ 3& -2& 1\end{array}\right]\cdot \left[\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right]& =\left[\begin{array}{c}1\\ 6\\ 4\end{array}\right]\\ 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{array}$$ แต่เรากำหนดไว้ $V=UX$ นั่นคือ $$\begin{array}{rl}\left[\begin{array}{ccc}1& 1& 1\\ 0& -1& -5\\ 0& 0& -10\end{array}\right]\cdot \left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]& =\left[\begin{array}{c}1\\ 2\\ 5\end{array}\right]\\ \\ \therefore x_1& =1,\\ x_2& =\frac{1}{2},\\ x_3& =-\frac{1}{2},\end{array}$$

เอกสารอ้างอิง

[1] https://en.wikipedia.org/wiki/Triangular_matrix

[2] https://youtu.be/RgnWMBpQPXk

[3] https://en.wikipedia.org/wiki/LU_decomposition