Kurs:Numerik I/6 Interpolation

Aus Wikiversity

Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

[Bearbeiten] 6.1 Einleitung

Das Problem der Interpolation besteht allgemein darin, für m gegebene Stützpunkte bzw. Daten (x_i, y_i), i = 1, \ldots, m ein Element z \in \mathcal Z_m eines gegebenen endlich-dimensionalen Funktionenraums \mathcal Z_m zu bestimmen, so dass

z(x_i) = y_i \quad (i = 1, \ldots, m)

gilt. Dabei können die yi von einer gegebenen, in den xi definierten Funktion f herrühren, d. h. kann

y_i := f(x_i) \quad (i = 1, \ldots, m)

gelten.

Ähnlich wie bei der Ausgleichsrechnung geht es also darum, eine große Zahl von Daten durch eine Funktion zu ersetzen bzw. eine Funktion, die möglicherweise durch eine komplizierte und numerisch aufwendig auszuwertende Vorschrift definiert ist, durch eine Funktion mit einer einfacheren Vorschrift anzunähern, wobei bei der Interpolation im Unterschied zur Ausgleichsrechnung gefordert wird, dass der Graph der gesuchten Funktion genau durch die Punkte (xi,yi) verläuft. Für die Wahl des Ansatzraumes \mathcal Z_m gibt es nun wie bei der Ausgleichsrechnung oder anderen Arten der Approximation viele Möglichkeiten. Hier wollen wir nur auf die wichtigste Art der Interpolation eingehen, die Polynominterpolation, bei der

\Pi_n := \{p | p \text{ ist Polynom vom Grad} \le n\}

der Funktionenraum aller Polynome vom Höchstgrad n, also \mathcal Z_m := \Pi_n mit m: = n + 1 ist.

Wir betrachten also jetzt das folgende Problem (IP) der Interpolation durch ein Polynom:

(IP) Für gegebene Stützpunkte
(6.1) (x_i, y_i), \quad i = 0, 1, \ldots, n
mit Stützstellen
(6.2) x_i \neq x_k, \quad i \neq k
bestimme ein Interpolationspolynom p \in \Pi_n mit
(6.3) p(x_i) = y_i \quad (i = 0, 1, \ldots, n).

Die Bedingung (6.2) könnte man an einigen Stellen in diesem Kapitel fortlassen. Sie ist aber sinnvoll und wird insbesondere zum Beweis der Eindeutigkeit des Interpolationspolynoms im nächsten Satz benötigt.

[Bearbeiten] Satz 6.1

Das Interpolationsproblem (IP) hat eine eindeutige Lösung p \in \Pi_n.

[Bearbeiten] Beweis.

Sei p \in \Pi_n in der Form

