Bài giảng 13: Thuật toán Phân rã LU

(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é! )

Giả sử ma trận $A$ có thể được biến đổi thành dạng bậc thang $U$ chỉ bằng các phép thay thế hàng, trong đó một hàng được cộng với bội số của một hàng khác nằm bên dưới nó. Trong trường hợp này, tồn tại các ma trận đơn vị tam giác dưới sơ cấp $E_1,\dots,E_p$ sao cho:

(3) $\begin{equation*}E_p\cdots E_1 A=U\end{equation*}$

Khi đó,

$A=(E_p\cdots E_1)^{-1}U=LU$

với

(4) $\begin{equation*}L=(E_p\cdots E_1)^{-1}\end{equation*}$

Có thể chứng minh rằng tích và nghịch đảo của các ma trận đơn vị tam giác dưới cũng là ma trận đơn vị tam giác dưới. Do đó, $L$ là một ma trận tam giác dưới đơn vị.

Lưu ý rằng các phép biến đổi hàng trong phương trình (3), biến đổi $A$ thành $U$ , cũng biến đổi $L$ trong phương trình (4) thành ma trận đơn vị $I$ , vì $E_p\cdots E_1 L=(E_p\cdots E_1)(E_p\cdots E_1)^{-1}=I$ . Quan sát này là chìa khóa để xây dựng ma trận $L$ .

Thuật toán phân rã LU

1. Biến đổi A thành dạng bậc thang U bằng một chuỗi phép thay thế hàng, nếu có thể.
2. Điền các phần tử vào L sao cho cùng một chuỗi phép biến đổi hàng có thể biến L thành I.

Bước 1 không phải lúc nào cũng thực hiện được, nhưng khi có thể, lập luận trên chứng minh rằng phân rã LU tồn tại. Ví dụ sau sẽ minh họa cách thực hiện bước 2. Theo cách xây dựng, $L$ sẽ thỏa mãn:

$(E_p\cdots E_1)L=I$

với cùng các $E_1,\dots,E_p$ như trong phương trình (3). Do đó, $L$ là khả nghịch theo Định lý Ma trận Khả nghịch, với $(E_p\cdots E_1)=L^{-1}$ .

Từ phương trình (3), ta có $L^{-1}A=U$ , suy ra $A=LU$ . Như vậy, bước 2 sẽ tạo ra một ma trận $L$ phù hợp.

Ví dụ: Tìm phân rã LU của

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

Giải: Vì $A$ có bốn hàng, nên $L$ sẽ có kích thước $4\times 4$ . Cột đầu tiên của $L$ chính là cột đầu tiên của $A$ chia cho phần tử trục (pivot) trên cùng.

$L=\begin{bmatrix}1&0&0&0\\-2&1&0&0\\1&&1&0\\-3&&&1\\\end{bmatrix}$

Hãy so sánh cột đầu tiên của $A$ và $L$ . Các phép biến đổi hàng tạo ra các số 0 trong cột đầu tiên của $A$ cũng sẽ tạo ra các số 0 trong cột đầu tiên của $L$ . Để đảm bảo các phép biến đổi hàng trên $A$ cũng áp dụng được cho $L$ , hãy quan sát quá trình biến đổi hàng của $A$ thành dạng bậc thang $U$ . Nghĩa là, cần làm nổi bật các phần tử trong từng ma trận, những phần tử này xác định trình tự các phép biến đổi hàng biến đổi $A$ thành $U$ .

Các phần tử được làm nổi bật này xác định cách biến đổi hàng của $A$ thành $U$ . Ở mỗi cột trục, ta chia các phần tử được làm nổi bật cho phần tử trục và đặt kết quả vào $L$ .

và $L=\begin{bmatrix}1&0&0&0\\-2&1&0&0\\1&-3&1&0\\-3&4&2&1\\\end{bmatrix}$

Một phép tính đơn giản xác nhận rằng $L$ và $U$ thỏa mãn $LU=A$ .

Trong thực tế, hoán đổi hàng gần như luôn cần thiết, vì phép chọn trục từng phần (partial pivoting) được sử dụng để tăng độ chính xác. (Nhắc lại rằng phương pháp này chọn phần tử có giá trị tuyệt đối lớn nhất trong cột làm trục.) Để xử lý hoán đổi hàng, phân rã LU trên có thể được điều chỉnh dễ dàng để tạo ra một $L$ có dạng tam giác dưới hoán vị, nghĩa là có thể sắp xếp lại các hàng của $L$ sao cho $L$ trở thành ma trận tam giác dưới đơn vị.

Phân rã LU có hoán vị vẫn giải hệ phương trình $A\mathbf{x}=\mathbf{b}$ theo cách như trước, ngoại trừ việc phép khử $\begin{bmatrix}L&\mathbf{b}\\\end{bmatrix}$ thành $\begin{bmatrix}I&\mathbf{y}\\\end{bmatrix}$ phải tuân theo thứ tự trục của $L$ từ trái sang phải, bắt đầu từ trục trong cột đầu tiên. Khi nhắc đến “phân rã LU”, người ta thường bao gồm cả khả năng $L$ là tam giác dưới hoán vị.

Ghi chú số học

Các tính toán sau áp dụng cho ma trận vuông $n\times n$ có hầu hết các phần tử khác 0, với $n$ đủ lớn, chẳng hạn $n\geq 30$ .

Tính phân rã LU của $A$ cần khoảng ${2n^3}/{3}$ phép toán (flops), tương đương với phép khử Gauss trên $\begin{bmatrix}A&\mathbf{b}\\\end{bmatrix}$ , trong khi tính nghịch đảo của $A$ cần khoảng $2n^3$ phép toán.
Giải hệ phương trình $L\mathbf{y}=\mathbf{b}$ và $U\mathbf{x}=\mathbf{y}$ cần khoảng $2n^2$ phép toán, vì hệ tam giác có thể được giải trong khoảng $n^2$ phép toán.
Nhân $\mathbf{b}$ với $A^{-1}$ cũng cần khoảng $2n^2$ phép toán, nhưng kết quả có thể kém chính xác hơn so với việc sử dụng $L$ và $U$ , do lỗi làm tròn khi tính cả $A^{-1}$ và $A^{-1}\mathbf{b}$ .
Nếu $A$ là ma trận thưa (hầu hết phần tử bằng 0), thì $L$ và $U$ cũng có thể thưa, trong khi $A^{-1}$ có xu hướng trở thành ma trận đặc. Trong trường hợp này, việc giải hệ $A\mathbf{x}=\mathbf{b}$ bằng phân rã LU nhanh hơn nhiều so với sử dụng $A^{-1}$ .