Ma trận chiếu trong ĐSTT

Trong hội họa (và đồ họa máy tính), có 2 dạng phép chiếu cơ bản là chiếu song song (parallel) và chiếu phối cảnh (perspective). Song song là phép chiếu mà các tia chiếu song song nhau, chiếu phối cảnh là trong trường hợp các tia chiếu cắt nhau tại một vị trí nào đó trên đường đi của chúng.

Phép chiếu song song còn được phân ra nhiều loại: chiếu trực giao (orthogonal), chiếu xiên (non-orthogonal, hay oblique), isometric (một phương pháp hay được dùng trong các game đồ họa, đặc biệt là trên các thiết bị di động, có thể tạo cảm giác 3D cho vật thể), dimetric, trimetric v.v… Phép chiếu phối cảnh ngược lại được dùng nhiều trong các ứng dụng đồ họa máy tính, giúp dựng hình 3D gần hơn với cảm nhận của con người.

Bóng của một vật trên mặt đất do mặt trời tạo ra là kết quả của phép chiếu song song, do mặt trời ở quá xa nên ta xem như các tia sáng là song song. Ngược lại, cầm một ngọn nến chiếu lên tường, ta được hình ảnh của phép chiếu phối cảnh. Hình ảnh mà con người nhìn bằng mắt hàng ngày là kết quả của phép chiếu phối cảnh. Hình ảnh thu được của máy ảnh là kết quả của phép chiếu phối cảnh. Người họa sĩ vẽ tranh phong cảnh cũng đang dùng phép chiếu phối cảnh. Nói chung phép chiếu phối cảnh là hết sức quen thuộc với con người, trong khi phép chiếu song song thường được dùng trong kĩ thuật, và kết quả của nó nói chung là xa lạ với cảm nhận của con người.

Để đặc trưng cho phép chiếu song song, ta đơn giản chỉ cần biết phương chiếu và mặt phẳng chiếu (mặt phẳng chứa hình chiếu sẽ nhận được). Trong khi đó, phép chiếu phối cảnh thông thường cần nhiều tham số hơn: điểm đặt mắt, hướng nhìn, hướng lên trên, và có thể cả độ sâu v.v…

Vậy Đại số tuyến tính liên quan gì đến phép chiếu? Có khá nhiều thuật toán trong Đại số tuyến tính xuất phát từ những quan sát rất trực quan. Chẳng hạn các thuật toán Householder trong phân tích QR, phân tích SVD, biến đổi ma trận về dạng Hessenberg v.v.. đều quan tâm đến phép chiếu một điểm lên một không gian vector. Thực tế thì các phép chiếu là một công cụ hữu ích và kinh điển trong Đại số tuyến tính. Trong bài này, chúng ta quan tâm đến các ma trận chiếu song song trong Đại số tuyến tính. Trong đó, ta muốn chiếu một điểm x theo một phương nào đó lên một không gian vector m chiều.

1. Ma trận chiếu

Ta định nghĩa một projector (chiếu tử – nghe ghê răng quá) là một ma trận vuông P thỏa mãn:

P^2 = P       (1)

Định nghĩa này bao gồm mọi phép chiếu song song, gồm trực giao lẫn không trực giao. Theo đó, gọi v \in \mathbb{C}^m là vector m chiều, thì Pv là phép chiếu v lên không gian range(P).

Trong trường hợp v\in range(P), hình chiếu Pv của v cũng chính là v, nói cách khác áp dụng projector P lên một vector nằm trong không gian range(P) ta sẽ được hình chiếu là chính nó. Có thể dễ dàng chứng mình điều này: do v\in range(P) nên tồn tại vector x nào đó sao cho v là hình chiếu của x qua projector P: v = Px. Như vậy ta có:

Pv = P^2x = Px = v       (2)

Projector

Hình 1: minh họa một phép chiếu xiên trong không gian 2 chiều.

Một ví dụ đơn giản được cho trong Hình 1. Xét ma trận chiếu

P=\left[\begin{array}{cc}2&-2\\1&-1\end{array}\right]

