نمایش مبدأ برای پیش‌نویس:روش FEE

در ریاضی، '''روش FEE روشی سریع برای حمع بندی''' سری‌های است که به یک فرم خاص هستند.  در سال 1990 این روش توسط Ekaterina A. Karatsuba <ref>E. A. Karatsuba, Fast evaluations of transcendental functions. Probl. Peredachi Informat., Vol. 27, No. 4, (1991)</ref> <ref>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).</ref> '''و FEE''' نامیده شد - '''ارزیابی فوری E-function''' - زیرا محاسبات سریع Siegel را انجام می دهد. <math>E</math> توابع ممکن است، مخصوصا از '''<math>e^x.</math>''' .

[[کارل لودویگ زیگل|سیگل]] گروهی از توابع را که «مانند تابع های نمایی» هستند، «تابع E» نامید. <ref>C. L. Siegel,
''Transcendental numbers''. Princeton University Press, Princeton (1949).</ref> از جمله این توابع می توان به [[توابع خاص]] مثل تابع فوق هندسی ، [[تابع بسل|استوانه]] ، [[هماهنگ‌های کروی|توابع کروی]] و ... اشاره کرد.

قضیه مقابل را با استفاده از FEE می توان اثبات نمود:

'''قضیه''' : فرض میکنیم که اگر <math>y=f(x)</math> یک '''[[تابع غیرجبری|تابع استعلایی]] مقدماتی''' باشد، یعنی [[تابع نمایی]] باشد یا یک [[توابع مثلثاتی|تابع مثلثاتی]] ، یا یک تابع جبری ابتدایی ، یا برهم نهی آنها، یا [[تابع وارون|معکوس]] آنها، یا برهم نهی معکوس ها.و بعد داریم :

: <math>
s_f(n) = O(M(n)\log^2n). \,
</math>

در فرمول فوق: پیچیدگی محاسبه (bit)  تابع <math>s_f(n)</math>  است  <math>f(x)</math> باn رقم دقت ، پیچیدگی ضرب دو <math>M(n)</math>  است اعداد صحیح n رقمی

الگوریتم‌های که  اساس آنها مبتنی  بر روش FEE هستند روشی برای محاسبه فوری هر [[تابع غیرجبری|تابع ابتدایی ماورایی]]  برای هر مقدار آرگومان، ثوابت کلاسیک [[E (عدد)|e]] . [[عدد پی|<math>\pi,</math>]]  [[ثابت اویلر–ماسکرونی|اویلرر]] <math>\gamma,</math> [[ثابت کاتالان|کاتالان]] و آپری ، <ref>Karatsuba E. A., Fast evaluation of <math>\zeta(3)</math>, Probl. Peredachi Informat., Vol. 29, No. 1 (1993)</ref> توابع ماورایی بالاتر مثل تابع [[تابع گاما|گامای اویلر]] و مشتقات آن، توابع ابر هندسی ،توابع <ref>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)</ref> [[هماهنگ‌های کروی|کروی]] ، توابع استوانه ای و برخی از تابع های دیگر برای مقادیر [[عدد جبری|جبری]] آرگومان و پارامترها، [[تابع زتای ریمان]] برای مقدار های صحیح آرگومان <ref>E. A. Karatsuba, Fast Evaluation of Riemann zeta-function <math>\zeta(s)</math> for integer values of argument <math>s</math>. Probl. Peredachi Informat., Vol. 31, No. 4 (1995).</ref> <ref>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).</ref> و تابع زتای هورویتز برای آرگومان عدد صحیح و مقدار های جبری پارامتر، <ref>E. A. Karatsuba, Fast evaluation of Hurwitz zeta function and Dirichlet <math>L</math>-series, Problem. Peredachi Informat., Vol. 34, No. 4, pp. 342–353, (1998).</ref> و به شکل مشابهی انتگرال های ویژه ای نظیر [[تابع خطا|انتگرال احتمال]] ، [[انتگرال فرینل|انتگرال فرنل]] ، تابع نمای  انتگرال، و برخی از انتگرال های دیگر <ref>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).</ref> برای مقدار های جبری استدلال با حد بالای پیچیدگی که به حد بهینه نزدیک است شامل میشوند، پس داریم :

: <math>
s_{f}(n)=
O(M(n)\log^2 n). \,
</math>

