Benutzer:Berntie/Risch-Algorithmus

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoVorlage:SSen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Berntie auf.

Eine Mitarbeit am entstehenden Artikel ist ausdrücklich erwünscht.

Der Risch-Algorithmus, benannt nach Robert Risch, ist ein Algorithmus für die unbestimmte Integration, also zum Finden von Stammfunktionen. Er transformiert das analytische Problem in ein algebraisches. Der Algorithmus basiert auf der Form der zu integrierenden Funktion und auf Integrationsmethoden für rationale Funktionen, Wurzelfunktionen, Logarithmen und Exponentialfunktionen. Risch, der den Algorithmus 1986 entwickelte, nannte ihn ein Entscheidungsverfahren, da er eine Methode darstellt, die entscheidet, ob eine Funktion eine elementare Funktion als Stammfunktion hat, und diese bestimmt, falls sie existiert. Der Risch-Algorithmus wird (auf über 100 Seiten) in Algorithms for Computer Algebra von Keith O. Geddes, Stephen R. Czapor und George Labahn beschrieben. Der Risch-Norman-Algorithmus, eine schnellere aber weniger mächtige Methode als der Risch-Algorithmus, wurde 1976 entwickelt.

Beschreibung

Der Risch-Algorithmus wird zur Integration elementarer Funktionen verwendet. Elementare Funktionen entstehen durch Verkettung von Logarithmen, Exponential-, Wurzel- und trigonometrischen Funktionen sowie den vier Grundrechenarten. Laplace löste das Problem für den Fall rationaler Funktionen, als er zeigte, dass das unbestimmte Integral einer rationalen Funktion eine rationale Funktion mit einer endlichen Anzahl konstanter Vielfacher von Logarithmen rationaler Funktionen ist. Der von Laplace beschriebene Algorithmus wird in Analysis-Lehrbüchern beschrieben, wurde aber erst in den 1960er-Jahren im Computer implementiert.

Das vom Risch-Algorithmus gelöste Problem wurde von Joseph Liouville formuliert: Liouville bewies mit analytischen Mitteln, dass, falls $g$ eine elementare Funktion und Lösung der Gleichung $g'=f$ ist, eine endliche Anzahl Konstanten $\alpha _{i}$ und elementare Funktionen $u_{i}$ und $v$ existieren, sodass $g$ von der Form

$g=v+\sum _{i=1}^{n}\alpha _{i}\ln u_{i}$

ist.

Risch entwickelte eine Methode, die es erlaubt, nur eine endliche Menge elementarer Funktionen in Liouvilles Form zu betrachten. Seine Intuition rührt vom Verhalten der Exponential- und Logarithmusfunktionen unter Differentiation her. Für differenzierbare Funktionen $f$ und $g$ gilt

$(f\cdot e^{g})'=(f^{\prime }+f\cdot g^{\prime })\cdot e^{g}$ und $(f\cdot \ln ^{n}g)'=f^{\prime }\ln ^{n}{g}+nf{\frac {g^{\prime }}{g}}\ln ^{n-1}{g}.$

Daher liegt es Nahe, zu erwarten, dass, falls $e^{g}$ oder eine Logarithmenpotenz im Resultat einer unbestimmten Integration vorkommt, $e^{g}$ beziehungsweise eine geringfügig höhere Logarithmenpotenz auch im Integral vorkommt.

Eine wichtige Folge von Rischs Ergebnis ist, dass sich das Fehlerintegral nicht elementar darstellen lässt.

Problembeispiele

Das Finden elementarer Stammfunktionen ist sehr empfindlich gegenüber Änderungen im Detail. Beispielsweise hat die Funktion

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

eine elementare Stammfunktion.

Wird $71$ zu $72$ geändert, ist es nicht mehr möglich, die Stammfunktion durch elementare Funktionen darzustellen. Der Grund dafür ist, dass die Galoisgruppe von

$x^{4}+10x^{2}-96x-71$

$D(4)$ ist, also beispielsweise von den Permutation $(1234)$ und $(13)$ erzeugt wird, und (wie $x^{4}-2$) acht Elemente enthält, während die Galoisgruppe von

$x^{4}+10x^{2}-96x-72$

$S(4)$ ist, also beispielsweise von den Permutationen $(12)$, $(13)$, $(14)$ erzeugt wird, und 24 Elemente enthält.

Entscheidbarkeit

Der Risch-Algorithmus ist eigentlich kein Algorithmus, sondern ein Semi-Algorithmus, da er in einem Teilschritt einen Ausdruck auf Gleichheit mit $0$ prüfen muss. Für elementare Funktionen ist es nicht bekannt, ob für diesen Teilschritt überhaupt ein Algorithmus existiert. (Wird die Betragsfunktion ebenfalls zu den elementaren Funktionen gezählt, so ist bekannt, dass kein solcher Algorithmus existiert.) Moderne Computeralgebrasysteme verwenden daher Heuristiken für diesen Teilschritt.

Siehe auch

• Tabelle von Ableitungs- und Stammfunktionen
• Algebraische Integration

Literatur

• R. H. Risch: The Problem of Integration in Finite Terms. In: Transactions of the American Mathematical Society. 139, 1969, S. 167–189. doi:10.2307/1995313. [1]
• R. H. Risch: The solution of the Problem of Integration in Finite Terms. In: Bulletin of the American Mathematical Society. 76, 1970, S. 605–608. doi:10.1090/S0002-9904-1970-12454-5. AMS page PDF document
• Maxwell Rosenlicht: Integration in finite terms. In: American Mathematical Monthly. 79, 1972, S. 963–972. doi:10.2307/2318066.
• Geddes, Czapor, Labahn: Algorithms for Computer Algebra (Englisch). Kluwer Academic Publishers, 1992, ISBN 0-7923-9259-0.
• Manuel Bronstein: Symbolic Integration I (Englisch). Springer, 2005, ISBN 3-540-21493-3.
• Manuel Bronstein: Symbolic Integration Tutorial (englisch, PDF) 1998.
• Bhatt, Bhuvanesh: Risch Algorithm. In: MathWorld (englisch).