[Numerik I] - Übung 8 *

Neue Frage »

05.01.2009, 01:04

tigerbine

Auf diesen Beitrag antworten »

Aufgaben Teil 1

Inverse mit Newton
Fourierkoeffizienten als Nullfolge
Newton-Cotes für gerade n
Extrapolation der Trapezregel

05.01.2009, 01:05

tigerbine

Auf diesen Beitrag antworten »

8.1 Algorithmus nur mit "*" und "+"
Die Iterationsvorschrift des Newtonverfahrens lautet:

$\begin{eqnarray*} x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)} \end{eqnarray*}$

Die Funktion

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

erfüllt die geforderten Bedingungen. Sie ist zweimal stetig differenzierbar und somit konvergiert as Newton Verfahren lokal quardratisch. Eingesetzt ergibt sich eine Iterationsvorschrift, die nur mit "*" und "+" auskommt.

$\begin{eqnarray*} x_{k+1} &&= x_k - \frac{\frac{1}{x_k}-a}{-\frac{1}{x_k^2}} = x_k+x_k+ax_k^2\\&&=2x_k+ax_k\cdot x_k \end{eqnarray*}$

Beispiel für a=3:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

  x_n+1            x_n           Delta
============================================
  0.019700        0.010000       0.970000 
  0.038236        0.019700       0.940900 
  0.072086        0.038236       0.885293 
  0.128582        0.072086       0.783743 
  0.207564        0.128582       0.614254 
  0.285880        0.207564       0.377308 
  0.326578        0.285880       0.142361 
  0.333196        0.326578       0.020267 
  0.333333        0.333196       0.000411 
  0.333333        0.333333       0.000000 
  0.333333        0.333333       0.000000

05.01.2009, 01:05

tigerbine

Auf diesen Beitrag antworten »

8.2 Riemannsches Lemma
ohne Bearbeitung.

05.01.2009, 01:06

tigerbine

Auf diesen Beitrag antworten »

8.3 Ordnung von NCF-Formeln
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.

05.01.2009, 01:08

tigerbine

Auf diesen Beitrag antworten »

8.4 Extrapolation der Trapezregel
Wir interessieren uns für das Integral

$\begin{eqnarray*} \int_{-1}^{1} ~f(x)~dx && = \int_{-1}^0~12*x^3~dx + \int_0^{1}~12x^2~dx \\&&= 3 [x^4]_{-1}^0 + 4 [x^3]_0^1 \\&&=-3+4=1 \end{eqnarray*}$

Nun soll das Integral durch Extrapolation der Trapezregel bestimmt werden. D.h. zu den Vorgaben h=1,1/2,1/4,1/8 bestimmen wir die Werte, indem das Intervall in $\begin{eqnarray*} \frac{1}{h} \end{eqnarray*}$ Teilintervalle unterteilt wird und dort das Teilintegral Funktionf jeweils über die Trapezregel approximiert wird. Aus der Fehlerformel entnimmt man die Konvergenz gegen das gesuchte Integral bei Extrapolation der Maschenweite gegen 0.

Zitat:

$\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*}$

Zunächst einmal das komplette Interval [-1,1]:

$\begin{eqnarray*} I^T_1 = \frac{1}{2} \Bigl\{f(-1) + f(1) \Bigr\} = 0 \end{eqnarray*}$

$\begin{eqnarray*} I^T_{0.5}=\frac{0.5}{2} \Bigl\{f(-1) +2\cdot f(0)+f(1) \Bigr\}= 0 \end{eqnarray*}$

$\begin{eqnarray*} I^T_{0.25}=\frac{0.25}{2} \Bigl\{f(-1) +2\cdot( f(-0.5)+f(0)+f(0.5))+f(1) \Bigr\}=0.375 \end{eqnarray*}$

$\begin{eqnarray*} I^T_{0.125}=\frac{0.125}{2} \Bigl\{f(-1) +2\cdot \sum_{p=1}^{N-1}~f(a+p\cdot 0.25)+f(1) \Bigr\}=0.46875 \end{eqnarray*}$

Anhand des aufgeteilten Intervalls (Programm verarbeitet keine abschnittsweise definierten Funktionen) soll das Romberg Verfahren gezeigt werden. Die erste Zeile des Schemas entspricht der Summierten Trapezregel. Dann werden aus bekannten Formeln neue Formeln höherer Ordnung.

$\begin{eqnarray*} I^T_1 = \frac{1}{2} \Bigl\{f(-1) + f(0) \Bigr\} = -6 \end{eqnarray*}$

$\begin{eqnarray*} I^T_{0.5}=\frac{0.5}{2} \Bigl\{f(-1) +2\cdot f(-0.5)+f(0) \Bigr\}=-3.75 \end{eqnarray*}$

$\begin{eqnarray*} I^T_{0.25}=\frac{0.25}{2} \Bigl\{f(-1) +2\cdot( f(-0.75)+f(-0.5)+f(-0.25))+f(0) \Bigr\}=-3.1875 \end{eqnarray*}$

code:
1: 2: 3: 4: 5: 6: 7:	Romberg Schema - Funktionswerte bei h=0 =============================================== IR = 1.0000 -6.0000 -3.0000 -3.0000 0.5000 -3.7500 -3.0000 0 0.2500 -3.1875 0 0

code:
1: 2: 3: 4: 5: 6: 7:	Romberg Schema - Funktionswerte bei h=0 =============================================== IR = 1.0000 6.0000 4.0000 4.0000 0.5000 4.5000 4.0000 0 0.2500 4.1250 0 0

31.01.2009, 00:01

tigerbine

Auf diesen Beitrag antworten »

Hier geht es weiter: [Numerik I] - Übung 9 *

Neue Frage »

Antworten »

[Numerik I] - Übung 8 *

Verwandte Themen