Lagrange-Interpolation mit Störung

16.04.2010, 16:12

Cordovan

Lagrange-Interpolation mit Störung

Hallo!

Ich stehe vor der folgenden Aufgabe. Gegeben seien Stützstellen $\begin{eqnarray*} T=(t_1,\ldots,t_n) \end{eqnarray*}$ und Werte $\begin{eqnarray*} F=(f_1,\ldots,f_n) \end{eqnarray*}$ . Diese werden durch $\begin{eqnarray*} p \end{eqnarray*}$ interpoliert und dann gestört. Ein Maß für Kondition ist die Funktion

$\begin{eqnarray*} c(t)=\max_{F,\tilde F}\frac{|p(t)-\tilde p(t)|}{\|F-\tilde F\|_\infty} \end{eqnarray*}$ ,

wobei $\begin{eqnarray*} \tilde F \end{eqnarray*}$ gestörte Werte und $\begin{eqnarray*} \tilde p \end{eqnarray*}$ das dazu passende Interpolationspolynom sind.

Zu zeigen sind jetzt 1. $\begin{eqnarray*} c(t_i)=1 \end{eqnarray*}$ und 2. $\begin{eqnarray*} c(t)=\sum_{i=1}^n|\ell_i(t)| \end{eqnarray*}$ , wobei $\begin{eqnarray*} \ell_i \end{eqnarray*}$ das $\begin{eqnarray*} i \end{eqnarray*}$ -te Lagrange-Polynom zu $\begin{eqnarray*} T \end{eqnarray*}$ ist.

Die erste Aussage habe ich (glaube ich) gezeigt, bei der zweiten fällt mir aber nichts Besseres ein, als die große Summe von Produkten auszuschreiben... Hat jemand vielleicht eine Idee?

Cordovan

17.04.2010, 17:09

Cordovan

Auf diesen Beitrag antworten »

Ich kann ja mal schreiben, wie ich (vermeintlich) Aufgabe 1 gezeigt habe. Vielleicht findet ja jemand einen Fehler. Also:

Klarerweise ist $\begin{eqnarray*} |p(t_i)-\tilde p(t_i)|=|f_i-\tilde f_i|\leq \|F-\tilde F\|_\infty \end{eqnarray*}$ , also ist $\begin{eqnarray*} c(t_i)\leq 1 \end{eqnarray*}$ .
Anderseits ist das Maximum immer größer gleich dem Wert einer speziellen Wahl von $\begin{eqnarray*} F \end{eqnarray*}$ und $\begin{eqnarray*} \tilde F \end{eqnarray*}$ . Wähle ich diese also so, dass $\begin{eqnarray*} (\forall i\in\{1,\ldots,n\}):\ \|F-\tilde F\|=|f_i-\tilde f_i| \end{eqnarray*}$ gilt, dann folgt $\begin{eqnarray*} c(t_i)\geq 1 \end{eqnarray*}$ . Fertig.

Ist das richtig?

Cordovan

18.04.2010, 14:28

tigerbine

Auf diesen Beitrag antworten »

Hallo Cordovan,

ich komme in die Notation noch nicht so ganz rein, um den Beweis prüfen zu können.

$\begin{eqnarray*} F \end{eqnarray*}$ soll der Vektor sein, der die Funktionswerte der Funktion $\begin{eqnarray*} f \end{eqnarray*}$ an den Stellen $\begin{eqnarray*} x_1 \end{eqnarray*}$ bis $\begin{eqnarray*} x_n \end{eqnarray*}$ enthält? D.h. wenn man die Funktionswerte exakt übergeben könnte wäre dies ein "Inputvektor".

Nun ist dies i.A. ja nicht möglich. D.h. allein durch die Eingabe wird der Datensatz schon gestört sein. Das wollen wir hier aber nur für den Wertevektor $\begin{eqnarray*} F \end{eqnarray*}$ betrachten. Der Knotenvektor $\begin{eqnarray*} T \end{eqnarray*}$ kann exakt übergeben werden [wir haben z.B. nur an ganzzahligen Stellen interpoliert]

Unter einer Konditionierung des Problems hätte ich nun eher so etwas verstanden

