12
12.1 Ý tưởng ban đầu
Mục tiêu cơ bản của phân tích QR là phân tích một ma trận thành tích của hai ma trận.
Phân tích QR thực ra chính là sử dụng thuật toán Gram-Schmidt cho các cột của ma trận và kết quả được biểu diễn ở dạng ma trận. Xét một ma trận [latex]A=(a_1, \ldots ,a_n)[/latex] kích thước [latex]m\times n[/latex], với mỗi [latex]a_i \in R^m[/latex] là một cột của [latex]A[/latex].
12.2 Trường hợp các cột độc lập tuyến tính
Giả sử [latex]a_1, \ldots ,a_n[/latex] (các cột của [latex]A[/latex]) là độc lập tuyến tính. Mỗi bước của thuật toán Gram-Schmidt có thể được viết là:
\[ a_i=\left(a_i^T q_1\right) q_1+\ldots+\left(a_i^T q_{i-1}\right) q_{i-1}+\left\|\tilde{q}_i\right\|_2 q_i, \quad i=1, \ldots, n \]
Chúng ta viết lại chúng thành: \[ a_i=r_{i 1} q_1+\ldots+r_{i, i-1} q_{i-1}+r_{i i} q_i, \quad i=1, \ldots, n, \] trong đó [latex]r_{ij}=(a_i^Tq_j) (1 \geq j \geq i-1)[/latex] và [latex]r_{ii}=||\tilde{q}_{ii}||_2[/latex].
Vì các [latex]q_i[/latex] là có độ dài đơn vị và được chuẩn hóa, ma trận [latex]Q=(q_1,\ldots,q_n)[/latex] thỏa mãn [latex]Q^TQ=I_n[/latex]. Phân tích QR của một ma trận [latex]m\times n[/latex] là [latex]A[/latex] do đó cho phép viết ma trận ở dạng đã phân tích:
\[ A=Q R, \quad Q=\left(\begin{array}{lll} q_1 & \ldots & q_n \end{array}\right), \quad R=\left(\begin{array}{cccc} r_{11} & r_{12} & \cdots & r_{1 n} \\ 0 & r_{22} & & r_{2 n} \\ \vdots & & \ddots & \vdots \\ 0 & & 0 & r_{n n} \end{array}\right) \]
trong đó [latex]Q[/latex] là ma trận [latex]m\times n[/latex] với [latex]Q^T Q=I_n[/latex], và [latex]R[/latex] là ma trận tam giác trên [latex]n\times n[/latex].
Ví dụ: Phân tích QR của một ma trận 4×6.
12.3 Trường hợp các cột không độc lập
Khi các cột của [latex]A[/latex] không độc lập, ở một bước nào đó của thuật toán Gram-Schmidt, chúng ta gặp một vectơ không [latex]\tilde{q}_j[/latex], có nghĩa là [latex]a_j[/latex] là một tổ hợp tuyến tính của [latex]a_{j-1},\ldots,a_i[/latex]. Thuật toán Gram-Schmidt cải tiến bỏ qua vectơ không và tiếp tục.
Ở dạng ma trận, chúng ta thu được
[latex]A=Q R[/latex], với [latex]Q \in \mathbb{R}^{m \times r}[/latex], [latex]r=\mathbf{rank}(A)[/latex], và [latex]R[/latex]
có dạng bậc thang, ví dụ:
\[ R=\left(\begin{array}{cccccc} * & * & * & * & * & *\\ 0 & 0 & * & * & * & * \\ 0 & 0 & 0 & 0 & * & * \end{array}\right). \]
(Đây đơn giản chỉ là một ma trận tam giác trên với một số hàng bị xóa. Nó vẫn là ma trận tam giác trên.) Chúng ta có thể hoán vị các cột của [latex]R[/latex] để đưa lên phía trước các phần tử khác không đầu tiên trong mỗi hàng:
\[R=\left( R_1 \mid R_2 \right) P^T,\quad \left( R_1 \mid R_2 \right):=\left(\begin{array}{ccc|ccc} * & * & * & * & * & *\\ 0 & * & 0 & * & * & * \\ 0 & 0 & * & 0 & 0 & * \end{array}\right) \]
trong đó [latex]P[/latex] là một ma trận hoán vị (tức là, các cột của nó là các vectơ đơn vị theo một thứ tự nào đó), có tác dụng hoán vị các cột. (Vì [latex]P[/latex] là trực giao, nghĩa là [latex]P^{-1}=P^T[/latex]). Bây giờ, [latex]R_1[/latex] là ma trận tam giác trên, và khả nghịch, vì không có phần tử nào trên đường chéo của nó bằng không. Phân tích QR có thể được viết là:
\[ AP = Q \left( \begin{array}{c|c} R_1 & R_2 \end{array} \right) \]
trong đó [latex]Q \in \mathbb{R}^{m \times r}, Q^T Q=I_r ;[/latex] [latex]r[/latex] là hạng của [latex]A[/latex]; [latex]R_1[/latex] là ma trận tam giác trên kích thước [latex]r \times r[/latex], khả nghịch; [latex]R_2[/latex] là ma trận [latex]r \times (n-r)[/latex]; [latex]P[/latex] là một ma trận hoán vị [latex]m \times m[/latex].
12.4 Phân tích QR đầy đủ
Phân tích QR đầy đủ cho phép viết [latex]A=QR[/latex] trong đó [latex]Q \in \mathbb{R}^{m \times m}[/latex] là vuông và trực giao ([latex]Q^TQ=QQ^T=I_m[/latex]). Nói cách khác, các cột của [latex]Q[/latex] là một cơ sở trực chuẩn cho toàn bộ không gian đầu ra [latex]R^m[/latex].
Chúng ta thu được phân tích đầy đủ bằng cách thêm một ma trận đơn vị [latex]m \times m[/latex] vào các cột của [latex]A[/latex]: [latex]A \to [A,I_m][/latex]. Phân tích QR của ma trận tăng cường cho phép viết:
\[ A P=Q R=\left(\begin{array}{ll} Q_1 & Q_2 \end{array}\right)\left(\begin{array}{cc} R_1 & R_2 \\ 0 & 0 \end{array}\right) . \]
trong đó các cột của ma trận [latex]m \times m[/latex] là [latex]Q=[Q_1,Q_2][/latex] là trực giao và [latex]R_1[/latex] là tam giác trên và khả nghịch. (Như trước, [latex]P[/latex] là ma trận hoán vị.) Trong thủ tục G-S, các cột của [latex]Q_1[/latex] được lấy từ các cột của [latex]A[/latex], trong khi các cột của [latex]Q_2[/latex] đến từ các cột bổ sung được thêm vào [latex]A[/latex].
Phân tích QR đầy đủ cho thấy hạng của [latex]A[/latex]: chúng ta chỉ cần xem các phần tử trên đường chéo của [latex]R[/latex] mà khác không, tức là kích thước của [latex]R_1[/latex].
