20.1. Ý tưởng cơ bản: đưa về hệ phương trình tam giác

Xét bài toán giải một hệ phương trình tuyến tính [latex]Ax = y[/latex], trong đó [latex]A \in \mathbb{R}^{m \times n}[/latex] và [latex]y \in \mathbb{R}^m[/latex] cho trước.

Ý tưởng cơ bản trong thuật toán giải bắt đầu với nhận xét rằng trong trường hợp đặc biệt khi [latex]A[/latex] là ma trận tam giác trên, tức là [latex]A_{ij} = 0[/latex] nếu [latex]i > j[/latex], thì hệ có thể được giải dễ dàng bằng một quá trình được gọi là \textbf{phép thế ngược}. Trong phép thế ngược, ta chỉ cần bắt đầu giải hệ bằng cách khử biến cuối cùng trước, sau đó tiến hành giải ngược lên. Quá trình này được minh họa trong ví dụ này, và được mô tả tổng quát tại đây.

20.2. Phân tích QR của một ma trận

Phân tích QR cho phép biểu diễn một ma trận [latex]m \times n[/latex] [latex]A[/latex] bất kỳ thành tích [latex]A = QR[/latex], trong đó [latex]Q[/latex] có cỡ [latex]m \times m[/latex] và trực giao (tức là, [latex]Q^TQ = I_m[/latex]) và [latex]R[/latex] là một ma trận tam giác trên cỡ [latex]m \times n[/latex]. Để biết thêm chi tiết về điều này, xem tại đây.

Một khi đã có phân tích QR của [latex]A[/latex], ta có thể giải hệ bằng cách nhân trước cả hai vế của phương trình với [latex]Q^T[/latex]:

[latex]\begin{align*} QRx = y \iff Rx = Q^Ty. \end{align*}[/latex]

Điều này là do [latex]Q^TQ = I_m[/latex]. Hệ mới [latex]Rx = Q^Ty[/latex] là một hệ tam giác và có thể được giải bằng \textbf{phép thế ngược}. Ví dụ, nếu [latex]A[/latex] có hạng cột đầy đủ, thì [latex]R[/latex] khả nghịch, do đó nghiệm là duy nhất, và được cho bởi [latex]x = R^{-1}Q^Ty.[/latex].

20.3. Sử dụng phân tích QR đầy đủ

Ta bắt đầu với \textbf{phân tích QR đầy đủ} của A với các hoán vị cột:

[latex]\begin{align*}  AP = QR = \begin{pmatrix} Q_1 & Q_2 \end{pmatrix} \begin{pmatrix} R_1 & R_2 \\ 0 & 0 \end{pmatrix} \end{align*}[/latex]

trong đó

• \item [latex]Q = [Q_1, Q_2][/latex] có cỡ [latex]m \times m[/latex] và trực giao ([latex]Q^TQ = I_m[/latex]);
• \item [latex]Q_1[/latex] có cỡ [latex]m \times r[/latex], với các cột trực chuẩn ([latex]Q_1^TQ_1 = I_r[/latex]);
• \item [latex]Q_2[/latex] có cỡ [latex]m \times (m-r)[/latex], với các cột trực chuẩn ([latex]Q_2^TQ_2 = I_{m-r}[/latex]);
• \item [latex]r[/latex] là \textbf{hạng} của [latex]A[/latex]; \item [latex]R_1[/latex] có cỡ [latex]r \times r[/latex], là ma trận tam giác trên, và khả nghịch;
• \item [latex]R_2[/latex] là một ma trận cỡ [latex]r \times (n - r)[/latex];
• \item [latex]P[/latex] là một ma trận hoán vị cỡ [latex]n \times n[/latex] (do đó, [latex]P^T = P^{-1}[/latex]).

Sử dụng [latex]A = QRP^T[/latex], ta có thể viết [latex]Rz = Q^Ty[/latex], trong đó [latex]z := P^Tx[/latex]. Ta hãy xem xét phương trình theo [latex]z[/latex] ở dạng khai triển:

[latex]\begin{align*} \begin{pmatrix} R_1 & R_2 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} z_1 \\ z_2 \end{pmatrix} = \begin{pmatrix} Q_1^Ty \\ Q_2^Ty \end{pmatrix}. \end{align*}[/latex]

Ta thấy rằng nếu [latex]Q_2^Ty \neq 0[/latex] thì không có nghiệm. Ta giả sử rằng [latex]Q_2^Ty = 0[/latex]. Khi đó ta có

[latex]\begin{align*} R_1z_1 + R_2z_2 = Q_1^Ty, \end{align*}[/latex]

đây là một hệ gồm [latex]r[/latex] phương trình tuyến tính với [latex]n[/latex] biến.

Một nghiệm cụ thể có được khi đặt [latex]z_2 = 0[/latex], dẫn đến một hệ tam giác theo [latex]z_1[/latex], với một ma trận tam giác khả nghịch [latex]R_1[/latex]. Do đó [latex]z_1 = R_1^{-1}Q_1^Ty[/latex], tương ứng với một nghiệm cụ thể [latex]x_0[/latex] của [latex]Ax = y[/latex]:

[latex]\begin{align*} x_0 := P\begin{pmatrix} R_1^{-1}Q_1^Ty\\ 0. \end{pmatrix} \end{align*}[/latex]

20.4. Tập nghiệm

Ta cũng có thể tạo ra tất cả các nghiệm, bằng cách lưu ý rằng [latex]z_2[/latex] là một biến tự do. Ta có

[latex]\begin{align*} x = P \begin{pmatrix} z_1 \\ z_2 \end{pmatrix} = P \begin{pmatrix} R_1^{-1}(Q_1^Ty - R_2z_2)\\ z_2 \end{pmatrix} = x_0 + Lz_2, \end{align*}[/latex]

trong đó

[latex]\begin{align*} L := P\begin{pmatrix} -R_1^{-1}R_2\\ I_{n-r} \end{pmatrix}. \end{align*}[/latex]

Tập nghiệm là một tập hợp afin [latex]\[ x_0 + \textbf{ảnh}(L) \][/latex].