نظرية التقريب

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

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

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

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

بمجرد اختيار مجال (عادةً ما يكون فترة) ودرجة متعددة الحدود، يتم اختيار متعددة الحدود نفسها بطريقة تقلل من أسوأ خطأ. أي أن الهدف هو تقليل القيمة القصوى لـ${\displaystyle \mid P(x)-f(x)\mid }$حيث P ( x ) هي متعددة الحدود التقريبية، و f ( x ) هي الدالة الفعلية، و x تتغير على الفترة المختارة. بالنسبة للدوال المنتظمة، توجد متعددة حدود من الدرجة N تؤدي إلى منحنى خطأ يتذبذب ذهابًا وإيابًا بين${\displaystyle +\varepsilon }$و${\displaystyle -\varepsilon }$بإجمالي N + 2 مرة، مما يعطي خطأ في أسوأ الحالات قدره${\displaystyle \varepsilon }$يُلاحظ وجود متعددة حدود من الدرجة N قادرة على استيفاء N +1 نقطة على منحنى. وتؤكد نظرية التذبذب المتساوي أن هذه المتعددة الحدود هي الأمثل دائمًا . من الممكن ابتكار دوال f ( x ) لا توجد لها متعددة حدود مماثلة، لكن هذا نادر الحدوث عمليًا.

على سبيل المثال، تُظهر الرسوم البيانية المعروضة على اليمين الخطأ في تقريب log(x) و exp(x) عندما N  =  4. المنحنيات الحمراء، لكثير الحدود الأمثل، مستوية ، أي أنها تتذبذب بين${\displaystyle +\varepsilon }$و${\displaystyle -\varepsilon }$بالضبط. في كل حالة، يكون عدد القيم القصوى هو N + 2، أي 6. اثنتان من القيم القصوى تقعان عند نهايتي الفترة، على الحافتين اليسرى واليمنى للرسوم البيانية.

لإثبات صحة ذلك بشكل عام، لنفترض أن P دالة حدود من الدرجة N تتمتع بالخاصية الموصوفة، أي أنها تُنتج دالة خطأ لها N  +  2 قيمة قصوى، ذات إشارات متناوبة وقيم متساوية. يُظهر الرسم البياني الأحمر على اليمين كيف قد تبدو دالة الخطأ هذه عندما N  =  4. لنفترض أن Q ( x ) (التي تظهر دالة خطأها باللون الأزرق على اليمين) دالة حدود أخرى من الدرجة N تُعدّ تقريبًا أفضل للدالة f من P. على وجه الخصوص، تكون Q أقرب إلى f من P لكل قيمة _xᵢ حيث تظهر قيمة قصوى لـ P − f ، لذا

${\displaystyle |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|.}$

عندما تحدث قيمة عظمى لـ P − f عند x _i ، فإن

${\displaystyle Q(x_{i})-f(x_{i})\leq |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|=P(x_{i})-f(x_{i}),}$

وعندما تحدث أدنى قيمة لـ P − f عند x _i ، فإن

${\displaystyle f(x_{i})-Q(x_{i})\leq |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|=f(x_{i})-P(x_{i}).}$

كما هو موضح في الرسم البياني، يجب أن تتبادل الدالة [ _P ( x ) -  f ( x ) ] - [ Q ( x ) - f ( x ) ] إشاراتها لقيم xᵢ N + 2. ولكن هذه الدالة تُختزل إلى P ( x ) - Q ( x ) وهي دالة كثيرة الحدود من الدرجة N. تغير هذه الدالة إشارتها N + 1 مرة على الأقل، لذا ، وفقًا لنظرية القيمة المتوسطة ، فإن لها N + 1 جذرًا ، وهو أمر مستحيل بالنسبة لكثيرة حدود من الدرجة N.               

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

إذا قام المرء بحساب معاملات متسلسلة تشيبيشيف لدالة ما:

${\displaystyle f(x)\sim \sum _{i=0}^{\infty }c_{i}T_{i}(x)}$

ثم يقطع المسلسل بعد ذلك${\displaystyle T_{N}}$عند هذا الحد، يحصل المرء على متعدد حدود من الدرجة N يقارب f ( x ).

يكمن سبب كون هذه المعادلة متعددة الحدود شبه مثالية في أنه بالنسبة للدوال ذات متسلسلات القوى المتقاربة بسرعة، إذا تم قطع المتسلسلة بعد حد معين، فإن الخطأ الكلي الناتج عن القطع يكون قريبًا من الحد الأول بعد القطع. أي أن الحد الأول بعد القطع يهيمن على جميع الحدود اللاحقة. وينطبق الأمر نفسه إذا كان التوسع بدلالة كثيرات حدود الانحناء. إذا تم قطع متسلسلة تشيبيشيف بعد${\displaystyle T_{N}}$، سيتخذ الخطأ شكلاً قريباً من مضاعفات${\displaystyle T_{N+1}}$. تتميز كثيرات حدود تشيبيشيف بخاصية أنها مستوية - فهي تتذبذب بين +1 و -1 في الفترة [-1، 1].${\displaystyle T_{N+1}}$يحتوي على N + 2 من القيم القصوى. هذا يعني أن الخطأ بين f ( x ) وتوسيع تشيبيشيف الخاص بها يصل إلى${\displaystyle T_{N}}$يقترب من دالة مستوى ذات N +2 قيم قصوى، لذا فهو قريب من متعدد الحدود الأمثل من الدرجة N.

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

