تصویری از قضیه Carathéodory برای یک مربع در R 2

در هندسه محدب ، قضیه کاراتودوری بیان می کند که اگر یک نقطه x از R d در پوسته محدب یک مجموعه P قرار داشته باشد ، آنگاه x را می توان به عنوان ترکیبی محدب از حداکثر  نقاط d + 1 در P. نوشت: یعنی زیر مجموعه ای وجود دارد. P ′ از P متشکل از d  + 1 یا نقاط کمتری است به طوری که x در پوسته محدب P P قرار دارد. معادل ، x در یک r - سیمپلکس با رئوس در P قرار دارد ، که در آن قرار داردr \ leq d. کوچکترین r که باعث می شود آخرین جمله برای هر x در بدنه محدب P معتبر باشد ، به عنوان تعداد P از کاراتودوری تعریف می شود . بسته به خاصیت P ، مرزهای بالایی پایین تر از آن که توسط قضیه کاراتودوری ارائه شده است می توان بدست آورد. [1] توجه داشته باشید که P نیازی نیست که خودش محدب باشد. نتیجه این امر این است که P P همیشه می تواند در P افراطی باشد ، زیرا نقاط غیر انتهای ممکن است بدون تغییر در عضویت x در بدنه محدب از P خارج شوند .

قضایای مشابه هلی و رادون از نزدیک با قضیه کاراتودوری ارتباط دارند: از قضیه اخیر می توان برای اثبات قضایای پیشین استفاده کرد و برعکس. [2]

نتیجه برای کنستانتین کاراتودوری نامگذاری شده است ، که قضیه را در سال 1907 اثبات کرد وقتی که P جمع و جور است. [3] در سال 1914 ارنست اشتاینیتز قضیه کاراتودوری را برای هر مجموعه P در R d گسترش داد . [4]

 

فهرست

مثال [ ویرایش ]

مجموعه ای از P = {(0،0) ، (0،1) ، (1،0) ، (1،1)} Consider را در نظر بگیرید که زیر مجموعه ای از R 2 است . بدنه محدب این مجموعه مربع است. اکنون یک نکته (x = (1/4 ، 1/4 را در نظر بگیرید که در پوسته محدب P قرار دارد . سپس می توانیم یک مجموعه {(0،0) ، (0،1) ، (1،0)} = P construc بسازیم ، پوسته محدب آن مثلث است و x را محصور می کند ، بنابراین قضیه برای این مثال کار می کند ، از | پ ′ | = 3. ممکن است به تجسم قضیه کاراتودوری در 2 بعد کمک کند ، به عنوان اینکه می توانیم مثلثی متشکل از نقاط از P را بسازیم که هر نقطه ای را در P محصور می کند .

اثبات [ ویرایش ]

بگذارید x یک نقطه در پوسته محدب P باشد. سپس، X است ترکیب محدب از تعداد متناهی از نقاط در P  :

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

جایی که هر x j در P است ، هر λ j (مثبت) است ، و\ sum_ {j = 1} ^ k \ lambda_j = 1.

فرض کنید k > d  + 1 (در غیر این صورت ، چیزی برای اثبات وجود ندارد). سپس بردارهای x 2  -  x 1 ، ... ، x k  -  x 1 به طور خطی وابسته هستند ،

بنابراین بندی واقعی وجود دارد μ 2 ، ...، μ K ، نه همه صفر، به طوری که

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

اگر μ 1 به عنوان تعریف شده باشد

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

سپس

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

\ sum_ {j = 1} ^ k \ mu_j = 0

و نه همه از μ J برابر با صفر است. بنابراین، حداقل یک μ J  > 0. سپس،

\ 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

برای هر α α واقعی . به طور خاص ، اگر a به عنوان تعریف شده باشد ، این برابری وجود خواهد داشت

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

توجه داشته باشید که α > 0 و برای هر j بین 1 و k ،

\ lambda_j- \ alpha \ mu_j \ geq 0.

به طور خاص ، λ i  -  αμ i = 0 با تعریف α . از این رو،

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

هر \ lambda_j - \ alpha \ mu_j غیر منافع است ، جمع آنها یک است و علاوه بر این ، \ lambda_i- \ alpha \ mu_i = 0. به عبارت دیگر ، x به عنوان ترکیبی محدب از حداکثر K -1 از P نشان داده شده است . این فرایند را می توان تا زمانی که x به عنوان ترکیبی محدب از حداکثر  نقاط d + 1 در P نشان داده شود ، تکرار شود .

اثبات جایگزین از قضیه هلی یا قضیه Perron-Frobenius استفاده می کند . [5] [6]

کلیات [ ویرایش ]

قضیه رنگارنگ کاراتودوری [ ویرایش ]

ااگرA1, ..., Ad+1مجموعه در a1 ∈ A1, ..., ad+1 ∈ Ad+1. اگر این مجموعه ها یک نقطه مشترک a را در شاخه های محدب خود به اشتراک بگذارند ، یک مجموعه{T = {a1, ..., ad+1  وجود دارد به گونه ای که پوسته محدب T شامل یک نقطه a باشد. [7]

با مشاهده مجموعه های  A1, ..., Ad+1به عنوان رنگ های مختلف ، مجموعه T توسط نقاطی از همه رنگ ها ساخته می شود ، از این رو "رنگارنگ" به نام قضیه. [8]

منبع

https://en.wikipedia.org/wiki/Carath%C3%A9odory%27s_theorem_(convex_hull)