p(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n

gegeben. Dann lauten die Gleichungen (6.3)

(6.4) a_0 + a_1x_i + a_2x^2_i + \ldots + a_nx^n_i = y_i \quad (i = 0, 1, \ldots, n).

Dies sind n + 1 Gleichungen in den n + 1 Unbekannten ai (i = 0, 1, \ldots, n). Die zu diesen Gleichungen gehörende Systemmatrix ist die bereits aus Abschnitt 4.2 bekannte Vandermonde-Matrix

V := \begin{pmatrix} 1 & x_0 & \ldots & x^n_0 \\ 1 & x_1 & \ldots & x^n_1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & \ldots & x^n_n \end{pmatrix}.

Ihre Determinante, die Vandermonde-Determinante, ist durch

\det(V) = \prod_{0 \le i<k \le n} (x_k - x_i)

gegeben (siehe R. Zurmühl: Matrizen und ihre technischen Anwendungen, Springer, Berlin, 1965). Wegen (6.2) ist \det(V) \neq 0 und alles gezeigt.

q.e.d.

Der Beweis des letzten Satzes macht deutlich, dass man das Interpolationspolynom bestimmen kann, indem man das System (6.4) löst. Leider ist die zugehörige Systemmatrix, die Vandermonde-Matrix, sehr schlecht konditioniert, wie wir bereits in Abschnitt 4.2 festgestellt hatten. Daher ist von diesem Weg zur Lösung des Interpolationsproblems abzuraten. Wir geben im Folgenden andere Möglichkeiten der Bestimmung an, die aber alle auch Vor- und Nachteile haben.

[Bearbeiten] 6.2 Die Lagrangesche Darstellung des Interpolationspolynoms

Wir führen zunächst spezielle Polynome ein:

[Bearbeiten] Definition 6.2

Zu n + 1 Stützstellen xi (i = 0, 1, \ldots, n) mit x_i \neq x_k für i \neq k sind die Langrangeschen Basispolynome L_i \in \Pi_n (i = 0, 1, \ldots, n) definiert durch
L_i(x) := \prod^n_{j=0 \atop j \neq i} \frac{x - x_j}{x_i - x_j}.

Offenbar hat das Lagrangesche Basispolynom Li die n Nullstellen xk (k \neq i) und genügt es den n + 1 Bedingungen

(6.5) L_i(x_k) = \delta_{ik} := \begin{cases} 1, & k = i, \\ 0, & k \neq i. \end{cases}

Da \sum^n_{i=0} a_iL_i(x) = 0 ein Polynom vom Höchstgrad n ist und somit, wenn es nicht das Nullpolynom ist, maximal n Nullstellen hat, folgt:

(6.6) \sum^n_{i=0} a_iL_i(x) = 0 \quad (x \in \R) \quad \Rightarrow \quad a_i = 0 \quad (i = 0, 1, \ldots, n).

Das heißt, die Li sind linear unabhängig und es ist somit

\dim(\operatorname{span}\{L_0, L_1, \ldots, L_n\}) = n + 1.

Wegen

\operatorname{span}\{L_0, L_1, \ldots, L_n\} \subseteq \Pi_n

folgt damit

\Pi_n = \operatorname{span}\{L_0, L_1, \ldots, L_n\}.

Die Funktionen L_0, L_1, \ldots, L_n bilden also eine Basis des Polynomraumes Πn, so dass sich jedes Polynom vom Höchstgrad n und damit auch das eindeutig bestimmte Interpolationspolynom als Linearkombination der Li darstellen lässt. Für die nach Satz 6.1 eindeutige Lösung p des Interpolationsproblems (IP) ist diese Darstellung wegen (6.5) besonders einfach. Denn macht man für p den Ansatz

p(x) = \sum^n_{i=0} a_iL_i(x),

so folgt mit (6.3) und (6.5)

y_k = p(x_k) = \sum^n_{i=0} a_iL_i(x_k) = a_kL_k(x_k) = a_k \quad (k = 0, 1, \ldots, n)

und damit die Lagrangesche Darstellung des Interpolationspolynoms

(6.7) p(x) = \sum^n_{i=0} y_iL_i(x).

Sie hat den Vorteil, dass man an ihr die Stützwerte yi für die Stützpunkte xi und damit die Interpolationsbedingungen (6.3) sofort ablesen kann.

[Bearbeiten] Beispiel 6.3

Zu den Stützpunkten

\begin{array}{c|c c c} i & 0 & 1 & 2 \\ \hline x_i & 0 & 1 & 3 \\ y_i & 1 & 3 & 2 \end{array}

lauten die Langrangeschen Basispolynome

L_0(x) = \frac{(x - 1) (x - 3)}{(0 - 1) (0 - 3)} = \frac{1}{3} (x - 1) (x - 3),
L_1(x) = \frac{(x - 0) (x - 3)}{(1 - 0) (1 - 3)} = - \frac{1}{2} x (x - 3),
L_2(x) = \frac{(x - 1) (x - 0)}{(3 - 1) (3 - 0)} = \frac{1}{6} x (x - 1).

Das Interpolationspolynom p \in \Pi_2 zu diesen Stützpunkten ist somit gegeben durch

p(x) = \frac{1}{3} (x - 1) (x - 3) - \frac{3}{2} x (x - 3) + \frac{1}{3} x (x - 1).

Zum Beispiel für x = 2 berechnet man

p(2) = 1 \cdot L_0(2) + 3 \cdot L_1(2) + 2 \cdot L2(2) = - \frac{1}{3} + 3 + \frac{2}{3} = \frac{10}{3}.

Man beachte, dass die Abbildung

\R^{n+1} \to \Pi_n, \quad (y_0, \ldots, y_n)^T \mapsto p,

die für vorgegebene, paarweise verschiedene xi jeder Menge von n + 1 Stützwerten yi das eindeutige Interpolationspolynom zuordnet, linear ist.

Leider ist aber auch die Lagrangesche Darstellung des Interpolationspolynoms für praktische Rechnungen mit großem n weniger geeignet. Denn die Berechnung von Li(ξ) in einem Punkt ξ für ein i verlangt insgesamt 2(n − 1) Produkte und 1 Division, so dass für die Auswertung des Interpolationspolynoms an einer Stelle ξ insgesamt (2n − 1)(n + 1) + (n + 1), also 2n^2 + \mathcal O(n) wesentliche arithmetische Operationen benötigt werden. Außerdem erfordert die Lagrangesche Darstellung des Interpolationspolynomes im Fall der Hinzunahme eines Stützpunktes oder mehrerer Stützpunkte zu der ursprünglichen Stützpunktmenge die Neuberechnung aller Li und damit des gesamten Interpolationspolynoms.

[Bearbeiten] 6.3 Das Neville-Schema

Die Lösung für das Problem (IP), d. h. das Interpolationspolynom, kann auch schrittweise aus den Interpolationspolynomen für m = 0, 1, \ldots Stützpunkte berechnet werden. Um dies zu zeigen, benötigen wir:

[Bearbeiten] Definition 6.4

Zu n + 1 Stützpunkten (xi,yi) wie in (6.1) und (6.2) bezeichne P_{i, i+1, \ldots, i+m} das (eindeutig bestimmte) Polynom vom Grad \le m mit
(6.8) P_{i, i+1, \ldots, i+m}(x_k) = y_k, \quad k = i, i+1, \ldots, i+m,
wobei i, m \ge 0 und i + m \le n seien.

Damit können wir die Lösung p \in \Pi_n des Problems (IP) auch in der Form

p(x) = P_{0, 1, \ldots, n}(x)

schreiben. Weiter können wir in diesem Zusammenhang beweisen:

[Bearbeiten] Satz 6.5

Für P_{i, i+1, \ldots, i+m} gilt die Rekursionsformel
(6.9) P_i(x) \equiv y_i,
(6.10) P_{i, i+1, \ldots, i+m}(x) = \frac{(x - x_i) P_{i+1, \ldots, i+m}(x) - (x - x_{i+m}) P_{i, \ldots, i+m-1}(x)}{x_{i+m} - x_i}, falls m \ge 1.

[Bearbeiten] Beweis.

Die Identität (6.9) ist wegen P_i \in \Pi_0 und Pi(xi) = yi richtig. Nun bezeichne Q(x) die rechte Seite von (6.10), so dass Q = P_{i, i+1, \ldots, i+m} zu zeigen ist.

Es gilt P_{i+1, \ldots, i+m} \in \Pi_{m-1} und P_{i, i+1, \ldots, i+m-1} \in \Pi_{m-1} und demnach Q \in \Pi_m. Weiter gilt

Q(x_i) = - \frac{(x_i - x_{i+m})y_i}{x_{i+m} - x_i} = y_i, \quad Q(x_{i+m}) = \frac{(x_{i+m} - x_i)y_{i+m}}{x_{i+m} - x_i} = y_{i+m}

und für k = i + 1, i + 2, \ldots, i + m - 1 hat man

Q(x_k) = \frac{(x_k - x_i)y_k - (x_k - x_{i+m})y_k}{x_{i+m} - x_i} = \frac{(-x_i + x_{i+m})y_k}{x_{i+m} - x_i} = yk.

Wegen der Eindeutigkeit des Interpolationspolynoms (vgl. Satz 6.1) folgt Q = P_{i, i+1, \ldots, i+m}.

q.e.d.

Die Formel (6.10) ist eine Rekursionsformel, die es ermöglicht, das Polynom P_{i, i+1, \ldots, i+m}(x) vom Grad \le m aus den beiden Polynomen P_{i+1, \ldots, i+m}(x) und P_{i, \ldots, i+m-1}(x) vom Grad m − 1 zu bestimmen. Sie führt auf das Neville-Schema, bei dem sich die Einträge spaltenweise berechnen lassen:

\begin{matrix} y_0 = P_0(x) & & & & & & & & \\ & \searrow & & & & & & & \\ y_1 = P_1(x) & \rightarrow & P_{01}(x) & & & & & & \\ & \searrow & & \searrow & & & & & \\ y_2 = P_2(x)& \rightarrow & P_{12}(x) & \rightarrow & P_{012}(x) & & & & \\ \vdots & & \vdots & & \vdots & \ddots & & & \\ y_{n-1} = P_{n-1}(x) & \rightarrow & P_{n-2, n-1}(x) & \rightarrow & \ldots & \ldots & P_{0, \ldots, n-1}(x) & & \\ & \searrow & & \searrow & & & & \searrow & \\ y_n = P_n(x) & \rightarrow & P_{n-1, n}(x) & \rightarrow & \ldots & \ldots & P_{1, \ldots, n}(x) & \rightarrow & {P_{0, 1, \ldots, n}(x)} \end{matrix}

Mit diesem Schema lässt sich das Interpolationspolynom p(x) = P_{0, 1, \ldots, n}(x) an einzelnen Stellen x auswerten. Dazu werden jeweils

3 \sum^n_{i=1} i = \frac{3}{2} n(n + 1)

Multiplikationen und Divisionen benötigt.

[Bearbeiten] Beispiel 6.6

Wir betrachten wieder die Stützpunkte aus Beispiel 6.3:

\begin{array}{c|c c c} i & 0 & 1 & 2 \\ \hline x_i & 0 & 1 & 3 \\ y_i & 1 & 3 & 2 \end{array}

Für x = 2 berechnet man

P_{01}(2) = \frac{(2 - 0)P_1(2) - (2 - 1)P_0(2)}{1 - 0} = \frac{2 \cdot 3 - 1 \cdot 1}{1} = 5,
P_{12}(2) = \frac{(2 - 1)P_2(2) - (2 - 3)P_1(2)}{3 - 1} = \frac{1 \cdot 2 - (-1) \cdot 3}{2} = \frac 52,
P_{12}(2) = \frac{(2 - 0)P_{12}(2) - (2 - 3)P_{01}(2)}{3 - 0} = \frac{2 \cdot (5/2) - (-1) \cdot 5}{3} = \frac{10}{3}.

Demnach sieht das Neville-Schema hier wie folgt aus:

\begin{matrix} y_0 = P_0(2) = 1 & & \\ y_1 = P_1(2) = 3 & P_{01}(2) = 5 & \\ y_2 = P_2(2) = 2 & P_{12}(2) = 5/2 & P_{012}(2) = 10/3. \end{matrix}

Bei Aufnahme eines neuen Stützpunktes oder mehrerer neuer Stützpunkte und Auswertung des Interpolationspolynoms an derselben Stelle wie zuvor, muss das Neville-Schema, anders als es eine Auswertung über die Lagrangesche Darstellung erfordern würde, nicht vollständig neu aufgestellt werden, sondern müssen nur entsprechende Zeilen am Ende des Schemas hinzugefügt werden. Falls ein Interpolationspolynom jedoch an mehreren Stellen zu bestimmen ist, sind trotzdem andere Methoden vorzuziehen. Eine davon wird im folgenden Abschnitt vorgestellt.

[Bearbeiten] 6.4 Die Newtonsche Darstellung des Interpolationspolynoms

Wir definieren zunächst:

[Bearbeiten] Definition 6.7

Zu gegebenen n + 1 Stützstellen xi (i = 0, 1, \ldots, n) sind die Newtonschen Basispolynome N_i \in \Pi_i (i = 0, 1, \ldots, n) definiert durch
N_i(x) := \prod^{i-1}_{j=0} (x - x_j).

Man beachte dabei, dass das leere Produkt als 1 definiert, also N_0(x) \equiv 1 ist. Ähnlich wie für die Lagrangeschen Basispolynome in (6.6) schließt man, dass die Newtonschen Basispolynome linear unabhängig sind und

\Pi_n = \operatorname{span}\{N_0(x), \ldots, N_n(x)\}

ist. Jedes Polynom vom Höchstgrad n lässt sich also auch nach Newtonschen Basispolynomen entwickeln. Insbesondere soll nun eine solche Entwicklung

(6.11) p(x) = \sum^n_{i=0} a_iN_i(x) = a_0 + a_1(x - x_0) + a_2(x - x_0)(x - x_1) + \ldots + a_n(x - x_0) \cdots (x - x_{n-1})

d. h., sollen nun zugehörige Koeffizienten ai für das Interpolationspolynom p \in \Pi_n bestimmt werden.

Die Koeffizienten ai in (6.11) lassen sich nacheinander aus den Gleichungen

y0 = p(x0) = a0,
y_1 = p(x_1) = a_0 + a_1(x_1 - x_0) \quad \Rightarrow \quad a_1 = (y_1 - y_0)/(x_1 - x_0),
y_2 = p(x_2) = a_0 + a_1(x_2 - x_0) + a_2(x_2 - x_0)(x_2 - x_1) \quad \Rightarrow \quad a_2 = \ldots,
\vdots

gewinnen. Zur Berechnung der Koeffizienten des Interpolationspolynoms wären bei dieser Vorgehensweise

\sum^n_{j=1} \sum^j_{i=1} i = \frac 12 \sum^n_{j=1} j(j + 1) = \frac{n(n + 1)(2n + 1)}{12} + \frac{n(n + 1)}{4} = \frac 16 n^ 3 + \frac 12 n^2 + \frac 13 n

Multiplikationen und Divisionen und insgesamt n^3/3+\mathcal O(n^2) arithmetische Operationen erforderlich. Eine Vorgehensweise, die dafür nur n2 / 2 + n / 2 Divisionen und nur insgesamt \mathcal O(n^2) arithmetische Operationen verlangt, soll im Folgenden vorgestellt werden.

[Bearbeiten] Definition 6.8

Für n + 1 Stützpunkte (xi,yi) wie in (6.1) und (6.2) heißen die Zahlen
y[xi]: = yi,
(6.12) 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}
dividierte Differenzen, wobei i, k \ge 0 und i + k \le n seien.