الان،  تنها هزینه ایجاد میکند به محاسبه فوری مقدار های توابع از گروهی از توابع برتر بالاتر، <ref>E. Bach, The complexity of number-theoretic constants. Info. Proc. Letters, No. 62 (1997).</ref> برخی انتگرال خاص از فیزیک و ریاضی از جمله ثابت کلاسیک به عنوان ثابت اویلرو ثابت کاتالان است <ref>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).</ref> و ثابت Apery کوتاه است. امکان موازی سازی الگوریتم ها بر اساس FEE است مزیت اضافی روش FEE .

== FEE-محاسبه ثابت های کلاسیک ==
می توان از فرمول اویلر به صورت زیر برای سنجش فوری  و سریع  ثابت <math>\pi,</math>  استفاده نمود <math>\frac{\pi}{4} = \arctan \frac12 + \arctan \frac13,</math> و مطابق بخش پایین میتوان از FEE برای محاسبه محموع جملات تیلور استفاده کرد.

: <math>
\arctan \frac12 = \frac{1}{1\cdot 2} - \frac{1}{3\cdot 2^3}+ \cdots +
\frac{(-1)^{r-1}}{(2r-1)2^{2r-1}} + R_1 ,
</math>

: <math>
\arctan \frac13 = \frac{1}{1\cdot 3} - \frac{1}{3\cdot 3^3}+ \cdots +
\frac{(-1)^{r-1}}{(2r-1)3^{2r-1}} + R_2 ,
</math>

: <math>|R_1| \leq \frac45\frac{1}{2r+1}\frac{1}{2^{2r+1}}; </math>

: <math>|R_2| \leq \frac{9}{10}\frac{1}{2r+1}\frac{1}{3^{2r+1}};</math>

و برای

: <math>r = n,\,</math>

: <math>4(|R_1|+|R_2|) \ < \ 2^{-n}.</math>

می توان از سایر تقریب ها برای حساب کردن <math>\pi</math> توسط FEE  نیز استفاده کرد <ref>D. H. Bailey, P. B. Borwein and S. Plouffe,
On the rapid computation of various polylogarithmic constants. Math.
Comp., Vol. 66 (1997).</ref> با این حال درتمام حالات برای پیچیدگی داریم :

: <math>s_\pi = O(M(n)\log^2 n). \,</math>

برای حساب کردن گامای ثابت اویلر با n رقم دقت، باید با دو سری FEE جمع شوند. پس داریم :

: <math>m=6n, \quad k = n, \quad k \geq 1, \, </math>

: <math>
\gamma = -
\log n \sum_{r=0}^{12n}
\frac{(-1)^rn^{r+1}}{(r+1)!} +
\sum_{r=0}^{12n}
\frac{(-1)^rn^{r+1}}{(r+1)!(r+1)} +
O(2^{-n}) .
</math>

: <math>s_\gamma = O(M(n)\log^2 n). \, </math>

برای بررسی فوری و سریع ثابت <math>\gamma</math> برای سایر تقریب ها امکان اعمال FEE  وجود دارد. <ref>R. P. Brent and E. M. McMillan,
Some new algorithms for high-precision computation of Euler's
constant. Math. Comp., Vol. 34 (1980).</ref>

== FEE-محاسبه سری های توان خاص ==
میتوان دو سری زیر را با استفاده از FEE سریع حساب کرد پس داریم :

: <math> f_1 =
f_1(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}z^j, </math>

: <math>f_2 = f_2(z) =
\sum_{j=0}^{\infty}\frac{a(j)}{b(j)}\frac{z^j}{j!}, </math>

فرض میکنیم  که <math>a(j), \quad b(j)</math> اعدادی صحیح هستند

: <math>|a(j)|+|b(j)| \leq (Cj)^K; \quad |z| \ < \ 1; \quad K</math>

و <math>C</math> ثابت هستند و <math>z</math> عددی جبری است و برای پیچیدگی ارزیابی آن داریم :

: <math>
s_{f_1}(n) = O\left(M(n)\log^2n \right), \,
</math>

: <math>
s_{f_2}(n)=
O\left(M(n)\log n \right).
</math>

== جزئیات FEE در مثال محاسبه سریع ثابت کلاسیک ''e'' ==
برای ارزیابی ثابت <math>e</math> گرفتن <math>m = 2^k, \quad k \geq
1</math> ، شرایط سری تیلور برای <math>e,</math>

: <math>
e = 1 + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{(m-1)!} + R_m.
</math>

