Bài giảng 12: Phân rã ma trận

(Nếu công thức chưa load được hoặc mờ, các bạn ấn refresh để công thức hiện và rõ nét hơn nhé! )

Phân rã một ma trận $A$ là một phương trình biểu diễn $A$ dưới dạng tích của hai hoặc nhiều ma trận. Trong khi phép nhân ma trận là một quá trình tổng hợp dữ liệu (kết hợp tác động của hai hoặc nhiều phép biến đổi tuyến tính thành một ma trận duy nhất), thì phân rã ma trận lại là một quá trình phân tích dữ liệu.

Trong ngôn ngữ khoa học máy tính, biểu diễn $A$ dưới dạng tích của các ma trận tương đương với việc tiền xử lý dữ liệu trong $A$ , sắp xếp dữ liệu đó thành hai hoặc nhiều phần có cấu trúc hữu ích hơn theo một cách nào đó, có thể giúp tính toán dễ dàng hơn.

Phân rã ma trận và sau này là phân rã các phép biến đổi tuyến tính sẽ xuất hiện tại nhiều điểm quan trọng trong cuốn sách này. Phần này tập trung vào một phương pháp phân rã đóng vai trò cốt lõi trong nhiều chương trình máy tính quan trọng, được ứng dụng rộng rãi, chẳng hạn như bài toán dòng khí được đề cập trong phần mở đầu chương.

Phân rã LU

Phân rã LU, được mô tả dưới đây, xuất phát từ một bài toán phổ biến trong công nghiệp và kinh doanh: giải một dãy phương trình có cùng ma trận hệ số:

(1) $\begin{equation*}A\mathbf{x}=\mathbf{b_{1}},\quad A\mathbf{x}=\mathbf{b_{2}},\quad...,A\mathbf{x}=\mathbf{b_{p}}\end{equation*}$

Khi $A$ khả nghịch, ta có thể tính $A^{-1}$ rồi nhân với $A^{-1}\mathbf{b}_1,\,A^{-1}\mathbf{b}_2,...$ để tìm nghiệm. Tuy nhiên, một cách hiệu quả hơn là giải phương trình đầu tiên trong dãy trên bằng phương pháp khử Gauss và đồng thời thu được phân rã LU của $A$ . Sau đó, các phương trình còn lại có thể được giải nhanh chóng bằng phân rã LU.

Trước tiên, giả sử $A$ là một ma trận $m\times n$ có thể khử về dạng bậc thang mà không cần hoán đổi hàng. Khi đó, $A$ có thể được viết dưới dạng $A=LU$ , trong đó $L$ là ma trận tam giác dưới $m\times m$ có đường chéo chính toàn số 1, còn $U$ là một ma trận $m\times n$ ở dạng bậc thang của $A$ . Một phân rã như vậy được gọi là phân rã LU của $A$ . Ma trận $L$ là khả nghịch và được gọi là ma trận tam giác dưới đơn vị.

Trước khi tìm hiểu cách xây dựng $L$ và $U$ , ta nên xem xét lý do tại sao chúng quan trọng. Khi $A=LU$ , phương trình $A\mathbf{x}=\mathbf{b}$ có thể được viết lại thành $L(U\mathbf{x})=\mathbf{b}$ . Gọi $\mathbf{y}=U\mathbf{x}$ , ta có thể tìm $\mathbf{x}$ bằng cách giải lần lượt hai phương trình:

(2) $\begin{equation*}\begin{aligned}\begin{matrix}L\mathbf{y}&=\mathbf{b}\\U\mathbf{x}&=\mathbf{y}\\\end{matrix}\end{aligned}\end{equation*}$

Giải $L\mathbf{y}=\mathbf{b}$ để tìm $\mathbf{y}$ .
Giải $U\mathbf{x}=\mathbf{y}$ để tìm $\mathbf{x}$ .

Xem hình 2. Mỗi phương trình trên đều dễ giải vì $L$ và $U$ là ma trận tam giác.

