Algorytm Rischa

W obliczeniach symbolicznych algorytm Rischa jest metodą całkowania na czas nieokreślony, używaną w niektórych systemach algebry komputerowej do znajdowania funkcji pierwotnych . Został nazwany na cześć amerykańskiego matematyka Roberta Henry'ego Rischa , specjalisty od algebry komputerowej, który opracował go w 1968 roku.

Algorytm przekształca problem całkowania w problem algebry . Opiera się na postaci całkowanej funkcji oraz metodach całkowania funkcji wymiernych , pierwiastków , logarytmów i funkcji wykładniczych . Risch nazwał to procedurą decyzyjną , ponieważ jest to metoda rozstrzygania, czy dana funkcja ma funkcję elementarną jako całki nieoznaczonej, a jeśli tak, to do wyznaczenia tej całki nieoznaczonej. Jednak algorytmowi nie zawsze udaje się określić, czy funkcja pierwotna danej funkcji w rzeczywistości może być wyrażona za pomocą funkcji elementarnych.

Pełny opis algorytmu Rischa zajmuje ponad 100 stron. Algorytm Rischa -Normana to prostszy, szybszy, ale mniej wydajny wariant, który został opracowany w 1976 roku przez Arthura Normana .

Poczyniono znaczne postępy w obliczaniu części logarytmicznej mieszanej całki transcendentalno-algebraicznej przez Briana L. Millera.

Opis

Algorytm Rischa służy do całkowania funkcji elementarnych . Są to funkcje uzyskane przez złożenie wykładników, logarytmów, pierwiastków, funkcji trygonometrycznych i czterech operacji arytmetycznych ( + − × ÷ ). Laplace rozwiązał ten problem dla funkcji wymiernych , pokazując, że całka nieoznaczona funkcji wymiernej jest funkcją wymierną i skończoną liczbą stałych wielokrotności logarytmów funkcji wymiernych . Algorytm zaproponowany przez Laplace'a jest zwykle opisywany w podręcznikach do rachunku różniczkowego; jako program komputerowy został ostatecznie wdrożony w latach 60. XX wieku.

Liouville sformułował problem, który rozwiązuje algorytm Rischa. Liouville udowodnił metodami analitycznymi, że jeśli istnieje elementarne rozwiązanie g równania g ′ = f , to istnieją stałe α _i oraz funkcje u _i i v w polu generowanym przez f takie, że rozwiązanie ma postać

${\ Displaystyle g = v + \ suma _ {i <n} \ alfa _ {i} \ ln (u_ {i})}$

Risch opracował metodę, która pozwala rozważać tylko skończony zbiór funkcji postaci Liouville'a.

Intuicja dla algorytmu Rischa wynika z zachowania funkcji wykładniczej i logarytmicznej podczas różniczkowania. Dla funkcji f np ^g , gdzie f i g są funkcjami różniczkowalnymi , mamy

${\ Displaystyle \ lewo (f \ cdot e ^ {g} \ prawej) ^ {\ pierwsza} = \ lewo (f ^ { \prime }+f\cdot g^{\prime }\right)\cdot e^{g},\,}$

więc gdyby np. ^g było wynikiem całkowania nieoznaczonego, należy oczekiwać, że znajdzie się wewnątrz całki. Również jak

${\ Displaystyle \ lewo (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}}$

to gdyby (ln g ) ⁿ było wynikiem całkowania, to należałoby się spodziewać tylko kilku potęg logarytmu.

Przykłady problemów

Znalezienie elementarnej funkcji pierwotnej jest bardzo wrażliwe na szczegóły. Na przykład następująca funkcja algebraiczna (opublikowana w sci.math.symbolic przez Henri Cohena w 1993 r.) ma elementarną funkcję pierwotną, jak pokazuje Wolfram Mathematica od wersji 13 (jednak Mathematica nie używa algorytmu Trager-Risch do obliczenia tej całki ):

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

mianowicie:

${\ Displaystyle {\ rozpocząć {wyrównane} F (x) = - {\ Frac {1} {8}} \ ln & \, {\ Duży (} (x ^ {6} + 15x ^ {4} -80x ^ {3}+27x^{2}-528x+781){\sqrt {x^{4}+10x^{2}-96x-71}}{\Duży .}\\&{}-{\Duży . }(x^{8}+20x^{6}-128x^{5}+54x^{4}-1408x^{3}+3124x^{2}+10001){\Duży )}+C.\end {wyrównany}}}$

Ale jeśli stały składnik 71 zostanie zmieniony na 72, nie jest możliwe przedstawienie funkcji pierwotnej w kategoriach funkcji elementarnych, jak pokazuje również FriCAS . Niektóre systemy algebry komputerowej mogą tutaj zwracać funkcję pierwotną w kategoriach funkcji nieelementarnych (tj. całek eliptycznych ), które są poza zakresem algorytmu Rischa. Całkę tę rozwiązał Czebyszew (a w jakich przypadkach jest ona elementarna), ale ścisłego dowodu na to ostatecznie dokonał Zołotariew .

Poniżej znajduje się bardziej złożony przykład, który obejmuje zarówno funkcje algebraiczne, jak i przestępne:

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

W rzeczywistości funkcja pierwotna tej funkcji ma dość krótką postać, którą można znaleźć za pomocą podstawienia ( SymPy może to rozwiązać $\ ln x}}}$ + podczas gdy FriCAS kończy się niepowodzeniem z powodu błędu „implementacja niekompletna (stałe pozostałości)” w algorytmie Rischa):

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

Niektóre „twierdzenia” Davenporta są wciąż wyjaśniane. Na przykład w 2020 roku znaleziono kontrprzykład do takiego „twierdzenia”, gdzie okazuje się, że elementarna funkcja pierwotna jednak istnieje.

