5.2. Vandermonde-Matrix

Anstatt für eine gegebene Menge von \(n+1\) Datenpunkten ein Interpolationspolynom mit Hilfe der Lagrangschen Interpolationsformel (5.7) zu berechnen, lassen sich auch Monome als Basisfunktionen \(g_k(x) \coloneqq x^k, k=0,\ldots,n\) wählen, so dass man ein anderes lineares Gleichungssystem in (5.3) erhält, bei der die Matrix \(A\) die sogenannte Vandermonde-Matrix darstellt.

Definition 5.4 (Vandermonde-Matrix)

Seien \((x_i,f_i) \in \mathbb{R}^2, i=0,\ldots,n\) eine Menge von \(n+1\) gemessenen Datenpunkten. Wir bezeichnen die Matrix

(5.8)\[A \ = \ \begin{pmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^n\\ 1 & x_1 & x_1^2 & \cdots & x_1^n\\ \vdots & & \vdots & & \vdots\\ 1 & x_n & x_n^2 & \cdots & x_n^n \end{pmatrix}\]

als Vandermonde-Matrix.

Mit ihr lässt sich das eindeutige Interpolationspolynom als Lösung des Gleichungssystems \(Ax = b\) bestimmen, wobei \(x = (a_0,\ldots,a_n)^T\) die unbekannten Koeffizienten des Polynoms darstellen und \(b = (f_0, \ldots, f_n)^T\) die beobachteten Stützwerte sind.

Bemerkung 5.3

Wir können folgende Aussagen zur Bestimmung des Interpolationspolynoms \(P(x)\) mit Hilfe der Vandermonde-Matrix machen:

1. Es lässt sich leicht zeigen, dass die Vandermonde-Matrix in (5.8) genau dann invertierbar ist, wenn die Datenpunkte \((x_i,f_i) \in \mathbb{R}^2, i=0,\ldots,n\) paarweise verschieden sind.

2. Die numerische Lösung des resultierenden linearen Gleichungssystems \(Ax = b\) ist in der Regel numerisch ineffizient, da die Vandermonde-Matrix im Allgemeinen voll besetzt ist und keine weiteren günstigen Eigenschaften aufweist, z.B., Hermizität. Aus diesem Grund sollte man diese Herangehensweise für eine große Anzahl \(n \in\mathbb{N}, n >\!\!> 1\) von Datenpunkten nur dann wählen, wenn man eine Reihe von \(m \in \mathbb{N}\) Interpolationsproblemen mit gleichen Stützstellen \(x_0,\ldots,x_n\) betrachtet bei der sich nur die Stützwerte \(f_0,\ldots,f_n\) ändern. Denn dann muss man die Matrix \(A\) nur ein einziges Mal invertieren.

3. Die numerische Lösung des resultierenden linearen Gleichungssystems \(Ax = b\) ist in der Regel numerisch instabil, da die Vandermonde-Matrix sehr schlecht konditioniert ist.

Um den Wert eines Polynoms \(P \in \Pi_n\), mit \(P(x) = \sum_{k=0}^na_kx^k\) an einer Stelle \(\xi \in \R\) auszurechnen benötigen wir \(n\) Additionen und \(2n\) Multiplikationen. Jedoch gibt es eine alternative Schreibweise des Polynoms \(P(x)\), die uns eine günstigere Auswertung erlaubt.

Definition 5.5 (Horner-Schema)

Sei \(P(x) \in \Pi_n\) ein Polynom von Grad \(n \in \N\) mit der Darstellung

\[P(x) \ = \ a_0 + a_1x + a_2x^2 + \ldots + a_nx^n.\]

Dann lautet eine äquivalente Darstellung von \(P\) im Horner-Schema wie folgt:

(5.9)\[P(x) \ = \ (\ldots(a_nx + a_{n-1})x + a_{n-2})x \ldots )x + a_1)x + a_0.\]

Der numerische Rechenaufwand zur Berechnung des Polynoms \(P\) an einer Stelle \(\xi \in \R\) reduziert sich durch die Verwendung des Horner-Schemas in Definition 5.5 signifikant, da wir nun nur noch \(n\) Multiplikationen und \(n\) Additionen durchführen müssen.