Um eine gegebene Funktion $f:\R \rightarrow \R$ durch ein Polynom $P_d \in \P _d$ mittels Interpolation zu approximieren, muß man d+1 lineare Funktionale $l_0,l_1,\dots,l_d$ vorgeben und dann jenes Polynom $P_d(x)$ bestimmen, das die Interpolationsbedingungen

$l_i P_d = l_i f, \quad i = 0, 1, \dots, d,$

erfüllt. Im Prinzip könnte man die Koeffizienten von $P_d$ durch Lösung des Gleichungssystems (9.3) mit den Basisfunktionen $g_i := x^i$ und den Werten $u_i := l_i f$ erhalten, müßte dabei jedoch einen $O(d^3)$ -Aufwand in Kauf nehmen. In wichtigen Spezialfällen gelingt es, das Polynom $P_d$ explizit darzustellen und dessen Koeffizienten durch Algorithmen erheblich geringerer Komplexität zu bestimmen.

Lagrange-Basis

Für den Fall $l_i f = f(x_i)$ mit paarweise verschiedenen Knoten $x_0,x_1,\dots,x_d$ kann man den Ansatz

$P_d(x) = \sum \limits_{i=0}^d f(x_i)\cdot \varphi_{d,i}(x)$ (Formel 9.22)

machen, wobei $\varphi_{d,0},\varphi_{d,1},\dots,\varphi_{d,d}$ die Lagrange-Polynome vom Grad d zur Knotenmenge $\{x_0,x_1,\dots,x_d\}$ sind. Da die Polynome $\varphi_{d,i}$ definitionsgemäß die Eigenschaft (9.9) besitzen, gilt $P_d(x_i) = f(x_i)$ : $P_d$ ist das gesuchte Interpolationspolynom. Die Darstellung (9.22) bezeichnet man als die Lagrangesche Form des Interpolationspolynoms.

Die Lagrangesche Darstellung macht die lineare Struktur des Interplationspolynoms $P_d$ bezüglich der Werte $f(x_0),\ldots,f(x_d)$ deutlich sichtbar, da die Basisfunktionen $\varphi_{d,i}$ nur von den Interpolationsknoten $x_0,\ldots,x_d$ abhängen. Für algorithmische Anwendungen kommt die Lagrange-Form jedoch wegen des Aufwandes, den die Berechnung der Funktion $\varphi_{d,i}$ erfordert, nur selten in Betracht.

Tschebyscheff-Basis

Eine Basis des $\P _d$ , die besondere Vorteile für die Numerische Datenverarbeitung besitzt, wird von den Tschebyscheff-Polynomen $\{T_0,T_1,\dots,T_d\}$ abgebildet. Die Koeffizienten $c_0,c_1,\ldots,c_d$ der Darstellung (9.15) sind durch das lineare Gleichungssystem

${\sum \limits_{i=0}^d}\mbox{}'' c_i T_i(x_j) = f(x_j), \quad j = 0, 1, \dots, d,$ (Formel 9.23)

festgelegt. Die Lösung des Gleichungssystems (9.23) erhält man durch sehr einfache Formeln, wenn man als Interpolationsknoten die Tschebyscheff-Nullstellen $\{ \xi_i \}$ oder die Tschebyscheff-Extrema $\{ \eta_i \}$ verwenden kann, da sich in diesen Fällen die diskrete Orthogonalität der Tschebyscheff-Polynome ausnutzen läßt.

Mulitpliziert man z.B. im Falle der Tschebyscheff-Extrema beide Seiten des linearen Gleichungssystems

$P_d(\eta_i) = {\sum \limits_{j=0}^d}\mbox{}'' c_j T_j(\eta_i) = f(\eta_i), \qquad i = 0, 1, \dots, d,$ (Formel 9.24)

von links mit der Matrix

$\left( \begin{array}{ccccc} \frac{1}{2} T_0(\eta_0) & T_0(\eta_1) & \cdots & T_0(\eta_{d-1}) & \frac{1}{2} T_0(\eta_d) \\[1.5ex] \frac{1}{2} T_1(\eta_0) & T_1(\eta_1) & \cdots & T_1(\eta_{d-1}) & \frac{1}{2} T_1(\eta_d) \\ \vdots & \vdots & & \vdots & \vdots \\ \frac{1}{2} T_d(\eta_0) & T_d(\eta_1) & \cdots & T_d(\eta_{d-1}) & \frac{1}{2} T_d(\eta_d) \end{array} \right) ,$

