نظرية فصل المستويات الفائقة

الموسوعة الحرة

في الهندسة ، تُعرف نظرية فصل المستويات الفائقة بأنها نظرية تتعلق بالمجموعات المحدبة المنفصلة في الفضاء الإقليدي ذي الأبعاد n . توجد عدة صيغ متشابهة إلى حد كبير. في إحدى صيغ النظرية، إذا كانت كلتا المجموعتين مغلقتين ، وكانت إحداهما على الأقل متراصة ، فإنه يوجد مستوى فائق بينهما، بل قد يوجد مستويان فائقان متوازيان بينهما يفصل بينهما فراغ. في صيغة أخرى، إذا كانت كلتا المجموعتين المحدبتين المنفصلتين مفتوحتين، فإنه يوجد مستوى فائق بينهما، ولكن ليس بالضرورة وجود فراغ. المحور المتعامد على المستوى الفائق الفاصل هو محور فاصل ، لأن الإسقاطات المتعامدة للأجسام المحدبة على هذا المحور منفصلة.

تُعزى نظرية فصل المستويات الفائقة إلى هيرمان مينكوفسكي . وتُعمم نظرية هان-باناش للفصل هذه النتيجة لتشمل الفضاءات المتجهة الطوبولوجية .

ومن النتائج ذات الصلة نظرية المستوى الفائق الداعم .

في سياق آلات المتجهات الداعمة ، يُعرف المستوى الفائق الأمثل للفصل أو المستوى الفائق ذو الهامش الأقصى بأنه مستوى فائق يفصل بين مجموعتين من النقاط ويزيد المسافة بينه وبين كلتا المجموعتين إلى أقصى حد. [ 1 ] [ 2 ] [ 3 ]

البيانات والإثباتات

نظرية فصل المستويات الفائقة [ 4 ] — ليكنأ{\displaystyle A}وب{\displaystyle B}ليكن مجموعتين جزئيتين محدبتين غير فارغتين منفصلتين منRن{\displaystyle \mathbb {R} ^{n}}إذن يوجد متجه غير صفريv{\displaystyle v}وعدد حقيقيج{\displaystyle c}بحيث

⟨x،v⟩≥ج و ⟨y،v⟩≤ج{\displaystyle \langle x,v\rangle \geq c\,{\text{ و }}\langle y,v\rangle \leq c}

للجميعx{\displaystyle x}فيأ{\displaystyle A}وy{\displaystyle y}فيب{\displaystyle B}أي، المستوى الفائق⟨⋅،v⟩=ج{\displaystyle \langle \cdot ,v\rangle =c}،v{\displaystyle v}المتجه العمودي، يفصلأ{\displaystyle A}وب{\displaystyle B}.

إذا كانت كلتا المجموعتين مغلقة، وكانت إحداهما على الأقل متراصة، فيمكن أن يكون الفصل صارمًا، أي⟨x،v⟩>ج1 و ⟨y،v⟩<ج2{\displaystyle \langle x,v\rangle >c_{1}\,{\text{ and }}\langle y,v\rangle <c_{2}}بالنسبة للبعضج1>ج2{\displaystyle c_{1}>c_{2}}

في جميع الحالات، افترضأ،ب{\displaystyle A,B}أن تكون مجموعات فرعية منفصلة وغير فارغة ومحدبة منRن{\displaystyle \mathbb {R} ^{n}}فيما يلي ملخص النتائج:

جدول ملخص
أ{\displaystyle A}ب{\displaystyle B}⟨x،v⟩{\displaystyle \langle x,v\rangle }⟨y،v⟩{\displaystyle \langle y,v\rangle }
≥ج{\displaystyle \geq c}≤ج{\displaystyle \leq c}
اتفاقية مغلقةمغلق>ج1{\displaystyle >c_{1}}<ج2{\displaystyle <c_{2}}معج2<ج1{\displaystyle c_{2}<c_{1}}
مغلقاتفاقية مغلقة>ج1{\displaystyle >c_{1}}<ج2{\displaystyle <c_{2}}معج2<ج1{\displaystyle c_{2}<c_{1}}
يفتح>ج{\displaystyle >c}≤ج{\displaystyle \leq c}
يفتحيفتح>ج{\displaystyle >c}<ج{\displaystyle <c}