Do 2 vector cột của P\left(2, 1\right)\left(-2, -1\right) phụ thuộc tuyến tính nên range(P) bao gồm tất cả các điểm có tọa độ \left(2k,k\right),\forall k \in \mathbb{R}. Trên hình, range(P) được biểu diễn bằng đường thẳng đi qua gốc tọa độ.

Xét điểm v=\left(2, 3\right) trong không gian 2 chiều, ta có Pv = \left(-2, -1\right) nằm trên đường thẳng range(A). Tương tự với w = \left(1, -2\right) thì Pw = \left(6, 3\right) \in range(A). Ví dụ đơn giản này về phép chiếu trong không gian 2D sẽ giúp ta hiểu rõ về phép chiếu trong các không gian nhiều chiều hơn.

Theo đúng tư tưởng về phép chiếu song song trong hình học, một thắc mắc tự nhiên là: chẳng hạn với ma trận chiếu P như trên, thì phương chiếu là phương nào? Nếu tinh ý thì trong Hình 1 ta nhận thấy Pv-vPw - w là 2 vector cùng phương. Giả sử với v bất kì và hình chiếu Pv của nó lên không gian range(P), thì khi áp dụng ma trận chiếu P lên vector Pv - v, ta được:

P\left(Pv - v\right) = P^2v-Pv = 0.      (3)

Nói cách khác, cho ma trận chiếu P bất kì, Pv - v nằm trong không gian null(P), với mọi v. Trong trường hợp đơn giản ở Hình 1, ta có cảm giác rằng ma trận chiếu P chỉ cho các phép chiếu trên cùng một phương, tuy nhiên nói chung điều này không đúng. Trong trường hợp tổng quát, ta chỉ có thể khẳng định rằng phương chiếu của ma trận chiếu P nằm trong không gian null(P). Đây là điểm quan trọng nên ta nhấn mạnh thêm lần nữa:

Cho ma trận chiếu P. Với các điểm v khác nhau thì phương chiếu Pv-v có thể khác nhau, nhưng Pv-v luôn nằm trong không gian null(P).

Đến đây chúng ta phân biệt một điểm quan trọng của phép chiếu song song trong Đại số tuyến tính và các lĩnh vực khác như Hình học, đồ họa… Trong đa số các ứng dụng kĩ thuật này, phép chiếu song song được đặc trưng bằng phương chiếu và không gian đích của phép chiếu (thông thường là một mặt phẳng 2D).

Trong khi đó với Đại số tuyến tính, ta dùng một ma trận vuông P thỏa P^2=P để đặc trưng cho phép chiếu. Khi đó phương chiếu nằm trong không gian null(P) và không gian đích là range(P).

2. Phép chiếu bù

Nếu P là một ma trận chiếu thì I – P cũng là ma trận chiếu, vì:

\left(I-P\right)^2 = I^2 - 2P + P^2 = I-P

Nhưng vấn đề là không gian đích của ma trận chiếu I – P là không gian nào? Câu trả lời chính là null(P).

Dễ dàng ta thấy với mọi v \in null(P) thì theo (3)Pv = 0, suy ra \left(I-P\right)v = v, do đó v \in range(I-P). Như vậy null(P)\subset range(I-P).

Ngược lại với mọi v \in range(I-P) thì theo (2)(I-P)v = v - Pv = v, suy ra Pv = 0 nên v \in null(P). Nghĩa là range(I-P) \subset null(P).

Từ 2 điều này suy ra với ma trận chiếu P bất kì thì:

range(I-P) = null(P)      (4)

Bằng cách viết P = I - \left(I-P\right), ta có được kết quả tương tự:

null(I-P) = range(P)    (5)

Ngoài ra ta cũng nhận xét rằng

range(P) \bigcap null(P) = \lbrace 0\rbrace   (6)

vì nếu v \in range(P) thì v = Pv. Nếu v cũng thuộc null(P) thì Pv = 0. Như vậy v thuộc cả range(P)null(P) khi và chỉ khi v = 0.

Một cách tương đương, ta có thể viết lại (6) như sau:

null(I-P) \bigcap null(P) = \lbrace 0\rbrace
range(I-P) \bigcap range(P) = \lbrace 0\rbrace     (7)

