Phép phân tích ma trận A=LU

Phép phân tích ma trận (hay Matrix Decomposition) là một phương pháp nhân tử hóa ma trận bằng cách tách ma trận đó ra thành phép nhân của nhiều ma trận khác nhau. Cũng giống như với một số tự nhiên, ta có thể tách số đó ra thành các nhân tử khác nhau như tách ra thành các thừa số nguyên tố để dễ dàng nhận biết được đặc điểm của con số ấy. Thì nhân tử hóa ma trận cũng được xây trên khái niệm tương tự. Phép phân tích ma trận đơn giản nhất là $A=LU$.

Trong đó:

• $A$ là một ma trận bất kỳ.
• $L$ là ma trận tam giác dưới. (L là viết tắt của Lower trong Lower Triangle).
• $U$ là ma trận tam giác trên. (U là viết tắt của Upper trong Upper Triangle).

$A = LU$

Phép phân tích ma trận này rất đơn giản, đầu tiên ta thực hiện các phép biến đổi trên dòng để đưa A thành một ma trận bậc thang. Lúc đó, ma trận bậc thang chính là U. Tôi sẽ lấy một ma trận có kích thước 3x3 để làm ví dụ. $$A = \begin{bmatrix} 1 & 5 & 2 \\ 3 & 6 & 4 \\ -2 & 2 & 7 \end{bmatrix}$$
Đầu tiên, ta cần tính toán hệ số $l$ để nhân dòng 1 rồi trừ cho dòng 2 để thực hiện loại trừ (elimination). Có thể tính được $l = \frac{A_21}{A_11} = \frac{3}{1} = 3$. Chúng ta gọi hệ số này là $l_21$. Vậy phép biến đổi dòng đầu tiên là $r_2 - l_21.r_1 = r_2 - 3.r_1$. Tương tự, ta cũng tính ra được $l_31 = \frac{A_31}{A_11}= -2$ và phép biến đổi dòng thứ hai là $r_3 - l_31.r_1 = r_3 + 2.r_1$.
Đến đây, ta có một ký hiệu chung $l_ij$ là hệ số nhân cho dòng j và trừ cho dòng i.
$$ \begin{bmatrix} 1 & 5 & 2 \\ 3 & 6 & 4 \\ -2 & 2 & 7 \end{bmatrix} \begin{aligned} &\xrightarrow{r_2-3r_1}\\ &\xrightarrow{r_3 +2r_2 } \end{aligned} \begin{bmatrix} 1 & 5 & 2 \\ 0 & -9 & -2 \\ 0 & 12 & 11 \end{bmatrix} $$
Tiếp tục bước loại trừ, ta có $l_32 = \frac{12}{-9} = -\frac{4}{3}$.
$$ \begin{bmatrix} 1 & 5 & 2 \\ 0 & -9 & -2 \\ 0 & 12 & 11 \end{bmatrix} \xrightarrow{r_3 + \frac{4}{3} r_2} \begin{bmatrix} 1 & 5 & 2 \\ 0 & -9 & -2 \\ 0 & 0 & \frac{25}{3} \end{bmatrix} $$
Vậy, ma trận U của ta có kết quả:
$$U= \begin{bmatrix} 1 & 5 & 2 \\ 0 & -9 & -2 \\ 0 & 0 & \frac{25}{3} \end{bmatrix}$$
Bây giờ ta cần tìm một ma trận $L$ sao cho $A = LU$ $$\begin{bmatrix} 1 & 5 & 2 \\ 3 & 6 & 4 \\ -2 & 2 & 7 \end{bmatrix} = L \begin{bmatrix} 1 & 5 & 2 \\ 0 & -9 & -2 \\ 0 & 0 & \frac{25}{3} \end{bmatrix}$$
Các bạn có thể tìm $U^{-1}$ để kiếm $L$ bằng phương trình $L = A U^{-1}$. Nhưng điều đó là không cần thiết vì thật ra ma trận $L$ của ta chính là: $$\begin{equation} \begin{split} L &= \begin{bmatrix} 1 & 0 & 0 \\ l_21 & 1 & 0 \\ l_31 & l_32 & 1 \end{bmatrix} \\ &= \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & -\frac{4}{3} &1 \end{bmatrix} \end{split} \end{equation}$$
Nếu bạn nghi ngờ giả thuyết của tôi, sao chúng ta không kiểm tra thử nhỉ.
$$LU = \begin{bmatrix} \vert & \vert & \vert \\ a_1 & a_2 & a_3 \\ \vert & \vert & \vert \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & -\frac{4}{3} &1 \end{bmatrix} \begin{bmatrix} 1 & 5 & 2 \\ 0 & -9 & -2 \\ 0 & 0 & \frac{25}{3} \end{bmatrix}$$
Ta tính cột đầu tiên $a_1$:
$$\begin{equation} \begin{split} \begin{bmatrix} \vert \\ a_1\\ \vert \end{bmatrix} &= \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & -\frac{4}{3} &1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}\\ &= 1\begin{bmatrix} 1 \\ 3 \\ -2 \end{bmatrix} + 0\begin{bmatrix} 0 \\ 1 \\ -\frac{4}{3} \end{bmatrix} + 0\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}\\ &= \begin{bmatrix} 1 \\ 3 \\ -2 \end{bmatrix} \end{split} \end{equation}$$
Cột $a_2$:
$$\begin{equation} \begin{split} \begin{bmatrix} \vert \\ a_2\\ \vert \end{bmatrix} &= \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & -\frac{4}{3} &1 \end{bmatrix} \begin{bmatrix} 5 \\ -9 \\ 0 \end{bmatrix}\\ &= 5\begin{bmatrix} 1 \\ 3 \\ -2 \end{bmatrix} - 9\begin{bmatrix} 0 \\ 1 \\ -\frac{4}{3} \end{bmatrix} + 0\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}\\ &= \begin{bmatrix} 5 \\ 6 \\ 2 \end{bmatrix} \end{split} \end{equation}$$
Cột $a_3$:
$$\begin{equation} \begin{split} \begin{bmatrix} \vert \\ a_3\\ \vert \end{bmatrix} &= \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & -\frac{4}{3} &1 \end{bmatrix} \begin{bmatrix} 2 \\ -2 \\ \frac{25}{3} \end{bmatrix}\\ &= 2\begin{bmatrix} 1 \\ 3 \\ -2 \end{bmatrix} - 2\begin{bmatrix} 0 \\ 1 \\ -\frac{4}{3} \end{bmatrix} + \frac{25}{3}\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}\\ &= \begin{bmatrix} 2 \\ 4 \\ 7 \end{bmatrix} \end{split} \end{equation}$$
Vậy : $$LU = \begin{bmatrix} 1 & 5 & 2 \\ 3 & 6 & 4 \\ -2 & 2 & 7 \end{bmatrix} = A$$
Thật ra đây không phải là đoán mò. Nếu chúng ta sử dụng một cách giải thích khác về phép nhân ma trận: $$\begin{equation} \begin{split} &\begin{bmatrix} c_1 & c_2 & c_3 \end{bmatrix} \begin{bmatrix} -& a_1^T &-\\ - & a_2^T & -\\ - & a_3^T & - \end{bmatrix} \\ = & c_1\begin{bmatrix} - & a_1^T & - \end{bmatrix} + c_2\begin{bmatrix} -& a_2^T &- \end{bmatrix} + c_3\begin{bmatrix} - & a_3^T & - \end{bmatrix} \end{split} \end{equation}$$
Thì thật ra những phần tử trong mỗi dòng của $L$ đang giúp ta đảo lại các phép toán trên dòng mà ta đã làm. Ví dụ với dòng 2 của ma trận U có được từ việc trừ đi $l_21.r_1$ thì ở dòng 2 của ma trận L ta đã khôi phục lại như sau:
$$\begin{equation} \begin{split} &\begin{bmatrix} l_21 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 5 & 2 \\ 0 & -9 & -2 \\ 0 & 0 & \frac{25}{3}\end{bmatrix} \\ = & l_21 \begin{bmatrix}1 & 5 & 2 \end{bmatrix}+ \begin{bmatrix}0 & -9 & -2\end{bmatrix} \end{split} \end{equation}$$
Ta đã lấy dòng 2 của $U$ (tức kết quả cuối cùng sau khi loại trừ) và cộng thêm vào dòng 1 để lấy lại dòng 2 ban đầu. Đối với dòng 3 cũng tương tự. Vậy, ta luôn có thể tính nhanh $L$ bằng cách giữ lại các $l_ij$ và xếp chúng vào các vị trí tương ứng.
$$L = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ l_21 & 1 & \cdots & 0 \\ \vdots &&\ddots & \\ l_{m1} & l_{m2} &\cdots &1 \end{bmatrix}$$

