Định lý Carathéodory (bao lồi)

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Minh họa cho định lý Carathéodory cho một hình vuông trong R2
Xem thêm các định lý Carathéodory khác

Trong hình học lồi, định lý Carathéodory khẳng định nếu điểm x trong Rd nằm trong bao lồi của tập hợp P, thì tồn tại một tập hợp con P′ của P gồm tối đa d+1 điểm sao cho x nằm trong bao lồi của P′. Một cách phát biểu tương đương là x nằm trong một r-đơn hình với các đỉnh thuộc P, trong đó r \leq  d. Kết quả này được đặt tên theo Constantin Carathéodory, người đã chứng minh định lý này năm 1911 cho trường hợp P compact.[1] Năm 1913, Ernst Steinitz mở rộng định lý Carathéodory cho mọi tập P trong Rd.[2]

Sau đây là một ví dụ. Ta xét tập hợp P = {(0,0), (0,1), (1,0), (1,1)} trong R2. Bao lồi của tập này là một hình vuông. Xét điểm x = (1/4, 1/4) nằm trong bao lồi của P. Ta có thể chọn tập {(0,0),(0,1),(1,0)} = P ′, với bao lồi là một hình tam giác chứa x và do đó định lý là đúng trong trường hợp này do |P′| = 3.

Chứng minh[sửa | sửa mã nguồn]

Giả sử x là một điểm trong bao lồi của P. Khi đó, xtổ hợp lồi của một tập hợp hữu hạn các điểm trong P:

\mathbf{x}=\sum_{j=1}^k \lambda_j \mathbf{x}_j

trong đó mọi xj đều thuộc P, λj là số dương, và \sum_{j=1}^k\lambda_j=1.

Giả sử k > d + 1 (nếu không ta có ngay điều phải chứng minh). Khi đó, các điểm x2 − x1,..., xk − x1phụ thuộc tuyến tính, nên tồn tại μ2,..., μk sao cho không phải tất cả chúng đều bằng 0 và

\sum_{j=2}^k \mu_j (\mathbf{x}_j-\mathbf{x}_1)=\mathbf{0}.

Nếu định nghĩa μ1 như sau

\mu_1:=-\sum_{j=2}^k \mu_j

thì

\sum_{j=1}^k \mu_j \mathbf{x}_j=\mathbf{0}
\sum_{j=1}^k \mu_j=0

và không phải tất cả μj đều bằng 0. Do đó tồn tại ít nhất một μj>0. Ta có,

\mathbf{x} = \sum_{j=1}^k \lambda_j \mathbf{x}_j-\alpha\sum_{j=1}^k \mu_j \mathbf{x}_j = \sum_{j=1}^k (\lambda_j-\alpha\mu_j) \mathbf{x}_j

cho mọi số thực α. Vì vậy đẳng thức trên là đúng khi chọn α như sau

 \alpha:=\min_{1\leq j \leq k} \left\{ \tfrac{\lambda_j}{\mu_j}:\mu_j>0\right\}=\tfrac{\lambda_i}{\mu_i}.

Ghi chú là α>0, và với mọi j từ 1 tới k,

\lambda_j-\alpha\mu_j \geq 0.

Ta nhận thấy λi − αμi = 0 theo cách chọn α. Vì vậy,

\mathbf{x} = \sum_{j=1}^k (\lambda_j-\alpha\mu_j) \mathbf{x}_j

trong đó mọi \lambda_j - \alpha \mu_j là không âm, tổng của chúng bằng 1, và thêm vào đó, \lambda_i-\alpha\mu_i=0. Nói cách khác, x là tổ hợp lồi của k-1 điểm trong P. Có thể lặp lại quá trình trên cho tới khi x là tổ hợp lồi của d + 1 điểm trong P.

Một cách chứng minh khác là sử dụng định lý Helly.

Xem thêm[sửa | sửa mã nguồn]

Ghi chú[sửa | sửa mã nguồn]

  1. ^ Carathéodory, C. (1911). “Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen”. Rendiconti del Circolo Matematico di Palermo 32: 193–217. 
  2. ^ Steinitz, Ernst (1913), “Bedingt konvergente Reihen und konvexe Systeme”, J. Reine Angew. Math. 143: 128–176, doi:10.1515/crll.1913.143.128 

Tài liệu tham khảo[sửa | sửa mã nguồn]

  • Danzer, L.; Grünbaum, B.; Klee, V. (1963), “Helly's theorem and its relatives”, Convexity, Proc. Symp. Pure Math. 7, American Mathematical Society, tr. 101–179 .
  • Eckhoff, J. (1993), “Helly, Radon, and Carathéodory type theorems”, Handbook of Convex Geometry A, B, Amsterdam: North-Holland, tr. 389–448 .

Liên kết ngoài[sửa | sửa mã nguồn]