Quá trình Gram–Schmidt

Trong toán học, đặc biệt là trong lĩnh vực đại số tuyến tính và giải tích số, **quá trình Gram–Schmidt** là một phương pháp trực chuẩn hóa một tập hợp các vectơ trong một không gian tích trong, thường là không gian Euclid **R***n* được trang bị tích trong tiêu chuẩn. Quá trình Gram–Schmidt xử lý một tập hợp vectơ hữu hạn và độc lập tuyến tính *S* = {***v***1,..., **''v**k*} với  và tạo ra từ tập đã cho một [[Trực giao|tập vectơ trực giao]] } [[Span tuyến tính|sinh]] ra không gian con *k* chiều của *'R**<sup>''n''</sup> tương tự không gian sinh bởi tập ''S''.

Phương pháp này được đặt tên theo [[Jørgen Pedersen Gram]] và [[Erhard Schmidt]], nhưng [[Pierre-Simon Laplace]] đã quen thuộc với nó trước Gram và Schmidt. Trong lý thuyết [[phân rã nhóm Lie]] nó được tổng quát hóa bởi [[phân rã Iwasawa]].

Áp dụng quá trình Gram–Schmidt vào các vectơ cột của một [[Ma trận (toán học)|ma trận]] với [[Hạng (đại số tuyến tính)|hạng]] cột đầy đủ, ta có phép [[phân rã QR]] (ma trận đó được phân rã thành một [[ma trận trực giao]] và [[Ma trận tam giác|tam giác]]).

== Quá trình Gram–Schmidt ==
[[Tập_tin:Gram-Schmidt_orthonormalization_process.gif|khung|Quá trình Gram-Schmidt (có cải tiến) được thực hiện trên ba vectơ độc lập tuyến tính không trực giao của một cơ sở cho không gian **R**<sup>3</sup>. Nhấp vào ảnh để xem chi tiết.]]
Ta định nghĩa [[toán tử]] [[Phép chiếu (đại số tuyến tính)|chiếu]] vectơ bởi

: <math>\mathrm{proj}_{\mathbf{u}}\,(\mathbf{v}) = {\langle \mathbf{u}, \mathbf{v}\rangle\over\langle \mathbf{u}, \mathbf{u}\rangle}{\mathbf{u}} , </math>

trong đó <math>\langle \mathbf{u}, \mathbf{v}\rangle</math> ký hiệu [[tích trong]] của hai vectơ **u** và **v**. Toán tử [[Chiếu vectơ|chiếu trực giao vectơ]] **v** vào đường thẳng span bởi vectơ **u**. Nếu **u** = **0**, ta định nghĩa <math>\mathrm{proj}_0\,(\mathbf{v}) := 0</math>, tức là ánh xạ chiếu <math>\mathrm{proj}_0</math> là [[Ánh xạ|ánh xạ không]], nó biến mọi vectơ thành [[vectơ không]].

Quá trình Gram–Schmidt sau đó được tiến hành như sau:

: <math>
\begin{align}
\mathbf{u}_1 & = \mathbf{v}_1, & \mathbf{e}_1 & = {\mathbf{u}_1 \over \|\mathbf{u}_1\|} \\
\mathbf{u}_2 & = \mathbf{v}_2-\mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_2),
& \mathbf{e}_2 & = {\mathbf{u}_2 \over \|\mathbf{u}_2\|} \\
\mathbf{u}_3 & = \mathbf{v}_3-\mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_3)-\mathrm{proj}_{\mathbf{u}_2}\,(\mathbf{v}_3), & \mathbf{e}_3 & = {\mathbf{u}_3 \over \|\mathbf{u}_3\|} \\
\mathbf{u}_4 & = \mathbf{v}_4-\mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_4)-\mathrm{proj}_{\mathbf{u}_2}\,(\mathbf{v}_4)-\mathrm{proj}_{\mathbf{u}_3}\,(\mathbf{v}_4), & \mathbf{e}_4 & = {\mathbf{u}_4 \over \|\mathbf{u}_4\|} \\
& {}\ \  \vdots & & {}\ \  \vdots \\
\mathbf{u}_k & = \mathbf{v}_k-\sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{u}_j}\,(\mathbf{v}_k), & \mathbf{e}_k & = {\mathbf{u}_k\over \|\mathbf{u}_k \|}.
\end{align}
</math>

Dãy **u**<sub>1</sub>,..., **u**<sub>''k''</sub> là dãy vectơ trực giao cần tìm, và các vectơ được chuẩn hóa **e**<sub>1</sub>,..., **e**<sub>''k''</sub> tạo thành một tập hợp ''[[trực chuẩn]]''. Việc tính toán dãy **u**<sub>1</sub>,..., **u**<sub>''k''</sub> được gọi là ''[[trực giao hóa]]'' ''Gram–Schmidt'', còn việc tính toán dãy **e**<sub>1</sub>,..., **e**<sub>''k''</sub> được gọi là ''[[trực chuẩn hóa]] Gram–Schmidt'' bởi vì các vectơ đã được chuẩn hóa.

