مقالات

7.5.1: معادلات أويلر للنقاط الفردية العادية (تمارين) - الرياضيات


Q7.4.1

في تمارين 7.4.1-7.4.18 أوجد الحل العام لمعادلة أويلر المحددة على ((0، infty) ).

1. (س ^ 2 ص '+ 7 س ص' + 8 ص = 0 )

2. (س ^ 2 ص "- 7 س ص" + 7 ص = 0 )

3. (x ^ 2y '' - xy '+ y = 0 )

4. (س ^ 2 ص '+ 5 س ص' + 4 ص = 0 )

5. (س ^ 2y '+ س ص' + ص = 0 )

6. (س ^ 2 ص "- 3 س ص" + 13 ص = 0 )

7. (س ^ 2 ص '+ 3 س ص'-3 ص = 0 )

8. (12x ^ 2y '' - 5xy '' + 6y = 0 )

9. (4x ^ 2y '+ 8xy' + y = 0 )

10. (3x ^ 2y '' - xy '+ y = 0 )

11. (2x ^ 2y '' - 3xy '+ 2y = 0 )

12. (س ^ 2 ص '+ 3 س ص' + 5 ص = 0 )

13. (9x ^ 2y '' + 15xy '+ y = 0 )

14. (س ^ 2 ص '' - س ص '+ 10 ص = 0 )

15. (س ^ 2 ص "- 6 ص = 0 )

16. (2x ^ 2y '' + 3xy'-y = 0 )

17. (س ^ 2 ص '' - 3 س ص '+ 4 ص = 0 )

18. (2x ^ 2y '' + 10xy '+ 9y = 0 )

Q7.4.2

19.

  1. قم بتكييف دليل النظرية 7.4.3 لإظهار أن (y = y (x) ) يفي بمعادلة أويلر [ax ^ 2y '' + bxy '+ cy = 0 tag {A} ] on (( - infty، 0) ) إذا وفقط إذا (Y (t) = y (-e ^ t) ) [a {d ^ 2Y over dt ^ 2} + (ba) {dY over dt } + cY = 0. nonumber ] في ((- infty، infty) ).
  2. استخدم (أ) لتوضيح أن الحل العام للمعادلة A في ((- infty، 0) ) هو [ start {align} y & = c_1 | x | ^ {r_1} + c_2 | x | ^ { r_2} mbox {if $ r_1 $ و $ r_2 $ أرقام حقيقية مميزة ؛ } y & = | x | ^ {r_1} (c_1 + c_2 ln | x |) mbox {if $ r_1 = r_2 $؛ } y & = | x | ^ { lambda} left [c_1 cos left ( omega ln | x | right) + c_2 sin left ( omega ln | x | right) right] mbox {if $ r_1، r_2 = lambda pm i omega $ with $ omega> 0 $}. end {align} nonumber ]

20. استخدم تقليل الترتيب لإظهار ذلك إذا

[ar (r-1) + br + c = 0 nonumber ]

له جذر متكرر (r_1 ) ثم (y = x ^ {r_1} (c_1 + c_2 ln x) ) هو الحل العام لـ

[ax ^ 2y '' + bxy '+ cy = 0 nonumber ]

على ((0، infty) ).

21. حل غير بديهي

[P_0 (x) y '' + P_1 (x) y '+ P_2 (x) y = 0 nonumber ]

يقال أن يكون تذبذبي على فاصل ((أ ، ب) ) إذا كان يحتوي على عدد لا نهائي من الأصفار في ((أ ، ب) ). وإلا يقال أن (ص ) غير متذبذب في ((أ ، ب) ). تبين أن المعادلة

[x ^ 2y '' + ky = 0 quad (k = ؛ mbox {Constant}) nonumber ]

لديه حلول تذبذبية على ((0، infty) ) إذا وفقط إذا (k> 1/4 ).

22. في المثال 7.4.2 ، رأينا أن (x_0 = 1 ) و (x_0 = -1 ) نقاط مفردة منتظمة في معادلة Legendre

[(1-x ^ 2) y '- 2xy' + alpha ( alpha + 1) y = 0. علامة {A} ]

  1. قدم المتغيرات الجديدة (t = x-1 ) و (Y (t) = y (t + 1) ) ، وأظهر أن (y ) هو حل (A) إذا وفقط إذا (Y ) هو حل [t (2 + t) {d ^ 2Y over dt ^ 2} +2 (1 + t) {dY over dt} - alpha ( alpha + 1) Y = 0، nonumber ] التي لها نقطة مفردة منتظمة عند (t_0 = 0 ).
  2. قدم المتغيرات الجديدة (t = x + 1 ) و (Y (t) = y (t-1) ) ، وأظهر أن (y ) هو حل (A) إذا وفقط إذا (Y ) هو حل [t (2-t) {d ^ 2Y over dt ^ 2} +2 (1-t) {dY over dt} + alpha ( alpha + 1) Y = 0، nonumber ] التي لها نقطة مفردة منتظمة عند (t_0 = 0 ).

23. لنفترض أن (P_0، P_1 ) و (P_2 ) متعددي الحدود بدون عامل مشترك ، وافترض أن (x_0 ne0 ) نقطة فردية في

[P_0 (x) y '+ P_1 (x) y' + P_2 (x) y = 0. علامة {A} ]

دع (t = x-x_0 ) و (Y (t) = y (t + x_0) ).

  1. بيّن أن (y ) هو حل لـ (A) إذا وفقط إذا كان (Y ) هو حل [R_0 (t) {d ^ 2Y over dt ^ 2} + R_1 (t) {dY أكثر من dt} + R_2 (t) Y = 0. tag {B} ] حيث [R_i (t) = P_i (t + x_0)، quad i = 0،1،2. nonumber ]
  2. بيّن أن (R_0 ) و (R_1 ) و (R_2 ) متعددو الحدود في (t ) بدون عوامل مشتركة ، و (R_0 (0) = 0 ) ؛ وبالتالي ، (t_0 = 0 ) هي نقطة مفردة من (ب).

7.5.1: معادلات أويلر للنقاط الفردية العادية (تمارين) - الرياضيات

أنت على وشك امسح عملك في هذا النشاط. هل انت متأكد من أنك تريد أن تفعل هذا؟

نسخة محدثة متوفرة

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

محرر التعبير الرياضي

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

طريقة فروبينيوس الثالث

ناقشنا في Trench 7.5 و 7.6 طرق إيجاد حلول Frobenius لمعادلة الدرجة الثانية الخطية المتجانسة بالقرب من نقطة مفردة عادية في الحالة التي تحتوي فيها المعادلة غير الرسمية على جذر متكرر أو جذور حقيقية مميزة لا تختلف بعدد صحيح. في هذا القسم ، نأخذ في الاعتبار الحالة التي يكون فيها للمعادلة غير المباشرة جذور حقيقية مميزة تختلف بعدد صحيح. سنقتصر مناقشتنا على المعادلات التي يمكن كتابتها على شكل

أو حيث تختلف جذور المعادلة الأساسية بعدد صحيح موجب.

نبدأ بنظرية توفر مجموعة أساسية من حلول المعادلات بالصيغة (مكافئ: 7.7.1).

نظرية الإثبات: 7.5.3 تدل على ذلك. سوف نظهر ذلك الآن. نظرًا لأنه عامل تشغيل خطي ، فهذا يعادل إظهار أنه للتحقق من ذلك ، سنبين ذلك وهذا يعني أنه منذ استبدال (eq: 7.7.7) و (eq: 7.7.8) في (eq: 7.7.7). 6) واستخدام عوائد (مكافئ: 7.7.4)

سنثبت (مكافئ: 7.7.8) أولاً. من Theorem thmtype: 7.6.1 ، تحديد وتذكر ذلك والعائد

نظرًا لأن المعادلة الأساسية هي جذورها ، يمكن كتابة كثير الحدود على أنه تمييز ينتج عن ذلك ، لذلك (مكافئ: 7.7.9) يعني (مكافئ: 7.7.8).

قبل إثبات (eq: 7.7.7) ، نلاحظ أولاً أنه تم تعريفه جيدًا بواسطة (eq: 7.7.3) لأنه بالنسبة لقيم. ومع ذلك ، لا يمكننا تعريف بـ (eq: 7.7.3) ، منذ ذلك الحين. للراحة ، نحدد ل. ثم من Theorem thmtype: 7.5.1 ،

أين و إذا ، إذن (eq: 7.7.3) يعني ذلك. إذا ، إذن بسبب. لذلك (eq: 7.7.10) يقلل إلى منذ ، وهذا يعني (eq: 7.7.7).

نترك الدليل الذي هو مجموعة أساسية كتدريب.

لحساب المعامِلات وفي ، نضع في (مكافئ: 7.7.13) ونطبق معادلة التكرار الناتجة ، وبالتالي ،

نستخدم التفاضل اللوغاريتمي للحصول على. من (مكافئ: 7.7.14) ، وبالتالي التمييز فيما يتعلق بالإنتاجية ، فإن التحديد هنا واسترجاع (مكافئ: 7.7.15)

استبدال هذا في عوائد (مكافئ: 7.7.16)

إذا كانت في (eq: 7.7.4) ، فلا داعي للحساب في الصيغة (eq: 7.7.5) من أجل. لذلك من الأفضل إجراء الحوسبة قبل الحوسبة. هذا موضح في المثال التالي.

لحساب المعاملات في ، قمنا بتعيين (مكافئ: 7.7.20) ونطبق معادلة التكرار الناتجة لـ ، ، وبالتالي ،

نعتبر الآن معادلات من الشكل حيث تكون جذور المعادلة الأساسية حقيقية وتختلف بعدد صحيح زوجي. إثبات النظرية التالية مشابه لإثبات النظرية من النوع: 7.7.1

لحساب المعاملات ، وفي ، قمنا بتعيين (مكافئ: 7.7.26) ونطبق صيغة التكرار الناتجة لـ ، وبالتالي ،

ينتج عن هذا الاستبدال ، و ، وفي عوائد (مكافئ: 7.7.23). لذلك ، من (مكافئ: 7.7.24) ،

للحصول على نستخدم التفاضل اللوغاريتمي. من (مكافئ: 7.7.27) ، وبالتالي ، فإن التمييز فيما يتعلق بالإنتاجية ، لذا فإن التحديد هنا واستدعاء (مكافئ: 7.7.28) ينتج

نظرًا لأنه يمكننا إعادة كتابة (مكافئ: 7.7.30) كاستبدال هذا في عوائد (مكافئ: 7.7.29)

لحساب المعاملات ، وفي ، وضعنا في (مكافئ: 7.7.33) ونطبق صيغة التكرار الناتجة لذلك ،

مصدر النص

ترينش ، ويليام ف. ، "المعادلات التفاضلية الأولية" (2013). مؤلف ومحرّر من كتب وأقراص مدمجة. 8. (CC-BY-NC-SA)


المزيد من الوظائف الخاصة

التمثيلات الهندسية المفرطة

يمكن التعبير عن عدد من الوظائف الخاصة المقدمة في هذا الكتاب من حيث الوظائف الهندسية الفائقة. يمكن عادةً إجراء التحديد من خلال ملاحظة أن هذه الوظائف هي حلول من ODE تمثل حالات خاصة لـ ODE المفرط الهندسي. من الضروري أيضًا تحديد العوامل اللازمة للتعبير عن الوظائف بالمقياس المتفق عليه. نستشهد بعدة أمثلة.

الوظائف فوق الكروية C n (α) (x) تفي بـ ODE المعطى كـ Eq. (18.99) ، وبما أن هذه المعادلة هي حالة خاصة من المعادلة فوق الهندسية ، فإن المعادلة. (18.120) ، نرى أن الوظائف فوق الكروية (ووظائف Legendre و Chebyshev) يمكن التعبير عنها كوظائف فوقية هندسية. بالنسبة للوظيفة فوق الكروية نحصل عليها

بالنسبة إلى وظائف Legendre ووظائف Legendre المرتبطة بها ، نجد

وظائف Chebyshev لها تمثيلات

يمكن استخدام سلسلة hypergeometric لتحديد الوظائف ذات المؤشرات غير المتكاملة. التطبيقات المادية ضئيلة.

إلى عن على ج، وعدد صحيح ، و أ و ب غير متكامل ، أظهر ذلك

ماذا يحدث إذا أ هو عدد صحيح ، على سبيل المثال ، أ = ،1 و ج = −2?

أوجد علاقات تكرار Legendre و Chebyshev I و Chebyshev II المقابلة لعلاقة دالة متجاورة مفرطة الهندسة المعطاة كـ Eq. (18.126).

قم بتحويل كثيرات الحدود التالية إلى دوال هندسية فائقة للوسيطة x 2: (أ)

T 2 n (x) = (- 1) n 2 F 1 (- n، n 1 2 x 2).

x - 1 T 2 n + 1 (x) = (- 1) n (2 n + 1) 2 F 1 (- n، n + 1 3 2 x 2).

U 2 n (x) = (- 1) n 2 F 1 (- n، n + 1 1 2 x 2).

x - 1 U 2 n + 1 (x) = (- 1) n (2 n + 2) 2 F 1 (- n، n + 2 3 2 x 2).

اشتق أو تحقق من العامل الرئيسي في التمثيلات الهندسية الفائقة لوظائف تشيبيشيف.

تحقق من أن وظيفة Legendre من النوع الثاني ،سν(ض)، اعطي من قبل

تم تحديد دالة بيتا غير المكتملة في Eq. (13.78) كما

تحقق من التمثيل المتكامل

ملحوظة. على الرغم من أن سلسلة الطاقة المستخدمة لتأسيس هذا التمثيل المتكامل صالحة فقط لـ |ض| العلامة & lt 1 ، التمثيل صالح للعامة ض، كما يمكن إثباته من خلال الاستمرار التحليلي. غير متكامل أ المحور الحقيقي في ض- الطائرة من 1 إلى عبارة عن خط مقطوع.

تلميح. التكامل يشبه بشكل مثير للريبة دالة بيتا ويمكن توسيعه إلى سلسلة من وظائف بيتا.

تلميح. هذه فرصة لاستخدام التمثيل المتكامل في التمرين 18.5.7.

تلميح. جرب التمثيل المتكامل.

ملحوظة. هذه العلاقة مفيدة في تطوير تمثيل رودريغز لـ تين(x) (انظر التمرين 18.5.10).

تلميح. أحد الاحتمالات هو استخدام علاقة دالة فوق هندسية

تبين أن المجموع في المعادل. (18.43) ،

تلميح. هذه فرصة لاستخدام علاقة دالة مجاورة Eq. (18.127) والاستقراء الرياضي (القسم 1.4). بدلاً من ذلك ، استخدم التمثيل المتكامل والدالة التجريبية.


جدول المحتويات

تمهيد للمدرب xv تمهيد للطالب xvii 1 ما هي المعادلة التفاضلية؟ 1 1.1 ملاحظات تمهيدية 1 1.2 تذوق المعادلات التفاضلية العادية 5 1.3 طبيعة الحلول 7 1.4 المعادلات القابلة للفصل 15 1.5 المعادلات الخطية من الدرجة الأولى 18 1.6 المعادلات الدقيقة 24 1.7 المسارات المتعامدة والمنحنيات 30 1.8 المعادلات المتجانسة 36 1.9 عوامل التكامل 41 1.10 تخفيض الطلب 46 1.10.1 مفقود المتغير التابع 46 1.10.2 مفقود المتغير المستقل 48 1.11 السلسلة المعلقة ومنحنيات السعي 52 1.11.1 السلسلة المعلقة 52 1.11.2 منحنيات السعي 57 1.12 الدوائر الكهربائية 62 1.13 تصميم آلة غسيل الكلى 67 مشاكل للمراجعة والاكتشاف 72 2 معادلات خطية من الدرجة الثانية 77 2.1 معادلات خطية من الدرجة الثانية ذات معاملات ثابتة 77 2.2 طريقة المعاملات غير المحددة 85 ix 2.3 طريقة اختلاف المعلمات 90 2.4 استخدام حل معروف لإيجاد حل آخر 95 2.5 الاهتزازات والتذبذبات 100 2.5.1 الحركة التوافقية البسيطة غير المخمدة 100 2.5.2 الاهتزازات المخففة 102 2.5.3 الاهتزازات القسرية 106 2.5.4 بعض الملاحظات أ نوبة الكهرباء 109 2.6 قانون نيوتن للجاذبية وقوانين كيبلر 112 2.6.1 قانون كيبلر الثاني 116 2.6.2 قانون كيبلر الأول 118 2.6.3 قانون كيبلر الثالث 121 2.7 معادلات الترتيب الأعلى 128 ملاحظة تاريخية 135 2.8 وظائف بيسيل والغشاء المهتز 136 مشاكل المراجعة والاكتشاف 142 3 حلول سلسلة الطاقة والوظائف الخاصة 145 3.1 مقدمة ومراجعة سلسلة الطاقة 145 3.1.1 مراجعة سلسلة الطاقة 146 3.2 سلسلة حلول معادلات الدرجة الأولى 157 3.3 النقاط العادية 163 3.4 النقاط الفردية العادية 173 3.5 المزيد حول النقاط الفردية العادية 180 ملاحظة تاريخية 190 ملاحظة تاريخية 192 3.6 درجة حرارة الحالة الثابتة في الكرة 193 مشكلات للمراجعة والاكتشاف 196 4 مشكلات ستورم-ليوفيل ومشكلات القيمة الحدودية 199 4.1 ما هي مشكلة ستورم وليوفيل؟ 199 4.2 تحليل مشكلة Sturm-Liouville 206 4.3 تطبيقات نظرية Sturm-Liouville 213 4.4 مفرد Sturm-Liouville 220 4.5 بعض الأفكار من ميكانيكا الكم 227 مشاكل للمراجعة والاكتشاف 231 5 الطرق العددية 235 5.1 ملاحظات تمهيدية 236 5.2 طريقة أويلر 238 5.3 مصطلح الخطأ 242 5.4 طريقة أويلر المحسنة 246 5.5 طريقة رونج-كوتا 252 5.6 طريقة الاضطراب المستمر 256 مشكلات للمراجعة والاكتشاف 260 6 سلسلة فورييه: المفاهيم الأساسية 265 6.1 معاملات فورييه 265 6.2 بعض الملاحظات حول التقارب 275 6.3 حتى والدوال الفردية: سلسلة جيب التمام والجيب 282 6.4 سلسلة فورييه على فترات تعسفية 289 6.5 الوظائف المتعامدة 293 الملاحظة التاريخية 299 6.6 مقدمة لتحويل فورييه 300 6.6.1 الالتواء وانقلاب فورييه 309 6.6.2 تحويل فورييه المعكوس 309 مشاكل للمراجعة و الاكتشاف 312 7 تحويلات لابلاس 317 7.0 مقدمة 317 7.1 تطبيقات المعادلات التفاضلية 321 7.2 المشتقات والتكامل ls 327 7.3 التلافيف 334 7.3.1 مشكلة ميكانيكا أبيل 337 7.4 خطوة الوحدة ووظائف النبضة 342 ملاحظة تاريخية 352 7.5 التدفق على لوحة مسطحة بدائية الاندفاع 353 مشاكل للمراجعة والاكتشاف 356 8 التوزيعات 363 8.1 توزيعات شوارتز 363 مشاكل للمراجعة والاكتشاف 371 9 Wavelets 373 9.1 التوطين في متغيرات الوقت والمكان 373 9.2 بناء تحليل فورييه مخصص 376 9.3 أساس Haar 379 9.4 بعض الأمثلة التوضيحية 384 9.5 بناء أساس مويج 394 9.5.1 بناء اندماجي لموجات Daubechies 398 9.5.2 موجات Daubechies من وجهة نظر تحليل فورييه 399 9.5.3 المويجات كأساس غير مشروط 402 9.5.4 المويجات وقابلية التقريب تقريبًا 403 9.6 التحويل المويج 406 9.7 المزيد عن التحويل المويج 423 9.8 التحلل ووجهها 429 9.9 بعض التطبيقات 435 9.10 الطاقة التراكمية والانتروبيا 445 مشاكل للمراجعة والاكتشاف 451 10 المعادلات التفاضلية الجزئية والربط مسائل القيمة 455 10.1 مقدمة وملاحظات تاريخية 455 10.2 القيم الذاتية وسلسلة الاهتزاز 460 10.2.1 مشاكل القيمة الحدودية 460 10.2.2 اشتقاق معادلة الموجة 461 10.2.3 حل معادلة الموجة 463 10.3 معادلة الحرارة 469 10.4 مشكلة ديريكليت لقرص 478 10.4.1 بواسون لا يتجزأ 481 ملاحظة تاريخية 488 ملاحظة تاريخية 489 مشاكل للمراجعة والاكتشاف 491 جدول الترميز 495 مسرد 501 حلول لتمارين مختارة 527 ببليوغرافيا 527 الفهرس 530


7. تبسيط معادلة أويلر.

افترض أن لاغرانج L = L (س ، ص ، ص & # 8216) يعتمد فقط على اثنين من المتغيرات الثلاثة س ، ص و ذ & # 8216. ثم يمكننا تبسيط معادلة أويلر إلى حد ما. لدينا ثلاث حالات خاصة:

حالة 1: L = L (س ، ص). ثم تكون معادلة أويلر & # 8217s

الحالة 2: L = L (س ، ص & # 8216 ). ثم تكون معادلة أويلر & # 8217s

أين ج ثابت تعسفي.
الحالة 3: L = L (y ، y & # 8216 ). ثم معادلة أويلر & # 8217s

أين ج هو وثابت تعسفي.

ملاحظة: تسمى العلاقة في الحالة 3 أعلاه هوية بلترامي & # 8217s.

حيث تأتي المساواة في الخطوة الأخيرة من معادلة أويلر & # 8217s.
المثال 12 (قارن المثال 5): أوجد الطرف الأقصى للوظيفة

وبالتالي يمكننا تبسيط المشكلة باستخدام هوية Beltrami & # 8217s أعلاه. نحن نحصل

والتي يمكن تبسيطها إلى

نختار علامة مينو أعلاه منذ ذلك الحين dy / dx & lt0 (انظر الشكل). الآن قم بتغيير المتغيرات


& lt & gt التي تصبح بها المعادلة

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

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

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

أين أنا هي لحظة القصور الذاتي للكرة وسرعتها الزاوية. إذا استخدمنا هذا التعبير بدلاً من

في المثال 5 ، ندرك بسهولة أنه يؤدي إلى نفس المعادلة التفاضلية وبالتالي نفس الحل.

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


هندسة القوى في المعادلات الجبرية والتفاضلية

8 الحل المقارب لنظام المعادلات

نحن نعتبر مشكلة أساسية. دع نظام المعادلات

أين ال Fأنا(X) هي كثيرة حدود لوران ، والمخروط المحدب ك في ℝ * ن. مطلوب العثور على جميع حلول المعلمات المتعددة للنظام (8.1) ، والتي تقع في المجموعة U (K * ، ε) ، حيث ك* هو المخروط ثنائي المخروط ك، و ε & gt 0 صغير بدرجة كافية ، ويمكن من خلاله رسم منحنى بالشكل (2.1) به صك (ص ≠ 0).

المشكلة الأساسية تسمى مخفض واحد إذا كنا نبحث عن فروع لا يساوي أي من الإحداثيات فيها صفرًا (أو ما لا نهاية). من الواضح أن مشكلة أساسية تنقسم إلى مشكلة مصغرة ذات أبعاد n وعدد محدود من المشكلات المختصرة التي ينسق فيها بعض xأنا تم تعيينها لتكون أصفار (أو ما لا نهاية) ، أي ثوابت ، ومخروط المشكلة هو تقاطع مخروط المشكلة الأساسية ك مع المجموعة

لحل المشكلة المصغرة مع مخروط المشكلة كلكل منها Fأنا نحن نشكل نيوتن متعدد السطوح Γأنا، ونفرد وجوهها Γ i k (d) مع المخاريط العادية U i k (d) هنا يكفي أن نفرز كل الوجوه Γ i k (d) التي تقاطع U i k (d) ∩ K غير فارغ. نقدم K i k (d) = K ∩ U i k (d) ونعتبر جميع التقاطعات غير الفارغة الممكنة

يترك ΠΛ كن أحد هذه التقاطع ، ودع النظام المبتور

إذا كان هناك دأنا = 0 ، ثم f ^ i = a X Q. حلول المعادلة اكس س = 0 يكون أحد الإحداثيات مساويًا للصفر (أو اللانهاية) ، ولا يمكن أن تكون حلولًا للمشكلة المختصرة. وبالتالي من الضروري النظر فقط في الأنظمة المبتورة (8.3) التي فيها جميعها دأنا & gt 0. وفقًا للنظام المبتور (8.3) ، نقوم بتحويل الطاقة والتخفيضات المذكورة في النظرية 7.1. ثم يتحول النظام (8.1) إلى النظام

ويتحول النظام المبتور (8.3) إلى النظام

أين د هو بعد النظام المبتور (8.3). نفترض أن g ^ i هي كثيرات حدود عادية في ذ1,…, ذد، وذلك في زأنا الاحداثيات ذد +1,…, ذن تظهر بقوى غير سالبة. من الممكن دائمًا تحقيق ذلك وفقًا للملاحظة 7.1. هنا مخروط الاقتطاع (8.5)

الآن علينا إيجاد تلك الحلول

إلى النظام الكامل (8.4) الذي له ترتيب المتجه P ∈ Π ˜ λ. وفقًا لنظرية 6.1 ، في مثل هذه الحلول القيم ذأنا = جأنا أنا = 1,…,د، تفي بالنظام (8.5). هنا كل شيء ج1,…, جد تختلف عن الصفر واللانهاية. يحتوي المخروط المماس T ˜ للنظام المبتور (8.5) على قيود فقط فد +1,…, فن، وهي تقع في المخروط فد +1,…, فن ≥ 0.

لو د & lt م، ففي الحالة العامة ، لا يوجد حلول للنظام المقتطع (8.5). إذا كان يحتوي على مجمع خطي معزول من الحلول ، فعندئذٍ في النظام (8.4) يتعين علينا إجراء تغيير خطي للإحداثيات ، والذي ينقل هذا المشعب إلى فضاء فرعي إحداثي ، ثم حله بالقرب من هذا الفضاء الجزئي ، باستخدام نيوتن متعددات الوجوه إذا لزم الأمر. إذا كان النظام (8.5) يحتوي على مجموعة مستمرة من الحلول ، وهي ليست مشعبًا خطيًا ، فعندئذٍ مثل قضية يسمى تتدهور سننظر فيه لاحقًا.

نحن نعتبر الآن النظام (8.5) مع

في ال د- مساحة الأبعاد مع الإحداثيات ذ1,…, ذد، يحدد نظام المعادلات المقطوعة (8.5) مشعب جبري G ^ علينا أن نجد الآن المشعب بالكامل G ^ نستخرج أولاً المجموعة الفرعية G ^ c لجميع النقاط الحرجة y1,…ذد، حيث يتم الاحتفاظ بالمساواة (8.5) والمصفوفة

من البعد د × م له رتبة أقل من ذلك م. يمكن تقسيم المجموعة G ^ G ^ c إلى عدد محدود من الأجزاء G ^ 1 ،… ، G ^ l في كل منها يوجد ترتيب ثانوي واحد على الأقل غير صفري م

من المصفوفة (8.7) ، والإحداثيات المقابلة y i 1 ، ... ، y i m يمكن التعبير عنها كدوال للإحداثيات المتبقية بين y1,…, ذد. دع G ^ 1 يكون ذلك الجزء من المجموعة G ^ G ^ c التي

ونحصل على الوظائف

التي نكتبها على هيئة كثيرات حدود في Z ^ = (z 1،…، z m، y d + 1،…، y n):

وأسس Q ^ للتوسعات (8.9) يكمن في مخروط الظل Ť، يساوي إسقاط المخروط T ˜ في الفضاء الجزئي للإحداثيات ف1,…, فم, فد+1,…, فن. الآن إلى نظام المعادلات

يمكن للمرء تطبيق نظرية الوظيفة الضمنية 5.2 والحصول على حلها في شكل سلسلة

أين ص″ = (ذد+1,…, ذن), ص″ = (صد+1,…, صن) والمعاملات φأنا ″ هي متعددة الحدود في Ψ1,…, Ψم, ذم+1,…, ذد، مقسومًا على قوى α من (8.10). تذكر التغيير (8.8) والعودة من ص ل X بمساعدة تحويل القوة ، نحصل على تمثيل حدودي X = X(ذم +1,…, ذن) لبعض حلول نظام المعادلات الأولي (8.1). بطريقة مماثلة نحصل على الحلول المتعلقة بالأجزاء الأخرى G ^ j من المجموعة G ^ G ^ c.

مجموعة النقاط الحرجة G ^ c للمشعب G ^ عبارة عن مشعب جبري بحد ذاته. يتكون من بعض المكونات المتصلة G ^ c 1،…، G ^ c k. إذا كان G ^ c j مشعبًا خطيًا معزولًا ، فإننا في النظام الكامل (8.4) نقوم بإجراء تغيير خطي للإحداثيات ، ونحول هذا المشعب إلى فضاء فرعي إحداثيات ، وندرس النظام الذي تم الحصول عليه بالقرب من هذا الفضاء الجزئي. هذه مرة أخرى مشكلة أساسية ، ولكن مع مجموعة أضيق من الحلول. إذا لم يكن G ^ c j مشعبًا خطيًا ، فهذا يعني قضية يسمى أيضًا ب تتدهور واحد.

في الوقت الحاضر لم يتم بعد وضع الإستراتيجية الموحدة لدراسة الحالات المتدهورة. في [Bruno and Soleev 1991a، § 4] تم تقديم استراتيجيتين من هذا القبيل. الأول هو الحصول عن طريق التلاعب في كثيرات الحدود ز1,…, زم كثير حدود جديد زم+1، وهي دالة ز1,…, زم، والتي لها اقتطاع g ^ m + 1 ، وهذا الاقتطاع ليس دالة للاقتطاع g ^ 1،…، g ^ m. إذا كان لا يمكن الحصول على مثل هذا كثير الحدود ، ثم كثيرات الحدود ز1,…, زم تعتمد وظيفيًا ، ويمكن للمرء أن يجد هذا الاعتماد. تتمثل الإستراتيجية الثانية في إدخال إحداثيات جديدة ذن+أنا = αأنا, أنا = 1,…, س، أين α1,…, αس تشكل أساسًا متعدد الحدود لمثل المتشعب G ^ c j ، وفي كتابة الوظائف ز1,…, زم مثل كثيرات الحدود في ذن + أنا,…, ذن + ق.

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

بالنسبة للمشاكل الأساسية الثانوية المتبقية ، يجب أن يستمر الإجراء. بعد عدد محدود من هذه الخطوات ، يمكن للمرء أن يفصل بين جميع الفروع ذات التعددية رقم واحد ولكن عدد الخطوات غير معروف مسبقًا (انظر [Kukles and Grus 1958]).

الحالة الأكثر دراسة هي م = ن - 1 ، عندما تكون جميع كثيرات الحدود F1,…, Fلا1 مستقلة وظيفيا. يعرف النظام (8.1) منحنى جبري وعلينا إيجاد فروعه [Bruno and Soleev 1991a]. لو د = م = ن - 1 ، ثم تؤكد النظرية الكلاسيكية لبيزوت أن عدد الحلول المعقدة لنظام المعادلات المقطوعة (8.5) يمكن تقديره من خلال درجاتها (إنها تساوي حاصل ضرب هذه الدرجات). حصل بيرنشتين [1975] على عدد أكثر دقة من الحلول لنظام المعادلات (قارن [كوشنرينكو 1975 أ ، 1976 خوفانسكي 1978 ب]). إنه يساوي حجم Minkovski المختلط الخامس(Γ1,…, Γم) من نيوتن متعددات الوجوه Γ1,…, Γم من كثيرات الحدود المقابلة (انظر [Khovanskii 1988]).

نسمي تعقيد النظام المبتور (8.3) في (ن - 1) حجم Minkovski المختلط الأبعاد للأوجه المترجمة المقابلة Γ i k (d i) + T i ، أنا = l،…،م، حيث - T i ∈ Γ i k (d i) ، ونسمي تعقيد المشكلة المخففة مجموع تعقيدات جميع الأنظمة المبتورة التي تتقاطع مخاريطها الطبيعية مع مخروط المشكلة. ثم في الحالة العامة ، فإن عدد الفروع المعقدة للمشكلة المختزلة يساوي تعقيدها.

توجد صيغ لعدد فروع الحلول للنظام (8.1) في حي صغير من النقطة الحرجة المعزولة X = 0 (انظر [Grin ′ 1971 Sather 1973 Fucuda et al. 1986 Szafraniec 1992]). سوف نعرض واحد منهم. نحدد 6 عدد فروع حلول النظام (8.1) في حي صغير من النقطة الحرجة المعزولة X = 0 ، ونضع

حيث F = def (f 1، ...، f n - 1) من الواضح ، φ(0) = 0. دع H = def (F ، δ).

[سففرانيك 1992] إذا كان أصل الإحداثيات نقطة حرجة معزولة في النظام (8.1) مع م = ن − 1, ثم بالنسبة للنظام H.(X) = 0 وهي أيضًا نقطة مفردة معزولة و b = 2 درجة ح.

يؤكد Szafraniec [1992] أن هذه الصيغة تمت برمجتها على جهاز كمبيوتر ، وأن البرنامج يستخدم مخططًا للأسس الأولية للنظام (8.1).

(استمرار للمثالين 6.1 و 7.1). مع القيم أ1 = 40, أ2 = −أ3 = 25, أ4 = −1, أ5 = 16, أ2أنا = −1, أنا = 1 ، 2 ، 3 ، 4 ، نعتبر النظام (6.6). ثم لكل من الأنظمة المبتورة (7.4) و (7.6) حلان بسيطان حقيقيان واثنان معقدان. وبالتالي فإن النظام (7.4) له حلين حقيقيين:

لأن كل الجذور بسيطة و د في - 1 ، ثم يتم عزل الفروع ، أي أن نظرية الوظيفة الضمنية 5.2 قابلة للتطبيق. الاستبدال في النظام (7.5) نعم ′ = نعم ′ 0 + ض′ وحساب أول شروط التوسعات Z ′(ذ3)، نحصل

بالعودة إلى الإحداثيات الأولية وفقًا لـ (7.3) ، نجد فرعين حقيقيين F j:

تعطي الجذور المعقدة (8.12) للنظام (7.4) فرعين مركبين F 5 ، 6:

يحتوي النظام المبتور (7.6) على حلين بسيطين حقيقيين: y 1 1 ، 2 0 = ± 1 ، y 2 0 = - 1 وحلين بسيطين معقدين: y 1 3 ، 4 0 = ± i ، y 2 0 = - 1 هذه الحلول نحصل عليها على التوالي فرعين حقيقيين F 3 ، 4:

وفرعين مركبين F 7 و 8:

دور المعلمة τ للفروع المكتشفة F 1 و 2 و 5 و 6 و F 3 و 4 و 7 و 8 يتم لعبها بواسطة y 3-1 و x 1 - 1 على التوالي.

في الشكل 2.1 يظهر التصرف التقريبي لنصف الفروع الحقيقية F 1 و F 2 لـ ذ3 & gt 0 و F 3 و F 4 من أجل x1 & GT 0 في حي صغير من النقطة X = 0 تمثل الخطوط المتقطعة منحنيات بها x2 & lt 0.

الشكل 2.1. التصرف في أنصاف الفروع F 1 - F 4 لمنحنى المثال 8.1 بالقرب من النقطة X = 0.

نحن ننظر الآن في الموقف بدعم غير محدود ، تم تحليله في الفصل 1 ، القسم 8. لو س هو دعم سلسلة Laurent F و ك هو مخروط المشكلة ، ثم نسمي الهيكل المحدب للمجموعة كΓ ال السطوح المتعددة السطوح نيوتن إلى عن على F.

نحن نعتبر الآن المشكلة الأساسية حيث الدعم سأنا= ملحقFأنا هي لانهائية ، ذات قيمة صحيحة ، وتقع في مجموعات من الشكل C * + <(Q 1 i،…، Q l i i)> (تختلف باختلاف أنا) ، ومخروط المشكلة ك يقع داخل مخروط عدد صحيح ج. لحل مثل هذه المشكلة الأساسية ، يطبق المرء الإجراء الموصوف سابقًا في حالة دعم الدعم المحدودFأنا. الفرق الوحيد هو أنه الآن بالنسبة للتعويضات بالصيغة y i = y j 0 + z j ، يحصل المرء على سلسلة في قوى غير سالبة لـ zي (بدلاً من كثيرات الحدود). على وجه الخصوص ، إذا كانت الوظائف Fأنا أنا = 1,…, م، تحليلي في محيط النقطة X = 0 ، ثم يتم توسيعها في سلسلة Maclaurin

يحدد النظام (8.1) مجموعة تحليلية (انظر [Hartshorne 1977]). هنا ج = <ص: ص ≤ 0>, ك = <ص: ص & lt 0> و س ≥ 0 لجميع Sأنا

بعد استخراج النظام المبتور وتحويل الطاقة ، المخاريط الأولية ج و ك إلى بعض المخاريط C ˜ و K ذات الطبيعة الأكثر عمومية. هذا هو السبب في أن المشكلة الأساسية في البداية تمت صياغتها في شكل ثابت فيما يتعلق بتحولات القوة. حول استبدال المعادلات التحليلية بالمعادلات الجبرية ، انظر أيضًا [MacMillan 1912a].


موضوعات في التقريب متعدد المتغيرات والاستيفاء

إيلينا بيرديشيفا. Joachim Stöckier ، في دراسات في الرياضيات الحاسوبية ، 2006

8 ملاحظات إضافية

تم تقديم مشغلي Durrmeyer (2) بواسطة Durrmeyer في أطروحته [15]. بدأ Derriennic دراسة خصائص التقريب الخاصة بهم في العديد من الأوراق ، ثم درسها لاحقًا العديد من المؤلفين. تظهر الخصائص الطيفية للنظرية 1 في [10] ، [11] و [12] للحالة غير الموزونة ، في [6] و [7] للحالة أحادية المتغير الموزونة ، وفي [14] للحالة الموزونة متعددة المتغيرات. انظر أيضًا الفصل 5.2 في كتاب Paltanea الأخير [23] ، والمراجع الواردة هناك.

بيان النظرية 2 أصلي ، كما هو الحال مع تطبيقه في القسم 6. بالنسبة لخصائص وصيغ الدوال الهندسية الفائقة ، نشير إلى الجدول القياسي ، مثل [1] و [22] ، بالنسبة لتكاملات نوع لابلاس ، يمكن اتباع نهج مباشر من Koornwinder [21] ، وعلى وجه الخصوص ، من Askey [ 2] عمل أنيق متعلق بهذا. من المفيد أيضًا الرجوع إلى فصل Szegö [27] حول جاكوبي متعدد الحدود.

العامل التفاضلي يوميكرومتر = يو1,ميكرومتر في (10) وتلعب صلاحياته دورًا بارزًا في دراسة النظريات المباشرة والعكسية لمشغل Durrmeyer ، انظر مرة أخرى الأوراق التي كتبها Derriennic و Berens و Xu و Ditzian ، حيث يمكن أيضًا العثور على الخصائص الطيفية لـ Lemma 6. حالة الترتيب الأعلى يوℓ ، μ تم التحقيق فيه لأول مرة في [4] ، باستخدام ترميز مختلف. في الحالة أحادية المتغير (غير مرجحة) ، يُطلق على هؤلاء المشغلين اسم مشغلي Legendre التفاضلي في Heilmann’s Habilitationsschrift [16]. في هذه الورقة ، اخترنا التعريف العودي (11) الذي يؤدي إلى تمثيل المنتج لـ يوℓ ، μ الذي نقله إلينا مايكل فلتن.

تم تقديم شبه الإقحامات (13) في [17] ، للحالة غير المرجحة. تم النظر في الحالة المرجحة في [18] و [4] ، حيث يمكن أيضًا العثور على بيانات النظرية 7 و Lemma 8. ومع ذلك ، فإن التعبير عن شبه الإقحامات من حيث عوامل Durrmeyer في Theorem 9 هو جديد. تدمج هذه النتيجة الأخيرة مشغلينا في فئة شبه الإقحامات التي تم إنشاؤها كمجموعات خطية من مشغلي Durrmeyer. ومع ذلك ، فإن هذا النهج عادة ما يكون أقل مباشرة وأقل وضوحًا من نهجنا. نشير مرة أخرى إلى أعمال Derriennic [13] ، وإلى Sablonnière [24] ، [25] و Heilmann [16]. تقدم ورقة Sablonnière الأخيرة [26] وصفًا جيدًا لهذه الإنشاءات.

إن عدم المساواة في برنشتاين ، نظرية 11 ، أصلية مرة أخرى. إنه يؤكد تخميننا المطروح في [3] حيث تم تقديم دليل مختلف للحالة الخاصة د = 1 و ميكرومتر = (0 ، 0). نتوقع أن يكون تمثيل شبه الإقحامات كمجموعة خطية من العوامل الموجبة T n - ℓ، μ ℓ على النحو الوارد في النظرية 14 تطبيقات بعيدة المدى. أخيرًا وليس آخرًا ، من المتوقع أن تؤدي الحالة M n ، μ n إلى تمثيل جديد متعدد الحدود لإعادة إنتاج النواة بترتيب كامل على البسيط س د ، مع وصلات إلى نظريات الجمع لكثيرات الحدود المتعامدة.

النتائج المباشرة في القسم 7 هي إلى حد ما عواقب فورية لعدم المساواة في برنشتاين. نشير إلى ورقتنا [4] ، ومرة ​​أخرى إلى العمل السابق لديرينيك [13] ، بيرينز وآخرون. [5] - [7] وديتسيان [14]. ومع ذلك ، ما زلنا لا نحل المسألة الطبيعية المتمثلة في "العكس" أو حتى نظريات "العكس القوي" لأشباه الاستدلالات. فيما يتعلق بهذا ، فإن ورقة تشين وديتزيان وإيفانوف [8] والتقنيات الدقيقة لنووب وزو في [19] ، [20] و Zhou's Habilitationsschrift [29] قد تكون مفيدة.

جاء الدافع الأولي لدراساتنا من مقال Chui et al. [9] ، حيث شبه المتغير أحادي المتغير على أقسام غير منتظمة من فاصل زمني محدد أنا were constructed as linear combinations of B-splines. In their approach, the quasi-interpolants من (ص) (for the unweighted case) are the starting point for an inductive method of knot insertion. The quasi-interpolants in [9] give rise to the definition of “approximate duals” of B-splines, which are the centerpiece for their construction of nonstationary wavelet frames.


Boundedness of solutions

It is well known that the longtime behaviour of a timedependent nonlineare differential equation

Next, we present some examples demonstrating the topic and utilizing compter software.

  1. Alekseev, V.M., Quasirandom dynamic systems, I, II, III, Math USSR Sb, 1868, Vol. 5, pp. 73--128, Vol. 6, pp. 505--560, 1969, pp. 1--43.
  2. Chen, Y.M. and Liu, J.K., A new method based on the harmonic balance method for nonlinear oscillators, Physics Letters A, 2007, Volume 368, Issue 5, pp. 371-378
  3. Dickerhoff, R. and Zehnder, E., Boundedness for solutions via twist theorem, Annali della Scuola Normale Superiore di Pisa, 1987, Vol. 14, No. 1, pp. 79--95.
  4. Lakshmikantham, V., Leela, S., and Martynyuk, A., Stability Analysis of Nonlinear Systems, 1989, Marcel DEkker, New York.
  5. Littlewood, J.,
  6. Littlewood, J.,
  7. Markus, L., Differential dynamic systems, 1969, American Mathematical Society, Providence, RI.
  8. Morris, G., A case of the boundedness in Littlewood's problem on oscillatory differential equations, Bulletine Austral Mathematical Society, 1976, Vol. 14, pp. 71--93.
  9. Moser, J., Stable and random motions in dynamic systems, Ann Math Studies, 1973, Vol. 77, Princeton, NJ.
  10. Raffoul, Y., Boundedness in nonlinear differential equations.
  11. Sitnikov, K., Existence of oscillating motions for three-body problemDokladu Akademii Nayk, SSSR, 1960, Vol. 133, No 2, pp. 303--306.
  12. Yoshizawa, T., Stability Theory by Lyapunov Second Method, 1966, The Math Society of Japan, Tokyo.
  13. You, J.-G., Boundedmess for solutions of super-linear duffing equations via the Twist theorem, Science in China, Series A: Mathematics, Physics, Astronamy & Technological Science, 1992, Vol.35No. 4, pp. 399--412.
  14. Yuan, X., Boundedness of solutions for Duffing-type equation, Science in China, SEries A: Mathematics, 1998, Vol. 41, No. 6, pp. 595--605.

Return to Mathematica page
Return to the main page (APMA0330)
Return to the Part 1 (Plotting)
Return to the Part 2 (First Order ODEs)
Return to the Part 3 (Numerical Methods)
Return to the Part 4 (Second and Higher Order ODEs)
Return to the Part 5 (Series and Recurrences)
Return to the Part 6 (Laplace Transform)
Return to the Part 7 (Boundary Value


V. Method Comparison

You also may want to compare some of the different methods to see how
they perform for a specific problem.

Implicit Runge--Kutta methods have a number of desirable properties.

The Gauss--Legendre methods, for example, are self-adjoint, meaning
that they provide the same solution when integrating forward or
backward in time.


A generic framework for implicit Runge--Kutta methods has been implemented. The focus so far is on methods with interesting geometric properties and currently covers the following schemes:

"ImplicitRungeKuttaGaussCoefficients"
"ImplicitRungeKuttaLobattoIIIACoefficients"
"ImplicitRungeKuttaLobattoIIIBCoefficients"
"ImplicitRungeKuttaLobattoIIICCoefficients"
"ImplicitRungeKuttaRadauIACoefficients"
"ImplicitRungeKuttaRadauIIACoefficients"

The derivation of the method coefficients can be carried out to arbitrary order and arbitrary precision.

References on Runge--Kutta algorithms

  1. explicit Runge--Kutta
  2. Butcher, J.C., A history of Runge--Kutta methods, Applied Numerical Mathematics, 20 (1996) 247--260

Return to the main page (APMA0330)
Return to the Part 1 (Plotting)
Return to the Part 2 (First Order ODEs)
Return to the Part 3 (Numerical Methods)
Return to the Part 4 (Second and Higher Order ODEs)
Return to the Part 5 (Series and Recurrences)
Return to the Part 6 (Laplace Transform)
Return to the Part 7 (Boundary Value Problems)


Voronoi Diagrams*

Franz Aurenhammer , Rolf Klein , in Handbook of Computational Geometry , 2000

4.4.1 Line segment Voronoi diagram and medial axis

يترك جي be a planar straight line graph on ن points in the plane, that is, a set of non-crossing line segments spanned by these points. على سبيل المثال، جي might be a tree, or a collection of disjoint line segments or polygons, or a complete triangulation of the points. The number of segments of جي is maximum, 3ن − 6, in the last case. We will discuss several types of diagrams for planar straight line graphs in the present and following subsections.

The classical type is the (closest point) Voronoi diagram, الخامس(جي), of جي. It consists of all points in the plane which have more than one closest segment in جي. الخامس(جي) is known under different names in different areas, for example, as the line Voronoi diagram أو هيكل عظمي من جي, or as the medial axis متي جي is a simple polygon. Applications in such diverse areas as biology, geography, pattern recognition, computer graphics, and motion planning exist see, e.g. Kirkpatrick [ 161 ] and Lee [ 180 ] for references.

See Figure 20 . الخامس(جي) is formed by straight line edges and parabolically curved edges, both shown as dashed lines. Straight edges are part of either the perpendicular bisector of two segment endpoints, or of the angular bisector of two segments. Curved edges consist of points equidistant from a segment endpoint and a segment’s interior. There are two types of vertices, namely of اكتب 2 having degree two, and of اكتب 3 having degree three (provided جي is in general position). Both are equidistant from a triple of objects (segment or segment endpoint), but for type-2 vertices the triple contains a segment along with one of its endpoints.

Fig. 20 . Line segment Voronoi diagram.

معا مع جي’s segments, the edges of الخامس(جي) partition the plane into regions. These can be refined by introducing certain normals through segment endpoints (shown dotted in Figure 20 ), in order to delineate وجوه each of which is closest to a particular segment or segment endpoint. Two such normals start at each segment endpoint where جي forms a reflex angle, and also at each محطة من جي which is an endpoint belonging to only one segment in جي. A normal ends either at a type-2 vertex of الخامس(جي) or extends to infinity.

It is well known that the number of faces, edges and vertices of الخامس(جي) is linear in ن, the number of segment endpoints for جي. The number of vertices is shown to be at most 4ن − 3 in Lee and Drysdale [ 182 ]. An exact bound, that also counts the ‘infinite’ vertices at unbounded edges and segment normals, is given below.

Let G be a planar straight line graph on n points in the plane, and let G realize t terminals and r reflex angles. عدد ال (finite and infinite) vertices of V(جي) is exactly 2ن + ر + ص − 2.

P roof . Suppose first that جي يتكون من ه disjoint segments (that do not touch at their endpoints). Then there are ه regions, and each type-3 vertex belongs to three of them. By the Euler formula for planar graphs, there are exactly 2 ه − 2 such vertices, if we also count those at infinity. To count the number of type-2 vertices, observe that each segment endpoint is a terminal and gives rise to two segment normals each of which, in turn, yields one (finite or infinite) vertex of type 2. Hence there are 4ه such vertices, and 6ه − 2 vertices in total.

الآن دع جي be a general planar straight line graph with ه شرائح. We simulate جي by disjoint segments, by shortening each segment slightly such that the segment endpoints are in general position. Then we subtract from 6ه − 2 the number of vertices which have been generated by this simulation.

Consider an endpoint ص that is incident to د ≥ 2 segments of جي. Obviously, ص gives rise to د copies in the simulation.

The Voronoi diagram of these copies has د − 2 finite vertices, which are new vertices of type 3. As the sum of the degrees د ≥ 2 in جي is 2هر, we get 2هر − 2(نر) new vertices in this way.

Each convex angle at ص gives rise to two new normals emanating at the respective copies of ص, and thus to two (finite) type-2 vertices. A possible reflex angle at ص gives rise to one (finite or infinite) type-3 vertex, on the perpendicular bisector of the corresponding copies of ص. هناك ص reflex angles in جي, and thus 2هرص convex angles. هذا يعطي ص + 2(2هرص) new vertices in addition. The lemma follows by simple arithmetic.

Surprisingly, the number of edges of جي does not influence the bound in Lemma 4.4 . The maximum number of vertices, 3ن − 2, is achieved, for example, if G is a set of disjoint segments (ر = ن و ص = 0), or if جي is a simple polygon ص (ر = 0 و ص = ن).

In the latter case, the majority of applications concerns the part of الخامس(ص) interior to ص. This part is commonly called the medial axis من ص. The medial axis of an ن-gon with ص reflex interior angles has a tree-like structure and realizes exactly ن + ص − 2 vertices and at most 2(ن + ص) − 3 edges. Lee [ 180 ] first mentioned this bound, and also listed some applications of the medial axis. An interesting application to NC pocket machining is described in Held [ 139 ].

Several algorithms for computing الخامس(جي), for general or restricted planar straight line graphs جي, have been proposed and tested for practical efficiency. الخامس(جي) can be computed in O(ن سجل ن) time and O(ن) space by divide & conquer (Kirkpatrick [ 161 ], Lee [ 180 ], and Yap [ 261 ]), plane sweep (Fortune [ 125 ]), and randomized incremental insertion (Boissonnat et al. [ 43 ] and Klein et al. [ 170 ]).

Burnikel et al. [ 51 ] give an overview of existing methods, and discuss implementation details of an algorithm in Sugihara et al. [ 243 ] that first inserts all segment endpoints, and then all the segments, of جي in random order. An algorithm of comparable simplicity and practical efficiency (though with a worst-case running time of O(ن 2 )) is given in Gold et al. [ 130 ]. They first construct a Voronoi diagram for point sites by selecting one endpoint for each segment, and then maintain the diagram while expanding the endpoints, one by one, to their corresponding segments. During an expansion, the resulting topological updates in the diagram can be carried out efficiently. In fact, Voronoi diagrams for moving point sites are well-studied concepts see, e.g. Guibas et al. [ 134 ] and Roos [ 221 ].

An efficient O(ن log 2 ن) work موازى algorithm for computing الخامس(جي) is given in Goodrich et al. [ 132 ]. This is improved to O(log ن) parallel (randomized) time using O(ن) processors in Rajesekaran and Ramaswami [ 218 ]. (The latter result also implies an optimal parallel construction method for the classical Voronoi diagram.)

لو جي is a connected graph then الخامس(جي) can be computed in randomized time O(ن log* ن) see Devillers [ 88 ]. Recently, O(ن) time randomized, and deterministic, algorithms for the medial axis of a simple polygon have been designed by Klein and Lingas [ 169 ] and Chin et al. [ 68 ], settling open questions of long standing. The case of a convex polygon is considerably easier see Subsection 4.4.3 .

Some of the algorithms above also work for curved objects. The plane-sweep algorithm in Fortune [ 125 ] elegantly handles arbitrary sets of circles (i.e., the additively weighted Voronoi diagram, or Johnson–Mehl model) without modification from the point site case. Yap [ 261 ] allows sets of disjoint segments of arbitrary degree-two curves. A randomized incremental algorithm for general curved objects is given in Alt and Schwarzkopf [ 12 ]. They show that complicated curved objects can be partitioned into ‘harmless’ ones by introducing new points. All these algorithms achieve an optimal running time, O(ن سجل ن).

In dimensions more than two, the known results are sparse. The complexity of the Voronoi diagram for ن line segments in د-space may be as large as Ω(ن د − 1 ), as was observed by Aronov [ 17 ]. By the relationship of Voronoi diagrams to lower envelopes of hypersurfaces (see Subsection 4.6 ), the results in Sharir [ 234 ] imply an upper bound of roughly O(n d ). No better upper bounds are known even for line segments in 3-space.

The Voronoi diagram for ن spheres in د-space has a size of only O(ند/2⌡ + 1 ) by its relationship to power diagrams proved in Aurenhammer and Imai [ 30 ].

A case of particular interest in several applications is the medial axis م(ص) of a (generally non-convex) polyhedron ص in 3-space. م(ص) contains pieces of parabolic and hyperbolic surfaces and thus has a fairly complicated structure. A practical and numerically stable algorithm for computing م(ص) is proposed in Milenkovic [ 198 ].


شاهد الفيديو: فيديو 3 دالة اويلر (شهر اكتوبر 2021).