CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Tập lồi (1) – Định nghĩa và một số ví dụ

Posted by Trần Quốc Long on Tháng Hai 10, 2008

Định nghĩa (tập lồi): Tập X\subset \mathbb{R}^n gọi là tập lồi nếu

x,y\in X\Rightarrow \lambda x+(1-\lambda)y\in X, \forall \lambda\in [0,1]

Nghĩa là nếu x,y\in X thì đoạn thẳng \left[x,y\right]\in X.

Ví dụ:

  1. \mathbb{R}^n, \emptyset, \{x\} là các tập lồi.
  2. \{x:a^Tx\leq b\} là tập lồi, nửa không gian ngăn cách bởi đường thẳng a^Tx=b .

Định nghĩa (tập affine): Tập X\subset \mathbb{R}^n gọi là tập affine nếu

x,y\in X\Rightarrow \lambda x+(1-\lambda)y\in X, \forall \lambda\in\mathbb{R}

Nghĩa là nếu x,y\in X thì đường thẳng đi qua x,y cũng nằm trong X.

Định lý (Tính chất của tập affine):

  1. Tập affine là tập lồi
  2. Nếu X affine vàa\in X, tập L=\{y:\exists x\in X, y=x-a\} là không gian con của \mathbb{R}^n=X-a, đồng thời L là duy nhất đối với X không phụ thuộc vào a. Ta cũng viết X=a+L.
  3. Tập X là tập affine nếu và chỉ nếu \exists A,b sao cho X=\{x:Ax=b\}.

Chứng minh (1): Đường thẳng qua x,y chứa đoạn thẳng \left[x,y\right] nên tính chất này là hiển nhiên.

Chứng minh (2): Nếu y\in L, suy ra y=x-a, ta có \lambda y=\lambda x-\lambda a=\lambda x+(1-\lambda)a-a\in L\lambda x+(1-\lambda)a\in X.

Nếu y_1,y_2\in L, suy ra y_1=x_1-a, y_2=x_2-a, ta cóy_1+y_2=(x_1+x_2)-2a=2\displaystyle\frac{x_1+x_2}{2}-a-a\in L2\displaystyle\frac{x_1+x_2}{2}-a\in X.

Để chứng minh L là duy nhất, xét L_1=X-a_1,L_2=X-a_2 với a_1\neq a_2\in X. Xét y\in L_1, suy ra

y=x-a_1=x-a_2+a_2-a_1

với x\in X. Rõ ràng x-a_2\in L_2a_2-a_1\in L_2a_1-a_2\in L_2, suy ra y\in L_2, tức là L_1\subset L_2. Tương tự ta cũng có L_2\subset L_1. Vậy L_1=L_2.

Chứng minh (3):

\Rightarrow“: Hiển nhiên.

\Leftarrow“: VìX=a+L, xét không gian trực giao L^\perp của L. Không gian này có hệ cơ sở a_1,\ldots,a_k. Đặt

A=\left[\begin{array}{c}a_1^T\\\vdots\\a_k^T\end{array}\right]

Ta có

Ax=\left[\begin{array}{c}a_1^Tx\\\vdots\\a_k^Tx\end{array}\right]=\left[\begin{array}{c}a_1^Ta\\\vdots\\a_k^Ta\end{array}\right]=b

Định nghĩa (hình cầu): Hình cầu tâm a, bán kính r trong \mathbb{R}^n là tập \{x:||x-a||\leq r\} với ||.|| là một chuẩn nào đó trong \mathbb{R}^n.

Nhận xét: Dễ dàng chứng minh được hình cầu là một tập đóng, lồi và giới nội.

Định nghĩa (lân cận \epsilon): Lân cận \epsilon của tập X là tập Y=\{y:\exists x\in X, ||x-y||\leq\epsilon\}.

Định lý: Lân cận \epsilon của tập lồiX là tập lồi.

Chứng minh: Xét x,y\in Y, nghĩa là tồn tạix',y'\in X sao cho||x-x'||\leq\epsilon,||y-y'||\leq\epsilon. Giả sử z=\lambda x+(1-\lambda)y, 0<\lambda<1. Ta sẽ chứng minh khoảng cách từ z đến z'=\lambda x'+(1-\lambda)y' không lớn hơn \epsilon. Thật vậy

||z-z'||=||\lambda x+(1-\lambda)y-(\lambda x'+(1-\lambda)y')||=||\lambda(x-x')+(1-\lambda)(y-y')||

\leq ||\lambda(x-x')||+||(1-\lambda)(y-y')||\leq |\lambda|||x-x'||+|(1-\lambda)|||y-y'||\leq\epsilon

z'\in X nênz\in Y.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: