Bài giảng 11: Bài toán Bình phương nhỏ nhất

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

Trong thực tế, các hệ phương trình không tương thích thường xuất hiện. Khi cần tìm nghiệm nhưng không có nghiệm chính xác, cách tốt nhất là tìm một $\mathbf{x}$ sao cho $A\mathbf{x}$ gần với $\mathbf{b}$ nhất có thể.

Hãy xem $A\mathbf{x}$ như một xấp xỉ của $\mathbf{b}$ . Khoảng cách giữa $\mathbf{b}$ và $A\mathbf{x}$ , được đo bằng $\|\mathbf{b}-A\mathbf{x}\|$ , càng nhỏ thì xấp xỉ càng tốt. Bài toán bình phương nhỏ nhất tổng quát là tìm một $\mathbf{x}$ sao cho $\|\mathbf{b}-A\mathbf{x}\|$ nhỏ nhất có thể. Thuật ngữ “bình phương nhỏ nhất” xuất phát từ việc $\|\mathbf{b}-A\mathbf{x}\|$ chính là căn bậc hai của tổng các bình phương.

Định nghĩa

Nếu  là ma trận  và  thuộc , thì một nghiệm bình phương nhỏ nhất của phương trình  là một  trong  sao cho:
.

Điểm quan trọng nhất trong bài toán bình phương nhỏ nhất là: dù chọn $\mathbf{x}$ như thế nào, vector $A\mathbf{x}$ luôn thuộc vào không gian cột ( $\text{Col A}$ ) của $A$ . Do đó, ta cần tìm $\mathbf{x}$ sao cho $A\mathbf{x}$ là điểm gần nhất trong không gian cột của $A$ với $\mathbf{b}$ . Xem hình 1 để trực quan hóa khái niệm này. (Tất nhiên, nếu $\mathbf{b}$ nằm trong $\text{Col A}$ , thì $\mathbf{b}$ có thể được biểu diễn dưới dạng $A\mathbf{x}$ cho một số $\mathbf{x}$ , và khi đó $\mathbf{x}$ chính là một nghiệm bình phương nhỏ nhất.)

Giải Bài toán Bình phương Nhỏ nhất Tổng quát

Giải Bài toán Bình phương Nhỏ nhất Tổng quát Cho ma trận $A$ và vector $\mathbf{b}$ như đã đề cập, ta áp dụng định lý xấp xỉ tốt nhất vào không gian con $\text{Col A}$ . Gọi:

$\mathbf{\hat{b}}=\text{proj}_{\text{Col}A}\mathbf{b}$

Hình 1: Vector $\mathbf{b}$ gần $A\mathbf{\hat{x}}$ hơn so với $A\mathbf{x}$ cho các giá trị khác của $\mathbf{x}$ .

Vì $\mathbf{\hat{b}}$ thuộc vào không gian cột của $A$ , phương trình $A\mathbf{x}=\hat{\mathbf{b}}$ luôn có nghiệm. Do đó, tồn tại một vector $\hat{\mathbf{x}}\in\mathbb{R}^n$ sao cho:

(1) $\begin{equation*}A\mathbf{\hat{x}}=\mathbf{\hat{b}}\end{equation*}$

Vì $\mathbf{\hat{b}}$ là điểm gần nhất trong không gian cột của $A$ với $\mathbf{b}$ , một vector $\mathbf{\hat{x}}$ là nghiệm bình phương nhỏ nhất của phương trình $A\mathbf{x}=\mathbf{b}$ nếu và chỉ nếu $\mathbf{\hat{x}}$ thỏa mãn điều kiện (1). Vector $\mathbf{\hat{x}}$ này trong $\mathbb{R}^n$ chính là tập hợp các hệ số dùng để xây dựng $\mathbf{\hat{b}}$ từ các cột của $A$ . Xem hình 2 để minh họa trực quan. (Nếu phương trình có biến tự do, sẽ tồn tại nhiều nghiệm cho phương trình $A\mathbf{\hat{x}}=\mathbf{\hat{b}}$ .)