Man beachte, dass die dividierte Differenz y[x_i, \ldots, x_{i+k}] von den Stützstellen x_i, \ldots, x_{i+k} und den Stützwerten y_i, \ldots, y_{i+k} abhängt. Die genauen Abhängigkeiten zwischen den einzelnen dividierten Differenzen können dem folgenden Tableau entnommen werden.

\begin{matrix} y_0 = y[x_0] & & & & & & & & \\ & \searrow & & & & & & & \\ y_1 = y[x_1] & \rightarrow & y[x_0, x_1] & & & & & & \\ & \searrow & & \searrow & & & & & \\ y_2 = y[x_2] & \rightarrow & y[x_1, x_2] & \rightarrow & y[x_0, x_1, x_2] & & & & \\ \vdots & & \vdots & & \vdots & \ddots & & & \\ y_{n-1} = y[x_{n-1}] & \rightarrow & y[x_{n-2}, x_{n-1}] & \rightarrow & \ldots & \ldots & y[x_0, x_{n-1}] & & \\ & \searrow & & \searrow & & & & \searrow & \\ y_n = y[x_n] & \rightarrow & y[x_{n-1}, x_n] & \rightarrow & \ldots & \ldots & y[x_1, \ldots, x_n] & \rightarrow & {y[x_0, \ldots, x_n]} \end{matrix}

