Risch algorithm

In symbolic computation, the Risch algorithm is a method of indefinite integration used in some computer algebra systems to find antiderivatives. It is named after the American mathematician Robert Henry Risch, a specialist in computer algebra who developed it in 1968.

The algorithm transforms the problem of integration into a problem in algebra. It is based on the form of the function being integrated and on methods for integrating rational functions, radicals, logarithms, and exponential functions. Risch called it a decision procedure, because it is a method for deciding whether a function has an elementary function as an indefinite integral, and if it does, for determining that indefinite integral. However, the algorithm does not always succeed in identifying whether or not the antiderivative of a given function in fact can be expressed in terms of elementary functions. Specifically, the algorithm cannot solve the constant problem, which is undecidable when it needs to determine whether an arbitrary complex number expression is equal to zero.

The complete description of the Risch algorithm takes over 100 pages.^[1] The Risch–Norman algorithm is a simpler, faster, but less powerful variant that was developed in 1976 by Arthur Norman.

Some significant progress has been made in computing the logarithmic part of a mixed transcendental-algebraic integral by Brian L. Miller.^[2]

The Risch algorithm is used to integrate elementary functions. These are functions obtained by composing exponentials, logarithms, radicals, trigonometric functions, and the four arithmetic operations (+ − × ÷). Laplace solved this problem for the case of rational functions, as he showed that the indefinite integral of a rational function is the sum of a rational function and a finite number of constant multiples of logarithms of rational functions. The algorithm suggested by Laplace is usually described in calculus textbooks; as a computer program, it was finally implemented in the 1960s.

صاغ ليوفيل المسألة التي تُحل بواسطة خوارزمية ريش. وأثبت ليوفيل تحليليًا أنه إذا وُجد حل أولي g للمعادلة g ′ = f، فإنه توجد ثوابت αᵢ ودوال uᵢ _و v في الحقل المُوَلَّد بواسطة f بحيث يكون الحل على الصورة التالية _:

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

قام ريش بتطوير طريقة تسمح للمرء بالنظر فقط في مجموعة محدودة من الدوال ذات شكل ليوفيل.

يستمد خوارزمية ريش فكرتها من سلوك الدالتين الأسية واللوغاريتمية عند التفاضل. بالنسبة للدالة f = e^ ^g ، حيث f و g دالتان قابلتان للتفاضل ، لدينا

${\displaystyle \left(f\cdot e^{g}\right)^{\prime }=\left(f^{\prime }+f\cdot g^{\prime }\right)\cdot e^{g},\,}$

لذا، إذا كان e ^g ناتجًا عن تكامل غير محدد، فمن المتوقع أن يكون داخل التكامل. أيضًا، بما

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

ثم إذا كان (ln g ) ⁿ هو نتيجة التكامل، فإنه لا ينبغي توقع سوى عدد قليل من قوى اللوغاريتم.

يُعدّ إيجاد الدالة الأصلية الأولية أمرًا بالغ الحساسية للتفاصيل. على سبيل المثال، الدالة الجبرية التالية (التي نشرها هنري كوهين على مجموعة sci.math.symbolic عام 1993 ^{[ 3 ]} ) لها دالة أصلية أولية، كما يُظهر برنامج Wolfram Mathematica منذ الإصدار 13 (مع ذلك، لا يستخدم Mathematica خوارزمية ريش لحساب هذا التكامل): ^{[ 4 ] [ 5 ]}

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

أي:

${\displaystyle {\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}}}$

لكن إذا تم تغيير الحد الثابت 71 إلى 72، فإنه لا يمكن تمثيل الدالة الأصلية بدلالة الدوال الأولية، ^{[ 6 ]} كما يوضح برنامج FriCAS أيضًا. قد تُعيد بعض أنظمة الجبر الحاسوبي هنا دالة أصلية بدلالة دوال غير أولية (أي التكاملات الإهليلجية )، والتي تقع خارج نطاق خوارزمية ريش. على سبيل المثال، يُعيد برنامج Mathematica نتيجةً باستخدام الدالتين EllipticPi و EllipticF. التكاملات على الصورة${\displaystyle \int {\frac {x+A}{\sqrt {x^{4}+ax^{3}+bx^{2}+cx+d}}}\,dx}$تم حلها بواسطة تشيبيشيف (وفي أي الحالات يكون الأمر بديهيًا)، ^{[ 7 ]} ولكن البرهان الدقيق لها تم في النهاية بواسطة زولوتاريف . ^{[ 6 ]}

