Kurs:Numerik I/Interpolation

Interpolationsproblem

Das Problem der Interpolation besteht allgemein darin, für $m$ gegebene Stützpunkte bzw. Daten $(x_{i},y_{i}),i=1,\ldots ,m$ ein Funktion $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 $y_{i}$ von einer gegebenen, in den $x_{i}$ definierten Funktion $f$ herrühren, d. h. kann

$y_{i}:=f(x_{i})\quad (i=1,\ldots ,m)$

gelten.

Zielsetzung

Ähnlich wie bei der Ausgleichsrechnung geht es also darum, eine große Zahl von Daten durch eine Funktion zu ersetzen bzw. eine Funktion $f$, die möglicherweise durch eine komplizierte und numerisch aufwendig auszuwertende Vorschrift definiert ist, durch eine Funktion $z$ mit einer einfacheren Vorschrift anzunähern, die ebenfalls die Daten $\mathbb {D} :=\{(x_{i},y_{i})\,:\,i=1,\ldots ,m\}$ interpoliert.

Unterschied zur Ausgleichsrechnung

Bei bei der Interpolation wird im Unterschied zur Ausgleichsrechnung gefordert, dass der Graph der gesuchten Funktion $z$ genau durch die Punkte $(x_{i},y_{i})$ verläuft und nicht nur mit einem möglichst geringen Fehler annähert.

Beispiel - Lineare Regression

Bei der linearen Regression versucht man eine Ausgleichsgerade zu finden, dessen Abstand zu den Daten $\mathbb {D} :=\{(x_{i},y_{i})\,:\,i=1,\ldots ,m\}$ minimiert. Das aus den Daten entstehende Gleichungssystem ist überbestimmt und daher im Allgemeinen nicht eindeutig lösbar. Eine Interpolation von mehr als zwei Datenpunkten mit einem Polynom 1. Grades ist daher im Allgemeinen nicht möglich.

Ansatzraumes

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}}\leq n\}$

der Funktionenraum aller Polynome vom Höchstgrad $n$, also ${\mathcal {Z}}_{m}:=\Pi _{n}$ mit $m:=n+1$ ist.

Polynominterpolation

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.

Satz - Eindeutigkeitssatz - Interpolationsproblem

Das Interpolationsproblem (IP) hat eine eindeutige Lösung $p\in \Pi _{n}$.

Beweis.

Sei $p\in \Pi _{n}$ in der Form

$p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n}x^{n}$

gegeben. Dann lauten die Gleichungen (6.3)

(6.4) $a_{0}+a_{1}x_{i}+a_{2}x_{i}^{2}+\ldots +a_{n}x_{i}^{n}=y_{i}\quad (i=0,1,\ldots ,n).$

Dies sind $n+1$ Gleichungen in den $n+1$ Unbekannten $a_{i}$ $(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_{0}^{n}\\1&x_{1}&\ldots &x_{1}^{n}\\\vdots &\vdots &\ddots &\vdots \\1&x_{n}&\ldots &x_{n}^{n}\end{pmatrix}}.$

Ihre Determinante, die Vandermonde-Determinante, ist durch

