ریاضیات علوم پایه

الگوریتم ریش

توسط 14p.ir

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

توصیف

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

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

 g = v + \sum_{i<n} \alpha_i \,\ln (u_i)

می باشد.

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

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

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

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

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

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

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

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

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

یعنی

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

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

 x^4 + 10 x^2 - 96 x - 71 \,

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

 x^4 + 10 x^2 - 96 x - 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) قابل تصمیم گیری است.

(Visited 130 times, 1 visits today)
  
کانال گردشگری

درباره نویسنده

14p.ir

Leave a Comment