ما در اینجا m را طوری انتخاب می کنیم که نیاز آن به باقی مانده <math>R_m</math> به طوریکه  نابرابری مقابل را داشته باشیم <math>R_m \leq 2^{-n-1}</math> برطرف می شود. برای مثال زمانی که <math>m\geq \frac{4n}{\log n}.</math> ، ما <math>m=2^k</math> را به طوری در نظر میگیریم  که عدد طبیعی <math>k</math> توسط نامساوی ها مشخص می گردد و داریم:

: <math>
2^k \geq \frac{4n}{\log n} > 2^{k-1}.
</math>

جمع را محاسبه می کنیم

: <math>
S = 1 + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{(m-1)!} =
\sum_{j=0}^{m-1}\frac{1}{(m-1-j)!} ,
</math>

و در k مرحله فرایند زیر داریم :

مرحله 1. ترکیب در <math>S</math> مجموع ها را به صورت دوتایی از داخل پرانتز عامل مشترک "بدیهی" را انجام می دهیم و حساب میکنیم پس داریم :

: <math>
\begin{align}
S & = \left(\frac{1}{(m-1)!} + \frac{1}{(m-2)!}\right) +
\left(\frac{1}{(m-3)!} + \frac{1}{(m-4)!}\right) + \cdots \\
& = \frac{1}{(m-1)!}(1+m-1) + \frac{1}{(m-3)!}(1+m-3) + \cdots .
\end{align}
</math>

ما مقداری های صحیح عبارت های داخل پرانتز را حساب میکنیم، یعنی داریم :

: <math>
m , m-2, m-4, \dots . \,
</math>

پس، در مرحله اول مجموع <math>S</math> در است

: <math>
S = S(1) = \sum_{j=0}^{m_1-1}\frac{1}{(m-1-2j)!}\alpha_{m_1-j}(1), </math>

: <math> m_1 = \frac m2, m = 2^k, k \geq 1 .</math>

در اولین قدم <math>\frac m2</math> اعداد صحیح فرم

: <math>
\alpha_{m_1-j}(1) = m-2j, \quad j = 0, 1, \dots, m_1 - 1 ,
</math>

حساب می گردند. بعد از آن به روشی مانند آن عمل می نماییم: در هر مرحله مجموع جمع را به صورت جفت و متوالی ترکیب می کنیم <math>S</math>، فاکتور مشترک «بدیهی» را از براکت ها خارج می نماییم و فقط مقدار های صحیح عبارات داخل پرانتز را محاسبه می کنیم. فرض کنید که اولی <math>i</math> مراحل این فرآیند تکمیل شده است.

: <math>
S = S(i+1) = \sum_{j=0}^{m_{i+1}-1}\frac{1}{(m-1-2^{i+1}j)!}
\alpha_{m_{i+1}-j}(i+1) ,</math>

: <math> m_{i+1} = \frac{m_i}{2} = \frac{m}{2^{i+1}} ,
</math>

: <math>
\alpha_{m_{i+1}-j}(i+1) = \alpha_{m_i-2j}(i) +
\alpha_{m_i-(2j+1)}(i)\frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!}
,</math>

: <math>j = 0, 1, \dots, \quad m_{i+1} - 1, \quad m = 2^k, \quad k \geq i+1 .</math>

: <math>\frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!}</math>

و غیره.

قسمت  آخر.  عددی صحیح را حساب می نماییم <math>\alpha_1(k),</math> ما با استفاده از الگوریتم فوری که پیش تر بررسی  شد، حساب می نماییم <math>(m-1)!,</math> و تقسیمی از عدد صحیح انجام دهید <math>\alpha_1(k)</math> توسط عدد صحیح <math>(m-1)!,</math> با دقت تا <math>n</math> ارقام نتیجه به دست آمده حاصل جمع است پیچیدگی همه محاسبات تا n رقم برابر <math>S,</math> است  یا ثابت <math>e</math>.

: <math>
O\left(M(m)\log^2 m\right) = O\left(M(n)\log n\right). \, 
</math>

== همچنین ببینید ==

* [[زمان اجرای الگوریتم|الگوریتم های سریع]]
* روش AGM
* [[تحلیل الگوریتم‌ها|پیچیدگی محاسباتی]]

== منابع ==
 

== مرجع : ==

* http://www.ccas.ru/personal/karatsuba/divcen.htm
* http://www.ccas.ru/personal/karatsuba/algen.htm
[[رده:الگوریتم‌های محاسباتی رایانه]]
[[رده:محاسبات عددی]]