تقريب تشيبيشيف والتقريب المصغر الأقصى (Minimax)

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

Definition

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

Scope

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

Core questions

• ما الذي يميز أفضل تقريب موحد، ولماذا هو فريد؟
• لماذا تُعد متعددات حدود تشيبيشيف أساسية للتقريب متعدد الحدود شبه الأمثل؟
• كيف تحسب خوارزمية ريميز التقريب المصغر الأقصى الحقيقي بشكل تكراري؟
• متى يكون التوافق المصغر الأقصى مفضلاً على التوافق بأقل المربعات، وما هي التكلفة الحسابية لذلك؟

Key theories

نظرية التذبذب المتساوي

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

شبه أمثلية تقريب تشيبيشيف

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

خوارزمية ريميز التبادلية

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

Mechanisms

تبدأ خوارزمية ريميز بتخمين لنقاط التذبذب المتساوي، وتحل نظامًا خطيًا صغيرًا بحيث يتذبذب الخطأ بشكل متساوٍ في المقدار وبإشارة متناوبة على تلك المجموعة المرجعية، ثم تعيد تحديد النقاط المرجعية إلى أقصى قيم الخطأ الجديدة وتكرر العملية؛ وتتقارب الإجراءات تربيعيًا نحو حل المصغر الأقصى. بدلاً من ذلك، يقوم تقريب تشيبيشيف بتوسيع الدالة في متعددات حدود تشيبيشيف — التي يمكن حسابها بكفاءة عبر تحويل فورييه السريع — مستغلاً خاصية المعيار الأقصى الأدنى (minimal sup-norm) للحصول على دقة شبه مثالية دون تكرار.

Clinical relevance

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

History

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

Key figures

• Pafnuty Chebyshev
• Evgeny Remez
• Lloyd N. Trefethen

Seminal works

• trefethen2013
• powell1981
• cheney1966

Frequently asked questions

ماذا يعني التذبذب المتساوي بشكل بديهي؟

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

لماذا نستخدم استيفاء تشيبيشيف بدلاً من متعدد الحدود المصغر الأقصى الدقيق؟

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