4
Một tập các véctơ [latex]u_1, \ldots, u_n[/latex] được gọi là trực giao nếu [latex]u_i^Tu_j = 0[/latex] khi [latex]i \neq j[/latex]. Hơn nữa, nếu [latex]||u_i||_2=1[/latex], chúng ta nói rằng cơ sở đó là trực chuẩn.
Ví dụ 1: Một cơ sở trực chuẩn trong [latex]\mathbb{R}^2[/latex]. Tập hợp các vector [latex]{u_1, u_2}[/latex], với [latex]\begin{align*} u_1 =\frac{1}{\sqrt{2}} \begin{pmatrix} 1 \ 1 \end{pmatrix}, \qquad & u_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \ -1 \end{pmatrix}, \end{align*}[/latex] tạo thành một cơ sở trực chuẩn của [latex]\mathbb{R}^2[/latex]. |
4.1. Trực giao hóa là gì?
Trực giao hóa là một quá trình tìm ra cơ sở trực chuẩn của không gian sinh bởi các vector cho trước.
Cho các vector [latex]a_1, \cdots, a_k \in \mathbb{R}^n[/latex], một quy trình trực giao hóa tính toán các vector [latex]q_1, \cdots, q_r \in \mathbb{R}^n[/latex] sao cho
[latex]\begin{align*} S:= \mathbf{span}\{a_1, \cdots, a_k\} = \mathbf{span}\{q_1, \cdots, q_r\}, \end{align*}[/latex]
trong đó [latex]r[/latex] là chiều của [latex]S[/latex], và
[latex]\begin{align*} q_i^Tq_j = 0 \hspace{0.05in} (i \neq j), q_i^Tq_i = 1, \hspace{0.05in} 1\leq i, j \leq r. \end{align*}[/latex]
Tức là, các vector [latex](q_1, \cdots, q_r)[/latex] tạo thành một cơ sở trực chuẩn cho không gian sinh bởi các vector [latex](a_1, \cdots, a_k)[/latex].
4.2. Phép chiếu lên một đường thẳng
Bước đầu tiên để tìm cơ sở trực giao là việc chiếu một vector lên một đường thẳng đi qua gốc tọa độ. Xét đường thẳng
[latex]\begin{align*} L(q) := {tq: t\in \mathbb{R}}, \end{align*}[/latex]
trong đó [latex]q \in \mathbb{R}^n[/latex] được cho, và đã được chuẩn hóa ([latex]||q||_2=1[/latex]).
Phép chiếu của một điểm [latex]a \in \mathbb{R}^n[/latex] cho trước lên đường thẳng là một vector [latex]v[/latex] nằm trên đường thẳng, gần nhất với [latex]a[/latex] (theo chuẩn Euclid). Điều này tương ứng với một bài toán tối ưu đơn giản:
[latex]\begin{align*} \min\limits_{t} ||a-tq||2 \end{align*}[/latex]
Vector [latex]a{proj}:= t^q[/latex], trong đó [latex]t^[/latex] là giá trị tối ưu, được gọi là phép chiếu của [latex]a[/latex] lên đường thẳng [latex]L(q)[/latex]. Như đã thấy ở đây, nghiệm của bài toán đơn giản này có một biểu thức dạng đóng:
[latex]\begin{align*} a_{\text{proj}} = (q^Ta)q. \end{align*}[/latex]
Lưu ý rằng vector [latex]a[/latex] bây giờ có thể được viết dưới dạng tổng của phép chiếu của nó và một vector khác trực giao với phép chiếu:
[latex]\begin{align*} a = (a - a_{\text{proj}}) + a_{\text{proj}} = (a - (q^Ta)q) + (q^Ta)q. \end{align*}[/latex]
trong đó [latex](a - a_{proj}) = (a - (q^Ta)q)[/latex] và [latex]a_{proj} = (q^Ta)q[/latex] là trực giao. Vector [latex](a - a_{proj})[/latex] có thể được hiểu là kết quả của việc loại bỏ thành phần của [latex]a[/latex] dọc theo [latex]q[/latex].
4.3. Thuật toán Gram-Schmidt
Thuật toán Gram-Schmidt là một thuật toán trực giao hóa lấy ý tưởng cơ bản là trực giao hóa mỗi vector đối với các vector trước đó; sau đó chuẩn hóa kết quả để có chuẩn bằng một.
Trường hợp khi các vector độc lập tuyến tính
Giả sử rằng các vector [latex]a_1, \cdots, a_n[/latex] độc lập tuyến tính. Thuật toán Gram-Schmidt được trình bày như sau.
Thuật toán Gram-Schmidt:
- đặt [latex]\tilde{q_1} = a_1[/latex].
- chuẩn hóa: đặt [latex]q_1 = \tilde{q_1}/ ||\tilde{q_1}||_2[/latex].
- loại bỏ thành phần của [latex]q_1[/latex] trong [latex]a_2[/latex]: đặt [latex]\tilde{q_2} = a_2 - (a_2^Tq_1)q_1[/latex].
- chuẩn hóa: đặt [latex]q_2 = \tilde{q_2}/ ||\tilde{q_2}||_2[/latex].
- loại bỏ các thành phần của [latex]q_1, q_2[/latex] trong [latex]a_3[/latex]: đặt [latex]\tilde{q_3} = a_3 - (a_3^Tq_1)q_1 - (a_3^Tq_2)q_2[/latex].
- chuẩn hóa: đặt [latex]q_3 = \tilde{q_3}/ ||\tilde{q_3}||_2[/latex].
- lặp lại cho [latex]a_2[/latex], …
Thuật toán Gram-Schmidt được định nghĩa tốt, vì ở mỗi bước [latex]\tilde{q_i} \neq 0[/latex] (nếu không điều này sẽ mâu thuẫn với tính độc lập tuyến tính của các [latex]a_i[/latex]).
Trường hợp tổng quát: các vector có thể phụ thuộc tuyến tính
Có thể sửa đổi thuật toán để cho phép nó xử lý trường hợp khi các [latex]a_i[/latex] không độc lập tuyến tính. Nếu ở bước [latex]i[/latex], chúng ta thấy [latex]\tilde{q_i} = 0[/latex], thì chúng ta trực tiếp nhảy đến bước tiếp theo.
Thuật toán Gram-Schmidt cải tiến:
- đặt [latex]r=0[/latex].
- cho [latex]i = 1, \cdots, n[/latex]:
- đặt [latex]\tilde{q} = a_i - \sum_{j=1}^{r}(q_j^Ta_i)q_j[/latex].
- nếu [latex]\tilde{q}\neq 0, r = r+1; q_r = \tilde{q}/||\tilde{q}||_2[/latex].
Kết thúc thuật toán, số nguyên [latex]r[/latex] chính là chiều của không gian sinh bởi các vector [latex]a_1, \cdots, a_k[/latex].