[WS] Polynominterpolation - Beispiele

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[WS] Polynominterpolation - Beispiele
Gliederung

  1. Datensatz 1
    1a. Lagrange-Darstellung
    1b. Newton-Darstellung
    1c. Monom-Darstellung

  2. Auslesen der Informationen aus
    2a. Schema der dividierte Differenzen (Neville)
    2b. Neville-Schema
    2c. vollständiges Hornerschema

  3. Aitken-Reihenfolge der Knoten
    3a. Schema der dividierten Differenzen (Aitken)
    3b. Aitken-Schema

  4. Hermite-Interpolation
    4a. Straßenlaternen-Aufgabe

  5. Richardson-Extrapolation zum Limes
    5a. Numerische Realisierung der l'Hospitalschen Regel
    5b. Numerische Differentiation

  6. Shamir's Secret Sharing

  7. Kleine matlab-files
    7a. Berechnung Interpolationspolynom
    7b. Berechnung vollst. Hornerschema


Die Theorie befindet sich in einem eigenen Workshop.

Fragen & Anregungen bitte hier posten.
tigerbine Auf diesen Beitrag antworten »
1. Datensatz 1
Es seien folgende Knoten und zugehörigen Funktionswerte gegeben:





Bestimme das Interpolationspolynom!
tigerbine Auf diesen Beitrag antworten »
1a. Lagrange-Darstellung
Gemäß der Definition erhalten wir:































tigerbine Auf diesen Beitrag antworten »
1b. Newton-Darstellung
Gemäß der Darstellung mit dividierten-Differenzen (Neville-Reihenfolge) erhalten wir:

















tigerbine Auf diesen Beitrag antworten »
1c. Monom-Darstellung
diese erhalten wir entweder aus (1a) oder(1b) durch ausmultiplizieren und zusammenfassen.

tigerbine Auf diesen Beitrag antworten »
2. Auslesen der Informationen aus...
In diesem Abschnitt soll erläutert werden, welche weiteren Informationen in den versch. Schematas enthalten sind.
 
 
tigerbine Auf diesen Beitrag antworten »
2a. Schema der dividierten Differenzen








Mit dem Datensatz also:



Nun bauen wir das mal Schrittweise auf, d.h. nehmen nach un nach einen Knoten hinzu.









D.h. wir interpolieren immer einen Knoten mehr. Dabei ist die Reihenfolge zu beachten. . Vergleiche dazu auch die Grafik:



Doch es steckt noch mehr Information in dem Schema. wir können zu jeder zusammenhängenden Knoten Auswahl das zugehörige Interpolationspolynom ablesen:

Ein Knoten:









Zwei Knoten:









Drei Knoten:








Vier Knoten:





tigerbine Auf diesen Beitrag antworten »
2b. Neville-Schema








Dabei bedeuten die Indizes: interpoliert die Knoten


Mit dem Datensatz also:



Und wieder das schon bekannte Bild:



Oder in einer matlab-Variante (dabei wurden die verschiedenen Funktionswerte an der Stelle x=1 markiert):

[attach]8611[/attach]
tigerbine Auf diesen Beitrag antworten »
2c. Vollständiges Hornerschema
Nun wollen wir das erhaltene Interpolationspolynom an der Stelle auswerten. Dabei gilt für





Einmal ganz ausführlich






















Das ganze als vollständiges Hornerschema notiert:











code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
]vollständiges Hornerschema
==========================
H =
     1    -2     3    -1
     1    -3     6    -7
     1    -4    10     0
     1    -5     0     0
     1     0     0     0
 
Auswertung der Funktion und ihrer Ableitungen
---------------------------------------------
p^(0)_3(-1)=       -7 
p^(1)_3(-1)=       10 
p^(2)_3(-1)=      -10 
p^(3)_3(-1)=        6 
 
Taylor-Polynom-Darstellung von p
--------------------------------
p_3(x)= -7 + 10 (x + 1)^1 - 5 (x + 1)^2 + 1 (x + 1)^3 
tigerbine Auf diesen Beitrag antworten »
3. Aitken-Reihenfolge der Knoten
Bei der Neville-Reihenfolge wurde das System der Knoten wie folgt erweitert:



Desweiteren konnte man aus dem Schema noch die Interpolationspolynome für jede zusammenhängende Teilmenge der Knoten ablesen. Bei der Aitken-Reihenfolge werden hingegen in k zusammenhängende Knoten und ein weiterer interpoliert. Ich führe sie hier auf, weil diese Darstellung des IPs und der dividierten Differenzen z.B. bei der Hermite-Interpolation von Bedeutung sein wird. Der Beweis der folgenden Rekursionsvorschriften ist analog zu dem der Neville Reihenfolge zu führen.


3a. Dividierte Differenzen - Aitken-Reihenfolge











tigerbine Auf diesen Beitrag antworten »
3b. Aitken-Schema





Dabei interpoliert die Knoten und









tigerbine Auf diesen Beitrag antworten »
4a. Straßenlaternen-Aufgabe
Als Rechenbeispiel zur Hermiteschen-Interpolationsaufgabe soll der Klassiker der Straßenlaterne einmal gerechnet werden.