Từ đây ta thấy một ma trận chiếu P chia không gian \mathbb{C}^m thành 2 không gian con là range(P)null(P): P là phép chiếu lên không gian range(P) theo “phương” null(P).

Trở lại với ví dụ đơn giản của ta ở Hình 1. Với phép chiếu P như trên thì một vector c=\left(x,y\right) thuộc null(P) khi và chỉ khi Pc = 0. Dễ dàng kiểm tra được điều này tương đương với x = y, do đó null(P) chính là đường chéo chính (màu xanh) như vẽ trong Hình 2. Rõ ràng ta thấy null(P)range(P) chỉ giao nhau tại điểm có tọa độ (0, 0), và hơn nữa, từ null(P)range(P) có thể phát sinh ra cả không gian \mathbb{R}^2.

Projector and complementary subspaces

Hình 2: Ma trận chiếu ở Hình 1, với null(P) và range(P)

Ngược lại, gọi S_1S_2 là hai không gian con của \mathbb{C}^m sao cho S_1\bigcap S_2 = \lbrace 0\rbraceS_1 + S_2 = \mathbb{C}^m, với S_1 + S_2 kí hiệu không gian tạo bởi các vector s_1 + s_2 với s_1\in S_1s_2 \in S_2 (cặp S_1S_2 như vậy gọi là không gian con bù). Khi đó tồn tại phép chiếu P sao cho range(P) = S_1null(P)=S_2. Ta nói P là phép chiếu lên S_1 theo phương S_2.

Vấn đề là cho S_1S_2, làm sao để tìm P như vậy? Người ta chứng minh được rằng phép chiếu này tương ứng với lời giải duy nhất của bài toán sau đây:

Cho vector v, tìm v_1 \in S_1v_2 \in S_2 sao cho v_1 + v_2 = v.

Phép chiếu tương ứng có thể tìm được dựa vào nhận xét rằng Pv = v_1\left(I-P\right)v=v_2.

Một trong những ứng dụng hay được dùng của phép chiếu là khi xét ma trận A\in \mathbb{C}^{m\times m} với đầy đủ m vector riêng \lbrace v_j\rbrace, khi đó các \lbrace v_j\rbrace tạo thành cơ sở cho không gian \mathbb{C}^{m\times m}. Thông thường ta có thể sẽ muốn tìm khai triển của các vector trong cơ sở \lbrace v_j\rbrace. Cho trước vector v\in \mathbb{C}^m, ta sẽ muốn tìm thành phần của x theo hướng của vector riêng v_j. Đáp án đương nhiên là Pv_j với P là ma trận chiếu có hạng bằng 1.

Trong phần tiếp theo, ta sẽ xem xét tiếp phép chiếu trực giao – một công cụ rất hay được dùng trong ĐSTT.

3. Phép chiếu trực giao

Phép chiếu trực giao

Hình 3: Phép chiếu trực giao – phương chiếu vuông góc với không gian chiếu.

Ta định nghĩa phép chiếu trực giao là phép chiếu P lên không gian S_1 theo phương S_2S_1S_2 là trực giao với nhau (mọi vector trong S_1 đều trực giao với mọi vector trong S_2 và ngược lại. Hai không gian con S_1S_2 như vậy gọi là không gian con trực giao – orthogonal subspaces). Lưu ý rằng phép chiếu trực giao không có nghĩa là ma trận chiếu của nó là ma trận trực giao!

Ma trận chiếu của một phép chiếu trực giao phải là ma trận Hermitian. Ta có định lí sau:

Định lí 1: Một phép chiếu P là trực giao khi và chỉ khi P = P^*.

Nhắc lại rằng cùng với điều kiện (1), một phép chiếu P trực giao khi P = P^* = P^2.

Chiều nghịch của định lí có thể chứng minh đơn giản: Cho phép chiếu P lên không gian S_1 theo phương S_2 thỏa P = P^*. Khi đó với mọi a\in S_1, b\in S_2 thì tồn tại x, y sao cho a = Px, b=(I-P)y. Ta có:

a^*b = x^*P^*\left(I-P\right)y = x^*P\left(I-P\right)y=x^*\left(P-P^2\right)y = 0.

