Newtonsche Darstellung - Satz < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 02:00 So 23.02.2020 | | Autor: | teskiro |
Moin, Leute.
Ich habe mich vorgestern gefragt, wie man auf die Formel für das Neville - Aitken - Schema kommt und bin dann auf den Beweises von folgendem Satz gestoßen:
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 sog. "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:
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.
Ich möchte diesen Beweis gerne verstehen, da ich vielleicht dadurch etwas schlauer werde.
Der Beweis ist mir etwas umständlich geschrieben, daher habe ich ihn auf meiner Art geschrieben. Meine Fragen dazu sind in den eckigen Klammern geschrieben.
Behauptung
_________
Es gilt [mm] $p_{i, i + k}(x) [/mm] = [mm] y[x_{i}] [/mm] + [mm] y[x_{i}, x_{i + 1}] [/mm] (x - [mm] x_{i}) [/mm] + [mm] \ldots [/mm] + [mm] y[x_{i}, \ldots, x_{i + k}] [/mm] (x - [mm] x_{i}) \cdot \ldots \cdot [/mm] (x - [mm] x_{i + k - 1})$
[/mm]
Beweis
______
Der Beweis wird durch Induktion bzgl. der Indexdifferenz $k = (i + k) - i$ geführt.
[Frage:Was hat das mit der Indexdifferenz $k = (i + k) - i$ auf sich ? Warum wird $k$ so ausgedrückt bzw., warum ist es notwendig, $k$ so auszudrücken?
Ich meine, es ist ja klar, dass man die Induktion über $k$ durchführen sollte. Oder hat das eine tiefere Bedeutung ?]
Induktionsanfang
______________
Sei $k = 0$.
Dann ist [mm] $p_{i, i + 0}(x) [/mm] = [mm] p_{i, i }(x) [/mm] = [mm] y[x_{i}] [/mm] = [mm] y_{i}$
[/mm]
Das Polynom interpoliert also den Punkt [mm] $(x_{i}, y_{i})$.
[/mm]
Induktionsannahme
______________
Wir nehmen an, die obige Gleichung stimmt für das Polynom [mm] $p_{i, i + k - 1}$. [/mm] Also:
[mm] $\exists [/mm] k [mm] \in \mathbb{N}: p_{i, i + k - 1} [/mm] (x) = [mm] y[x_{i}] [/mm] + [mm] y[x_{i}, x_{i + 1}] [/mm] (x - [mm] x_{i}) [/mm] + [mm] \ldots [/mm] + [mm] y[x_{i}, \ldots, x_{i + k - 1}] [/mm] (x - [mm] x_{i}) \cdot \ldots \cdot [/mm] (x - [mm] x_{i + k - 2})$
[/mm]
Induktionsschritt: k - 1 [mm] \mapsto [/mm] k
______________
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]
In der Induktionsannahme nehmen wir an, dass [mm] $p_{i, i + k - 1} [/mm] (x) = [mm] y[x_{i}] [/mm] + [mm] y[x_{i}, x_{i + 1}] [/mm] (x - [mm] x_{i}) [/mm] + [mm] \ldots [/mm] + [mm] y[x_{i}, \ldots, x_{i + k - 1}] [/mm] (x - [mm] x_{i}) \cdot \ldots \cdot [/mm] (x - [mm] x_{i + k - 2})$ [/mm] gilt.
Es gilt offensichtlich [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]
[Frage: Warum ist danach von [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] die Rede ? Über die Form des Polynoms [mm] $p_{i + 1, i + k }(x)$ [/mm] wissen wir nichts, oder etwa doch ? ]
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]
Das heißt, es gilt: [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] = [mm] p_{i, i + k - 1}(x) [/mm] + a(x - [mm] x_{i}) \cdot \ldots \cdot [/mm] (x - [mm] x_{i + k - 1})$
[/mm]
Daraus folgt, dass $(x - [mm] x_{i}) \frac{p_{i + 1, i + k}(x) - p_{i, i + k - 1}(x)}{x_{i + k} - x_{i}} [/mm] = a(x - [mm] x_{i}) \cdot \ldots \cdot [/mm] (x - [mm] x_{i + k - 1})$.
[/mm]
[Frage: Wie kommt man nun darauf, dass $a = [mm] y[x_{i}, \ldots, x_{i + k}]$ [/mm] ist ? ]
Das wär's von meiner Seite erst einmal. Freue mich, wenn jemand sich meldet! Bedanke mich schon mal im Voraus.
Grüße, Teskiro
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:39 Sa 29.02.2020 | | Autor: | meili |
Hallo Teskiro,
> Moin, Leute.
>
> Ich habe mich vorgestern gefragt, wie man auf die Formel
> für das Neville - Aitken - Schema kommt und bin dann auf
> den Beweises von folgendem Satz gestoßen:
>
>
> Behauptung:
>
>
> Sei [mm]D:= \{ 0, 1, \ldots, n \}[/mm]
>
> Das Lagrangsche Interpolationspolynom zu den Punkten
> [mm](x_{i}, y_{i})[/mm] für [mm]i \in D[/mm] lässt sich bezüglich. der
> Newtonchen Polynombasis schreiben in der Form:
>
> [mm]p(x) = \sum\limits_{i = 0}^{n} y[x_{0}, \ldots, x_{i} N_{i} (x)[/mm]
>
>
> Dabei bezeichnen [mm]y[x_{0}, \ldots, x_{i}][/mm] die zu den Punkten
> [mm](x_{i}, y_{i})[/mm] gehörenden sog. "dividierten Differenzen",
> welche rekursiv definiert sind durch
>
>
> [mm]i = 0, \ldots, n[/mm] : [mm]y[x_{i}]:= y_{i}[/mm]
>
> [mm]k = 1, \ldots, n - i[/mm]: [mm]y[x_{i}, \ldots, x_{i + k}] := \frac{y[x_{i + 1}, \ldots, x_{i + k }] - y[x_{i}, \ldots, x_{i + k - 1}]}{x_{i + k} - x_{i}}[/mm]
>
>
>
>
> Beweis:
>
> 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 } = p[/mm] das gesuchte
> Interpolationspolynom.
>
> Wir zeigen [mm]p_{i, i + k}(x) = y[x_{i}] + y[x_{i}, x_{i + 1}](x - x_{i}) + \ldots + y[x_{i}, \ldots, x_{i + k }](x - x_{i}) \ldots (x - x_{i + k - 1})[/mm],
>
> was offensichtlich die Aussage des Satzes als Spezialfall
> beinhaltet.
>
>
> Der Beweis wird durch Induktion bzgl. der Indexdifferenz [mm]k = (i + k) - i[/mm]
> geführt.
>
>
> Für [mm]k = 0[/mm] ist [mm]p_{i, i} = y_{i} = y[x_{i}], i =0, \ldots, n[/mm].
>
>
> Sei die Behauptung richtig für [mm]k - 1 \ge 0[/mm].
>
>
> Konstruktionsgemäß gilt [mm]p_{i, i + k}(x) = p_{i, i + k - 1}(x) + a(x - x_{i}) \cdot \ldots \cdot (x - x_{i + k - 1})[/mm]
>
>
>
> Zu zeigen ist also, dass [mm]a = y[x_{i}, \ldots, x_{i + k}][/mm].
> Offenbar ist [mm]a[/mm] 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) = \ldots + y[x_{i}, \ldots, x_{i + k - 1}] \cdot x^{k - 1}[/mm],
>
> [mm]p_{i + 1, i + k }(x) = \ldots + 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 [mm]k - 2[/mm] steht. Wie man leicht verifiziert,
> interpoliert das durch
>
>
>
>
> [mm]q(x) = \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}} = p_{i, i + k - 1}(x) + (x - x_{i}) \frac{p_{i + 1, i + k}(x) - p_{i, i + k - 1}(x)}{x_{i + k} - x_{i}}[/mm]
>
>
> gegebene Polynom [mm]q \in P_{k}[/mm] die [mm]k + 1[/mm] Stützpunkte [mm](x_{j}, y_{j}), j = i, \ldots, i + k[/mm].
>
>
> Wegen der Eindeutigkeit des Interpolationspolynoms ist dann
> notwendig [mm]q \equiv p_{i, i + k}[/mm].
>
>
> Der führende Koeffizient ist [mm]p_{i, i + k}(x)[/mm] ist demnach
>
>
> [mm]a = \frac{y[x_{i + 1}, \ldots, x_{i + k}] - y[x_{i}, \ldots, x_{i + k - 1}]}{x_{i + k} - x_{i}} = y[x_{i}, \ldots, x_{i + k }][/mm],
> was den Beweis vervollständigt.
>
>
>
>
> Ich möchte diesen Beweis gerne verstehen, da ich
> vielleicht dadurch etwas schlauer werde.
>
> Der Beweis ist mir etwas umständlich geschrieben, daher
> habe ich ihn auf meiner Art geschrieben. Meine Fragen dazu
> sind in den eckigen Klammern geschrieben.
>
>
>
>
>
> Behauptung
> _________
>
> Es gilt [mm]p_{i, i + k}(x) = y[x_{i}] + y[x_{i}, x_{i + 1}] (x - x_{i}) + \ldots + y[x_{i}, \ldots, x_{i + k}] (x - x_{i}) \cdot \ldots \cdot (x - x_{i + k - 1})[/mm]
>
>
>
>
> Beweis
> ______
>
> Der Beweis wird durch Induktion bzgl. der Indexdifferenz [mm]k = (i + k) - i[/mm]
> geführt.
>
>
>
> [Frage:Was hat das mit der Indexdifferenz [mm]k = (i + k) - i[/mm]
> auf sich ? Warum wird [mm]k[/mm] so ausgedrückt bzw., warum ist es
> notwendig, [mm]k[/mm] so auszudrücken?
>
> Ich meine, es ist ja klar, dass man die Induktion über [mm]k[/mm]
> durchführen sollte. Oder hat das eine tiefere Bedeutung
> ?]
>
Im Beweis habe ich auch keine Stelle gefunden, in der direkt $(i+k)-i$
vorkommt, aber i im Index ist häufig und so kann man $(i+k)$
hineinbekommen, falls man es braucht.
>
>
>
>
> Induktionsanfang
> ______________
>
>
> Sei [mm]k = 0[/mm].
>
> Dann ist [mm]p_{i, i + 0}(x) = p_{i, i }(x) = y[x_{i}] = y_{i}[/mm]
>
> Das Polynom interpoliert also den Punkt [mm](x_{i}, y_{i})[/mm].
>
>
>
>
>
> Induktionsannahme
> ______________
>
>
> Wir nehmen an, die obige Gleichung stimmt für das Polynom
> [mm]p_{i, i + k - 1}[/mm]. Also:
>
>
> [mm]\exists k \in \mathbb{N}: p_{i, i + k - 1} (x) = y[x_{i}] + y[x_{i}, x_{i + 1}] (x - x_{i}) + \ldots + y[x_{i}, \ldots, x_{i + k - 1}] (x - x_{i}) \cdot \ldots \cdot (x - x_{i + k - 2})[/mm]
>
>
> Induktionsschritt: k - 1 [mm]\mapsto[/mm] k
> ______________
>
>
> Konstruktionsgemäß gilt [mm]p_{i, i + k}(x) = p_{i, i + k - 1}(x) + a(x - x_{i}) \cdot \ldots \cdot (x - x_{i + k - 1})[/mm].
>
>
>
> In der Induktionsannahme nehmen wir an, dass [mm]p_{i, i + k - 1} (x) = y[x_{i}] + y[x_{i}, x_{i + 1}] (x - x_{i}) + \ldots + y[x_{i}, \ldots, x_{i + k - 1}] (x - x_{i}) \cdot \ldots \cdot (x - x_{i + k - 2})[/mm]
> gilt.
>
>
> Es gilt offensichtlich [mm]p_{i, i + k - 1}(x) = \ldots + y[x_{i}, \ldots, x_{i + k - 1}] \cdot x^{k - 1}[/mm].
>
>
>
> [Frage: Warum ist danach von [mm]p_{i + 1, i + k }(x) = \ldots + y[x_{i + 1}, \ldots, x_{i + k }] \cdot x^{k - 1}[/mm]
> die Rede ? Über die Form des Polynoms [mm]p_{i + 1, i + k }(x)[/mm]
> wissen wir nichts, oder etwa doch ? ]
>
[mm]p_{i + 1, i + k }(x) = \ldots + y[x_{i + 1}, \ldots, x_{i + k }] \cdot x^{k - 1}[/mm] wird benutzt um auf die dividierte Differenz
als Koeffizienten der höchsten Potenz von x zu kommen.
Nach dem Induktionsanfang, für den Schritt von $k - 1 [mm] \mapsto [/mm] k$
sei die Behauptung [mm]p_{i, i + k - 1}(x) = \ldots + y[x_{i}, \ldots, x_{i + k - 1}] \cdot x^{k - 1}[/mm] richtig für [mm]k - 1 \ge 0[/mm];
und zwar für alle $i = 1, [mm] \ldots [/mm] , n$; und [mm]k = 1, \ldots, n - i[/mm].
Man könnte [mm]p_{i + 1, i + k }(x) = \ldots + y[x_{i + 1}, \ldots, x_{i + k }] \cdot x^{k - 1}[/mm] auch
[mm]p_{i + 1, (i+1) + (k-1) }(x) = \ldots + y[x_{i + 1}, \ldots, x_{(i+1) + (k-1) }] \cdot x^{k - 1}[/mm] schreiben.
>
>
>
> Wie man leicht verifiziert, interpoliert das durch
>
>
>
>
> [mm]q(x) = \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}} = p_{i, i + k - 1}(x) + (x - x_{i}) \frac{p_{i + 1, i + k}(x) - p_{i, i + k - 1}(x)}{x_{i + k} - x_{i}}[/mm]
>
>
> gegebene Polynom [mm]q \in P_{k}[/mm] die [mm]k + 1[/mm] Stützpunkte [mm](x_{j}, y_{j}), j = i, \ldots, i + k[/mm].
>
>
> Wegen der Eindeutigkeit des Interpolationspolynoms ist dann
> notwendig [mm]q \equiv p_{i, i + k}[/mm].
>
>
>
>
> Das heißt, es gilt: [mm]p_{i, i + k - 1}(x) + (x - x_{i}) \frac{p_{i + 1, i + k}(x) - p_{i, i + k - 1}(x)}{x_{i + k} - x_{i}} = p_{i, i + k - 1}(x) + a(x - x_{i}) \cdot \ldots \cdot (x - x_{i + k - 1})[/mm]
>
> Daraus folgt, dass [mm](x - x_{i}) \frac{p_{i + 1, i + k}(x) - p_{i, i + k - 1}(x)}{x_{i + k} - x_{i}} = a(x - x_{i}) \cdot \ldots \cdot (x - x_{i + k - 1})[/mm].
>
>
>
>
> [Frage: Wie kommt man nun darauf, dass [mm]a = y[x_{i}, \ldots, x_{i + k}][/mm]
> ist ? ]
Durch Koeffizientenvergleich; aber wie man [mm](x - x_{i}) \frac{p_{i + 1, i + k}(x) - p_{i, i + k - 1}(x)}{x_{i + k} - x_{i}}[/mm] so kürzen kann,
dass [mm] y[x_{i}, \ldots, x_{i + k}](x - x_{i}) \cdot \ldots \cdot (x - x_{i + k - 1})[/mm] rauskommt, kann ich jetzt nicht ausprobieren,
deshalb stelle ich auch nur auf teilweise beantwortet.
>
>
>
>
> Das wär's von meiner Seite erst einmal. Freue mich, wenn
> jemand sich meldet! Bedanke mich schon mal im Voraus.
>
> Grüße, Teskiro
Gruß
meili
|
|
|
|
