Geschickt integrieren

17.01.2008, 12:09

tigerbine

Geschickt integrieren

Hallo zusammen,

mit liegt ein normiertes Polynom vom Grad n in Linearfaktorzerlegung vor. Gibt es einen geschickten Weg das Integral über dem Intervall [a,b] zu Berechnen, d.h. ohne dass man das Polynom vorher ausmultipliziert?

LG,
tigerbine

17.01.2008, 19:57

Dual Space

Auf diesen Beitrag antworten »

RE: Geschickt integrieren
Mmm ... ich fürchte, da gibt es keinen allgemeinen Trick. verwirrt

17.01.2008, 23:28

tigerbine

Auf diesen Beitrag antworten »

RE: Geschickt integrieren
@ Dual: Schau mal hier rein. Ich will eigentlich spezielle Polynome integrieren. Knotenpolynome zu äquidistanten Stützstellen auf [a,b] Ich frage mich warum immer eine Potenz von (b-a) raus kommt.

18.01.2008, 01:36

tigerbine

Auf diesen Beitrag antworten »

RE: Geschickt integrieren
Für die ersten würde das z.B. (sagt maple) so aussehen:

$\begin{eqnarray*} &&\omega_1(x) = (x-a)(x-b) \\ &&\Rightarrow \int_a^b \omega_1(x)~dx = 1/6\,(a-b)^3 \end{eqnarray*}$

$\begin{eqnarray*} &&\omega_3(x) = (x-a)(x-(a+(b-a)/3))(x-(a+2(b-a)/3))(x-b) \\&&\Rightarrow \int_a^b \omega_3(x)~dx =23/135\,(a-b)^5 \end{eqnarray*}$

$\begin{eqnarray*} &&\omega_5(x) \\&&\Rightarrow \int_a^b \omega_3(x)~dx =11/52500\,(a-b)^7 \end{eqnarray*}$

Aber warum dieses (a-b) verwirrt

18.01.2008, 11:14

WebFritzi

Auf diesen Beitrag antworten »

RE: Geschickt integrieren

Zitat:

Original von tigerbine
@ Dual: Schau mal hier rein.

18.01.2008, 11:21

tigerbine

Auf diesen Beitrag antworten »

RE: Geschickt integrieren
Dann mach ich den Link mal offiziell. Der Artikel ist aber noch in der Bearbeitung. Augenzwinkern

Mir geht es um die Berechnung der Fehlerabschätzungen bei Newton-Cotes-Formeln (numerische Integration). Leider fallen diese in vielen Skripten einfach vom Himmel. Man kann sicher mit "brute force" einfach ausrechnen, integrieren, zusammenfassen, faktorisieren, da aber "immer" (zumindest in den gedruckten Beispielen) der Faktor (b-a) in einer Potenz auftaucht, vermute ich da doch ein System.

Leider weiß ich eben nicht, wie ich das Integral geschickt berechnen kann.

18.01.2008, 11:41

Tomtomtomtom

Auf diesen Beitrag antworten »

Ich habe noch kein Ergebnis, aber was ich als erstes machen würde (und jetzt auch mal ausprobieren werde) ist für beliebige Nullstellen eine Rekursionsformel nach dem Grad des Polynoms aufzustellen und mit vollständiger Induktion oder ähnlichem zu beweisen. Wenn man sich die ersten mal anschaut, sieht das sehr danach aus, als ob das gehen könnte.

18.01.2008, 12:04

Dual Space

Auf diesen Beitrag antworten »

Ich teile die Ansicht tomtomtomtoms. Zunächst wäre es sinnvoll eine allgemeine Darstellung für die Knotenpolynome zu haben, also $\begin{eqnarray*} \omega_n=\dots \end{eqnarray*}$ . Hast du sowas parat?

18.01.2008, 12:31

Tomtomtomtom

Auf diesen Beitrag antworten »

Auf jeden Fall kannst du in dem Integral schonmal eine Koordinatentransformation durchführen, so daß die Stützstellen äquidistant im Intervall [-1,1] liegen. Ich habs nicht ausgerechnet, aber dadurch dürfte der Vorfaktor mit der entsprechenden Potenz von (a-b)^n entstehen. Bleibt natürlich immer noch die Aufgabe, eine schöne Formel für den restlichen Koeffizienten zu finden, und zu beweisen.

18.01.2008, 12:41

tigerbine

Auf diesen Beitrag antworten »

@Dual Space: Was meinst Du damit? Es ist mir nur die Darstellung (Produkt) aus dem WS bekannt.

