[WS] Polynominterpolation - Theorie

Neue Frage »

29.01.2007, 00:15	tigerbine	Auf diesen Beitrag antworten »
[WS] Polynominterpolation - Theorie Gliederung Lagrange-Interpolations-Aufgabe Eindeutigkeit und Existenz Horner-Schema 3a. Abspaltung einer Nullstelle Polynom vom Grad n mit (n+1) Nullstellen ist gleich dem Nullpolynom Taylor-Polynom-Darstellung 5a. Koeffizientenberechnung mittels vollst. Horner-Schema Monom-Darstellung Lagrange-Darstellung Newton-Darstellung 8a. Dividierte Differenzen - Definition 8b. Dividierte Differenzen - Berechnung 8c. Neville-Schema Interpolationsfehler 9a. Darstellung 2 9b. Darstellung 3 9c. Abschätzungen Approximation 10a. Tschebyscheffknoten 10b. Konvergenz 10c. Approximationssatz von Weierstraß 10d. Fehlerempfindlichkeit und Extrapolation Weitere Darstellung der Dividierten Differenzen 11a. Integraldarstellung der dividierten Differenzen 11b. Integraldarstellung des Interpolationsfehlers 11c. Mehrfachknoten Hermitsche-Interpolations-Aufgabe 12a. Eindeutigkeit 12b. Existenz (Neville-Hermite-Schema) 12c. Dividierte Differenzen (Neville-Hermite) 12d. Hermite-Darstellung 12e. Interpolationsfehler Im Anhang habe ich ein Schaubild dieses Themas beigefügt. Dabei kann es bei der Nummerierung zu Abweichungen von obiger Gliederung kommen. Jedoch sollte es über die Titel möglich sein, den Zusammenhang herzustellen. Rechenbeispiele befinden sich in einem eigenen Workshop. Fragen & Anregungen bitte hier posten.
29.01.2007, 11:22	tigerbine	Auf diesen Beitrag antworten »
1. Lagrange-Interpolations-Aufgabe In diesem Workshop wollen wir uns mit der Lösung der Lagrange'schen Interpolationsaufgabe beschäftigen. Dazu müssen wir sie zunächst formulieren: LIPA Bestimme zu (n+1) paarweise verschiedenen Knoten $\begin{eqnarray} x_0,...,x_n \end{eqnarray}$ und zugehörigen Knotenwerten $\begin{eqnarray} y_0,...,y_n \end{eqnarray}$ ein Polynom $\begin{eqnarray} p\in \Pi_n \end{eqnarray}$ mit: $\begin{eqnarray} p(x_j)=y_j~\forall j=0,...,n \end{eqnarray}$
29.01.2007, 11:28	tigerbine	Auf diesen Beitrag antworten »
2. Eindeutigkeit der Lösung Seien $\begin{eqnarray} p_1,~p_2 \in \Pi_n \end{eqnarray}$ zwei Lösungen der LIPA. Dann hat das Polynom $\begin{eqnarray} s(x)=p_1(x)-p_2(x) \end{eqnarray}$ (n+1) Nullstellen. Mit (4) folgt dann $\begin{eqnarray} s \equiv0 \end{eqnarray}$ und damit $\begin{eqnarray} p_1=p_2 \end{eqnarray}$ .
29.01.2007, 14:27	tigerbine	Auf diesen Beitrag antworten »
3. Horner-Schema Klassischer Weise ist ein Polynom in der Monom-Darstellung gegeben: $\begin{eqnarray} p_n(x) = \sum_{j=0}^n~a_j\cdot x^j = a_0 + a_1x + ...+a_nx^n \end{eqnarray}$ Jedoch ist diese Darstellung zur Auswertung an einer Stelle $\begin{eqnarray} \xi \end{eqnarray}$ eher ungeeignet, sind doch: $\begin{eqnarray} \text{- n Summationen} \end{eqnarray}$ $\begin{eqnarray} \text{- }\frac{n(n+1)}{2}=\frac{1}{2}(n^2+n) \text{ Multipklikationen} \end{eqnarray}$ durchzuführen. Deswegen schreibt man es wie folgt um: $\begin{eqnarray} p_n(x)=a_0+x(a_1+x(a_2+....x(a_{n-1}+a_nx)...) \end{eqnarray}$ Und werten die Klamern von innen(rechts) nach außen (links) aus. Das führt dann auf die Berechnungsvorschrift des Hornerschemas: $\begin{eqnarray} a_n^{(1)}=a_n^{(0)} \end{eqnarray}$ $\begin{eqnarray} a_j^{(1)}=a_j^{(0)}+\xi\cdot a_{j+1}^{(1)}, ~\forall j=(n-1),...,1 \end{eqnarray}$ $\begin{eqnarray} p_n(\xi)=a_0^{(0)}+\xi\cdot a_1^{(1)} \end{eqnarray}$ Das Polynom mit den Koeffizienten $\begin{eqnarray} a_j^{(1)} \end{eqnarray}$ bezeichnen wir mit: $\begin{eqnarray} p_{n-1}(x) :=\sum_{j=1}^n~a_j^{(1)}\cdot x^{j-1} \end{eqnarray}$ Auch dieses Polynom könnten wir wieder an der Stelle $\begin{eqnarray} \xi \end{eqnarray}$ auswerten. Wiederholte Anwendung liefert das vollständige Hornerschema: $\begin{eqnarray} a_n^{(0)}\qquad a_{n-1}^{(0)}\qquad ...\qquad a_2^{(0)}\qquad a_1^{(0)}\qquad a_0^{(0)} \end{eqnarray}$ $\begin{eqnarray} a_n^{(1)}\qquad a_{n-1}^{(1)}\qquad ...\qquad a_2^{(1)}\qquad a_1^{(1)}\qquad p_n(\xi) \end{eqnarray}$ $\begin{eqnarray} a_n^{(2)}\qquad a_{n-1}^{(2)}\qquad ...\qquad a_2^{(2)}\qquad p_{n-1}(\xi) \end{eqnarray}$ $\begin{eqnarray} \vdots \end{eqnarray}$ $\begin{eqnarray} a_n^{(n)} \qquad p_1(\xi) \end{eqnarray}$ $\begin{eqnarray} p_0(\xi) \end{eqnarray}$
29.01.2007, 17:03	tigerbine	Auf diesen Beitrag antworten »
3a - Abspalten einer Nullstelle Es gilt der folgende Zusammenhäng zwischen $\begin{eqnarray} p_n(x) \end{eqnarray}$ und $\begin{eqnarray} p_{n-1}(x) \end{eqnarray}$ die in (3) eingeführt wurde. Beweis ist durch Nachrechnen führbar. $\begin{eqnarray} p_n(x)=p_{n-1}(x)\cdot (x-\xi) + p_n(\xi) \end{eqnarray}$ Es muss $\begin{eqnarray} \xi \end{eqnarray}$ natürlich nicht unbedingt eine Nullstelle von $\begin{eqnarray} p_n \end{eqnarray}$ sein, die Titelwahl erklärt sich mit den nächsten post.
29.01.2007, 17:55	tigerbine	Auf diesen Beitrag antworten »
4. Polynom vom Grad n mit (n+1) Nullstellen ist gleich dem Nullpolynom Nun können wir die in (2) verwendete Behauptung beweisen. Sei $\begin{eqnarray} p_n \in \Pi_n \end{eqnarray}$ und besitze (n+1) Nullstellen. Dann können wir folgende vollst. Induktion führen: $\begin{eqnarray} \text{IA: } \quad n = 0, ~p_0 = 0 \text{ konstantes Polynom } \end{eqnarray}$ $\begin{eqnarray} \text{IV: } \quad \text{Sei die Behauptung richtig für (n-1)} \end{eqnarray}$ $\begin{eqnarray} \text{IS: } \quad \text{Nach (3a) gilt für } p_n \in \Pi_n: \end{eqnarray}$ $\begin{eqnarray} \qquad p_n(x) = p_{n-1}(x)\cdot(x-\xi) + p_n(\xi) \end{eqnarray}$ Aus (IV) wissen wir, dass $\begin{eqnarray} p_{n-1} \end{eqnarray}$ n Nullstellen hat. Es muss also $\begin{eqnarray} p_n \end{eqnarray}$ noch eine weitere Nullstelle haben. Sei diese Nullstelle nun mit $\begin{eqnarray} \xi \end{eqnarray}$ bezeichnet, dann folgt: $\begin{eqnarray} p_n(x)=p_{n-1}(x)\cdot(x-\xi)+0 = p_{n-1}(x)\cdot(x-\xi) \stackrel{\mathrm{IV}}= 0 \cdot (x-\xi) \equiv 0 \end{eqnarray}$ fertig.
Anzeige

29.01.2007, 18:17	tigerbine	Auf diesen Beitrag antworten »
5. Taylor-Polynom-Darstellung Hier wollen wir uns die Taylorpolynom-Darstellung des Polynoms $\begin{eqnarray} p_n \end{eqnarray}$ anschauen. Entwickeln wir diese um $\begin{eqnarray} \xi \end{eqnarray}$ , so gilt offensichtlich: $\begin{eqnarray} T_{n,p_n}(x,\xi)=p_n(\xi)+\frac{p_n^{(1)}(\xi)}{1!}\cdot (x-\xi) +\frac{p_n^{(2)}(\xi)}{2!}\cdot (x-\xi)^2+...+\frac{p_n^{(n)}(\xi)}{n!}\cdot (x-\xi)^n \end{eqnarray}$ Denn es gilt für das Restglied (hier in der Lagransche-Form): $\begin{eqnarray} R_{n+1}(x)=\frac{p_n^{(n+1)}(\xi)}{(n+1)!}\cdot (x-\xi)^{n+1} =0 \end{eqnarray}$ Somit haben wir eine weitere Darstellung des Interpolationspolynoms. Die Koeffizienten lassen sich aus dem vollständigen Hornerschema ablesen, siehe (5a).
29.01.2007, 22:29	tigerbine	Auf diesen Beitrag antworten »
5a. Koeffizientenberechnung mittels vollst. Horner-Schema In diesem Abschnitt soll gezeigt werden, dass in der letzten Diagonale des vollst. Horner-Schemas die gesuchten Koeffizienten stehen, also dass gilt: $\begin{eqnarray} p_{n-j}(\xi) = \frac{p_n^{(j)}(\xi)}{j!} \quad \Leftrightarrow \quad p_n^{(j)}(\xi)=j!\cdot p_{n-j}(\xi) \end{eqnarray}$ Beweis *(1) j-maliges Differenzieren von $\begin{eqnarray} p_n \end{eqnarray}$ in der Darstellung (3a)* $\begin{eqnarray} p_n(x)=p_{n-1}(x-\xi)+p_n(\xi) \end{eqnarray}$ $\begin{eqnarray} p_n^{(1)}(x)=p_{n-1}^{(1)}(x)(x-\xi) + p_{n-1}(x) \cdot 1 \qquad \qquad \Rightarrow p_n^{(1)}(\xi) = p_{n-1}(\xi) \end{eqnarray}$ $\begin{eqnarray} p_n^{(2)}(x)=p_{n-1}^{(2)}(x)(x-\xi) + p_{n-1}^{(1)}(x) + p_{n-1}^{(1)}(x) \quad \Rightarrow p_n^{(2)}(\xi) = p_{n-1}^{(1)}(\xi) \end{eqnarray}$ $\begin{eqnarray} \vdots \end{eqnarray}$ $\begin{eqnarray} p_n^{(j)}=p_{n-1}^{(j)}(x-\xi) + j\cdot p_{n+1}^{(j-1)}(x) \qquad \qquad \qquad \Rightarrow p_n^{(j)}(\xi) = j \cdot p_{n-1}^{(j-1)}(\xi) \end{eqnarray}$ Zürückführen auf (n-j) $\begin{eqnarray} p_n^{(j)}(\xi) = j\cdot \Bigl( p_{n-1}^{(j-1)}(\xi) \Bigr) = j\cdot(j-1) \Bigl( p_{n-2}^{(j-2)}(\xi) \Bigr) = \end{eqnarray}$ $\begin{eqnarray} = j\cdot (j-1) \cdot (j-2) \cdot ... \cdot (j-(j-2))\cdot \Bigl( p_{n-(j-1)}^{(j-(j-1))}(\xi) \Bigr) = \end{eqnarray}$ $\begin{eqnarray} =j\cdot (j-1) \cdot (j-(j-1)) \cdot \Bigl( p_{n-j}^{(0)}(\xi) \Bigr) = \end{eqnarray}$ $\begin{eqnarray} = j!\cdot p_{n-j}(\xi) \end{eqnarray}$
29.01.2007, 23:57	tigerbine	Auf diesen Beitrag antworten »
6. Monom-Darstellung Wie bereits erwähnt, können wir das gesuchte Interpolationspolynom (IP) in der Monom-Schreibweise wie folgt angeben: $\begin{eqnarray} p_n(x) = \sum_{j=0}^n~a_j\cdot x^j \end{eqnarray}$ Da es Lösung der LIPA (siehe 1) ist, gilt folglich für alle i = 0,...,n: $\begin{eqnarray} y_i = \sum_{j=0}^n~a_j\cdot (x_i)^j \end{eqnarray}$ Dieses können wir dann als Lineares Gleichungssystem schreiben: $\begin{eqnarray} \begin{pmatrix} 1& x_0& x_0^2& \ldots &x_0^n \\ 1& x_1& x_1^2& \ldots &x_1^n \\ \vdots \\ 1& x_n& x_n^2& \ldots &x_n^n \end{pmatrix} \begin{pmatrix}a_0 \\ a_1 \\ \vdots \\ a_n \end{pmatrix} = \begin{pmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \end{pmatrix} \end{eqnarray}$ Diese Matrix nennt man Vandermonde-Matrix. Aus ihrer Regularität folgt die Existenz und Eindeutigkeit des Koefizientenvektors a und damit des IPs. Man kann dies aber auch ohne ihre Kenntnis beweisen. Dazu betrachten wir den Spezialfall $\begin{eqnarray} y_0 = ... = y_n = 0 \end{eqnarray}$ , also das homogene LGS: $\begin{eqnarray} \begin{pmatrix} 1& x_0& x_0^2& \ldots &x_0^n \\ 1& x_1& x_1^2& \ldots &x_1^n \\ \vdots \\ 1& x_n& x_n^2& \ldots &x_n^n \end{pmatrix} \begin{pmatrix}a_0 \\ a_1 \\ \vdots \\ a_n \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix} \end{eqnarray}$ Lesen wir dies zeilenweise, so steht im Grunde a, dass das gesuchte IP (n+1) Nullstellen hat. Mit (4) folgt, dass es sich dann eindeutig um das Nullpolynom handelt. Daher ist $\begin{eqnarray} (0 &\ldots & 0)^T \end{eqnarray}$ die einzige Lösung, somit der Kern nur der Nullvektor, also die Matrix regulär. Wieder folgt daraus die Existenz und Eindeutigkeit des Interpolationspolynoms
30.01.2007, 00:19	tigerbine	Auf diesen Beitrag antworten »
7. Lagrange-Darstellung Leider ist die Monom-Darstellung zur praktischen Bestimmung des IPs nur bedingt geeignet, muss doch ein inhomogenes LGS einer meist vollbesetzten (nxn)-Matrix gelöst werden. Hier eine weitere Darstellung des IPs, die Lagrange-Darstellung: $\begin{eqnarray} p_n(x)=\sum_{j=0}^n~l_j(x)\cdot y_j \quad \text{ mit } l_j(x) := \prod_{ \begin{matrix}k=0 \\ k \neq j \end{matrix}}^n \frac{(x-x_k)}{(x_j-x_k)} \end{eqnarray}$ Der Nachweis der Erfüllung der LIPA erfolgt durch Rechnung. Mit dieser Form sind wir also jetzt in der Lage, das IP direkt aus den Knoten und zug. Werten zu bestimmen. Anwendung findet diese Darstellung unter anderem beim Thema Numerische Integration. Um der Kritik in Punkt 8 vorzugreifen, empfehle ich das PDF über die baryzentrische Darstellung aus diesem Thread. Sie spielt vor allem unter dem Gesichtspunkt eine Rolle, dem wir uns in Punkt 10a. (Tschebyscheffknoten) dieses Workshops widmen.
30.01.2007, 01:29	tigerbine	Auf diesen Beitrag antworten »
8. Newton-Darstellung Ein Nachteil der Lagrange-Darstellung ist jedoch, dass man bei der Hinzunahme eines weiteren Knotens die bisherigen Ergebnisse verwerfen muss. Gesucht ist nun eine Darstellung von $\begin{eqnarray} p_n \end{eqnarray}$ , die einfach zu $\begin{eqnarray} p_{n+1} \end{eqnarray}$ bei der Hinzunahme eines weiteren Knotens, zu erweitern ist. Da $\begin{eqnarray} \Pi_n \end{eqnarray}$ einen Vektorraum bildet, besitzt $\begin{eqnarray} p_n \in \Pi_n \end{eqnarray}$ eine eindeutige Darstellung bzgl. jeder Basis dieses Vektorraums. In (6) wurde das IP z.B. als Linearkombination der Monom-Basis $\begin{eqnarray} 1,x,...,x^n \end{eqnarray}$ ausgedrückt. Eine andere Basis erhält man durch die Basisfunktion N: - $\begin{eqnarray} N_0(x):=1 \end{eqnarray}$ - $\begin{eqnarray} N_i(x):=\prod_{j=0}^{i-1}~(x-x_j) \end{eqnarray}$ Die Newton-Darstellung des IPs sieht dann wie folgt aus: $\begin{eqnarray} p_n(x) = \sum_{i=0}^n~a_i \cdot N_i(x) \end{eqnarray}$ Das die LIPA wiederspiegelnde LGS sieht dann wie folgt aus: $\begin{eqnarray} \begin{pmatrix} 1 & 0 & \ldots &0 \\ 1 & (x_1-x_0) & \ldots& 0 \\ \vdots \\1 & (x_n-x_0)&\ldots& (x_n-x_0)\cdot \ldots \cdot(x_n-x_{n-1}) \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \\ \vdots \\ a_n \end{pmatrix} = \begin{pmatrix} y_0 \\ y_1 \\ \vdots \\ y_n\end{pmatrix} \end{eqnarray}$ Da die Knoten paarweise verschieden sind, erkennt man sofort die Regularität der Matrix und damit wieder die Existenz und Eindeutigkeit des IPs. Des weiteren können die gesuchten Koeffizienten mittels der weniger aufwändigen Vorwärtssubstitution berechnet werden. $\begin{eqnarray} a_0 = y_0 \end{eqnarray}$ $\begin{eqnarray} a_1 =\frac{y_1-a_0}{x_1-x_0}= \frac{y_1-y_0}{x_1-x_0} \end{eqnarray}$ $\begin{eqnarray} \vdots \end{eqnarray}$ Dies kann man nun schematisch darstellen. Dazu verwendet man das Schema der dividierten Differenzen.
31.01.2007, 16:27	tigerbine	Auf diesen Beitrag antworten »
8a. Dividierte Differenzen - Definition Die dividierten Differenzen sind wie folgt definiert: $\begin{eqnarray} f_{i,0}:=f_i = y_i~\qquad \qquad \qquad \forall i =0,...,n \end{eqnarray}$ $\begin{eqnarray} f_{i,k}:=\frac{f_{i+1,k-1}-f_{i,k-1}}{x_{i+k}-x_{i}} \qquad \forall i=0,...,n,~ k=n-i \end{eqnarray}$ Es ist dann zunächst der Nachweis zu führen, dass das daraus erhalte Polynom: $\begin{eqnarray} p_n(x)=f_{0,0}+f_{0,1}(x-x_0) + ... +f_{0,n}(x-x_0)\cdot ... \cdot(x-x_{n-1}) \end{eqnarray}$ die LIPA erfüllt. Dies geschieht durch vollständige Induktion, wobei man die Behauptung sogar noch etwas allgemeiner fast: $\begin{eqnarray} p_{i,k}(x)=f_{i,0}+f_{i,1}(x-x_i) + ... +f_{i,k}(x-x_i) \cdot ... \cdot(x-x_{i+(k-1)}) \end{eqnarray}$ interpoliert die Punkte $\begin{eqnarray} (x_i,y_i),...,(x_{i+k},y_{i+k})~\quad \forall i=0,...,n,~k=0,...,n-i \end{eqnarray}$ Beweis über k = (i+k)-i: $\begin{eqnarray} \text{IA: k=0 } ~p_{i,0}(x)=f_{i,0}=f_i = y_i ~\quad \forall i=0,...,n \end{eqnarray}$ $\begin{eqnarray} \text{IV: Sei die Beh. richtig für }~ k-1 \geq 0 \end{eqnarray}$ $\begin{eqnarray} \text{IS: } ~ p_{i,k}(x)=p_{i,k-1}(x)+a\cdot(x-x_i)\cdot ... \cdot (x-x_{i+(k-1)}) \end{eqnarray}$ Denn wegen diesem Zusammenhang hat man ja die Newton-Darstallung eingeführt. Es bleibt also zu zeigen, dass gilt: $\begin{eqnarray} a = f_{i,k} \end{eqnarray}$ Dies geschieht Mittels des Polynoms (Nevillesches Polynom) $\begin{eqnarray} q(x):=\frac{(x-x_i)\cdot p_{i+1,k-1}(x) - (x-x_{i+k}\cdot p_{i,k-1}(x))}{x_{i+k}-x_i} \end{eqnarray}$ durch: Nachweis, dass q die LIPA erfüllt Eindeutigkeit des IPs Koeffizientenvergleich von $\begin{eqnarray} q, p_{i,k} \end{eqnarray}$
31.01.2007, 16:46	tigerbine	Auf diesen Beitrag antworten »
8b. Dividierte Differenzen - Berechnung So gut wie in jedem Buch ist eine andere Nomenklatur zu diesem Thema zu finden. Ich habe mich für diese entschieden, weil die Index-Vergabe analog zu der Bezeichnung der Einträge einer Matrix ist (wenn wir dort die erste Zeile mit 0 bezeichnen würden ) $\begin{eqnarray} \begin{pmatrix} a_{00} & a_{01} & a_{02} & a_{03} \\ a_{10} & a_{11} & a_{12} & a_{13} \\ a_{20} & a_{21} & a_{22} & a_{23} \\ a_{30} & a_{31} & a_{32} & a_{33} \end{pmatrix} \end{eqnarray}$ Schema dividierte Differenzen für n=3 $\begin{eqnarray} x_0 \quad \|\|~ y_0 = f_{0,0} \quad \| ~f_{0,1} \quad \|~ f_{0,2} \quad \|~f_{0,3} \quad \| \end{eqnarray}$ $\begin{eqnarray} x_1 \quad \|\|~ y_1 = f_{1,0} \quad \| ~f_{1,1} \quad \|~ f_{1,2} \quad \| \end{eqnarray}$ $\begin{eqnarray} x_2 \quad \|\|~ y_2 = f_{2,0} \quad \| ~f_{2,1} \quad \| \end{eqnarray}$ $\begin{eqnarray} x_3 \quad \|\|~ y_3 = f_{3,0} \quad \| \end{eqnarray}$ Um nun die benötigten Koeffizienten des IPs zu berechnen (erste Zeile) müssen wir die in (8) definierte Rekursionsformel anwenden. Aber auch hier gibt es eine Eselsbrücke.
31.01.2007, 18:28	tigerbine	Auf diesen Beitrag antworten »
8c. Neville Schema Hier wollen wir uns das in (8a) eingeführte Polynom q noch einmal etwas genauer ansehen. Wenn man den dortigen Beweis geführt hat, liefert dieser gerade, dass q eine weitere Darstellung des IP ist. Die bezeichnen wir als Neville-Darstellung. $\begin{eqnarray} p_{i,k}(x) = \frac{(x-x_i)\cdot p_{i+1,k-1}(x) - (x-x_{i+k})\cdot p_{i,k-1}(x)}{x_{i+k}-x_i} \end{eqnarray}$ Diese interpoliert wie gesagt die (k+1) Knoten $\begin{eqnarray} x_i,...,x_{k+1} \end{eqnarray}$ und man kann das letztlich gesuchte IP der (n+1) Knoten $\begin{eqnarray} x_0, ...,x_n \end{eqnarray}$ rekursiv berechnen. Schreibt man diese Rekursion wieder tabellarisch auf, so erkennt man sofort die Ähnlichkeit zum Schema der dividierten Differenzen. Neville- Schema für n=3 $\begin{eqnarray} x_0 \quad \|\|~ y_0 = p_{0,0} \quad \| ~p_{0,1} \quad \|~ p_{0,2} \quad \|~p_{0,3} \quad \| \end{eqnarray}$ $\begin{eqnarray} x_1 \quad \|\|~ y_1 = p_{1,0} \quad \| ~p_{1,1} \quad \|~ p_{1,2} \quad \| \end{eqnarray}$ $\begin{eqnarray} x_2 \quad \|\|~ y_2 = p_{2,0} \quad \| ~p_{2,1} \quad \| \end{eqnarray}$ $\begin{eqnarray} x_3 \quad \|\|~ y_3 = p_{3,0} \quad \| \end{eqnarray}$ Verwendet man die Formel in einem Algorithmus, so stellt man die zunächst auf folgende Darstellung um. So sind weniger wesentliche Operationen nötig. $\begin{eqnarray} p_{i,k}(x) &&= \frac{(x-x_i)\cdot p_{i+1,k-1}(x) - (x-x_{i+k})\cdot p_{i,k-1}(x)}{x_{i+k}-x_i} \\\\ && =\frac{ (x-x_i)\cdot p_{i+1,k-1}(x) +x_{i+k}\cdot p_{i+1,k-1}(x)- x_{i+k}\cdot p_{i+1,k-1}(x) +(x-x_{i+k})\cdot p_{i,k-1}(x)}{x_{i+k}-x_i} \\ && =\frac{x_{i+k}\cdot p_{i+1,k-1}(x)-x_i\cdot p_{i+1,k-1}(x)+x\cdot p_{i+1,k-1}(x) - x_{i+k}\cdot p_{i+1,k-1}(x) +x\cdot p_{i,k-1}(x)-x_{i+k}\cdot p_{i,k-1}(x)}{x_{i+k}-x_i} \\ && =\frac{(x_{i+k}-x_i)\cdot p_{i+1,k-1}(x)-x_i\cdot p_{i+1,k-1}(x)+(p_{i+1,k-1}(x)-p_{i,k-1}(x))\cdot (x-x_{i+k})}{x_{i+k}-x_i} \\ && =\frac{(x_{i+k}-x_i)\cdot p_{i+1,k-1}(x)+(p_{i+1,k-1}-p_{i,k-1})(x)\cdot (x-x_{i+k})}{x_{i+k}-x_i} \\ \\&& = p_{i+1,k-1}(x) + (p_{i+1,k-1}-p_{i,k-1})(x) \cdot \frac{x-x_{i+k}}{x_{i+k}-x_i} \end{eqnarray}$
31.01.2007, 22:23	tigerbine	Auf diesen Beitrag antworten »
9. Interpolationsfehler Bezweckte man mit der Berechnung des IPs eine Funktion f zu approximieren, so ist natürlich von Interesse zu wissen, wie gut das durch die Polynominterpolation gelingt. Deswegen definiert man den Interpolationsfehler wie folgt: $\begin{eqnarray} \varepsilon(x):=f(x)-p_n(x) \end{eqnarray}$ Desweiteren ist es von Interesse zu wissen, ob die Approximation für größe n immer besser wird, ob also gilt: $\begin{eqnarray} \lim_{n \to \infty} \varepsilon(x) = 0 \end{eqnarray}$
01.02.2007, 00:01	tigerbine	Auf diesen Beitrag antworten »
9a. Darstellung 2 Das können wir aber aus der Definition (9) nicht beantworten. Deswegen betrachtet man eine weitere Darstellung des Interpolationsfehlers, mittels dividierter Differenzen. $\begin{eqnarray} \varepsilon(x)=f_{0,n+1}\cdot \prod_{j=0}^n~(x-x_j) \end{eqnarray}$ Beweis: Sei $\begin{eqnarray} x_{n+1} \neq x_j \end{eqnarray}$ für j=0,...,n. Dann hat das IP durch die Knoten $\begin{eqnarray} x_1,...,x_n,x_{n+1} \end{eqnarray}$ die Newton-Form: $\begin{eqnarray} p_{n+1}(x)=p_n(x)+f_{0,n+1}\cdot \prod_{j=0}^n(x-x_j)~\quad() \end{eqnarray}$ Setzt man nun $\begin{eqnarray} x=x_{n+1} \end{eqnarray}$ , dann folgt: $\begin{eqnarray} f(x_{n+1}) = p_{n+1}(x_{n+1}) = p_n(x_{n+1})+f_{0,n+1}\cdot \prod_{j=0}^n(x_{n+1}-x_j) \end{eqnarray}$ $\begin{eqnarray} f(x_{n+1})-p_n(x_{n+1})= f_{0,n+1}\cdot \prod_{j=0}^n(x_{n+1}-x_j) \end{eqnarray}$ Setzte $\begin{eqnarray} x_{n+1} = x \end{eqnarray*}$ . Fertig.
01.02.2007, 00:04	tigerbine	Auf diesen Beitrag antworten »
9b. Darstellung 3 Was wir jetzt schon aus dieser Darstellung erkennen, ist dass sich der Interpolationsfehler aus 2 Faktoren zusammensetzt. Knotenpolynom $\begin{eqnarray} \prod_{j=0}^n(x-x_j) \end{eqnarray}$ dividierter Differenz $\begin{eqnarray} f_{0,n+1} \end{eqnarray}$ Letzteren wollen wir noch etwas genauer untersuchen. Dazu werden wir den Satz von Rolle benötigen. Seien $\begin{eqnarray} x_0,...,x_{n+1} \end{eqnarray}$ paarweise verschiedene Knoten in einem Intervall I=[a,b] und $\begin{eqnarray} f \in C^{n+1}(I) \end{eqnarray}$ . Dann gibt es ein $\begin{eqnarray} \xi \in I \end{eqnarray}$ mit $\begin{eqnarray} f_{0,n+1}=\frac{f^{(n+1)}(\xi)}{(n+1)!} \end{eqnarray}$ Beweis: $\begin{eqnarray} p_{n+1} \in \Pi_n \end{eqnarray}$ interpoliere $\begin{eqnarray} (x_0,f_0),...,(x_{n+1},f_{n+1}) \in I \end{eqnarray}$ . Dann hat die Funktion $\begin{eqnarray} \hat \varepsilon(x):=f(x)-p_{n+1}(x) \end{eqnarray}$ (n+2) Nullstellen in I. $\begin{eqnarray} \xrightarrow{\text{Rolle}} ~\hat \varepsilon ' \end{eqnarray}$ hat (n+1) Nullstellen $\begin{eqnarray} \xrightarrow{\text{Rolle}} ~... \end{eqnarray}$ $\begin{eqnarray} \xrightarrow{\text{Rolle}} ~ \hat \varepsilon^{(n+1)} \end{eqnarray}$ hat 1 Nullstelle $\begin{eqnarray} \xi \end{eqnarray}$ und es ist $\begin{eqnarray} \hat\varepsilon^{(n+1)}(x)=f^{(n+1)}(x)-p_{n+1}^{(n+1)}(x)\stackrel{\mathrm{Darst. 2 ()}}=f^{(n+1)}(x)-(n+1)!\cdot f_{0,n+1} \end{eqnarray}$ $\begin{eqnarray} \hat \varepsilon^{(n+1)}(\xi)&&=f^{(n+1)}(\xi)-(n+1)!\cdot f_{0,n+1} \\ 0 &&= f^{(n+1)}(\xi)-(n+1)!\cdot f_{0,n+1} \\ \\ f_{0,n+1} &&= \frac{f^{(n+1)}(\xi)}{(n+1)!} \end{eqnarray*}$
01.02.2007, 00:19	tigerbine	Auf diesen Beitrag antworten »
9c. Abschätzungen Mit (9a), (9b) erhält man erhält man: $\begin{eqnarray} \varepsilon(x)=f(x)-p_n(x)=\prod_{j=0}^{n}(x-x_j)\cdot \frac{f^{(n+1)}(\xi_x)}{(n+1)!}, \quad \xi \in [a,b] \end{eqnarray}$ Da nun aber $\begin{eqnarray} \xi_x \end{eqnarray}$ nicht explizit bekannt ist und auch von x abhängt, schätz man weiter ab: $\begin{eqnarray} \|\varepsilon(x)\| \leq \|\prod_{j=0}^{n}(x-x_j)\|\cdot \max_{t\in [a,b]} \frac{\|f^{(n+1)}(t)\|}{\|(n+1)!\|} \leq (b-a)^{n+1} \cdot \max_{t\in [a,b]} \frac{\|f^{(n+1)}(t)\|}{\|(n+1)!\|} \end{eqnarray}$ für alle $\begin{eqnarray} x \in [a,b] \end{eqnarray}$
01.02.2007, 00:22	tigerbine	Auf diesen Beitrag antworten »
10. Approximation Aus der Darstellung des Interpolationsfehlers wissen wir, dass er von 2 Faktoren abhängt. Diese sollen im Folgenden einzeln betrachtet werden. $\begin{eqnarray} \varepsilon(x)=f_{0,n+1}\cdot \prod_{j=0}^n~(x-x_j) = f_{0,n+1}\cdot \omega(x) \end{eqnarray}$
01.02.2007, 00:29	tigerbine	Auf diesen Beitrag antworten »
10a. Tschebyscheffknoten In diesem Abschnitt wollen wir den Fehleranteil verursacht durch das Knotenpolynom minimieren. *Aufgabe: min! $\begin{eqnarray} \max_{x\in [a,b]}\|\omega(x)\| \end{eqnarray}$* Lösung: Wähle als Knoten die Nullstellen des Tschebyscheff-Polynoms (Mehr dazu im Workshop Orthogonale Polynome): $\begin{eqnarray} T_{n+1}(x):=\cos \Bigl((n+1)\cdot \arccos(x)\Bigr) \end{eqnarray}$ $\begin{eqnarray} x_j=\cos \Bigl( \frac{2(n-j-1)+1}{2n}\cdot \pi\Bigr) ~\forall j = 0,...,n \end{eqnarray}$ Beweis: Sei $\begin{eqnarray} \omega_0(x) = \prod_{j=0}^n~(x-x_j) \end{eqnarray}$ das Knotenpolynom mit obigen Tschebyscheff-Knoten. Sei nun $\begin{eqnarray} \xi_j,~j=0,...,n \end{eqnarray}$ eine bessere Knotenwahl, d.h. für das zugehörige Knotenpolynom gelte: $\begin{eqnarray} \max_{x\in I} \|\omega(x)\| < \max_{x\in I} \|\omega_0(x)\| \quad () \end{eqnarray}$ Mit dem Workshop orth. Polynom weiß man aus (1e), dass $\begin{eqnarray} \omega_0 \text { und } T_{n+1} \end{eqnarray}$ dieselben Nullstellen haben. Da sie sich nur um den konstanten Faktor $\begin{eqnarray} 2^n \end{eqnarray}$ unterscheiden, liegt auch das gleiche oszillierende Verhalten vor (siehe* 1f) Es ist $\begin{eqnarray} p:=\omega-\omega_0 \in \Pi_n \end{eqnarray}$ , da beide Polynome den gleichen Höchstkoeffizienten (1 bei $\begin{eqnarray} x^{n+1} \end{eqnarray}$ ) besitzen. Wegen() sind die beiden Polynome aber verschieden und es gilt $\begin{eqnarray} p \neq 0 \end{eqnarray}$ Seien $\begin{eqnarray} m_j,~m_{j+1} \end{eqnarray}$ zwei aufeinanderfolgende Extremstellen von $\begin{eqnarray} \omega_0,~j=0,1,...,n \end{eqnarray}$ . Dann gilt wegen der Oszillation und derselben Ausschlaghöhe: $\begin{eqnarray} \omega_0(m_j) + \omega_0(m_{j+1}) = 0 \Leftrightarrow \omega_0(m_j) = -\omega_0(m_{j+1}) \end{eqnarray}$ und $\begin{eqnarray} \|\omega_0(m_j)\| = \| \omega_0(m_{j+1})\|=\max_{x \in I} \|\omega_0(x)\| \end{eqnarray}$ $\begin{eqnarray} p(m_j)=\omega(m_j)-\omega_0(m_j) \text { und } \|\omega(m_j)\| < \|\omega_0(m_j)\| \end{eqnarray}$ und $\begin{eqnarray} p(m_{j+1}) = \omega(m_{j+1})-\omega_0(m_{j+1}) \text { und } \|\omega(m_{j+1})\| < \|\omega_0(m_{j+1})\| \end{eqnarray}$ $\begin{eqnarray} \Rightarrow \end{eqnarray}$ Also haben dann $\begin{eqnarray} p(m_j) \end{eqnarray}$ und $\begin{eqnarray} p(m_{j+1}) \end{eqnarray}$ verschiedene Vorzeichen. $\begin{eqnarray} \Rightarrow \end{eqnarray}$ Somit liegt zwischen $\begin{eqnarray} m_j \end{eqnarray}$ und $\begin{eqnarray} m_{j+1} \end{eqnarray}$ nach dem ZWS für stetige Funktion eine Nullstelle von p. $\begin{eqnarray} \Rightarrow \end{eqnarray}$ Somit hat p(n+1)-Nullstellen $\begin{eqnarray} \Rightarrow \end{eqnarray}$ p ist das Nullpolynom, Widerspruch zu $\begin{eqnarray} p \neq 0 \end{eqnarray}$ . Veranschaulichung* äquidistante Knoten $\begin{eqnarray} x_0 = -1,~x_1=-0.5,~x_3=0,~x_4=0.5,~x_5=1 \end{eqnarray}$ $\begin{eqnarray} \omega(x) = (x+1)(x+0.5)(x)(x-0.5)(x-1) \end{eqnarray}$ Tschebyscheff-Knoten Nullstellen von $\begin{eqnarray} T_{n+1} \end{eqnarray}$ : $\begin{eqnarray} x_j=\cos \Bigl( \frac{2(n-j)+1}{2n+2}\cdot \pi\Bigr) \end{eqnarray}$ Nullstellen von $\begin{eqnarray} T_{5} \end{eqnarray}$ : $\begin{eqnarray} x_j=\cos \Bigl( \frac{9-2j}{10}\cdot \pi\Bigr) \end{eqnarray}$ $\begin{eqnarray} x_0= \cos(\frac{9}{10}\pi)\approx -0.95 ,~x_1 =\cos(\frac{7}{10}\pi) \approx -0.59,~x_2 =\cos(\frac{5}{10}\pi) = 0, ~ \end{eqnarray}$ $\begin{eqnarray} x_3 =\cos(\frac{3}{10}\pi) \approx 0.59,~x_4 =\cos(\frac{1}{10}\pi) \approx 0.95 \end{eqnarray}$
01.02.2007, 00:32	tigerbine	Auf diesen Beitrag antworten »
10b. Konvergenz Hat man die Knoten nun optimal gewählt, hängt die Frage ob $\begin{eqnarray} \max_{[a,b]} \|f(x)-p(x)\| \rightarrow 0 \end{eqnarray}$ für $\begin{eqnarray} n\rightarrow \infty \end{eqnarray}$ von der zu approximierenden Funktion f ab. $\begin{eqnarray} \varepsilon(x) = f(x)-p_n(X) = \prod_{j=0}^n(x-x_j)\cdot \frac{1}{(n+1)!}\cdot f^{(n+1)}(\xi_x) \end{eqnarray}$ Dabei gilt: $\begin{eqnarray} \frac{1}{(n+1)!}\rightarrow 0 \end{eqnarray}$ für $\begin{eqnarray} n \to \infty \end{eqnarray}$ $\begin{eqnarray} \prod_{j=0}^n(x-x_j) \end{eqnarray}$ wird umso kleiner, je enger die Knoten zusammenliegen. Somit ist der ausschlaggebende Faktor $\begin{eqnarray} f^{(n+1)}(\xi_x) \end{eqnarray}$ . Sind also die Ableitungen von f beschränkt auf [a,b] und f genügend oft differenzierbar, so gilt $\begin{eqnarray} \|\varepsilon(x)\| \rightarrow 0 \end{eqnarray}$ für $\begin{eqnarray} n \rightarrow \infty \end{eqnarray}$ . Dies ist jedoch i.A. - bei beliebiger Stützstellenwahl - nicht zu erwarten. Für vernünftige Verwendung wird man auch gleichmäßige Konvergenz fordern. Beispiel von Runge Satz von Faber + Konvergenzsatz mit Tschebyscheff
01.02.2007, 00:38	tigerbine	Auf diesen Beitrag antworten »
10c. Approximationssatz von Weierstraß *Zu jeder stetigen Funktion f auf einem kompakten Intervall [a,b] gibt es eine Folge $\begin{eqnarray} (P_k) \end{eqnarray}$ von Polynomen, die auf [a,b] gleichmäßig gegen f konvergieren.* Achtung: Dieser Satz besagt nicht, dass man diese Folge durch die Lagrangeschen Interpolationspolynome erhält! Siehe auch Satz von Faber.
01.02.2007, 00:42	tigerbine	Auf diesen Beitrag antworten »
10d. Fehleranfälligkeit und Extrapolation Liegen fehlerhafte Daten $\begin{eqnarray} y_i + \vartriangle y_i \end{eqnarray}$ vor, so verändert dies stark die Gestalt des IPs im gesamten Intervall. Konstruieren wir mal ein einfaches Beispiel. Auf dem Intervall [-1,1] wollen wir die Nullfunktion approximieren. Dazu wählen wir die äquidistanten Stützstellen $\begin{eqnarray} x_i=-1+i\cdot h,~i = 0,...,2m,~ h:=\frac{2}{2m}=\frac{1}{m} \end{eqnarray}$ $\begin{eqnarray} x_m=0 \end{eqnarray}$ Und vergeben folgende Funktionswerte: $\begin{eqnarray} y_i = 0, ~\forall i\neq m \end{eqnarray}$ $\begin{eqnarray} y_m = \varepsilon \end{eqnarray}$ Nun berechnen wir das IP in der Lagrange-Darstellung (): $\begin{eqnarray} p_{2m+1}(x) = \sum_{j=0}^{2m}~l_j(x)\cdot y_j =\sum_{j=0}^{2m}~ \prod_{ \begin{matrix}k=0 \\ k \neq j \end{matrix}}^{2m} \frac{(x-x_k)}{(x_j-x_k)}\cdot y_j = \varepsilon \cdot \prod_{ \begin{matrix}k=0 \\ k \neq m \end{matrix}}^{2m} \frac{(x-x_k)}{(x_m-x_k)} \end{eqnarray}$ $\begin{eqnarray} p_{2m+1}(x)= \varepsilon \cdot \prod_{ \begin{matrix}k=0 \\ k \neq m \end{matrix}}^{2m} \frac{(x-x_k)}{(-x_k)} = \varepsilon \cdot (-1)^{2m} \prod_{ \begin{matrix}k=0 \\ k \neq m \end{matrix}}^{2m} \frac{(x-x_k)}{x_k}= \varepsilon \prod_{ \begin{matrix}k=0 \\ k \neq m \end{matrix}}^{2m} \frac{(x-x_k)}{x_k} \end{eqnarray}$ Beispiel $\begin{eqnarray} \varepsilon = 0.001 \end{eqnarray}$ $\begin{eqnarray} m_1=1 \end{eqnarray}$ $\begin{eqnarray} x_0=-1, x_1=0, x_2=1 \end{eqnarray}$ $\begin{eqnarray} p_{3}(x)=0.001 \cdot \frac{(x-x_0)}{x_0}\cdot \frac{(x-x_2)}{x_2} =- 0.001 \cdot (x+1)(x-1) = -0.001 (x^2-1) \end{eqnarray}$ __________________________________________________________ $\begin{eqnarray} m_2=2 \end{eqnarray}$ $\begin{eqnarray} x_0=-1, x_1=-0.5, x_2=0,x_3=0.5,x_4=1 \end{eqnarray}$ $\begin{eqnarray} p_{5}(x)=0.001 \cdot \frac{(x+1)}{-1} \cdot \frac{(x+0.5)}{-0.5} \cdot \frac{(x-0.5)}{0.5} \cdot \frac{(x-1)}{1} = 0.004 \cdot (x^2-1)(x^2-0.25) \end{eqnarray}$ __________________________________________________________ $\begin{eqnarray} m_3=4 \end{eqnarray}$ $\begin{eqnarray} x_0=-1, x_1 =-0.75,x_2=-0.5, x_3=-0.25, x_4=0, x_5=0.25, x_6 =0.5 x_7 =0.75, x_8=1 \end{eqnarray}$ $\begin{eqnarray} p_{9}(x)\approx 0.11378\cdot (x^2-1)(x^2-0.5625)(x^2-0.25)(x^2-0.0625) \end{eqnarray}$ Man erkennt auch deutlich, dass sich das IP mit steigender Knotenzahl ausserhalb von [-1,1] immer schneller von der Funktion f entfernt. Deswegen ist das IP i.A. auch nicht zur Extrapolation geeignet. Achtung, denn trifft man diese Aussage generell, so tappt man leicht in eine Falle. Das IP so wie es hier bestimmt wurde hat ja das Ziel die Funktion f auf dem Intervall [a,b] möglichst gut zu approximieren. Daher ist es bei dieser Konstruktion auch nicht von Interesse, wie sich das IP außerhalb des Intervalls verhält. Dennoch wird man Interpolationspolynome auch zur Extrapolation verwenden, jedoch mit anders gestalteter Knotenwahl. Mehr dazu steht im [WS] Extrapolation
08.02.2007, 15:01	tigerbine	Auf diesen Beitrag antworten »
11a. Integraldarstellung der Dividierten Differenzen Zunächst noch eine Notation $\begin{eqnarray} \mathcal 5 x_j:= x_j - x_{j-1},~j \geq 1 \end{eqnarray}$ $\begin{eqnarray} f[x_i,x_{i+1},...x_{i+k}] := f_{i,k} \end{eqnarray}$ Satz von Hermite-Genocchi Sei $\begin{eqnarray} f \in C^n(\mathbb R) \end{eqnarray}$ und $\begin{eqnarray} x_j,~j=0,...,n \end{eqnarray}$ paarweise verschieden. Dann besitzen die dividierten Differenzen folgende Darstellung: $\begin{eqnarray} f[x_0,x_{1},...x_{n}] = \int_0^1 \int_0^{t_1} ... \int_0^{t_{n-1}} f^{(n)} (x_0 + \mathcal 5 x_1\cdot t_1 + ...+ \mathcal 5 x_n \cdot t_n)~dt_ndt_{n-1}...dt_1 \end{eqnarray}$ Beweis: vollst. Induktion n=0: $\begin{eqnarray} \int_0^1f^{(0)}(x_0)~dt_1 = f^{(0)}(x_0) \cdot \int_0^1~dt_1 = f(x_0) [t_1]_0^1 = f(x_0) = f[x_0] \end{eqnarray}$ Sei die Behauptung wahr für (n-1). Ferner verifiziere man: $\begin{eqnarray} \int_0^{t_{n-1}}f{(n)}(x_0+...+\mathcal 5 x_n \cdot t_n)~dt_n = \frac{1}{\mathcal 5 x_n}[f{(n-1)} (x_0+...+ \mathcal 5 x_n \cdot t_n)]_0^{t_{n-1}} = \end{eqnarray}$ $\begin{eqnarray} \frac{1}{\mathcal 5 x_n} \Bigl( f^{(n-1)} (x_0+...+ (x_n-x_{n-2}) t_{n-1})-f^{(n-1)}(x_0+...+ \mathcal 5 x_{n-1}\cdot t_{n-1}) \Bigr) \end{eqnarray}$ Somit folgt für n: $\begin{eqnarray} \int_0^1 \int_0^{t_1} ... \int_0^{t_{n-1}} f^{(n)} (x_0 + \mathcal 5 x_1\cdot t_1 + ...+ \mathcal 5 x_n \cdot t_n)~dt_ndt_{n-1}...dt_1 = \end{eqnarray}$ $\begin{eqnarray} \frac{1}{\mathcal 5 x_n} \biggl( \int_0^1 \int_0^{t_1} ... \int_0^{t_{n-2}} f^{(n-1)} (x_0 + ... + (x_n-x_{x-2})\cdot t_n)~dt_{n-1}...dt_1 - \int_0^1 \int_0^{t_1} ... \int_0^{t_{n-2}}f^{(n-1)}(x_0+... \mathcal 5 x_{n-1} \cdot t_{n-1})~dt_{n-1}...dt_1 \biggr) = \end{eqnarray}$ $\begin{eqnarray} \stackrel{\mathrm{IV}}= \frac{1}{\mathcal 5 x_n} \cdot \biggl( f[x_0,x_1,...,x_{n-2},x_n] - f[x_0,x_1,....,x_{n-1}]\biggr) = \end{eqnarray}$ $\begin{eqnarray} \stackrel{\mathrm{Aitken}}=f[x_0,x_1,....,x_n] \end{eqnarray}$
08.02.2007, 15:02	tigerbine	Auf diesen Beitrag antworten »
11b. Integraldarstellung des Interpolationsfehlers Somt kann man den Interpolationsfehler auch wie folgt schreiben: $\begin{eqnarray} \varepsilon (x) = f[x_0,...,x_n,x]\cdot \prod_{j=0}^n(x-x_j) = \end{eqnarray}$ $\begin{eqnarray} =\int_0^1\int_0^{t_1}....\int_0^{t_n} f^{(n-1)}(x_0 + t_1(x_1-x_0) + ... + t_n(x_n-x_{n-1}) + t(x-x_n)~dt...dt_1~\cdot ~\prod_{j=0}^n(x-x_j) \end{eqnarray}$
08.02.2007, 15:02	tigerbine	Auf diesen Beitrag antworten »
11c. Mehrfachknoten Durch die Integraldarstellung der dividierten Differenzen $\begin{eqnarray} f[x_0,...,x_n] \end{eqnarray}$ kann man sie stetig fortsetzen für den Fall, dass Knoten zusammenfallen: $\begin{eqnarray} f[x_0,...,x_n]:=\lim_{\varepsilon \to 0}~f[x_0,...,x_r,x_r+\varepsilon,...,x_n] \end{eqnarray}$ Für den Fall $\begin{eqnarray} x_0=...=x_n \end{eqnarray}$ folgt dann, da $\begin{eqnarray} \mathcal 5 x_j=x_j-x_{j-1} = 0,~j \geq 1 \end{eqnarray}$ : $\begin{eqnarray} f[x_0,...,x_n] = \int_0^1 \int_0^{t_1}... \int_0^{t_{n-1}}~f^{(n)}(x_0)~dt_n...dt_2dt_1 = \end{eqnarray}$ $\begin{eqnarray} =f^{(n)}(x_0) \cdot \int_0^1 \int_0^{t_1}... \int_0^{t_{n-1}}~1~dt_n...dt_2dt_1 = \end{eqnarray}$ $\begin{eqnarray} = \frac{1}{n!}\cdot f^{(n)}(x_0) \end{eqnarray}$ Für (k+1)-gleiche Knoten gilt analog: $\begin{eqnarray} f[x_j,...,x_j] = \frac{f^{(k)}(x_j)}{k!} \end{eqnarray}$ Nochmal zum Fall (n+1) gleicher Knoten zurück. Es ergibt sich dann in der Newton-Darstellung: $\begin{eqnarray} p_n(x) = f_{0,0} + \sum_{j=1}^{n}~f_{0,j}\cdot \prod_{k=0}^{j-1}~(x-x_k) = \end{eqnarray}$ $\begin{eqnarray} = f[x_0] + \sum_{j=1}^{n}~f[\underbrace {x_0,...x_0}_{j+1}] \cdot \prod_{k=0}^{j-1}~(x-x_k) = \end{eqnarray}$ $\begin{eqnarray} = \sum_{j=0}^n~\frac{f^{(j)}(x_0)}{j!} \cdot (x-x_0)^j \end{eqnarray}$ also nichts anderes, als das n-te Taylorpolynom in $\begin{eqnarray} x_0 \end{eqnarray}$
08.02.2007, 15:08	tigerbine	Auf diesen Beitrag antworten »
12. Hermitsche-Interpolations-Aufgabe Nun ist aus der Schulzeit noch bekannt, dass ein Polynom n-ten Grades nicht nur durch die Vorgabe von (n+1) Funktionswerten an paarweise verschiedenen Knoten eindeutig bestimmt ist. Oft kommen in dem "Steckbrief" auch Bedingungen für die Ableitungen vor. Den Beweis, dass man im Falle von Mehrfachknoten auch durch diese Bedingungen, das interpolierende Polynom eindeutig bestimmt ist, soll mit der Hermitschen-Interpolationsaufgabe (HIPA) gezeigt werden. HIPA Gegeben sind m-paarweise verschiedene Knoten auf dem Gitter $\begin{eqnarray} x_0,...,x_n \end{eqnarray}$ . An den sog. Mehrfachknoten, soll das interpolierende Polynom nicht nur den Wert der Funktion annehmen, sondern auch noch den Wert der Ableitung(en). Somit sieht der Datensatz wie folgt aus: $\begin{eqnarray} (x_0, f_0^{(0)},...,f_0^{(i_0)}) \end{eqnarray}$ $\begin{eqnarray} \vdots \end{eqnarray}$ $\begin{eqnarray} (x_n, f_n^{(0)},...,f_n^{(i_n)}) \end{eqnarray}$ Gesucht ist nun ein Polynom p von möglichst niedrigem Grad, so dass die Bedingung: $\begin{eqnarray} p^{(i)}(x_j)=f_j^{(i)},~\qquad i=0,1,...,i_j;\quad j=0,1,...,n \end{eqnarray}$ erfüllt ist.
08.02.2007, 15:08	tigerbine	Auf diesen Beitrag antworten »
12a. Eindeutigkeit Sei $\begin{eqnarray} N:=n+\sum_{j=0}^{n}~i_j \end{eqnarray}$ . Seien $\begin{eqnarray} p_1,p_2 \in \Pi_N \end{eqnarray}$ zwei Lösungen der HIPA und $\begin{eqnarray} q:=p_1-p_2 \end{eqnarray}$ . Dann hat das Polynom $\begin{eqnarray} q \in \Pi_n \end{eqnarray}$ höchstens den Grad N und die Eigenschaft: $\begin{eqnarray} q^{(i)}(x_j) = 0,\qquad i=0,1...,i_j; \quad j = 0,1,...,n \end{eqnarray}$ D.h. am Knoten $\begin{eqnarray} x_j \end{eqnarray}$ hat q eine $\begin{eqnarray} (i_j+1) \end{eqnarray}$ -fache Nullstelle. Insgesamt hat dann q, $\begin{eqnarray} \sum_{j=0}^n~(i_j+1)=n+\sum_{j=0}^n~(i_j)~+1=N+1 \end{eqnarray}$ Nullstellen. Somit ist $\begin{eqnarray} q \equiv 0 \end{eqnarray}$ und $\begin{eqnarray} p_1=p_2 \end{eqnarray}$ .
08.02.2007, 15:09	tigerbine	Auf diesen Beitrag antworten »
12b. Existenz (Neville-Hermite-Schema) Bei der LIPA haben wir in(8c) das Neville-Schema zur Bestimmung der Newton-Darstellung des Interpolationspolynoms verwendet. Dabei wird im Beweis (den der Leser zu führen hat) gezeigt, dass gilt "q interpoliert $\begin{eqnarray} (x_0,f_0),...,(x_n,f_n) \end{eqnarray}$ . Dies hätte man auch als Existenzbeweis des IPs der LIPA nehmen können. (Beweis durch LGS ist einfacher) Um auch hier ein Berechnungsschema zu erhalten, überträgt man nun (8c) auf die HIPA: Neville-Hermitsche-Formel Die im folgenden Algorithmus bestimmen $\begin{eqnarray} p_{i,k} \end{eqnarray}$ liegen in $\begin{eqnarray} \Pi_k \end{eqnarray}$ und interpolieren die gegebenen Daten an den (k+1), nicht notwendiger Weise verschiedenen, Stellen $\begin{eqnarray} \xi_i,\xi_{i+1},...,,\xi_{i+k},\quad i+k \leq n,\quad 0 \leq i \end{eqnarray}$ . Bei Mehrfachknoten sind dann auch die Ableitungen heranzuziehen. Der Algorithmus lautet: $\begin{eqnarray} p_{i,0}(x):=f_i \end{eqnarray}$ $\begin{eqnarray} p_{i,k}(x):=\begin{cases} \frac{(x-\xi_i)p_{i+1,k-1}(x)-(x-\xi_{i+k})p_{i,k-1}(x)}{\xi_{i+k}-\xi_i}& \xi_i \neq \xi_{i+k} \\ p_{i,k-1}(x)+(x-\xi_i)^k\frac{f^{(k)}(\xi_i)}{k!}\quad 1 \leq k \leq N & \text{sonst} \end{cases} \end{eqnarray}$ Beweis ist wieder durch vollst. Induktion zu führen.
08.02.2007, 15:09	tigerbine	Auf diesen Beitrag antworten »
12c. Dividerte Differenzen (Neville-Hermite) $\begin{eqnarray} f_{l,j}=f[x_k,...,x_{l+j}]=\frac{f_{l+1,j-1}-f_{l,j-1}}{x_{l+j}-x_l} \end{eqnarray}$ $\begin{eqnarray} f[\underbrace {x_s,...,x_s}_{k+1}]=\frac{f^{(k)}(x_n)}{k!} \end{eqnarray}$ $\begin{eqnarray} f_{l,0}=f[x_l]=f(x_l) \end{eqnarray}$ $\begin{eqnarray} f[x_i,x_i,x_i,x_{i+1}]=\frac{f[x_i,x_i,x_{i+1}]-f[x_i,x_i,x_i]}{x_{i+1}-x_i} \end{eqnarray}$
08.02.2007, 15:09	tigerbine	Auf diesen Beitrag antworten »
12d. Hermite-Darstellung Analog zur Newton-Darstellung: $\begin{eqnarray} p_N(x)=\sum_{j=0}^{N}~f[x_0,...,x_j]\cdot \prod_{k=0}^{j=1}(x-x_k) =\sum_{j=0}^{N}~f_{0,j}\cdot \prod_{k=0}^{j=1}(x-x_k) \end{eqnarray}$
08.02.2007, 15:09	tigerbine	Auf diesen Beitrag antworten »
12e. Interpolationsfehler $\begin{eqnarray} \varepsilon(x)=f(x)-p_N(x) = f[x_0,...x_N,x]\cdot \prod_{j=0}^{n}(x-x_j)^{i_j+1}= \end{eqnarray}$ $\begin{eqnarray} = \frac{f^{(N+1)}(\zeta)}{(N+1)!}\cdot \prod_{j=0}^{n}(x-x_j)^{i_j+1} \end{eqnarray}$
20.09.2007, 05:35	tigerbine	Auf diesen Beitrag antworten »
Ausblick Abschließend erkennt man also dass ein Datensatz der Länge (n+1) zwar eindeutig ein IP vom Grad N festlegt, man aber nicht mit wachsendem n (also höherem Aufwand) bessere Resultate erzielen muss. Im [Workshop-Spline-Interpolation-Theorie] soll daher ein anderer Ansatz für eine interpolierende Funktion gezeigt werden. Einen anderen Ansatz eine Funktion durch die Datenwolke zu legen, verfolgt die Methode der kleinsten Quadrate.

Neue Frage »

Antworten »

[WS] Polynominterpolation - Theorie

Verwandte Themen