Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


39. Integration



Symbolische Integration

Falls über eine Funktion vollständige Informationen zur Verfügung stehen, lohnt es sich möglicherweise, eine Methode anzuwenden, die in der Umformung einer bestimmten Darstellung der Funktion besteht, anstatt mit Zahlenwerten zu arbeiten. Das Ziel besteht darin, eine Darstellung der Funktion in eine Darstellung des Integrals umzuwandeln, praktisch in der gleichen Weise, in der ein unbestimmtes Integral von Hand berechnet wird.

Ein einfaches Beispiel dafür ist die Integration von Polynomen. In Kapitel 36 betrachteten wir Verfahren, die es gestatteten, Summen und Produkte von Polynomen »symbolisch« zu berechnen. Diese benutzen Programme, die eine bestimmte Darstellung der Polynome bearbeiteten und aus dieser Darstellung der Ergebnisse erzeugten. Die Integration (und Differentiation) von Polynomen kann gleichfalls auf diese Weise ausgeführt werden. Falls ein Polynom

p(x) = p0 + p1x + p2x2 + ... + pN-1xN-1

einfach in der Weise dargestellt ist, daß die Werte der Koeffizienten in einem Feld p abgelegt werden, so kann das Integral leicht wie folgt berechnet werden:

    for i:=N downto 1 do p[i]:=p[i-1]/i; p[0]:=0;

Für jedes Glied des Polynoms wird in diesem Programm die bekannte Regel für die symbolische Integration Integral 0->x ti-1 dt = xi/i für i > 0 angewandt. Durch Hinzufügen weiterer Regeln für die symbolische Integration kann eine umfangreichere Klasse von Funktionen als nur die Polynome behandelt werden. Wenn man Verknüpfungsregeln, wie die der partiellen Integration,

Integral u dv = uv - Integral v du

hinzufügt, kann man die Menge der integrierbaren Funktionen beträchtlich erweitern. (Die partielle Integration erfordert eine Möglichkeit zur Differentiation. Eine symbolische Differentiation ist etwas einfacher als eine symbolische Integration, da eine sinnvolle Menge elementarer Regeln zusammen mit Verknüpfungen ermöglichenden Kettenregel für die meisten gebräuchlichen Funktionen ausreichend ist.)

Die große Anzahl existierender Regeln, die auf spezielle Funktionen anzuwenden sind, bewirkt, daß die symbolische Integration eine komplizierte Aufgabe ist. Jedoch wurde erst unlängst gezeigt, daß für diese Aufgabe ein Algorithmus existiert: eine Prozedur, die für eine beliebige gegebene Funktion entweder ihr Integral zurückgibt oder aussagt, daß das Ergebnis nicht mit Hilfe elementarer Funktionen formuliert werden kann. Eine Beschreibung dieses Algorithmus in seiner allgemeinsten Form würde über den Rahmen dieses Buches hinausgehen. Wenn die zu verarbeitenden Funktionen jedoch einer kleinen, beschränkten Klasse angehören, kann die symbolische Integration ein leistungsfähiges Werkzeug sein.

Natürlich gilt für symbolische Methoden die grundlegende Einschränkung, daß sehr viele Integrale (von denen viele in der Praxis häufig auftreten) nicht symbolisch berechnet werden können. Wir wollen nunmehr einige Verfahren betrachten, die entwickelt wurden, um Näherungen für die Werte wirklicher Integrale zu berechnen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]