Dividierte Differenzen

13.01.2011, 13:59

StAnger_

Auf diesen Beitrag antworten »

Dividierte Differenzen

Hallo, folgende Aufgabe:

Gegeben ist eine Wertetabelle eines Polynoms vierten Grades:
x 1 2 3 4 5 6 7 8 9 10 11
f(x) 8 23 33 37 31 28 18 8 2 5 23

Einer der Funktionswerte ist falsch und soll korrigiert werden!

Hinweis: Überlegen sie sich, wie ein Fehler sich im Schema der dividierten Differenzen auswirkt

Ich hab keine Ahnung wie ich das machen soll. Das Schema der dividierten Differenzen ist ja rekursiv, demnach müsste man für die Koeffizienten falsche Werte heraus bekommen, sobald man bei dem falschen Funktionswert angekommen ist, aber wie soll man diesen Funktionswert finden?
Bitte um Hilfe!!!

13.01.2011, 14:13

tigerbine

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen
Was bedeutet es, dass das Polynom Grad 4 hat?

Wie viele Knoten sind angegeben?

Was berechnet man mit den dividierten Differenzen?

16.01.2011, 19:08

StAnger_

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen
Ok wenn das Polynom 4. Grad hat reichen 5 Knoten um es anzugeben.
Mit den dividierten Differenzen berechnet man die Koeffizienten des Newotnpolynoms.

Also könnte ich so vorgehen:
1. 5 beliebige Knoten auswählen
2. Polynom berechnen
3. Werte einsetzen und überprüfen
4. Falls ich bei den ausgewählten Knoten, den einen falschen dabei hatte, müssten nun mehrere Funktionswerte falsch sein. Wenn ich mir jetzt 5 andere Knoten wähle müsste ich auf jeden Fall das richtige Polynom rausbekommen.
Falls ich den falschen Knoten nicht dabei hatte kann ich ihn nun korrigieren.

Richtig?

16.01.2011, 19:18

tigerbine

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen

Zitat:

Hinweis: Überlegen sie sich, wie ein Fehler sich im Schema der dividierten Differenzen auswirkt

16.01.2011, 19:43

StAnger_

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen
Hm, funktioniert nicht, so wie ichs versucht hab

Ein Fehlter wirkt sich meiner Meinung nach so aus, dass man halt dann die falschen Koeffizienten ausrechnet, aber wie soll man erkennen, ob sie richtig oder falsch sind...ich komm nicht drauf, wie ich das an dem Schema sehen soll?!?!

16.01.2011, 19:45

tigerbine

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen
Wenn man das Schema nur mit den richtigen Knoten macht, was muss dann alles 0 sein? Denn wir wissen ja, welchen Grad das Polynom hat.

Anzeige

16.01.2011, 20:26

StAnger_

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen
Ich komm nicht drauf unglücklich

unglücklich

16.01.2011, 21:42

tigerbine

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen
Naja, wenn du den Maximalgrad hast, müssen alle weiteren 0 sein, oder?

17.01.2011, 08:55

StAnger_

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen
Ok, aber das bedeutet doch auch, wenn ich das Schema einmal mit den ersten 5 Knoten mach und einmal mit den letzten 5, dass dann eins von beiden Polynomen auf jeden Fall richtig sein muss oder? Das hat bei mir aber nicht funktioniert, ausser ich hab mich völlig verrechnet, das werd ich nochmal nachprüfen!

17.01.2011, 12:41

tigerbine

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen
Sind deine Daten wirklich korrekt, bevor ich weitere Rechnungen anstelle? Bitte noch mal checken. Erst dann füttere ich mein Programm weiter. Die Daten unten sind also unter Vorbehalt.

**********************
Was genau der Prof. nun sehen möchte, kann ich dir nicht sagen. Ich weiß auch nicht, ob ihr das von Hand lösen sollt oder mit PC. Lege ich das IP durch alle Knoten, erhalte ich

Knoten 1 bis 11

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:

Newton-Darstellung  
===============================================================================================
 
Dividierte Differenzen Schema
-----------------------------
 
