Polynominterpolation

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Dividierte Differenzen)
Wechseln zu: Navigation, Suche
Interpolationspolynom 7. Grades

In der numerischen Mathematik versteht man unter Polynominterpolation die Suche nach einem Polynom, welches exakt durch vorgegebene Punkte (z. B. aus einer Messreihe) verläuft. Dieses Polynom wird Interpolationspolynom genannt und man sagt, es interpoliere die gegebenen Punkte.

Anwendungen[Bearbeiten]

Polynome lassen sich sehr leicht integrieren und ableiten. Deswegen tauchen interpolierende Polynome an vielen Stellen in der numerischen Mathematik auf, beispielsweise bei der numerischen Integration und entsprechend bei Verfahren zur numerischen Lösung gewöhnlicher Differentialgleichungen.

Problemstellung[Bearbeiten]

Für n+1 gegebene Wertepaare (x_i,\,f_i) mit paarweise verschiedenen Stützstellen x_i wird ein Polynom P maximal n-ten Grades gesucht, das alle Gleichungen

P(x_i) = f_i, \quad i=0,\dotsc,n

erfüllt. Ein solches Polynom existiert stets und ist eindeutig bestimmt, wie im Folgenden gezeigt wird.

Beim Interpolationsproblem ist also P im Vektorraum \Pi_n der Polynome mit Grad n oder kleiner zu suchen, kurz P \in \Pi_n. Ist \phi_0,\dotsc,\phi_n eine Basis von \Pi_n, so ergeben die Gleichungen P(x_i) = f_i ein lineares Gleichungssystem für die Koeffizienten der Basisdarstellung P = \sum_{k=0}^n a_k \phi_k. Da sich ein und dasselbe Polynom aber unterschiedlich darstellen lässt, je nachdem welche Basis für den Vektorraum \Pi_n gewählt wird, kann man ganz verschiedene Gleichungssysteme erhalten. Wählt man für \Pi_n die Standardbasis \left\{x^k\mid 0\le k\le n\right\}, also für P die Darstellung P(x) = \sum_{k=0}^n a_kx^k, so erhält man ein Gleichungssystem mit der Vandermonde-Matrix:


\begin{pmatrix}
1 & x_0 & \cdots & x_0^n \\
\vdots & \vdots & \ddots & \vdots \\
1 & x_n & \cdots & x_n^n
\end{pmatrix}
\begin{pmatrix}
a_0 \\
\vdots \\
a_n
\end{pmatrix}
= 
\begin{pmatrix}
f_0 \\
\vdots \\
f_n
\end{pmatrix}
.

Diese ist regulär, wenn die Stützstellen x_i paarweise verschieden sind, das Gleichungssystem lässt sich dann eindeutig lösen. Somit ist die Existenz und Eindeutigkeit des gesuchten Polynoms P \in \Pi_n immer sichergestellt. Trotz der theoretischen Machbarkeit wird diese Art der Interpolation in der Praxis nicht durchgeführt, da die Berechnung der Vandermonde-Matrix aufwendig ist (\mathcal O(n^2), siehe Landau-Symbole) und zudem schlecht konditioniert bei einer ungeeigneten Wahl der Stützstellen.

Lösungsverfahren[Bearbeiten]

Obiges Gleichungssystem ließe sich beispielsweise mit dem Gaußschen Eliminationsverfahren lösen. Der Aufwand dafür ist mit \mathcal O(n^3) allerdings vergleichsweise groß. Bei Wahl einer anderen Basis als der Standardbasis zur Beschreibung des Polynoms P kann der Aufwand verringert werden.

Lagrangesche Interpolationsformel[Bearbeiten]

Eher für theoretische Betrachtungen günstig ist eine Darstellung in der Lagrange-Basis. Die Basisfunktionen sind die Lagrange-Polynome

\ell_i(x) = \prod_{\begin{smallmatrix}j=0\\j\neq i\end{smallmatrix}}^n \frac{x-x_j}{x_i-x_j}=\frac{x-x_0}{x_i-x_0}\cdots\frac{x-x_{i-1}}{x_i-x_{i-1}}\cdot\frac{x-x_{i+1}}{x_i-x_{i+1}}\cdots\frac{x-x_n}{x_i-x_n},

die so definiert sind, dass