$\begin{eqnarray*} \frac{\|\tilde p(t) - p(t) \|_{\infty}}{\|p(t) \|_{\infty}} \leq c \cdot \frac{\|\tilde F -F \|_{\infty}}{\|F \|_{\infty}} \end{eqnarray*}$

Was mir bei dir nicht klar ist, was mit $\begin{eqnarray*} \max F, \tilde F \end{eqnarray*}$ gemeint ist.

18.04.2010, 18:32

Cordovan

Auf diesen Beitrag antworten »

Hallo tigerbine!

Danke, dass du schreibst! Also:

Zitat:

$\begin{eqnarray*} F \end{eqnarray*}$ soll der Vektor sein, der die Funktionswerte der Funktion $\begin{eqnarray*} f \end{eqnarray*}$ an den Stellen $\begin{eqnarray*} x_1 \end{eqnarray*}$ bis $\begin{eqnarray*} x_n \end{eqnarray*}$ enthält? D.h. wenn man die Funktionswerte exakt übergeben könnte wäre dies ein "Inputvektor".

Ja, genau (du meinst die Stellen $\begin{eqnarray*} t_1 \end{eqnarray*}$ bis $\begin{eqnarray*} t_n \end{eqnarray*}$ , richtig?).

Zitat:

Nun ist dies i.A. ja nicht möglich. D.h. allein durch die Eingabe wird der Datensatz schon gestört sein. Das wollen wir hier aber nur für den Wertevektor $\begin{eqnarray*} F \end{eqnarray*}$ betrachten. Der Knotenvektor $\begin{eqnarray*} T \end{eqnarray*}$ kann exakt übergeben werden [wir haben z.B. nur an ganzzahligen Stellen interpoliert]

Richtig.

Zitat:

Was mir bei dir nicht klar ist, was mit $\begin{eqnarray*} \max F, \tilde F \end{eqnarray*}$ gemeint ist.

Ich schätze, dass das Maximum über alle Belegungen von F und \tilde F bei festem Knotenvektor T genommen wird. Dabei wird die Supremumsnorm im Nenner zwar groß, allerdings beträgt der Zähler ja $\begin{eqnarray*} |p(t)-\tilde p(t)|=|\sum_{i=1}^n(f_i-\tilde f_i)\ell_i(t)| \end{eqnarray*}$ , so dass das Maximum (wahrscheinlich?) tatsächlich existiert.

Hast du eine Idee?

Cordovan

18.04.2010, 18:47

tigerbine

Auf diesen Beitrag antworten »

ersetzte x durch t. Augenzwinkern

Dass hieße dann ja, dass man diese Kondition unabhängig von der zu interpolierenden Funktion betrachten will, oder?

$\begin{eqnarray*} c(t):=\max_{F,\tilde F}\frac{|p(t)-\tilde p(t)|}{\|F-\tilde F\|_\infty} =\max_{F,\tilde F}\frac{|p(t)-\tilde p(t)|}{\max_{i=1,...,n} |f_i-\tilde f_i|} \end{eqnarray*}$

Warum hast du in deinem Beweis [Post 2] nun $\begin{eqnarray*} t_i \end{eqnarray*}$ betrachtet und nicht alle t?

18.04.2010, 18:47

tigerbine

Auf diesen Beitrag antworten »

ersetzte x durch t. Augenzwinkern

Zitat:

$\begin{eqnarray*} c(t_i)=1 \end{eqnarray*}$

Dann ergibt sich

$\begin{eqnarray*} \frac{|f_i-\tilde f_i|}{\max_{i=1,...,n} |f_i-\tilde f_i|} \leq 1 \end{eqnarray*}$

Dabei wurde natürlich oben und unten der gleiche Funktionswertevektor vorausgesetzt. Jetzt ist die Frage mit dem Maximum. Da hast du nur unten variiert, oder?

18.04.2010, 19:09

Cordovan

Auf diesen Beitrag antworten »

Im zweiten Post habe ich nur die erste Aussage gezeigt, also $\begin{eqnarray*} c(t_i)=1 \end{eqnarray*}$ . Daher habe ich nur t_i betrachtet.

Zitat:

Dass hieße dann ja, dass man diese Kondition unabhängig von der zu interpolierenden Funktion betrachten will, oder?

Richtig, das soll ein allgemeines Konditionsmaß für Lagrange-Interpolation sein.

Zitat:

Dabei wurde natürlich oben und unten der gleiche Funktionswertevektor vorausgesetzt. Jetzt ist die Frage mit dem Maximum. Da hast du nur unten variiert, oder?

Ich habe für die Abschätzung nach unten eben eine bestimmte Wahl von $\begin{eqnarray*} F \end{eqnarray*}$ und $\begin{eqnarray*} \tilde F \end{eqnarray*}$ getroffen... Das Maximum muss ja größer gleich jeder speziellen Wahl sein.

Cordovan

18.04.2010, 19:41

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Original von Cordovan
Ich habe für die Abschätzung nach unten eben eine bestimmte Wahl von $\begin{eqnarray*} F \end{eqnarray*}$ und $\begin{eqnarray*} \tilde F \end{eqnarray*}$ getroffen... Das Maximum muss ja größer gleich jeder speziellen Wahl sein.

Cordovan

Das meinte ich nicht. Meine Frage war, ob man dann nicht auch den Zähler anpassen müßte. Denn die Werte dort hängen doch auch von $\begin{eqnarray*} F, \tilde F \end{eqnarray*}$ ab?

Wenn man aber alle Funktion zur Verfügung hat, dann aber doch auch die konstanten Funktionen. [ Dann ist der Bezug Zähler, Nenner imho klarer] Für die ist das was du gefordert hast doch sichergestellt, wir sollten zu Sicherheit noch $\begin{eqnarray*} F \neq \tilde F \end{eqnarray*}$ fordern. Was ja eigentlich klar ist.

Für den zweiten Teil... verwirrt

Da die Stützstellen gleich bleiben...

$\begin{eqnarray*} p(t)=\sum_{k=1}^{n} f_k\cdot l_k(t) \end{eqnarray*}$ , $\begin{eqnarray*} \tilde p(t)=\sum_{k=1}^{n} \tilde f_k\cdot l_k(t) \end{eqnarray*}$

$\begin{eqnarray*} p(t) - \tilde p(t)=\sum_{k=1}^{n} \left(f_k- \tilde f_k \right) \cdot l_k(t) \end{eqnarray*}$

Damit hätten wir dann

$\begin{eqnarray*} c(t):=\max_{F,\tilde F}\frac{|p(t)-\tilde p(t)|}{\|F-\tilde F\|_\infty} =\max_{F,\tilde F}\frac{|\sum_{k=1}^{n} \left(f_k- \tilde f_k \right) \cdot l_k(t)|}{\max_{i=1,...,n} |f_i-\tilde f_i|} \end{eqnarray*}$

Ich überlege, ob man nicht wieder das mit den konstanten Funktionen machen kann. Stellen wir noch sicher, dass $\begin{eqnarray*} f > \tilde f \end{eqnarray*}$ Dann erhalten wir für so einen Fall doch

$\begin{eqnarray*} \max_{F,\tilde F}\frac{|\sum_{k=1}^{n} \left(f_k- \tilde f_k \right) \cdot l_k(t)|}{\max_{i=1,...,n} |f_i-\tilde f_i|} \geq |\sum_{k=1}^{n} l_k(t)| \end{eqnarray*}$

Wie man den Betrag da nun reinbekommt, weiß ich gerade nicht.

Hier mal noch ein Link, der den Zusammenhang etwas anders herleitet. http://www.ipvs.uni-stuttgart.de/abteilu.../Teil2_1-24.pdf

18.04.2010, 21:06

Cordovan

Auf diesen Beitrag antworten »

Gut, dann sind wir uns ja über den ersten Teil einig smile

Beim Zweiten: so etwas ähnliches hatte ich mir auch überlegt. Ich glaube aber, dass die konstanten Funktionen keine ausreichende Abschätzung ergeben - den Betrag kriegt man nicht in die Summe rein. Es muss einen anderen Weg geben.

Deinem Link bin ich gefolgt. Er leitet ein ähnliches Resultat her, aber im Prinzip ist es ja nur ein Beispiel, das gerechnet wird. Sieht so aus, als müsste man tatsächlich die Definition der $\begin{eqnarray*} \ell_i \end{eqnarray*}$ einsetzen und irgendwie "rumwurschteln"...

Cordovan

Neue Frage »

Antworten »

Lagrange-Interpolation mit Störung

Verwandte Themen