الگوریتم ریش

الگوریتم Risch، به افتخار رابرت ایچ Risch به این نام نامیده شد که برای حساب دیفرانسیل و انتگرال جبر می‌باشد. این الگوریتم مسئله انتگرال را درون یک مسئله جبری تغییر شکل می‌دهد. آن مبنایی بر مشکل عملی می‌باشد که انتگرال گیری شده و مطابق بر روشهایی برای عملکرد منطقی انتگرال گیری، رادیکال، لگاریتم و تابع تشریعی می‌باشد. رِیش الگوریتم را در سال ۱۹۶۸ ساخت و آن را فرایند تصمیم‌گیری نامید. چرا که متدی است برای تصمیمِ اینکه آیا یک تابع، تابعِ اولیه‌ای دارد که انتگرالِ نامعین داشته باشد و همچنین اگر دارد، تعیینش می‌کند. الگوریتم Risch در الگوریتمی برای جبر کامپیوتری توسط Keith O.Geddes مختصراً توضیح داده شده‌است. همچنین توسط Gedde , Stephen R. Czapor و George Labah مختصراً توضیح داده شده‌است. الگوریتم Risch-Normal در سال ۱۹۷۶ تولید شد که سریعتر اما از نظرِ فنی ضعیف تر است.

توصیف

الگوریتم Risch برای تابع اولیه انتگرال استفاده شده‌است. این‌ها توابعی هستند که شامل ترکیب تابع‌های نمایی، لگاریتم‌ها، رادیکال‌ها، مثلثات و چهار عمل اصلی علم حساب (ضرب و جمع و تفریق و تقسیم) می‌باشند. لاپلاس این مسئله را برای وضعیت تابع منطقی حل کرد همانطوری که او نشان داد انتگرال نامعینِ یک تابع منطقی، تابعیست منطقی و یک عدد محدود از ضربِ تعداد محدودی از ضرب‌های ثابت لگاریتم تابع منطقی است. الگوریتمِ پیشنهاد شده توسطِ لاپلاس معمولاً در متون کتاب حساب دیفرانسیل شرح داده شده‌است و سرانجام در دهه ۱۹۶۰ به عنوانِ یک برنامه کامپیوتری پیاده‌سازی شد.

Liouville مسئله حل شده توسط الگوریتم Rischرا به صورت فرمول درآورد. Liouville به روش تحلیلی اثبات کرد که اگر یک راه حل ابتدایی یا اولیه که اسمش g باشد وجود داشته باشد، برای معادله g ′ = f آنگاه برای ثابت α_i و تابع اصلی u_i و v پاسخ به شکل زیر

$g=v+\sum _{i<n}\alpha _{i}\,\ln(u_{i})$

می‌باشد.

Risch روشی ساخت که اجازه می‌داد شخص فقط نگرانِ مجموعه‌ای محدود از توابع اولیه به صورتِ فرمولِ لیوویل باشد.

فراستِ الگوریتم رِیش، از رفتارِ توابع نمایی و لگاریتمی در مشتق گیری می‌آید. برای تابع f e^g که f و g توابع متغیری هستند که ما داریم

$(f\cdot e^{g})'=(f^{\prime }+f\cdot g^{\prime })\cdot e^{g},\,$

لذا اگر e^g در نتیجه انتگرال نامعین بود، باید انتظار داشت که داخلِ انتگرال نیز باشد همانگونه که:

$(f\cdot \ln ^{n}g)'=f^{\prime }\ln ^{n}{g}+nf{\frac {g^{\prime }}{g}}\ln ^{n-1}{g}$

سپس اگر lnⁿg در نتیجه انتگرال باشد آنوقت فقط توان‌های کمی از لگاریتم می‌توان انتظار داشت..

مثال‌های مسئله

یافتن ضد مشتق اولیه برای جزئیاتی خیلی حساس است. به عنوان مثال تابع زیر یک ضد مشتق اولیه دارد:

$f(x)={\frac {x}{\sqrt {x^{4}+10x^{2}-96x-71}}},$

یعنی

${\begin{aligned}F(x)=-{\frac {1}{8}}\ln &\,{\Big (}(x^{6}+15x^{4}-80x^{3}+27x^{2}-528x+781){\sqrt {x^{4}+10x^{2}-96x-71}}{\Big .}\\&-{\Big .}(x^{8}+20x^{6}-128x^{5}+54x^{4}-1408x^{3}+3124x^{2}+10001){\Big )}+C.\end{aligned}}$

برخی از سیستم‌های جبریِ کامپیوتری ممکن است در اینجا یک ضد مشتق بر حسب تابع غیرِ اصلی برگردانند (مثل انتگرال‌های بیضی) هرچند خارج از حوزه الگوریتم رِیش هستند. اما اگر ۷۱ به ۷۲ تغییر کند نمایش دادنِ ضد مشتق با استفاده از تابع اولیه، ممکن نیست! دلیلش این است که گروه Galois از