يُعد تقريب تشيبيشيف أساسًا لتقنية التكامل العددي كلينشو-كورتيس .

تُستخدم خوارزمية ريميز (أو ريميس) لإنتاج متعددة حدود مثلى P ( x ) تُقارب دالة معطاة f ( x ) على فترة معينة. وهي خوارزمية تكرارية تتقارب إلى متعددة حدود ذات دالة خطأ تحتوي على N +2 نقطة قصوى. وبحسب النظرية المذكورة أعلاه، فإن متعددة الحدود هذه هي المثلى.

تستخدم خوارزمية ريميز حقيقة أنه يمكن للمرء إنشاء متعدد حدود من الدرجة N يؤدي إلى قيم خطأ مستوية ومتناوبة، مع الأخذ في الاعتبار N + 2 نقطة اختبار.

بافتراض وجود N + 2 نقطة اختبار${\displaystyle x_{1}}$،${\displaystyle x_{2}}$...${\displaystyle x_{N+2}}$(أين${\displaystyle x_{1}}$و${\displaystyle x_{N+2}}$(يفترض أن هذه هي نقاط نهاية فترة التقريب)، يجب حل هذه المعادلات:

${\displaystyle {\begin{aligned}P(x_{1})-f(x_{1})&=+\varepsilon \\P(x_{2})-f(x_{2})&=-\varepsilon \\P(x_{3})-f(x_{3})&=+\varepsilon \\&\ \ \vdots \\P(x_{N+2})-f(x_{N+2})&=\pm \varepsilon .\end{aligned}}}$

تتبادل الجوانب اليمنى في الإشارة.

إنه،

${\displaystyle {\begin{aligned}P_{0}+P_{1}x_{1}+P_{2}x_{1}^{2}+P_{3}x_{1}^{3}+\dots +P_{N}x_{1}^{N}-f(x_{1})&=+\varepsilon \\P_{0}+P_{1}x_{2}+P_{2}x_{2}^{2}+P_{3}x_{2}^{3}+\dots +P_{N}x_{2}^{N}-f(x_{2})&=-\varepsilon \\&\ \ \vdots \end{aligned}}}$

منذ${\displaystyle x_{1}}$...${\displaystyle x_{N+2}}$تم منحهم جميع صلاحياتهم، وهي معروفة، و${\displaystyle f(x_{1})}$...${\displaystyle f(x_{N+2})}$وهي معروفة أيضاً. وهذا يعني أن المعادلات المذكورة أعلاه هي ببساطة N + 2 معادلات خطية في N + 2 متغيرات.${\displaystyle P_{0}}$،${\displaystyle P_{1}}$...${\displaystyle P_{N}}$، و${\displaystyle \varepsilon }$بالنظر إلى نقاط الاختبار${\displaystyle x_{1}}$...${\displaystyle x_{N+2}}$يمكن حل هذا النظام للحصول على متعددة الحدود P والعدد${\displaystyle \varepsilon }$.

يوضح الرسم البياني أدناه مثالاً على ذلك، حيث ينتج عنه متعددة حدود من الدرجة الرابعة تقارب${\displaystyle e^{x}}$على الفترة [−1, 1]. تم تحديد نقاط الاختبار عند −1، −0.7، −0.1، +0.4، +0.9، و1. هذه القيم موضحة باللون الأخضر. القيمة الناتجة هي${\displaystyle \varepsilon }$يساوي 4.43 × ^10⁻⁴

يأخذ الرسم البياني للخطأ القيم بالفعل${\displaystyle \pm \varepsilon }$عند نقاط الاختبار الست، بما في ذلك النقاط الطرفية، ولكن هذه النقاط ليست نقاطًا قصوى. إذا كانت نقاط الاختبار الداخلية الأربع نقاطًا قصوى (أي أن الدالة P ( x ) f ( x ) لها قيم عظمى أو صغرى عند هذه النقاط)، فإن متعددة الحدود ستكون مثالية.

تتمثل الخطوة الثانية من خوارزمية ريميز في نقل نقاط الاختبار إلى المواقع التقريبية التي كانت عندها دالة الخطأ تحقق قيمها العظمى أو الصغرى المحلية الفعلية. على سبيل المثال، يمكن استنتاج من الرسم البياني أن النقطة عند -0.1 كان ينبغي أن تكون عند -0.28 تقريبًا. تُنفذ هذه الخطوة في الخوارزمية باستخدام جولة واحدة من طريقة نيوتن . وبما أن المشتقة الأولى والثانية لـ P ( x ) - f ( x ) معروفة ، يمكن حساب المسافة التقريبية التي يجب نقل نقطة الاختبار إليها حتى تصبح المشتقة صفرًا.

حساب مشتقات كثير الحدود أمرٌ بسيط. يجب أيضًا أن يكون المرء قادرًا على حساب المشتقة الأولى والثانية للدالة f ( x ). تتطلب خوارزمية ريميز القدرة على حساب${\displaystyle f(x)\,}$،${\displaystyle f'(x)\,}$، و${\displaystyle f''(x)\,}$بدقة عالية للغاية. يجب تنفيذ الخوارزمية بأكملها بدقة أعلى من الدقة المطلوبة للنتيجة.

بعد تحريك نقاط الاختبار، تُعاد معالجة المعادلة الخطية، فنحصل على متعددة حدود جديدة، ثم تُستخدم طريقة نيوتن مرة أخرى لتحريك نقاط الاختبار مجددًا. يستمر هذا التسلسل حتى تتقارب النتيجة إلى الدقة المطلوبة. تتقارب الخوارزمية بسرعة كبيرة. يكون التقارب تربيعيًا للدوال المنتظمة - إذا كانت نقاط الاختبار ضمن${\displaystyle 10^{-15}}$من النتيجة الصحيحة، ستكون تقريبًا ضمن${\displaystyle 10^{-30}}$من النتيجة الصحيحة بعد الجولة التالية.

تبدأ خوارزمية ريميز عادةً باختيار القيم القصوى لكثير حدود تشيبيشيف${\displaystyle T_{N+1}}$باعتبارها النقاط الأولية، لأن دالة الخطأ النهائية ستكون مشابهة لتلك الدالة متعددة الحدود.

• مجلة نظرية التقريب
• التقريب البنّاء
• مجلة الشرق حول التقريبات

• أخييزر (Akhiezer)، NI (2013) [1956]. نظرية التقريب . ترجمة هيمان، سي جيه دوفر. ISBN 978-0-486-15313-1. OCLC 1067500225 . 
• تيمان، أ. ف. (2014) [1963]. نظرية تقريب الدوال لمتغير حقيقي . السلسلة الدولية في الرياضيات البحتة والتطبيقية. المجلد  34. إلسيفير. ISBN 978-1-4831-8481-4.
• هاستينغز الابن، سي. (2015) [1955]. تقريبات للحواسيب الرقمية . مطبعة جامعة برينستون. ISBN 978-1-4008-7559-7.
• هارت، جيه إف؛ تشيني، إي دبليو ؛ لوسون، سي إل؛ ماهلي، إتش جيه؛ ميزتيني، سي كيه؛ رايس، جيه آر الابن ؛ ثاتشر، إتش سي؛ ويتزغال، سي. (1968). تقريبات الحاسوب . وايلي. OCLC 0471356301 . 
• فوكس، ل.؛ باركر، آي بي (1968). كثيرات حدود تشيبيشيف في التحليل العددي . كتيبات أكسفورد الرياضية. مطبعة جامعة أكسفورد. ISBN 978-0-19-859614-1. OCLC 9036207 . 
• بريس، دبليو إتش ؛ تيوكولسكي، إس إيه ؛ فيترلينغ، دبليو تي؛ فلانيري، بي بي (2007). "الفقرة 5.8: تقريب تشيبيشيف". وصفات عددية: فن الحوسبة العلمية (  الطبعة الثالثة). مطبعة جامعة كامبريدج. ISBN 978-0-521-88068-8.
• كودي الابن، دبليو جيه؛ وايت، دبليو. (1980). دليل برمجي للوظائف الأساسية . برنتيس هول. ISBN 0-13-822064-6. OCLC 654695035 . 
• ريميس (ريمز)، إي (1934). "Sur le calcul Effectif des polynomes d'approximation de Tschebyschef" . سي آر أكاد. الخيال العلمي. (باللغة الفرنسية). 199 : 337 – 340.
• ستيفنز، ك. ج. (2006). أناستاسيو، جورج أ. (محرر). تاريخ نظرية التقريب: من أويلر إلى برنشتاين . بيركهاوزر. doi : 10.1007/0-8176-4475-X . ISBN 0-8176-4353-2.
• إرديلي، ت. (2008). "امتدادات نظرية بلوخ-بوليا حول عدد الأصفار الحقيقية المميزة لكثيرات الحدود" . مجلة نظرية الأسماء في بوردو . 20 : 281– 7. دوى : 10.5802/jtnb.627 .
• إرديلي، ت. (2009). "متباينة ريميز للتركيبات الخطية للدوال الغاوسية المزاحة". وقائع الجمعية الفلسفية في كامبريدج . 146 (3): 523-530 . doi : 10.1017/S0305004108001849 .
• تريفثين، إل إن (2020). نظرية التقريب وممارسة التقريب . سيام. رقم ISBN 978-1-61197-594-9.الفصول من 1 إلى 6 من طبعة 2013

• تاريخ نظرية التقريب (HAT)
• دراسات استقصائية في نظرية التقريب (SAT)