Hình 2: Phân rã ánh xạ $\mathbf{x}\mapsto A\mathbf{x}$

Ví dụ 1: Có thể xác minh rằng

$A=\begin{bmatrix}3&-7&-2&2\\-3&5&1&0\\6&-4&0&-5\\-9&5&-5&12\\\end{bmatrix}=\begin{bmatrix}1&0&0&0\\-1&1&0&0\\2&-5&1&0\\-3&8&3&1\\\end{bmatrix}\begin{bmatrix}3&-7&-2&2\\0&-2&-1&2\\0&0&-1&1\\0&0&0&-1\\\end{bmatrix}=LU$

Sử dụng phân rã này để giải $A\mathbf{x}=\mathbf{b}$ , với $\mathbf{b}=\begin{bmatrix}-9\\5\\7\\11\end{bmatrix}$ .

Giải: Giải $L\mathbf{y}=\mathbf{b}$ chỉ cần 6 phép nhân và 6 phép cộng, vì các phép toán chỉ diễn ra trong một cột nhất định. (Các số 0 dưới mỗi phần tử trục chính của $L$ được tạo ra tự động do cách chọn phép biến đổi hàng.)

$\begin{bmatrix}L&\mathbf{b}\\\end{bmatrix}=\begin{bmatrix}1&0&0&0&-9\\-1&1&0&0&5\\2&-5&1&0&7\\-3&8&3&1&11\\\end{bmatrix}\sim\begin{bmatrix}1&0&0&0&-9\\0&1&0&0&-4\\0&0&1&0&5\\0&0&0&1&1\\\end{bmatrix}=\begin{bmatrix}I&\mathbf{y}\\\end{bmatrix}$

Sau đó, giải $U\mathbf{x}=\mathbf{y}$ cần: 4 phép chia, 6 phép nhân, 6 phép cộng

Chẳng hạn, để tạo số 0 trong cột thứ tư của $\begin{bmatrix}U&\mathbf{y}\\\end{bmatrix}$ , ta cần 1 phép chia và 3 cặp phép nhân – cộng để trừ bội số của hàng 4 khỏi các hàng trên.

$\begin{bmatrix}U&\mathbf{y}\\\end{bmatrix}=\begin{bmatrix}3&-7&-2&2&-9\\0&-2&-1&2&-4\\0&0&-1&1&5\\0&0&0&-1&1\\\end{bmatrix}\sim\begin{bmatrix}1&0&0&0&3\\0&1&0&0&4\\0&0&1&0&-6\\0&0&0&1&-1\\\end{bmatrix},\quad\mathbf{x}=\begin{bmatrix}3\\4\\-6\\-1\end{bmatrix}$

Tổng cộng, việc tìm $\mathbf{x}$ đòi hỏi 28 phép toán số thực (flops), chưa tính đến chi phí tìm $L$ và $U$ . Trong khi đó, nếu thực hiện khử Gauss trực tiếp trên hệ mở rộng $\begin{bmatrix}A&\mathbf{b}\\\end{bmatrix}$ để đưa về dạng $\begin{bmatrix}I&\mathbf{x}\\\end{bmatrix}$ , ta cần đến 62 phép toán.

Hiệu suất tính toán của phân rã LU phụ thuộc vào việc có sẵn $L$ và $U$ . Thuật toán tiếp theo cho thấy rằng việc khử hàng của $A$ thành dạng bậc thang $U$ thực chất chính là quá trình tạo phân rã LU, vì nó đồng thời sinh ra $L$ mà không cần làm thêm nhiều bước tính toán. Sau lần khử hàng đầu tiên, $L$ và $U$ đã sẵn sàng để giải quyết các phương trình bổ sung có cùng ma trận hệ số $A$ .

Phân rã LU

Để lại một bình luận Hủy

Chịu trách nhiệm nội dung

Bản quyền

Ý kiến bạn đọc

Bài giảng 12: Phân rã ma trận

Lesson Attachments

Phân rã LU

Để lại một bình luận Hủy