5.4. Stabilität und Fehlerabschätzung der Polynominterpolation

Wir wollen uns im Folgenden mit der Frage beschäftigen, welche Aussagen man zur numerischen Stabilität der Polynominterpolation machen kann und ob es nützliche Fehlerabschätzungen gibt. Nehmen wir hierfür zuerst an, dass die bisher beobachteten Datenpunkte \((x_i,f_i) \in \mathbb{R}^2, i=0,\ldots,n\) Abtastungen einer zu Grunde liegenden Funktion \(f\) sind, für die gilt \(f(x_i) = f_i\). Dann ergibt sich natürlich die Frage, wie gut das eindeutige Interpolationspolynom \(P \in \Pi_n\), das die Datenpunkte \((x_i,f_i)\) interpoliert, die Funktion \(f\) approximiert.

5.4.1. Fehlerabschätzung

Es wird klar, dass die Abweichung \(|P(x) - f(x)|\) für beliebiges \(x \neq x_i, i=0,\ldots,n\) bei geeigneter Wahl von \(f\) beliebig groß werden kann, falls man keine weiteren Forderungen an die Funktion \(f\) stellt. Folgender Satz liefert eine Fehlerabschätzung für genügend glatte Funktionen

Satz 5.2 (Fehler der Polynominterpolation)

Sei \(f\) eine \((n+1)\)-mal stetig differenzierbare Funktion, d.h. es gilt \(f \in C^{n+1}(\R)\). Seien weiter \((x_i,f_i) \in \mathbb{R}^2, i=0,\ldots,n\) eine Menge von \(n+1\) Datenpunkten deren Stützstellen paarweise verschieden sind mit \(f(x_i) = f_i, i=0,\ldots,n\). Es sei \(P \in \Pi_n\) das eindeutig bestimmte Interpolationspolynom von Grad \(n\), das die Datenpunkte interpoliert mit \(P(x_i) = f_i, i=0,\ldots,n\).

Dann gibt es für jedes \(\overline{x} \in I\) ein \(\xi \in I\) aus dem kleinsten Intervall \(I\), das alle Stützstellen \(x_i\) und \(\overline{x}\) enthält, so dass gilt:

\[f(\overline{x}) - P(\overline{x}) \ = \ \frac{w_{n+1}(\overline{x})}{(n+1)!}f^{(n+1)}(\xi),\]

wobei \(w_{n+1}(x) = (x - x_0)(x - x_1)\ldots (x-x_n)\) die Basispolynome aus der Lagrangeschen Interpolationsformel (5.7) sind.

Proof. Beweis. Für \(\overline{x} = x_i, i\in \lbrace0,\ldots,n \rbrace\) ist nichts zu zeigen, denn sowohl der Fehler \(f(x_i) - P(x_i)\) als auch der Wert \(w_{n+1}(\overline{x})\) sind Null in den Stützstellen. Sei nun also \(\overline{x} \in I\) mit \(\overline{x} \neq x_i, i=0\ldots,n\) beliebig. Wir betrachten nun die Hilfsfunktion

\[F(x) \ \coloneqq \ f(x) - P(x) - K\cdot w_{n+1}(x).\]

Wählt man die Konstante \(K \in \R\) nun so, dass die Funktion \(F\) an der Stelle \(x = \overline{x}\) verschwindet, so stellt man fest, dass \(F\) mindestens die \(n+2\) Nullstellen \(x_0,\ldots,x_n,\overline{x}\) auf dem Intervall \(I\) besitzt.