Để kiểm tra xem các công thức trên liệu có cho một dãy trực giao, đầu tiên ta tính <math>\langle \mathbf{u}_1, \mathbf{u}_2 \rangle</math> bằng cách thế vào công thức ở trên cho **u**<sub>2</sub>: ta được 0. Sau đó sử dụng điều này để tính <math>\langle \mathbf{u}_1, \mathbf{u}_3 \rangle</math> bằng cách lại thế vào công thức ở trên cho **u**<sub>3</sub>: ta tiếp tục được 0. Chứng minh tổng quát sau đó được tiếp tục nhờ phép [[quy nạp toán học]].

Nói một cách hình học, phương pháp này được tiếp tục như sau: để tính **u**<sub>''i''</sub> nó chiếu trực giao vectơ **v**<sub>''i''</sub> vào không gian con ''U'' sinh bởi **u**<sub>1</sub>,..., **u**<sub>''i''−1</sub>, mà đó cũng là không gian con sinh bởi **v**<sub>1</sub>,..., **v**<sub>''i''−1</sub>. Vectơ **u**<sub>''i''</sub> sau đó được định nghĩa là [[Chiếu vectơ#Hình phản chiếu vectơ|hiệu]] giữa **v**<sub>''i''</sub> và hình chiếu này và đảm bảo là trực giao với tất cả các vectơ trong không gian con ''U''.

Quá trình Gram–Schmidt cũng áp dụng cho một dãy độc lập tuyến tính và [[vô hạn đếm được]] {**v**<sub>''i''</sub>}<sub>''i''</sub>. Kết quả là một dãy trực giao (hay trực chuẩn) {**u**<sub>''i''</sub>}<sub>''i''</sub> sao cho với một số tự nhiên ''n'': [[Span tuyến tính|span]] đại số của **v**<sub>1</sub>,..., **v**<sub>''n''</sub> cũng chính là span của **u**<sub>1</sub>,..., **u**<sub>''n''</sub>.

Nếu quá trình Gram–Schmidt được áp dụng cho một dãy phụ thuộc tuyến tính, nó sẽ cho ra vectơ **0** ở bước thứ ''i'', giả sử **v**<sub>''i''</sub> là một tổ hợp tuyến tính của . Nếu cần phải có một hệ cơ sở trực chuẩn thì thuật toán nên tìm ra các vectơ không trong các kết quả và loại bỏ chúng vì không có một bội nào của vectơ không mà có độ dài bằng 1. Số vectơ đầu ra của thuật toán sẽ bằng số chiều của không gian được span bởi các vectơ đầu vào.

== Ví dụ ==

=== Không gian Euclide ===
Xét hệ vectơ sau trong **R**<sup>2</sup> (với [[Không gian tích trong|tích trong]] quy ước chính là [[tích vô hướng]])

: <math>S = \left\lbrace\mathbf{v}_1=\begin{pmatrix} 3 \\ 1\end{pmatrix}, \mathbf{v}_2=\begin{pmatrix}2 \\2\end{pmatrix}\right\rbrace.</math>

Bây giờ, thực hiện Gram–Schmidt để có được hệ các vectơ trực giao:

: <math>\mathbf{u}_1=\mathbf{v}_1=\begin{pmatrix}3\\1\end{pmatrix}</math>
: <math> \mathbf{u}_2 = \mathbf{v}_2 - \mathrm{proj}_{\mathbf{u}_1} \, (\mathbf{v}_2) = \begin{pmatrix}2\\2\end{pmatrix} - \mathrm{proj}_{({3 \atop 1})} \, ({\begin{pmatrix}2\\2\end{pmatrix})} = \begin{pmatrix}2\\2\end{pmatrix} - {8 \over 10} \begin{pmatrix} 3 \\1 \end{pmatrix} = \begin{pmatrix} -2/5 \\6/5 \end{pmatrix}. </math>

Ta kiểm tra rằng các vectơ **u**<sub>1</sub> và **u*'<sub>2</sub> chắc chắn là trực giao:

: <math>\langle\mathbf{u}_1,\mathbf{u}_2\rangle = \left\langle \begin{pmatrix}3\\1\end{pmatrix}, \begin{pmatrix}-2/5\\6/5\end{pmatrix} \right\rangle = -\frac65 + \frac65 = 0,</math>

lưu ý rằng nếu tích vô hướng của hai vectơ bằng *0'' thì chúng trực giao.

Đối với các vectơ khác vectơ không, ta có thể chuẩn hóa các vectơ đó bằng cách chia cho độ dài của chúng như dưới đây:

: \mathbf{e}_1 = {1 \over \sqrt {10}}\begin{pmatrix}3\\1\end{pmatrix}
: \mathbf{e}_2 = {1 \over \sqrt{40 \over 25}} \begin{pmatrix}-2/5\\6/5\end{pmatrix}
 = {1\over\sqrt{10}} \begin{pmatrix}-1\\3\end{pmatrix}. 

## Tham khảo

## Tham khảo sách

* .
* .
* .
* .

## Liên kết ngoài

* 
* Harvey Mudd College Math Tutorial on the Gram-Schmidt algorithm
* Earliest known uses of some of the words of mathematics: G The entry "Gram-Schmidt orthogonalization" has some information and references on the origins of the method.
* Demos: Gram Schmidt process in plane and Gram Schmidt process in space
* Gram-Schmidt orthogonalization applet
* NAG Gram–Schmidt orthogonalization of n vectors of order m routine
* Proof: Raymond Puzio, Keenan Kidwell. "proof of Gram-Schmidt orthogonalization algorithm" (version 8). PlanetMath.org.