Der Algorithmus von Risch, genannt nach Robert Henry Risch, ist ein Algorithmus für die Rechnungsoperation der unbestimmten Integration (d. h., Antiableitungen findend). Der Algorithmus gestaltet das Problem der Integration in ein Problem in der Algebra um. Es basiert auf der Form der Funktion, die wird integriert und auf Methoden, um vernünftige Funktionen, Radikale, Logarithmen und Exponentialfunktionen zu integrieren. Risch, der den Algorithmus 1968, genannt es ein Entscheidungsverfahren entwickelt hat, weil es eine Methode ist, um zu entscheiden, ob eine Funktion eine Elementarfunktion als ein unbestimmtes Integral hat; und auch, wenn es tut, es bestimmend. Der Algorithmus von Risch wird (in mehr als 100 Seiten) in Algorithmen für die Computeralgebra von Keith O. Geddes, Stephen R. Czapor und George Labahn zusammengefasst. Der Risch-normannische Algorithmus (nach A. C. Norman), eine schnellere, aber weniger starke Technik, wurde 1976 entwickelt.

Beschreibung

Der Risch Algorithmus wird verwendet, um Elementarfunktionen zu integrieren. Das sind erhaltene Funktionen durch das Bestehen exponentials, Logarithmen, Radikale, trigonometrische Funktionen und die vier arithmetischen Operationen (+  × ÷). Laplace hat dieses Problem für den Fall von vernünftigen Funktionen behoben, weil er gezeigt hat, dass das unbestimmte Integral einer vernünftigen Funktion eine vernünftige Funktion und eine begrenzte Zahl von unveränderlichen Vielfachen von Logarithmen von vernünftigen Funktionen ist. Der von Laplace angedeutete Algorithmus wird gewöhnlich in Rechnungslehrbüchern beschrieben; als ein Computerprogramm wurde es schließlich in den 1960er Jahren durchgeführt.

Liouville hat das durch den Algorithmus von Risch behobene Problem formuliert. Durch den analytischen bewiesener Liouville meint, dass, wenn es eine elementare Lösung g der Gleichung g  = f dann für Konstanten α und Elementarfunktionen u und v gibt, die Lösung der Form ist

Risch hat eine Methode entwickelt, die demjenigen erlaubt, nur einen begrenzten Satz von Elementarfunktionen der Form von Liouville zu denken.

Die Intuition für den Algorithmus von Risch kommt aus dem Verhalten der Exponentialfunktionen und Logarithmus-Funktionen unter der Unterscheidung. Für die Funktion f e, wo f und g Differentiable-Funktionen sind, haben wir

so, wenn e im Ergebnis einer unbestimmten Integration waren, wie man erwarten sollte, ist es innerhalb des Integrals. Außerdem als

dann, wenn (ln g) im Ergebnis einer Integration waren, dann sollten nur einige Mächte des Logarithmus erwartet werden.

Problem-Beispiele

Die Entdeckung einer elementaren Antiableitung ist zu Details sehr empfindlich. Zum Beispiel hat die folgende Funktion eine elementare Antiableitung:

nämlich:

(Einige Computeralgebra-Systeme können hier eine Antiableitung in Bezug auf Nichtelementarfunktionen zurückgeben (d. h. elliptische Integrale), die jedoch außerhalb des Spielraums des Algorithmus von Risch sind.), Aber wenn 71 zu 72 geändert wird, ist es nicht möglich, die antiabgeleiteten Verwenden-Elementarfunktionen zu vertreten.

Die folgende Funktion ist ein komplizierteres Beispiel:

Tatsächlich hat die Antiableitung dieser Funktion eine ziemlich kurze Form:

Durchführung

Das Umwandeln des theoretischen Algorithmus von Risch in einen Algorithmus, der durch einen Computer effektiv durchgeführt werden kann, ist eine komplizierte Aufgabe, die viel Zeit in Anspruch genommen hat.

Der Fall rein sind transzendente Funktionen (die Wurzeln von Polynomen nicht einschließen) relativ leicht und sind früh in den meisten Computeralgebra-Systemen durchgeführt worden. Die erste Durchführung wurde von Joel Moses in Macsyma bald nach der Veröffentlichung von Papier von Risch getan.

Der Fall von rein algebraischen Funktionen ist gelöst und darin durchgeführt worden Nehmen durch James H. Davenport Ab.

Der allgemeine Fall ist gelöst und im Notizblock, einem Vorgänger des Axioms von Manuel Bronstein durchgeführt worden.

Entscheidbarkeit

Der Risch auf allgemeine Elementarfunktionen angewandte Algorithmus ist nicht ein Algorithmus, aber ein Halbalgorithmus, weil er als ein Teil seiner Operation überprüfen muss, wenn bestimmte Ausdrücke zur Null (unveränderliches Problem) insbesondere im unveränderlichen Feld gleichwertig sind. Für Ausdrücke, die nur Funktionen einschließen, die allgemein genommen sind, um elementar zu sein, ist es nicht bekannt, ob ein Algorithmus, der solch eine Kontrolle durchführt, besteht oder nicht (aktuelle Computeralgebra-Systeme Heuristik verwenden); außerdem, wenn man die absolute Wertfunktion zur Liste von Elementarfunktionen hinzufügt, ist es bekannt, dass kein solcher Algorithmus besteht; sieh den Lehrsatz von Richardson.

Bemerken Sie, dass dieses Problem auch im polynomischen Abteilungsalgorithmus entsteht; dieser Algorithmus wird scheitern, wenn er nicht richtig bestimmen kann, ob Koeffizienten identisch verschwinden. Eigentlich verwendet jeder nichttriviale Algorithmus in Zusammenhang mit Polynomen den polynomischen Abteilungsalgorithmus, der eingeschlossene Algorithmus von Risch. Wenn das unveränderliche Feld, d. h. für von x nicht abhängige Elemente berechenbar ist, ist das Problem der Nullgleichwertigkeit entscheidbar, dann ist der Algorithmus von Risch ein ganzer Algorithmus. Beispiele von berechenbaren unveränderlichen Feldern sind und, d. h., rationale Zahlen und vernünftige Funktionen in y mit Koeffizienten der rationalen Zahl beziehungsweise, wo y ein unbestimmter ist, der von x nicht abhängt.

Das ist auch ein Problem im Beseitigungsmatrixalgorithmus von Gaussian (oder jeder Algorithmus, der den nullspace einer Matrix schätzen kann), der auch für viele Teile des Algorithmus von Risch notwendig ist. Beseitigung von Gaussian wird falsche Ergebnisse erzeugen, wenn sie nicht richtig bestimmen kann, ob eine Türangel identisch Null-ist).

Siehe auch

• Listen von Integralen
• Der Lehrsatz von Liouville (Differenzialalgebra)
• Symbolische Integration
• Axiom (Computeralgebra-System)
• Unvollständige Gammafunktion

Referenzen