Autor: Stefan Huber

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

6.7.2 Darstellungsformen univariater Polynome

Wenn zwei Polynome vom Grad d dieselben d+1 Datenpunkte interpollieren, dann folgt aus der Unisolvenz-Eigenschaft der univariaten Polynome, daß es sich höchstens um zwei verschiedene Darstellungen desselben Polynoms bezüglich verschiedener Basen des $\P _d$ handeln kann. Aus dieser Tatsache kann man zwei wichtige Folgerungen ableiten:

  1. Die "Reihenfolge der Daten hat keinen Einfluß auf das Interpolationspolynom, höchstens auf dessen Darstellung.
  2. Ein numerisches Verfahren, das auf Polynominterpolation beruht, kann mit der am besten dafür geeigneten Darstellung analysiert und mit einer anderen Darstellung - bezüglich einer anderen Basis des Raumes $\P_d$ - praktisch ausgeführt werden.

Monom-Darstellungen

Die Form, bei der ein univariates Polynom als Linearkombination der Monome $1, x, x^2, \dots, x^d$ dargestellt wird (9.6) - die Potenzform eines Polynoms vom Grad d -, ist die mathematische Standardform, wie sie vor allem für theoretische Untersuchungen verwendet wird. Für numerische Berechnungen sind aber oft andere Darstellungen weit günstiger, wie z.B. die Form

P_d(x;c,b_0,b_1,\ldots,b_d) = b_0 + b_1(x - c) + b_2(x - c)^2 + \cdots + b_d(x - c)^d, (Formel 9.8)

die man durch Entwicklung von (9.6) um die Stelle c erhält. Die Form (9.8) der Polynomdarstellung kann - bei geeigneter Wahl der Entwicklungsstelle c - numerisch wesentlich stablier sein als die Form (9.6). Beispiel (Polynom-Auswertung) Der Parabel $1 + (x - 5\,555.5)^2$ entspricht in der Form (9.8) das Polynom

P_2(x) = 30\,863\,580.25 - 11\,111x + x^2.

Berechnet man die Werte $P_2(5\,555)$ und $P_2(5\,554.5)$ mit Zahlen aus $\F(10,6,-9,9,\true)$, so erhält man aufgrund von Auslöschungseffekten nur die grob fehlerhaften Resultate 0 bzw. 100. Die Auswertung der Form (9.8)

\overline{P}_2(x) = 1 + (x - 5\,555.5)^2

ist in diesem Fall ohne Auslöschung möglich und liefert die exakten Werte 1.25 und 2.

Es empfiehlt sich generell, die Form (9.8) der Potenzform (9.6) vorzuziehen, wobei die Wahl der Entwicklungsstelle c möglichst im Schwerpunkt jener x-Werte erfolgen sollte, für die das Polynom ausgewertet werden soll.

Basis der Lagrange-Polynome

Die Lagrange-Polynome $\phi_{d,i} \in \P_d$ (die auch Lagrangesche Basis- oder Elementarpolynome genannt werden) bilden eine Basis

B_d^{L} = \{ \phi_{d,0}, \phi_{d,1}, \ldots, \phi_{d,d} \}

des Vektorraums $\P_d$ . Sie sind für eine gegebene Menge $\{x_0,x_1,\ldots,x_d\}$ von d+1 voneinander verschiedenen Punkten - den Interpolationsknoten - durch folgende Eigenschaften charakterisiert:

\phi_{d,i} (x_j) = \left\{ \begin{array}{cc} 1 & \qquad i = j \\ 0 & \qquad i \ne j. \end{array} \right. (Formel 9.9)

Die Lagrange-Polynome $\phi_{d,0}, \ldots, \phi_{d,d}$ , deren Existenz und Eindeutigkeit nach den Resultaten des Abschnitts 6.6 gesichert ist, kann man z.B. durch ihre Linearfaktorenzerlegung darstellen:

\phi_{d,i} (x) = \frac{x-x_{0 }}{x_i-x_{0 }}\cdot\,\cdots\,\cdot \frac{x-x_{i-1}}{x_i-x_{i-1}}\cdot \frac{x-x_{i+1}}{x_i-x_{i+1}}\cdot\,\cdots\,\cdot \frac{x-x_{d }}{x_i-x_{d }}..

Beispiel (Lagrange-Polynome)

In Abb. 9.4 ist das Lagrange-Polynom $\varphi_{5,3}$ für zwei verschiedene Anordnungen der Interpolationsknoten dargestellt: für äquidistante Knoten auf [-1,1] und die Nullstellen des Tschebyscheff-Polynoms $T_5$ (siehe Abb. 9.7).

Abb. 9.4: Lagrange-Polynom $\varphi_{5,3}(x)$ für die Tschebyscheff-Knoten (--) und die äquidistanten Knoten (--) auf [-1.1]

Diskrete Orthogonalität: Bezüglich des inneren Produktes

\langle f,g\rangle_L := \sum_{k=0}^d f(x_k) g(x_k), (Formel 9.10)

wobei $\{ x_0, x_1, \dots, x_d \}$ die Menge der Interpolationsknoten ist, gilt:

\langle\phi_{d,i}, \phi_{d,j}\rangle_L = \left\{ \begin{array}{l@{\qquad}l} 0 & i \not= j \\ 1 & i = j. \end{array} \right.

Die Lagrange-Basis $B_d^L$ ist also bezüglich (9.10) ein Orthonormalsystem.

Basis der Bernstein-Polynome

Die Bernstein-Polynome $b_{d,i}\in\P_d$ sind durch

$$b_{d,i}(x):={d\choose i} x^i(1-x)^{d-i},\qquad i=0,1,\dots,d,$$

definiert. Auch sie bilden eine Basis

$$B_d^B=\{b_{d,0},b_{d,1},\dots,b_{d,d}\}$$

des linearen Raumes $\P_d$ . Dementsprechend besitzt jedes Polynom $P_d\in\P_d$ eine Darstellung bezüglich der Bernstein-Basis $B_d^B$:

P_d = \sum_{i=0}^{d}\beta_i b_{d,i}. (Formel 9.11)

Die Koeffizienten $\beta_0,\beta_1,\dots,\beta_d$ nennt man aber zumeist nicht Bernstein-, sondern Bézier-Koeffizienten; (9.11) bezeichnet man als Bézier-Darstellung.

Nullstellen: hat genau zwei reelle Nullstellen:

$x=0$ ist eine i-fache Nullstelle,
$x=1$ ist eine (d-i)-fache Nullstelle.

Maxima: $b_{d,i}$ hat in $[0,1]$ hat in [0,1] genau ein Maximum an der Stelle x=i/d.

Basis der Tschebyscheff-Polynome

Von allen Systemen orthogonaler Polynome, die eine Basis des Raumes $\P _d$ bilden, spielen in der Numerischen Datenverarbeitung die Tschebyscheff-Polynome $\{T_0,T_1,\ldots,T_d\}$ die wichtigste Rolle:

T_0(x) & :\equiv & 1 \nonumber \\ T_1(x) & := & x \nonumber \\ T_d(x) & := & 2xT_{d-1}(x) - T_{d-2}(x),\qquad d=2,3,\dots\,. \label{eqn:rtpoly} (Formel 9.12)

Mit Hilfe der Rekursion (9.12) kann man $T_2, T_3, \dots$ ermitteln:

T_2(x) = 2 x^2 - 1, \quad T_3(x) = 4 x^3 - 3x, \quad T_4(x) = 8 x^4 - 8 x^2 + 1, \, \ldots\, . (Formel 9.13)

In (9.13) wird jedes Tschebyscheff-Polynom $T_d$ bezüglich der Monombasis $B_d = \{1,x,x^2,\ldots,x^d\}$ ausgedrückt. Umgekehrt kann man jedes Monom $x^d$ durch die Elemente der Tschebyscheff-Basis

B_d^{T} = \{T_0,T_1,\ldots,T_d\}

ausdrücken:

1 = T_0, \quad x = T_1, \quad x^2 = (T_0 + T_2)/2, \quad x^3 = (3T_1 + T_3)/4, \, \ldots\, .

Jedes beliebige Polynom $P_d \in \P_d$ Kann dementsprechend als Linearkombination von Tschebyscheff-Polynomen dargestellt werden:

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

wobei die Koeffizienten dieser Darstellung mit jenen der Monom-Darstellung (9.6) im allgemeinen nicht übereinstimmen.

Notation (Summe mit Strich)
Die Konvention, den ersten Koeffizienten zu halbieren, was durch $\sum '$ ausgedrückt wird, stammt von der Reihendarstellung beliebiger Funktionen durch

f(x) = {\sum \limits_{i=0}^{\infty}}\mbox{}' a_i T_i(x)= \frac{a_0}{2}+a_1T_1(x)+a_2T_2(x)+\cdots,

womit sich eine einheitliche Formel (10.13) für alle Koeffizienten $a_0,a_1,a_2,\dots$ ergibt.

In manchen Situationen ist auch die Darstellung

!P_d(x) (Formel 9.15)

bei der erster und letzter Summand halbiert werden, zweckmäßig.

Notation (Zweigestrichene Summe)
Durch $\sum''$ wird ausgedrückt, daß bei der Summation der erste und der letzte Summand halbiert werden (vgl. 9.15):

{\sum \limits_{i=0}^d}\mbox{}'' \alpha_i := \frac{\alpha_0}{2} + \alpha_1 + \cdots + \alpha_{d-1} + \frac{\alpha_d}{2}.

Abb. 9.5: Tschebyscheff-Polynome $T_3,\,T_4,\, T_7,\,T_8$ auf [-1,1]

Nullstellen: $ T_d(x) $ hat in [-1,1] d Nullstellen (siehe Abb. 9.6 und Abb. 9.7)

\xi_j \,:=\, \xi_j^{(d)} \,:=\, \cos \left( \frac{2j - 1}{2d} \pi \right), \qquad j = 1, 2, \dots, d.


Abb. 9.6: Nullstellen $\xi_1,\xi_2,\dots,\xi_8$ des Tschebyscheff-Polynoms $T_8$


Abb. 9.7: Nullstellen der Tschebyscheff-Polynome $T_5,\, T_{10},\,T_{15},\,T_{20}$

Extrema: Im Intervall [-1,1] gibe es d+1 Stellen (Extrema)

\eta_k \,:=\, \eta_k^{(d)} \,:=\, \cos \left( \frac{k}{d}\pi \right) , \qquad k = 0, 1, \dots, d, (Formel 9.17)

wo $T_d$ ein Minimum oder ein Maximum besitzt (Rivlin [341]). Dabei gilt

T_d(\eta_k) = (-1)^k, \qquad k = 0, 1, \dots, d,

d.h., an jeder Maximumstelle hat $T_d$ den Wert 1 und an jeder Minimumstelle den Wert -1. Auf [-1,1] gilt somit $\| T_d \|_{\infty} = 1$.

Die Nullstellen und Extrema der Tschebyscheff-Polynome spielen als Interpolationsknoten eine wichtige Rolle.

Terminologie (Tschebyscheff-Abszissen) Falls im folgenden von Tschebyscheff-Abszissen oder -Knoten die Rede ist, handelt es sich um die Nullstellen von $T_d$ . Zur genaueren Unterscheidung wird auch von Tschebyscheff-Extrema gesprochen.

Diskrete Orthogonalität: Bezüglich des speziellen inneren Produktes

\langle f,g\rangle _{T} := \sum_{k=0}^{d}f(\xi_{k})g(\xi_{k}), (Formel 9.18)

wobei $ \{\xi_{0},\dots,\xi_d\} $ die Menge der Nullstellen von $ T_{d+1} $ ist, gilt (Cheney [35]):

\langle T_{i},T_{j}\rangle _{T} = \left\{\begin{array}{ll} 0 & i \not= j \\ (d + 1)/2 & i = j = 1, 2, \dots, d \\ d + 1 & i = j = 0. (Formel 9.19)

Eine ähnliche Eigenschaft gibt es auch bezüglich des inneren Produkts

\langle f,g\rangle _{U} & := & \frac{1}{2}f(\eta_{0})g(\eta_{0}) + f(\eta_{1})g(\eta_{1}) + \, \cdots \nonumber \\ & & \cdots + f(\eta_{d-1})g(\eta_{d-1}) + \frac{1}{2}f(\eta_{d})g(\eta_{d}) = \nonumber \\ & = & {\sum_{k=0}^{d}}\mbox{}'' f(\eta_{k})g(\eta_{k}), \label{eqn:spezinnerprod2} (Formel 9.20)

wobei $ \{\eta_{0},\dots,\eta_d\} $ die Menge der Extrema von $ T_{d} $ ist. Hier gilt:

\langle T_{i},T_{j}\rangle _{U} = \left\{\begin{array}{ll} 0 & i \not= j \\ d/2 & i = j = 1, 2, \dots, d \\ d & i = j = 0. (Formel 9.21)

Bemerkung (Kontinuierliche Orthogonalität)
Die kontinuierliche Orthogonalität der Tschebyscheff-Polynome wird erst in Kapitel 10 behandelt (vgl. Formel (10.11) ).

Minimax-Eigenschaft: Die Tschebyscheff-Polynome sind unter allen Polynomen durch folgende Eigenschaft ausgezeichnet:

Satz 9.3.1 (Tschebyscheff)
Von allen Polynomen $P_d \in \P _d$ mit einem Anfangskoeffizienten $a_d = 1$ hat das Polynom

$$ \frac{1}{2^{d-1}} T_d$$

die kleinste Maximumnorm auf dem Intervall [-1,1]. Wegen $\|T_d\|_{\infty} = 1$ ist dieser Wert $1/2^{d-1}$

Beweis: Rivlin [341].

Die sogenannte Minimax-Eigenschaft der Tschebyscheff-Polynome kann man auch anders formulieren: Unter allen Polynomen mit $\|P_d\|_{\infty} = 1$ auf [-1,1] und $a_d\ne0$ hat das Tschebyscheff-Polynom $T_d$ mit $a_d = 2^{d-1}$ den größten führenden Koeffizienten und das Monom $x^d$ mit $a_d = 1$ den kleinsten. Eine Entwicklung (Darstellung) nach Tschebyscheff-Polynomen hat daher den Vorteil des schellsten Abklingverhaltens der Koeffizenten. Entwicklungen mit schnell abklingenden Koeffizienten ermöglichen sehr "kompakte" Approximationen, wenn man die Terme mit vernachlässigbar (betrags) kleinen Koeffizienten wegläßt.

Eine ausführliche Behandlung wichtiger Eigenschaften der Tschebyscheff-Polynome findet man z.B. in Büchern von Rivlin [341] sowie Fox und Parker [199].

Autor: Stefan Huber

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