@TTTT: Bist Du fit in Analysis? Ich hänge mal ein Skript an. Dort werden Quadraturfehler berechnet, Idee ist die zu integrierende Funktion f mittels Taylorpolynom zu approximieren (Restglied von Peano). S. 51. h entspricht der Intervalllänge, also h=(b-a). Am Ende S. 55 erhält man dann eine Fehlerformel aus 3 Gliedern. (3.8) und somit das Auftreten der Potenz von (b-a) erklärt. Ich steig da aber nicht ganz durch.

Da die Probleme Knotenpolynom und Fehlerdarstellung zusammenhängen bekommt man auf diesen Seiten vielleicht auch eine Idee für das Integral des KP. Die Frage könnte man sich ja auch unabhängig von der numerischen Integrationsproblematik gestellt haben.

Danke Wink

18.01.2008, 14:23

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Original von Tomtomtomtom
Auf jeden Fall kannst du in dem Integral schonmal eine Koordinatentransformation durchführen, so daß die Stützstellen äquidistant im Intervall [-1,1] liegen. Ich habs nicht ausgerechnet, aber dadurch dürfte der Vorfaktor mit der entsprechenden Potenz von (a-b)^n entstehen. Bleibt natürlich immer noch die Aufgabe, eine schöne Formel für den restlichen Koeffizienten zu finden, und zu beweisen.

Hab ich hier mal gemacht. Wegen des verlinkten Skripts aber auf das Intervall [0,1]. Die Transfo würde aber nur (b-a) bringen, und keine Potenz, oder?

18.01.2008, 14:43

Tomtomtomtom

Auf diesen Beitrag antworten »

Ne, ein b-a aus jedem Faktor und noch eins aus der Funktionaldeterminante. Kommt genau hin, egal welche lineare Transformation auf ein beliebiges Intervall man vornimmt. Und passt mit den Exponenten dieses Ausdrucks aus deinem Posting zusammen.

18.01.2008, 14:52

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Original von Tomtomtomtom
Ne, ein b-a aus jedem Faktor und noch eins aus der Funktionaldeterminante.

Kannst du das mal ausschreiben. Im Moment stehe ich mir irgendwie im Weg. Danke.

18.01.2008, 15:31

tigerbine

Auf diesen Beitrag antworten »

Meinst Du das vielleicht so?

18.01.2008, 15:31

Tomtomtomtom

Auf diesen Beitrag antworten »

Ich nehme mal dein vorgeschlagenes Intervall [0,1], aber im Prinzip geht das mit jedem Intervall.

Du willst berechnen:

$\begin{eqnarray*} \int_a^b \prod_{i=0}^n \big(x - a+\frac{i}{n}(a-b)\big)dx \end{eqnarray*}$

Damit es nicht ganz so unhandlich wird, versuchst du eine lineare Transformation u=cx+d auf das Intervall [0,1]. Bei linearen Transformationen bleiben die Stützstellen äquidistant. Damit die Grenzen passen muß gelten:

ca+d=0, cb+d=1

Das ist ein lineares GLS in c,d mit der Lösung

$\begin{eqnarray*} d=- \frac{a}{b-a}, c=\frac{1}{b-a} \end{eqnarray*}$ .

Also ist

$\begin{eqnarray*} u=\frac{1}{b-a}x-\frac{a}{b-a} \end{eqnarray*}$

oder umgestellt $\begin{eqnarray*} x-a=u(b-a) \end{eqnarray*}$

und $\begin{eqnarray*} dx=(b-a)du \end{eqnarray*}$ .

Oben eingesetzt ergibt sich

$\begin{eqnarray*} \int_0^1 \prod_{i=0}^n \big( u (b-a) +\frac{i}{n}(a-b)\big) \cdot (b-a) du \end{eqnarray*}$

Jetzt kannst du aus jedem Faktor ein (b-a) rausziehen und noch das ganz hinten, was von der Funktionaldeterminante herrührt, und erhältst:

$\begin{eqnarray*} =(b-a)^{n+2} \int_0^1 \prod_{i=0}^n \big( u - \frac{i}{n}\big) du \end{eqnarray*}$

Bleibt trotzdem das Problem, eine geschlossene Darstellung für das Integral zu finden, das ist jetzt aber schon nur noch eine Zahl. Wirklcih einfacher wird das Problem dadurch aber nicht, man muß sich aber wenigstens nicht mehr mit dem beliebigen Intervall rumschlagen.

18.01.2008, 15:48

tigerbine

Auf diesen Beitrag antworten »

hast Du meins mal Korrektur gelesen?

Zitat:

Bleibt trotzdem das Problem, eine geschlossene Darstellung für das Integral zu finden, das ist jetzt aber schon nur noch eine Zahl. Wirklcih einfacher wird das Problem dadurch aber nicht, man muß sich aber wenigstens nicht mehr mit dem beliebigen Intervall rumschlagen.