Với mọi a\in S_1, b\in S_2 thì a^*b = 0, suy ra S_1, S_2 là trực giao, nên P là phép chiếu trực giao.

Chiều thuận của định lí có thể được chứng minh bằng cách khéo léo xây dựng phân tích SVD của ma trận P, sau đó dựa vào phân tích này để chứng tỏ P = P^*.

Giả sử phép chiếu P lên không gian S_1 theo phương S_2 với S_1 \perp S_2S_1n chiều (n\leq m). Gọi \lbrace q_1,q_2,...,q_m\rbrace là cơ sở trực chuẩn của không gian \mathbb{C}^m trong đó \lbrace q_1,q_2,...,q_n\rbrace là cơ sở của S_1\lbrace q_{n+1},q_{n+2},...,q_m\rbrace là cơ sở của S_2. Như vậy với j\leq n thì Pq_j=q_j và với j > n thì Pq_j = 0. Gọi Q =\Bigl[q_1\vert q_2\vert\cdots\vert q_m\Bigr] là ma trận có các cột là các q_j, thì ta có:

PQ =\left[\begin{array}{c|c|c|c|c}\;&\;&\;&\;&\;\\\;&\;&\;&\;&\;\\q_1&\cdots&q_n&\mathbf{0}&\cdots\\\;&\;&\;&\;&\;\\\;&\;&\;&\;&\;\end{array}\right]

Do q_j là các vector cơ sở trực chuẩn nên q_j^*q_j = e_j, suy ra:

Q^*PQ =\left[\begin{array}{c|c|c|c|c}1&\;&\;&\;&\;\\\;&\ddots&\;&\;&\;\\\;&\;&1&\;&\;\\\;&\;&\;&\mathbf{0}&\;\\\;&\;&\;&\;&\ddots\end{array}\right]=\Sigma

với \Sigma là ma trận đường chéo với n phần tử đầu tiên bằng 1 và các phần tử còn lại bằng 0. Như vậy ta đã tạo được phân tích SVD của P:

P = Q\Sigma Q^*    (8)

Ta có P^* = \left(Q\Sigma Q^*\right)^* = Q\Sigma^* Q^* = Q\Sigma Q^* = P nên P là ma trận Hermitian. (do \Sigma = Q^*PQ nên \Sigma^*=\Sigma).

4. Phép chiếu với cơ sở trực chuẩn

Trong khai triển SVD của P ở phương trình (8), ta thấy có một số cột của Q bằng 0, do đó có thể bỏ đi, và sử dụng dạng rút gọn của SVD. Khi đó ta được khai triển rất đơn giản sau của P:

P =\hat{Q}\hat{Q}^*       (9)

trong đó, nhắc lại, các cột của \hat{Q} là các vector trực chuẩn.

Một cách tổng quát, các cột của \hat{Q} trong (9) không nhất thiết phải là kết quả của SVD. Gọi \lbrace q_1, q_2, \cdots q_n\rbrace là tập n vector trực chuẩn bất kì của không gian \mathbb{C}^m\hat{Q} là ma trận m\times n tương ứng, thì người ta chứng minh được P =\hat{Q}\hat{Q}^* cũng là phép chiếu trực giao lên không gian range\left(\hat{Q}\right). Tương tự, phần bù I-\hat{Q}\hat{Q}^* cũng là một phép chiếu trực giao lên không gian trực giao của range\left(\hat{Q}\right) (chứng minh I-\hat{Q}\hat{Q}^* là ma trận Hermitian?).

Tóm lại, ta nhấn mạnh:

Cho \hat{Q} là ma trận m\times n tạo bởi bộ n vector trực chuẩn \lbrace q_1, q_2, \cdots, q_n\rbrace của \mathbb{C}^m thì:

  • P =\hat{Q}\hat{Q}^* là phép chiếu trực giao lên không gian range\left(\hat{Q}\right), và
  • I-\hat{Q}\hat{Q}^* cũng là phép chiếu trực giao lên không gian trực giao với range\left(\hat{Q}\right)