DD =
  Columns 1 through 4 
    1.0000    8.0000   15.0000   -2.5000
    2.0000   23.0000   10.0000   -3.0000
    3.0000   33.0000    4.0000   -5.0000
    4.0000   37.0000   -6.0000    1.5000
    5.0000   31.0000   -3.0000   -3.5000
    6.0000   28.0000  -10.0000         0
    7.0000   18.0000  -10.0000    2.0000
    8.0000    8.0000   -6.0000    4.5000
    9.0000    2.0000    3.0000    7.5000
   10.0000    5.0000   18.0000         0
   11.0000   23.0000         0         0
  Columns 5 through 8 
   -0.1667   -0.1250    0.1667   -0.0833
   -0.6667    0.7083   -0.3333    0.1111
    2.1667   -0.9583    0.3333   -0.0833
   -1.6667    0.7083   -0.1667    0.0333
    1.1667   -0.1250    0.0333   -0.0056
    0.6667    0.0417   -0.0000         0
    0.8333    0.0417         0         0
    1.0000         0         0         0
         0         0         0         0
         0         0         0         0
         0         0         0         0
  Columns 9 through 12 
    0.0278   -0.0069    0.0014   -0.0002
   -0.0278    0.0056   -0.0009         0
    0.0167   -0.0028         0         0
   -0.0056         0         0         0
         0         0         0         0
         0         0         0         0
         0         0         0         0
         0         0         0         0
         0         0         0         0
         0         0         0         0
         0         0         0         0
 
Interpolationspolynom
---------------------
 
p_10(x)= 
 
         +    8 
         +   15 * [x - 1]   
         -  2.5 * [x - 1] [x - 2]   
         - 0.166667 * [x - 1] [x - 2] [x - 3]   
         - 0.125 * [x - 1] [x - 2] [x - 3] [x - 4]   
         + 0.166667 * [x - 1] [x - 2] [x - 3] [x - 4] [x - 5]   
         - 0.0833333 * [x - 1] [x - 2] [x - 3] [x - 4] [x - 5] [x - 6]   
         + 0.0277778 * [x - 1] [x - 2] [x - 3] [x - 4] [x - 5] [x - 6] [x - 7]   
         - 0.00694444 * [x - 1] [x - 2] [x - 3] [x - 4] [x - 5] [x - 6] [x - 7] [x - 8]   
         + 0.00138889 * [x - 1] [x - 2] [x - 3] [x - 4] [x - 5] [x - 6] [x - 7] [x - 8] [x - 9]   
         - 0.000231481 * [x - 1] [x - 2] [x - 3] [x - 4] [x - 5] [x - 6] [x - 7] [x - 8] [x - 9] [x - 10]

[attach]17629[/attach]

Wie erwartet also ein Polynom von zu hohem Grad. Was auffällt, das keine 0er entstehen. Würden die ersten 6 Punkte auf der Funktion vom Grad vier liegen, müßte sich ja eine 0 ergeben beim letzten Koeffizienten.

Knoten 1 bis 5

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

Newton-Darstellung  
===============================================================================================
 
Dividierte Differenzen Schema
-----------------------------
 
DD =
    1.0000    8.0000   15.0000   -2.5000   -0.1667   -0.1250
    2.0000   23.0000   10.0000   -3.0000   -0.6667         0
    3.0000   33.0000    4.0000   -5.0000         0         0
    4.0000   37.0000   -6.0000         0         0         0
    5.0000   31.0000         0         0         0         0
 
Interpolationspolynom
---------------------
 
p_ 4(x)= 
 
         +    8 
         +   15 * [x - 1]   
         -  2.5 * [x - 1] [x - 2]   
         - 0.166667 * [x - 1] [x - 2] [x - 3]   
         - 0.125 * [x - 1] [x - 2] [x - 3] [x - 4]

[attach]17628[/attach]

Packen wir also noch einen Knoten drauf und schauen was passiert:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

Newton-Darstellung  
===============================================================================================
 
Dividierte Differenzen Schema
-----------------------------
 