Zum Beispiel gilt

y[x_0, x_1] = \frac{y[x_1] - y[x_0]}{x_1 - x_0}, \quad y[x_1, x_2] = \frac{y[x_2] - y[x_1]}{x_2 - x_1}, \quad y[x_0, x_1, x_2] = \frac{y[x_1, x_2] - y[x_0, x_1]}{x_2 - x_0}

Zur Berechnung aller dividierten Differenzen für n + 1 Stützpunkte werden insgesamt nur

\sum^n_{i=1} i = \frac 12 n(n + 1)

Divisionen benötigt. Ferner gilt folgender Satz:

[Bearbeiten] Satz 6.9

Für die Lösung p \in \Pi_n des Interpolationsproblems (IP) hat man die Darstellung (6.11) mit
(6.13) a_i := y[x_0, \ldots, x_i], \quad i = 0, 1, \ldots, n.

[Bearbeiten] Beweis.

Der Beweis wird per vollständiger Induktion über n geführt. Die Behauptung ist sicher für n = 0 richtig. Es sei nun angenommen, dass sie für beliebiges n \in \N_0 und beliebige Stützpunkte (u_i, v_i), i = 1, \ldots, n mit u_i \neq v_k für i \neq k richtig sei.

Seien nun n + 2 Stützpunkte (x_i, y_i), i = 0, 1, \ldots, n + 1 mit x_i \neq x_k für i \neq k gegeben und p \in \Pi_{n+1} das zugehörige Interpolationspolynom. Mit den in Definition 6.4 definierten Polynomen gilt dann

p - P_{0, \ldots, n} \in \Pi_{n+1}, \quad p(x_k) - P_{0, \ldots, n}(x_k) = 0, \quad k = 0, 1, \ldots, n

und daher mit einer Konstanten a \in \R (a = 0 ist möglich)

p(x) - P_{0, \ldots, n}(x) = a(x - x_0) \cdots (x - x_n)

bzw.

(6.14) p(x) = P_{0, \ldots, n}(x) + a(x - x_0) \cdots (x - x_n).

Nach Induktionsvoraussetzung gilt nun a_i := y[x_0, \ldots, x_i], i = 0, 1, \ldots, n, so dass noch

a = y[x_0, \ldots, x_{n+1}]

zu zeigen bleibt.

Nach Satz 6.5 gilt

(6.15) p(x) = P_{0, 1, \ldots, n+1}(x) = \frac{(x - x_0)P_{1, \ldots, n+1}(x) - (x - x_{n+1})P_{0, \ldots, n}(x)}{x_{n+1} - x_0}

so dass die Behauptung per Koeffizientenvergleich folgt: wegen (6.14) muss a der Hauptkoeffizient von p, d. h. muss

p = Q + axn + 1

für ein gewisses Polynom Q \in \Pi_n sein. Weiter ist nach Induktionsvoraussetzung bekannt, dass P_{1, \ldots, n+1} und P_{0, \ldots, n} die Hauptkoeffizienten y[x_1, \ldots, x_{n+1}] und y[x_0, \ldots, x_n] haben und damit p den folgenden Hauptkoeffizienten hat:

a = \frac{y[x_1, \ldots, x_{n+1}] - y[x_0, \ldots, x_n]}{x_{n+1} - x_0} = y[x_0, \ldots, x_{n+1}].

Somit ist alles gezeigt.

q.e.d.

Die Darstellung (6.13) nennt man die Newtonsche Darstellung des Interpolationspolynoms. Nimmt man einen weiteren Stützpunkt zu den ursprünglich n Stützpunkten zusätzlich mit auf, so ändern sich offenbar die ersten n Koeffizienten des Interpolationspolynoms in dieser Darstellung nicht und kann man den Koeffizienten an + 1 berechnen, indem man im Schema der dividierten Differenzen unten eine zusätzliche Zeile für diesen Punkt berechnet.

Sind schließlich die Koeffizienten ai der Newtonschen Darstellung (6.11) des Interpolationspolynoms p bekannt, so kann dieses für jedes x: = ξ effizient mit dem Horner-Schema

p(\xi) = [\ldots [a_n(\xi - x_{n-1}) + a_{n-1}] (\xi - x_{n-2}) + \ldots + a_1] (\xi - x_0) + a_0

ausgewertet werden, wobei die Operationen von links nach rechts auszuführen sind.

Zum Abschluss zeigen wir die Vorgehensweise wieder an unserem Standardbeispiel.

[Bearbeiten] Beispiel 6.10

Gegeben seien die Stützpunkte

\begin{array}{c|c c c} i & 0 & 1 & 2 \\ \hline x_i & 0 & 1 & 3 \\ y_i & 1 & 3 & 2 \end{array}

Dazu stellen wir das Schema der dividierten Differenzen auf:

\begin{matrix} y[x_0]=1 & & & & \\ & \searrow & & & \\ y[x_1]=3 & \rightarrow & y[x_0,x_1]=\frac{y[x_1]-y[x_0]}{x_1-x_0}=2 & & \\ & \searrow & & \searrow & \\ y[x_2]=2 & \rightarrow & y[x_1,x_2]=\frac{y[x_2]-y[x_1]}{x_2-x_1}=-\frac 12& \rightarrow & y[x_0,x_1,x_2]=\frac{y[x_1,x_2]-y[x_0,x_1]}{x_2-x_0}=-\frac 56 \end{matrix}

Das Interpolationspolynom p \in \Pi_2 zu diesen Stützpunkten lautet somit in der Newtonschen Darstellung:

(6.16) p(x) = 1 + 2x - \frac 56x(x - 1).

Nimmt man beispielsweise den Punkt (x_3, y_3) := \left(2, \frac 52\right) mit hinzu, so muss man nur das obige Schema um eine Zeile erweitern:

\begin{array}{c|c c c c} x_i & y_i & & & \\ \hline 0 & 1 & & & \\ 1 & 3 & 2 & & \\ 3 & 2 & -\frac 12 & -\frac 56 & \\ 2 & \frac 52 & -\frac 12 & 0 & \frac 5{12} \end{array}

Das Interpolationspolynom p \in \Pi_3 zu diesen Stützpunkten ist dann in Bezug auf (6.16) nur um einen Term zu erweitern:

p(x) = 1 + 2x - \frac 56x(x - 1) + \frac 5{12} x(x - 1)(x - 3).

Das Horner-Schema zur Berechnung von letzterem Polynom an der Stelle ξ: = 4 lässt sich mit

b_n := a_n, \quad b_i := a_i + (\xi - x_i)b_{i+1} \quad (i = n - 1, n - 2, \ldots, 0)

wie folgt darstellen, wobei hier n: = 3 ist:

\begin{array}{|c||c|c|c|c|} \hline i & 3 & 2 & 1 & 0 \\ \hline x_i & & 3 & 1 & 0 \\ \hline \xi - x_i & & 1 & 3 & 4 \\ \hline a_i & \frac 5{12} & -\frac 56 & 2 & 1 \\ \hline b_i & \frac 5{12} & -\frac 5{12} & \frac 34 & \mbox{4} \\ \hline \end{array}

Offenbar ist p(2) = b0 = 4.

[Bearbeiten] 6.5 Der Fehler bei der Polynominterpolation

Der folgende Satz gibt für hinreichend oft differenzierbare Funktionen eine Darstellung des bei der Polynominterpolation auftretenden Fehlers an.

[Bearbeiten] Satz 6.11

Es seien f \in C^{n+1}[a, b], x_i \in [a, b] und y_i := f(x_i), i = 0, 1, \ldots, n. Für jedes x \in [a, b] genügt dann die Lösung p \in \Pi_n des Interpolationsproblems (IP) der Gleichung
(6.17) f(x) - p(x) = \frac{f^{(n+1)}(\xi_x)}{(n + 1)!} \omega(x)
mit
(6.18) \omega(x) := (x - x_0) \cdots (x - x_n)
und einem \xi_x \in [a, b].

[Bearbeiten] Beweis.

Da für x: = xi für i \in \{0, 1, \ldots, n\} nichts zu zeigen ist, nehmen wir x \neq x_i für i = 0, 1, \ldots, n an. Sei nun

ψ(t): = f(t) − p(t) − Kω(t)

mit

K := \frac{f(x) - p(x)}{\omega(x)},

so dass ψ(x) = 0 folgt. Also besitzt ψ in dem Intervall [a,b] mindestens n + 2 paarweise verschiedene Nullstellen

x_0, \ldots, x_n, x.

Wiederholte Anwendung des Satzes von Rolle zeigt, dass ψ' in dem Intervall [a,b] mindestens n + 1 Nullstellen besitzt, ψ'' mindestens n usw. und somit ψ(n + 1) mindestens noch eine Nullstelle ξx. Nun gilt aber

p^{(n+1)}(x) \equiv 0, \quad \omega^{(n+1)}(x) \equiv (n + 1)!,

wobei die zweite Identität aus der Tatsache folgt, dass \omega \in \Pi_{n+1} den Hauptkoeffizienten 1 hat. Insgesamt erhält man damit

\psi^{(n+1)}(\xi_x) = f^{(n+1)}(\xi_x) - K(n + 1)! = 0, \quad K = \frac{f^{(n+1)}(\xi_x)}{(n + 1)!},

was den Beweis vervollständigt.

q.e.d.

Eine weitere Darstellung für den bei der Polynominterpolation entstehenden Fehler erhält man mittels dividierter Differenzen.

[Bearbeiten] Satz 6.12

Es seien f \in C^{n+1}[a, b], x_i \in [a, b] und y_i := f(x_i), i = 0, 1, \ldots, n. Für jedes x \in [a, b] \setminus \{x_0, \ldots, x_n\} genügt dann die Lösung p \in \Pi_n des Interpolationsproblems (IP) der Gleichung
f(x) - p(x) = y[x_0, \ldots, x_n, x] \omega(x).

[Bearbeiten] Beweis.

Mit xn + 1: = x für x \notin \{x_0, \ldots, x_n\} hat man nach Satz 6.9

P_{0, \ldots, n+1}(t) = P_{0, \ldots, n}(t) + y[x_0, \ldots, x_n, x] \omega(t)

für alle t \in \R, so dass mit der Identität f(x) = P_{0, \ldots, n+1}(x) die Behauptung folgt.

q.e.d.

Als Konsequenz aus den Sätzen 6.11 und 6.12 ergibt sich für die dividierten Differenzen:

[Bearbeiten] Korollar 6.13

Es seien f \in C^n[a, b] und y_i := f(x_i), i = 0, 1, \ldots, n Stützwerte zu Stützstellen x_i \in [a, b] mit x_i \neq x_k für i \neq k. Dann existiert ein \xi \in [a, b] mit

y[x_0, \ldots, x_n] = \frac{f^{(n)}(\xi)}{n!}.

[Bearbeiten] Beweis.

Für n = 0 ist die Behauptung trivial und für n \ge 1 folgt sie unmittelbar aus einem Vergleich der rechten Seiten in den Sätzen 6.11 und 6.12, wenn diese auf x_0, \ldots, x_{n-1} und x: = xn angewandt werden.

q.e.d.

Wir wollen nun der Frage nachgehen, ob die Wahl von mehr Stützstellen automatisch auch zu einer Verringerung des bezüglich [a,b] maximalen Interpolationsfehlers führt oder, anders ausgedrückt, ob der maximale Interpolationsfehler für eine Folge von Interpolationspolynomen zu zunehmend wachsender Zahl von Stützstellen gegen Null strebt. Dazu sei für jedes j \in \N_0 für den Rest des Unterabschnitts

(6.19) \Delta_j := \Bigl\{x^{(j)}_i \Big| a := x^{(j)}_0 < x^{(j)}_1 < \ldots < x^{(j)}_{n_j} := b\Bigr\}

mit einem n_j \in \N_0 eine Partition von [a,b] und

\|\Delta_j\| := \max_{1\le i\le n_j} (x^{(j)}_i - x^{(j)}_{i-1})

ein Maß für die Feinheit der Unterteilung. Weiter sei p_j \in \Pi^{n_j} das Interpolationspolynom zu f mit den Stützstellen (x^{(j)}_i, f(x^{(j)}_i)), i = 0, 1, \ldots, n_j. Aus Satz 6.11 können wir dann zunächst das folgende Konvergenzergebnis schließen. Man beachte, dass dafür nicht \|\Delta_j\| \to 0 (j \to \infty) gefordert ist.

[Bearbeiten] Satz 6.14

Es sei f \in C^\infty[a, b] und es gelte mit einem M \ge 0
\max_{x \in [a, b]} \left| f^{(k)}(x) \right| \le M, \quad k \in \N.
Weiter sei \Delta_j, j \in \N_0 eine Folge von Partitionen von [a,b] der Form (6.19) mit n_j \to \infty (j \to \infty). Dann konvergiert die Folge der zugehörigen Interpolationspolynome auf [a,b] gleichmäßig gegen f, d. h., es gilt
\lim_{j\to\infty} \max_{x \in [a, b]} |f(x) - p_j(x)| = 0.

[Bearbeiten] Beweis.

