Die Trapezregel, das h und das O(h)

26.09.2008, 10:42

tigerbine

Die Trapezregel, das h und das O(h)

Sind die Hauptakteure der kleinen Geschichte, die mich letzte Nacht beschäftigt hat. Oberthema ist immer noch die numerische Integration, dabei bezeichnet die Ordnung einer Quadraturformel, welchen Maximalgrad von Polynomen noch exakt integriert (allerdings +1). So integriert eine QF der Ordnung 2 nur Polynome vom Maximalgrad 1 exakt.

Will man diese Eigenschaft überprüfen, so muss man sich die Fehlerdarstellung anschauen. Bei der Trapezregel:

$\begin{eqnarray*} |I(f)-I_1(f)|\leq \frac{(b-a)^3}{12}\cdot \max_{x \in[a,b]}~|f^{(2)}(x)| \end{eqnarray*}$ (*)

Der erste Faktor hängt nur von der Intervalllänge ab, ist also konstant. Der zweite wird eben für alle $\begin{eqnarray*} f \in \Pi_1 \end{eqnarray*}$ Null. Daher ist die Ordnung (mindestens) 2.

Schauen wir uns nun die summierte Trapezregel an, bei der das Intervall [a,b] in n Teilintervalle der Länge h unterteilt wird.

$\begin{eqnarray*} |I(f)-I^T(f)|\leq \frac{(b-a)}{12}\cdot h^2 \cdot \max_{x \in[a,b]}~|f^{(2)}(x)| \end{eqnarray*}$ (**)

Wieder ist der Faktor mit der Ableitung für die Ordnung verandwortlich, der Faktor h sichert aber für h->0 die Konvergenz der QF gegen das Integral. Soweit ist es mir klar.

----------------------------------------------------------------------------------

Nun betrachten wir die Abschätzung (**) unter einem anderen Blickwinkel. Die Funktion f sei genügend oft stetig differenzierbar. Das Maximum hängt in meinen Augen nicht von h ab, also könnte man vereinfacht schreiben:

$\begin{eqnarray*} |I(f)-I^T(f)|\leq c \cdot h^2 \end{eqnarray*}$

Damit würde der Fehler in der Größenordnung $\begin{eqnarray*} O(h^2) \end{eqnarray*}$ liegen? (***)

Solche Betrachtungen kann man auch noch für andere Formeln aufstellen. In den Büchern wird dann gesagt, man blicke auf (***), die Formel habe die Ordnung 2.

Wie soll ich nun aber aus (***) folgern, dass Polynome vom Maximalgrad 1 exakt integriert werden ?

Meiner Meinung nach gar nicht. Es werden nun weitere Formeln konstruiert, in denen auch mehrere Potenzen von h auftreten. Um aber doch dann ein Abschätzung der Form $\begin{eqnarray*} O(h^{m} \end{eqnarray*}$ , wobei m der kleinste Koeffizient sei, muss man doch erstmal einschränken, dass h<1 gelten soll, oder? Denn nur so ist der Term mit der kleinsten Potenz von h ja der entscheidende.

Vergleicht man nun 2 Formeln, so sollte diejenige mit dem größerem m wohl schneller zum Erfolg führen, also '"besser" sein. Gibt es bzgl. dieser O-Notation auch den Begriff Ordnung?

Danke,
tigerbine Wink

26.09.2008, 11:41

Huggy

Auf diesen Beitrag antworten »

RE: Die Trapezregel, das h und das O(h)
Mein Eindruck ist, dass nur dann Verwirrung entsteht, wenn man 'Ordnung' für unterschiedliche Sachverhalte benutzt. Üblicherweise wird schon sorgfältig unterschieden zwischen dem 'Genauigkeitsgrad' einer Quadraturformel, der angibt, bis zu welchem Grad Polynome noch exakt integriert werden und dem 'Quadraturfehler', der die Abweichung der Formel vom exakten Integral angibt.

Wenn man diese Informationen in der O-Notation zusammenfasst, bleibt üblicherweise dein c als Ableitung stehen, und dann kann man auch den Genauigkeitsgrad erkennen. Eine übliche Schreibweise ist z. B.:

$\begin{eqnarray*} O(h^2f''(\xi)) \end{eqnarray*}$

26.09.2008, 12:02

tigerbine

Auf diesen Beitrag antworten »

Der "übliche" Weg
Naja, die Autoren schreiben aber immer Ordnung. Am Anfang vom Kapitel eben mit der Definition "welche Polynome exakt integriert werden". Zum Beweis kann man imho ohne Probleme den Quadraturfehler (*), (**) heranziehen. Da dann eben der Ableitungsfaktor verschwindet.

Dann untersucht man Formeln, gerne Newotn Cotes etc. und weitere Verfahren. Du erinnerst dich an an die Adaption. Augenzwinkern

irgendwann kommt dann auch die Sprache auf Romberg, oder allgemeiner die Idee der Extrapolation. Hat man bis dato noch mühsam die Formeln konstruiert, fallen sie nun einfach vom Himmel.

Die Autoren nehmen an, dass sich eine QF wie folgt schreiben lässt:

$\begin{eqnarray*} I_h(f)=I(f) + c_1h^{k_1} + c_2h^{k_2} + ....,~k_1 < k_2 \end{eqnarray*}$

Da finde ich schon die ... nicht sehr gelungen, ferner wird keine Aussage über h getroffen. Warum sollte also $\begin{eqnarray*} h^{k_1} \end{eqnarray*}$ der entscheidende Term dieser Abschätzung sein. Es folgt ohne Begründung, dass diese Formel die Ordnung k1 habe. Warum?

Dann konstruiert man eine neue Formel, das wie sei nun erst einmal egal, auf jedenfall gilt dann für diese:

$\begin{eqnarray*} I_h(f)=I(f) + d_1h^{k_2} + ...., \end{eqnarray*}$

Diese sei nun besser, da sie die Ordnung k2 habe. Warum das denn?

Nirgendwo wurde in dem Kapitel eine weitere Definition der Ordnung eingeführt. Aber wie soll ich denn aus der Schrittweite h ablesen, welche Polynome exakt integriert werden. Und integriert die zweite wirklich mehr Polynome "exakt".

Ich würde eher vermuten, dass die neue Formel, bei gleicher Schrittweite h einen kleineren Fehler aufweist. Dabei setzte ich aber |h|<1 voraus. Daher "besser" ist, aber ich würde nicht den Begriff Ordnung wählen, zumindest nicht ohne neue Definition. "Fehlerordnung" oder so...

Problem ist auch, zoomt man etwas heraus, landet man bei der Idee der Richardson Extrapolation. Die Romberg Integration ist nur eine Anwendung davon mit bestimmten Parametern. Eine Andere wäre die numerische Differentiation mittels h-Methode. Da fällt auch wieder der Begriff Ordnung. Na, da kann wohl wohl kaum die exakte Integration gemeint sein.

26.09.2008, 12:23

Huggy

Auf diesen Beitrag antworten »

RE: Der "übliche" Weg
Wenn Bücher den Begriff 'Ordnung' für alles Mögliche verwenden und auch nicht exakt definieren, dann sind das schlampige Bücher.

26.09.2008, 12:35

tigerbine

Auf diesen Beitrag antworten »

RE: Der "übliche" Weg
Stimmt denn meine Vermutung mit diesen zwei Fällen, also das was unterschiedliches gemeint ist und wie ich es interpretiere? Sorry, ich bin nach all dem Lesen (inet, Skripte, Bücher) nun unsicher.

26.09.2008, 13:40

Huggy

Auf diesen Beitrag antworten »

RE: Der "übliche" Weg
So wie du das darstellst, hast du einige Werke studiert, die den Begriff 'Ordnung des Verfahrens' sowohl für den Genauigkeitsgrad der Formel als auch für den Quadraturfehler benutzen. Das ist natürlich misslich.

In der Praxis spielt der Quadraturfehler meist die entscheidende Rolle, da man die Ableitung im Allgemeinen eh nicht kennt, und wenn doch, wird sie nicht ausgewertet.

Die Aussage, der Quadraturfehler sei $\begin{eqnarray*} O(h^n) \end{eqnarray*}$ , hat auch für h > 1 Bedeutung. Bei gegebenem h kann man daraus natürlich nicht schließen, dass ein Verfahren mit höherem n den kleineren Quadraturfehler hat. Das kann man noch nicht mal bei h < 1. Interessieren tut auch meist etwas anderes. Wie ändert sich der maximale Fehler, wenn man h ändert. Wenn man h halbiert, viertelt sich der maximale Fehler bei einem Verfahren $\begin{eqnarray*} O(h^2) \end{eqnarray*}$ , bei einem Verfahren $\begin{eqnarray*} O(h^4) \end{eqnarray*}$ sechzehntelt er sich. Das gilt auch für h > 1.

26.09.2008, 13:44

tigerbine

Auf diesen Beitrag antworten »

RE: Der "übliche" Weg

Zitat:

Die Aussage, der Quadraturfehler sei $\begin{eqnarray*} O(h^n) \end{eqnarray*}$ , hat auch für h > 1 Bedeutung. Bei gegebenem h kann man daraus natürlich nicht schließen, dass ein Verfahren mit höherem n den kleineren Quadraturfehler hat. Das kann man noch nicht mal bei h < 1. Interessieren tut auch meist etwas anderes. Wie ändert sich der maximale Fehler, wenn man h ändert. Wenn man h halbiert, viertelt sich der maximale Fehler bei einem Verfahren $\begin{eqnarray*} O(h^2) \end{eqnarray*}$ , bei einem Verfahren $\begin{eqnarray*} O(h^4) \end{eqnarray*}$ sechzehntelt er sich. Das gilt auch für h > 1.

Ok, das könnte dann der entscheidende Baustein für die Konstruktion der Formeln sein, ich werde dann im [WS] einen erläuternden Satz einschieben, der die "Ordnungen" auseinander hält.

Danke dir. Ich versuche das am Nachmittag umzusetzten. Wink

27.09.2008, 09:55

tigerbine

Auf diesen Beitrag antworten »

Allgemein
So, ich habe nun mal versucht, die zur Richardson gehörige Rekursionsformel bezüglich der Ordnung zu Erläutern. so ok?

Zitat:

Gegeben ist ein zu berechnender Wert einer Funktion. Nennen wir in Allgemein F. Das kann zum Beispiel ein bestimmes Integral sein. In Abhängigkeit von der Schrittweite h haben wir eine Näherungsformel $\begin{eqnarray*} F_h \end{eqnarray*}$ .

Nun treffen wir die Annahme, dass der Fehler eine bestimmte Gestalt hat.

$\begin{eqnarray*} F_h(f)-F(f) = c_1h^{k_1} + c_2h^{k_2} + c_3h^{k_3} + c_4h^{k_4} + ...~,\quad k_1 < k_2 \end{eqnarray*}$

Dabei habe diese Formel die Ordnung k1, d.h. wir können den Approximationsfehler mit $\begin{eqnarray*} O(h^{k_1}) \end{eqnarray*}$ beziffern (Erläuterung).

Nun nehmen wir eine zweite Formel, mit der halben Schrittweite

$\begin{eqnarray*} F_{h/2}(f)-F(f) = c_1(\frac{1}{2}h)^{k_1} + c_2(\frac{1}{2}h)^{k_2} + c_3(\frac{1}{2}h)^{k_3} + c_4(\frac{1}{2}h)^{k_4} + ...~,\quad k_1 < k_2 \end{eqnarray*}$ (*)

Aus diesen beiden konstruiert man nun eine neue Formel und untersucht, welche Ordnung diese hat.

$\begin{eqnarray*} \hat{F}_{h/2} &&=\frac{2^{k_1}F_{h/2}-F_h}{2^{k_1}-1} \quad(**)\\&&= \frac{2^{k_1}[c_1(\frac{1}{2}h)^{k_1} + c_2(\frac{1}{2}h)^{k_2} + c_3(\frac{1}{2}h)^{k_3} + c_4(\frac{1}{2}h)^{k_4}+ ...]-[c_1h^{k_1} + c_2h^{k_2} + c_3h^{k_3} + c_4h^{k_4} + ...]} {2^{k_1}-1} \\&& =\frac{2^{k_1}[c_2(\frac{1}{2}h)^{k_2} + c_3(\frac{1}{2}h)^{k_3} + c_4(\frac{1}{2}h)^{k_4}+ ...]-[ c_2h^{k_2} + c_3h^{k_3} + c_4h^{k_4} + ...]} {2^{k_1}-1} \\&&=d_2h^{k_2} + d_3h^{k_3} + d_4h^{k_4} + ... \end{eqnarray*}$

Hier können wir nun den Approximationsfehler mit $\begin{eqnarray*} O(h^{k_2}) \end{eqnarray*}$ beziffern, die Formel hat also in obigem Sinne eine höherer Ordnung.

Was bedeutet dies?

Wählen wir als konkretes Beispiel $\begin{eqnarray*} k_1=2 \end{eqnarray*}$ und $\begin{eqnarray*} k_2=4 \end{eqnarray*}$ . Der Approximationsfehler der ersten Formel hat dann die Größenordnung $\begin{eqnarray*} O(h^2) \end{eqnarray*}$ , das bedeutet, halbiert man h, so viertelt sich der maximale Fehler dieses Verfahrens. Die durch den Quotienten gewonne Formel leistet, da ihr Approximationsfehler von der Größe $\begin{eqnarray*} O(h^4) \end{eqnarray*}$ bei der Halbierung von h schon eine Sechzehntelung.

Wie kann man es nutzen?

Da es nicht immer möglich ist, die benötigte Schrittweite h a priori zu bestimmen, wird man sich bei der Umsetzung von Verfahren für ein Abbruch Kriterium entscheiden müssen. Welche Möglichkeiten bieten sich einem? Zunächst einmal könnte man mit einer Schrittweite h begonnen, den Wert der Näherung einer Prüfung unterziehen und falls sie nicht bestanden wird, die Berechnung mit der halbierten Schrittweite wiederholen, so lange bis die Abbruchbedingung erfüllt ist.

Sollte der Algorithmus nicht schon direkt für erst gewähltes h abbrechen, so wird man sicher zunächst einen zweiten Durchlauf starten. Wenn immer noch nicht abgebrochen wird, so bietet uns obige Formel (*) die Möglichkeit aus den bereits vorhandenen Daten (sofern man sie gespeichert hat) mit geringem Aufwand eine bessere Approximation zu bestimmen.

Diese Idee kann man in einem Dreiecksschema umsetzten und wir werden im folgenden den Bezug zum Neville-Schema, welches im [WS] Polynominterpolation-Theorie vorgestellt wird aufzeigen.

27.09.2008, 10:34

Huggy

Auf diesen Beitrag antworten »

RE: Allgemein
Sieht gut aus!

27.09.2008, 12:09

tigerbine

Auf diesen Beitrag antworten »

RE: Allgemein
Danke dir, wiedermal Mit Zunge

Neue Frage »

Antworten »

Die Trapezregel, das h und das O(h)

Verwandte Themen