روش FEE
در ریاضی، روش FEE روشی سریع برای حمع بندی سریهای است که به یک فرم خاص هستند. در سال ۱۹۹۰ این روش توسط Ekaterina A. Karatsuba[۱][۲] و FEE نامیده شد - ارزیابی فوری E-function - زیرا محاسبات سریع Siegel را انجام میدهد. توابع ممکن است، مخصوصاً از .
سیگل گروهی از توابع را که «مانند تابعهای نمایی» هستند، «تابع E» نامید.[۳] از جمله این توابع میتوان به توابع خاص مثل تابع فوق هندسی، استوانه، توابع کروی و … اشاره کرد.
قضیه مقابل را با استفاده از FEE میتوان اثبات نمود:
قضیه: فرض میکنیم که اگر یک تابع استعلایی مقدماتی باشد، یعنی تابع نمایی باشد یا یک تابع مثلثاتی، یا یک تابع جبری ابتدایی، یا برهم نهی آنها، یا معکوس آنها، یا برهم نهی معکوسها. و بعد داریم:
در فرمول فوق: پیچیدگی محاسبه (bit) تابع است باn رقم دقت، پیچیدگی ضرب دو است اعداد صحیح n رقمی
الگوریتمهای که اساس آنها مبتنی بر روش FEE هستند روشی برای محاسبه فوری هر تابع ابتدایی ماورایی برای هر مقدار آرگومان، ثوابت کلاسیک e. اویلرر کاتالان و آپری،[۴] توابع ماورایی بالاتر مثل تابع گامای اویلر و مشتقات آن، توابع ابر هندسی، توابع[۵] کروی، توابع استوانه ای و برخی از تابعهای دیگر برای مقادیر جبری آرگومان و پارامترها، تابع زتای ریمان برای مقدارهای صحیح آرگومان[۶][۷] و تابع زتای هورویتز برای آرگومان عدد صحیح و مقدارهای جبری پارامتر،[۸] و به شکل مشابهی انتگرالهای ویژه ای نظیر انتگرال احتمال، انتگرال فرنل، تابع نمای انتگرال، و برخی از انتگرالهای دیگر[۹] برای مقدارهای جبری استدلال با حد بالای پیچیدگی که به حد بهینه نزدیک است شامل میشوند، پس داریم:
الان، تنها هزینه ایجاد میکند به محاسبه فوری مقدارهای توابع از گروهی از توابع برتر بالاتر،[۱۰] برخی انتگرال خاص از فیزیک و ریاضی از جمله ثابت کلاسیک به عنوان ثابت اویلرو ثابت کاتالان است[۱۱] و ثابت Apery کوتاه است. امکان موازی سازی الگوریتمها بر اساس FEE است مزیت اضافی روش FEE.
FEE-محاسبه ثابتهای کلاسیک
ویرایشمیتوان از فرمول اویلر به صورت زیر برای سنجش فوری و سریع ثابت استفاده نمود و مطابق بخش پایین میتوان از FEE برای محاسبه محموع جملات تیلور استفاده کرد.
و برای
میتوان از سایر تقریبها برای حساب کردن توسط FEE نیز استفاده کرد[۱۲] با این حال درتمام حالات برای پیچیدگی داریم:
برای حساب کردن گامای ثابت اویلر با n رقم دقت، باید با دو سری FEE جمع شوند. پس داریم:
برای بررسی فوری و سریع ثابت برای سایر تقریبها امکان اعمال FEE وجود دارد.[۱۳]
FEE-محاسبه سریهای توان خاص
ویرایشمیتوان دو سری زیر را با استفاده از FEE سریع حساب کرد پس داریم:
فرض میکنیم که اعدادی صحیح هستند
و ثابت هستند و عددی جبری است و برای پیچیدگی ارزیابی آن داریم:
جزئیات FEE در مثال محاسبه سریع ثابت کلاسیک e
ویرایشبرای ارزیابی ثابت گرفتن ، شرایط سری تیلور برای
ما در اینجا m را طوری انتخاب میکنیم که نیاز آن به باقی مانده به طوریکه نابرابری مقابل را داشته باشیم برطرف میشود. برای مثال زمانی که ، ما را به طوری در نظر میگیریم که عدد طبیعی توسط نامساویها مشخص میگردد و داریم:
جمع را محاسبه میکنیم
و در k مرحله فرایند زیر داریم:
مرحله ۱. ترکیب در مجموعها را به صورت دوتایی از داخل پرانتز عامل مشترک «بدیهی» را انجام میدهیم و حساب میکنیم پس داریم:
ما مقداریهای صحیح عبارتهای داخل پرانتز را حساب میکنیم، یعنی داریم:
پس، در مرحله اول مجموع در است
در اولین قدم اعداد صحیح فرم
حساب میگردند. بعد از آن به روشی مانند آن عمل مینماییم: در هر مرحله مجموع جمع را به صورت جفت و متوالی ترکیب میکنیم ، فاکتور مشترک «بدیهی» را از براکتها خارج مینماییم و فقط مقدارهای صحیح عبارات داخل پرانتز را محاسبه میکنیم. فرض کنید که اولی مراحل این فرایند تکمیل شدهاست.
و غیره.
قسمت آخر. عددی صحیح را حساب مینماییم ما با استفاده از الگوریتم فوری که پیش تر بررسی شد، حساب مینماییم و تقسیمی از عدد صحیح انجام دهید توسط عدد صحیح با دقت تا ارقام نتیجه به دست آمده حاصل جمع است پیچیدگی همه محاسبات تا n رقم برابر است یا ثابت .
جستارهای وابسته
ویرایش- الگوریتمهای سریع
- روش AGM
- پیچیدگی محاسباتی
منابع
ویرایش- ↑ E. A. Karatsuba, Fast evaluations of transcendental functions. Probl. Peredachi Informat. , Vol. 27, No. 4, (1991)
- ↑ D. W. Lozier and F. W. J. Olver, Numerical Evaluation of Special Functions. Mathematics of Computation 1943–1993: A Half-Century of Computational Mathematics, W. Gautschi, eds. , Proc. Sympos. Applied Mathematics, AMS, Vol. 48 (1994).
- ↑ C. L. Siegel, Transcendental numbers. Princeton University Press, Princeton (1949).
- ↑ Karatsuba E. A. , Fast evaluation of , Probl. Peredachi Informat. , Vol. 29, No. 1 (1993)
- ↑ Ekatharine A. Karatsuba, Fast evaluation of hypergeometric function by FEE. Computational Methods and Function Theory (CMFT'97), N. Papamichael, St. Ruscheweyh and E. B. Saff, eds. , World Sc. Pub. (1999)
- ↑ E. A. Karatsuba, Fast Evaluation of Riemann zeta-function for integer values of argument . Probl. Peredachi Informat. , Vol. 31, No. 4 (1995).
- ↑ J. M. Borwein, D. M. Bradley and R. E. Crandall, Computational strategies for the Riemann zeta function. J. of Comput. Appl. Math. , Vol. 121, No. 1–2 (2000).
- ↑ E. A. Karatsuba, Fast evaluation of Hurwitz zeta function and Dirichlet -series, Problem. Peredachi Informat. , Vol. 34, No. 4, pp. 342–353, (1998).
- ↑ E. A. Karatsuba, Fast computation of some special integrals of mathematical physics. Scientific Computing, Validated Numerics, Interval Methods, W. Kramer, J. W. von Gudenberg, eds.(2001).
- ↑ E. Bach, The complexity of number-theoretic constants. Info. Proc. Letters, No. 62 (1997).
- ↑ E. A. Karatsuba, Fast computation of $\zeta(3)$ and of some special integrals ,using the polylogarithms, the Ramanujan formula and its generalization. J. of Numerical Mathematics BIT, Vol. 41, No. 4 (2001).
- ↑ D. H. Bailey, P. B. Borwein and S. Plouffe, On the rapid computation of various polylogarithmic constants. Math. Comp. , Vol. 66 (1997).
- ↑ R. P. Brent and E. M. McMillan, Some new algorithms for high-precision computation of Euler's constant. Math. Comp. , Vol. 34 (1980).