$x^{4}+10x^{2}-96x-71\,$

(D(۴ می‌باشد. مثلاً توسط جایگشت‌های (۱و۲و۳و۴) و (۳و۱) تولید شده و هشت عنصر را شامل می‌شود (درx^۴ − ۲ یکسان است) در حالی که گروه Galois از

$x^{4}+10x^{2}-96x-72\,$

(S(۴ می‌شود، مثلاً توسط جایگشت‌های (۲ ۱) و (۳ ۱) و (۴ ۱) تولید شده و شامل ۲۴ عنصر می‌باشد. تابع زیر یک مثال پیچیده تری است:

$f(x)={\frac {x^{2}+2x+1+(3x+1){\sqrt {x+\ln x}}}{x\,{\sqrt {x+\ln x}}(x+{\sqrt {x+\ln x}})}}$

در واقع، ضد مشتق این تابع یک شکل نسبتاً کوتاهی دارد:

$F(x)=2({\sqrt {x+\ln x}}+\ln(x+{\sqrt {x+\ln x}}))+C.$

پیاده‌سازی

تبدیلِ فرایندِ تصمیمِ رِیش به یک الگوریتم که بتواند توسط کامپیوتر اجرا شود وظیفهٔ پیچیده‌ای است که نیازمند مطالعات ابتکاری و پالایشِ زیاد می‌باشد. هیچ نرم‌افزاری (تا فوریه ۲۰۱۱) شناخته نشد که بتواند الگوریتمِ رِیش را به طورِ کامل پیاده‌سازی کند، اگرچه چندین سیستم جبری کامپیوتری جزئی از آن را پیاده‌سازی کرده‌اند.

تصمیم پذیری

الگوریتمِ رِیش اعمال شده به توابع اولیه عمومی یک الگوریتم نیست! بلکه یک نیمه الگوریتماست. چراکه به عنوانِ بخشی از عملیاتِ خودش نیاز به بررسی دارد که آیا عباراتِ خاصی، برابر با صفر می‌شوند! (مسئله پایدار)، به خصوص در زمینه پایدار. برای عباراتی که فقط درگیرِ توابعی اند که معمولاً برای این گرفته شده‌اند که اولیه باشند، شناخته شده نیست، خواه الگوریتم بررسی را انجام دهد یا خیر (سیستم‌های جبری کامپیوتری فعلی از روش‌های ابتکاری استفاده می‌کنند)؛ علاوه بر اون اگر کسی یک Absolute Value Function به لیستِ توابع اولیه بیفزاید، اینطور برداشت می‌شود که همچین الگوریتمی وجود ندارد! الگوریتم ریچاردسون را ببینید.

توجه کنید که این مسئله همچنین در الگوریتم تقسیم چندجمله‌ای polynomial نیز وجود دارد؛ این الگوریتم با شکست مواجه خواهد شد اگر نتواند به درستی تعیین کند که آیا عواملِ مشترک عیناً به صفر می‌رسد. بنابراین، الگوریتم Risch نیاز زیادی دارد که قسمتِ ثابت قابل محاسبه باشد. مثلاً؛ برای عناصری که به X بستگی نداشته باشند، مسئله معادله صفر (zero-equivalence) قابل تصمیم‌گیری است.

جستارهای وابسته

• لیست انتگرال‌ها
• قضیه Liouville (جبر متفاوت)
• انتگرال نمادی
• اصل کلی
• تابع گاما ناکامل

منابع

• R. H. Risch (1969). "The problem of integration in finite terms". Transactions of the American Mathematical Society. American Mathematical Society. 139: 167–189. doi:10.2307/1995313. JSTOR 1995313.. http://www.ams.org/bull/1970-76-03/S0002-9904-1970-12455-7/S0002-9904-1970-12455-7.pdf
• R. H. Risch (1970). "The solution of the problem of integration in finite terms". Bulletin of the American Mathematical Society. 76 (3): 605–608. doi:10.1090/S0002-9904-1970-12454-5. AMS page PDF document
• Maxwell Rosenlicht (1972). "Integration in finite terms". American Mathematical Monthly. Mathematical Association of America. 79 (9): 963–972. doi:10.2307/2318066. JSTOR 2318066.
• Geddes, Czapor, Labahn (1992). Algorithms for Computer Algebra. Kluwer Academic Publishers. ISBN 0-7923-9259-0.{{cite book}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
• Manuel Bronstein (2005). Symbolic Integration I. Springer. ISBN 3-540-21493-3.
• Manuel Bronstein (1998). "Symbolic Integration Tutorial" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
• Bhatt, Bhuvanesh. "Risch Algorithm". MathWorld.