Xem mã nguồn của Bình phương tối thiểu tuyến tính

'''Bình phương tối thiểu tuyến tính''' là một kỹ thuật trong ngành [[tối ưu]] [[toán học]] để tìm một nghiệm gần đúng cho một [[hệ phương trình tuyến tính]] không có nghiệm chính xác. Điều này thường xảy ra khi số phương trình là (''m'') lớn hơn số [[biến số|biến]] (''n''). (Xem thêm [[linear regression]].)

==Định nghĩa==

Theo từ ngữ toán học, chúng ta muốn tìm nghiệm của "phương trình" 
:<math>A\mathbf{x} \approx \mathbf{b}</math>,
với ''A'' là một [[ma trận]] cỡ ''m''-nhân-''n'' (với ''m'' > ''n'') và '''x''' và '''b''' theo thứ tự đó là [[vectơ]] cột với ''n''- và ''m''-hàng. Một cách chính xác hơn, ta muốn làm tối thiểu [[chuẩn Euclidean]] bình phương của [[phần dư]] ''A'''''x''' &minus; '''b''', nghĩa là, đại lượng

:<math>\|A\mathbf{x}-\mathbf{b}\|^2 = \left([A\mathbf{x}]_1-\mathbf{b}_1\right)^2
+\left([A\mathbf{x}]_2-\mathbf{b}_2\right)^2
+\dots+
\left([A\mathbf{x}]_m-\mathbf{b}_m\right)^2,
</math>

với [''A'''''x''']<sub>''i''</sub> ký hiệu phần tử thứ ''i'' của vectơ ''A'''''x'''. Do đó mà có cái tên "bình phương tối thiểu".

Sử dụng sự kiện bình phương chuẩn của '''v''' là '''v'''<sup>T</sup>'''v''', với '''v'''<sup>T</sup> ký hiệu cho [[ma trận chuyển]] của '''v''', ta viết lại biểu thức trên như là

:<math>(A \mathbf{x}- \mathbf{b})^T(A \mathbf{x}- \mathbf{b}) = (A \mathbf{x})^T (A \mathbf{x}) - \mathbf{b}^T A \mathbf{x} - (A \mathbf{x})^T \mathbf{b} + \mathbf{b}^T \mathbf{b}.</math>

Hai hạng tử ở giữa là như nhau, do đó giá trị tối thiểu có thể được tìm tại zero của đạo hàm theo biến '''x''',

:<math>2 A^T A \mathbf{x} - 2 A^T \mathbf{b} = \mathbf{0}.</math>

Do vậy là tối thiểu '''x''' là nghiệm của '''phương trình normal''' sau đây 
:<math> A^T \! A \mathbf{x} = A^T \mathbf{b}. </math>

Để ý rằng điều này tương đương với một [[hệ phương trình tuyến tính]]. Ma trận ''A''<sup>T</sup>''A'' ở phía bên trái là một ma trận vuông, và khả nghịch nếu như ''A'' có đầy rank theo cột (nghĩa là, nếu như [[Rank (ma trận)|rank]] của ''A'' là ''n''). Trong trường hợp đó, nghiệm của hệ phương trình tuyến tính là duy nhất và được cho bởi
:<math> \mathbf{x} = (A^T\!A)^{-1} A^T \mathbf{b}. </math> 
Ma trận <math>(A^TA)^{-1}A^T</math> gọi là [[ma trận giả nghịch đảo]] của ''A''. Chúng ta không thể sử dụng [[ma trận khả nghịch|ma trận nghịch đảo]] thật sự của ''A'' (nghĩa là, <math>A^{-1}</math>), vì nó không tồn tại do ''A'' không phải là một [[Ma trận|ma trận vuông]] (''m'' &ne; ''n'').

==Tính toán==

Nếu ma trận ''A<sup>T</sup>A'' đầy rank và ổn định (well-conditioned), phương trình normal có thể được giải trực tiếp bằng [[phân tích Cholesky]] ''A<sup>T</sup>A'' = ''R<sup>T</sup>R'', cho ta:
: <math> R^T R \mathbf{x} = A^T \mathbf{b}. </math>
với ''R'' là một [[ma trận tam giác]] trên (ma trận mà các số phía dưới đường chéo đều bằng 0,''upper triangular matrix'').

Một phương pháp chậm hơn nhưng [[phương pháp tính ổn định|ổn định]] hơn, vẫn làm việc nếu ''A'' không đầy rank, có thể đạt được bằng cách tính [[phân tích QR]] ''A = Q R''. Sau đó ta có thể giải
: <math> R \mathbf{x} = Q^T \mathbf{b}. </math>
với ''Q'' là một [[ma trận trực giao]] và ''R'' là một [[ma trận tam giác]] trên.