DD =
    1.0000    8.0000   15.0000   -2.5000   -0.1667   -0.1250    0.1667
    2.0000   23.0000   10.0000   -3.0000   -0.6667    0.7083         0
    3.0000   33.0000    4.0000   -5.0000    2.1667         0         0
    4.0000   37.0000   -6.0000    1.5000         0         0         0
    5.0000   31.0000   -3.0000         0         0         0         0
    6.0000   28.0000         0         0         0         0         0
 
Interpolationspolynom
---------------------
 
p_ 5(x)= 
 
         +    8 
         +   15 * [x - 1]   
         -  2.5 * [x - 1] [x - 2]   
         - 0.166667 * [x - 1] [x - 2] [x - 3]   
         - 0.125 * [x - 1] [x - 2] [x - 3] [x - 4]   
         + 0.166667 * [x - 1] [x - 2] [x - 3] [x - 4] [x - 5]   
 
Weiter mit beliebiger Taste

[attach]17630[/attach]

Somit folgere ich, dass einer der Knoten 1 bis 6 der Ausreißer sein muss. Sonst hätten wir als IP ja ein Polynom vom Grad 4 erhalten. Im Umkehrschluss liegt der Ausreißer nicht in Knoten 7 bis 11. Imho kommt man um Testen nun nicht herum. Man nimmt Knoten 7 hinzu und lässt immer einen anderen Weg.

17.01.2011, 13:28

René Gruber

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen
Man muss nur genau hinschauen - die entscheidende Stelle ist hier:

Zitat:

Original von tigerbine
Dividierte Differenzen Schema
-----------------------------

DD =
Columns 1 through 4
1.0000 8.0000 15.0000 -2.5000
2.0000 23.0000 10.0000 -3.0000
3.0000 33.0000 4.0000 -5.0000
4.0000 37.0000 -6.0000 1.5000
5.0000 31.0000 -3.0000 -3.5000
6.0000 28.0000 -10.0000 0
7.0000 18.0000 -10.0000 2.0000
8.0000 8.0000 -6.0000 4.5000
9.0000 2.0000 3.0000 7.5000
10.0000 5.0000 18.0000 0
11.0000 23.0000 0 0
Columns 5 through 8
-0.1667 -0.1250 0.1667 -0.0833
-0.6667 0.7083 -0.3333 0.1111
2.1667 -0.9583 0.3333 -0.0833
-1.6667 0.7083 -0.1667 0.0333
1.1667 -0.1250 0.0333 -0.0056
0.6667 0.0417 -0.0000 0
0.8333 0.0417 0 0
1.0000 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Das ist sie, die gesuchte Null. Sie besagt, dass die 6 Werte 6 bis 11 auf einer Funktion vierten Grades liegen. Da der Wert darüber aber ungleich Null ist, gilt das für die Werte 5 bis 11 nicht. Zwangsläufig ist Wert 5 der gesuchte Übeltäter.

17.01.2011, 13:40

StAnger_

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen
Also die Daten hab ich nochmal überprüft, die sind korrekt. Danke erst mal für die große Mühe. Knoten 5 hatte ich von Anfang an schon vermutet, aber das hilft ja nix. Aber das heißt doch, wenn ich beim Schema der dividierten Differenzen die Knoten 1,2,3,4,6 verwende und damit das Polynom berechne müsste ich doch das richtige rausbekommen...genauso wenn ich die Knoten 7,8,9,10,11 verwenden würde, oder hab ich da 'nen Denkfehler. Solange ich Knoten 5 nicht verwende müsste ich doch immer das gleiche richtige Polynom rausbekommen???

P.S. Wir sollen es übrigens von Hand lösen!

17.01.2011, 13:58

René Gruber

Auf diesen Beitrag antworten »

Ich würde nur die iterierten Differenzen betrachten, also ohne die Vorfaktoren, die tigerbine in Hinblick auf die Interpolationspolynome benutzt:

$\begin{eqnarray*} \Delta^{(m)}y_k := \Delta^{(m-1)}y_{k+1} - \Delta^{(m-1)}y_k \end{eqnarray*}$ für $\begin{eqnarray*} m\geq 1,k\geq 1 \end{eqnarray*}$

