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

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
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]