تقریب چبیشف و مینیمکس
تقریب مینیمکس به دنبال تقریبی است که بزرگترین خطای آن تا حد امکان کوچک باشد و تضمین دقت یکنواخت را ارائه دهد؛ چندجملهایهای چبیشف و الگوریتم رمِز ابزارهای اصلی برای محاسبه و درک چنین بهترین تقریبهای یکنواختی هستند.
Definition
تقریب مینیمکس عبارت است از تعیین تقریبی که حداکثر خطای مطلق را در دامنه به حداقل میرساند، و تقریب چبیشف مجموعهای از نظریهها و روشها است که حول چندجملهایهای چبیشف ساخته شده و این بهترین برازش یکنواخت را ارائه میدهد یا به آن بسیار نزدیک میشود.
Scope
این موضوع بهترین تقریب یکنواخت (مینیمکس) در نرم بینهایت، قضیه همنوسانی چبیشف، نقش و نزدیکی به بهینگی چندجملهایهای چبیشف و درونیابی چبیشف، و الگوریتم تبادل رمِز برای محاسبه تقریبهای چندجملهای و گویا مینیمکس را پوشش میدهد.
Core questions
- چه چیزی بهترین تقریب یکنواخت را مشخص میکند و چرا منحصر به فرد است؟
- چرا چندجملهایهای چبیشف برای تقریب چندجملهای نزدیک به بهینه محوری هستند؟
- الگوریتم رمِز چگونه تقریب مینیمکس واقعی را به صورت تکراری محاسبه میکند؟
- چه زمانی برازش مینیمکس به برازش حداقل مربعات ترجیح داده میشود و با چه هزینه محاسباتی؟
Key theories
- قضیه همنوسانی
- یک چندجملهای با درجه حداکثر n بهترین تقریب یکنواخت برای یک تابع پیوسته است اگر و تنها اگر خطای آن حداکثر مقدار خود را با علائم متناوب در حداقل n+2 نقطه به دست آورد؛ این ویژگی بهترین تقریب را منحصر به فرد و قابل محاسبه میسازد.
- نزدیکی به بهینگی تقریب چبیشف
- درونیابی یا بسط در چندجملهایهای چبیشف در نقاط چبیشف، تقریبهایی را به دست میدهد که حداکثر خطای آنها در یک عامل کوچک و با رشد لگاریتمی از بهترین حالت ممکن قرار دارد، بنابراین روشهای چبیشف جایگزینی ارزان برای برازشهای مینیمکس واقعی فراهم میکنند.
- الگوریتم تبادل رمِز
- الگوریتم رمِز به صورت تکراری مجموعهای از نقاط مرجع کاندید را تنظیم میکند تا شرط همنوسانی را اعمال کند و به سرعت به بهترین تقریب چندجملهای یا گویای مینیمکس دقیق همگرا میشود.
Mechanisms
الگوریتم رمِز با حدسی از نقاط همنوسانی آغاز میشود، یک سیستم خطی کوچک را حل میکند تا خطا با اندازه مساوی و علامت متناوب در آن مجموعه مرجع همنوسان شود، سپس نقاط مرجع را به اکسترممهای خطای جدید منتقل کرده و تکرار میکند؛ این رویه به صورت درجه دوم به حل مینیمکس همگرا میشود. تقریب چبیشف به جای آن، تابع را در چندجملهایهای چبیشف بسط میدهد — که به طور کارآمد از طریق تبدیل فوریه سریع قابل محاسبه است — و از ویژگی نرم سوپریموم حداقل آنها برای دستیابی به دقتی نزدیک به بهترین بدون تکرار بهره میبرد.
Clinical relevance
تقریب مینیمکس و چبیشف برای ساخت روالهای توابع ابتدایی در کتابخانههای ریاضی، طراحی فیلترهای دیجیتال با خطای پاسخ فرکانسی یکنواخت، و ساخت تقریبهای فشرده و با دقت یکنواخت برای محاسبات جاسازیشده و بلادرنگ که در آنها کران خطای بدترین حالت مهمتر از خطای متوسط است، استفاده میشوند.
History
این نظریه با مطالعه چبیشف در قرن نوزدهم در مورد بهترین تقریب یکنواخت و اصل همنوسانی آغاز شد؛ یوگنی رمِز الگوریتم تبادل خود را در دهه ۱۹۳۰ ابداع کرد، و محاسبات مبتنی بر چبیشف در اواخر قرن بیستم به یک رکن عملی نرمافزارهای عددی تبدیل شد، به ویژه از طریق فناوری چبیشف بدون مشتقگیری خودکار در سیستمهای مدرن.
Key figures
- Pafnuty Chebyshev
- Evgeny Remez
- Lloyd N. Trefethen
Related topics
Seminal works
- trefethen2013
- powell1981
- cheney1966
Frequently asked questions
- همنوسانی به صورت شهودی به چه معناست؟
- به این معنی است که بهترین تقریب یکنواخت خطای خود را به گونهای توزیع میکند که منحنی خطا به طور مکرر به حداکثر ارتفاع خود میرسد، به طور متناوب بین مثبت و منفی، در نقاط کافی. هر کاندیدای دیگری میتواند بهبود یابد، بنابراین این الگوی خطای متعادل نشاندهنده بهینگی است.
- چرا از درونیابی چبیشف به جای چندجملهای مینیمکس دقیق استفاده کنیم؟
- محاسبه چندجملهای مینیمکس دقیق به الگوریتم تکراری رمِز نیاز دارد، در حالی که درونیابی چبیشف سریع و غیرتکراری است و در یک عامل کوچک از بهترین خطای ممکن قرار میگیرد، بنابراین معمولاً انتخاب عملی است.