يجب أن يكون عدد الأبعاد محدودًا. في الفضاءات ذات الأبعاد اللانهائية، توجد أمثلة على مجموعتين مغلقتين، محدبتين، ومنفصلتين لا يمكن فصلهما بواسطة مستوى فائق مغلق (مستوى فائق حيث تساوي دالة خطية متصلة ثابتًا ما) حتى بالمعنى الضعيف حيث لا تكون المتباينات صارمة. [ 5 ]

هنا، لا يمكن التهاون في شرط التراص في الفرضية؛ انظر مثالاً في قسم الأمثلة المضادة والوحدانية . ويمكن تعميم هذه الصيغة من نظرية الفصل لتشمل الأبعاد اللانهائية؛ ويُعرف هذا التعميم باسم نظرية هان-باناخ للفصل .

يستند البرهان إلى اللمة التالية:

اللمة — دعأ{\displaystyle A}وب{\displaystyle B}ليكن مجموعتين جزئيتين مغلقتين منفصلتين منRن{\displaystyle \mathbb {R} ^{n}}وافترضأ{\displaystyle A}متراصة. إذن توجد نقاطأ0∈أ{\displaystyle a_{0}\in A}وب0∈ب{\displaystyle b_{0}\in B}تقليل المسافة‖أ-ب‖{\displaystyle \|ab\|}زيادةأ∈أ{\displaystyle a\in A}وب∈ب{\displaystyle b\in B}.

برهان اللمة