Doch, wir haben schon viel erreicht. Nämlich mehr Verständnis für die Gestalt der Quadraturfehler. Mit den 2 Ausklammerungsmöglichkeiten erklären sich auch Teile der Fehlerformeln für summierte Formeln.

Bleibst sicher das Problem, den Fehlerfaktor/Fehlerkonstante zu bestimmen. Ob es dafür eine Formel gibt, weiß ich nicht. Ist mir zumindest noch nie unter gekommen. Ich werde da mal weiter recherchieren.

18.01.2008, 16:13

Tomtomtomtom

Auf diesen Beitrag antworten »

Naja, das wird eigentlich nicht gemacht, es reicht, daß man weiß, daß man es gegen eine Konstante abschätzen kann. Bei dem Faktor, den man aus dem Satz von Taylor gewinnt, kann man ja eh nur eine Abschätzung angeben, und damit ist es relativ sinnlos, den anderen Faktor exakt ausrechnen zu wollen. In der Regel geht es ja nur um die Größenordnung des Fehlers im Verhältnis zur Intervalllänge h (bzw. Anzahl der Stützstellen). Wenn der Fehler dann in der Größenordnung h^3 oder h^4 liegt, geht das eh so schnell gegen 0, daß es herzlich egal ist, wie genau man die Konstanten abgeschätzt hat.

18.01.2008, 16:16

tigerbine

Auf diesen Beitrag antworten »

Dann ist mit dem Umformen eigentlich das Nötige getan, oder? In die Konstante fließt dann noch der Faktor $\begin{eqnarray*} \frac{1}{(n+1)!} \end{eqnarray*}$ ein und man kann sich, wenn man mag die Konstanten für gängige Formeln tabellieren.

Richtig so?

18.01.2008, 16:47

Tomtomtomtom

Auf diesen Beitrag antworten »

Ich möchte dich nicht kritisieren, aber ich hab mir jetzt mal die Links angeschaut, und da stellt sich mir die Frage, was genau möchtest du in deinem neuen Workshop eigentlich machen? Numerik ist absolut nicht mein Gebiet, und vielleicht sollte sich das mal jemand anschauen, der mehr Ahnung davon hat als ich, aber soweit ich mich erinnern kann, sind Interpolation und Quadratur zwei völlig verschiedene paar Schuhe. Wenn ich das beim überfliegen richtig mitbekommen habe, willst du das komplette Interpolationspolynome über alle Stützstellen als Quadraturformeln verwenden. Ist das wirklich üblich? Ich kenne eigentlich nur Verfahren, die Quadraturen über höchstens 3 oder 4 Stützstellen nebeneinanderliegende Stützstellen verwenden, und diese werden dann halt zusammengesetzt. Gerade auch deswegen weil ein höherer Grad des Interpolationspolynoms nicht unbedingt zu einer Verbesserung der Quadraturformel führt.

18.01.2008, 17:57

tigerbine

Auf diesen Beitrag antworten »

Zitat:

ch möchte dich nicht kritisieren, aber ich hab mir jetzt mal die Links angeschaut, und da stellt sich mir die Frage, was genau möchtest du in deinem neuen Workshop eigentlich machen?

Also der [Artikel] ist gerade nur ein Zwischenspeicher von Überlegungen. Der richtige [WS] heißt numerische Integration, den kannst du aber noch nicht sehen. Bei dessen Bearbeitungen stellte sich mir eben die FRage, warum taucht in der Fehlerabschatzung immer (b-a) in einer Potenz auf. Das sollte nun geklärt sein und ich werde es dann in den [WS] einbauen.

Zitat:

aber soweit ich mich erinnern kann, sind Interpolation und Quadratur zwei völlig verschiedene paar Schuhe. Wenn ich das beim überfliegen richtig mitbekommen habe, willst du das komplette Interpolationspolynome über alle Stützstellen als Quadraturformeln verwenden. Ist das wirklich üblich?

Ja und nein. Es ist ein gängiger Einstieg folgendes zu tun. Anstatt eine Funktion f zu Integrieren, integriert man ein IP, welches man ja auch als Approximation der Funktion f auffassen kann. Dazu wählt man die Lagrangedarstellung und landet beim Thema "Interpolatorische Quadraturformeln". Den Spezialfall für äquidistante Stützstellen (Newton-Cotes-Formel) habe ich hier versucht zu betrachten.

Zitat:

Ich kenne eigentlich nur Verfahren, die Quadraturen über höchstens 3 oder 4 Stützstellen nebeneinanderliegende Stützstellen verwenden, und diese werden dann halt zusammengesetzt.