Aus Satz 6.11 schließt man

\max_{x \in [a, b]} |f(x) - p_j(x)| \le \frac M{(n_j + 1)!} \max_{x \in [a, b]} \left|(x - x_0) \cdots (x - x_{n_j})\right| \le \frac{M(b - a)^{n_j+1}}{(n_j + 1)!}.

Für n_j \to \infty (j \to \infty) konvergiert der letzte Term für j \to \infty gegen Null, so dass alles gezeigt ist.

q.e.d.

[Bearbeiten] Beispiel 6.15

Für f(x): = e − 0.5x hat man

f'(x) = - \frac 12 e^{-0.5x}, \quad f''(x) = \frac 1{2^2} e^{-0.5x}, \quad \ldots, \quad f^{(k)}(x) = (-1)^k \frac 1{2^k} e^{-0.5x}

und somit z. B. für [a,b]: = [0,2]

\max_{x \in [0, 2]} \left| f^{(k)}(x) \right| \le \frac 1{2^k} e^0 \le \frac 12, \quad k \in \N.

Allgemein kann man jedoch nicht erwarten, dass eine gegebene Funktion auf einem kompakten Intervall umso besser durch ein Interpolationspolynom approximiert wird, je feiner die Unterteilung der Stützstellen gewählt wird. Wie man zeigen kann, ist dafür die Funktion

f(x) := \frac 1{1 + x^2}, \quad x \in [-5, 5]

ein Beispiel. Für deren Ableitungen in x man

f^{(n)}(x) \approx (-1)^n 2^n n! O(|x|^{-2-n})

zeigen kann, so dass z. B. für x = 4 mit einer Konstanten C > 0 folgt:

\left| f^{(n+1)}(x) \right| \approx C \frac{2^{n+1}(n + 1)!}{2^{2(n+3)}} = \frac C{2^4} \frac{(n + 1)!}{2^{n+1}} \to +\infty \quad (n \to \infty).

In diesem Fall ist also auch die Voraussetzung von Satz 6.14 nicht erfüllt. Allgemein hat man in diesem Zusammenhang das folgende „Negativergebnis“, den Satz von Faber, welcher insbesondere für Folgen von Partitionen Δj mit \|\Delta_j\| \to 0 (j \to \infty) von Interesse ist. (Einen Beweis, der allerdings einiges voraussetzt, findet man bei E. W. Cheney: Introduction to Approximation Theory, 2nd edition, Chelsea, New York, 1982.)

[Bearbeiten] Satz 6.16 (Faber)

Zu jeder Folge von Partitionen \Delta_j, j \in \N_0 von [a,b] der Form (6.19) existiert eine Funktion f \in C[a, b], so dass für die Folge der zugehörigen Interpolationspolynome auf [a,b] gilt:
\lim_{j \to \infty} \max_{x \in [a, b]} |f(x) - p_j(x)| = \infty.

[Bearbeiten] 6.6 Tschebyscheff-Polynome

Der Fehler des Interpolationspolynoms zu n + 1 vorgegebenen Stützstellen wird durch (6.17) beschrieben. Da der Punkt ξx in (6.17) i. a. unbekannt ist, macht es Sinn, statt der Darstellung (6.17) des Interpolationsfehlers die Abschätzung

(6.20) \max_{x \in [a, b]} |f(x) - p(x)| \le \frac 1{(n + 1)!} \max_{x \in [a, b]} \left| f^{(n+1)}(x) \right| \max_{x \in [a, b]} |\omega(x)|

zu betrachten. In diesem Abschnitt wird der Frage nachgegangen, für welche Stützstellen xi der darin stehende Ausdruck

\max_{x \in [a, b]} |\omega(x)| = \max_{x \in [a, b]} |(x - x_0) \cdots (x - x_n)|

am kleinsten wird, d. h. es soll das Minimax-Problem

\min_{x_0, \ldots, x_n \in [a, b]} \max_{x \in [a, b]} |(x - x_0) \cdots (x - x_n)|

gelöst werden. Da jedes Polynom vom Grad n + 1 mit Hauptkoeffizientem 1 mit Hilfe seiner Nullstellen xi als Produkt (x - x_0) \cdots (x - x_n) geschrieben werden kann, ist also ein Polynom gesucht, welches unter allen Polynomen vom Grad n + 1 mit Hauptkoeffizienten 1 die Maximumnorm bezüglich [a,b] minimal macht. Wählt man die n + 1 Nullstellen eines solchen Polynoms als Stützstellen, so erzeugt also das zugehörige Interpolationspolynom p unter allen Interpolationspolynomen zu n + 1 Stützpunkten (xi,f(xi)) die kleinste obere Fehlerschranke in (6.20).

Wir betrachten zunächst nur das Intervall [a,b]: = [ − 1,1]. Es wird sich im Folgenden herausstellen, dass die gesuchten „optimalen“ Stützstellen x_i \in [-1, 1] gerade die Nullstellen des (n + 1)-ten Tschebyscheff-Polynoms erster Art sind.

[Bearbeiten] Definition 6.17

Die Funktionen
(6.21) T_n(x) := \cos(n \arccos(x)), \quad x \in [-1, 1], \quad n = 0, 1, \ldots
heißen Tschebyscheff-Polynome erster Art.

Im folgenden Satz sind einige Eigenschaften dieser Funktionen aufgeführt.

[Bearbeiten] Satz 6.18

Für Tn wie in (6.21) gelten die folgenden Aussagen:
(i) T_n(\cos(\theta)) = \cos(n\theta), \quad \theta \in [0, \pi], \quad n = 0, 1, \ldots
(ii) Für x \in [-1, 1] gilt T0(x) = 1,T1(x) = x und
(6.22) T_{n+1}(x) = 2xT_n(x) - T_{n-1}(x), \quad n = 1, 2, \ldots
und Fortsetzung des Definitionsbereichs der so definierten Tn auf ganz \R liefert
(6.23) T_n \in \Pi_n.
(iii) Tn hat für n \ge 1 den Hauptkoeffizienten 2n − 1.
(iv) Es gilt
\max_{x \in [-1, 1]} |T_n(x)| = 1.
(v) Tn besitzt die n einfachen Nullstellen
(6.24) x^{(n)}_j := \cos \left( \frac{(2j + 1) \pi}{2n} \right), \quad j = 0, \ldots, n - 1,
welche alle in dem Intervall [ − 1,1] liegen.
(vi) Tn besitzt in dem Intervall [ − 1,1] insgesamt n + 1 Extremwerte
T_n(y^{(n)}_j) = (-1)^j, \quad j = 0, 1, \ldots, n
für
(6.25) y^{(n)}_j := \cos \left( \frac{j\pi}n \right), \quad j = 0, 1, \ldots, n