Một cách thứ ba là sử dụng [[singular value decomposition]] (SVD). Nếu <math> A = U\Sigma V^*</math> là singular value decomposition của ''A'', thì ma trận giả nghịch đảo của ''A'' là
''V &Sigma;<sup>+</sup> U<sup>*</sup>'', so
:<math> \mathbf{x} = V \Sigma^+ U^* \mathbf{b} \,</math>
với &Sigma;<sup>+</sup> là ma trận chuyển của &Sigma; với mọi phần tử khác 0 được thay bằng phần tử nghịch đảo. Phương pháp này cần dùng nhiều sức máy nhất, nhưng rất hữu ích nếu như ma trận ''A'' rất không ổn định (i.e. nếu như [[số điều kiện]] của nó nhân với [[sai số]] của máy khá lớn). Trong trường hợp đó, thêm vào những giá trị nhỏ nhất của các giá trị singular trong ma trận nghịch đảo chỉ cộng thêm nhiễu vào đáp số. Điều này có thể được chữa bằng tiếp cận sử dụng SVD, cho ra một lời giải chính xác hơn và ổn định hơn, bằng cách đặt bằng zero tất cả các giá trị singular dưới một ngưỡng nào đó và mặc kệ chúng, trước khi tính toán ma trận giả nghịch đảo.

==Áp dụng==

Phương pháp bình phương tối thiểu tuyến tính có thể được sử dụng để tìm một hàm affine '''R'''<sup>n</sup> &rarr; '''R''' khớp nhất với một tập hợp dữ liệu cho trước (xem phương pháp [[bình phương tối thiểu]]).

Ví dụ

: <math>y = \alpha + \beta x + \gamma x^2 + \varepsilon</math>

là một mô hình regression tuyến tính, với phần phải là một tổ hợp tuyến tính của các tham số &alpha;, &beta;, và &gamma;; hơn nữa, các đánh giá bình phương tối thiểu của các tham số này là tuyến tính trong vector của các giá trị quan sát ''y''.

Chúng ta viết hàm tuyến tính cần tìm như là một ma trận 1-nhân-''n'' '''x'''<sup>T</sup> (do đó '''x''' thật ra là 1 vectơ cột, xem thêm [[biến đổi tuyến tính]]).

Tập dữ liệu gồm có ''m'' (''n''&nbsp;+&nbsp;1)-[[bộ n số|bộ số]] (''x''<sub>1</sub>,..., ''x''<sub>''n''</sub>, ''y''). Những giá trị này được viết vào một ma trận ''m''-nhân-''n'' ''A'' và một vector '''b''', với mỗi bộ tương ứng với một hàng của ''A'', và ''y'' trở thành các phần tử tương ứng trong '''b'''.

Sau đó, 
: ''A'''''x''' &asymp; '''b'''
cho ta hàm số '''x''' cần tìm.

== Ví dụ ==
Cho các điểm (0, 3), (2, 3), (4, 4), (&minus;1, 2). Chúng ta tìm một lời giải có dạng &alpha;''x'' + &beta; = ''y'', nghĩa là,

: <math>\begin{pmatrix}x & 1 \end{pmatrix}\begin{pmatrix} \alpha \\ \beta\end{pmatrix} = y</math>

Chúng ta sau đó có thể lập ma trận ''A'':
: <math>A=\begin{pmatrix}
0 & 1 \\
2 & 1 \\
4 & 1 \\
-1 & 1 \\ \end{pmatrix}</math>
: <math>A^T=\begin{pmatrix}
0  & 2 & 4 & -1 \\
1  & 1 & 1 & 1 \end{pmatrix}</math>
: <math>A^TA=\begin{pmatrix}
21 & 5 \\
5 & 4 \end{pmatrix}</math>
và vectơ '''b'''
: <math>\mathbf{b} = \begin{pmatrix}
3 \\
3 \\
4 \\ 
2 \end{pmatrix}</math>
và sau đó
:<math>A^T\mathbf{b}=\begin{pmatrix}
20 \\
12 \end{pmatrix}</math>
Do đó, phương trình normal là 
[[Tập tin:leastsquaresexamp.png|300 px|frame|phải|Hình vẽ các điểm và lời giải.]]
:<math>A^TA\begin{pmatrix} \alpha \\ \beta \end{pmatrix} = A^T\mathbf{b}</math>
:<math>\begin{pmatrix}
21 & 5 \\
5 & 4 \end{pmatrix} \begin{pmatrix} \alpha \\ \beta \end{pmatrix}=\begin{pmatrix}
20 \\
12 \end{pmatrix}</math>
Sau đó,
:<math>(A^TA)^{-1}={1\over 59}\begin{pmatrix}
4 & -5 \\
-5 & 21 \end{pmatrix}</math>
and
:<math>\begin{pmatrix} \alpha \\ \beta\end{pmatrix}={1\over 59}\begin{pmatrix}
4 & -5 \\
-5 & 21 \end{pmatrix}\begin{pmatrix}
20 \\
12 \end{pmatrix}=\begin{pmatrix}
20/59 \\
152/59 \end{pmatrix}</math>
và đường thẳng tốt nhất là (20/59)''x'' + 152/59 = ''y''.

==Xem thêm==

* [[Linear regression]]
* [[Least-squares estimation of linear regression coefficients]]
* [[Tikhonov regularization]]

==Tham khảo==
{{tham khảo}}
==Liên kết ngoài==
*[http://mathworld.wolfram.com/LeastSquaresFitting.html Least Squares Fitting &ndash; From MathWorld]

[[Thể loại:Tối ưu hóa (toán học)]]
[[Thể loại:Đại số tuyến tính]]
[[Thể loại:Thuật toán tối ưu hóa]]