\ell_i(x_k) = \delta_{ik} = \left\{\begin{matrix}
 1 & \mbox{falls } i=k \\
 0 & \mbox{falls } i \neq k
\end{matrix}\right.

gilt, wobei \delta_{ik} das Kronecker-Delta darstellt. Damit entspricht die Matrix \left(\ell_i\left(x_j\right)\right)_{i,j=0,1,\ldots,n} genau der Einheitsmatrix. Die Lösung des Interpolationsproblems lässt sich dann einfach angeben als

P(x) = \sum_{i=0}^n f_i\ell_i\left(x\right)

mit den Stützwerten f_i. Dies wird häufig benutzt, um die Existenz der Lösung des Interpolationsproblems zu beweisen. Ein Vorteil der Lagrange-Basis ist somit, dass die Basisfunktionen \ell_i von den Stützwerten f_i unabhängig sind. Dadurch lassen sich verschiedene Sätze von Stützwerten f_i mit gleichen Stützstellen x_i schnell interpolieren, wenn die Basisfunktionen \ell_i einmal bestimmt worden sind. Ein Nachteil dieser Darstellung ist jedoch, dass alle Basisvektoren bei Hinzunahme einer einzelnen Stützstelle komplett neu berechnet werden müssen, weshalb dieses Verfahren für die meisten praktischen Zwecke zu aufwendig ist.

Newtonscher Algorithmus[Bearbeiten]

In diesem Verfahren wird das Polynom P in Newton-Basis dargestellt, so dass die Koeffizienten effizient mit dem Schema der dividierten Differenzen bestimmt werden können. Eine effiziente Auswertung des Polynoms kann dann mithilfe des Horner-Schemas erfolgen.

Ansatz: Newton-Basis[Bearbeiten]

Als Ansatz für das gesuchte Interpolationspolynom P wählt man die Newton-Basisfunktionen N_0(x)=1 und \textstyle N_i(x) = \prod_{j=0}^{i-1}\left(x-x_j\right)=\left(x-x_0\right)\cdots\left(x-x_{i-1}\right) mit i=1,\ldots ,n, so dass P dargestellt wird mit der Newtonschen Interpolationsformel

P(x)=\sum_{i=0}^n c_i\cdot N_i(x)=c_0+c_1 \left(x-x_0\right)+c_2 \left(x-x_0\right) \left(x-x_1\right)+\dotsb+c_n\left(x-x_0\right)\dotsm \left(x-x_{n-1}\right)

Das Gleichungssystem der Gleichungen P(x_i) = f_i hat dann die Form


\begin{pmatrix}
1 & & & & 0 \\
1 & (x_1 - x_0) & & & \\
1 & (x_2 - x_0) & (x_2 - x_0)(x_2 - x_1) & & \\
\vdots & \vdots & & \ddots & \\
1 & (x_n - x_0) & \cdots & & \prod_{i=0}^{n-1}(x_n - x_i) \\
\end{pmatrix}
\cdot
  \begin{pmatrix} c_0 \\ \vdots \\ c_n \end{pmatrix}
= \begin{pmatrix} f_0 \\ \vdots \\ f_n \end{pmatrix}

Im Gegensatz zur komplizierten Vandermonde-Matrix bei Wahl der Standardbasis \{x^k|0 \le k \le n\} erhält man bei Wahl der Newton-Basis also eine einfach strukturierte untere Dreiecksmatrix und das Gleichungssystem lässt sich einfach lösen.

Bestimmung der Koeffizienten: Schema der dividierten Differenzen[Bearbeiten]

Die Koeffizienten c_i werden aber nicht direkt aus dem obigen Gleichungssystem bestimmt, sondern effizienter mithilfe der dividierten Differenzen. Durch Induktion beweist man mit der Rekursionsformel von Aitken, dass für die Koeffizienten c_i gilt

c_i = [x_0, \dotsb, x_i]f.

Dabei sind für i<j die dividierten Differenzen [x_i, \dotsc, x_j]f rekursiv definiert durch

[x_i]f = f_i \qquad
[x_i,\dotsc,x_j]f = \frac {[x_{i+1},\dotsc,x_j]f-[x_i,\dotsc,x_{j-1}]f}{x_j - x_i}.

Die Notation mit angehängtem f erklärt sich dadurch, dass oft eine unbekannte Funktion f angenommen wird, die bei bekannten Funktionswerten f_i = f(x_i) interpoliert werden soll.

Die rekursive Berechnung der dividierten Differenzen lässt sich wie folgt veranschaulichen. Dabei sind die gesuchten Koeffizienten c_i genau die oberste Schrägzeile:

\begin{array}{crcrccrcrc}
[x_0]f \\   
       & \searrow \\{}
[x_1]f & \rightarrow  & [x_0,x_1]f  \\
       & \searrow     &                & \searrow     \\{}
[x_2]f & \rightarrow  & [x_1,x_2]f     & \rightarrow & [x_0,x_1,x_2]f \\{}
 \vdots & \vdots      & \vdots         & \vdots    & \vdots  &\ddots \\{}
  & \searrow     &                & \searrow    & &              & \searrow \\{}
[x_{n-1}]f & \rightarrow  & [x_{n-2},x_{n-1}]f & \rightarrow & [x_{n-3},x_{n-2},x_{n-1}]f 
  & \cdots & \rightarrow & [x_0\ldots x_{n-1}]f  \\
  & \searrow     &                & \searrow    & &              & \searrow && \searrow\\{}
[x_n]f & \rightarrow  & [x_{n-1},x_n]f & \rightarrow & [x_{n-2},x_{n-1},x_n]f 
  & \cdots & \rightarrow & [x_1\ldots x_n]f & \rightarrow & [x_0\ldots x_n]f
\end{array}

Offensichtlich ist bei Ergänzung der n+1 Wertepaare (x_i, f_i) um einen weiteren Punkt (x_{n+1}, f_{n+1}) in obigem Schema nur eine weitere Zeile hinzuzufügen, um den zusätzlichen Koeffizienten c_{n+1} = [x_0, \dotsc, x_{n+1}]f zu berechnen. Die zuvor bestimmten Koeffizienten c_0, \dotsc, c_n müssen nicht neu berechnet werden.

Auswertung des Polynoms: Horner-Schema[Bearbeiten]

Wenn die Koeffizienten c_i des Interpolationspolynoms P einmal bekannt sind, kann man es effizient mithilfe des Horner-Schemas auswerten. Dazu schreibt man P in der Form (einfache Umformung der Newtonschen Interpolationsformel)

P(x) = \left(\cdots\left(c_n(x - x_{n-1}\right) + c_{n-1})(x - x_{n-2}) + \dotsb + c_1\right)(x - x_0) + c_0,

so dass P(x) rekursiv berechnet werden kann durch

\begin{align}
b_n & = c_n \\
b_i & = b_{i+1}(x - x_i) + c_i, \qquad i = n - 1, \dotsc, 0 \\
P(x) & = b_0
\end{align}

Dies erfordert einen Aufwand von O(n).

Algorithmus von Neville-Aitken[Bearbeiten]

Ähnlich wie im Newtonschen Algorithmus wird beim Algorithmus von Neville-Aitken die Lösung rekursiv berechnet. Dazu bezeichne p\left(f|x_i...x_{j}\right) das eindeutig bestimmte Interpolationspolynom k-ten Grades zu den k+1 Stützpunkten (x_{i}, f_{i}), \dots, (x_{j}, f_{j}), wobei k=j-i ist. Es gilt dann die Rekursionsformel von Aitken:

\begin{align}p(f|x_i)(x) & \equiv f_i, \\
p(f|x_i, \dotsc, x_{j})(x) & \equiv \frac{(x - x_i)p(f|x_{i+1}, \dotsc, x_{j})(x) - (x - x_{j})p(f|x_{i}, \dotsc, x_{j-1})(x)}{x_{j}-x_{i}}.\end{align}

Beweisen lässt sie sich durch Einsetzen von x_i, wodurch man verifiziert, dass die rechte Seite der Gleichung die Interpolationsbedingung erfüllt. Die Eindeutigkeit des Interpolationspolynoms liefert dann die Behauptung.

Mit dem Schema von Neville kann die Auswertung von p(f|{x_0, \dotsc, x_n})(x) = P(x) dann rekursiv erfolgen:

Polynominterpolation Schema von Neville.jpg

Vergleich der Lösungsverfahren[Bearbeiten]

Möchte man alle Koeffizienten des Interpolationspolynoms P bestimmen, so bietet der Newtonsche Algorithmus hierfür den geringsten notwendigen Aufwand von \mathcal O(n^2). Das so bestimmte Polynom lässt sich dann mit \mathcal O(n) Operationen an einer Stelle auswerten. Darum ist der Newtonsche Algorithmus gut geeignet, wenn das Interpolationspolynom an vielen Stellen ausgewertet werden soll. Auch lassen sich effizient weitere Stützpunkte hinzufügen. Liegen die Stützstellen oder die Stützwerte allerdings zu nahe beieinander, so besteht die Gefahr der Auslöschung bei der Bestimmung der dividierten Differenzen.

Der Neville-Aitken-Algorithmus ist dagegen gut geeignet, wenn ein Interpolationspolynom nur an ganz wenigen Stellen ausgewertet werden soll, dabei ist er weniger anfällig gegen Auslöschung. Auch im Neville-Aitken-Algorithmus lassen sich effizient neue Stützpunkte hinzufügen. So kann z. B. eine gewünschte Genauigkeit der Interpolation an einer Stelle durch Hinzufügen immer weiterer Stützstellen erreicht werden.

Beispiel: Interpolation der Tangensfunktion[Bearbeiten]

Tangensfunktion und ihre Polynominterpolante vierten Grades

Interpoliere die Funktion f(x) = \tan(x) bei gegebenen Punkten

x_0 = -1{,}5 f(x_0) = -14{,}101420
x_1 = -0{,}75 f(x_1) =  -0{,}931596
x_2 = 0 f(x_2) = 0
x_3 = 0{,}75 f(x_3) = 0{,}931596
x_4 = 1{,}5 f(x_4) = 14{,}101420

Lösung mit Lagrange[Bearbeiten]

Die Lagrange-Basisfunktionen sind

\begin{align}
\ell_0(x)&={x - x_1 \over x_0 - x_1}\cdot{x - x_2 \over x_0 - x_2}\cdot{x - x_3 \over x_0 - x_3}\cdot{x - x_4 \over x_0 - x_4}
             ={1\over 243} x (2x-3)(4x-3)(4x+3)\\
\ell_1(x)&= {x - x_0 \over x_1 - x_0}\cdot{x - x_2 \over x_1 - x_2}\cdot{x - x_3 \over x_1 - x_3}\cdot{x - x_4 \over x_1 - x_4}
             =-{8\over 243} x (2x-3)(2x+3)(4x-3)\\
\ell_2(x)&={x - x_0 \over x_2 - x_0}\cdot{x - x_1 \over x_2 - x_1}\cdot{x - x_3 \over x_2 - x_3}\cdot{x - x_4 \over x_2 - x_4}
             ={3\over 243} (2x+3)(4x+3)(4x-3)(2x-3)\\
\ell_3(x)&={x - x_0 \over x_3 - x_0}\cdot{x - x_1 \over x_3 - x_1}\cdot{x - x_2 \over x_3 - x_2}\cdot{x - x_4 \over x_3 - x_4}
             =-{8\over 243} x (2x-3)(2x+3)(4x+3)\\
\ell_4(x)&={x - x_0 \over x_4 - x_0}\cdot{x - x_1 \over x_4 - x_1}\cdot{x - x_2 \over x_4 - x_2}\cdot{x - x_3 \over x_4 - x_3}
             ={1\over 243} x (2x+3)(4x-3)(4x+3)
\end{align}

also ist das Interpolationspolynom

 \begin{align}P_\text{Lagrange}(x) =& \tfrac1{243}\big(f(x_0)x (2x-3)(4x-3)(4x+3) \\
& \qquad{} - 8f(x_1)x (2x-3)(2x+3)(4x-3) \\
& \qquad{} + 3f(x_2)(2x+3)(4x+3)(4x-3)(2x-3) \\
& \qquad{} - 8f(x_3)x (2x-3)(2x+3)(4x+3) \\
& \qquad{} + f(x_4)x (2x+3)(4x-3)(4x+3)\big)\\
=&  - 1{,}477474x + 4{,}834848x^3 
\end{align}

Lösung mit Newton[Bearbeiten]

Die dividierten Differenzen sind hier

\begin{array}{rrrrrr}
x_i    & f(x_i)     &                                                           &                                                  &                                               &\\
-1{,}50& -14{,}10140&                                                           &                                                  &                                               &\\
       &            &                                                           &                                                  &                                               &\\
-0{,}75& -0{,}931596&{-0{,}931596-(-14{,}1014) \over -0{,}75-(-1{,}5)}=17{,}5597&                                                  &                                               &\\
       &            &                                                           &                                                  &                                               &\\
0{,}00 & 0{,}00000  &{0-(-0{,}931596) \over 0 - (-0{,}75)}=1{,}24213            &{1{,}24213-17{,}5597 \over 0-(-1{,}5) }=-10{,}8784&                                               &\\
       &            &                                                           &                                                  &                                               &\\
0{,}75 & 0{,}931596 &{0{,}931596 - 0 \over 0{,}75-0}=1{,}24213                  &{1{,}24213-1{,}24213 \over 0{,}75-(-0{,}75)}=0{,}00000    &{0 - (-10{,}8784) \over 0{,}75-(-1{,}5)}=4{,}83484&\\
       &            &                                                           &                                                  &                                               &\\
1{,}50 & 14{,}10140 &{14{,}10140-0{,}931596 \over 1{,}5 - 0{,}75}=17{,}5597     &{17{,}5597-1{,}24213 \over 1{,}5-0}=10{,}8784     &{10{,}8784-0 \over 1{,}5-(-0{,}75)}=4{,}83484  &{4{,}83484-4{,}83484 \over 1{,}5-(-1{,}5)}=0\\
\end{array}

und das Interpolationspolynom ist

\begin{align}P_\text{Newton}(x)  =& -14{,}1014+17{,}5597(x+1{,}5)-10{,}8784(x+1{,}5)(x+0{,}75) \\
 & {} +4{,}83484(x+1{,}5)(x+0{,}75)x+0(x+1{,}5)(x+0{,}75)x(x-0{,}75)\\
 =&  -0{,}00005-1{,}4775x-0{,}00001x^2+4{,}83484x^3\end{align}

Verwendet man genauere Startwerte f(x_i), verschwinden der erste und der dritte Koeffizient.

Interpolationsgüte[Bearbeiten]

Fehlerabschätzung[Bearbeiten]

Gegeben sei eine Funktion f, deren n+1 Funktionswerte f_i an den Stellen x_i durch das Polynom P interpoliert werden. Mit I sei das kleinste Intervall bezeichnet, das die Stützstellen x_i und eine Stelle x enthält. Ferner sei f (n+1)-mal stetig differenzierbar auf I. Dann existiert ein \xi \in I, für das gilt:

f(x) - P(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x-x_i)

Insbesondere ist also bezüglich der Supremumsnorm auf [a,b]:

|f(x)-P(x)| \leq\frac{\|f^{(n+1)}\|_\infty}{(n+1)!} \prod_{i=0}^n |x-x_i|

Fehleroptimierung nach Tschebyschow[1][Bearbeiten]

Für größere n clustern die Tschebyschow-Punkte an den Intervallrändern.

Der Fehler hängt also von einer Ableitung von f ab und von dem Produkt w_n(x):=\prod_{i=0}^n (x-x_i), also den Stützstellen x_i. Manchmal ist man in der Position, dass man sich Stützstellen selbst wählen kann; etwa, wenn man ein physikalisches Experiment durchführt, oder aber auch bei einigen Verfahren zur numerischen Lösung von Differentialgleichungen. In diesem Fall ist die Frage interessant, für welche Stützstellen das Produkt w_n(x) in der Maximumsnorm minimal wird.

Tschebyschow hat diese Frage vollständig geklärt: Betrachte die Polynome T_{n+1}(x)=\cos((n+1) \arccos(x) ) mit den Nullstellen t_k=\cos\left(\frac{2k+1}{2n+2} \pi\right) k\in\{0,1,\dotsc,n\}. (Die „Tschebyschow-Polynome“ und „Tschebyschow-Punkte“) Die ersten Tschebyschow-Polynome sind:

\begin{align}
T_2(x)= 2x^2-1, &&& T_3(x)= 4x^3-3x, &&& T_4(x)=8x^4-8x^2+1
\end{align}

Man kann dann beweisen, dass jedes Polynom der Form w_n auf dem Intervall [-1,1] durch ein normiertes Tschebyschow-Polynom beschränkt bleibt. Diese Aussage kann dann mit der Transformation

\begin{align} 
\xi\in[-1,1] &\rightsquigarrow x=\frac{a+b}{2}+\frac{b-a}{2}\xi &\in [a,b] \\
x\in[a,b] &\rightsquigarrow \xi = \frac{2x-a-b}{b-a} &\in [-1,1]
\end{align}

auf den Fall eines allgemeinen Intervalls [a,b]\subset\mathbb{R} übertragen werden. Der Beweis liefert auch die Abschätzung

\begin{align}
\|w_n(x)\|_{[a,b],\infty} =\max_{x\in[a,b]} |w_n(x)| =2\left(\frac{b-a}{4}\right)^{n+1}.
\end{align}

Runges Phänomen[Bearbeiten]

Interpolation der Runge-Funktion (n=5)
Interpolation der Runge-Funktion (n=10)

Verbessert sich die Interpolationsgüte, wenn mehr Stützpunkte hinzugefügt werden? Im Allgemeinen nicht: Bei hohem Grad des Polynoms kann es vorkommen, dass die Polynomfunktion kaum noch der zu interpolierenden Funktion ähnelt, was auch als Runges Phänomen bekannt ist. Polynome streben im Grenzfall x\to \pm \infty gegen \pm\infty. Verhält sich die zu interpolierende Funktion anders, etwa periodisch oder asymptotisch konstant, treten starke Oszillationen in der Nähe der Intervallgrenzen auf. Für solche Funktionen sind Polynominterpolationen über das gesamte Intervall relativ ungeeignet.

Tschebyschow-Stützstellen, die an den Intervallgrenzen dichter liegen, können zwar den Gesamtfehler der Interpolation verkleinern, dennoch empfiehlt sich ein Wechsel des Interpolationsverfahrens, etwa zur Spline-Interpolation. Runge gab für dieses Phänomen ein Beispiel an, die nach ihm benannte Runge-Funktion:

f(x)=\frac{1}{1+x^2}\,,\quad x\in[-5;5]

Konvergenzverhalten[Bearbeiten]

Es gibt aber Bedingungen, unter denen sich die Interpolationsgüte mit steigender Anzahl von Stützpunkten verbessert: Wenn das Stützstellengitter immer „feiner“ wird und eine analytische Funktion interpoliert wird. Genauer: Sei f eine analytische Funktion auf dem Intervall I=[a,b] \subset \R. Für eine Intervallteilung

\Delta_m = \{a=x_0^{(m)} < x_1^{(m)} < \dotsb < x_{n_m}^{(m)}=b\}, \qquad m\in \N

sei ihre Norm definiert durch

\|\Delta_m\| = \max_i|x_{i+1}^{(m)} - x_i^{(m)}|.

Zu jeder Intervallteilung \Delta_m gibt es ein eindeutig bestimmtes Polynom P_{\Delta_m}, das f an den Stützstellen \Delta_m interpoliert. Gilt für eine Folge von Intervallteilungen \|\Delta_m\| \rightarrow 0, so folgt P_{\Delta_m} \rightarrow f gleichmäßig.

Allerdings lässt sich zu jeder Folge \{\Delta_m\}_{m \in \N} auch eine auf I stetige Funktion f finden, so dass \{P_{\Delta_m}\}_{m \in \N} nicht gleichmäßig gegen f konvergiert (Satz von Faber[2]).

Verallgemeinerung[Bearbeiten]

Bisher wurden die Stützstellen x_i des Interpolationspolynoms P als paarweise verschieden angenommen. Bei der Hermiteinterpolation ist das nicht der Fall. Mehrfach vorkommende Stützstellen werden dabei als Ableitungen der zu interpolierenden Funktion f interpretiert.

Literatur[Bearbeiten]

  • Hans R. Schwarz, Norbert Köckler: Numerische Mathematik, 5. Aufl., Teubner, Stuttgart 2004, ISBN 3-519-42960-8
  •  Stoer, Bulirsch: Numerische Mathematik 1. 10. Auflage. Springer Verlag, Berlin, Heidelberg, New York 2007, ISBN 978-3-540-45389-5, 2.1 Interpolation durch Polynome, S. 39-57 (Behandelt die Verfahren nach Lagrange, Neville-Aitken und Newton, Hermite-Interpolation und Fehlerabschätzung jeweils mit Beispielen und Beweisen.).
  •  Press, Teukolsky, Vetterling, Flannery: Numerical Recipes. The Art of Scientific Computing. 3. Auflage. Cambridge University Press, Cambridge 2007, ISBN 978-0-521-88407-5, 3.2 Polynomial Interpolation and Extrapolation, S. 118-120 (Neville-Aitken-Algorithmus mit C++-Implementation).

Weblinks[Bearbeiten]

 Wikibooks: Dividierte Differenzen & Horner-Schema – Implementierungen in der Algorithmensammlung

Einzelnachweise[Bearbeiten]

  1. Jochen Werner: 10.4. In: Numerische Mathematik, 1, Vieweg Studium, Nr.32, Vieweg Verlagsgesellschaft, 1992, ISBN 3528072326.
    • Auch hier (4.1.3.; PDF-Datei; 11,68 MB)
  2. Andrei Nikolajewitsch Kolmogorow, et al.: 4. In: Mathematics of the 19th Century, 1, Birkhäuser, 1998, ISBN 3764358459.