فيما يلي مثال أكثر تعقيدًا يتضمن كلاً من الدوال الجبرية والمتسامية : ^{[ 8 ]}

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

في الواقع، الدالة الأصلية لهذه الدالة لها شكل قصير نسبيًا يمكن إيجاده باستخدام التعويض. ${\displaystyle u=x+{\sqrt {x+\ln x}}}$( يستطيع SymPy حلها بينما يفشل FriCAS مع ظهور خطأ "التنفيذ غير مكتمل (بقايا ثابتة)" في خوارزمية ريش):

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

لا تزال بعض "نظريات" دافنبورت قيد التوضيح. فعلى سبيل المثال، في عام 2020 تم العثور على مثال مضاد لإحدى هذه "النظريات"، حيث تبين أن هناك دالة أصلية ابتدائية موجودة بالفعل. ^{[ 9 ]}

كان تحويل خوارزمية ريش النظرية إلى خوارزمية يمكن تنفيذها بفعالية بواسطة جهاز كمبيوتر مهمة معقدة استغرقت وقتاً طويلاً.

تُعدّ حالة الدوال المتسامية البحتة (التي لا تتضمن جذور كثيرات الحدود) سهلة نسبيًا، وقد تمّ تطبيقها مبكرًا في معظم أنظمة الجبر الحاسوبي . وقد قام جويل موسى بأول تطبيق لها في برنامج ماكسيما بعد فترة وجيزة من نشر ورقة ريش البحثية. ^{[ 10 ]}

تم حل مشكلة الدوال الجبرية البحتة جزئيًا وتطبيقها في برنامج Reduce بواسطة جيمس إتش. دافنبورت - ولتبسيط الأمر، كان البرنامج يتعامل فقط مع الجذور التربيعية والجذور التربيعية المتكررة، وليس مع الجذور العامة أو العلاقات الجبرية غير التربيعية الأخرى بين المتغيرات. ^{[ 11 ]}

تم حل الحالة العامة وتطبيقها بشكل شبه كامل في سكراتش باد، وهو برنامج سابق لأكسيوم ، من تطوير مانويل برونشتاين. يوجد أيضًا نسخة معدلة من أكسيوم تُسمى فريكاس، مع تطوير نشط لخوارزمية ريش وغيرها من الخوارزميات على جيت هاب. ^{[ 12 ] [ 13 ]} مع ذلك، لم يشمل التطبيق بعض الفروع الخاصة بالحالات الخاصة بشكل كامل. ^{[ 14 ] [ 15 ]} اعتبارًا من عام 2025^{[ 16 ]} لا يوجد تطبيق كامل لخوارزمية ريش.

إن خوارزمية ريش، عند تطبيقها على الدوال الأولية العامة، ليست خوارزمية بالمعنى الدقيق، بل هي شبه خوارزمية، لأنها تتطلب، كجزء من عملها، التحقق مما إذا كانت بعض التعبيرات مكافئة للصفر ( مشكلة الثوابت )، وخاصة في حقل الثوابت. بالنسبة للتعبيرات التي تتضمن دوالًا تُعتبر عادةً أولية ، فإنه من غير المعروف ما إذا كانت هناك خوارزمية تُجري هذا التحقق ( تستخدم أنظمة الجبر الحاسوبي الحالية أساليب استدلالية)؛ علاوة على ذلك، إذا أضفنا دالة القيمة المطلقة إلى قائمة الدوال الأولية، فمن المعروف أنه لا توجد خوارزمية كهذه؛ انظر نظرية ريتشاردسون .

