Movatterモバイル変換

Quá trình Gram–Schmidt

Bách khoa toàn thư mở Wikipedia

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áptrực chuẩn hóa một tập hợp cácvectơ trong một không gian tích trong, thường làkhông gian EuclidRⁿ đượ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ínhS = {v₁,...,v_k} vớik ≤n và tạo ra từ tập đã cho mộttập vectơ trực giaoS′ = {u₁,...,u_k}sinh ra không gian conk chiều củaRⁿ tương tự không gian sinh bởi tậpS.

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

Áp dụng quá trình Gram–Schmidt vào các vectơ cột của mộtma trận vớihạng cột đầy đủ, ta có phépphân rã QR (ma trận đó được phân rã thành mộtma trận trực giao vàtam giác).

Quá trình Gram–Schmidt

[sửa |sửa mã nguồn]

Ta định nghĩatoán tử chiếu vectơ bởi

\mathrm {proj} _{\mathbf {u} }\,(\mathbf {v} )={\langle \mathbf {u} ,\mathbf {v} \rangle  \over \langle \mathbf {u} ,\mathbf {u} \rangle }{\mathbf {u} },

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

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

{\begin{aligned}\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{aligned}}

Dãyu₁,...,u_k là dãy vectơ trực giao cần tìm, và các vectơ được chuẩn hóae₁,...,e_k tạo thành một tập hợptrực chuẩn. Việc tính toán dãyu₁,...,u_k được gọi làtrực giao hóaGram–Schmidt, còn việc tính toán dãye₁,...,e_k đượ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 $\langle \mathbf {u} _{1},\mathbf {u} _{2}\rangle$ bằng cách thế vào công thức ở trên chou₂: ta được 0. Sau đó sử dụng điều này để tính $\langle \mathbf {u} _{1},\mathbf {u} _{3}\rangle$ bằng cách lại thế vào công thức ở trên chou₃: ta tiếp tục được 0. Chứng minh tổng quát sau đó được tiếp tục nhờ phépquy 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ínhu_i nó chiếu trực giao vectơv_i vào không gian conU sinh bởiu₁,...,u_i−1, mà đó cũng là không gian con sinh bởiv₁,...,v_i−1. Vectơu_i sau đó được định nghĩa làhiệu giữav_i 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 conU.

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_i}_i. Kết quả là một dãy trực giao (hay trực chuẩn) {u_i}_i sao cho với một số tự nhiênn:span đại số củav₁,...,v_n cũng chính là span củau₁,...,u_n.

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_i là một tổ hợp tuyến tính củav₁,...,v_i−1. 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ụ

[sửa |sửa mã nguồn]

Không gian Euclide

[sửa |sửa mã nguồn]

Xét hệ vectơ sau trongR² (vớitích trong quy ước chính làtích vô hướng)

S=\left\lbrace \mathbf {v} _{1}={\begin{pmatrix}3\\1\end{pmatrix}},\mathbf {v} _{2}={\begin{pmatrix}2\\2\end{pmatrix}}\right\rbrace .

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

\mathbf {u} _{1}=\mathbf {v} _{1}={\begin{pmatrix}3\\1\end{pmatrix}}

\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}}.

Ta kiểm tra rằng các vectơu₁ vàu₂ chắc chắn là trực giao:

\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 =-{\frac {6}{5}}+{\frac {6}{5}}=0,

lưu ý rằng nếu tích vô hướng của hai vectơ bằng0 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

[sửa |sửa mã nguồn]

^Cheney, Ward; Kincaid, David (2009).Linear Algebra: Theory and Applications. Sudbury, Ma: Jones and Bartlett. tr. 544, 558.ISBN 978-0-7637-5020-6.

Tham khảo sách

[sửa |sửa mã nguồn]

Bau III, David;Trefethen, Lloyd N. (1997),Numerical linear algebra, Philadelphia: Society for Industrial and Applied Mathematics,ISBN 978-0-89871-361-9.
Golub, Gene H.;Van Loan, Charles F. (1996),Matrix Computations (ấn bản thứ 3), Johns Hopkins,ISBN 978-0-8018-5414-9.
Greub, Werner (1975),Linear Algebra (ấn bản thứ 4), Springer.
Soliverez, C. E.; Gagliano, E. (1985),"Orthonormalization on the plane: a geometric approach"(PDF),Mex. J. Phys.,31 (4):743–758,Bản gốc(PDF) lưu trữ ngày 7 tháng 3 năm 2014, truy cập ngày 25 tháng 2 năm 2021{{Chú thích}}:Đã bỏ qua tham số không rõ|= (trợ giúp).

Liên kết ngoài

[sửa |sửa mã nguồn]

Hazewinkel, Michiel, biên tập (2001),"Orthogonalization",Bách khoa toàn thư Toán học,Springer,ISBN 978-1-55608-010-4
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 andGram 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.

x t s Đại số tuyến tính
Đại cương Thuật ngữ
Khái niệm cơ bản	Vô hướng Vectơ Không gian vectơ Phép nhân vô hướng Chiếu vectơ Hệ sinh Ánh xạ tuyến tính Phép chiếu tuyến tính Độc lập tuyến tính Tổ hợp tuyến tính Cơ sở Chuyển cơ sở Vectơ hàng và cột Không gian hàng và cột Hạt nhân Giá trị riêng và vectơ riêng Ma trận chuyển vị Hệ phương trình tuyến tính
Ma trận	Khối Phân rã Nghịch đảo Định thức con Tích Hạng Biến đổi Quy tắc Cramer Phép khử Gauss
Song tuyến tính	Trực giao Tích vô hướng Không gian tích trong Tích ngoài Quá trình Gram–Schmidt
Đại số đa tuyến tính	Định thức Tích vectơ Tích ba Tích vectơ 7 chiều Đại số hình học Đại số ngoài Song vectơ Đa vectơ Tenxơ Cấu xạ ngoài
Xây dựng không gian vectơ	Không gian đối ngẫu Tổng trực tiếp Không gian hàm Thương Không gian con Tích tenxơ
Đại số tuyến tính số	Dấu phẩy động Bình phương tối thiểu tuyến tính Ổn định số Basic Linear Algebra Subprograms Ma trận thưa Comparison of linear algebra libraries
Thể loại Mục lục Chủ đề Toán học Wikibook Wikiversity