Một trường hợp đặc biệt là khi ta quan tâm đến phép chiếu trực giao có hạng bằng 1 lên một trục duy nhất q, khi đó ma trận chiếu trực giao tương ứng sẽ là:

P_q = qq^*    (10)

Phần bù của phép chiếu này là phép chiếu trực giao có hạng m-1, bỏ đi thành phần của phép chiếu theo chiều của q. Đây chính là phép chiếu lên không gian trực giao với q theo phương q:

P_{\perp q}=I-qq^*     (11)

Công thức (10) và (11) là cho trường hợp q là vector đơn vị. Trong trường hợp vector a bất kì, các ma trận chiếu tương ứng là:

P_a = \frac{aa^*}{a^*a}
P_{\perp a}=I-\frac{aa^*}{a^*a}     (12)

Đây chính là công thức phép chiếu mà ta đã gặp trong thuật toán Householder.

5. Phép chiếu với cơ sở bất kì

Trong phần trước, ta có thể tạo ra một phép chiếu trực giao lên không gian con của \mathbb{C}^m từ một cơ sở trực chuẩn. Tuy nhiên cho một cơ sở bất kì (không nhất thiết trực chuẩn), ta cũng có thể tạo được phép chiếu trực giao tương ứng.

Giả sử ta muốn xây dựng phép chiếu trực giao lên không gian con của \mathbb{C}^m sinh bởi tập \lbrace a_1, a_2, \cdots, a_n\rbrace độc lập tuyến tính. Gọi A là ma trận m\times n với các cột là các a_j.

Khi đó cho vector v\in \mathbb{C}^m, gọi y là hình chiếu của v lên range(A), thì vector y-v phải trực giao với các a_j, hay nói cách khác a_j^*\left(y-v\right)=0, \forall j. Vì y\in range(A) nên có thể viết y = Ax với x nào đó. Điều kiện trên trở thành a_j^*\left(Ax-v\right)=0, \forall j, viết tương đương là A^*\left(Ax-v\right)=0, hay A^*Ax = A^*v. Do A là ma trận hạng đủ nên A^*A không suy biến, ta có:

x=\left(A^*A\right)^{-1}A^*v.

Cuối cùng ảnh của v trên range(A)y=Ax = A\left(A^*A\right)^{-1}A^*v, do đó phép chiếu trực giao lên range(A) có thể biểu diễn bằng ma trận chiếu:

P = A\left(A^*A\right)^{-1}A^*     (13)

Để ý rằng đây là trường hợp nhiều chiều của (12). Ngoài ra khi A là ma trận trực chuẩn thì phần trong ngoặc trở thành ma trận đơn vị, và ta lại được phương trình (9).

Ví dụ

Cho ma trận A=\left[\begin{array}{cc}1&2\\\mathbf{0}&1\\1&\mathbf{0}\end{array}\right].

Phép chiếu vuông góc lên range(A) là:

P = A\left(A^*A\right)^{-1}A^* =\frac{1}{6}\left[\begin{array}{ccc}5&2&1\\2&2&-2\\1&-2&5\end{array}\right]

Cho điểm v = \left(1, 2, 3\right)^*, ảnh của v qua phép chiếu P là:

w = Pv = \left[\begin{array}{c}2\\\mathbf{0}\\2\end{array}\right]

6. Kết luận

Tóm lại trong bài này, cần nhớ những điểm sau:

  • Cho ma trận P thỏa P^2 = P thì P là một phép chiếu lên không gian range(P) theo phương null(P). Hai không gian con này là bù nhau: ta nói P chia không gian \mathbb{C}^m thành 2 không gian con bù.
  • Phép chiếu P gọi là trực giao khi và chỉ khi P là Hermitian: P^* = P. Khi đó range(P)null(P) là 2 không gian con trực giao.
  • Cho một vector a. Phép chiếu trực giao theo chiều a được biểu diễn bằng phương trình (12).
  • Cho một ma trận A tạo thành từ các cột độc lập tuyến tính. Phép chiếu trực giao lên range(A) được thể hiện bằng phương trình (13).
About these ads

2 Trackbacks to “Ma trận chiếu trong ĐSTT”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 61 other followers

%d bloggers like this: