Newtonsche Darstellung Beweis < Numerik < Hochschule < Mathe < Vorhilfe
|
Hallo, ich bin seit gestern dabei,folgenden Abschnitt aus meinem Skript zu verstehen:
______________________________________________________________________
Behauptung
___________
Sei $D:= [mm] \{ 0, 1, \ldots, n \}$
[/mm]
Das Lagrangsche Interpolationspolynom zu den Punkten [mm] $(x_{i}, y_{i})$ [/mm] für $ i [mm] \in [/mm] D$ lässt sich bezüglich. der Newtonchen Polynombasis schreiben in der Form:
$p(x) = [mm] \sum\limits_{i = 0}^{n} y[x_{0}, \ldots, x_{i} N_{i} [/mm] (x)$
Dabei bezeichnen [mm] $y[x_{0}, \ldots, x_{i}]$ [/mm] die zu den Punkten [mm] $(x_{i}, y_{i})$ [/mm] gehörenden spg. "dividierten Differenzen", welche rekursiv definiert sind durch
$i = 0, [mm] \ldots, [/mm] n$ : [mm] $y[x_{i}]:= y_{i}$
[/mm]
$k = 1, [mm] \ldots, [/mm] n - i$: [mm] $y[x_{i}, \ldots, x_{i + k}] [/mm] := [mm] \frac{y[x_{i + 1}, \ldots, x_{i + k }] - y[x_{i}, \ldots, x_{i + k - 1}]}{x_{i + k} - x_{i}}$
[/mm]
Beweis per Induktion
______
Es bezeichne [mm] $p_{i, i + k} \in P_{k}$ [/mm] das Polynom , welches die Punkte [mm] $(x_{i}, y_{i}), \ldots, (x_{i + k}, y_{i + k})$ [/mm] interpoliert.
Speziell ist also [mm] $p_{0, n } [/mm] = p$ das gesuchte Interpolationspolynom.
Wir zeigen [mm] $p_{i, i + k}(x) [/mm] = [mm] y[x_{i}] [/mm] + [mm] y[x_{i}, x_{i + 1}](x [/mm] - [mm] x_{i}) [/mm] + [mm] \ldots [/mm] + [mm] y[x_{i}, \ldots, x_{i + k }](x [/mm] - [mm] x_{i}) \ldots [/mm] (x - [mm] x_{i + k - 1})$,
[/mm]
was offensichtlich die Aussage des Satzes als Spezialfall beinhaltet.
Der Beweis wird durch Induktion bzgl. der Indexdifferenz $k = (i + k) - i$ geführt.
Für $k = 0$ ist [mm] $p_{i, i} [/mm] = [mm] y_{i} [/mm] = [mm] y[x_{i}], [/mm] i =0, [mm] \ldots, [/mm] n$.
Sei die Behauptung richtig für $ k - 1 [mm] \ge [/mm] 0$.
Konstruktionsgemäß gilt [mm] $p_{i, i + k}(x) [/mm] = [mm] p_{i, i + k - 1}(x) [/mm] + a(x - [mm] x_{i}) \cdot \ldots \cdot [/mm] (x - [mm] x_{i + k - 1})$
[/mm]
Zu zeigen ist also, dass $a = [mm] y[x_{i}, \ldots, x_{i + k}]$. [/mm] Offenbar ist $a$ der Koeffizient von [mm] $x^{k}$ [/mm] in [mm] $p_{i, i + k}(x)$. [/mm] Nach Induktionsannahme ist weiter
[mm] $p_{i, i + k - 1}(x) [/mm] = [mm] \ldots [/mm] + [mm] y[x_{i}, \ldots, x_{i + k - 1}] \cdot x^{k - 1}$,
[/mm]
[mm] $p_{i + 1, i + k }(x) [/mm] = [mm] \ldots [/mm] + [mm] y[x_{i + 1}, \ldots, x_{i + k }] \cdot x^{k - 1}$,
[/mm]
wobei [mm] "$\ldots$" [/mm] für Polynomanteile vom Grad kleiner oder gleich $ k - 2$ steht. Wie man leicht verifiziert, interpoliert das durch
$q(x) = [mm] \frac{(x - x_{i}) p_{i + 1, i + k}(x) - (x - x_{i + k}) p_{i, i + k - 1} (x)}{x_{i + k} - x_{i}} [/mm] = [mm] p_{i, i + k - 1}(x) [/mm] + (x - [mm] x_{i}) \frac{p_{i + 1, i + k}(x) - p_{i, i + k - 1}(x)}{x_{i + k} - x_{i}}$
[/mm]
gegebene Polynom $q [mm] \in P_{k}$ [/mm] die $ k + 1$ Stützpunkte [mm] $(x_{j}, y_{j}), [/mm] j = i, [mm] \ldots, [/mm] i + k$.
Wegen der Eindeutigkeit des Interpolationspolynoms ist dann notwendig $q [mm] \equiv p_{i, i + k}$.
[/mm]
Der führende Koeffizient ist [mm] $p_{i, i + k}(x)$ [/mm] ist demnach
$a = [mm] \frac{y[x_{i + 1}, \ldots, x_{i + k}] - y[x_{i}, \ldots, x_{i + k - 1}]}{x_{i + k} - x_{i}} [/mm] = [mm] y[x_{i}, \ldots, x_{i + k }]$, [/mm] was den Beweis vervollständigt.
______________________________________________________________________
Die Aussage des Satzes habe ich verstanden, aber den Beweis verstehe ich nicht ganz.
Man möchte durch vollständige Induktion zeigen, dass [mm] $p_{i, i + k}(x) [/mm] = [mm] y[x_{i}] [/mm] + [mm] y[x_{i}, x_{i + 1}](x [/mm] - [mm] x_{i}) [/mm] + [mm] \ldots [/mm] + [mm] y[x_{i}, \ldots, x_{i + k }](x [/mm] - [mm] x_{i}) \ldots [/mm] (x - [mm] x_{i + k - 1})$ [/mm] gilt.
Aber zum weiteren Verlauf des Beweises habe ich ein paar Fragen:
1. Frage
_________
Warum wird die Induktion mit der Indexdifferenz $k = (i + k) - i$ geführt ? Worin liegt der Vorteil, das zu verkomplizieren?
2. Frage
_________
Warum ist $a$ der Koeffizient von [mm] $x^{k}$ [/mm] in [mm] $p_{i, i + k }(x)$ [/mm] ? Ich weiß nicht genau, was man damit meint. Ich habe gestern versucht, mir das zu erschließen, aber es kommt einfach nicht bei mir an.
Sollte $a$ nicht der Koeffizient von [mm] $N_{k}(x)$ [/mm] sein? Wobei ich mit [mm] $N_{k}$ [/mm] den $k$ - ten Newtonschen Basispolynom meine.
Und da sich mir das nicht erschließt, verstehe ich auch nicht die
nächsten Zeilen, also:
"Nach Induktionsannahme ist weiter
[mm] $p_{i, i + k - 1}(x) [/mm] = [mm] \ldots [/mm] + [mm] y[x_{i}, \ldots, x_{i + k - 1}] \cdot x^{k - 1}$,
[/mm]
[mm] $p_{i + 1, i + k }(x) [/mm] = [mm] \ldots [/mm] + [mm] y[x_{i + 1}, \ldots, x_{i + k }] \cdot x^{k - 1}$"
[/mm]
Soviel zu meinen Fragen. Die restlichen Fragen versuche ich gleich mal selbst zu beantworten. Aber das sind die Fragen, die ich mir alleine nicht beantworten kann..
Würde mich freuen, wenn jemand Lust hätte, mir zu helfen :)
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
Zunächst erst mal etwas Allgemeines zum Lagrange-Polynom. Es gibt einfachere Darstellungen für die Konstruktion des Interpolationspolynoms, die aber auch Nachteile haben.
Beispiel: i | [mm] x_i [/mm] | [mm] y_i
[/mm]
-------+---------+------
0 | 1 | 21
1 | 2 | 36
2 | 3 | 43
"symmetrischer" Ansatz:
[mm] P(x)=y_0 \bruch{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}+y_1 \bruch{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}+y_2 \bruch{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}
[/mm]
Die Summanden sind alle gleich aufgebaut: Der mit dem Index i hat als Vorfaktor [mm] y_i, [/mm] der Zähler besteht aus allen Linearfaktoren [mm] (x-x_j), [/mm] wobei der i-te fehlt, der Nenner aus allen Faktoren [mm] (x_i-x_j), [/mm] wobei ebenfalls der i-te fehlt (also i [mm] \ne [/mm] j). Mann kann alles sofort hinschreiben, für obiges Beispiel
P(x)=21 [mm] \bruch{(x-2)(x-3)}{(1-2)(1-3)}+36 \bruch{(x-1)(x-3)}{(2-1)(2-3)}+43 \bruch{(x-1)(x-2)}{(3-1)(3-2)}
[/mm]
Dann wird [mm] P(1)=21\bruch{(1-2)(1-3)}{(1-2)(1-3)}+36 \bruch{(1-1)(1-3)}{(2-1)(2-3)}+43 \bruch{(1-1)(1-2)}{(3-1)(3-2)}=21+0+0=21,
[/mm]
[mm] P(2)=21\bruch{(2-2)(2-3)}{(1-2)(1-3)}+36 \bruch{(2-1)(2-3)}{(2-1)(2-3)}+43 \bruch{(2-1)(2-2)}{(3-2)(3-2)}=0+36+0=36,
[/mm]
[mm] P(3)=21\bruch{(3-2)(3-3)}{(1-2)(1-3)}+36 \bruch{(3-1)(3-3)}{(2-1)(2-3)}+43 \bruch{(3-1)(3-2)}{(3-1)(3-2)}=0+0+43=43.
[/mm]
Das Polynom nun ohne Computer zu vereinfachen ist bei mehr Daten sehr aufwändig und fehleranfällig. Kommt dann noch ein weiteres Zahlenpaar hinzu, müssen alle Polynome neu berechnet werden. Man kann sich nun vorstellen, wie das bei 10 Paaren aussieht. Natürlich erwartet man ein Polynom 9. Grades, aber bei der Berechnung nach Lagrange werden die Summanden nur nacheinander komplizierter, und man kann das Ganze jederzeit um neue Stützpunkte ergänzen.
Für obiges Beispiel geht die Konstruktion nach Lagrange dann so:
[mm] P_0(x) [/mm] = 21
[mm] P_1(x) [/mm] = 21 + a(x-1) mit [mm] P_1(1)=21 [/mm] und [mm] P_1(2)= [/mm] 21+a=36, also a=15
[mm] P_1(x) [/mm] = 21 + 15(x-1)
[mm] P_2(x) [/mm] = 21 + 15(x-1) + b(x-1)(x-2) mit [mm] P_2(1) [/mm] = 21 + 0 + 0 = 21,
[mm] P_2(2) [/mm] = 21 + 15 + 0 = 36 und [mm] P_2(3) [/mm] = 21 + 15*2 + b*2*1 = 51+2b=43, also b= -4 und damit
[mm] P_2(x) [/mm] = 21 + 15(x-1) - 4(x-1)(x-2) = [mm] -4x^2 [/mm] + 27x -2.
Nun zu deinen Fragen.
1. Warum wird die Induktion mit der Indexdifferenz k = (i+k)-i durchgeführt?
Es wird ja behauptet, dass [mm] y[x_{i}, \ldots, x_{i + k}] [/mm] := [mm] \frac{y[x_{i + 1}, \ldots, x_{i + k }] - y[x_{i}, \ldots, x_{i + k - 1}]}{x_{i + k} - x_{i}} [/mm] gilt.Wenn man nun die Induktion über die Anzahl Stützstellen macht, kann man davon ausgehen, dass die Formel für [mm] y[x_{i}, \ldots, x_{i + k-1}] [/mm] stimmt und nun der Stützpunkt [mm] (x_{i+k}| y_{i+k}) [/mm] hinzukommt. Hierfür wird aber offenbar nach obiger Behauptung (1. Ausdruck auf dem Bruchstrich) ein Wert gebraucht, der [mm] x_{i+k} [/mm] schon enthält und von dem man daher nicht ausgehen kann, dass er schon richtig ist. Man dürfte also [mm] y[x_{i}, \ldots, x_{i + k}] [/mm] nicht mit Hilfe von [mm] y[x_{i+1}, \ldots, x_{i + k}] [/mm] erklären.
Nimmt man aber an, dass das y[..] für alle Stützstellen mit weniger als k Stück richtig ist, lässt sich das längere [mm] y[x_{i}, \ldots, x_{i + k}] [/mm] mit dem kürzeren [mm] y[x_{i+1}, \ldots, x_{i + k}] [/mm] und dem kürzeren [mm] y[x_{i}, \ldots, x_{i + k-1}] [/mm] per Induktion berechnen.
Für obiges Beispiel ergibt sich dann:
y[1]=21, y[2]=36, y[3]=43
y[1,2]=15, y[2,3]=7 und
y[1,2,3]= -4, was wieder auf
[mm] P_2(x)= [/mm] 21 + 15(x-1) - 4(x-1)(x-2) führt.
2. Warum ist a der Koeffizient von [mm] x^k?
[/mm]
"Konstruktionsgemäß gilt [mm] p_{i, i + k}(x) [/mm] = [mm] p_{i, i + k - 1}(x) [/mm] + a(x - [mm] x_{i}) \cdot \ldots \cdot [/mm] (x - [mm] x_{i + k - 1})" [/mm] heißt: [mm] p_{i, i + k}(x) [/mm] wird sukzessive so aufgebaut, das die Stützstellen für [mm] x_i, x_{i+1}...x_{i+k-1} [/mm] durch [mm] p_{i, i + k - 1}(x) [/mm] bereits richtig berechnet werden und dass nun noch ein Summand so ergänzt wird, dass das auch noch für [mm] x_{i+k} [/mm] gilt.
Das bedeutet, dass der hinzukommende Summand für [mm] x_{i+1}, ...x_{i+k-1} [/mm] immer 0 ergeben muss, und damit muss er ein Polynom mit den Linearfaktoren [mm] (x-x_i),(x-x_{i+1})...(x-x_{i+k-1})sein. [/mm] Durch den Vorfaktor, den wir jetzt der Einfachheit halber a nennen, kann man das nun so anpassen, dass [mm] p_{i, i + k }(x_{i+k})= y_{i+k} [/mm] wird, wie ich das oben am Beispiel gezeigt habe.
Wenn du nun den hinzugekommenen Summanden [mm] a(x-x_i)(x-x_{i+1})...(x-x_{i+k-1}) [/mm] ausrechnest, erhältst du den höchsten Exponenten in x, indem du alle x-e aus jeder Klammer mit sich selber malnimmst und das dann mit a. Somit ist [mm] ax^{k-1} [/mm] die höchste Potenz, die im Polynom [mm] p_{i, i + k }(x) [/mm] vorkommt, da [mm] p_{i, i + k - 1}(x) [/mm] einen kleineren Grad hat (der Grad wächst von Mal zu Mal). Er ist somit nicht der Koeffizient von [mm] x^k, [/mm] wie im Text behauptet, sondern von [mm] x^{k-1}, [/mm] aber das wirkt sich auf die Beweisführung nicht weiter aus.
Jetzt schau dir mal das q(x) an. Wenn du [mm] q(x_i) [/mm] berechnest, wird der erste Ausdruck auf dem Bruchstrich wegen [mm] (x_i-x_i)=0 [/mm] Null und die zweite Klammer wird zu [mm] x_i-x_{i+k}, [/mm] sie kürzt sich mit dem Nenner weg, so dass [mm] p_{i,i+k-1}(x_i)=y_i [/mm] herauskommt.Wenn du [mm] q(x_{i+k}) [/mm] berechnest, wird die erste Klammer auf dem Bruchstrich [mm] (x_{i+k}-x_i), [/mm] kürzt sich mit dem Nenner weg, so dass [mm] p_{i+1,i+k}(x_{i+k})=y_{i+k} [/mm] herauskommt, weil die zweite Klammer auf dem Bruchstrich zu 0 wird.
Was ist mit den Stützstellen dazwischen? Nehmen wir z.B. k>3 an und berechnen das beispielhaft für [mm] x_{i+3}:
[/mm]
[mm] q(x_{i+3})=\bruch{(x_{i+3}-x_i)p_{i+1,i+k}(x_{i+3})-(x_{i+3}-x_{i+k})p_{i,i+k}(x_{i+3})}{x_{i+k}-x_i}=\bruch{(x_{i+3}-x_i)y_{i+3}-(x_{i+3}-x_{i+k})y_{i+3}}{x_{i+k}-x_i}=\bruch{(x_{i+k}-x_{i+3})y_{i+3}}{x_{i+k}-x_i}=y_{i+3}, [/mm] und entsprechend auch mit anderen x-Werten. Deshalb berechnet q die Stützpunkte alle richtig und entspricht [mm] p_{i,i+k}.
[/mm]
Die rechte Seite von q entsteht aus einer Umformung des Bruches. Das vordere Polynom hat den Grad k-2, die beiden Polynome auf dem Bruchstrich ebenfalls. Mit der Klammer davor steigt der Grad um eins, und der führende Koeffizient entsteht somit nur durch den zweiten Summanden. Weil das x in Der Klammer keinen weiteren Faktor hat, stimmt er somit mit [mm] \bruch{Leitkoeff. von p_{i+1,i+k} - Leitkoeff. von p_{i,i+k-1}}{x_{i+k}-x_i} [/mm] überein.
Die Polynome sind nun so aufgebaut, dass der Grad ihrer Summanden zunimmt und damit der Leitkoeffizient im letzten Summanden steckt, also [mm] y[x_{i+1},...x_{i+k}] [/mm] bzw. [mm] y[x_i,...x_{i+k-1}] [/mm] ist, und daraus ergibt sich nun der Leitkoeff. von [mm] p_{i,i+k} [/mm] als a= [mm] \bruch{y[x_{i+1},...x_{i+k}] - y[x_i,...x_{i+k-1}]}{x_{i+k}-x_i}, [/mm] und das muss der Faktor vor dem neu hinzugekommenen Summanden sein.
|
|
|
| |
|
In diesem Beitrag wurden nachträglich einige Indices korrigiert. (Eine mit 0 beginnende Zählung fällt mir naturgemäß schwer.)
Eine wesentlich unkompliziertere Darstellung, die meinem Beispiel folgt, ist die folgende:
n+1 Stützpunkte [mm] (x_i|y_i), [/mm] 0 [mm] \le [/mm] i [mm] \le [/mm] n, lassen sich durch das Polynom
[mm] P_n(x)=\summe_{i=0}^{n}a_i K_i(x) [/mm] darstellen, wobei das Polynom [mm] K_i(x)=(x-x_0)(x-x_1)...(x-x_{i-1}) [/mm] ist.
Dabei hängen die [mm] a_i [/mm] von den ersten i+1 Koordinaten der Stützpunkte ab.
Beweis durch Vollst. Ind.:
n=0. Dann ist [mm] P_0(x)=a_0=y_0 [/mm] das gesuchte Polynom.
n [mm] \mapsto [/mm] n+1:
[mm] P_{n+1}(x)=\summe_{i=0}^{n+1}a_i K_i(x)= P_n(x)+ a_{n+1} K_{n+1}(x)= P_n(x)+a_{n+1}(x-x_0)(x-x_1)...(x-x_n)
[/mm]
Der erste Summand [mm] P_n(x) [/mm] berechnet nach I.V. alle n+1 Stützstellen von i=0 bis n. Unabhängig vom noch zu bestimmenden [mm] a_{n+1} [/mm] wird der letzte Summand der rechten Seite 0 für alle diese Stützstellen. Also berechnet [mm] P_{n+1}(x) [/mm] schon mal alle Stützstellen von i=0 bis n.
Nun lässt sich [mm] a_{n+1} [/mm] so wählen, dass auch [mm] P_{n+1}(x_{n+1})=y_{n+1} [/mm] wird:
[mm] P_{n+1}(x_{n+1})=P_n(x_{n+1})+a_{n+1}(x_{n+1}-x_0)(x_{n+1}-x_1)...(x_{n+1}-x_n)= y_{n+1} [/mm] und damit
[mm] a_{n+1}=\bruch{y_{n+1} - P_n(x_{n+1})}{(x_{n+1}-x_0)(x_{n+1}-x_1)...(x_{n+1}-x_n)}.
[/mm]
Der Nenner wird nicht 0, da die [mm] x_i [/mm] voneinander verschieden sein müssen. Also ist das benötigte [mm] a_{n+1} [/mm] berechenbar, und [mm] P_{n+1}(x) [/mm] berechnet alle Stützstellen von i=0 bis n+1.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:59 Do 21.11.2019 | | Autor: | inkeddude |
Hey, sehr vielen lieben Dank, dass du dir die Mühe gemacht hast, mir eine ausführliche Antwort zu geben. Ich habe leider deine Antwort erst jetzt bemerkt, weil ich schon die Hoffnung auf eine Antwort aufgegeben hatte 
Ich lese mir den Text morgen durch und melde mich noch einmal bei dir!
Ein schönen Abend noch, Inkeddude
|
|
|
|