dann erhält man wegen der diskreten Orthogonalität (9.21)

$c_j = \frac{2}{d} \cdot {\sum \limits_{k=0}^d}\mbox{}'' f(\eta_k) T_j(\eta_k), \quad j = 0, 1, \dots, d.$

Da die Tschebyscheff-Polynome auch in der Form

$T_j(x) = \cos (j \arccos x)$

dargestellt werden können, erhält man für die Tschebyscheff-Extrema (9.17) als Interpolationsknoten den besonders einfachen Ausdruck

$c_j = \frac{2}{d} \cdot {\sum \limits_{k=0}^d}\mbox{}'' f(\eta_k) \cos \left(j \cdot \frac{k}{d} \cdot \pi \right), \qquad j = 0, 1, \dots, d,$ (Formel 9.25)

für die Koeffizienten von (9.24).

Analog erhält man für die Tschebyscheff-Nullstellen (9.14) das lineare Gleichungssystem

$P_d(\xi_i) = {\sum \limits_{j=0}^d}\mbox{}' a_j T_j(\xi_i), \qquad i = 0, 1, \dots, d,$

für die Koeffizienten $a_0,a_1,\dots,a_d$ der Darstellung (9.14). Aus der diskreten Orthogonalität (9.19) der Tschebyscheff-Polynome folgt

$a_j & = & \frac{2}{d+1} \cdot {\sum \limits_{k=0}^d}\mbox{}' f(\xi_k) T_j(\xi_k) = \nonumber \\ & = & \frac{2}{d+1} \cdot {\sum \limits_{k=0}^d}\mbox{}' f(\xi_k) \cos \left(j \frac{2k + 1}{2d + 2} \pi \right), \qquad j = 0, 1, \dots, d.\label{eqn:tentwkoeff}$ (Formel 9.26)

Software (Berechnung eines interpolierenden Polynoms)
Die 2 Unterprogramme NAG/e01aef und NAG/e02aff berechnen zu vorgegebenen Datenpunkten die Koeffizienten der Tschebyscheff-Darstellung des entsprechenden Interpolationspolynoms. Während das Unterprogramm NAG/e02aff nur für die Interpolation an den Tschebyscheff-Extrema geeignet ist, können mittels NAG/e01aef Funktionswerte - und auch eventuell zusätzlich vorgegebene Ableitungswerte - an beliebig verteilten, paarweise verschiedenen Abszissen interpoliert werden.
Das Unterprogramm SLATEC/polint berechnet für beliebig verteilte Datenpunkte die Koeffizienten - die sogenannten dividierten Differenzen - der Newton-Darstellung des zugehörigen Interpolationspolynoms (de Boor [40]).

Beispiel (Schwierig zu approximierende Funktion)

$f(x)= \frac{0.9}{\cosh^2(10(x-0.2))} + \frac{0.8}{\cosh^4(10^2(x-0.4))} + \frac{0.9}{\cosh^6(10^3(x-0.54))}$ (Formel 9.27)

ist auf [0,1] beliebig oft differenzierbar, die Folge der Interpolationspolynome $P_d$ auf den Tschebyscheff-Knoten konvergiert daher für $d \to \infty$ gegen $f$ (vgl. Abschnitt 6.7.7 ). Es ist also gewährleistet, daß es für jede Toleranz $\tau$ ein Polynom $P_d$ gibt, das von $f$ um nicht mehr als $\tau$ abweicht. Selbst für bescheidene Werte von $\tau$ sind hierfür allerdings sehr hohe Polynomgrade erforderlich (siehe Abb. 9.8, Abb. 9.9 und Abb. 9.10).

Abb. 9.8: Interpolation der Funktion (9.27) durch ein Polynom zu den 100 auf [0,1] transformierten Tschebyscheff-Abszissen.

Abb. 9.9: Interpolation der Funktion (9.27) durch ein Polynom zu den 1000 auf [0,1] transformierten Tschebyscheff-Abszissen.

Abb. 9.10: Interpolation der Funktion (9.27) durch ein Polynom zu den 10 000 auf [0,1] transformierten Tschebyscheff-Abszissen.

Autor: Stefan Huber

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

6.7.3 Koeffizientenberechnung

Lagrange-Basis

Tschebyscheff-Basis