$\det(V)=\prod _{0\leq i<k\leq 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.

6.2 Die Lagrangesche Darstellung des Interpolationspolynoms

Wir führen zunächst spezielle Polynome ein:

Definition 6.2

Zu $n+1$ Stützstellen $x_{i}$ $(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 _{j=0 \atop j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}.$

Offenbar hat das Lagrangesche Basispolynom $L_{i}$ die $n$ Nullstellen $x_{k}$ $(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 _{i=0}^{n}a_{i}L_{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 _{i=0}^{n}a_{i}L_{i}(x)=0\quad (x\in \mathbb {R} )\quad \Rightarrow \quad a_{i}=0\quad (i=0,1,\ldots ,n).$

Das heißt, die $L_{i}$ 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 $\Pi _{n}$, so dass sich jedes Polynom vom Höchstgrad $n$ und damit auch das eindeutig bestimmte Interpolationspolynom als Linearkombination der $L_{i}$ 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 _{i=0}^{n}a_{i}L_{i}(x),$

so folgt mit (6.3) und (6.5)

$y_{k}=p(x_{k})=\sum _{i=0}^{n}a_{i}L_{i}(x_{k})=a_{k}L_{k}(x_{k})=a_{k}\quad (k=0,1,\ldots ,n)$

und damit die Lagrangesche Darstellung des Interpolationspolynoms

(6.7) $p(x)=\sum _{i=0}^{n}y_{i}L_{i}(x).$

Sie hat den Vorteil, dass man an ihr die Stützwerte $y_{i}$ für die Stützpunkte $x_{i}$ und damit die Interpolationsbedingungen (6.3) sofort ablesen kann.

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

$\mathbb {R} ^{n+1}\to \Pi _{n},\quad (y_{0},\ldots ,y_{n})^{T}\mapsto p,$

die für vorgegebene, paarweise verschiedene $x_{i}$ jeder Menge von $n+1$ Stützwerten $y_{i}$ 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 $L_{i}(\xi )$ in einem Punkt $\xi$ für ein $i$ verlangt insgesamt $2(n-1)$ Produkte und 1 Division, so dass für die Auswertung des Interpolationspolynoms an einer Stelle $\xi$ 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 $L_{i}$ und damit des gesamten Interpolationspolynoms.

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:

Definition 6.4

Zu $n+1$ Stützpunkten $(x_{i},y_{i})$ wie in (6.1) und (6.2) bezeichne $P_{i,i+1,\ldots ,i+m}$ das (eindeutig bestimmte) Polynom vom Grad $\leq 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\geq 0$ und $i+m\leq 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:

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\geq 1$.

Beweis.

Die Identität (6.9) ist wegen $P_{i}\in \Pi _{0}$ und $P_{i}(x_{i})=y_{i}$ 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 $\leq 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 _{i=1}^{n}i={\frac {3}{2}}n(n+1)$

Multiplikationen und Divisionen benötigt.

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 {5}{2}},$

$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.

6.4 Die Newtonsche Darstellung des Interpolationspolynoms

Wir definieren zunächst:

Definition 6.7

Zu gegebenen $n+1$ Stützstellen $x_{i}$ $(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 _{j=0}^{i-1}(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 _{i=0}^{n}a_{i}N_{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 $a_{i}$ für das Interpolationspolynom $p\in \Pi _{n}$ bestimmt werden.

Die Koeffizienten $a_{i}$ in (6.11) lassen sich nacheinander aus den Gleichungen

$y_{0}=p(x_{0})=a_{0},$

$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 _{j=1}^{n}\sum _{i=1}^{j}i={\frac {1}{2}}\sum _{j=1}^{n}j(j+1)={\frac {n(n+1)(2n+1)}{12}}+{\frac {n(n+1)}{4}}={\frac {1}{6}}n^{3}+{\frac {1}{2}}n^{2}+{\frac {1}{3}}n$

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

Definition 6.8

Für $n+1$ Stützpunkte $(x_{i},y_{i})$ wie in (6.1) und (6.2) heißen die Zahlen

$y[x_{i}]:=y_{i},$

(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\geq 0$ und $i+k\leq 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 _{i=1}^{n}i={\frac {1}{2}}n(n+1)$

Divisionen benötigt. Ferner gilt folgender Satz:

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.$

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 \mathbb {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 \mathbb {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+ax^{n+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 $a_{n+1}$ berechnen, indem man im Schema der dividierten Differenzen unten eine zusätzliche Zeile für diesen Punkt berechnet.

Sind schließlich die Koeffizienten $a_{i}$ der Newtonschen Darstellung (6.11) des Interpolationspolynoms $p$ bekannt, so kann dieses für jedes $x:=\xi$ 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.

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 {1}{2}}&\rightarrow &y[x_{0},x_{1},x_{2}]={\frac {y[x_{1},x_{2}]-y[x_{0},x_{1}]}{x_{2}-x_{0}}}=-{\frac {5}{6}}\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 {5}{6}}x(x-1).$

Nimmt man beispielsweise den Punkt $(x_{3},y_{3}):=\left(2,{\frac {5}{2}}\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 {1}{2}}&-{\frac {5}{6}}&\\2&{\frac {5}{2}}&-{\frac {1}{2}}&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 {5}{6}}x(x-1)+{\frac {5}{12}}x(x-1)(x-3).$

Das Horner-Schema zur Berechnung von letzterem Polynom an der Stelle $\xi :=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 {5}{6}}&2&1\\\hline b_{i}&{\frac {5}{12}}&-{\frac {5}{12}}&{\frac {3}{4}}&{\mbox{4}}\\\hline \end{array}}$

Offenbar ist $p(2)=b_{0}=4$.

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.

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]$.

Beweis.

Da für $x:=x_{i}$ 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

$\psi (t):=f(t)-p(t)-K\omega (t)$

mit

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

so dass $\psi (x)=0$ folgt. Also besitzt $\psi$ 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 $\psi '$ in dem Intervall $[a,b]$ mindestens $n+1$ Nullstellen besitzt, $\psi ''$ mindestens $n$ usw. und somit $\psi ^{(n+1)}$ mindestens noch eine Nullstelle $\xi _{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.

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).$

Beweis.

Mit $x_{n+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 \mathbb {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:

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!}}.$

Beweis.

Für $n=0$ ist die Behauptung trivial und für $n\geq 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:=x_{n}$ 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 \mathbb {N} _{0}$ für den Rest des Unterabschnitts

(6.19) $\Delta _{j}:={\Bigl \{}x_{i}^{(j)}{\Big |}a:=x_{0}^{(j)}<x_{1}^{(j)}<\ldots <x_{n_{j}}^{(j)}:=b{\Bigr \}}$

mit einem $n_{j}\in \mathbb {N} _{0}$ eine Partition von $[a,b]$ und

$\|\Delta _{j}\|:=\max _{1\leq i\leq n_{j}}(x_{i}^{(j)}-x_{i-1}^{(j)})$

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_{i}^{(j)},f(x_{i}^{(j)})),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.

Satz 6.14

Es sei $f\in C^{\infty }[a,b]$ und es gelte mit einem $M\geq 0$

$\max _{x\in [a,b]}\left|f^{(k)}(x)\right|\leq M,\quad k\in \mathbb {N} .$

Weiter sei $\Delta _{j},j\in \mathbb {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.$

Beweis.

Aus Satz 6.11 schließt man

$\max _{x\in [a,b]}|f(x)-p_{j}(x)|\leq {\frac {M}{(n_{j}+1)!}}\max _{x\in [a,b]}\left|(x-x_{0})\cdots (x-x_{n_{j}})\right|\leq {\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.

Beispiel 6.15

Für $f(x):=e^{-0.5x}$ hat man

$f'(x)=-{\frac {1}{2}}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|\leq {\frac {1}{2^{k}}}e^{0}\leq {\frac {1}{2}},\quad k\in \mathbb {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 $\Delta _{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.)

Satz 6.16 (Faber)

Zu jeder Folge von Partitionen $\Delta _{j},j\in \mathbb {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 .$

6.6 Tschebyscheff-Polynome

Der Fehler des Interpolationspolynoms zu $n+1$ vorgegebenen Stützstellen wird durch (6.17) beschrieben. Da der Punkt $\xi _{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)|\leq {\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 $x_{i}$ 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 $x_{i}$ 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 $(x_{i},f(x_{i}))$ 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.

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.

Satz 6.18

Für $T_{n}$ 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 $T_{0}(x)=1,T_{1}(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 $T_{n}$ auf ganz $\mathbb {R}$ liefert

(6.23) $T_{n}\in \Pi _{n}.$

(iii) $T_{n}$ hat für $n\geq 1$ den Hauptkoeffizienten $2^{n-1}$.

(iv) Es gilt

$\max _{x\in [-1,1]}|T_{n}(x)|=1.$

(v) $T_{n}$ besitzt die $n$ einfachen Nullstellen

(6.24) $x_{j}^{(n)}:=\cos \left({\frac {(2j+1)\pi }{2n}}\right),\quad j=0,\ldots ,n-1,$

welche alle in dem Intervall $[-1,1]$ liegen.

(vi) $T_{n}$ besitzt in dem Intervall $[-1,1]$ insgesamt $n+1$ Extremwerte

$T_{n}(y_{j}^{(n)})=(-1)^{j},\quad j=0,1,\ldots ,n$

für

(6.25) $y_{j}^{(n)}:=\cos \left({\frac {j\pi }{n}}\right),\quad j=0,1,\ldots ,n$

Beweis.

(i) gilt offensichtlich und die Darstellungen für $T_{0}$ und $T_{1}$ 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 \mathbb {R} .$

Mit (i) liefert diese für $x=\cos(\theta ),\alpha :=(n+1)\theta$ und $\beta :=(n-1)\theta$

$T_{n+1}(x)=\cos[(n+1)\theta ]=2\cos(\theta )\cos(n\theta )-\cos[(n-1)\theta ]=2xT_{n}(x)-T_{n-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_{j}^{(n+1)}$ von $T_{n+1}$ wie in (6.24) die Darstellung

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

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.

Satz 6.19

Für $n\in \mathbb {N} _{0}$ und die $x_{j}^{(n+1)}$ 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}}}.$

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 „$\leq$“ offensichtlich. Die Abschätzung „$\geq$“ 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_{j}^{(n+1)})q(y_{j-1}^{(n+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 $T_{n+1}/2^{n}$ als auch $\omega$ 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 {1}{2}}[a+b+(b-a)t],$

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

Satz 6.20

Mit der Funktion $\psi$ aus (6.30) und den $x_{j}^{(n+1)}$ 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_{0}^{(n+1)}){\Bigr )}\cdots {\Bigl (}x-\psi (x_{n}^{(n+1)}){\Bigr )}{\Bigr |}$

(6.32) $={\frac {(b-a)^{n+1}}{2^{2n+1}}}.$

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_{0}^{(n+1)}){\Bigr )}\cdots {\Bigl (}x-\psi (x_{n}^{(n+1)}){\Bigr )}{\Bigr |}$

$=max_{t\in [-1,1]}{\Bigl |}{\Bigl (}\psi (t)-\psi (x_{0}^{(n+1)}){\Bigr )}\cdots {\Bigl (}\psi (t)-\psi (x_{n}^{(n+1)}){\Bigr )}{\Bigr |}$

$=\left({\frac {b-a}{2}}\right)^{n+1}\max _{t\in [-1,1]}\left|(t-x_{0}^{(n+1)})\cdots (t-x_{n}^{(n+1)})\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 „$\leq$“ richtig. Zum Beweis der Ungleichung „$\geq$“ seien nun $x_{0},\ldots ,x_{n}\in [a,b]$ beliebig. Dann gibt es eindeutig bestimmte Zahlen $y_{0},\ldots ,y_{n}\in [-1,1]$ mit $\psi (y_{k})=x_{k}$ 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})|\geq {\frac {(b-a)^{n+1}}{2^{2n+1}}}.$

