Apakah ada implementasi lengkap dari algoritma Risch?

Oct 15 2020

Apakah ada implementasi yang umum tersedia (komersial atau tidak) lengkap dari algoritma Risch untuk menentukan apakah fungsi elementer memiliki antiturunan elementer?

The artikel Wikipedia pada integrasi simbolis klaim bahwa kasus umum dari algoritma Risch diselesaikan dan dilaksanakan di Axiom oleh Manuel Bronstein, dan jawaban atas pertanyaan MO lain mengatakan hal yang sama. Namun, saya ragu, berdasarkan komentar berikut oleh Manuel Bronstein sendiri di newsgroup USENET sci.math.symbolicpada tanggal 5 September 2003:

Jika Aksioma mengembalikan integral yang tidak dievaluasi, maka itu telah membuktikan bahwa tidak ada antiturunan dasar. Namun ada beberapa kasus di mana Aksioma dapat mengembalikan pesan kesalahan yang mengatakan bahwa Anda telah mencapai cabang algoritma yang tidak diimplementasikan, dalam hal ini tidak dapat disimpulkan. Jadi Richard benar saat menunjukkan bahwa algoritme Risch juga tidak diterapkan sepenuhnya di sana. Aksioma unik dalam membuat perbedaan antara cabang yang tidak diimplementasikan dan bukti non-integrabilitas, dan juga dalam benar-benar membuktikan kemandirian aljabar dari blok-blok penyusun dari integrand sebelum menyimpulkan nonintegrabilitas (orang lain biasanya menganggap kemerdekaan ini setelah melakukan beberapa pemeriksaan ketergantungan heuristik).

Bronstein sayangnya meninggal pada 6 Juni 2005 . Mungkin saja dia menyelesaikan implementasinya sebelum dia meninggal, tetapi saya belum bisa memastikannya. Saya tahu bahwa Bronstein tidak pernah berhasil menyelesaikan buku yang dimaksudkannya tentang integrasi fungsi aljabar. [ EDIT: Sebagai pemeriksaan lebih lanjut, saya mengirim email ke Barry Trager. Dia menegaskan bahwa implementasi yang dia dan Bronstein kerjakan tidak lengkap. Dia tidak tahu banyak tentang implementasi lain, tetapi tidak mengetahui implementasi lengkap apa pun.]

Saya memiliki akses ke Maple 2018, dan tampaknya implementasi tersebut juga tidak lengkap. Kasus uji yang berguna adalah integral berikut, diambil dari makalah (yang tampaknya tidak dipublikasikan) Algoritme Trager untuk integrasi fungsi aljabar yang ditinjau kembali oleh Daniel Schultz:$$\int \frac{29x^2+18x-3}{\sqrt{x^6+4x^5+6x^4-12x^3+33x^2-16x}}\,dx$$ Schultz secara eksplisit memberikan antiturunan dasar dalam makalahnya, tetapi Maple 2018 mengembalikan integral yang tidak dievaluasi.

Jawaban

20 SamBlake Oct 15 2020 at 08:43

Tidak ada sistem aljabar komputer yang menerapkan proses keputusan lengkap untuk integrasi fungsi transendental dan aljabar campuran.

Integral dari makalah Schultz yang sangat baik dapat diselesaikan oleh Maple jika Anda mengonversi notasi integrand ke RootOf (Mengapa ini tidak dilakukan secara internal di Maple adalah pertanyaan yang menarik?)

int(convert((29*x^2+18*x-3)/(x^6+4*x^5+6*x^4-12*x^3+33*x^2-16*x)^(1/2),RootOf),x);

Percobaan saya menyarankan Maple memiliki implementasi terbaik dari algoritma Risch-Trager-Bronstein untuk integrasi integral aljabar murni dalam hal fungsi dasar (ref: tabel 1, bagian 3 dari Sam Blake, Metode Sederhana untuk Menghitung Beberapa Integral Pseudo-Elliptic dalam Ketentuan Fungsi Dasar , arXiv: 2004.04910 ). Namun, implementasi Maple tidak mengintegrasikan ekspresi yang berisi parameter atau radikal bersarang (keduanya memiliki dukungan di AXIOM dan FriCAS).

Tampaknya beberapa kemajuan signifikan telah dibuat dalam menghitung bagian logaritmik dari integral aljabar-transendental campuran oleh Miller [1]. Padahal, sejauh yang saya tahu, tidak ada sistem aljabar komputer yang menerapkan algoritmanya. Juga tidak jelas apakah algoritma Miller dapat menangani parameter, misalnya, algoritma Risch-Trager-Bronstein mengalami kesulitan dengan integral pseudo-eliptik berikut

$$\int\frac{\left(p x^2-q\right) \left(p x^2-x+q\right)dx}{x \left(p x^2+2 x+q\right) \sqrt{2 p^2x^4+2 p x^3+(4 p q+1) x^2+2 q x+2 q^2}} = - \frac{1}{\sqrt{2}}\log (x) + \frac{1}{\sqrt{2}}\log \left(\sqrt{2} y +2 p x^2+x+2q\right) - \frac{3}{\sqrt{5}}\tanh ^{-1}\left(\frac{\sqrt{5} y}{3 p x^2+3 q+x}\right),$$ dimana $y=\sqrt{2 p^2 x^4+2 p x^3+(4 pq+1)x^2+2 q x+2 q^2}$. Heuristik saya dalam makalah yang ditautkan sebelumnya menghitung integral ini dengan cepat dengan substitusi$u=\frac{px^2+q}{p x}$.

Berkenaan dengan kasus campuran aljabar-transendental dari algoritma Risch-Trager-Bronstein, sebuah integral yang tidak dapat diselesaikan dengan Maple, Mathematica, AXIOM atau FriCAS (dan mungkin CAS lainnya) adalah

$$\int \frac{\left(\sqrt{x}+1\right) \left(e^{2x \sqrt{x}} -a\right) \sqrt{a^2+2 a x e^{2 \sqrt{x}} +cx e^{2 \sqrt{x}} +x^2 e^{4 \sqrt{x}}}}{x \sqrt{x}e^{\sqrt{x}} \left(a+x e^{2 \sqrt{x}} \right)} dx.$$

Integral ini menarik karena menampilkan dua pesan berbeda dari AXIOM dan FriCAS yang menunjukkan penerapannya masing-masing tidak lengkap. FriCAS kembali

(1) -> integrate(((-a+exp(2*x^(1/2))*x)*x^(-3/2)*(1+x^(1/2))*(a^2+2*a*exp(2*x^(1/2))*x+c*exp(2*x^(1/2))*x+exp(4*x^(1/2))*x^2)^(1/2))/(exp(x^(1/2))*(a+exp(2*x^(1/2))*x)),x)
                                                                                                        
   >> Error detected within library code:                                                               
   integrate: implementation incomplete (has polynomial part)

Sementara AXIOM kembali

(1) -> integrate(((-a+exp(2*x^(1/2))*x)*x^(-3/2)*(1+x^(1/2))*(a^2+2*a*exp(2*x^(1/2))*x+c*exp(2*x^(1/2))*x+exp(4*x^(1/2))*x^2)^(1/2))/(exp(x^(1/2))*(a+exp(2*x^(1/2))*x)),x)
                                                                                                        
   >> Error detected within library code:
   integrate: implementation incomplete (constant residues)

[1] Miller, B. (2012). “ Tentang Integrasi Fungsi Dasar: Menghitung Bagian Logaritmik ”. Tesis (Ph.D.) Texas Tech University, Dept. Matematika dan Statistik.