خوارزمية ريميز


خوارزمية ريميز أو خوارزمية تبادل ريميز، التي نشرها وجيني ياكوفليفيتش ريمز في عام 1934 ، هي خوارزمية تكرارية تستخدم لإيجاد تقريب بسيط للدالات وتحديدا التقريبات بواسطة الدوال في مساحة تشيبيشيف التي تكون الأفضل في المعيار الموحد بمعنى L. [1] يشار إليه أحيانًا باسم خوارزمية ريميس أو خوارزمية ريم

ويشكل مثالًا نموذجيًا لفضاء شيبيشيف الفرعي، الفضاء الفرعي للدوال الجزئية شيبيشيف من الرتبة n في فضاء الدوال المستمرة الحقيقية على فترة محددة، C [a، b]. يتم تحديد الدالة الجزئية الأفضل تقريبًا داخل الفضاء الفرعي المحدد بأنها تقلل الفرق المطلق الأقصى بين الدالة الجزئية والدالة المستهدفة. وفي هذه الحالة، يتم تحديد شكل الحل بدقة بواسطة نظرية التذبذب المتساوي.

الإجراء

عدل

تبدأ خوارزمية ريميز بالدالة   لتقريب ومجموعة   ل   نقاط العينة   في الفاصل الزمني التقريبي ، عادةً ما يتم تعيين أقصى حدود تشيبيشيف متعدد الحدود خطيًا إلى الفترة. الخطوات هي:

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

والنتيجة تسمى كثير الحدود لأفضل تقريب أو خوارزمية الحد الأدنى للتقريب .

قدم دبليو فريزر مراجعة للجوانب الفنية في تنفيذ خوارزمية ريميز.[2]

اختيار التهيئة

عدل

تعتبر عقد تشيبيشيف خيارًا شائعًا للتقريب الأولي بسبب دورها في نظرية الاستيفاء متعدد الحدود. لتهيئة مشكلة التحسين للدالة f بواسطة متعدد حدود لاغرانج L n ( f ) ، يمكن إظهار أن هذا التقريب الأولي مقيد بـ

 

مع القاعدة أو ثابت ليبيج لمشغل الاستيفاء لاغرانج L n للعقد ( t 1 ، ...، t n + 1 ) يجري

 

T كونها أصفار تشيبيشيف متعدد الحدود ، و ليبيج دالة كونها:

 

أثبت ثيودور إيه كيلجور ، [3] وكارل دي بور ، وألان بينكوس [4] وجود حرف t فريد لكل L n ، على الرغم من عدم معرفته صراحةً عن كثيرات الحدود (العادية). بصورة مماثلة،   ، ويمكن التعبير عن أمثلية اختيار العقد كـ  

بالنسبة لعقد تشيبيشيف ، التي توفر خيارًا دون المستوى الأمثل ، ولكن صريحًا من الناحية التحليلية ، يُعرف السلوك المقارب باسم [5]

 

( γ كونه ثابت أويلر-ماسكيروني ) مع

  ل  

والحد الأعلى [6]

 

حصل ليف بروتمان [7] على الحدود   ، و   كونها أصفار متعددات حدود تشيبيشيفالموسعة:

 

حصل روديجر جونتنر على [8] تقدير أكثر دقة لـ  

 

مناقشة مفصلة

عدل

يوفر هذا القسم مزيدًا من المعلومات حول الخطوات الموضحة أعلاه. في هذا القسم ، يتم تشغيل الفهرس i من 0 إلى n +1.

الخطوة 1: معطى   ، حل النظام الخطي من المعادلات n +2

  (أين   ) ،
للمجهولين   و هـ .

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

حساب التداخل القياسي من الدرجة n   ل   في العقد الأول n +1 وأيضًا المقحم القياسي من الدرجة n   على الاحداثيات  

 

تحقيقا لهذه الغاية ، استخدم في كل مرة صيغة الاستيفاء لنيوتن مع الفروق المقسمة في الترتيب   و   عمليات حسابية.

كثير الحدود   له رقم i -th صفر بين   و   ، وبالتالي لا مزيد من الأصفار بين   و   :   و   لها نفس العلامة   .

التركيبة الخطية   هي أيضًا كثيرة حدود من الدرجة n و

 

هذه هي نفس المعادلة أعلاه لـ   ولأي اختيار من E. نفس المعادلة لـ i = n +1 هي

  ويحتاج إلى تفكير خاص: حل للمتغير E ، هو تعريف E :
 

كما ذكر أعلاه ، فإن المصطلحين في المقام لهما نفس العلامة: E وبالتالي   دائمًا ما تكون محددة جيدًا.

الخطأ في العقد المحددة n +2 موجب وسالب بدوره لأن

 

تنص نظرية شارل جون دو لا فالي بوسان على أنه في ظل هذه الحالة لا يوجد كثير حدود من الدرجة n مع وجود خطأ أقل من E. في الواقع ، إذا وجدت مثل هذه كثيرة الحدود ، فسمها   ثم الاختلاف   سيظل موجبًا / سلبيًا عند n +2 عقد   وبالتالي تحتوي على n +1 أصفار على الأقل وهو أمر مستحيل بالنسبة لكثيرات الحدود من الدرجة n . وبالتالي ، فإن هذا E هو الحد الأدنى للحد الأدنى للخطأ الذي يمكن تحقيقه مع كثيرات الحدود من الدرجة n .

الخطوة 2 تغير التدوين من   ل   .

الخطوة 3 تعمل على تحسين عقد الإدخال   وأخطائهم   على النحو التالي.