تظهر هذه المشكلة أيضًا في خوارزمية قسمة كثيرات الحدود ؛ إذ تفشل هذه الخوارزمية إذا لم تتمكن من تحديد ما إذا كانت المعاملات تتلاشى بشكل متطابق. ^{[ 17 ]} تستخدم جميع الخوارزميات غير التافهة المتعلقة بكثيرات الحدود تقريبًا خوارزمية قسمة كثيرات الحدود، بما في ذلك خوارزمية ريش. إذا كان حقل الثوابت قابلاً للحساب ، أي للعناصر غير المعتمدة على x ، فإن مشكلة التكافؤ الصفري قابلة للحل، وبالتالي فإن خوارزمية ريش تُعد خوارزمية كاملة. من أمثلة حقول الثوابت القابلة للحساب ℚ وℚ ( y ) ، أي الأعداد النسبية والدوال النسبية في y بمعاملات أعداد نسبية، على التوالي، حيث y متغير غير محدد لا يعتمد على x .

تُعدّ هذه مشكلةً أيضاً في خوارزمية حذف المصفوفة باستخدام طريقة غاوس (أو أي خوارزمية أخرى قادرة على حساب الفضاء الصفري للمصفوفة)، وهو أمرٌ ضروريٌّ أيضاً للعديد من أجزاء خوارزمية ريش. إذ تُنتج طريقة غاوس نتائج غير صحيحة إذا لم تتمكن من تحديد ما إذا كان العنصر المحوري يساوي صفراً تماماً.

• أكسيوم (نظام الجبر الحاسوبي)
• تعبير مغلق الشكل
• دالة غاما غير مكتملة
• قوائم التكاملات
• نظرية ليوفيل (الجبر التفاضلي)
• التكامل غير الأولي
• التكامل الرمزي

• برونشتاين، مانويل (1990). "تكامل الدوال الأولية". مجلة الحساب الرمزي . 9 (2): 117-173 . doi : 10.1016/s0747-7171(08)80027-2 .

• برونشتاين، مانويل (1998). "دليل التكامل الرمزي" (ملف PDF) . مؤتمر ISSAC'98، روستوك (أغسطس 1998) وورشة عمل الجبر التفاضلي، روتجرز .

• برونشتاين، مانويل (2005). التكامل الرمزي 1. سبرينغر. ISBN 3-540-21493-3.

• دافنبورت، جيمس هـ. (1981). حول تكامل الدوال الجبرية . سلسلة محاضرات في علوم الحاسوب . المجلد  102. سبرينغر. ISBN 978-3-540-10290-8.

• جيديس، كيث أو .؛ ​​تشابور، ستيفن ر.؛ لاباهن، جورج (1992). خوارزميات الجبر الحاسوبي . بوسطن، ماساتشوستس: دار نشر كلوير الأكاديمية. الصفحات:  585 صفحة + 22 صفحة تمهيدية. رمز Bibcode : 1992afca.book.....G . doi : 10.1007/b102438 . ISBN 0-7923-9259-0.

• موسى، جويل (2012). "ماكسيما: تاريخ شخصي". مجلة الحوسبة الرمزية . 47 (2): 123-130 . doi : 10.1016/j.jsc.2010.08.018 .

• ريش، ر. هـ. (1969). "مسألة التكامل في الحدود المحدودة" . معاملات الجمعية الرياضية الأمريكية . 139. الجمعية الرياضية الأمريكية: 167-189 . doi : 10.2307/1995313 . JSTOR 1995313 . 

• ريش، ر. هـ. (1970). "حل مسألة التكامل في حدود منتهية" . نشرة الجمعية الرياضية الأمريكية . 76 (3): 605-608 . doi : 10.1090/S0002-9904-1970-12454-5 .

• روزنليخت، ماكسويل (1972). "التكامل في الحدود المحدودة". المجلة الرياضية الأمريكية الشهرية . 79 (9). الجمعية الرياضية الأمريكية: 963-972 . doi : 10.2307/2318066 . JSTOR 2318066 . 

• بهات، بوفانيش. "خوارزمية ريش" . عالم الرياضيات .