HÌNH 2 Nghiệm bình phương tối thiểu ( x_O ) thuộc ( \mathbb{R}^n ).

Giả sử $\mathbf{\hat{x}}$ thỏa mãn $A\mathbf{\hat{x}}=\mathbf{\hat{b}}$ . Theo Định lý Phân rã Trực giao, phép chiếu $\mathbf{\hat{b}}$ có tính chất rằng $\mathbf{b}-\mathbf{\hat{b}}$ trực giao với không gian cột của $A$ , do đó $\mathbf{b}-A\mathbf{\hat{x}}$ trực giao với từng cột của $A$ . Nếu aja_j là một cột bất kỳ của $A$ , thì $\mathbf{a}_j^T(\mathbf{b}-A\mathbf{\hat{x}})=0$ . Vì mỗi $\mathbf{a}_j^T$ là một hàng của $A^T$ , ta có:

(2) $\begin{equation*}A^T(\mathbf{b}-A\mathbf{\hat{x}})=0\end{equation*}$

Do đó:

$\begin{matrix}A^T\mathbf{b}-A^T A\mathbf{\hat{x}}=&0\\\qquad\quad A^T A\mathbf{\hat{x}}=&A^T\mathbf{b}\\\end{matrix}$

Các phép biến đổi trên cho thấy mỗi nghiệm bình phương nhỏ nhất của $A\mathbf{x}=\mathbf{b}$ đều thỏa mãn phương trình:

(3) $\begin{equation*}A^T A\mathbf{x}=A^T\mathbf{b}\end{equation*}$

Phương trình ma trận (3) biểu diễn một hệ phương trình được gọi là phương trình chuẩn tắc cho $A\mathbf{x}=\mathbf{b}$ . Một nghiệm của (3) thường được ký hiệu là $\mathbf{\hat{x}}$ .

Định lý 13
Tập hợp các nghiệm bình phương nhỏ nhất của  trùng với tập nghiệm không rỗng của phương trình chuẩn tắc .

Chứng minh: Như đã chỉ ra trước đó, tập nghiệm bình phương nhỏ nhất là không rỗng và mỗi nghiệm bình phương nhỏ nhất $\mathbf{\hat{x}}$ đều thỏa mãn phương trình chuẩn tắc. Ngược lại, giả sử $\mathbf{\hat{x}}$ thỏa mãn phương trình $A^T A\mathbf{\hat{x}}=A^T\mathbf{b}$ . Khi đó, $\mathbf{\hat{x}}$ thỏa mãn phương trình (2), điều này cho thấy rằng $\mathbf{b}-A\mathbf{\hat{x}}$ trực giao với các hàng của $A^T$ và do đó cũng trực giao với các cột của $A$ . Vì các cột của $A$ sinh ra không gian cột $\text{Col}\,A$ , nên vectơ $\mathbf{b}-A\mathbf{\hat{x}}$ trực giao với toàn bộ $\text{Col}\,A$ . Do đó, phương trình

$\mathbf{b}=A\mathbf{\hat{x}}+(\mathbf{b}-A\mathbf{\hat{x}})$

là một phép phân rã $\mathbf{b}$ thành tổng của một vectơ trong $\text{Col}\,A$ và một vectơ trực giao với $\text{Col}\,A$ . Theo tính duy nhất của phân rã trực giao, $A\mathbf{\hat{x}}$ phải là phép chiếu trực giao của $\mathbf{b}$ lên $\text{Col}\,A$ . Nghĩa là, $A\mathbf{\hat{x}}=\mathbf{\hat{b}}$ , và $\mathbf{\hat{x}}$ là một nghiệm bình phương nhỏ nhất.

Ví dụ 1: Tìm nghiệm bình phương nhỏ nhất của hệ phương trình không tương thích $A\mathbf{x}=\mathbf{b}$ , với