[Bearbeiten] Beweis.

(i) gilt offensichtlich und die Darstellungen für T0 und T1 in (ii) ergeben sich sofort aus der Definition (6.21). Für die Herleitung der Rekursionsformel (6.22) benötigen wir die Formel

\cos(\alpha) + \cos(\beta) = 2 \cos \left( \frac{\alpha + \beta}2 \right) \cos \left( \frac{\alpha - \beta}2 \right), \quad \alpha, \beta \in \R.

Mit (i) liefert diese für x = cos(θ),α: = (n + 1)θ und β: = (n − 1)θ

Tn + 1(x) = cos[(n + 1)θ] = 2cos(θ)cos(nθ) − cos[(n − 1)θ] = 2xTn(x) − Tn − 1(x).

Weiter folgt (iii) aus der Rekursionsformel (ii) und folgt (iv) mit (i) wegen

\max_{x \in [-1, 1]} |T_n(x)| = \max_{\theta \in [0, \pi]} |T_n(\cos(\theta))| = \max_{\theta \in [0, \pi]} |\cos(n\theta)| = 1.

Schließlich sind die Aussagen (v) und (vi) offensichtlich richtig.

q.e.d.

Nach Satz 6.18 (iii) und (v) gilt mit den Nullstellen x^{(n+1)}_j von Tn + 1 wie in (6.24) die Darstellung

(6.26) \left[ \frac 1{2^n} T_{n+1} \right] (x) = (x - x^{(n+1)}_0) \cdots (x - x^{(n+1)}_n).

Der folgende Satz besagt nun, dass dieses Polynom unter allen Polynomen vom Grad n + 1 mit Hauptkoeffizienten 1 die Maximumnorm auf [ − 1,1] minimal macht und dass man überdies den zugehörigen Wert dieser Norm auch angeben kann.

[Bearbeiten] Satz 6.19

Für n \in \N_0 und die x^{(n+1)}_j wie in (6.24) gilt die folgende Optimalitätseigenschaft:

(6.27) \min_{x_0, \ldots, x_n \in [-1, 1]} \max_{x \in [-1, 1]} |(x - x_0) \cdots (x - x_n)| = \max_{x \in [-1, 1]} \left|(x - x_0^{(n + 1)}) \cdots (x - x_n^{(n + 1)})\right| = \frac 1{2^n}.

[Bearbeiten] Beweis.

Die zweite Identität folgt aus (6.26) mit Satz 6.18 (iv). Weiter ist bei der ersten Identität in (6.27) die Abschätzung „\le“ offensichtlich. Die Abschätzung „\ge“ soll nun durch eine Widerspruchsannahme nachgewiesen werden.

Angenommen, es gibt Zahlen x_0, \ldots, x_n \in [-1, 1] mit

(6.28) \frac 1{2^n} > \max_{x \in [-1, 1]} |\omega(x)|

für \omega(x) := (x - x_0) \cdots (x - x_n). Also ist insbesondere

(6.29) - \frac 1{2^n} < \omega(x) < \frac 1{2n}, \quad x \in [-1, 1].

Für das Polynom

q(x) := \frac 1{2^n} T_{n+1}(x) - \omega(x)

schließt man mit (6.25) und (6.29)

\begin{array}{c c c c} \left[ \frac 1{2^n}T_{n+1}\right] (y_0^{(n+1)})=\frac 1{2^n}, & \omega(y_0^{(n+1)})<\frac 1{2^n} & \Rightarrow & q(y_0^{(n+1)})>0, \\ \left[ \frac 1{2^n}T_{n+1}\right] (y_1^{(n+1)})=-\frac 1{2^n}, & \omega(y_1^{(n+1)})>-\frac 1{2^n} & \Rightarrow & q(y_1^{(n+1)})<0, \\ \left[ \frac 1{2^n}T_{n+1}\right] (y_2^{(n+1)})=\frac 1{2^n}, & \omega(y_2^{(n+1)})<\frac 1{2^n} & \Rightarrow & q(y_2^{(n+1)})>0. \\ \vdots & \vdots & \vdots & \vdots \end{array}

Also hat q mindestens n + 1 Vorzeichenwechsel in [ − 1,1] und gilt allgemein

q(y^{(n+1)}_j) q(y^{(n+1)}_{j-1}) < 0, \quad j = 1, \ldots, n + 1.

Das Polynom q besitzt demnach n + 1 einfache paarweise verschiedene Nullstellen in [ − 1,1]. Nun ist sowohl Tn + 1 / 2n als auch ω ein Polynom vom Grad n + 1 und besitzen beide Funktionen den führenden Koeffizienten 1, so dass notwendigerweise q \in \Pi_n gilt. Da q im Fall q \neq 0 nur höchstens n paarweise verschiedene Nullstellen haben kann, folgt q \equiv 0 bzw.

\frac 1{2^n} T_{n+1} \equiv \omega,

was aber wegen Satz 6.18 (iv) und (6.29) der Annahme (6.28) widerspricht.

q.e.d.

Damit haben wir den Fall [a,b]: = [ − 1,1] behandelt. Abschließend werden wir nun noch allgemeine Intervalle [a,b] betrachten. Dazu verwenden wir die affin-lineare Transformation

(6.30) \psi: [-1, 1] \to [a, b], \quad \psi(t) := \frac 12 [a + b + (b - a)t],

mit welcher der nachfolgende Satz leicht aus Satz 6.19 zu schließen ist.

[Bearbeiten] Satz 6.20

Mit der Funktion ψ aus (6.30) und den x^{(n+1)}_j wie in (6.24) gilt die Optimalitätseigenschaft
\min_{x_0, \ldots, x_n \in [a, b]} \max_{x \in [a, b]} |(x - x_0) \cdots (x - x_n)|
(6.31) = \max_{x \in [a, b]} \Bigl| \Bigl( x - \psi(x^{(n+1)}_0) \Bigr) \cdots \Bigl( x - \psi(x^{(n+1)}_n) \Bigr) \Bigr|
(6.32) = \frac{(b - a)^{n+1}}{2^{2n+1}}.

[Bearbeiten] Beweis.

Die Identität (6.32) ergibt sich mit Satz 6.19 unter Verwendung von (6.30) aus

\max_{x \in [a, b]} \Bigl| \Bigl( x - \psi(x^{(n+1)}_0) \Bigr) \cdots \Bigl( x - \psi(x^{(n+1)}_n) \Bigr) \Bigr|
= max_{t \in [-1, 1]} \Bigl| \Bigl( \psi(t) - \psi(x^{(n+1)}_0) \Bigr) \cdots \Bigl( \psi(t) - \psi(x^{(n+1)}_n) \Bigr) \Bigr|
= \left( \frac{b - a}2 \right)^{n+1} \max_{t \in [-1, 1]} \left| (t - x^{(n+1)}_0) \cdots (t - x^{(n+1)}_n) \right|
= \left( \frac{b - a}2 \right)^{n+1} \frac 1{2^n} = \frac{(b - a)^{n+1}}{2^{2n+1}}.

Weiter ist in (6.31) sicher die Ungleichung „\le“ richtig. Zum Beweis der Ungleichung „\ge“ seien nun x_0, \ldots, x_n \in [a, b] beliebig. Dann gibt es eindeutig bestimmte Zahlen <math>y_0, \ldots, y_n \in [-1, 1] mit ψ(yk) = xk für k = 0, \ldots, n und mit diesen erhält man ähnlich wie im ersten Teil des Beweises

max_{x \in [a, b]} |(x - x_0) \cdots (x - x_n)| = \max_{t \in [-1, 1]} |(\psi(t) - \psi(y_0)) \cdots (\psi(t) - \psi(y_n))|
= \left( \frac{b - a}2 \right)^{n+1} \max_{t \in [-1, 1]} |(t - y_0) \cdots (t - y_n)| \ge \frac{(b - a)^{n+1}}{2^{2n+1}}.

q.e.d.

[Bearbeiten] Korollar 6.21

Sei f \in C^{n+1}[a, b] und p \in \Pi_n das Interpolationspolynom zu den Stützpunkten (\xi_j, f(\xi_j)), j = 0, 1, \ldots, n mit \xi_j := \psi(x^{(n+1)}_j) für ψ aus (6.30) und x^{(n+1)}_j wie in (6.24). Dann gilt für den Interpolationsfehler
(6.33) \max_{x \in [a, b]} |f(x) - p(x)| \le \frac{(b - a)^{n+1}}{2^{2n+1} \cdot (n + 1)!} \max_{x \in [a, b]} \left| f^{(n+1)}(x) \right|.

Man beachte aber, dass nach dem Satz von Faber 6.16 auch bei Wahl der Tschebyscheff-Knoten die Interpolationspolynome mit wachsendem n nicht gleichmäßig auf [a,b] gegen f konvergieren müssen.

[Bearbeiten] Beispiel 6.22

Gegeben sei die Funktion f(x): = 2e0.75x, welche im Intervall [a,b]: = [ − 2,0] in 5 Punkten durch ein Interpolationspolynom möglichst kleinen Grades so interpoliert werden soll, dass die maximale Schranke für den Approximationsfehler möglichst klein ausfällt. Die Stützstellen sind dann gemäß Korollar 6.21 zu wählen. Da der erste Punkt den Index 0 hat, ist hier n = 4. Mit

\psi(t) := \frac 12 [a + b + (b - a)t] = \frac 12 [-2 + 2t] = t - 1

und (6.24) lauten die gesuchten Stützstellen

Parser-Fehler (Syntaxfehler): \xi_j := \psi(x^{(5)}_j) := \psi \left( \cos \left( \frac{(2j + 1)\pi}{2(4 + 1)} \right) = \cos \left( \frac{(2j + 1)\pi}{10} \right) - 1, \quad j = 0, \ldots, 4.

Demnach errechnet man mit \eta_j := f(\xi_j) = 2e^{0.75 \cdot \xi_j}

\begin{array}{|c||c|c|c|c|c|} \hline j & 0 & 1 & 2 & 3 & 4 \\ \hline \xi_j & -0.048\, 943 & -0.412\, 215 & -1 & -1.587\, 785 & -1.951\, 057 \\ \hline \eta_j & 1.927\, 92 & 1.468\, 12 & 0.944\, 733 & 0.607\, 932 & 0.462\, 946 \\ \hline \end{array}

Man hat weiter für f(x): = 2e0.75x

f'(x) := 2 \cdot \frac 34 e^{\frac 34 x}, \quad f''(x) := 2 \cdot \left( \frac 34 \right)^2 e^{\frac 34 x}, \quad \ldots, \quad f^{(5)}(x) := 2 \cdot \left( \frac 3{2^2} \right)^5 e^{\frac 34 x} = \frac{243}{512} e^{\frac 34 x}

und damit

\max_{x \in [-2, 0]} \left| f^{(5)}(x) \right| = \frac{243}{512} e^{\frac 34 \cdot 0} = \frac{243}{512} \approx 0.474\, 609 \le 0.48.

Für das Interpolationspolynom p4(x) zu den berechneten Stützpunkten kann man also gemäß (6.33) die folgende maximale Abweichung von f(x) auf [ − 2,0] vorhersagen:

\max_{x \in [-2, 0]} |f(x) - p_4(x)| \le \frac{2^5}{2^9 \cdot 5!} \max_{x \in [-2, 0]} \left| f^{(5)}(x) \right| \le \frac 1{16 \cdot 120} 0.48 = 0.000\, 25.

Abschließend sei noch gesagt, dass ein Nachteil der in diesem gesamten Kapitel dargestellten Form der Interpolation ihrer großen Fehlerempfindlichkeit ist. Fehlerhafte Daten yi + δyi wirken sich nicht nur lokal bei der Stützstelle xi aus, sondern verändern den Verlauf über das ganze Intervall hinweg relativ stark. Dies wird an dem folgenden einfachen Beispiel deutlich.

[Bearbeiten] Beispiel 6.23

Seien

x_i := -1 + ih \quad (i = 0, 1, \ldots, 2m), \quad h := 1/m,
y_i := 0 \quad (i = 0, 1, \ldots, 2m), \quad i \neq m, \quad y_m := \varepsilon.

Dann hat man xm = 0 und somit

p(x) = \sum^{2m}_{i=0} y_iL_i(x) = \varepsilon L_m(x) = \varepsilon \prod^{2m}_{j=0 \atop j \neq m} \frac{x - x_j}{-x_j} = \varepsilon \prod^{2m}_{j=0 \atop j \neq m} \frac{x - x_j}{x_j}.

Darstellung des Interpolationspolynoms p(x) und damit des auf f(x): = 0 bezogenen Interpolationsfehlers für z. B. m = 5 zeigt, dass p(x) durch „Messfehler“ \varepsilon := 0.01 und \varepsilon := 0.05 an der Stelle xm = 0 sehr unterschiedlich verändert wird und zwar keineswegs nur an der Stelle xm.

Von „http://de.wikiversity.org/wiki/Kurs:Numerik_I/6_Interpolation“
Persönliche Werkzeuge