Realizacja

Przekształcenie teoretycznego algorytmu Rischa w algorytm, który może być skutecznie wykonywany przez komputer, było złożonym zadaniem, które zajęło dużo czasu.

Przypadek funkcji czysto transcendentalnych (które nie obejmują pierwiastków wielomianów) jest stosunkowo łatwy i został wcześnie zaimplementowany w większości systemów algebry komputerowej . Pierwszą implementację wykonał Joel Moses w Macsyma wkrótce po opublikowaniu artykułu Rischa.

Przypadek funkcji czysto algebraicznych został rozwiązany i zaimplementowany w Reduce przez Jamesa H. Davenporta , chociaż dla uproszczenia mógł dotyczyć tylko pierwiastków kwadratowych i powtarzanych pierwiastków kwadratowych, a nie ogólnych pierwiastków lub innych niekwadratowych relacji algebraicznych między zmiennymi.

Ogólny przypadek został rozwiązany i prawie w pełni zaimplementowany w Scratchpadzie, prekursorze Axiomu , przez Manuela Bronsteina, i jest obecnie rozwijany w rozwidleniu Axioma, FriCAS. Wdrożenie nie obejmowało jednak w całości niektórych oddziałów dla przypadków szczególnych. Obecnie nie jest znana pełna implementacja algorytmu Rischa.

rozstrzygalność

Algorytm Rischa zastosowany do ogólnych funkcji elementarnych nie jest algorytmem, ale półalgorytmem , ponieważ w ramach swojego działania musi sprawdzać, czy określone wyrażenia są równoważne zeru ( problem ze stałą ), w szczególności w polu stałym. W przypadku wyrażeń, które obejmują tylko funkcje powszechnie uważane za elementarne , nie wiadomo, czy istnieje algorytm przeprowadzający taką kontrolę (obecne systemy algebry komputerowej wykorzystują heurystykę); ponadto, jeśli dodać funkcję wartości bezwzględnej do listy funkcji elementarnych wiadomo, że taki algorytm nie istnieje; zobacz twierdzenie Richardsona .

Należy zauważyć, że problem ten pojawia się również w algorytmie dzielenia wielomianowego ; ten algorytm zawiedzie, jeśli nie będzie w stanie poprawnie określić, czy współczynniki znikają identycznie. Praktycznie każdy nietrywialny algorytm dotyczący wielomianów wykorzystuje algorytm dzielenia wielomianów, w tym algorytm Rischa. Jeśli pole stałe jest obliczalne , tj. dla elementów nie zależnych od x problem zerowej równoważności jest rozstrzygalny, to algorytm Rischa jest algorytmem kompletnym. Przykładami obliczalnych pól stałych są Q i Q ( y ) , tj. odpowiednio liczby wymierne i funkcje wymierne w y ze współczynnikami liczb wymiernych, gdzie y jest liczbą nieokreśloną, która nie zależy od x .

Jest to również problem w algorytmie macierzy eliminacji Gaussa (lub dowolnym algorytmie, który może obliczyć przestrzeń zerową macierzy), który jest również niezbędny dla wielu części algorytmu Rischa. Eliminacja Gaussa da nieprawidłowe wyniki, jeśli nie będzie w stanie poprawnie określić, czy oś obrotu jest identyczna zerem .

Zobacz też

• Aksjomat (system algebry komputerowej)
• Wyrażenie w formie zamkniętej
• Niekompletna funkcja gamma
• Listy całek
• Twierdzenie Liouville'a ( algebra różniczkowa )
• Całka nieelementarna
• Integracja symboliczna

Notatki

• Bronstein, Manuel (1990). „Całkowanie funkcji elementarnych” . Dziennik obliczeń symbolicznych . 9 (2): 117–173. doi : 10.1016/s0747-7171(08)80027-2 .

• Bronstein, Manuel (1998). „Samouczek integracji symbolicznej” (PDF) . {{ cite journal }} : Cite journalwymaga |journal= ( pomoc )

• Bronstein, Manuel (2005). Integracja symboliczna I. Skoczek. ISBN   3-540-21493-3 .

•   Davenport, James H. (1981). O całkowaniu funkcji algebraicznych . Notatki z wykładów z informatyki . Tom. 102. Springera. ISBN 978-3-540-10290-8 .

•   Geddes, Keith O .; Czapor, Stephen R.; Labahn, George (1992). Algorytmy algebry komputerowej . Boston, MA: Wydawcy akademiccy Kluwer. s. XXII + 585. Bibcode : 1992afca.book.....G . doi : 10.1007/b102438 . ISBN 0-7923-9259-0 .

• Mojżesz, Joel (2012). „Macsyma: osobista historia” . Dziennik obliczeń symbolicznych . 47 (2): 123–130. doi : 10.1016/j.jsc.2010.08.018 .

•   Risch, RH (1969). „Problem integracji w kategoriach skończonych” . Transakcje Amerykańskiego Towarzystwa Matematycznego . Amerykańskie Towarzystwo Matematyczne. 139 : 167–189. doi : 10.2307/1995313 . JSTOR 1995313 .

• Risch, RH (1970). „Rozwiązanie problemu integracji w kategoriach skończonych” . Biuletyn Amerykańskiego Towarzystwa Matematycznego . 76 (3): 605–608. doi : 10.1090/S0002-9904-1970-12454-5 .

•   Rosenlicht, Maxwell (1972). „Integracja w kategoriach skończonych”. Amerykański miesięcznik matematyczny . Amerykańskie Stowarzyszenie Matematyczne. 79 (9): 963–972. doi : 10.2307/2318066 . JSTOR 2318066 .

Linki zewnętrzne

• Bhatt, Bhuvanesh. „Algorytm Rischa” . MathWorld .