$A=\begin{bmatrix}4&0\\0&2\\1&1\end{bmatrix},\quad\mathbf{b}=\begin{bmatrix}2\\0\\1\end{bmatrix}$

Giải: Để sử dụng phương trình chuẩn (3), trước tiên ta tính

$\begin{matrix}A^T A=&\begin{bmatrix}4&0&1\\0&2&1\end{bmatrix}\begin{bmatrix}4&0\\0&2\\1&1\end{bmatrix}=\begin{bmatrix}17&1\\1&5\end{bmatrix}\\A^T\mathbf{b}=&\begin{bmatrix}4&0&1\\0&2&1\end{bmatrix}\begin{bmatrix}2\\0\\11\end{bmatrix}=\begin{bmatrix}19\\11\end{bmatrix}\\\end{matrix}$

Do đó, phương trình $A^T A\mathbf{x}=A^T\mathbf{b}$ trở thành

$\begin{bmatrix}17&1\\1&5\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix}=\begin{bmatrix}19\\11\end{bmatrix}$

Vì $A^T A$ là ma trận vuông $2\times 2$ và khả nghịch, ta có thể tính nghịch đảo của nó:

$(A^T A)^{-1}=\frac{1}{84}\begin{bmatrix}5&-1\\-1&17\end{bmatrix}$

Sau đó, nghiệm bình phương nhỏ nhất là

$\begin{matrix}\hat{\mathbf{x}}=&(A^T A)^{-1}A^T b\\\\\quad=&\frac{1}{84}\begin{bmatrix}5&-1\\-1&17\end{bmatrix}\begin{bmatrix}19\\11\end{bmatrix}=\frac{1}{84}\begin{bmatrix}84\\168\end{bmatrix}=\begin{bmatrix}1\\2\end{bmatrix}\\\end{matrix}$

Trong nhiều tính toán, $A^T A$ là khả nghịch, nhưng không phải lúc nào cũng vậy. Ví dụ tiếp theo sẽ minh họa trường hợp ma trận xuất hiện trong các bài toán phân tích phương sai trong thống kê.

Ví dụ 2: Tìm nghiệm bình phương nhỏ nhất của phương trình $A\mathbf{x}=\mathbf{b}$ với

$A=\begin{bmatrix}1&1&0&0\\1&1&0&0\\1&0&1&0\\1&0&1&0\\1&0&0&1\\1&0&0&1\\\end{bmatrix},\quad\mathbf{b}=\begin{bmatrix}-3\\-1\\0\\2\\5\\1\end{bmatrix}$

Giải: Tính

$\begin{matrix}A^T A=&\begin{bmatrix}1&1&1&1&1&1\\1&1&0&0&0&0\\0&0&1&1&0&0\\0&0&0&0&1&1\\\end{bmatrix}\begin{bmatrix}1&1&0&0\\1&1&0&0\\1&0&1&0\\1&0&1&0\\1&0&0&1\\1&0&0&1\\\end{bmatrix}=\begin{bmatrix}6&2&2&2\\2&2&0&0\\2&0&2&2\\2&0&0&2\\\end{bmatrix}\\A^T\mathbf{b}=&\begin{bmatrix}1&1&1&1&1&1\\1&1&&0&0&0\\0&0&1&1&0&0\\0&0&0&0&1&1\\\end{bmatrix}\begin{bmatrix}-3\\-1\\0\\2\\5\\1\end{bmatrix}=\begin{bmatrix}4\\-4\\2\\6\end{bmatrix}\\\end{matrix}$

Ma trận mở rộng của hệ $A^T A\mathbf{x}=A^T\mathbf{b}$ là:

$\begin{bmatrix}6&2&2&2&4\\2&2&0&0&-4\\2&0&2&0&2\\2&0&0&2&6\\\end{bmatrix}\sim\begin{bmatrix}1&0&0&1&3\\0&1&0&-1&-5\\0&0&1&-1&-2\\0&0&0&0&0\\\end{bmatrix}$

