[WS] Numerische Integration - Theorie

Neue Frage »

31.03.2007, 00:18	tigerbine	Auf diesen Beitrag antworten »
[WS] Numerische Integration - Theorie Gliederung Numerische Integration 1a. Ordnung von Quadraturformeln Interpolatorische Quadraturformeln & Integrationsfehler 2a. Konstruktion 2b. Spezialfall: zur Intervallmitte symmetrische Knoten (ungerade) Newton-Cotes-Formeln - äquidistante Stützstellen 3a. Abgeschlossene Newton-Cotes-Formeln 3a. Fehlerabschätzung abgeschlossene NC-Formeln 3b. Offene Newton-Cotes-Formeln 3b. Fehlerabschätzung der offenen NC-Formeln 3c. Bemerkungen zu den NC-Formeln Summierte Quadraturformeln 4a. Summierte Mittelpunktsregel 4b. SummierteTrapezregel 4c. Summierte Simpsonregel Konvergenz von Quadraturformeln 5a. Korollare Extrapolation Adaptive Verfahren Maximale Ordnung von Quadraturformeln Gaußsche Quadraturformeln 9a. Orthogonale Polynome 1: Wann steht ein Polynom senkrecht auf "allen anderen" Polynomen? 9b. Orthogonale Polynome 2: Wahl der Knoten als deren Nullstellen 9c. Berechnung der Orthogonalen Polynome 9d. Golub & Welsch - Berechnung der Knoten und Gewichte 9e. Konvergenz von Quadraturformeln 9f. Quadraturfehler
31.03.2007, 00:26	tigerbine	Auf diesen Beitrag antworten »
1. Numerische Integration Gesucht sind diesem Workshop Wege zur numerischen Bestimmung des bestimmten Integrals $\begin{eqnarray} I(f):=\int_a^b~f(x)~dx \end{eqnarray}$ Dabei sollen zur Approximation von $\begin{eqnarray} I(f) \end{eqnarray}$ Quadraturformeln verwendet werden. Diese haben die allgemeine Gestalt: $\begin{eqnarray} I_n(f):=\sum_{j=0}^{n}~\alpha_j\cdot f(x_j) \end{eqnarray}$ Dabei bezeichnen $\begin{eqnarray} a\leq x_0 \leq ... \leq x-n \leq b \end{eqnarray}$ die Stützstellen und $\begin{eqnarray} \alpha_j \end{eqnarray}$ die zugehörigen Gewichte. Dabei ist der Name Quadratur historisch bedingt und spielt auf das Integral als Fläche zwischen dem Graphen einer Funktion und der x-Achse an. Eine Motivation der obigen Gestalt von Quadraturformeln ist in der Gestalt des Riemann-Integrals zu sehen. Die Produkte "*Gewicht Funktionswert**" lassen sich als Flächeninhalte von Rechtecken interpretieren. (Anschauliches gibt es im [WS] - Beispiele)
31.03.2007, 00:33	tigerbine	Auf diesen Beitrag antworten »
1a. Ordnung von Quadraturformeln Eine Quadraturformel $\begin{eqnarray} I_n(f) \end{eqnarray}$ hat die Ordnung $\begin{eqnarray} k \in \mathbb N \end{eqnarray}$ , wenn sie alle Polynome $\begin{eqnarray} p \in \Pi_{k-1} \end{eqnarray}$ exakt integriert, d.h. wenn gilt: $\begin{eqnarray} I(p)=I_n(p) \qquad \forall~ p \in \Pi_{k-1} \end{eqnarray}$ Eine Quadraturformel der Ordnung k hat somit auch jede kleinere Ordnung als k. Zur Überprüfung der Ordnung einer Quadraturformel genügt es - wegen der Linearität der Integralfunktion - zu zeigen, dass gilt: $\begin{eqnarray} I_n(p_j)=I(p_j) \qquad j=1,2,...,k \quad \text{für eine Polynombasis }p_1,...,p_k \text{ von } \Pi_{k-1} \end{eqnarray}$ Jedes Polynom p aus dem Vektorraum $\begin{eqnarray} \Pi_{k-1} \end{eqnarray}$ lässt sich als Linearkombination dieser Basispolynome darstellen und es folgt: $\begin{eqnarray} \int_{a}^{b}~p(x)~dx = \int_{a}^{b}~\sum_{j=1}^{k}~a_j\cdot p_j(x)~dx = \sum_{j=1}^{k}~ \int_{a}^{b}~a_j\cdot p_j(x)~dx = \sum_{j=1}^{k}~ a_j\cdot\int_{a}^{b}~ p_j(x)~dx \end{eqnarray}$ Besitzt $\begin{eqnarray} I_n \end{eqnarray}$ die Ordnung $\begin{eqnarray} n+1 \end{eqnarray}$ , so nennt man die Quadraturformel interpolatorisch. Diese Definition bietet uns gleich einen Ansatz, welche Eigenschaften solche Quadraturformeln haben müssen. Es ist sicherlich eine sinnvoll zu fordern, dass zumindest konstante Funktionen exakt integriert werden. Es muss also das Basispolynom $\begin{eqnarray} p_0=1 \end{eqnarray}$ exakt integriert werden. Unmittelbar ergibt sich $\begin{eqnarray} \sum_{j=0}^n~\alpha_j \cdot 1 \stackrel{!} = \int_a^b~1~dx \end{eqnarray}$ Was nichts anderes bedeutet, als das die Summe der Gewichte der Länge des Intervalls entsprechen muss: $\begin{eqnarray} \sum_{j=0}^n~\alpha_j \stackrel{!} = (b-a) \end{eqnarray}$ In einigen Büchern werden die folgenden Betrachtungen auf das Intervall [0,1] eingeschränkt. Dennoch sind die Folgerungen leicht übertragbar auf ein Intervall [a,b]. Beachte hierzu die Substitutionsregel. Mit einer entsprechenden Hilfsfunktion $\begin{eqnarray} \varphi \end{eqnarray}$ ergibt sich: $\begin{eqnarray} \int_{\varphi(0)}^{\varphi(1)}~f(x)~dx = \int_{0}^{1}~(f \circ \varphi(t)) \cdot \varphi'(t)~dt \end{eqnarray}$ $\begin{eqnarray} \varphi:~[0,1] \to [a,b],\quad \varphi(t):=a + (b-a)\cdot t \end{eqnarray}$ Und wir erhalten schließlich: $\begin{eqnarray} \int_{a}^{b}~f(x)~dx = (b-a) \cdot \int_{0}^{1}~(f \circ \varphi(t)) ~dt \end{eqnarray}$ Gerade bei Tabellen mit Gewichten zu Quadraturformeln sollte man dies stets im Hinterkopf haben.
31.03.2007, 01:21	tigerbine	Auf diesen Beitrag antworten »
2a. Interpolatorische Quadraturformeln Bildet man zu den paarweise verschiedenen Stützstellen (Knoten) $\begin{eqnarray} x_j \end{eqnarray}$ das Lagrangesche Interpolationspolynom (2a), so erhält man als Quadraturformel: $\begin{eqnarray} I_n(f) &&=\int_a^b~p_n(x)~dx=\int_a^b~\Bigl(\sum_{j=0}^n~l_j(x)\cdot y_j \Bigr) = \sum_{j=0}^n \Bigl(f(x_j) \cdot \int_a^b~l_j(x)~dx \Bigr) = \\&& =\sum_{j=0}^n~\alpha_j \cdot f(x_j) \quad \text{mit } \quad \alpha_j:=\int_a^b~l_j(x) dx \end{eqnarray}$ Die so konstruierten Formeln haben die Ordnung (n+1), sind also interpolatorisch (und daher der Name). Beweis: Ist $\begin{eqnarray} f \in \Pi_n \end{eqnarray}$ , so stimmt f mit dem an den (n+1) Knoten interpolierenden Polynom p überein. Also gilt: $\begin{eqnarray} I_n(f)=I(p) = I(f) \end{eqnarray}$ Alternativ könnte man auch über die Integration des Interpolationsfehlers argumentieren: $\begin{eqnarray} \|I(f)-I_n(f)\| &&= \|I(f) - I(p_n)\|\\\\&&= \|I(f-p_n)\| \\ \\&& = \|\int_a^b~\frac{f^{(n+1)}(\xi_x)}{(n+1)!} \cdot \prod_{j=0}^n (x-x_j)~dx\| \\&& \leq \frac{1}{(n+1)!}\cdot \max_{x\in[a,b]}~\|f^{(n+1)}(x)\|\cdot \int_a^b~\|\prod_{j=0}^n (x-x_j)\|~dx \end{eqnarray}$ Da wir hier - im Gegensatz zur Grenzwertbetrachtung bei der Polynominterpolation - die Abschätzung für festes n betrachten, sind der erste und letzte Faktor irgendwelche reelle Zahlen. Ist nun $\begin{eqnarray} f \in \Pi_n \end{eqnarray}$ , so gilt $\begin{eqnarray} f^{(n+1)}(x)=0 \end{eqnarray}$ und damit gilt folgt die Behauptung. Ferner haben wir eine Abschätzung für den Integrationsfehler erhalten. Quadraturfehler Wem die Abschätzung nicht reicht, kann natürlich auch den exakten Fehler bestimmen. Dazu soll die Formel zunächst einmal auf eine andere Gestalt gebracht werden, um die in den meisten Fällen tabellierte Form zu erläutern. Wir gehen in zwei Schritten vor. (1) Verallgemeinerter erster Mittelwertsatz der Integralrechnung - Teil 2 (Bronstein) $\begin{eqnarray} f \in C([a,b]) \end{eqnarray}$ $\begin{eqnarray} g(x) \geq 0 \text{ oder } g(x) \leq 0~\forall x \in [a,b] \end{eqnarray}$ $\begin{eqnarray} \Rightarrow \end{eqnarray}$ $\begin{eqnarray} \int_a^b~f(x)g(x)~dx = f(\xi) \cdot \int_a^b g(x)~dx,~\xi \in [a,b] \end{eqnarray}$ (2) Lineare Transformation $\begin{eqnarray} \int_{a}^{b}~\|w(x)\|~dx &&= \int_{a}^{b}~\|\prod_{j=0}^n~(x-x_j)\|~dx = \int_{a}^{b}\| \prod_{j=0}^n~\Bigl(x- (a+j \cdot \frac{(b-a)}{n}) \Bigr)\|~dx \\&& =\int_{a}^{b}\| \prod_{j=0}^n~\Bigl(x- (a+\frac{j}{n}\cdot (b-a)) \Bigr)\|~dx \end{eqnarray}$ Dazu verwendet man wieder die Substitionsregel und erhält: $\begin{eqnarray} \int_{a}^{b} \prod_{j=0}^n~\Bigl(x- (a+\frac{j}{n}\cdot (b-a)) \Bigr)~dx &&=(b-a) \cdot \int_{0}^{1}\prod_{j=0}^n~\Bigl(a+t\cdot (b-a)- (a+\frac{j}{n}\cdot (b-a)) \Bigr)~dt \\&& = (b-a) \cdot \int_{0}^{1}\prod_{j=0}^n~\Bigl(t\cdot (b-a)- \frac{j}{n}\cdot (b-a)) \Bigr)~dt \\\\&& = (b-a)^{n+2} \cdot \int_{0}^{1}\prod_{j=0}^n~\Bigl(t- \frac{j}{n} \Bigr)~dt \end{eqnarray}$ Somit erklären sich die Potenzen von (b-a) in den Fehlern, das Integral liefert einen Teil des Faktors. Man kommt um eine Berechnung nicht herum.
31.03.2007, 01:49	tigerbine	Auf diesen Beitrag antworten »
2b. Spezialfall: zur Intervallmitte symmetrische Knoten Für gerades n (also n=2m ) und (damit 2m+1 => ungerade) zur Intervallmitte symmetrischen (SIM) Stützstellen (Knoten), hat die zugehörige interpolatorische Quadraturformel sogar die Ordnung 2m+2. Man kann dies z.B. durch die exakte und numerische Integration der Testfunktion $\begin{eqnarray} f(x)=\Bigl( x-\frac{a+b}{2}\Bigr)^{2m+1} \end{eqnarray}$ zeigen. Für einen anderen Weg braucht man die folgenden Hilfsresultate. ************************************************************ Hilfsresultat 1:** $\begin{eqnarray} \int_a^b~\prod_{j=0}^{2m}(x-x_j)~dx = 0 \end{eqnarray}$ Beweis: Für die SIM-Knoten gilt: $\begin{eqnarray} b - x_{2m-j} \stackrel{()}= x_j-a \qquad \forall j=0,...,2m \end{eqnarray}$ . Somit gilt für das Knotenpolynom $\begin{eqnarray} w(x)=\prod_{j=0}^{2m}~(x-x_j) \end{eqnarray}$ : $\begin{eqnarray} w(a+b-x) &&=\prod_{j=0}^{2m}~(a+b-x-x_j) = \prod_{j=0}^{2m}~\Bigl(b-(x_j-a)-x\Bigr) \stackrel{()}= \prod_{j=0}^{2m}~(-x +x_{2m-j}) \\&&= (-1)^{2m+1} \prod_{j=0}^{2m}~(x-x_{2m-j})= - \prod_{j=0}^{2m}~(x-x_{2m-j}) \stackrel{\text{Umnummerierung}}= - \prod_{j=0}^{2m}~(x-x_j) = \\&& = -w(x) \end{eqnarray}$ Substituiert man nun x = a+b-y = g(y), so erhält man nach der Substitutionsregel für Integrale: $\begin{eqnarray} g^{-1}(y) = a+b-y \text{ und } g'(y) = -1 \end{eqnarray}$ . Daher folgt: $\begin{eqnarray} \int_a^b~w(x)~dx &&= \int_{g^{-1}(a)}^{g^{-1}(b)}~w\Bigl( g(y)\Bigr) \cdot g'(y)~dy = - \int_b^a~w(a+b-y)~dy = \\ && = \int_a^b~w(a+b-y)~dy = \\ &&= - \int_a^b~w(y)~dy \end{eqnarray}$ $\begin{eqnarray} \Rightarrow \int_a^b~w(x)~dx=0 \end{eqnarray}$ ********************************************************* Hilfsresultat 2:** Sei nun $\begin{eqnarray} x_{2m+1} \end{eqnarray}$ ein weiterer Knoten und $\begin{eqnarray} p_{2m+j},~j = 0,1 \end{eqnarray}$ das die Daten $\begin{eqnarray} (x_0,~f(x_0)),...,(x_{2m+j},~f(x_{2m+j})) \end{eqnarray}$ interpolierende Polynom, so folgt: $\begin{eqnarray} \int_a^b~p_{2m+1}(x)~dx = \int_a^b~p_{2m}(x)~dx \end{eqnarray}$ Beweis: Die Newton -Form von $\begin{eqnarray} p_{2m+1} \end{eqnarray}$ lautet: $\begin{eqnarray} p_{2m+1}(x) = p_{2m}+f_{2m+1}\cdot \prod_{j=0}^{2m}~(x-x_j) \end{eqnarray}$ Mit dem Hilfsresultat 1 folgt dann: $\begin{eqnarray} \int_a^b~p_{2m+1}(x)~dx = \int_a^b~p_{2m}(x)~dx + f_{2m+1}\cdot \int_a^b~\prod_{j=0}^{2m}~(x-x_j)~dx = \int_a^b~p_{2m}(x)~dx \end{eqnarray}$ ********************************************************* Beweis:** So, kommen wir zu obiger Behauptung zurück. Welche Ordnung hat die Quadraturformel $\begin{eqnarray} I_{2m} \end{eqnarray}$ mit SIM-Stützstellen? $\begin{eqnarray} \|I(f)-I_{2m}(f)\| &&= \|I(f)-I(p_{2m})\| \stackrel{\mathrm{HR ~2}}= \|I(f)-I(p_{2m+1})\| \\ && \leq \frac{1}{(2m+2)!} \cdot \max_{x \in [a,b]}~\|f^{(2m+2)}(x)\| \cdot \int_a^b~\|\prod_{j=0}^{2m+1}(x-x_j)\|~dx \end{eqnarray}$ Wegen $\begin{eqnarray} f^{2m+2}(x)=0 \quad \forall f \in \Pi_{2m+1} \end{eqnarray}$ und somit folgt die Behauptung.
31.03.2007, 22:37	tigerbine	Auf diesen Beitrag antworten »
3. Newton-Cotes-Formeln: äquidistante Stützstellen Einen Spezialfall der Interpolatorischen Quadraturformeln sind die Newton-Cotes-Formeln. Dabei wurden die für das Interpolationspolynom benötigten Stützstellen (Knoten) äquidistant gewählt.
Anzeige