Das Manko der Lagrange-Interpolation ist, dass man für größere Polynomgrade (n) i.a. nicht bessere Ergebnisse erwarten kann. Daher ist es richtig, dass auch die Integration dieser nicht wirklich Sinn macht. Dennoch kann man die Formeln aufstellen.

Das was Du dann ansprichst sind zusammengesetzte Quadraturformeln. D.h. Fixer Polynomgrad, aber auf immer kleineren Teilintervallen. auch hier werde ich die Darstellung des Fehlers benötigen, deswegen habe ich auch in h und (b-a) unterschieden (letzter link). Mit diesen Formeln sind dann auch die Konvergenzprobleme beseitigt.

Nun klarer? Augenzwinkern

18.01.2008, 18:10

Tomtomtomtom

Auf diesen Beitrag antworten »

Ja, wenn du das im Rahmen eines größeren Workshops einbaust, ok. Ich will dir da auch nicht reinreden, aber ich hätte es einfach für didaktisch falsch gehalten, die gesamte Quadraturtheorie von Interpolationspolynomen mit beliebiger Anzahl Stützstellen aus aufzubauen, eben weil es sehr schnell zu Problemen führt (gerade bei äquidistanten Stützstellen) und in der Praxis nicht so gemacht wird.

18.01.2008, 18:24

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Ich will dir da auch nicht reinreden,

Ein qualifiziertes Gespräch schadet doch niemandem. Augenzwinkern

Es ist eben ein üblicher Einstieg, den ich nicht "erfunden" habe, ihn aber für gut halte, solange man da nicht aufhört. Wie gesagt benötigt man die Formeln auch um die zusammengesetzten berechnen zu können. Ferner geben sie was die Ordnung einer QF betrifft, das untere Ende, oder das was man mindestens erwarten sollte.

Zitat:

und in der Praxis nicht so gemacht wird

Spielst Du auf adaptive Verfahren an?

18.01.2008, 19:06

Tomtomtomtom

Auf diesen Beitrag antworten »

Nein davon habe ich erst recht keine Ahnung mehr. Aber ich habe halt an "Grundverfahren" noch nie etwas anderes alsTrapezregel, Mittelpunktsregel, Simpsonregel, 3/8-Regel gesehen. Selbst die in dem Skript erwähnte Milne-Regel war mir unbekannt, und in irgendwelchen Tabellen sind auch in der Regel nur zu den von mir genannten Verfahren überhaupt die Knotengewichte aufgeführt.

Aber um nochmal auf das ursprüngliche Problem zurückzukommen: An welcher Stelle benötigst du denn nun konkret solche Ausdrücke, über die zu zuerst etwas wissen wolltest? Ich sehe immer nur Beträge in der Fehlerabschätzung.

18.01.2008, 19:19

tigerbine

Auf diesen Beitrag antworten »

RE: Geschickt integrieren

Zitat:

Original von tigerbine
Für die ersten würde das z.B. (sagt maple) so aussehen:

$\begin{eqnarray*} &&\omega_1(x) = (x-a)(x-b) \\ &&\Rightarrow \int_a^b \omega_1(x)~dx = 1/6\,(a-b)^3 \end{eqnarray*}$

$\begin{eqnarray*} &&\omega_3(x) = (x-a)(x-(a+(b-a)/3))(x-(a+2(b-a)/3))(x-b) \\&&\Rightarrow \int_a^b \omega_3(x)~dx =23/135\,(a-b)^5 \end{eqnarray*}$

$\begin{eqnarray*} &&\omega_5(x) \\&&\Rightarrow \int_a^b \omega_3(x)~dx =11/52500\,(a-b)^7 \end{eqnarray*}$

Aber warum dieses (a-b) verwirrt

Meinst Du die? Primäres Anliegen war mir, wie kommt das (b-a)^? in die Fehlerabschätzungen. Man könnte da auch die Beträge weglassen und von Restgliedern sprechen. Das ist von Autor zu Autor verschieden. Ich hab das dann maple übergeben und mich gefragt, ob es nicht einfacher geht, als erst alles ausmultiplizieren, integrieren, faktorisieren. Und das haben wir ja nun auch geklärt, zumindest woher das(b-a) kommt.

Der Threadtitel mit dem Knotenpolynom war vielleicht nicht sehr glücklich, aber das ist eben der Teil in der Formel auf den es hier ankommt. Aber war ja eigentlich auch nicht für die Öffentlichkeit gedacht.

Meine Fragen sind für das erste beantwortet, ich versuche nun die tabellierten Abschätzungen damit zu rekonstruieren.

Neue Frage »

Antworten »

Geschickt integrieren

Verwandte Themen