Giải hệ phương trình, ta được nghiệm tổng quát $x_1=3-x_4,\,x_2=-5+x_4,\,x_3=-2+x_4,$ và $x_4$ là biến tự do. Vậy nghiệm bình phương nhỏ nhất tổng quát của $A\mathbf{x}=\mathbf{b}$ có dạng:

$\mathbf{\hat{x}}=\begin{bmatrix}3\\5\\-2\\0\end{bmatrix}+x_4\begin{bmatrix}-1\\1\\1\\1\end{bmatrix}$

Định lý tiếp theo đưa ra các tiêu chí hữu ích để xác định khi nào phương trình $A\mathbf{x}=\mathbf{b}$ có duy nhất một nghiệm bình phương nhỏ nhất. (Tất nhiên, hình chiếu trực giao $\mathbf{\hat{b}}$ luôn là duy nhất.)

Định lý 14

Cho $A$ là một ma trận $m\times n$ . Các mệnh đề sau là tương đương:
a. Phương trình $A\mathbf{x}=\mathbf{b}$ có duy nhất một nghiệm bình phương nhỏ nhất với mọi $\mathbf{b}\in\mathbb{R}^m$ .
b. Các cột của $A$ là độc lập tuyến tính.
c. Ma trận $A^T A$ khả nghịch.
Khi các mệnh đề này đúng, nghiệm bình phương nhỏ nhất $\mathbf{\hat{x}}$ được cho bởi:

(4) $\begin{equation*}\mathbf{\hat{x}}=(A^T A)^{-1}A^T\mathbf{b}\end{equation*}$

Công thức $(A^T A)^{-1}A^T\mathbf{b}$ chủ yếu hữu ích cho các mục đích lý thuyết và khi thực hiện tính toán bằng tay với $A^T A$ là ma trận $2\times 2$ khả nghịch.

Khi nghiệm bình phương nhỏ nhất $\mathbf{\hat{x}}$ được sử dụng để tính $A\mathbf{\hat{x}}$ làm xấp xỉ của $\mathbf{b}$ , thì khoảng cách từ $\mathbf{b}$ đến $A\mathbf{\hat{x}}$ được gọi là sai số bình phương nhỏ nhất của phép xấp xỉ này.

Ví dụ 3: Cho $A$ và $\mathbf{b}$ như trong ví dụ 1, hãy xác định sai số bình phương nhỏ nhất trong nghiệm bình phương nhỏ nhất của phương trình $A\mathbf{x}=\mathbf{b}$ .

Giải: Từ Ví dụ 1, ta có:

$\mathbf{b}=\begin{bmatrix}2\\0\\11\end{bmatrix},\quad A\mathbf{\hat{x}}=\begin{bmatrix}4&0\\0&2\\1&1\\\end{bmatrix}\begin{bmatrix}1\\2\end{bmatrix}=\begin{bmatrix}4\\4\\3\end{bmatrix}$

Do đó,

$\mathbf{b}-A\mathbf{\hat{x}}=\begin{bmatrix}2\\0\\11\end{bmatrix}-\begin{bmatrix}4\\4\\3\end{bmatrix}=\begin{bmatrix}-2\\-4\\8\end{bmatrix}$

và

$\|\mathbf{b}-A\mathbf{\hat{x}}\|=\sqrt{(-2)^2+(-4)^2+8^2}=\sqrt{84}$

Vậy sai số bình phương nhỏ nhất là $\sqrt{84}$ . Đối với mọi $\mathbf{x}\in\mathbb{R}^2$ , khoảng cách giữa $\mathbf{b}$ và $A\mathbf{x}$ luôn lớn hơn hoặc bằng $\sqrt{84}$ . Hình 3 minh họa điều này. Lưu ý rằng nghiệm bình phương nhỏ nhất $\mathbf{\hat{x}}$ không xuất hiện trực tiếp trong hình.

Để 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 11: Bài toán Bình phương nhỏ nhất

Lesson Attachments

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