31.03.2007, 23:22	tigerbine	Auf diesen Beitrag antworten »
3a. Abgeschlossene Newton-Cotes-Formeln Dabei gilt für die Stützstellen: $\begin{eqnarray} x_j=a+j\cdot h \qquad \forall j = 0,...,n \qquad \text{und } \quad h:=\frac{b-a}{n} \end{eqnarray}$ Für die Gewichte $\begin{eqnarray} \alpha_j \end{eqnarray}$ gilt dann: $\begin{eqnarray} \alpha_j=\int_a^b~l_j(x)~dx \stackrel{\mathrm{Beweis}}= (b-a) \cdot \int_0^1~\prod_{k=0 \atop k \neq j}^n \frac{(nt-k)}{(j-k)}~dt = (b-a) \cdot \alpha_j^{(1)} \end{eqnarray}$ Beweis: Wieder verwendet man die Substitutionsregel der Integralrechnung (vergleiche 1a). Das liefert: $\begin{eqnarray} \int_{a}^{b}~l_j(x)~dx &&\stackrel{\text{Subst.}}=(b-a) \cdot \int_{0}^{1}~l_j(\varphi(t))~dt \\ && = (b-a)\cdot \int_{0}^{1}~\prod_{k=0 \atop k \neq j}^{n}~\frac{[a+(b-a)\cdot t]-[a+\frac{(b-a)}{n}\cdot k]}{[a+\frac{(b-a)}{n}\cdot j]-[a+\frac{(b-a)}{n}\cdot k]}~dt \\&& = (b-a) \cdot \int_{0}^{1}~\prod_{k=0 \atop k \neq j}^{n}~\frac{(nt-k)}{(j-k)}~dt \end{eqnarray}$ Weitere Eigenschaften: $\begin{eqnarray} \sum_{j=0}^n~\alpha_j^{(1)}=1 \quad \text{und} \quad \sum_{j=0}^n~\alpha_j=b-a \end{eqnarray}$ Beweis: Da die Formeln interpolatorisch sind, sind sie insbesondere exakt auf $\begin{eqnarray} \Pi_0 \end{eqnarray}$ . $\begin{eqnarray} \alpha_j \text{ und } \alpha_j^{(1)} \end{eqnarray}$ sind symmetrisch, d.h. $\begin{eqnarray} \alpha_j = \alpha_{n-j} \text{ und } \alpha_j^{(1)} = \alpha_{n-j}^{(1)} \end{eqnarray}$ Beweis: $\begin{eqnarray} \alpha_{n-j}&&=(b-a) \cdot \int_{0}^{1}~\prod_{k=0 \atop k \neq {n-j}}^{n}~\frac{nt-k}{(n-j) -k}~dt \\&& \text{Substutition } i:=n-k, \text{d.h. Reihenfolge umdrehen} \\&& = (b-a) \cdot \int_{0}^{1}~\prod_{i=0 \atop i \neq {j}}^{n}~\frac{nt-(n-i)}{(n-j) -(n-i)}~dt \\&& = (b-a) \cdot \int_{0}^{1}~\prod_{i=0 \atop i \neq {j}}^{n}~\frac{n(1-t)-i}{j-i}~dt \\&& \hat{t} :=1-t, \text{ Substitutionsregel und Vertauschen der Integrationsgrenzen} \\&& =(b-a) \cdot \int_{0}^{1}~\prod_{i=0 \atop i \neq {j}}^{n}~\frac{n\hat{t}-i}{j-i}~d\hat{t} \\&& = \alpha_{j} \end{eqnarray}$ Beispiele: Gewichte berechnet für das Intervall [0,1] $\begin{eqnarray} \begin{array} {c\| c c c c c l } n & \alpha_0^{(1)} & \alpha_1^{(1)} & \alpha_2^{(1)} & \alpha_3^{(1)} & & \text{Name} \\ \hline \\ 1 & \frac{1}{2} & \frac{1}{2} & & & &\text{Trapezregel}\\ \\ \hline \\2 & \frac{1}{6} & \frac{4}{6} & \frac{1}{6} & & & \text{Simpson-Regel /Keplersche Faßregel}\\ \\ \hline \\ 3 & \frac{1}{8} & \frac{3}{8} & \frac{3}{8} & \frac{1}{8} & & \text{Pulccherrima - 3/8-Regel} \\ \\ \end{array} \end{eqnarray}$
10.04.2007, 10:09	tigerbine	Auf diesen Beitrag antworten »
Fehlerabschätzung abgeschlossene NC-Formeln Zur Berechnung ziehen wir obige Abschätzung heran. Bei geradem n liegen SIM-Knoten vor. Hier die Ergebnisse in der Übersicht: $\begin{eqnarray} n=1:\qquad \|I(f)-I_1(f)\|\leq \frac{(b-a)^3}{12}\cdot \max_{x \in[a,b]}~\|f^{(2)}(x)\| \end{eqnarray}$ $\begin{eqnarray} n=2:\qquad \|I(f)-I_2(f)\|\leq \frac{(b-a)^5}{2880}\cdot \max_{x \in[a,b]}~\|f^{(4)}(x)\| \end{eqnarray}$ $\begin{eqnarray} n=3:\qquad \|I(f)-I_3(f)\|\leq \frac{(b-a)^5}{6480}\cdot \max_{x \in[a,b]}~\|f^{(4)}(x)\| \end{eqnarray}$ Man erkennt also, dass es stark auf die Funktion f ankommt, wie gut die Verfahren zur Integration geeignet sind.
10.04.2007, 10:22	tigerbine	Auf diesen Beitrag antworten »
3b. Offene Newton-Cotes-Formeln Dabei gilt für die Stützstellen: $\begin{eqnarray} x_j=a+(j+1)\cdot h \qquad \forall j = 0,...,n \qquad \text{und } \quad h:=\frac{b-a}{n+2} \end{eqnarray}$ Für die Gewichte $\begin{eqnarray} \alpha_j \end{eqnarray}$ gilt dann: $\begin{eqnarray} \alpha_j=\int_a^b~l_j(x)~dx \stackrel{\mathrm{Beweis}}= (b-a) \cdot \int_{0}^{1}~\prod_{k=0 \atop k \neq j}^n \frac{(n+2)t-(k+1)}{j-k}~dt = (b-a) \cdot \alpha_j^{(1)} \end{eqnarray}$ Beweis: Wieder verwendet man die Substitutionsregel der Integralrechnung. Beweisidee ist analog zu den abgeschlossenen Formeln. Weitere Eigenschaften: $\begin{eqnarray} \sum_{j=0}^n~\alpha_j^{(1)}=1 \quad \text{und} \quad \sum_{j=0}^n~\alpha_j=b-a \end{eqnarray}$ Beweis: Da die Formeln interpolatorisch sind, sind sie insbesondere exakt auf $\begin{eqnarray} \Pi_0 \end{eqnarray}$ . $\begin{eqnarray} \alpha_j \text{ und } \alpha_j^{(n)} \end{eqnarray}$ sind symmetrisch, d.h. $\begin{eqnarray} \alpha_j = \alpha_{n-j} \text{ und } \alpha_j^{(n)} = \alpha_{n-j}^{(n)} \end{eqnarray}$ Beweis: Analoge Beweisstruktur wie bei den abgeschlossenen Formeln Beispiele: Berechnet für das Intervall [0,1] $\begin{eqnarray} \begin{array} {c\| c c c c c l } n & \alpha_0^{(1)} & \alpha_1^{(1)} & \alpha_2^{(1)} & \alpha_3^{(1)} & & \text{Name} \\ \hline \\ 0 & 1 & & & & &\text{Mittelpunktsregel}\\ \\ \hline \\1 & \frac{1}{2} & \frac{1}{2} & & & & \\ \\ \hline \\ 2 & \frac{2}{3} & -\frac{1}{3} & \frac{2}{3} & & & \\ \\ \end{array} \end{eqnarray}$
10.04.2007, 10:26	tigerbine	Auf diesen Beitrag antworten »
Fehlerabschätzung der offenen NC-Formeln zur Berechnung ziehen wir obige Abschätzung heran. $\begin{eqnarray} n=0:\qquad \|I(f)-I_0(f)\|\leq \frac{(b-a)^3}{24}\cdot \max_{x \in[a,b]}~\|f^{(2)}(x)\| \end{eqnarray}$ $\begin{eqnarray} n=1:\qquad \|I(f)-I_1(f)\|\leq \frac{(b-a)^3}{108}\cdot \max_{x \in[a,b]}~\|f^{(2)}(x)\| \end{eqnarray}$ $\begin{eqnarray} n=2:\qquad \|I(f)-I_2(f)\|\leq \frac{(b-a)^5}{23.040}\cdot \max_{x \in[a,b]}~\|f^{(4)}(x)\| \end{eqnarray}$ Auch hier spielt die Gestalt von f wieder eine entscheidende Rolle in der Fehlerabschätzung.
10.04.2007, 10:31	tigerbine	Auf diesen Beitrag antworten »
3c. Bemerkungen zu den NC-Formeln Bei den abgeschlossenen treten ab n=7 und bei den offenen ab n=2 negative Gewichte auf. Dadurch erhöht sich die Fehleranfälligkeit dieser Formeln (Auslöschung). Außerdem ist i.a. keine Konvergenz $\begin{eqnarray} I_n(f) \rightarrow I(f)\quad (n \to \infty) \end{eqnarray}$ zu erwarten, da für die Lagrange-Interpolation nicht generell gilt: $\begin{eqnarray} p_n \rightarrow f \quad (n \to \infty) \end{eqnarray}$ Vergleiche hierzu den Workshop Polynominterpolation, wieder liegt das Problem in der geforderten n-fachen Differenzierbarkeit und der Gestalt dieser Ableitung.
10.04.2007, 14:38	tigerbine	Auf diesen Beitrag antworten »
4. Summierte (Zusammengesetzte) Quadraturformeln Ähnlich wie die Argumentation von der Lagrange-Interpolation hin zur Spline-Interpolation führte, gelangt man nun hier zu den Summierten Quadraturformeln. D.h. man zerlegt das Intervall [a,b] in N Teilintervalle der äquidistanten Länge $\begin{eqnarray} h=\frac{b-a}{N} \end{eqnarray}$ . Somit führt das Verfahren für $\begin{eqnarray} n \to \infty~(h \to 0) \end{eqnarray}$ zur Konvergenz, falls die zu integrierende Funktion genügend oft differenzierbar ist (Je nach verwendeter NC-Formel). Das Integral stellt sich nun wie folgt dar: $\begin{eqnarray} I(f)=\int_{J}~f(x)~dx = \sum_{p=1}^{N}~\int_{J_p}~f(x)~dx \end{eqnarray}$ dabei gilt: $\begin{eqnarray} && J=[a,b]\text{ mit Zerlegung } J_1,~J_2,...,J_N \text{ :} \\ \\&&\bigcup_{p=1}^{N}J_P = J \text{ und } J_j \cap J_k \text{ besteht aus max einem Punkt für } j \neq k \end{eqnarray}$ Es soll nun der Fall gleich langer Teilintervalle unter Verwendung derselben Quadraturformel betrachtet werden. Es gilt dann: $\begin{eqnarray} h=\frac{b-a}{N} \end{eqnarray}$ $\begin{eqnarray} J_p=[a+(p-1)\cdot h,~a+p\cdot h] \qquad p=1,...,N \end{eqnarray}$ Für die Fehlerabschätzungen benutzt man die Voraussetzung, dass die entsprechende Ableitung der Funktion stetig ist. Deswegen läßt sich der Zwischenwertsatz anwenden.
12.04.2007, 22:11	tigerbine	Auf diesen Beitrag antworten »
4a. Summierte Mittelpunktsregel $\begin{eqnarray} I^M(f)&&=\sum_{p=1}^{N}~\int_{J_p}p_0(x)~dx =\\ &&=\sum_{p=1}^{N}~I_0^{J_p}(f) =\sum_{p=1}^{N}~h\cdot f(x_p)=\\&&=h \cdot \sum_{p=1}^N~f(x_p) \end{eqnarray}$ $\begin{eqnarray} \text{mit } x_p = a + p\cdot h -\frac{1}{2}\cdot h = a + h\cdot(p-\frac{1}{2}) \end{eqnarray}$ Fehlerabschätzung: $\begin{eqnarray} \|I(f)-I^{M}(f)\| \leq \frac{b-a}{24} \cdot h^2 \cdot \max_{x \in [a,b]}~\|f''(x)\| \end{eqnarray}$ Beweis: Ergibt sich direkt aus der Fehlerabschätzung der Mittelpunktsregel. $\begin{eqnarray} \|I(f)-I^{M}(f)\| = \sum_{p=1}^{N} \|I(f)-I_0(f)\|_{J_p} \leq N \cdot \frac{h^3}{24} \cdot \max_{x \in [a,b]}~\|f''(x)\| =\frac{b-a}{24} \cdot h^2 \cdot \max_{x \in [a,b]}~\|f''(x)\| \end{eqnarray}$
12.04.2007, 22:17	tigerbine	Auf diesen Beitrag antworten »
4b. SummierteTrapezregel $\begin{eqnarray} I^T(f)=\frac{h}{2} \Bigl\{f(a) +2\cdot \sum_{p=1}^{N-1}~f(a+p\cdot h)+f(b) \Bigr\} \end{eqnarray}$ Fehlerabschätzung: $\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}$
12.04.2007, 22:21	tigerbine	Auf diesen Beitrag antworten »
4c. Summierte Simpsonregel $\begin{eqnarray} I^S(f)=\frac{h}{6} \Bigl\{f(a) + 2\cdot \sum_{p=1}^{N-1}~f(a+p\cdot h)+ 4\cdot \sum_{p=1}^{N}~f(a+(2p-1)\frac{h}{2})+f(b) \Bigr\} \end{eqnarray}$ Fehlerabschätzung: $\begin{eqnarray} \|I(f)-I^S(f)\|\leq \frac{(b-a)}{2880}\cdot h^4 \max_{x \in[a,b]}~\|f^{(4)}(x)\| \end{eqnarray}$ Beachte, die Maschenweite ist hier $\begin{eqnarray} \hat h = \frac{h}{2} \end{eqnarray}$
12.04.2007, 23:41	tigerbine	Auf diesen Beitrag antworten »
5. Konvergenz von Quadraturformeln Mit vorherigem Absatz hat man sich bzgl. der Konvergenz von Quadraturformeln also schon einmal dahin verbessert, dass sie für bestimmte Funktionen, z.B. $\begin{eqnarray} f \in C^4 \end{eqnarray}$ für $\begin{eqnarray} I^S \end{eqnarray}$ , konvergieren. Ziel ist es nun ein Kriterium zu formulieren, aus dem folgt, unter welchen Bedingungen eine Quadraturformel für jede stetige Funktion bei wachsender Knotenzahl gegen das Integral konvergiert. Hierzu betrachtet man die Folge von Quadraturformeln: $\begin{eqnarray} \text{(1) } \quad I_n(f) = \sum_{j=0}^n~w_j^{(n)}\cdot f(x_j^{(n)}),\quad n=0,1,2,... \end{eqnarray}$ Dabei gelte die Voraussetzung: $\begin{eqnarray} \text{(2) } \quad I_n(p) \to I(p) \quad \text{für jedes Polynom p von beliebigem Grad} \end{eqnarray}$ Bemerkung: Diese Voraussetzung ist einerseits plausibel und andererseits in vielen konkreten Fällen auch leicht nachprüfbar. Z.B. erfüllen die zusammengesetzte Trapez- und Mittelpunktsregel diese Voraussetzung, da diese Formeln im wesentlichen die numerische Realisierung der Integraldefinition mit Hilfe von Riemann-Summen darstellen. (siehe [WS] - Beispiele) Es gilt dann der folgende Satz: Gibt es eine Konstante c, so dass $\begin{eqnarray} \sum_{j=0}^{n}~\|w_j^{(n)}\| \leq c~\forall n\in \mathbb N_0 \end{eqnarray}$ , dann konvergiert obige Quadraturformel-Folge $\begin{eqnarray} I_n(f) \to I(f) \quad \forall ~f \in C([a,b]) \end{eqnarray}$ . Beweis: Nach einem Satz von Weierstraß gibt gibt es zu vorgegebenem $\begin{eqnarray} \varepsilon > 0 \end{eqnarray}$ zu jedem $\begin{eqnarray} f \in C([a,b]) \end{eqnarray}$ ein Polynom p, so dass gilt: $\begin{eqnarray} \max_{x \in [a,b]}~\|f(x)-p(x)\| \leq \varepsilon \end{eqnarray}$ Wegen der Voraussetzung (2) gibt es zu diesem $\begin{eqnarray} \varepsilon \end{eqnarray}$ ein $\begin{eqnarray} n_0 \end{eqnarray}$ , so dass $\begin{eqnarray} \|I_n(p)-I(p)\| \leq \varepsilon \quad \forall n \geq n_0 \end{eqnarray}$ Daher gilt für alle $\begin{eqnarray} n \geq n_0 \end{eqnarray}$ die Abschätzung: $\begin{eqnarray} \|I_n(f)-I(f)\| && = \|I_n(f-p) + I_n(p) - I(p) + I(p-f)\| \\&&\leq \|I_n(f-p)\|+\|I_n(p)-I(p)\| + \|I(p-f)\| \\&& \leq \varepsilon \cdot \sum_{j=0}^n~\|w_j^{(n)}\|+ \varepsilon +(b-a)\cdot \varepsilon \\&& \leq (c+1+b-a)\cdot \varepsilon \end{eqnarray}$ Also konvergiert $\begin{eqnarray} I_n(f) \to I(f) \end{eqnarray}$ .
13.04.2007, 01:02	tigerbine	Auf diesen Beitrag antworten »
Korollare Korollar 1: Sind die in (1) vorkommenden Gewichte nicht negativ, also $\begin{eqnarray} w_j^{(n)} \geq 0 \quad \forall j = 0,...,n \text{ und }~\forall n \in \mathbb N_0 \end{eqnarray}$ , dann sind die Formeln $\begin{eqnarray} I_n(f) \end{eqnarray}$ konvergent, d.h. vorheriger Satz gilt. Beweis: Wendet man die Voraussetzung (2) für p=1 an, dann gilt: $\begin{eqnarray} \sum_{j=0}^n~\|w_j^{(n)}\|= \sum_{j=0}^n~w_j^{(n)}=I_n(1) \to I(1) = b-a \leq c \qquad \forall n \in \mathbb N_0 \end{eqnarray}$ Somit ist die Voraussetzung des Satzes erfüllt und die Formeln sind konvergent. Bemerkung: Die Newton-Cotes-Formeln erfüllen dieses Korollar i.A. nicht, denn wie man gesehen hat, treten dort schon für recht kleine n negative Gewichte auf (offene ab n=2, abgeschlossene ab n=8). Korollar 2: Für die zusammengesetze Simpson-Regel gilt $\begin{eqnarray} I^S(f) \to I(f) \end{eqnarray}$ für jede stetige Funktion $\begin{eqnarray} f \in C([a,b]) \end{eqnarray}$ . Beweis: Die Gewichte der $\begin{eqnarray} I^S \end{eqnarray}$ sind $\begin{eqnarray} \frac{h}{6},~\frac{h}{3},~\frac{2h}{3} \end{eqnarray}$ , also alle positiv. Die Bedingung (2) ist auch erfüllt, wie man mit der angegebenen Fehlerabschätzung nachprüfen kann. Setzt man dort für f ein Polynom ein, so lautet die rechte Seite: $\begin{eqnarray} const.\cdot h^4 \end{eqnarray}$ . Für wachsende n geht aber h gegen 0. Somit folgt die Behauptung aus Korollar 1.
13.04.2007, 01:11	tigerbine	Auf diesen Beitrag antworten »
6. Extrapolation Im Workshop "Interpolation" haben wir uns mit dem Nachweis der Konvergenz (Spline-Interpolation) zufrieden gegeben. Dabei sei bemerkt, dass zusammengesetzte Trapezregel im Grunde die Integration des interpolierenden linearen Splines darstellt. Da das Verfahren der Richardson-Extrapolation nicht nur zum numerischen Integrieren verwendet werden kann, ist es in einem eigenen Workshop [WS] Extrapolation ausgelagert. Man interessiert sich für den Wert einer Funktion an der Stelle h=0, kann aber z.B. diesen Wert aber nicht explizit berechen. So legt man durch andere Meßpunkte eine Funktion (Interpolationspolynom) und wertet dieses bei 0 aus. Um sinnvolle Ergebnisse zu erhalten, sollten die Meßpunkte eine Nullfolge bilden. Vergleiche hierzu die erwähnte Problematik im [WS] Polynominterpolation-Theorie
13.04.2007, 01:26	tigerbine	Auf diesen Beitrag antworten »
7. Adaptive Verfahren Mit den summierten Quadraturformeln können wir zwar Konvergenz sicherstellen, sofern die entsprechende Ableitung betragsmäßig von oben beschränkt war. Auf die Gestalt der Funktion wurde nicht eingegangen. Dies kann dann zur Notwendigkeit einer sehr kleinen Maschenweite h führen (viele Knoten), um die gewünschte Genauigkeit sicherzustellen. Verdeutlichen wir uns das an einem Beispiel. $\begin{eqnarray} \int_{-1}^{1}~\frac{1}{10^{-4}+x^2}~dx \end{eqnarray}$ Wollten wir das Integral nun mit der summierten Simpson-Regel approximieren, so hätten wir es mit der Fehlerabschätzung zu tun: $\begin{eqnarray} \|I(f)-I_2(f)\|\leq \frac{(b-a)}{2880}\cdot h^4 \max_{x \in[a,b]}~\|f^{(4)}(x)\| \end{eqnarray}$ Auf unser Beispiel angewandt ergibt sich dabei: $\begin{eqnarray} \max_{x\in [-1,1]} \|f^{(4)}\| \leq \frac{24}{10^{12}} \end{eqnarray}$ Und somit: $\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} \\ h^4 &&\stackrel{!} \leq 6 \cdot 10^{-12} \\ h && \stackrel{!} \leq \sqrt[4]{6} \cdot 10^{-3} \end{eqnarray}$ Das würde für die Anzahl der benötigten Teilintervalle bedeuten? $\begin{eqnarray} m:=\frac{2}{h} \stackrel{!} \geq \frac{2}{\sqrt[4]{6}} \cdot 10^{3} \end{eqnarray}$ , Also müßte man auf über 1000 Teilintervallen die Simpsonregel anwenden, um eine Genauigkeit von 0.10 zu erhalten. Das entspricht über xx Funktionsauswertungen. Geht das nicht auch besser? Wie können wir also das Integral mit hinreichender Genauigkeit und möglichst geringem Aufwand approximieren? Wir wollen das Integral einer Funktion $\begin{eqnarray} I(f):=\int_a^b~f(x)~dx \end{eqnarray}$ mit Hilfe der summierten Simpson-Regel derart approximieren, dass der Fehler möglichst nicht größer als eine vorgegebene Genauigkeit $\begin{eqnarray} \varepsilon >0 \end{eqnarray}$ ist. Dazu teilen wir das Intervall $\begin{eqnarray} [a,b] \end{eqnarray}$ sukzessive in geeignete Teilintervalle $\begin{eqnarray} I_i:=[x_i,~x_{i+1}] \end{eqnarray}$ der Länge $\begin{eqnarray} h_i \end{eqnarray}$ ein. Die Anzahl m dieser Teilintervalle sowie die genaue Lage der Stützpunkte $\begin{eqnarray} x_i \end{eqnarray}$ sind zu Beginn der Rechnung unbekannt Betrachtung eines Teilintervalls exaktes Integral: $\begin{eqnarray} I_i(f):=\int_{x_i}^{x_{i+1}}~f(x)~dx \end{eqnarray}$ Näherung 1 (Simpson): $\begin{eqnarray} P_i(f)=\frac{h_i}{6} \Bigl\{f(x_i) + 4\cdot f(x_i + \frac{h_i}{2})+f(x_{i+1}) \Bigr\} \end{eqnarray}$ Näherung 2 (1x sum. Simpson): $\begin{eqnarray} Q_i(f)=\frac{h_i}{12} \Bigl\{f(x_i) + 4\cdot f(x_i + \frac{h_i}{4})+2\cdot f(x_i + \frac{h_i}{2}) + 4\cdot f(x_i + \frac{3h_i}{4}) + f(x_{i+1}) \Bigr\} \Bigr\} \end{eqnarray}$ Voraussetzung 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) - P_i(f) \approx \tau \cdot h_i^5 \end{eqnarray}$ Daraus ergibt sich für die einfach zusammengesetze Formel: $\begin{eqnarray} I_i(f) - Q_i(f) \approx 2\tau \cdot (\frac{h_i}{2})^5 \end{eqnarray}$ Daraus erhalten wir: $\begin{eqnarray} I_i(f) - Q_i(f) && \approx 2\tau \cdot (\frac{h_i}{2})^5 \\16 (I_i(f) - Q_i(f)) && \approx 32\tau \cdot (\frac{h_i}{2})^5 \\&& = \tau h_i^5 \\ && \approx I_i(f) - P_i(f) \\&& = I_i - Q_i(f) + Q_i(f) - P_i(f) \end{eqnarray}$ Mit diesem Trick erhalten wir also die Gleichung: $\begin{eqnarray} 15 (I_i(f) - Q_i(f)) \approx Q_i(f) - P_i(f) \end{eqnarray}$ Und daraus die approximative Gleichung: $\begin{eqnarray} I_i(f) - Q_i(f) \approx \frac{1}{15}(Q_i(f) - P_i(f)) \end{eqnarray}$ So können wir den nicht bekannten Fehler (linke Seite - wahrer Integralwert ist unbekannt) durch die Differenz der beiden Quadraturformeln auf der rechten Seite annähern. Welche Abschätzung müssen wir nun fordern, um am Ende die gewünschte Genauigkeit zu erhalten? $\begin{eqnarray} \|Q_i(f)-P_i(f)\| \leq \frac{15h_j\varepsilon}{b-a} \end{eqnarray}$ () Dann ergibt sich: $\begin{eqnarray} \| \int_{a}^{b}f(x)~dx - \sum_{i=0}^{m}Q_i(f)\| &&= \|\sum_{i=0}^{m-1} (I_i(f)-Q_i(f))\| \\ && \leq \sum_{i=0}^{m-1}\|I_i(f)-Q_i(f)\| \\ && \approx \sum_{i=0}^{m-1} \|\frac{1}{15} (Q_i(f) - P_i(f))\| \\ && \leq \frac{1}{15} \cdot \frac{15h_j\varepsilon}{b-a}\sum_{i=0}^{m-1}h_i \\&& = \varepsilon \end{eqnarray}$ Wie geht man nun vor?* 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). Die Umsetzung dieses Verfahrens für obige Funktion findet man im Beispielteil dieses Workshops.
13.04.2007, 01:26	tigerbine	Auf diesen Beitrag antworten »
8. Maximale Ordnung von Quadraturformeln Wieder betrachtet man die Quadraturformeln vom bekannten Typ: $\begin{eqnarray} I_n(f)=\sum_{j=0}^n~w_j\cdot f(x_j) \end{eqnarray}$ Bei den interpolatorischen Formeln galt: $\begin{eqnarray} w_j=\int_a^b~l_j(x)~dx \end{eqnarray}$ und es ließ sich mindestens die Ordnung (n+1) erreichen. Es stellt sich nun die Frage, od die Ordnung von Quadraturformeln (bzgl. n) von oben beschränkt ist und wie die Knoten $\begin{eqnarray} x_0,...,x_n \end{eqnarray}$ zu wählen sind, um eine möglichst hohe Ordnung der Quadraturformeln zu erhalten. Satz: Die Ordnung obiger Quadraturformeln beträgt höchstens 2n+2, d.h. alle Polynome $\begin{eqnarray} p \in \Pi_{2n+1} \end{eqnarray}$ werden exakt integriert. Beweis: Man betrachtet die Funktion $\begin{eqnarray} \omega^2(x) = \prod_{j=0}^{n}~(x-x_j)^2 \in \Pi_{2n+2} \end{eqnarray}$ . Integriert man die Funktion numerisch erhält man: $\begin{eqnarray} I_n(w^2) = \sum_{j=0}^n~w_j\cdot \omega^2(x_j) = 0 \end{eqnarray}$ Für das Exakte Integral hingegen gilt: $\begin{eqnarray} \omega^2(x) \neq \text{Nullfunktion }, \omega^2(x) \geq 0 \Rightarrow I(\omega^2) >0 \end{eqnarray}$ Somit erhält man: $\begin{eqnarray} I(\omega^2)-I_n(\omega^2) > 0 \end{eqnarray}$ . Folglich wird das Polynom $\begin{eqnarray} \omega^2 \in \Pi_{2n+2} \end{eqnarray}$ nicht exakt integriert.
13.04.2007, 01:28	tigerbine	Auf diesen Beitrag antworten »
9. Gaußsche Quadraturformeln Ziel ist es nun interpolatorische Quadraturformeln (durch Integration des Interpolationspolynoms) zu konstruieren, welche die Maximalordnung 2n+2 haben. Diese bezeichnet man als die sog. Gaußschen Quadraturformeln. Mit $\begin{eqnarray} \Pi \end{eqnarray}$ sei die Menge aller Polynome ohne Gradbeschränkung bezeichnet, im Gegensatz dazu bezeichnet $\begin{eqnarray} \Pi_n \end{eqnarray}$ die Menge aller Polynom vom Höchstgrad n. Das weiteren interessieren wir uns in diesem Abschnitt für Integrale vom Typ: $\begin{eqnarray} I(f) := \int_a^b~\gamma(x) \cdot f(x)~dx \end{eqnarray}$ () Dabei ist $\begin{eqnarray} \gamma \end{eqnarray}$ eine gegebene Gewichtsfunktion* mit folgenden Eigenschaften: Die Funktion $\begin{eqnarray} \gamma \end{eqnarray}$ hat keine negativen Werte Die Integrale $\begin{eqnarray} \int_a^b~\gamma(x)\cdot p(x)~dx \end{eqnarray}$ existieren für alle $\begin{eqnarray} p\in \Pi \end{eqnarray}$ $\begin{eqnarray} \int_a^b~\gamma(x)\cdot p(x)~dx \neq 0 \end{eqnarray}$ für alle Polynome $\begin{eqnarray} p \neq 0 \end{eqnarray}$ ohne Vorzeichenwechsel in $\begin{eqnarray} ]a,b[ \end{eqnarray}$ Achtung! Es wird hier zugelassen, dass die Integrationsgrenzen a,b mit -oo bzw. +oo zusammenfallen, sofern obige Bedingungen für eine Gewichtsfunktion erfüllt sind. In diesem Fall sind aber nicht mehr alle stetigen Funktionen im Sinne von () integrierbar. Ist $\begin{eqnarray} \gamma \end{eqnarray}$ beispielsweise eine positive, stetige Gewichtsfunktion (z.B. $\begin{eqnarray} e^{-x}~\forall~x \geq 0) \end{eqnarray}$ auf einem unendlichen Intervall, so ist $\begin{eqnarray} f=1/\gamma \end{eqnarray}$ stetig, aber I(f) existiert nicht. Die vorherigen Überlegungen können aber ohne weiteres auf Integrale vom Typ () ausgedehnt werden. Die früher auftretenden Integrale müssen um den Faktor $\begin{eqnarray} \gamma \end{eqnarray}$ ergänzt werden. Insbesondere kann der Begriff der Ordnung einer Integrationsformel unverändert übernommen werden. Nicht mehr gültig sind im Falle unendlich langer Intervalle allerdings der Konvergenzsatz und das Korollar, da der im Beweis verwendete Satz von Weierstraß nur für kompakte Intervalle gilt. Das Lemma bzgl. der höheren Ordnung im Falle von SIM-Knoten belibt nur bestehen, wenn auch die Gewichtsfunktion $\begin{eqnarray} \gamma \end{eqnarray}$ auf dem gegebenen Intervall symmterisch zum Mittelpunkt ist. Kennt man die Knoten $\begin{eqnarray} x_0,...,x_n \end{eqnarray}$ so ergeben sich die Gewichte $\begin{eqnarray} w_j \end{eqnarray}$ wieder über die Lagrange Koeffizienten $\begin{eqnarray} l_j \in \Pi_n \end{eqnarray}$ : $\begin{eqnarray} w_j=\int_a^b~\gamma (x)\cdot l_j(x)~dx,\qquad j=0,1,...,n \end{eqnarray}$ Vektorraum und Skalarprodukte Die Mengen $\begin{eqnarray} \Pi, \Pi_n \end{eqnarray}$ bilden Vektorräume auf denen wie folgt ein Skalarprodukt definiert werden kann: $\begin{eqnarray} <f,g>:=\int_a^b~\gamma(x)\cdot f(x)\cdot g(x)~dx, \quad f,g \in C([a,b]) \end{eqnarray}$
13.04.2007, 01:31	tigerbine	Auf diesen Beitrag antworten »
9a. Orthogonale Polynome 1: Wann steht ein Polynom senkrecht auf "allen anderen" Polynomen? Gilt $\begin{eqnarray} <f,g>=0 \end{eqnarray}$ , so nennt man f und g orthogonal. Satz 1: Sei $\begin{eqnarray} \omega \in \Pi_{n+1},~n \geq 0 \end{eqnarray}$ und $\begin{eqnarray} <\omega,p>=0~ \forall ~p \in \Pi_n \end{eqnarray}$ . Dann ist entweder: $\begin{eqnarray} \omega \equiv \end{eqnarray}$ 0, oder $\begin{eqnarray} \omega \end{eqnarray}$ hat genau (n+1) paarweise verschiedene Nullstellen in ]a,b[. Beweis: Aus der linearen Algebra weiß man, dass der Nullvektor per Definition senkrecht auf jedem Vektor steht. Somit erklärt sich die Schlussfolgerung $\begin{eqnarray} \omega \equiv 0 \end{eqnarray}$ von selbst. Sei also nun $\begin{eqnarray} \omega \neq 0 \end{eqnarray}$ . Mit $\begin{eqnarray} t_0 < ... < t_m \end{eqnarray}$ seien die Nullstellen von w in ]a,b[ mit Vorzeichenwechsel bezeichnet. Dann definiert man folgendes Polynom s: $\begin{eqnarray} s(x):= \begin{cases} \prod_{j=0}^m~(x-x_t) & t_j \text{ existieren} \\ 1 &\text{sonst} \end{cases} \end{eqnarray}$ Die Polynomfunktion $\begin{eqnarray} \omega \cdot s \end{eqnarray}$ hat dann in ]a,b[ keinen Vorzeichenwechsel. Daher folgt mit den Anforderungen an die Gewichtsfunktion: $\begin{eqnarray} \Rightarrow <\omega,s> = \int_a^b \gamma(x)\cdot \omega (x)\cdot s(x)~dx \neq 0 \end{eqnarray}$ $\begin{eqnarray} \Rightarrow s \notin \Pi_n \end{eqnarray}$ Da nun aber s per Definition den Grad (m+1) hat und es gilt $\begin{eqnarray} n < \text{ Grad(s) } \leq \text{ Grad }(\omega) \end{eqnarray}$ , folgt wegen $\begin{eqnarray} \omega \in \Pi_{n+1} \end{eqnarray}$ : $\begin{eqnarray} \Rightarrow m = n \end{eqnarray}$ Das Polynom $\begin{eqnarray} \omega \end{eqnarray}$ hat daher notwendigerweise genau (n+1) paarweise verschiedene Nullstellen in ]a,b[. Korollar 1: Sei $\begin{eqnarray} \omega \in \Pi_{n+1} \end{eqnarray}$ und $\begin{eqnarray} \omega \neq 0 \end{eqnarray}$ . Dann ist $\begin{eqnarray} \omega \end{eqnarray}$ bis auf einen multiplikativen Faktor eindeutig bestimmt. Beweis: Sei $\begin{eqnarray} \omega \in \Pi_{n+1},~\omega \neq 0 \end{eqnarray}$ und erfülle die Bedingung $\begin{eqnarray} <\omega,p> =0 ~\forall~ p \in \Pi_n \end{eqnarray}$ . Nach den Rechenregeln für Skalarprodukte folgt dann, dass auch für jedes skalare Vielfache von \omega gilt: $\begin{eqnarray} <a\cdot \omega,p> = a\cdot < \omega,p> = 0 ~\forall~ p \in \Pi_n \end{eqnarray}$ Bleibt die "Eindeutigkeit" noch zu zeigen. Seien nun $\begin{eqnarray} \omega_1,\omega_2 \end{eqnarray}$ zwei nicht verschwindende Polynome, die obige Bedingung erfüllen. Dann ist auch für $\begin{eqnarray} \vartriangle \omega:=\omega_1-\omega_2 \end{eqnarray}$ die Bedingung erfüllt: $\begin{eqnarray} <\vartriangle \omega, p> = <\omega_1,p>-<\omega_2,p> = 0-0 = 0 ~\forall p \in \Pi_n \end{eqnarray}$ . Durch entsprechende Multiplikation mir geeigneten Zahlenfaktoren kann man erreichen, dass $\begin{eqnarray} \omega_1,\omega_2 \end{eqnarray}$ den gleichen Höchstkoeffizienten haben, sind sie doch beide vom Grad (n+1). Also gilt dann $\begin{eqnarray} \vartriangle \omega \in \Pi_n \end{eqnarray}$ und mit obigem Satz folgt dann, dass $\begin{eqnarray} \vartriangle \omega =0 \end{eqnarray}$ gelten muss, uns somit stimmen $\begin{eqnarray} \omega_1,\omega_2 \end{eqnarray}$ bis auf einen multiplikativen Faktor überein.
13.04.2007, 01:33	tigerbine	Auf diesen Beitrag antworten »
9b. Orthogonale Polynome 2: Wahl der Knoten als deren Nullstellen Satz 2: Die Quadraturformel hat genau dann die (maximale) Ordnung (2n+2), wenn die Knoten $\begin{eqnarray} x_j \in ]a,b[ \end{eqnarray}$ so gewählt werden, dass für $\begin{eqnarray} \omega \in \Pi_{n+1} \end{eqnarray}$ mit $\begin{eqnarray} \omega(x)=\prod_{j=0}^n~(x-x_j) \end{eqnarray}$ gilt: $\begin{eqnarray} <\omega,p> = 0 \quad \forall ~ p \in \Pi_{n} \end{eqnarray}$ Beweis: $\begin{eqnarray} \Rightarrow \end{eqnarray}$ Sei $\begin{eqnarray} I_n(f)=\sum_{j=0}^n~w_j \cdot f(x_j) \end{eqnarray}$ eine Formel der Ordnung (2n+2) zur Integration von f auf dem Intervall $\begin{eqnarray} I:=]a,b[ \end{eqnarray}$ . Dann sind $\begin{eqnarray} x_j \end{eqnarray}$ paarweise verschiedene Knoten aus I. $\begin{eqnarray} I_n(f)=I(f) \quad \forall f \in \Pi_{2n+1} \end{eqnarray}$ $\begin{eqnarray} \Rightarrow \text{Damit auch }\forall~ f=\omega \cdot p \in \Pi_{2n+1} \text{ mit } p \in \Pi_n \end{eqnarray}$ Es folgt daraus: $\begin{eqnarray} 0 = I(f)-I_n(f)&&=\int_a^b~\gamma(x)\cdot f(x) ~dx - \sum_{j=0}^n~w_j\cdot f(x_j)~dx =\\&&=\int_a^b~\gamma(x)\cdot \omega (x)p(x)~dx - \sum_{j=0}^n~w_j\cdot \omega (x_j)p(x_j)~dx =\\&&=\int_a^b~\gamma(x)\cdot \omega (x)p(x)~dx - \sum_{j=0}^n~w_j\cdot 0\cdot p(x_j)~dx= \\&&=\int_a^b~\gamma(x)\cdot \omega (x)p(x)~dx \\&& = <\omega,p> \end{eqnarray}$ Somit gilt: $\begin{eqnarray} <\omega ,p>=0 \quad \forall ~p \in \Pi_n \end{eqnarray}$ $\begin{eqnarray} \Leftarrow \end{eqnarray}$ Seien nun $\begin{eqnarray} x_j \in ]a,b[ \end{eqnarray}$ so gewählt, dass gilt: $\begin{eqnarray} <\omega ,p>= 0 \quad \forall~p\in\Pi_n \end{eqnarray}$ mit $\begin{eqnarray} \omega (x) =\prod_{j=0}^n(x-x_j) \end{eqnarray}$ Ferner sei $\begin{eqnarray} f \in \Pi_{2n+1} \end{eqnarray}$ . Dann kann man mittels Polynomdivision f durch w dividieren und erhält die folgende Darstellung: $\begin{eqnarray} f = wp+r \qquad p,r \in \Pi_n \end{eqnarray}$ Integriert man nun, so erhält man: $\begin{eqnarray} \int_a^b~\gamma(x) \cdot f(x)~dx &&= \int_a^b~\gamma \cdot w(x)p(x)~dx + \int_a^b~\gamma(x)\cdot r(x)~dx=\\&&=<\omega,p> + \int_a^b~\gamma(x) \cdot r(x) ~dx = \\&&=0 +\int_a^b~\gamma(x) \cdot r(x) ~dx \end{eqnarray}$ $\begin{eqnarray} \Rightarrow I(f)=I(r) \end{eqnarray}$ Andererseits ist $\begin{eqnarray} I_n(f)&&=\sum_{j=0}^n~w_j\cdot f(x_j) =\sum_{j=0}^n~w_j\cdot[\omega(x_j)\cdot p(x_j)+r(x_j)] = \\&&=\sum_{j=0}^n~w_j\cdot [0+r(x_j)]~dx =\sum-{j=0}^n~w_j\cdot r(x_j)=\\&&=I_n(r) \end{eqnarray}$ Da die Quadraturformeln $\begin{eqnarray} I_n \end{eqnarray}$ interpolatorisch sind und $\begin{eqnarray} r \in \Pi_n \end{eqnarray}$ folgt: $\begin{eqnarray} I(f)=I(r)=I_n(r)=I_n(f) \end{eqnarray}$
13.04.2007, 01:37	tigerbine	Auf diesen Beitrag antworten »
9c. Berechnung der Orthogonalen Polynome Damit man ein Konstruktionsverfahren für Quadraturformeln der Ordnung 2n+2 angeben kann, muss noch der Beweis über die Existenz der Polynome $\begin{eqnarray} \omega \end{eqnarray}$ geführt werden. Dies läßt sich aber schnell nachholen. Mit dem Gram-Schmidtschen Orthogonalisierungsverfahren können in einem Vektorraum mit Skalarprodukt, linear unabhängige Elemente immer in paarweise zueinander orthogonale Elemente umgerechnet werden. Die linear unabhängigen Polynome 1,x,x²,... können also paarweise orthogonalisiert werden. Damit ist die Existent der diskutierten orthogonalen Polynome gesichert. Jede Gewichtsfunktion $\begin{eqnarray} \gamma \end{eqnarray}$ definiert also, bis auf einen Faktor, eindeutige orthogonale Polynome $\begin{eqnarray} q_0=1 \end{eqnarray}$ und $\begin{eqnarray} q_{n+1} \in \Pi_{n+1} \end{eqnarray}$ . Berechnung der orthogonalen Polynome Aus der Orthogonalität der Polynome $\begin{eqnarray} q_0,...q_{n+1} \end{eqnarray}$ folgt deren lineare Unabhängigkeit. Sie bilden also eine Basis des $\begin{eqnarray} \Pi_{n+1} \end{eqnarray}$ . Somit können wir folgenden Satz zur Drei-Term-Rekursion ihrer Berechnung formulieren: () $\begin{eqnarray} c_{n+1}\cdot q_{n+1} = (x-a_n)\cdot q_n - b_{n-1}\cdot q_{n-1} \qquad n \geq0,~q_{-1}=0,~q_0=1 \end{eqnarray}$ mit: $\begin{eqnarray} h_n \text{ Höchstkoeffizient von }q_n \end{eqnarray}$ $\begin{eqnarray} c_{n+1}=\frac{h_n}{h_{n+1}} \end{eqnarray}$ $\begin{eqnarray} a_n=\frac{<xq_n,q_n>}{<q_n,q_n>} \end{eqnarray}$ $\begin{eqnarray} b_{n-1}=\frac{h_{n-1}<q_n,q_n>}{h_n<q_{n-1},q_{n-1}>} \end{eqnarray}$ Besonders einfach gestaltet sich die Berechnung natürlich, wenn alle Koeffizienten a priori bekannt sind. Ein Beispiel dafür sind die Tschebyscheff-Polynome. Generell gilt dabei die Logikkette: Vorgabe Intervall $\begin{eqnarray} ]a,b[ \end{eqnarray}$ und Gewichtsfunktion $\begin{eqnarray} \Rightarrow \end{eqnarray}$ Skalarprodukt $\begin{eqnarray} <f,g> \end{eqnarray}$ wird definiert Satz 1 + Korollar 1 $\begin{eqnarray} \Rightarrow \end{eqnarray}$ $\begin{eqnarray} q_{n+1} \end{eqnarray}$ ist bis auf Faktor eindeutig bestimmt $\begin{eqnarray} \Rightarrow \end{eqnarray}$ weitere Bedingung, z.B. $\begin{eqnarray} q_{n+1}(1)=1 \end{eqnarray}$ Hier nun verschiedene Gewichtsfunktionen und die zugehörigen Rekursionskoeffizienten (siehe ) der orthogonalen Polynome. Die Lage ihrer Nullstellen determiniert das Intervall ]a,b[: $\begin{eqnarray} \begin{array} {\| c \| c \|c \|\|c \|c\|c \|c \| l \|} \hline &&&&&&&\\ \gamma & a & b & c_{n+1} & a_n & b_{n-1} & q_1 & \text{Name} \\ \hline \hline &&&&&&&\\ 1& -1& 1& \frac{n+1}{2n+1} & 0 & \frac{n}{2n+1} & x & P_n\text{ Legendre} \\ \hline &&&&&&&\\ \frac{1}{\sqrt{1-x^2}} & -1 & 1& \frac{1}{2} & 0 & \frac{1}{2} & x & T_n \text{ Tschebyscheff} \\ \hline &&&&&&&\\ \frac{1}{\sqrt{1-x^2}} & -1 & 1& \frac{1}{2} & 0 & \frac{1}{2} & 2x & T_n \text{ Tschebyscheff 2. Art} \\ \hline &&&&&&&\\ e^{-x} & 0 & \infty& -n-1 & 1+2n & -n & 1-x & L_n \text{ Laguerre} \\ \hline &&&&&&&\\ e^{-x^2} & -\infty & \infty & \frac{1}{2} & 0 & n & 2x & H_n \text{ Hermite} \\ \hline \end{array} \end{eqnarray}$ Bitte hierzu auch die Beispiele betrachten, da die Koeffizienten teilweise erst ab einem bestimmten Index für n gelten! Ferner ist zu beachten, dass zwar die Funktion an den Knoten ausgewertet wird, jedoch ein gewichtetes Integral approximiert wird $\begin{eqnarray} \int_{a}^{b}~\gamma(x)f(x)~dx \approx \sum_{j=0}^{n} w_jf(x_j) \end{eqnarray}$ Möchte man also f integrieren, so muss man wie folgt ansetzen: $\begin{eqnarray} \int_{a}^{b}~\gamma(x) \underbrace{\frac{f(x)}{\gamma(x)}}_{\hat f(x)}~dx \approx \sum_{j=0}^{n} w_j \hat f(x_j) \end{eqnarray}$
15.04.2007, 00:59	tigerbine	Auf diesen Beitrag antworten »
9d. Golub & Welsch - Berechnung der Knoten und Gewichte Normiert man die Rekursionsformel unter Erhalt ihrer Struktur, so kann man die neuen Koeffizienten in eine Tridiagonalmatrix eintragen. aus den Eigenwerten und Eigenvektoren kann man dann die Knoten und Gewichte der Gauß-Polynome bestimmen. Vorgeführt wird das Verfahren hier: [WS] Orthogonale Polynome
24.04.2007, 17:41	tigerbine	Auf diesen Beitrag antworten »
9e. Konvergenz Es bleibt nun die Frage offen, ob diese Quadraturformeln der Maximalordnung auch für größer werdende n gegen das Integral konvergieren. Im Falle eines abgeschlossenen Intervalls findet das Lemma Anwendung und es gilt nun zu zeigen, dass: Die Gewichte der Gaußschen Quadraturformeln positiv sind. Beweis: Sind $\begin{eqnarray} l_j \end{eqnarray}$ wie üblich die Lagrange-Koeffizienten, so gilt hier für die Gewichte $\begin{eqnarray} w_j \end{eqnarray}$ wegen $\begin{eqnarray} (l_j)^2 \in \Pi_{2n} \end{eqnarray}$ : $\begin{eqnarray} <l_j,l_j> ~&&=~\int_a^b~\gamma(x)\cdot l_j(x)\cdot l_j(x)~dx =\int_a^b~\gamma(x) \cdot (l_j(x))^2~dx = \\&& \stackrel{\mathrm{Max. Ordn.}}=\sum_{k=0}^{n} ~w_k \cdot (l_j(x_k))^2 = \\ &&\stackrel{\mathrm{Lagr.Koeff.}} = w_j \\&&\stackrel{\mathrm{skal.Prod.}} > 0 \end{eqnarray}$
24.04.2007, 18:00	tigerbine	Auf diesen Beitrag antworten »
9f. Quadraturfehler Als Ausblick sei noch eine Formel zur Bestimmung des Quadraturfehlers angegeben: $\begin{eqnarray} I(f)-I_n(f)=\frac{f^{(2n+2)}(\xi)}{(2n+2)!}\cdot \frac{<q_{n+1},q_{n+1}>}{(h_{n+1})^2} \quad \xi \in [a,b] \end{eqnarray}$ $\begin{eqnarray} q_{n+1} \in \Pi_{n+1}: \quad \text{Das zur gewählten Gewichtsfunktion gehörende Orthogonalpolynom} \end{eqnarray}$ $\begin{eqnarray} h_{n+1}: \quad \text{Höchstkoeffizient von }q_{n+1} \end{eqnarray}$

Neue Frage »

Antworten »

[WS] Numerische Integration - Theorie

Verwandte Themen