Eine Straßenlaterne bestehe aus einem senkrechten Pfosten, an den ein parabelförmiger Bogen AB befestig ist, der an seinem freien Ende eine Lampe trägt. Aus technischen Gründen wird verlangt, das die beiden Enden des Bogens einen vorgegebenen Abstand (1m) über die über die Straße haben müssen und zwar und . Außerdem soll die Lampe unter einem Winkel die Straße beleuchten. Man vgl. hierzu die Abbildung. Gesucht ist die genaue Lage des parabelförmigen Bogens, so dass die oben genannten Anforderungen erfüllt sind.

Lösung:

Gesucht ist hier also ein Polynom mit folgenden Eigenschaften:

  • (Newton-Darstellung des IPs)












tigerbine Auf diesen Beitrag antworten »
5. Richardson-Extrapolation zum Limes
Gesucht ist hier dir nicht direkt berechenbare Größe . Zur Annäherung von berechnet man für gewisse Werte , und nimmt den Wert des zugehörigen Interpolytionspolynoms zu als Schätzung für.
tigerbine Auf diesen Beitrag antworten »
5a. Numerische Realisierung der l'Hospitalschen Regel
Beispiel:



Man setzt

und berechnet einige Funktionswerte.







Mit Bestimmung des IPs folgt:

tigerbine Auf diesen Beitrag antworten »
5b. Numerische Differentiation
Sei f eine differenzierbare Funktion, so ist ihre Ableitung wie folgt definiert (Differentialquotient):



Daraus erhält man daraus die Funktion:



und interessiert sich für den Wert an der Stelle h=0. Wieder ist es möglich für einen Datensatz zu erzeugen und das daraus erhaltene Interpolationspolynom an der Stelle h=0 zu extrapolieren. Aufgrund von Auslöschungseffekten wird man jedoch eher den zentralen Differenzenquotienten



verwenden.
tigerbine Auf diesen Beitrag antworten »
6. Shamir's Secret Sharing
Wir wir gesehen haben, wird durch n paarweise verschiedene Knoten und zug. Funktionswerte (Punkte) eindeutig ein interpolierendes Polynom festgelegt. Durch 2 Punkte wird eine Gerade festgelegt, jedoch gibt es unendlich viele Polynome 2ten Grades, sie durch diese 2 Punkte verlaufen. Fügt man jedoch noch genau einen Punkt hinzu, so gibt es nur genau ein Polynom 2ten Grades.

Wie kann man das für das Mehrschlüsselprinzip ausnutzen?

  • Kennt man die Koordinaten alles 3 Punkte, so läßt sich das Polynom eindeutig bestimmen und man kann für eine beliebige Stelle den zugehörigen Funktionswert bestimmen.

  • Um ein Geheimnis S zwischen n Personen zu teilen, so dass eine Teilmenge von Ihnen in der Lage sind, dass Geheimnis zu rekonstruieren, generiert man ein Polynom vom Grad (m-1), dass Durch den Punkt (0;S) geht.

  • Dann gibt man jeder der n Personen "vertraulich" die Koordinaten eines "persönlichen Punktes" auf der Kurve, so dass keine 2 Personen denselben Punkt besitzen.

  • Eine Gruppe von m Personen hat nun immer genügend Punkte, um das Polynom eindeutig zu bestimmen. Setzt man x=0 ein, so erhält man als Ergebnis das Geheimnis s.

  • Kommen nur (m-1) Personen zusammen, so kann das Geheimnis nicht entschlüsselt werden, da es immer noch unendlich viele Polynome gibt, die durch diese Punkte verlaufen.

  • Shamir's Secret Sharing ist damit informationstheoretisch sicher.

Vorgehensweise bei der Verteilung des Geheimnisses
  1. Ausgangspunkt ist das Polynom



  2. Ziehe ganzzahlige Zufallszahlen für die Koeffizienten . Gemeinsam mit S, ist die Kurve nun eindeutig definiert.

  3. Verteile die Punkte an die n Personen.

  4. Zerstöre und S. Verwendung von ganzen Zahlen zur vermeidung von Rundungseffekten.

Eigenschaften:
  • Die Zahl n der zugelassenen personen ist jederzeit erweiterbar, ohne bisherige Teilschlüssel ändern zu müssen.

  • Teilschlüssel sind änderbar (Verlust, Entzug), ohne den Gesamtschlüssel S zu ändern.

  • Hierarchien sind durch Mehrfach-Teilschlüssel modelierbar.
tigerbine Auf diesen Beitrag antworten »
7. matlab-file
In der Sammlung befindet sich ein kleiner matlab Rechenknecht zur Überprüfung der verschiedenen Darstellungen des IPs zu gegebenem Datensatz und weitere Helfer zu den hier behandelten Themen. Wer nicht über matlab verfügt, kann sich hier über die Freeware GNU Octave informieren. Das file läuft auch dort. Die Plotausgabe muss jedoch angepasst werden.

http://www.smileygarden.de/smilie/Computer/43.gif
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »