Neville-Aitken-Schema

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Inhaltsverzeichnis

1 Problemstellung
2 Existenz und Eindeutigkeit
3 Lemma von Aitken
4 Schema von Neville
5 Dividierte Differenzen
6 Schema der dividierten Differenzen

[Bearbeiten] Problemstellung

Das Schema von Neville/Aitken wird zur effizienten Berechnung der Koeffizienten interpolierender Polynome verwendet. Zu $n + 1$ gegebenen Stützstellen $x_0<...<x_n\,$ mit vorgegebenen Werten $f_i\,$ ist hier ein Polynom $p(x)\,$ vom Grade n gesucht, so dass $p(x_i)=f_i\,$ für alle $i \in (0,...,n)\,$ .

[Bearbeiten] Existenz und Eindeutigkeit

Behauptung: Ein solches Polynom existiert stets und ist mit dieser Eigenschaft eindeutig bestimmt.

Beweis:

Seien $p$ und $q$ Polynome vom Grade $n$ , die an den Stellen $x_i\,$ die Werte $f_i\,$ annehmen. Dann ist $p - q\,$ ein Polynom vom Grade $\le n$ , das an allen (n+1) Stellen $x_i\,$ Nullstellen besitzt. Also ist $p - q\,$ schon überall identisch 0, und das gesuchte Polynom ist eindeutig bestimmt.

Für die Lagrangepolynome $\ell_{i}(x) = \prod_{j=0, j \neq i}^{n} \frac{x-x_{j}}{x_{i}-x_{j}}$

kann man durch Einsetzen verifizieren, dass gilt: $\ell_{i}(x_{j}) = \delta_{ij}\,$

wobei $\delta_{ij}\,$ das Kronecker-Delta darstellt (siehe auch Polynominterpolation). Damit erfüllt $p(x) = \sum_{i=0}^{n} f_{i} \ell_{i}(x)$ die gewünschten Eigenschaften.

In dieser Darstellung ist die Auswertung des Polynoms jedoch zu aufwendig, deshalb versucht man, das Polynom bezüglich einer effizienteren Polynombasis darzustellen. Dies führt zum

[Bearbeiten] Lemma von Aitken

Es bezeichne $p(f|x_i...x_{i+k})(x)\,$ das eindeutig bestimmte Polynom k-ten Grades, das an den angegebenen Stellen durch die jeweiligen $f_j\,$ interpoliert wird. Dann gilt:

$p(f|x_0...x_n)(x) = \frac {(x_0 - x)\, p(f|x_1...x_n)(x) - (x_n - x) \,p(f|x_0...x_{n-1})(x)}{x_0-x_n}$

Beweis: Durch Einsetzen von $x_i\,$ verifiziert man, dass die rechte Seite der Gleichung die Interpolationseigenschaft erfüllt. Die Eindeutigkeit des Interpolationspolynoms liefert dann die Behauptung.

[Bearbeiten] Schema von Neville

Da $p(f|x_i)(x) \equiv f_i\,$ ein eindeutiges und bekanntes konstantes Polynom darstellt, lässt sich die Auswertung von $p(f|x_{0}...x_{n})(x)\,$ mit Hilfe des Lemmas von Aitken an einer Stelle x rekursiv berechnen. Dieses Schema wird als "Schema von Neville" bezeichnet.

Eine Auswertung benötigt also $O(\frac{n(n+1)}{2})$ Operationen. Dies ist bei vielen Funktionsauswertungen des interpolierten Polynoms noch nicht optimal.

[Bearbeiten] Dividierte Differenzen

Eine bessere Darstellung erreicht man durch sogenannte dividierte Differenzen. Es sei $p(f|x_i...x_{i+k})(x)\,$ wieder das eindeutige Interpolationspolynome vom Grade k. Dann bezeichne den höchsten Koeffizienten dieses Polynoms mit $[x_i...x_{i+k}]f\,$ und bezeichne ihn als "dividierte Differenz".

Mit Hilfe der Newton-Basis $N_{k}(x) = \begin{cases} 1 & : k=0 \\ \prod_{j=0}^{k-1}(x-x_{j}) & : k\ge1 \end{cases}$ lässt sich das Interpolationspolynome eindeutig darstellen.

Behauptung: $p(f|x_{0}...x_{n})(x) = \sum_{k=0}^{n} [x_0...x_k]f \, N_k(x)$

Beweis: durch vollständige Induktion. Der Fall n=1 ist trivial. Es gelte die Behauptung bis n-1. Dann gilt:

$p(f|x_{0}...x_{n})(x) = [x_0...x_n]f \, N_n(x) + q(x)\,$ mit einem Polynom $q\,$ vom Grade $\le n-1$ .

Für dieses gilt nun

$q(x)=p(f|x_{0}...x_{n})(x) - [x_0...x_n]f\,N_n(x)$

Insbesondere also (da $N_n(x_i) = 0\,$ für alle $i \in (0..n)$ ): $q(x_i)=f_i\,$ .

Nach der Eindeutigkeit des Interpolationspolynoms gilt daher schon $q(x)=p(f|x_{0}...x_{n-1})(x)\,$ , und nach Induktionsvoraussetzung folgt die Behauptung:

$p(f|x_{0}...x_{n})(x) = [x_0...x_n]f \, N_n(x) + q(x) = [x_0...x_n]f + \sum_{k=0}^{n-1} [x_0...x_k]f \, N_k(x)\,$

[Bearbeiten] Schema der dividierten Differenzen

Die Auswertung des Polynoms dargestellt in der Newton-Basis kann sehr effizient mit dem Horner-Schema durchgeführt werden. Es bleibt, die dividierten Differenzen als Koeffizienten zu berechnen. Aus dem Lemma von Aitken folgt direkt die dazu benötigte Rekursionsformel:

$[x_0...x_n]f = \frac {[x_0...x_{n-1}]f-[x_1...x_{n}]f}{x_0 - x_n}$