[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

Wahl der Interpolationsknoten

Wenn man eine Funktion f auf einem Intervall [a,b] durch ein Interpolationspolynom approximieren will und über die Interpolationsknoten frei verfügen kann, dann sollte man unbedingt die Tschebyscheff-Abszissen verwenden. Man hat dann gegenüber äquidistanten Knoten folgende Vorteile:

Wegen Ungleichung
Formel 7.7.2
(Siehe Satz) ist auch für sehr hohe Grade das so erhaltene Interpolationspolynom in seiner Approximationsqualität kaum schlechter als das bezüglich der Maximumnorm bestapproximierende Polynom $P_d^{*}$ .
Die Empfindlichkeit gegenüber Datenstörungen (die Kondition des Interpolationsproblems) ist schon ab mittleren Polynomgraden deutlich geringer als bei Verwendung äquidistanter Interpolationsknoten.
Die Berechnung einer Tschebyscheff-Darstellung von ist sehr effizient durch Auswertung von ( ) bzw. ( ) möglich.

Wenn man sich für die Funktionsapproximation durch Interpolation an den Tschebyscheff-Knoten entschieden hat, bleibt noch die Frage nach der Wahl der Anzahl der Interpolationsknoten und damit verbunden des Polynomgrades d . Soferne man über Abschätzungen der Ableitungen von f verfügt, kann man die Fehlerformel (

) anwenden. Für $\omega_{d+1}$ gilt

$\omega_{d+1}(x) = (x -\xi_0^{(d)})(x -\xi_1^{(d)}) \cdots (x - \xi_d^{(d)})$

Da die $\xi_j^{(d)}$ laut Voraussetzung die Nullstellen des Tschebyscheff-Polynoms $T_{d+1}$ sind, ist $\omega_{d+1}$ in diesem Fall ein Vielfaches von $T_{d+1}$ . Aus der

und weiters, daß die Tschebyscheff-Abszissen jene Interpolationsknoten in [-1,1] sind, für die

$\max \{ |\omega_{d+1}(x)|: x \in [-1,1] \}$

minimal ist, was neuerlich die Sonderstellung der Tschebyscheff-Abszissen betont. Die Abschätzung ( ) für den Interpolationsfehler lautet daher in diesem Spezialfall

$|e_d(x)| = |P_d(x) - f(x)| \leq \frac{M_{d+1}}{2^d(d+1)!} \qquad \mbox{f$ ,

wobei $M_{d+1}$ eine Schranke für den Betrag der Ableitung $f^{(d+1)}$ auf [-1,1] bezeichnet.

Das Beispiel Approximation der Sinusfunktion zeigt die Anwendung des Gelernten.

Eine Alternative zum Abbruch der Entwicklung eines Interpolationspolynoms mit zu hohem Grad besteht im sukzessiven Erhöhen des Polynomgrades , bis man die gewünschte Approximationsgenauigkeit erreicht hat. Die beiden Vorgehensweisen werden nun genauer beläuchtet.

* * *

Abbruch der Entwicklung in Tschebyscheff-Polynomen

Im häufig auftretenden Fall, daß man über die Ableitungen von f keine Information besitzt, kann man die Polynominterpolation an den Tschebyscheff-Knoten auf folgende Art einsetzen:

Man wählt eine Stützstellenanzahl, bei der mit großer Wahrscheinlichkeit der benötigte Polynomgrad (bei dem man die geforderte Genauigkeit erreicht) überschritten wird. Dann benützt man folgende Eigenschaft der Koeffizienten a_i der Entwicklung

$P_d(x) = \frac{a_0}{2}T_0(x) + a_1T_1(x) + \cdots + a_dT_d(x) = {\sum \limits_{i=0}^d}\mbox{}' a_iT_i(x)$

des Interpolationspolynoms P_d . Die Beträge $|a_0|, |a_1|, \dots$ fallen bis zu einem Niveau, das durch die Genauigkeit der Funktionswerte bestimmt wird (dies kann auch die Genauigkeit der Maschinenzahlen $\Box y_i$ sein, falls sonst keine Störungen der Funktionswerte vorliegen).

bsp1424

bsp1465

Sukzessives Erhöhen des Polynomgrades

Bei dieser Vorgangsweise verwendet man aber nicht die Nullstellen, sondern die Extremstellen der Tschebyscheff-Polynome als Interpolationsknoten. Man kommt auf diese Art zu Interpolationspolynomen mit fast gleich guten Approximationseigenschaften, die den Vorteil haben, daß beim Übergang vom Polynom $Q_d$ zum Polynom $Q_{2d}$ sämtliche f-Auswertungen, die man für die Bestimmung von $Q_d$ benötigt, bei der Berechnung von $Q_{2d}$ wieder verwendet werden können. Man kann dann z.B.

$\max \{ |Q_d(x_j^{2d}) - f(x_j^{2d})|: j = 1,3,5,\dots,2d-1 \}$

als Fehlerschätzung verwenden, $Q_{2d}$ berechnen und gegebenenfalls die Entwicklung abbrechen.

* * *

Beispiele:

Approximation der Sinusfunktion

Die Implementierung der trigonometrischen Funktionen als vordefinierte Unterprogramme in den höheren Programmiersprachen erfolgt oft mit approximierenden Polynomen in einem Periodenintervall oder einem Teil davon. Approximiert man z.B. sin (x) durch ein Interpolationspolynom P_d(x) an den Tschebyscheff-Knoten im Intervall $[-\pi/2,\pi/2]$ , so ergibt sich wegen

$M_d = 1 \qquad \mbox{f$

und

$\omega_{d+1} = \left( \frac{\pi}{2} \right)^{d+1} \frac{T_{d+1}}{2^d}$ ,

wobei der Faktor $(\pi/2)^{d+1}$ von der Umskalierung von [-1,1] auf $[-\pi/2,\pi/2]$ herrührt, die Fehlerabschätzung

|P_d(x)

Das Polynom P₉ mit einer Fehlerschranke $5 \cdot 10^{-8}$ würde für $\F$ (2,24,-125,128,true) bereits eine zufriedenstellende absolute Approximationsgenauigkeit liefern. Durch Verkleinerung des Interpolationsintervalls auf $[0,\pi/4]$ und gleichzeitige Approximation von cos (x) kann der erforderliche Polynomgrad d noch weiter gesenkt werden.

* * *

Approximation der Exponentialfunktion

Interpoliert man f(x) = e^x auf dem Intervall

$\left[-\frac{\ln 2}{2},\,\frac{\ln 2}{2}\right]\,\approx\,\left[-0.347,\, 0.347\right]$

an den Tschebyscheff-Nullstellen durch $P_{100}$ , dann zeigen die Beträge $|a_0|$, $|a_1|,\dots$ das aus Tabelle~\ref{tab:09.KO} ersichtliche Abklingverhalten.

$\begin{table}[hbtp] \caption{Koeffizienten der Entwicklung (\protect\ref{eqn:09.KO}) für die Exponentialfunktion} \label{tab:09.KO} \begin{center} \begin{tabular}{||c|l||c|l||} \hline \strutHline $i$ & \multicolumn{1}{c||}{$|a_i|$} & $i$ & \multicolumn{1}{c||} {$|a_i|$} \\ \hline \strutNachHline 0 & $ 2.532 $ & 5 & $ 5.429 \cdot 10^{-4}$ \\ 1 & $ 1.130 $ & 6 & $ 4.498 \cdot 10^{-5}$ \\ 2 & $ 2.715 \cdot 10^{-1}$ & 7 & $ 3.049 \cdot 10^{-6}$ \\ 3 & $ 4.434 \cdot 10^{-2}$ & 8 & $ 4.528 \cdot 10^{-7}$ \\ \strutVorHline 4 & $ 5.474 \cdot 10^{-3}$ & 9 & $ 3.294 \cdot 10^{-7}$ \\ \hline \end{tabular} \end{center} \end{table}$

Die Werte $a_{10},a_{11},\dots,a_{100}$ bleiben bei einfach genauer Rechnung alle in der Größenordnung $5 \cdot 10^{-7}$ . Man wird in diesem Fall die abgebrochene Entwicklung

$\overline{P}_7(x) := {\sum \limits_{i=0}^7}\mbox{}' a_iT_i(x)$

mit 8 Koeffizienten als Approximation verwenden. Das schnelle Abfallen der |a_i| gegen den "Minimalpegel" ist bei glatten Funktionen, wie bei diesem Beispiel, besonders deutlich. Das Polynom $\overline{P}_7$ stellt das bestapproximierende Polynom im Sinne der kleinsten Quadrate dar (siehe Abschnitt~\ref{s:l2approx}).

* * *

Approximation der Logarithmusfunktion

Interpoliert man $f(x)=\ln x$ auf dem Intervall [0.71,1.41] an 100 Tschebyscheff-Nullstellen, verwendet aber nur k=1,2,...,30 Koeffizienten, so nimmt das Maximum des Approximationsfehlers den nachfolgend dargestellten Verlauf.

Maximaler absoluter Fehler

Abbildung: Maximaler absoluter Fehler bei abgebrochener Tschebyscheff-Interpolation der Logarithmusfunktion zu 100 Knoten im Intervall $[1/\protect\sqrt{2},\protect\sqrt{2}] \approx[0.71,1.41]$

Bereits mit 10 Koeffizienten ist das Maximum des absoluten Approximationsfehlers auf $6.41\cdot10^{-9}$ abgesunken (siehe die nachfolgende Abbildung).

Abbildung absoluter Fehler

Abbildung: Absoluter Fehler der nach 10 Koeffizienten abgebrochenen Tschebyscheff-Interpolation der Logarithmusfunktion zu 100 Knoten im Intervall $[1/\protect\sqrt{2},\protect\sqrt{2}] \approx[0.71,1.41]$

[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]