q.e.d.

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_{j}^{(n+1)})$ für $\psi$ aus (6.30) und $x_{j}^{(n+1)}$ wie in (6.24). Dann gilt für den Interpolationsfehler

(6.33) $\max _{x\in [a,b]}|f(x)-p(x)|\leq {\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.

Beispiel 6.22

Gegeben sei die Funktion $f(x):=2e^{0.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 {1}{2}}[a+b+(b-a)t]={\frac {1}{2}}[-2+2t]=t-1$

und (6.24) lauten die gesuchten Stützstellen

$\xi _{j}:=\psi (x_{j}^{(5)}):=\psi \left(\cos \left({\frac {(2j+1)\pi }{2(4+1)}}\right)\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):=2e^{0.75x}$

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

und damit

$\max _{x\in [-2,0]}\left|f^{(5)}(x)\right|={\frac {243}{512}}e^{{\frac {3}{4}}\cdot 0}={\frac {243}{512}}\approx 0.474\,609\leq 0.48.$

Für das Interpolationspolynom $p_{4}(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)|\leq {\frac {2^{5}}{2^{9}\cdot 5!}}\max _{x\in [-2,0]}\left|f^{(5)}(x)\right|\leq {\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 $y_{i}+\delta y_{i}$ wirken sich nicht nur lokal bei der Stützstelle $x_{i}$ aus, sondern verändern den Verlauf über das ganze Intervall hinweg relativ stark. Dies wird an dem folgenden einfachen Beispiel deutlich.

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 $x_{m}=0$ und somit

$p(x)=\sum _{i=0}^{2m}y_{i}L_{i}(x)=\varepsilon L_{m}(x)=\varepsilon \prod _{j=0 \atop j\neq m}^{2m}{\frac {x-x_{j}}{-x_{j}}}=\varepsilon \prod _{j=0 \atop j\neq m}^{2m}{\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 $x_{m}=0$ sehr unterschiedlich verändert wird und zwar keineswegs nur an der Stelle $x_{m}$.

Seiteninformation

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Numerik%20I/Interpolation
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.