Nach dem Satz von Rolle besitzt somit \(F'\) mindestens \(n+1\) Nullstellen in \(I\), \(F''\) mindestens \(n\) Nullstellen in \(I\), usw. bis schließlich \(F^{(n+1)}\) mindestens eine Nullstelle \(\xi\) in \(I\) besitzt. Da das Interpolationspolynom \(P \in \Pi_n\) vom Grad \(n\) ist, gilt aber auch schon \(P^{(n+1)}(x) \equiv 0\) und somit erhalten wir für ein \(\xi \in I\)

\[F^{(n+1)}(\xi) \ = \ f^{(n+1)}(\xi) \: - \: \underbrace{P^{(n+1)}(\xi)}_{= 0} \: - \: K \cdot (n+1)! \ = \ 0.\]

Damit wissen wir, dass die Konstante \(K\) wie folgt gewählt werden muss

\[K \ \coloneqq \ \frac{f^{(n+1)}(\xi)}{(n+1)!}.\]

Mit dieser Wahl folgt dann die Behauptung

\[f(\overline{x}) - P(\overline{x}) \ = \ K \cdot w_{n+1}(\overline{x}) \ = \ \frac{w_{n+1}(\overline{x})}{(n+1)!}f^{(n+1)}(\xi).\]

◻

Um den Fehler in Satz 5.2 noch besser interpretieren zu können, müssen wir zunächst den Term \(w_{n+1}\) vernünftig abschätzen.

Korollar 5.1 (Fehlerabschätzung in der \infty-Norm)

Für ein gegebenes Intervall \(I\), das die Stützstellen \(x_i, i=0,\ldots,n\) enthält, lässt sich die folgende Abschätzung treffen

\[||w_{n+1}||_\infty \ = \ \max_{x\in I} |(x - x_0)\cdot \ldots \cdot (x-x_n)| \ \leq \ \frac{n!}{4} h_{n+1},\]

wobei \(h_{n+1}\) der größte Abstand zweier benachbarter Stützstellen ist. Mit Hilfe dieser Abschätzung können wir eine obere Schranke für den Fehler der Polynominterpolation auf dem Intervall \(I\) angeben:

\[|| f - P||_\infty \ \leq \ \frac{||f^{(n+1)}||_\infty}{4(n+1)}h_{n+1} .\]

Diese Fehlerabschätzung erlaubt es uns in Spezialfällen zu zeigen, dass der Approximationsfehler der Polynominterpolation gleichmäßig gegen \(0\) konvergiert, wie das folgende Lemma zeigt.

Korollar 5.2 (Gleichmäßige Konvergenz)

Sei \(f \in C^\infty(I)\) und es seien alle Ableitung von \(f\) beschränkt, d.h. \(||f^{(n)}||_\infty \leq C, C>0\). Dann lässt sich zeigen, dass der Approximationsfehler der Polynominterpolation für wachsende Anzahl von Stützstellen verschwindet, d.h.,

\[\lim_{n\rightarrow \infty} ||f - P_n||_\infty \ = \ 0.\]

Proof. Beweis. Die Aussage folgt direkt aus dem Korollar 5.1, denn es gilt:

\[\begin{split} \lim_{n\rightarrow \infty} ||f - P_n||_\infty \ &\leq \ \lim_{n\rightarrow \infty} \frac{||f^{(n+1)}||\infty}{4(n+1)}h_{n+1} \\ \ &\leq \ \lim_{n\rightarrow \infty} \frac{C}{4(n+1)}h_{n+1} \ = \ 0. \end{split}\]

◻

Wir können im Allgemeinen nicht davon ausgehen, dass wir bei der Interpolation einer Funktion \(f\) auf einem festen Intervall \(I\) immer mehr Stützstellen hinzunehmen können und damit die Funktion \(f\) in \(I\) immer besser approximieren. Es lässt sich nämlich zeigen, dass zu gegebenen Datenpunkten \((x_i,f_i) \in \mathbb{R}^2, i=0,\ldots,n\) auf einem Intervall \(I\) immer eine stetige Funktion \(f \in C^0(I)\) existiert, so dass das Interpolationspolynom \(P \in \Pi_n\) nicht gleichmäßig, d.h. bezüglich der Maximumsnorm, gegen \(f\) konvergiert. Dies können wir mit Hilfe des folgenden berühmten Beispiels zeigen.

Beispiel 5.5 (Runges Gegenbeispiel)

Wir nehmen an, dass wir die Funktion

\[f(x) \ = \ \frac{1}{1 + x^2}, \qquad -5 \leq x \leq 5\]

mit Hilfe der Langrangeschen Interpolationsformel auf einem äquidistanten Gitter approximieren wollen. Es kann gezeigt werden, dass es Punkte \(x\) innerhalb des Interpolationsintervalls gibt, so dass für die Folge der Interpolationspolynome \(\lbrace P_n\rbrace_{n\in \mathbb{N}}\) gilt

\[\lim_{n\rightarrow \infty} |f(x) - P_n(x)| \ \neq \ 0.\]

Speziell kann man zeigen, dass die Folge der Interpolationspolynome \(P_n\) divergiert für alle Punkte \(x\) mit \(|x| > 3.63\ldots\). Dieses Phänomen ist auf die Wahl von äquidistanten Stützstellen \(x_i\) zurückzuführen. Betrachten wir die \(n\)-te Ableitung der Funktion \(f\), welche gegeben ist durch

\[f^{(n)}(x) \ = \ (-1)^n \cdot n! \cdot \frac{\sin[(n+1)\operatorname{arccot(x)}]}{(1+x^2)^\frac{n+1}{2}},\]

so können wir approximativ sagen, dass sich \(f^{(n)}\) asymptotisch verhält wie \(n!\). Mit Hilfe der Fehlerabschätzung in Korollar 5.1 können wir damit das asympotische Verhalten des Approximationsfehlers in Runges Gegenbeispiel angeben als:

\[||f - P_n||_\infty \ \leq \ \frac{||f^{(n+1)}||_\infty}{4(n+1)}h_{n+1} \ \simeq \ \frac{2\pi\cdot 10}{4} \cdot \left( \frac{10}{e} \right)^n \cdot \frac{1}{\sqrt{n}}.\]

Mit der Regel von L’Hospital lässt sich zeigen, dass die obere Schranke an den Fehler für \(n\rightarrow \infty\) divergiert und man somit mit wachsender Anzahl von Stützstellen potentiell einen immer größeren Approximationsfehler macht. Dies lässt sich auch numerisch belegen.

5.4.2. Stabilität unter Störungen

Wir wollen uns abschließend mit der Frage beschäftigen wie stabil die Bestimmung des eindeutigen Interpolationspolynoms \(P\) mit Bezug auf kleine Änderungen der Stützwerte \(f_i = f(x_i)\) ist. Solche kleinen Abweichungen können durch verschiedene Störungen wie Messfehler oder Rundungsfehler auftreten.

Betrachten wir hierzu eine Menge von Funktionswerten \(\tilde{f}(x_i), i=0,\ldots,n\), die eine Störung der Daten \(f(x_i)\) in den Stützstellen \(x_i, i=0,\ldots,n\) im Intervall \(I\) sei. Bezeichnen wir nun mit \(P \in \Pi_n\) das Interpolationspolynom durch die ungestörten Stützwerte \(f(x_i), i=0,\ldots,n\) und mit \(\tilde{P} \in \Pi_n\) das Interpolationspolynom durch die gestörten Stützwerte \(\tilde{f}(x_i), i=0,\ldots,n\). Dann betrachten wir die maximale Abweichung zwischen den beiden Polynomen in der Lagrangeschen Interpolationsdarstellung aus Interpolationsformel nach Lagrange auf dem Intervall \(I\) durch

\[\begin{split} || P - \tilde{P} ||_\infty \ &= \ \max_{x\in I} \, \left| \sum_{i=0}^n(f(x_i) - \tilde{f}(x_i)) L_i(x) \right| \\ \ &\leq \ \Lambda_n \max_{i=0,\ldots,n} |f(x_i) - \tilde{f}(x_i)|, \end{split}\]

wobei \(L_i(x)\) das Lagrangesche Basispolynom in (5.5) ist und \(\Lambda_n \coloneqq || \sum_{i=0}^n|L_i|~||_\infty\) die Lebesguekonstante des Interpolationsproblems, für die man zeigen kann, dass gilt

\[\Lambda_n \ > \ \frac{2}{\pi} \log(n+1) - C.\]

Hierbei ist \(C > 0\) eine Konstante, die nur von den Datenpunkten \((x_i,f_i) \in \mathbb{R}^2, i=0,\ldots,n\) abhängt. Das heißt es gilt, dass \(\Lambda_n \rightarrow \infty\) für \(n \rightarrow \infty\). Wir können also folgern, dass kleine Abweichungen in den Stützwerten \(f(x_i)\) nur dann zu kleinen Änderungen im Interpolationspolynom führen, wenn die Lebesguekonstante klein ist. Sie spielt hier die Rolle der Konditionszahl des Interpolationsproblems.

Als abschließendes Fazit lässt sich sagen, dass das Interpolationsproblem mit wachsender Anzahl an Datenpunkten \((x_i,f_i) \in \mathbb{R}^2\) zunehmend instabiler wird und zugleich in der Regel keine gute Approximation an eine gegebene Funktion \(f\) darstellt. Mögliche Optionen zu Vermeidung dieser Probleme sind die Verwendung von Tschebyscheff-Polynomen, welche die \(\infty\)-Norm des Approximationsfehlers minimieren oder ein lokaler Ansatz basierend auf Splines. Mit Letzeren wollen wir uns im Folgenden näher beschäftigen.