في كل منطقة P ، العقدة الحالية   يتم استبداله بالمكبر المحلي   وفي كل منطقة N   مع المصغر المحلي. (يتوقع   في A ، و   قريب   ، و   عند B. ) ليست هناك حاجة إلى دقة عالية هنا ، يجب أن يكون البحث القياسي عن الخط مع بضع نوبات تربيعية كافياً. (انظر [9] )

يترك   . كل سعة   أكبر من أو يساوي E. تنطبق أيضًا نظرية شارل جون دو لا فالي بوسان وإثباتها   مع   كالحد الأدنى الجديد لأفضل خطأ ممكن مع كثيرات الحدود من الدرجة n .

علاوة على ذلك،   يأتي في متناول اليد باعتباره حدًا أعلى واضحًا لأفضل خطأ ممكن.

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

المتغيرات

عدل

بعض التعديلات على الخوارزمية موجودة في الأدبيات.[10] وتشمل هذه:

  • استبدال أكثر من نقطة عينة واحدة بمواقع الاختلافات المطلقة القصوى القريبة. [ بحاجة لمصدر ]
  • استبدال جميع نقاط العينة بتكرار واحد بمواقع الكل ، والتناوب ، والحد الأقصى للاختلافات.[11]
  • استخدام الخطأ النسبي لقياس الفرق بين التقريب والوظيفة ، خاصة إذا كان سيتم استخدام التقريب لحساب الوظيفة على جهاز كمبيوتر يستخدم حساب الفاصلة العائمة ؛
  • بما في ذلك قيود نقطة الخطأ الصفري.[11]
  • متغير فريزر هارت ، يستخدم لتحديد أفضل تقريب منطقي لـ تشيبيشيف.[12]

أنظر أيضا

عدل

مراجع

عدل
  1. ^ E. Ya. Remez, "Sur la détermination des polynômes d'approximation de degré donnée", Comm. Soc. Math. Kharkov 10, 41 (1934);
    "Sur un procédé convergent d'approximations successives pour déterminer les polynômes d'approximation, Compt. Rend. Acad. Sc. 198, 2063 (1934);
    "Sur le calcul effectiv des polynômes d'approximation des Tschebyscheff", Compt. Rend. Acade. Sc. 199, 337 (1934).
  2. ^ Fraser، W. (1965). "A Survey of Methods of Computing Minimax and Near-Minimax Polynomial Approximations for Functions of a Single Independent Variable". J. ACM. ج. 12 ع. 3: 295–314. DOI:10.1145/321281.321282.
  3. ^ Kilgore، T. A. (1978). "A characterization of the Lagrange interpolating projection with minimal Tchebycheff norm". J. Approx. Theory. ج. 24 ع. 4: 273–288. DOI:10.1016/0021-9045(78)90013-8.
  4. ^ de Boor، C.؛ Pinkus، A. (1978). "Proof of the conjectures of Bernstein and Erdös concerning the optimal nodes for polynomial interpolation". Journal of Approximation Theory. ج. 24 ع. 4: 289–303. DOI:10.1016/0021-9045(78)90014-X.
  5. ^ Luttmann، F. W.؛ Rivlin، T. J. (1965). "Some numerical experiments in the theory of polynomial interpolation". IBM J. Res. Dev. ج. 9 ع. 3: 187–191. DOI:10.1147/rd.93.0187.
  6. ^ T. Rivlin, "The Lebesgue constants for polynomial interpolation", in Proceedings of the Int. Conf. on Functional Analysis and Its Application, edited by H. G. Garnier et al. (Springer-Verlag, Berlin, 1974), p. 422; The Chebyshev polynomials (Wiley-Interscience, New York, 1974).
  7. ^ Brutman، L. (1978). "On the Lebesgue Function for Polynomial Interpolation". SIAM J. Numer. Anal. ج. 15 ع. 4: 694–704. Bibcode:1978SJNA...15..694B. DOI:10.1137/0715046.
  8. ^ Günttner، R. (1980). "Evaluation of Lebesgue Constants". SIAM J. Numer. Anal. ج. 17 ع. 4: 512–520. Bibcode:1980SJNA...17..512G. DOI:10.1137/0717043.
  9. ^ David G. Luenberger: Introduction to Linear and Nonlinear Programming, Addison-Wesley Publishing Company 1973.
  10. ^ Egidi, Nadaniela; Fatone, Lorella; Misici, Luciano (2020), Sergeyev; Kvasov, Dmitri E. (eds.), "A New Remez-Type Algorithm for Best Polynomial Approximation", Numerical Computations: Theory and Algorithms (بالإنجليزية), Cham: Springer International Publishing, vol. 11973, pp. 56–69, DOI:10.1007/978-3-030-39081-5_7, ISBN:978-3-030-39080-8, Archived from the original on 2022-03-19, Retrieved 2022-03-19
  11. ^ ا ب Temes, G.C.; Barcilon, V.; Marshall, F.C. (1973). "The optimization of bandlimited systems". Proceedings of the IEEE. 61 (2): 196–234. doi:10.1109/PROC.1973.9004. ISSN 0018-9219.
  12. ^ Dunham, Charles B. (1975). "Convergence of the Fraser-Hart algorithm for rational Chebyshev approximation". Mathematics of Computation (بالإنجليزية). 29 (132): 1078–1082. DOI:10.1090/S0025-5718-1975-0388732-9. ISSN:0025-5718. Archived from the original on 2022-05-09.

روابط خارجية

عدل