mit Start $\begin{eqnarray*} \Delta^{(0)}y_k := y_k \end{eqnarray*}$ . Eine Abweichung $\begin{eqnarray*} \varepsilon \end{eqnarray*}$ in $\begin{eqnarray*} y_k \end{eqnarray*}$ äußert sich dann gemäß dieser Rekursion in einer Abweichung $\begin{eqnarray*} (-1)^m\varepsilon \end{eqnarray*}$ in $\begin{eqnarray*} \Delta^{(m)}y_k \end{eqnarray*}$ , sofern die nachfolgenden Werte $\begin{eqnarray*} y_{k+1},y_{k+2},\ldots \end{eqnarray*}$ alle intakt bleiben.

Im vorliegenden Fall ergibt die Tabelle

$\begin{eqnarray*} \begin{array}{|r|r|r|r|r|r|r|} \hline k & y_k & \Delta^{(1)}y_k& \Delta^{(2)}y_k & \Delta^{(3)}y_k & \Delta^{(4)}y_k & \Delta^{(5)}y_k \\ \hline\hline 1 & 8 & 15 & -5 & -1 & -3 & 20 \\ \hline 2 & 23 & 10 & -6 & -4 & 17 & -40 \\ \hline 3 & 33 & 4 & -10 & 13 & -23 & 40 \\ \hline 4 & 37 & -6 & 3 & -10 & 17 & -20 \\ \hline 5 & 31 & -3 & -7 & 7 & -3 & 4 \\ \hline 6 & 28 & -10 & 0 & 4 & 1 & 0 \\ \hline 7 & 18 & -10 & 4 & 5 & 1 & \\ \hline 8 & 8 & -6 & 9 & 6 & & \\ \hline 9 & 2 & 3 & 15 & & & \\ \hline 10 & 5 & 18 & & & & \\ \hline 11 & 23 & & & & & \\ \hline \end{array} \end{eqnarray*}$

Die Abweichung $\begin{eqnarray*} \Delta^{(5)}y_5 = 4 \end{eqnarray*}$ gegenüber dem erwarteten Wert $\begin{eqnarray*} \Delta^{(5)}y_k = 0 \end{eqnarray*}$ bei einem wirklichen Polynom vierten Grades lässt auf die Abweichung $\begin{eqnarray*} (-1)^5 \cdot 4 = -4 \end{eqnarray*}$ gegenüber dem tatsächlichen fünften Wert $\begin{eqnarray*} \tilde{y}_5 \end{eqnarray*}$ schließen. Also ist $\begin{eqnarray*} y_5-\tilde{y}_5 = -4 \end{eqnarray*}$ , der gesuchte tatsächliche Wert ist $\begin{eqnarray*} \tilde{y}_5 = y_5+4 = 31+4 = 35 \end{eqnarray*}$ .

P.S.: Die obige Tabelle kann man ganz gut auch von Hand eintragen - bei diesen bloßen Differenzen ganzer Zahlen rechnet man sich nun nicht gerade kaputt. Augenzwinkern

Augenzwinkern

17.01.2011, 14:06

StAnger_

Auf diesen Beitrag antworten »

Sorry, hatte vergessen zu erwähnen, dass wir das Polynom auch angeben sollen, dafür hilft mir die letzte Tabelle ja leider nicht viel weiter, aber trotzdem danke für die Alternative smile

smile

17.01.2011, 14:11

René Gruber

Auf diesen Beitrag antworten »

Achso, das ist natürlich was anderes. Mein Vorschlag war darauf optimiert, nur den "falschen" Funktionswert aufzuspüren und zu korrigieren. Augenzwinkern

Augenzwinkern

17.01.2011, 14:12

StAnger_

Auf diesen Beitrag antworten »

Ja, sorry, war ja mein Fehler, aber ihr beiden habt mir wirklich weitergeholfen. Danke!!!

17.01.2011, 14:48

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von StAnger_
Ja, sorry, war ja mein Fehler, aber ihr beiden habt mir wirklich weitergeholfen. Danke!!!