يتركأ∈أ{\displaystyle a\in A}وب∈ب{\displaystyle b\in B}ليكن أي زوج من النقاط، وليكنر1=‖ب-أ‖{\displaystyle r_{1}=\|ba\|}. منذأ{\displaystyle A}مضغوطة، وهي موجودة داخل كرة مركزهاأ{\displaystyle a}ليكن نصف قطر هذه الكرةر2{\displaystyle r_{2}}. يتركS=ب∩بر1+ر2(أ)¯{\displaystyle S=B\cap {\overline {B_{r_{1}+r_{2}}(a)}}}أن يكون تقاطعب{\displaystyle B}مع كرة مغلقة نصف قطرهار1+ر2{\displaystyle r_{1}+r_{2}}حولأ{\displaystyle a}. ثمS{\displaystyle S}مضغوطة وغير فارغة لأنها تحتوي علىب{\displaystyle b}بما أن دالة المسافة متصلة، فإنه توجد نقاطأ0{\displaystyle a_{0}}وب0{\displaystyle b_{0}}المسافة‖أ0-ب0‖{\displaystyle \|a_{0}-b_{0}\|}هو الحد الأدنى لجميع أزواج النقاط فيأ×S{\displaystyle A\times S}يبقى أن نثبت ذلكأ0{\displaystyle a_{0}}وب0{\displaystyle b_{0}}في الواقع، يجب أن تكون المسافة هي أقصر مسافة بين جميع أزواج النقاط فيأ×ب{\displaystyle A\times B}لنفترض جدلاً أنه توجد نقاطأ′{\displaystyle a'}وب′{\displaystyle b'}بحيث‖أ′-ب′‖<‖أ0-ب0‖{\displaystyle \|a'-b'\|<\|a_{0}-b_{0}\|}ثم على وجه الخصوص،‖أ′-ب′‖<ر1{\displaystyle \|a'-b'\|<r_{1}}وبحسب متباينة المثلث،‖أ-ب′‖≤‖أ′-ب′‖+‖أ-أ′‖<ر1+ر2{\displaystyle \|ab'\|\leq \|a'-b'\|+\|aa'\|<r_{1}+r_{2}}. لذلكب′{\displaystyle b'}يحتوي علىS{\displaystyle S}وهذا يتناقض مع حقيقة أنأ0{\displaystyle a_{0}}وب0{\displaystyle b_{0}}كان الحد الأدنى للمسافةأ×S{\displaystyle A\times S}.◻{\displaystyle \square }

دليل توضيحي.
برهان النظرية

سنثبت الحالة الثانية أولاً. (انظر الرسم التوضيحي.)

مدونة WLOG،أ{\displaystyle A}هي متراصة. وبحسب اللمة، توجد نقاطأ0∈أ{\displaystyle a_{0}\in A}وب0∈ب{\displaystyle b_{0}\in B}بمسافة دنيا بين كل منهما. بما أنأ{\displaystyle A}وب{\displaystyle B}إذا كانت منفصلة، ​​فلديناأ0≠ب0{\displaystyle a_{0}\neq b_{0}}الآن، قم بإنشاء مستويين فائقينلأ،لب{\displaystyle L_{A},L_{B}}عمودي على القطعة المستقيمة[أ0،ب0]{\displaystyle [a_{0},b_{0}]}، معلأ{\displaystyle L_{A}}عيرأ0{\displaystyle a_{0}}ولب{\displaystyle L_{B}}عيرب0{\displaystyle b_{0}}نزعم أن لاأ{\displaystyle A}ولاب{\displaystyle B}يدخل الفراغ بينلأ،لب{\displaystyle L_{A},L_{B}}وبالتالي فإن المستويات الفائقة العمودية على(أ0،ب0){\displaystyle (a_{0},b_{0})}استيفاء متطلبات النظرية.

جبريًا، المستويات الفائقةلأ،لب{\displaystyle L_{A},L_{B}}يتم تعريفها بواسطة المتجهv:=ب0-أ0{\displaystyle v:=b_{0}-a_{0}}وثابتانجأ:=⟨v،أ0⟩<جب:=⟨v،ب0⟩{\displaystyle c_{A}:=\langle v,a_{0}\rangle <c_{B}:=\langle v,b_{0}\rangle }بحيثلأ={x:⟨v،x⟩=جأ}،لب={x:⟨v،x⟩=جب}{\displaystyle L_{A}=\{x:\langle v,x\rangle =c_{A}\},L_{B}=\{x:\langle v,x\rangle =c_{B}\}}ندّعي أن∀أ∈أ،⟨v،أ⟩≤جأ{\displaystyle \forall a\in A,\langle v,a\rangle \leq c_{A}}و∀ب∈ب،⟨v،ب⟩≥جب{\displaystyle \forall b\in B,\langle v,b\rangle \geq c_{B}}.

لنفترض جدلاً أن هناك نقطة ماأ∈أ{\displaystyle a\in A}بحيث ⟨v،أ⟩>جأ{\displaystyle \langle v,a\rangle >c_{A}}ثم بما أن تدرج الدالةو(z)=‖z-ب0‖2{\displaystyle f(z)=\|z-b_{0}\|^{2}}يُعطى بواسطة∇و(z)=2(z-ب0){\displaystyle \nabla f(z)=2(z-b_{0})}وبالتالي، فإن المشتق الاتجاهي∇أ-أ0و(أ0){\displaystyle \nabla _{a-a_{0}}f(a_{0})}له نفس الإشارة مثل⟨أ-أ0،2(أ0-ب0)⟩=-2⟨أ-أ0،v⟩{\displaystyle \langle a-a_{0},2(a_{0}-b_{0})\rangle =-2\langle a-a_{0},v\rangle }وهو أمر سلبي. لذا بالنسبة لقيم صغيرة بما فيه الكفايةϵ>0{\displaystyle \epsilon >0}النقطةأ′=أ0+ϵ(أ-أ0){\displaystyle a'=a_{0}+\epsilon (a-a_{0})}يرضيو(أ′)<و(أ0){\displaystyle f(a')<f(a_{0})}وهذا يتناقض مع اختيارأ0{\displaystyle a_{0}}منذأ′∈أ{\displaystyle a'\in A}عن طريق التحدب. وتُظهر حجة مماثلة∀ب∈ب،⟨v،ب⟩≥جب{\displaystyle \forall b\in B,\langle v,b\rangle \geq c_{B}}.

والآن ننتقل إلى الحالة الأولى.

تعامل مع كلا الأمرينأ،ب{\displaystyle A,B}من الداخل بواسطةأ1⊆أ2⊆⋯⊆أ{\displaystyle A_{1}\subseteq A_{2}\subseteq \cdots \subseteq A}وب1⊆ب2⊆⋯⊆ب{\displaystyle B_{1}\subseteq B_{2}\subseteq \cdots \subseteq B}بحيث يكون كلأك،بك{\displaystyle A_{k},B_{k}}مغلق ومضغوط، والاتحادات هي الأجزاء الداخلية النسبية.رهـلأنانت(أ)،رهـلأنانت(ب){\displaystyle \mathrm {relint} (A),\mathrm {relint} (B)}(انظر الصفحة الداخلية ذات الصلة لمزيد من التفاصيل.)

أما في الحالة الثانية، فلكل زوجأك،بك{\displaystyle A_{k},B_{k}}يوجد متجه وحدةvك{\displaystyle v_{k}}والعدد الحقيقيجك{\displaystyle c_{k}}بحيث⟨vك،أك⟩<جك<⟨vك،بك⟩{\displaystyle \langle v_{k},A_{k}\rangle <c_{k}<\langle v_{k},B_{k}\rangle }.

بما أن الكرة الوحدة متراصة، يمكننا اختيار متتالية جزئية متقاربة، بحيثvك→v{\displaystyle v_{k}\to v}. يتركجأ:=رشفةأ∈أ⟨v،أ⟩،جب:=معلوماتب∈ب⟨v،ب⟩{\displaystyle c_{A}:=\sup _{a\in A}\langle v,a\rangle ,c_{B}:=\inf _{b\in B}\langle v,b\rangle }نزعم أنجأ≤جب{\displaystyle c_{A}\leq c_{B}}وبالتالي الفصلأ،ب{\displaystyle A,B}.

لنفترض عكس ذلك، إذن يوجد شيء ماأ∈أ،ب∈ب{\displaystyle a\in A,b\in B}بحيث⟨v،أ⟩>⟨v،ب⟩{\displaystyle \langle v,a\rangle >\langle v,b\rangle }ثم بما أنvك→v{\displaystyle v_{k}\to v}، بالنسبة للكبير بما فيه الكفايةك{\displaystyle k}لدينا⟨vك،أ⟩>⟨vك،ب⟩{\displaystyle \langle v_{k},a\rangle >\langle v_{k},b\rangle }، تناقض.

بما أن المستوى الفاصل لا يمكنه أن يتقاطع مع الأجزاء الداخلية للمجموعات المحدبة المفتوحة، فإن لدينا نتيجة منطقية:

نظرية الفصل الأولى - ليكنأ{\displaystyle A}وب{\displaystyle B}ليكن مجموعتين محدبتين غير فارغتين منفصلتين. إذاأ{\displaystyle A}إذا كانت مفتوحة، فإنه يوجد متجه غير صفريv{\displaystyle v}والعدد الحقيقيج{\displaystyle c}بحيث

⟨x،v⟩>ج و ⟨y،v⟩≤ج{\displaystyle \langle x,v\rangle >c\,{\text{ and }}\langle y,v\rangle \leq c}

للجميعx{\displaystyle x}فيأ{\displaystyle A}وy{\displaystyle y}فيب{\displaystyle B}إذا كانت كلتا المجموعتين مفتوحتين، فإنه يوجد متجه غير صفريv{\displaystyle v}والعدد الحقيقيج{\displaystyle c}بحيث

⟨x،v⟩>ج و ⟨y،v⟩<ج{\displaystyle \langle x,v\rangle >c\,{\text{ and }}\langle y,v\rangle <c}

للجميعx{\displaystyle x}فيأ{\displaystyle A}وy{\displaystyle y}فيب{\displaystyle B}.

حالة مع تقاطعات محتملة

إذا كانت المجموعاتأ،ب{\displaystyle A,B}إذا كانت هناك تقاطعات محتملة، ولكن الأجزاء الداخلية النسبية منفصلة، ​​فإن برهان الحالة الأولى لا يزال ساريًا دون تغيير، مما ينتج عنه:

نظرية الفصل الثانية — ليكنأ{\displaystyle A}وب{\displaystyle B}ليكن مجموعتين جزئيتين محدبتين غير فارغتين منRن{\displaystyle \mathbb {R} ^{n}}مع وجود دواخل نسبية منفصلة. عندئذٍ يوجد متجه غير صفريv{\displaystyle v}وعدد حقيقيج{\displaystyle c}بحيث

⟨x،v⟩≥ج و ⟨y،v⟩≤ج{\displaystyle \langle x,v\rangle \geq c\,{\text{ and }}\langle y,v\rangle \leq c}

على وجه الخصوص، لدينا نظرية المستوى الفائق الداعم .

نظرية المستوى الفائق الداعم — إذاأ{\displaystyle A}هي مجموعة محدبة فيRن،{\displaystyle \mathbb {R} ^{n},}وأ0{\displaystyle a_{0}}هي نقطة على حدودأ{\displaystyle A}إذن، يوجد مستوى فائق داعم منأ{\displaystyle A}يحتوي علىأ0{\displaystyle a_{0}}.

دليل

إذا كان مدى أفيني لـأ{\displaystyle A}ليس كل شيءRن{\displaystyle \mathbb {R} ^{n}}ثم قم بتمديد الامتداد الأفيني إلى مستوى فائق داعم. وإلا،رهـلأنانت(أ)=أنانت(أ){\displaystyle \mathrm {relint} (A)=\mathrm {int} (A)}منفصل عنرهـلأنانت({أ0})={أ0}{\displaystyle \mathrm {relint} (\{a_{0}\})=\{a_{0}\}}لذا، قم بتطبيق النظرية المذكورة أعلاه.

عكس النظرية

لاحظ أن وجود مستوى فائق يفصل بين مجموعتين محدبتين فقط بالمعنى الضعيف، حيث تكون المتباينتان غير صارمتين، لا يعني بالضرورة أن المجموعتين منفصلتان. فمن الممكن أن تحتوي كلتا المجموعتين على نقاط تقع على المستوى الفائق.

الأمثلة المضادة والتفرد

لا تنطبق النظرية إذا لم يكن أحد الجسمين محدبًا.

إذا لم يكن أحد المستويين A أو B محدبًا، فهناك العديد من الأمثلة المضادة المحتملة. على سبيل المثال، يمكن أن يكون A و B دائرتين متحدتي المركز. ومن الأمثلة المضادة الأكثر دقة أن يكون كل من A و B مغلقين ولكن ليس أي منهما متراصًا. على سبيل المثال، إذا كان A نصف مستوى مغلقًا وكان B محصورًا بأحد أذرع قطع زائد، فلا يوجد مستوى فائق فاصل تمامًا.

أ={(x،y):x≤0}{\displaystyle A=\{(x,y):x\leq 0\}}
ب={(x،y):x>0،y≥1/x}. {\displaystyle B=\{(x,y):x>0,y\geq 1/x\}.\ }

(مع ذلك، وبحسب مثال من النظرية الثانية، يوجد مستوى فائق يفصل بين باطنيهما). يوجد نوع آخر من الأمثلة المضادة حيث يكون A متراصًا و B مفتوحًا. على سبيل المثال، يمكن أن يكون A مربعًا مغلقًا وB مربعًا مفتوحًا يلامس A.

في الصيغة الأولى من النظرية، من الواضح أن المستوى الفاصل ليس فريدًا أبدًا. أما في الصيغة الثانية، فقد يكون فريدًا أو غير فريد. من الناحية الفنية، لا يكون المحور الفاصل فريدًا أبدًا لأنه قابل للانتقال؛ في الصيغة الثانية من النظرية، يمكن أن يكون المحور الفاصل فريدًا حتى الانتقال.

تُقدّم زاوية القرن مثالاً مضاداً جيداً للعديد من فواصل المستويات الفائقة. على سبيل المثال، فيR2{\displaystyle \mathbb {R} ^{2}}، القرص الواحد منفصل عن الفترة المفتوحة((1،0)،(1،1)){\displaystyle ((1,0),(1,1))}لكن الخط الوحيد الذي يفصل بينهما يحتوي على كامل((1،0)،(1،1)){\displaystyle ((1,0),(1,1))}وهذا يدل على أنه إذاأ{\displaystyle A}مغلق وب{\displaystyle B}إذا كانت المنطقة مفتوحة نسبياً ، فلا يوجد بالضرورة فصل صارم بينب{\displaystyle B}لكن، إذاأ{\displaystyle A}إذا كان متعدد السطوح محدبًا مغلقًا، فإن هذا الفصل موجود. [ 6 ]

المزيد من الخيارات

يمكن فهم مبرهنة فاركاس والنتائج ذات الصلة على أنها نظريات فصل المستويات الفائقة عندما يتم تعريف الأجسام المحدبة بواسطة عدد محدود من المتباينات الخطية.

قد يتم العثور على المزيد من النتائج. [ 6 ]

يُستخدم في اكتشاف التصادم

في مجال اكتشاف التصادم ، تُستخدم نظرية فصل المستويات الفائقة عادةً بالشكل التالي:

نظرية المحور الفاصل - يكون الجسمان المحدبان المغلقان منفصلين إذا كان هناك خط ("المحور الفاصل") تكون إسقاطات الجسمين عليه منفصلة.

بغض النظر عن الأبعاد، فإن المحور الفاصل يكون دائمًا خطًا. على سبيل المثال، في الفضاء ثلاثي الأبعاد، يتم فصل الفضاء بواسطة مستويات، لكن المحور الفاصل يكون عموديًا على المستوى الفاصل.

يمكن تطبيق نظرية المحور الفاصل للكشف السريع عن التصادم بين شبكات المضلعات. يُستخدم اتجاه كل وجه عموديًا أو اتجاه ميزة أخرى كمحور فاصل. تجدر الإشارة إلى أن هذا يُنتج محاور فاصلة محتملة، وليس خطوطًا/مستويات فاصلة.

في الفضاء ثلاثي الأبعاد، لن يؤدي استخدام متجهات السطح العمودية وحدها إلى فصل بعض حالات عدم تصادم الحواف. لذا، يلزم استخدام محاور إضافية، تتكون من حاصل الضرب الاتجاهي لأزواج من الحواف، محور واحد مأخوذ من كل جسم. [ 7 ]

لزيادة الكفاءة، يمكن حساب المحاور المتوازية كمحور واحد.

انظر أيضاً

ملحوظات

  1. ↑ هاستي، تريفور ؛ تيبشيراني، روبرت ؛ فريدمان، جيروم (2008). عناصر التعلم الإحصائي  : التنقيب عن البيانات، والاستدلال، والتنبؤ (ملف PDF) (الطبعة الثانية  ). نيويورك: سبرينغر. الصفحات 129-135 . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 10 أبريل 2019. 
  2. ↑ ويتن، إيان هـ.؛ فرانك، إيبي؛ هول، مارك أ.؛ بال، كريستوفر ج. (2016). استخراج البيانات: أدوات وتقنيات عملية للتعلم الآلي ( الطبعة الرابعة). مورغان كوفمان. ص 253-254 . ISBN   9780128043578.
  3. ↑ دايزنروث، مارك بيتر؛ فيصل، أ. ألدو؛ أونغ، تشنغ سون (2020). الرياضيات للتعلم الآلي . مطبعة جامعة كامبريدج. ص 337-338 . ISBN  978-1-108-45514-5.
  4. ^ بويد وفاندنبيرج 2004 ، التمرين 2.22.
  5. ↑ حاييم بريزيس ، التحليل الوظيفي، فضاءات سوبوليف والمعادلات التفاضلية الجزئية ، 2011، الملاحظة 4، ص 7.
  6. 1 2 ستوير، جوزيف؛ ويتزغال، كريستوف (1970). التحدب والتحسين في الأبعاد المحدودة 1. سبرينغر برلين، هايدلبرغ. (2.12.9). doi : 10.1007/978-3-642-46216-0 . ISBN 978-3-642-46216-0.
  7. ↑ "الرياضيات المتجهة المتقدمة" .

مراجع

  • بويد، ستيفن ب.؛ فاندنبيرغ، ليفين (2004). التحسين المحدب (ملف PDF) . مطبعة جامعة كامبريدج. ISBN 978-0-521-83378-3.
  • غولشتاين، إي جي؛ تريتياكوف، إن في (1996). لاغرانجيات معدلة وخرائط رتيبة في التحسين . نيويورك: وايلي. ص  6. ISBN 0-471-54821-9.{{cite book}}: CS1 maint: publisher location ( link )
  • شيميزو، كيوتاكا؛ إيشيزوكا، يو؛ بارد، جوناثان ف. (1997). البرمجة الرياضية غير القابلة للتفاضل وذات المستويين . بوسطن: دار نشر كلوير الأكاديمية. ص  19. ISBN 0-7923-9821-1.{{cite book}}: CS1 maint: publisher location ( link )
  • سلطان، ف. (2021). خصائص الدعم والفصل للمجموعات المحدبة في الأبعاد المحدودة . مجلة إكستراكت ماث. المجلد 36، العدد 2، 241-278.