$A = LDU$ và $A = LDL^T$

Tuy nhiên, các ma trận tam giác sẽ đúng chuẩn hơn khi trên đường chéo của chúng chỉ là 1. Ma trận $U$ mà ta đã kiếm được ở trên do vậy cần một chút điều chỉnh nhỏ.
$$\begin{bmatrix} 1 & 5 & 2 \\ 0 & -9 & -2 \\ 0 & 0 & \frac{25}{3} \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & -9 & 0 \\ 0 & 0 & \frac{25}{3} \end{bmatrix} \begin{bmatrix} 1 & 5 & 2 \\ 0 & 1 & \frac{2}{9} \\ 0 & 0 & 1 \end{bmatrix} = DU$$
Vậy, nếu phân tích theo phương pháp $$A = LDU$$ ta sẽ được: $$\begin{equation} \begin{split} A &= LDU\\ &=\begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & -\frac{4}{3} &1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & -9 & 0 \\ 0 & 0 & \frac{25}{3} \end{bmatrix} \begin{bmatrix} 1 & 5 & 2 \\ 0 & 1 & \frac{2}{9} \\ 0 & 0 & 1 \end{bmatrix} \end{split} \end{equation}$$
Phép phân tích này rất có lợi khi ta muốn tìm các phần tử cơ sở (pivot variable) sau khi rút gọn ma trận.
Một sự thật thú vị là nếu $A$ là một ma trận đối xứng. Lúc này phép phân tích trên sẽ trở thành $A = LDL^T$. Vì tính chất của ma trận đối xứng, ta có: $$A^T = A \tag{1}$$ Mà $$ \begin{equation} \begin{split} A^T &= (LDU)^T\\ &=U^TDL^T \end{split} \end{equation}\tag{2}$$ Từ (1) và (2), ta có: $$U^TDL^T = LDU$$ Việc này chỉ xảy ra khi $L = U^T \Rightarrow U=L^T$

$PA = LU$

Đôi khi chúng ta cần phải thay đổi các dòng với nhau mới có thể thực hiện loại trừ. Trong trường hợp đó ta không thể sử dụng cách phân tích $A=LU$ đã nói trên được vì $LU$ bây giờ là kết quả của phép phân tích trên ma trận $A$ đã được đổi dòng (tạm gọi là $A^'$). Lúc này ta phải sử dụng thêm một ma trận $P$ để thực hiện các phép hoán đổi dòng trên $A$. Lúc này: $$A^' = LU \Leftrightarrow PA = LU$$