Trotzdem ist natürlich aus tigerbines Tabelle (oder meiner, Zeile 6) bereits das Interpolationspolynom ablesbar - in Hornerschema-Schreibweise:

$\begin{eqnarray*} f(x) = 28 + (x-6) \cdot \left( -10 + (x-7) \cdot \left( \frac{0}{2} + (x-8) \cdot \left( \frac{4}{6} + (x-9) \cdot \frac{1}{24} \right) \right) \right) \end{eqnarray*}$

17.01.2011, 15:49

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Das ist sie, die gesuchte Null.

Glatt übersehen. Wir bekommen dann z.B. das Schema durch die Knoten 1bis 4, 6 und 7. Man sieht nun dort auch die "führende 0".

code:

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

Dividierte Differenzen Schema
-----------------------------
 
DD =
    1.0000    8.0000   15.0000   -2.5000   -0.1667    0.0417    0.0000
    2.0000   23.0000   10.0000   -3.0000    0.0417    0.0417         0
    3.0000   33.0000    4.0000   -2.8333    0.2500         0         0
    4.0000   37.0000   -4.5000   -1.8333         0         0         0
    6.0000   28.0000  -10.0000         0         0         0         0
    7.0000   18.0000         0         0         0         0         0

17.01.2011, 20:56

StAnger_

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen

Zitat:

Original von René Gruber
Man muss nur genau hinschauen - die entscheidende Stelle ist hier:

Zitat:

Original von tigerbine
Dividierte Differenzen Schema
-----------------------------

DD =
Columns 1 through 4
1.0000 8.0000 15.0000 -2.5000
2.0000 23.0000 10.0000 -3.0000
3.0000 33.0000 4.0000 -5.0000
4.0000 37.0000 -6.0000 1.5000
5.0000 31.0000 -3.0000 -3.5000
6.0000 28.0000 -10.0000 0
7.0000 18.0000 -10.0000 2.0000
8.0000 8.0000 -6.0000 4.5000
9.0000 2.0000 3.0000 7.5000
10.0000 5.0000 18.0000 0
11.0000 23.0000 0 0
Columns 5 through 8
-0.1667 -0.1250 0.1667 -0.0833
-0.6667 0.7083 -0.3333 0.1111
2.1667 -0.9583 0.3333 -0.0833
-1.6667 0.7083 -0.1667 0.0333
1.1667 -0.1250 0.0333 -0.0056
0.6667 0.0417 -0.0000 0
0.8333 0.0417 0 0
1.0000 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Das ist sie, die gesuchte Null. Sie besagt, dass die 6 Werte 6 bis 11 auf einer Funktion vierten Grades liegen. Da der Wert darüber aber ungleich Null ist, gilt das für die Werte 5 bis 11 nicht. Zwangsläufig ist Wert 5 der gesuchte Übeltäter.

Könntest du mir nochmal erklären warum man an dieser Null erkennt das die Knoten 6 bis 11 auf einem Polynom 4. Grades liegen und man an der 0.0333 sieht, dass Knoten 5 nicht auf diesem Polynom liegen kann?

18.01.2011, 01:15

tigerbine

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen
[WS] Polynominterpolation - Beispiele

Bauen wir das Schema doch mal von unten auf. Du deckst mal alles oberhalb der Nullzeile ab. Dann bekommst du ja das Schema für die Knoten 6 bis 11. Ganz extrem fangen wir mit dem lesen im Knoten 11 an. Dann kommt immer einer dazu. im Knoten 7 haben wir dann 5 Knoten, also ein IP vom Maxgrad 4. Nun kommt knoten 6 hinzu. Das IP hat aber wieder den Maxgrad 4. Die Koeffizienten ändern sich, da wir ja immer von oben nach unten die (x-x0) etc. Aufbauen. Beim Knoten 5 erhöht sich der Grad des IPs wieder. Daher muss er der gesuchte Knoten sein.

18.01.2011, 07:52

StAnger_

Auf diesen Beitrag antworten »

RE: Dividierte Differenzen
Ahhhhh, ok. Vielen Dank!!!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »