adaptive Integration

25.08.2008, 05:38

tigerbine

Auf diesen Beitrag antworten »

adaptive Integration

Hallo zusammen,

bei einer Skriptlektüre hat mich folgendes verwundert. Nach Newton-Cotes-Formlen wurde folgende Funktion als Motivation für adaptive Verfahren genommen. (basierend auf Simpson-Regel)

Zitat:

$\begin{eqnarray*} \int_{-1}^{1}~\frac{1}{10^{-4}+x^2}~dx \end{eqnarray*}$

Nun kann man für die summierte Simpsonregel die Abschätzung formuieren:

$\begin{eqnarray*} |I(f)-I_2(f)|\leq \frac{(b-a)^5}{2880}\cdot \max_{x \in[a,b]}~|f^{(4)}(x)| \end{eqnarray*}$

Das Problem dabei ist doch eigentlich die Beschränktheit der 4ten Ableitung *** und es gilt:

$\begin{eqnarray*} f^{(4)} = \frac{120}{x^6} \end{eqnarray*}$ edit: gilt nicht, siehe unten

Damit ist die 4te Ableitung auch [-1,1] doch betragsmäßig nicht von oben Beschränkt. (?) Bei der Konstruktion des adaptiven Verfahrens wird dann allerdings folgende Voraussetzung getroffen:

Zitat:

Es gibt eine von der Schrittweite $\begin{eqnarray*} h_i \end{eqnarray*}$ unabhängige Konstante $\begin{eqnarray*} \tau \end{eqnarray*}$ mit:

$\begin{eqnarray*} I_i(f) - I_{2_i}(f) \approx \tau \cdot h_i^5 \end{eqnarray*}$

Das ist aber doch im Grunde die Forderung nach der Beschränktheit der 4ten Ableitung verwirrt

verwirrt

weitere Fragen:

Wer kennt eine Funktion ohne Polstelle, die sich an einer Stelle schon "auftürmt". (Fejér-Kern, würde mir vom Bild her einfallen, aber um das Thema "drücke ich mich gerne )
Sind diese adaptiven Verfahren überhaupt für solche Integrale wie in obigem Beispiel geeignet?

Danke,
tigerbine Wink

Wink

25.08.2008, 10:43

Huggy

Auf diesen Beitrag antworten »

RE: adaptive Integration
Deine Funktion hat doch für x = 0 gar keine Polstelle. Sie hat dort den den Wert 10^4. Sie ist nur sehr stark an der Stelle x = 0 konzentriert. Und dafür ist ein Verfahren mit äquidistanten Stützstellen logischerweise nicht geeignet. Man verschwendet Stützstellen für Bereiche, die praktisch nicht zum Integral beitragen. Ein adaptives Verfahren, das merkt, wo sich etwas tut, und dort die Stützstellen enger wählt, ist dann klar besser.

25.08.2008, 13:46

tigerbine

Auf diesen Beitrag antworten »

RE: adaptive Integration
Finger1

Finger1

Es war wohl einfach zu spät in der Nacht. Vergessen wir den Pol....

Das "Prinzip" hinter den adaptivern verfahren habe ich verstanden, kommen wir aber zu der Voraussetzung der Abschätzung

$\begin{eqnarray*} I_i(f) - I_{2_i}(f) \approx \tau \cdot h_i^5 \end{eqnarray*}$

Stimmt denn nun meine Ableitung? verwirrt

verwirrt

Wie kann es dann ein solches $\begin{eqnarray*} \tau \end{eqnarray*}$ auf [-1,1] geben?

25.08.2008, 13:56

Huggy

Auf diesen Beitrag antworten »

RE: adaptive Integration

Zitat:

Original von tigerbine
Finger1

Finger1

Es war wohl einfach zu spät in der Nacht. Vergessen wir den Pol....

Das "Prinzip" hinter den adaptivern verfahren habe ich verstanden, kommen wir aber zu der Voraussetzung der Abschätzung

$\begin{eqnarray*} I_i(f) - I_{2_i}(f) \approx \tau \cdot h_i^5 \end{eqnarray*}$

Stimmt denn nun meine Ableitung? verwirrt

verwirrt

Wie kann es dann ein solches $\begin{eqnarray*} \tau \end{eqnarray*}$ auf [-1,1] geben?

Dazu kann ich leider nichts beitragen. Bin mit der Thematik zu wenig vertraut.

25.08.2008, 13:56

Mathespezialschüler

Auf diesen Beitrag antworten »

Hallo tigerbine,
also deine Ableitung kann irgendwie nicht stimmen. Nach der Ketten-/Quotientenregel muss doch der Term $\begin{eqnarray*} 10^{-4}+x^2 \end{eqnarray*}$ in einer bestimmten Potenz immer im Nenner stehen bleiben, während Potenzen von $\begin{eqnarray*} x \end{eqnarray*}$ immer in den Zähler gelangen. Im Übrigen erkennt man schon ohne Rechnung an der Darstellung

$\begin{eqnarray*} \frac{1}{10^{-4}+x^2}=\frac{1}{10^{-4}}\cdot \frac{1}{1+(100x)^2} \end{eqnarray*}$

mithilfe der geometrischen Reihe, dass die Funktion im Nullpunkt sogar in eine Potenzreihe (mit Konvergenzradius $\begin{eqnarray*} 10^{-2} \end{eqnarray*}$ ) entwickelbar ist und dementsprechend dort natürlich unendlich oft differenzierbar sein muss.

25.08.2008, 14:18

tigerbine

Auf diesen Beitrag antworten »

Oh man, da hätte ich echt besser in Bett gehen sollen. Hab ich den Summanden einfach mal... lalala. Ich setzt mich nach dem Mittagessen noch mal dran.

Dane Euch Wink

Wink

Anzeige

25.08.2008, 17:14

tigerbine

Auf diesen Beitrag antworten »

So, ich wage mich nun noch einmal aufs Glatteis. Ups

Ups

Wir haben die Funktion

$\begin{eqnarray*} f(x)=\frac{1}{x^2+10^{-4}} \end{eqnarray*}$

Ihre Ableitungen haben die Gestalt einer rationalen Funktion

$\begin{eqnarray*} f^{(n)}(x)=\frac{g(x)}{[x^2+10^{-4}]^{2^n}} \end{eqnarray*}$

Dabei ist g ein Polynom, dessen Maximalgrad m kleiner als $\begin{eqnarray*} (2)^{2^n} \end{eqnarray*}$ (Maximalgrad im Nenner) ist. Sind die Ableitungen (speziell Nr. 4) dann auf [-1,1] betragsmäßig von oben beschränkt oder nicht. verwirrt

verwirrt

Ich würde dazu

$\begin{eqnarray*} \lim_{x \to 0} f^{(n)}(x) \end{eqnarray*}$

betrachten, aber da ich hier schon so viel in den Sand gesetzt habe, frage ich lieber erstmal. Wink

Wink

25.08.2008, 20:52

Huggy

Auf diesen Beitrag antworten »

Die Ableitungen sind natürlich nach oben beschränkt, denn der Nenner jeder Ableitung ist nach unten und der Zähler nach oben beschränkt. Für die 4. Ableitung von

$\begin{eqnarray*} f(x)= \frac{1}{x^2+a^2} \end{eqnarray*}$

ergibt sich:

$\begin{eqnarray*} f^{(4)}(x)= 24\frac{a^4-10a^2x^2+5x^4}{(x^2+a^2)^5} \end{eqnarray*}$

$\begin{eqnarray*} f^{(4)}(x) \end{eqnarray*}$ hat bei x = 0 ein lokales Maximum, welches auch das globale Maximum ist. Daraus folgt:

$\begin{eqnarray*} Max(f^{(4)}(x))\leq \frac{24}{a^6} \end{eqnarray*}$

Frage: Du hast in der Fehlerabschätzung der Simpson-Regel den Faktor 1/2880 vwewendet. Woher kommt der? Ich fand beim Nachschlagen nur den Faktor 1/90.

25.08.2008, 21:22

tigerbine

Auf diesen Beitrag antworten »

Och männo, mit dieser Funktion und mir, das geht einfach nicht zusammen. Aber gut das sie beschränkt ist, dann passt das ja mit der Theorie und dem Beispiel.

Zur Simpson: meinst du in der summierten Formel? Liegt daran, welche Maschenweite in der Formel verwendet wird. Die Maschenweite

$\begin{eqnarray*} h_s = \frac{h}{2} \end{eqnarray*}$

Damit dann in der Formel:

$\begin{eqnarray*} h = 2h_s \end{eqnarray*}$

$\begin{eqnarray*} \frac{32}{2880} = \frac{1}{90} \end{eqnarray*}$

Kannst du mal deine Abschätzung komplett posten? die muss ja in mehr als dem Nenner abweichen. Wink

Wink

25.08.2008, 21:52

Huggy

Auf diesen Beitrag antworten »

Sorry, du hast recht!
Ich habe das summiert überlesen. Damit passt das auch zu meinen Büchern.

25.08.2008, 21:57

tigerbine

Auf diesen Beitrag antworten »

Musst dich nicht entschuldigen. Ich falle doch seid Threadbegin immer wieder auf meinen gleichen Denkfehler rein. Big Laugh

Big Laugh

Wink

26.08.2008, 00:24

tigerbine

Auf diesen Beitrag antworten »

Ist der Ruf erst ruiniert, postet es sich ungeniert
Nehmen wir nun einmal an, jemand möchte obiges Integral mit der Summierten Simpsonregel bestimmen. Es muss auch gar nicht so genau sein (oder würde man $\begin{eqnarray*} \varepsilon \leq 10^{-1} \end{eqnarray*}$ ) schon genau nennen. Sicher, alles eine Frage der Perspektive. verwirrt

verwirrt

Mit dem was Huggy gepostet hat, folgt doch dann, für die summierte Formel

$\begin{eqnarray*} |I(f)-I_2(f)| && \leq \frac{(b-a)}{2880}\cdot h^4 \cdot 24 \cdot 10^{24} \\ && = 4 \cdot 10^{23} \cdot h^4 \\&& \stackrel{!} \leq 10^{-1} \end{eqnarray*}$ (editiert)

Daraus würde sich ergeben:

$\begin{eqnarray*} h \leq \frac{1}{\sqrt{2}} \cdot 10^{-6} \end{eqnarray*}$

Dementsprechend hätte man

$\begin{eqnarray*} \frac{2}{h} = 2\sqrt{2} \cdot 10^6 \end{eqnarray*}$

Teilintervalle auf denen man die Simpson Regel anwenden müßte?

26.08.2008, 10:08

Huggy

Auf diesen Beitrag antworten »

RE: Ist der Ruf erst ruiniert, postet es sich ungeniert
Nicht ganz!!!

(1) Bei (b - a) = 2 behauptet mein Taschenrechner stur:

$\begin{eqnarray*} \frac{2}{2880} \cdot24 \cdot 10^{24}=\frac{1}{6} \cdot 10^{23} \end{eqnarray*}$

(2) h^5 sollte h^5 bleiben.

(3) Und ganz fies habe ich in die Formel a^2 geschrieben. Also ist a = 10^-2 und a^6 = 10^-12. Das spart ein paar Stützstellen.

26.08.2008, 15:26

tigerbine

Auf diesen Beitrag antworten »

RE: Ist der Ruf erst ruiniert, postet es sich ungeniert
Danke, sollte ich mich nun länger nicht melden, muss ich gerade in den Grundrechenarten nachsitzen. Oder bin wie Rumpelstilzchen explodiert. böse

böse

Bis später. Wink

Wink

26.08.2008, 17:17

tigerbine

Auf diesen Beitrag antworten »

Angetreten zum Nachsitzen
So, das $\begin{eqnarray*} h^4 \end{eqnarray*}$ stimmt, aber es war oben falsch. Es gilt:

$\begin{eqnarray*} |I(f) - I^S(f)| \leq \frac{b-a}{2880}\cdot h^4 \cdot \max_{x\in [a,b]} |f^{(4)}(x)| \end{eqnarray*}$

Für das konkrete Integral.

$\begin{eqnarray*} \int_{-1}^{1}~\frac{1}{10^{-4} + x^2}~dx \end{eqnarray*}$

gilt dann:

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

Zitat:

$\begin{eqnarray*} \max~|f^{(4)}(x)| \leq \frac{24}{a^6} \end{eqnarray*}$

Das mit dem a war gemein von dir. Augenzwinkern

Augenzwinkern

$\begin{eqnarray*} a = 10^{-2} \Rightarrow a^6 = 10^{-12} \end{eqnarray*}$

Macht dann am Ende:

$\begin{eqnarray*} |I(f) - I^S(f)| \leq \frac{2}{2880}\cdot h^4 \cdot 24 \cdot 10^{12} = \frac{1}{6} \cdot 10^{11} \cdot h^4 \end{eqnarray*}$

Dann ergibt sich

$\begin{eqnarray*} \frac{1}{6} \cdot 10^{11} \cdot h^4 \stackrel{!} \leq 10^{-1} \end{eqnarray*}$

$\begin{eqnarray*} h^4 \stackrel{!} \leq 6 \cdot 10^{-12} \end{eqnarray*}$

$\begin{eqnarray*} h \stackrel{!} \leq \sqrt[4]{6} \cdot 10^{-3} \end{eqnarray*}$

Anzahl der Teilintervalle:

$\begin{eqnarray*} m:=\frac{2}{h} \stackrel{!} \geq \frac{2}{\sqrt[4]{6}} \cdot 10^{3} \end{eqnarray*}$

Gruß Erstaunt2

Erstaunt2

26.08.2008, 20:04

Huggy

Auf diesen Beitrag antworten »

RE: Angetreten zum Nachsitzen
Das sollte jetzt stimmen, allerdings bin ich auch ein großer Freund der kleinen Fehler, daher ohne jede Gewähr.

Weit über 1000 Intervalle für die mickrige Genauigkeit von 0,1 erscheint zunächst viel. Aber ein paar Zahlen machen das verständlicher:

I = I [-1; 1] = 312,159...
I [-0,1; 0,1] = 294,225...
I [-0,01; 0,01] = 157,079...
I [-0,001; 0,001] = 19,933...

Schon der Bereich in der Mitte, der nur von etwa einem einzigen Intervall abgedeckt wird, trägt signifikant zum Integral bei.

Deshalb: Hoch lebe die adaptive numerische Integration!

26.08.2008, 20:13

tigerbine

Auf diesen Beitrag antworten »

RE: Angetreten zum Nachsitzen

Zitat:

Deshalb: Hoch lebe die adaptive numerische Integration!

Na dann

Prost

27.08.2008, 04:01

tigerbine

Auf diesen Beitrag antworten »

Mit neuem Mut
So, genug gefeiert. Big Laugh

Big Laugh

Wenn man nun das adaptive Verfahren mit dem summierten Vergleichen will, wie muss man da genau vorgehen? Bei dem summierten kann man ja apriori berechnen (so wie wir es getan haben) wie klein man h wählen muss.

Worin ist nun der Aufwand eines Verfahrens zu sehen? In der Anzahl der Funktionsauswertungen?

Wie lange braucht den ein heutzutage handelsüblicher Rechner dafür? Sicher, wenn man es von Hand machen will ist klar, dass man auf mehr wie 1000 Auswertungen wenig Lust hat... nur wird ein Funktionsgraph (z.B. mit unserem Plotter) nicht nach dem gleichen Prinzip , also Wertetabelle erstellt? Das dauert ja nun auch nicht ewig...

Bei dem Adaptiven Verfahren, kann man so wie ich nun meine Unterlagen verstanden habe, nicht apriori berechnen, wie die Intervallaufteilung aussieht, sondern es wird nach jedem Schritt überprüft, ob die geforderte Teilgenauigkeit erreicht wurde. D.h. man müßte am Ende zusammen zählen, wie oft die Funktion in den Durchläufen ausgewertet wurde, um die beiden Verfahren zu vergleichen?

Gruß Wink

Wink

27.08.2008, 11:09

Huggy

Auf diesen Beitrag antworten »

RE: Mit neuem Mut
Wie schon gesagt, sind meine Kenntnisse und Erfahrungen mit numerischen Verfahren gering, weshalb ich dazu wenig sagen kann. Mein Wissen ist:

Der Aufwand einer numerischen Integration liegt hauptsächlich in der Zahl der Funktionsaufrufe.
Bei einzelnen Integrationen ist der Aufwand in der Praxis belanglos. Die heutigen Rechner machen das schneller als man gucken kann. Ausnahme:Extrem aufwendig zu berechnende Funktionen.
Man geht praktisch nie so vor, dass man aus der gewünschten Genauigkeit mittels einer Fehlerabschätzung die erforderliche Schrittweite berechnet. Stattdessen halbiert man fortlaufend die Schrittweite bis der Unterschied zwischen aufeinanderfolgenden Näherungen unter einer vorzugebenden Schranke liegt. Dabei achtet man darauf, dass schon berechnete Funktionswerte nicht neu berechnet werden müssen.
Bei den adaptiven Verfahren behandelt man das Integral als Differentialgleichung und verwendet die Methoden der Schrittenweitensteuerung für die numerische Lösung von Differentialgleichungen.

27.08.2008, 13:57

tigerbine

Auf diesen Beitrag antworten »

RE: Mit neuem Mut

Zitat:

Bei den adaptiven Verfahren behandelt man das Integral als Differentialgleichung und verwendet die Methoden der Schrittenweitensteuerung für die numerische Lösung von Differentialgleichungen.

Erstaunt2

Also das Skirpt, in dem ich gerade lese sagt: P z.B. Simpson Regel, Q: 1x summ. simpsonregel. Dann

Man startet mit dem Intervall $\begin{eqnarray*} I_i:=[a,b] \end{eqnarray*}$ und berechnet die zugehörigen Näherungen $\begin{eqnarray*} P_i(f) \end{eqnarray*}$ und $\begin{eqnarray*} Q_i(f) \end{eqnarray*}$ mit $\begin{eqnarray*} h_i:=b-a \end{eqnarray*}$
Ist (*) erfüllt, so kann man abbrechen. Ansonsten
wähle man den Intervallmittelpunkt als neuen Punkt und prüfe (*) für die beiden entstehenden Intervale.
Dieses Halbierungsverfahren wird solange fortgesetzt, bis (*) für alle Teilintervalle erfüllt ist.
Sind auf diese Weise m Teilintervalle entstanden, so liefert die Summe $\begin{eqnarray*} \sum_{i=0}^{m-1}Q_i(f) \end{eqnarray*}$ dann die gewünschte Näherung an das Integral I(f).

Dabei ist (*):

$\begin{eqnarray*} |Q_i(f)-P_i(f)| \leq \frac{15h_j\varepsilon}{b-a} \end{eqnarray*}$

LG Wink

Wink

27.08.2008, 15:01

Huggy

Auf diesen Beitrag antworten »

RE: Mit neuem Mut
Auch das im Skript beschriebene Verfahren erscheint mir logisch. Meine 'Weisheit' ist aus:

W: H. Press et al.
Numerical Recipes
The Art of Scientific Computing

Ich zitiere mal aus der Einleitung des Kapitels über die Integration von Funktionen:

---
The evaluation of the integral

$\begin{eqnarray*} I= \int_{a}^{b}~f(x)~dx (4.0.1) \end{eqnarray*}$

is precisely equivalent to solving for I = y(b) the differental equation

$\begin{eqnarray*} \frac{dy}{dx} = f(x) (4.0.2) \end{eqnarray*}$

with the boundary condition

$\begin{eqnarray*} y(a)= 0 (4.0.3) \end{eqnarray*}$

Chapterr 16 of this book deals with the numerical integration of differential equations. In that chapter, much emphasis is given to the concept of 'variable' or adaptive choices of step size. ... If the function that you propose to integrate is sharply concentrated in one or more peaks, or if its shape is not readily characterized by a single length-scale, then it is likely that you should cast the problem in the form (4.02)-(4.03) and use the methods of Chapter 16.

27.08.2008, 15:06

tigerbine

Auf diesen Beitrag antworten »

RE: Mit neuem Mut
Danke. Mit Differentialgleichungen kenne ich mich nun gar nicht aus. Mein Kurs "Differentialgleichungen für Dummys" liegt schon zu lange her. Das Thema steht zwar auch auf meiner Liste der zu lesenden Mathematischen Themen, aber das kann noch was dauern. Lesen2

Lesen2

Für ein Beispiel werde ich dann mal "mein" oberes Verfahren anschaulich darstellen. Mal sehen, wie lange das dann im Vergleich braucht.

Aber für die Besucher des Boards ist dein Buchhinweis ja schon einmal hilfreich Wink

Wink

29.08.2008, 14:37

tigerbine

Auf diesen Beitrag antworten »

Bite überprüfen
So, nachdem diese Funktion und ich nicht die besten Freunde sind, vielleicht kann es ja mal jemand nachrechnen. Danke. Wink

Wink

Zitat:

Ziel ist die adaptive Berechnung des Integrals. Beginnen wir mit der Bestimmung des ersten Teilintervalls, also [-1,?]. Zunächst einmal ein paar Vergleichswerte:

$\begin{eqnarray*} \int_{-1}^{1}~\frac{1}{10^{-4}+x^2}~dx = [100 \cdot \arctan(100x)]_{-1}^{+1} \approx 312.1593 \end{eqnarray*}$

$\begin{eqnarray*} \int_{-1}^{0}~\frac{1}{10^{-4}+x^2}~dx = [100 \cdot \arctan(100x)]_{-1}^{0} \approx 156.0797 \end{eqnarray*}$

$\begin{eqnarray*} \int_{-1}^{-0.5}~\frac{1}{10^{-4}+x^2}~dx = [100 \cdot \arctan(100x)]_{-1}^{-0.5} \approx 0.9998 \end{eqnarray*}$

1. Durchlauf

$\begin{eqnarray*} h_0 = 1 - (-1) = 2 \end{eqnarray*}$

$\begin{eqnarray*} P_0(f) = \frac{2}{6} \cdot \{f(-1) + 4 f(0) + f(1)\} \approx 13333.9999 \end{eqnarray*}$

$\begin{eqnarray*} Q_0(f) = \frac{2}{12} \cdot \{f(-1) + 4 f(-0.5) + 2 f(0) + 4f(0.5)+ f(1)\} \approx 3338.9978 \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow |Q_0(f)-P_0(f)| = 9995.0021 > \frac{15 \cdot 2 \cdot 0.1}{2} = 1.5 \end{eqnarray*}$

2. Durchlauf

$\begin{eqnarray*} P_1(f) = \frac{1}{6} \cdot \{f(-1) + 4 f(-0.5) + f(0)\} \approx 1669.4989 \end{eqnarray*}$

$\begin{eqnarray*} Q_1(f) = \frac{1}{12} \cdot \{f(-1) + 4 f(-0.75) +2 f(-0.5) + 4f(-0.25)+ f(0)\} \approx 840.0004 \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow |Q_1(f)-P_1(f)| = 829.4986 > \frac{15 \cdot 1 \cdot 0.1}{2} = 0.75 \end{eqnarray*}$

3. Durchlauf

$\begin{eqnarray*} P_2(f) = \frac{0.5}{6} \cdot \{f(-1) + 4 f(-0.75) + f(-0.5)\} \approx 1.0090 \end{eqnarray*}$

$\begin{eqnarray*} Q_2(f) = \frac{0.5}{12} \cdot \{f(-1) + 4 f(-0.75) +2 f(-0.5) + 4f(-0.25)+ f(0)\} \approx 1.0006 \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow |Q_1(f)-P_1(f)| = 0.0084 < \frac{15 \cdot 0.5 \cdot 0.1}{2} = 0.375 \end{eqnarray*}$

D.h. nach 3 Durchläufen ist für das Intervall [-1,-0.5] die geforderte Genauigkeit erreicht.

29.08.2008, 16:53

Huggy

Auf diesen Beitrag antworten »

RE: Bite überprüfen
Das stimmt!

29.08.2008, 17:04

tigerbine

Auf diesen Beitrag antworten »

RE: Bite überprüfen
merci Wink

Wink

02.09.2008, 11:37

tigerbine

Auf diesen Beitrag antworten »

RE: Mit neuem Mut

Zitat:

Original von tigerbine

Dieses Halbierungsverfahren wird solange fortgesetzt, bis (*) für alle Teilintervalle erfüllt ist.:

Wie setzt man so was denn in einem Programm um? Also zunächst hat man ja nur ein Intervall. Ok, test. Wenn der nicht bestanden wird hat man 2 Intervalle. Prüft man diese nun "parallel" oder erst das "linke" und dann solange weiter das "linke" bis es passt und setzt als neues Startintervall, was was von[a,b] nun noch über ist?

Wink

Wink

02.09.2008, 12:27

Huggy

Auf diesen Beitrag antworten »

RE: Mit neuem Mut

Zitat:

Original von tigerbine

Zitat:

Original von tigerbine

Dieses Halbierungsverfahren wird solange fortgesetzt, bis (*) für alle Teilintervalle erfüllt ist.:

Wie setzt man so was denn in einem Programm um? Also zunächst hat man ja nur ein Intervall. Ok, test. Wenn der nicht bestanden wird hat man 2 Intervalle. Prüft man diese nun "parallel" oder erst das "linke" und dann solange weiter das "linke" bis es passt und setzt als neues Startintervall, was was von[a,b] nun noch über ist?

Wink

Wink

Ich könnte mir folgendes vorstellen: Bei der Halbierung eines Intervalls entsteht zwei Teilintervalle, ein linkes und ein rechtes. Man führt nun für die Intervalle einen Bezeichner LR = links oder rechts mit. Für das aktuell geprüfte Intervall gilt also LR = links oder LR = rechts.

Nach der Prüfung des aktuellen Intervalls entscheidet das Programm so:

Falls Prüfung nicht erfüllt, LR = egal
Halbiere aktuelles Intervall
Gehe zum linken Teilintervall
Gib diesem LR = links

Falls Prüfung erfüllt und LR = links
Gehe zum rechten Teilintervall der aktuellen Teilungsstufe
Dieses hat linke Grenze = rechte Grenze aktuelles Intervall
Breite = Breite aktuelles Intervall
Gib diesem LR = rechts

Falls Prüfung erfüllt und LR = rechts
Gehe zum rechten Teilintervall der vorigen Teilungsstufe
Dieses hat linke Grenze = rechte Grenze aktuelles Intervall
Breite = doppelte Breite aktuelles Intervall
Gib diesem LR = rechts

Auf diese Weise braucht man nur die Abmessungen des aktuellen Intervalls mitzuführen.

12.09.2008, 01:19

tigerbine

Auf diesen Beitrag antworten »

RE: Mit neuem Mut
So, ich habe mal versucht matlab zu erklären, was ich möchte. Augenzwinkern

Augenzwinkern

Vielleicht kann jemand ja mal die Zahlen checken. Die Aufgabe ist immer von oben. m_i gibt dabei den Teildurchlauf an, der zum Erfolg führt, dabei wird mit 0 angefangen zu zählen. Das erste Intervall brauchte also 3 Durchläufe und auf dem Intervall [-1,0.5] haben wir ein Teilnäherung des Teilintegrals in der geforderten Genauigkeit. Dann geht das Spiel auf dem Intervall [-0.5,1] weiter.

Danke,
tigerbine

i Nummer des Teilintervalls am Ende.
Q_i: Quadraturergebnis auf dem Teilintervall
QS: Summer der Q_i

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:

I_Matlab=3.121593e+002 
 
 i      [x_i,x_i+1]                  Q_i                  QS              m_i 
--------------------------------------------------------------------------------------
 0      [-1.000000,-0.500000]        1.000600e+000        1.000600e+000      2
 1      [-0.500000,-0.312500]        1.199355e+000        2.199955e+000      3
 2      [-0.312500,-0.148438]        3.531779e+000        5.731734e+000      3
 3      [-0.148438,-0.076660]        6.248594e+000        1.198033e+001      4
 4      [-0.076660,-0.059837]        3.587635e+000        1.556796e+001      6
 5      [-0.059837,-0.043277]        6.149413e+000        2.171738e+001      6
 6      [-0.043277,-0.035127]        5.026412e+000        2.674379e+001      7
 7      [-0.035127,-0.027040]        7.688005e+000        3.443179e+001      7
 8      [-0.027040,-0.019016]        1.299049e+001        4.742228e+001      7
 9      [-0.019016,-0.011055]        2.512028e+001        7.254256e+001      7
10      [-0.011055,-0.007106]        2.176855e+001        9.431111e+001      8
11      [-0.007106,-0.003172]        3.106523e+001        1.253763e+002      8
12      [-0.003172,-0.001212]        1.864853e+001        1.440249e+002      9
13      [-0.001212,+0.000743]        1.948243e+001        1.635073e+002      9
14      [+0.000743,+0.004647]        3.607910e+001        1.995864e+002      8
15      [+0.004647,+0.008535]        2.715263e+001        2.267390e+002      8
16      [+0.008535,+0.012408]        1.859288e+001        2.453319e+002      8
17      [+0.012408,+0.020123]        2.171687e+001        2.670488e+002      7
18      [+0.020123,+0.027778]        1.156499e+001        2.786138e+002      7
19      [+0.027778,+0.042969]        1.169016e+001        2.903039e+002      6
20      [+0.042969,+0.072877]        9.230552e+000        2.995345e+002      5
21      [+0.072877,+0.130822]        6.009690e+000        3.055442e+002      4
22      [+0.130822,+0.348116]        4.776698e+000        3.103209e+002      2
23      [+0.348116,+1.000000]        1.882952e+000        3.122038e+002      0
 
Fehler = 0.044491

13.09.2008, 13:16

tigerbine

Auf diesen Beitrag antworten »

RE: Mit neuem Mut
Tränen

Tränen

Keiner da, der ein paar Werte überprüfen kann?

13.09.2008, 15:32

Huggy

Auf diesen Beitrag antworten »

RE: Mit neuem Mut
Ich habe etwas anderes gemacht, nämlich die Schrittweitensteuerung nach meiner obigen Idee. Es ergeben sich geringfügig mehr Intervalle als bei dir, dafür ist die Iterationstiefe deutlich geringer. Der Gesamtaufwand für das Programm reduziert sich merklich.

[Attach]8602[/Attach]

Mit Matlab würde ich auch gern arbeiten. Aber wie kommt man da ran, wenn man weder an der Uni noch an der Schule ist?

13.09.2008, 15:53

tigerbine

Auf diesen Beitrag antworten »

RE: Mit neuem Mut
Du könntest alternative Octave nehmen. Wie man sonst günstig rankommt, keine Idee.
Freeware-Programme

Ich versuche mal, meine Iterationstiefe zu reduzieren, aber ich bin schon froh, dass es so nun läuft. Big Laugh

Big Laugh

13.09.2008, 21:08

tigerbine

Auf diesen Beitrag antworten »

RE: Mit neuem Mut
Ich weiß nun nicht, wie ich dein "LR=links" oder "LR=rechts" bei mir umsetzten könnte. Nimmt man aber die letzte erfolgreiche Maschenweite h als Maßstab, und verdoppelt als neuen Ansatz, anstatt bisher einfach für das Restintervallsl [a+h,b] wieder von vorne anzufangen, so sieht es mit der Rekursionstiefe schon was besser aus.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:

 i      [x_i,x_i+1]                  Q_i                  QS              m_i 
--------------------------------------------------------------------------------------
 0      [-1.000000,-0.500000]        1.000600e+000        1.000600e+000      2
 1      [-0.500000,-0.250000]        1.999794e+000        3.000394e+000      2
 2      [-0.250000,-0.125000]        3.988376e+000        6.988771e+000      2
 3      [-0.125000,-0.093750]        2.643535e+000        9.632306e+000      3
 4      [-0.093750,-0.062500]        5.239414e+000        1.487172e+001      1
 5      [-0.062500,-0.046875]        5.152812e+000        2.002453e+001      2
 6      [-0.046875,-0.031250]        9.952541e+000        2.997707e+001      1
 7      [-0.031250,-0.023438]        9.357928e+000        3.933500e+001      2
 8      [-0.023438,-0.015625]        1.660337e+001        5.593837e+001      1
 9      [-0.015625,-0.011719]        1.371128e+001        6.964966e+001      2
10      [-0.011719,-0.007813]        2.011666e+001        8.976631e+001      1
11      [-0.007813,-0.003906]        2.908028e+001        1.188466e+002      1
12      [-0.003906,-0.001953]        1.795142e+001        1.367980e+002      2
13      [-0.001953,+0.000000]        1.928844e+001        1.560864e+002      1
14      [+0.000000,+0.001953]        1.928844e+001        1.753749e+002      1
15      [+0.001953,+0.005859]        3.371303e+001        2.090879e+002      0
16      [+0.005859,+0.009766]        2.435244e+001        2.334404e+002      1
17      [+0.009766,+0.017578]        2.800233e+001        2.614427e+002      0
18      [+0.017578,+0.025391]        1.420411e+001        2.756468e+002      1
19      [+0.025391,+0.033203]        8.265489e+000        2.839123e+002      1
20      [+0.033203,+0.048828]        9.053302e+000        2.929656e+002      0
21      [+0.048828,+0.080078]        7.778394e+000        3.007440e+002      0
22      [+0.080078,+0.142578]        5.423128e+000        3.061671e+002      0
23      [+0.142578,+0.267578]        3.268479e+000        3.094356e+002      0
24      [+0.267578,+0.517578]        1.804851e+000        3.112404e+002      0
25      [+0.517578,+1.000000]        9.324854e-001        3.121729e+002      0
 
Fehler = 0.013592

14.09.2008, 09:59

Huggy

Auf diesen Beitrag antworten »

RE: Mit neuem Mut
Das unterscheidet sich ja nicht mehr stark von meinen Iterationstiefen. Fragt sich also, ob sich zusätzlicher Aufwand lohnt. Ich habe die LR-Regel ziemlich wörtlich mit 'if-Anweisungen' umgesetzt.

14.09.2008, 11:52

tigerbine

Auf diesen Beitrag antworten »

RE: Mit neuem Mut
Ich denke ich lasse es nun erst einmal so. Das Programm soll ja nur die Idee darstellen. Augenzwinkern

Augenzwinkern

Ich versuche nun mal Romberg umzusetzen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »