Polynominterpolation

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

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

Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n+1} gegebene Wertepaare Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x_i,\,f_i)} mit paarweise verschiedenen Stützstellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} wird ein Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} maximal Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -ten Grades gesucht, das alle Gleichungen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Pi_n} der Polynome mit Grad Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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\leq k\leq n\right\}$ , also für $P$ die Darstellung $P(x)=\sum _{k=0}^{n}a_{k}x^{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 einfachen Darstellung wird dieses Gleichungssystem in der Praxis nicht zur Berechnung des Interpolationspolynoms verwendet, da seine Lösung aufwendig ist und es zudem im Allgemeinen schlecht konditioniert ist.

Lösungsverfahren

Obiges Gleichungssystem ließe sich beispielsweise mit dem Gaußschen Eliminationsverfahren lösen. Der Aufwand dafür wäre mit ${\mathcal {O}}\left(n^{3}\right)$ (siehe Landau-Symbole) allerdings vergleichsweise groß. Bei Wahl einer anderen Basis als der Standardbasis zur Beschreibung des Polynoms $P$ kann der Aufwand verringert werden.

Lagrangesche Interpolationsformel

Beispielhafte lagrangesche Basisfunktionen für x₀ = 0, x₁ = 1, x₂ = 2, x₃ = 3 (n = 3)

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&{\text{falls }}i=k\\0&{\text{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,\dotsc ,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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} schnell interpolieren, wenn die Basisfunktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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. In der digitalen Signalverarbeitung wird die Lagrange-Interpolation unter dem Namen "Farrow Filter" für adaptives Resampling eingesetzt.

Baryzentrische Interpolationsformel

Die Lagrangesche Interpolationsformel kann umgeformt werden in die praktisch relevantere Baryzentrische Interpolationsformel

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(x) = \frac{\sum_{j=1}^n \frac{\lambda_j f_j}{x-x_j} } {\sum_{j=1}^n \frac{\lambda_j}{x-x_j} } \, }

für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x\neq x_1,\ldots,x_n} , wobei die Baryzentrischen Gewichte wie folgt definiert sind

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda_j := \prod_{\begin{smallmatrix}i=1\\i\neq j\end{smallmatrix}}^n \frac{1}{x_j - x_i} \, . }

Für vorgegebene Stützstellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(x_i\right)_i} können die Gewichte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(\lambda_i\right)_i} vorberechnet werden, sodass der Aufwand für die Auswertung von $P(x)$ nur noch bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n)} liegt. Beim Hinzufügen einer neuen Stützstelle müssen die Gewichte neubestimmt werden. Dies hat einen Aufwand von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n)} im Vergleich zum Neubestimmen der Lagrangepolynome von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}\left(n^2\right)} .

Newtonscher Algorithmus

In diesem Verfahren wird das Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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

Als Ansatz für das gesuchte Interpolationspolynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} wählt man die Newton-Basisfunktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N_0(x)=1} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle N_i(x) = \prod_{j=0}^{i-1}\left(x-x_j\right)=\left(x-x_0\right)\dotsm\left(x-x_{i-1}\right)} mit $i=1,\dotsc ,n$ , so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Vandermonde-Matrix bei Wahl der Standardbasis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left\{x^k \mid 0 \le k \le n\right\}} 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

Die Koeffizienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_i} gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_i = \left[x_0, \dotsc, x_i\right]f} .

Dabei sind für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i<j} die dividierten Differenzen $\left[x_{i},\dotsc ,x_{j}\right]f$ rekursiv definiert durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left[x_i\right]f = f_i \qquad}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left[x_i,\dotsc,x_j\right]f = \frac{\left[x_{i+1},\dotsc,x_j\right]f-\left[x_i,\dotsc,x_{j-1}\right]f}{x_j - x_i}} .

Die Notation mit angehängtem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} erklärt sich dadurch, dass oft eine unbekannte Funktion $f$ angenommen wird, die bei bekannten Funktionswerten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_i = f\left(x_i\right)} interpoliert werden soll.

Die rekursive Berechnung der dividierten Differenzen lässt sich wie folgt veranschaulichen. Dabei sind die gesuchten Koeffizienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(x_i, f_i\right)} um einen weiteren Punkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(x_{n+1}, f_{n+1}\right)} in obigem Schema nur eine weitere Zeile hinzuzufügen, um den zusätzlichen Koeffizienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_{n+1} = \left[x_0, \dotsc, x_{n+1}\right]f} zu berechnen. Die zuvor bestimmten Koeffizienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_0, \dotsc, c_n} müssen nicht neu berechnet werden.

Alternativ zur obigen rekursiven Definition wird zum Beispiel in einem der Artikel von Marsden^[1] die dividierte Differenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left[x_0,\dotsc,x_n\right]f} einer hinreichend oft differenzierbaren Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} als der eindeutige Koeffizient zur höchsten Potenz von $x$ eines Polynoms $n$ -ten Grads Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(x)} definiert, das Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} an den Stellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0,\dotsc,x_n} interpoliert. Tritt dabei ein Wert in der Sequenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0,\dotsc,x_n} mit der Vielfachheit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \nu\geq 1} auf, so sollen die Ableitungen des Polynoms die Ableitungen der Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} an dieser Stelle bis zur Ordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \nu-1} interpolieren. Es gilt somit

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left[x_0,\dotsc,x_k\right]f = \frac{ f^{(k)}(x^*) }{k!} \qquad \text{falls} \quad x^* := x_0 = \dotsb = x_k \, . }

Auswertung des Polynoms: Horner-Schema

Wenn die Koeffizienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_i} des Interpolationspolynoms Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} einmal bekannt sind, kann man es effizient mithilfe des Horner-Schemas auswerten. Dazu schreibt man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} in der Form (einfache Umformung der Newtonschen Interpolationsformel)

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(x) = \left(\dotso\left(c_n\left(x - x_{n-1}\right) + c_{n-1}\right)\left(x - x_{n-2}\right) + \dotsb + c_1\right)\left(x - x_0\right) + c_0} ,

so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(x)} rekursiv berechnet werden kann durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} b_n & = c_n \\ b_i & = b_{i+1}\left(x - x_i\right) + c_i, \qquad i = n - 1, \dotsc, 0 \\ P(x) & = b_0 \end{align}}

Dies erfordert einen Aufwand von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n)} .

Algorithmus von Neville-Aitken

Ähnlich wie im Newtonschen Algorithmus wird beim Algorithmus von Neville-Aitken die Lösung rekursiv berechnet. Dazu bezeichne Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p\left(f|x_i,\dotsc,x_j\right)} das eindeutig bestimmte Interpolationspolynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -ten Grades zu den Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k+1} Stützpunkten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(x_i, f_i\right), \dotsc, \left(x_j, f_j\right)} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k=j-i} ist. Es gilt dann die Rekursionsformel von Aitken:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align}p(f|x_i)(x) & = f_i, \\ p\left(f|x_i, \dotsc, x_j\right)(x) & = \frac{\left(x - x_i\right)p\left(f|x_{i+1}, \dotsc, x_j\right)(x) - \left(x - x_j\right)p\left(f|x_i, \dotsc, x_{j-1}\right)(x)}{x_j-x_i}.\end{align}}

Beweisen lässt sie sich durch Einsetzen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i,\ldots,x_j} , wodurch man verifiziert, dass die rechte Seite der Gleichung die Interpolationsbedingung erfüllt. Die Eindeutigkeit des Interpolationspolynoms liefert dann die Behauptung.

Nach der Rekursionsformel von Aitken ergibt sich der eindeutige Koeffizient von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p\left(f|x_i,\dotsc,x_j\right)} zur Potenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^{j-i}} als Differenz der Koeffizienten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p\left(f|x_{i+1},\dotsc,x_j\right)} und $p\left(f|x_{i},\dotsc ,x_{j-1}\right)$ zu $x^{j-i-1}$ dividiert durch $x_{j}-x_{i}$ . Dies zeigt, dass die Diagonalelemente Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [x_0,\ldots,x_j]f} im Schema der dividierten Differenzen genau die Koeffizienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_j} des Interpolationspolynoms Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} nach dem Ansatz von Newton liefern.

Mit dem Schema von Neville kann außerdem die Auswertung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p\left(f|x_0, \dotsc, x_n\right)(x) = P(x)} an einer Stelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} rekursiv erfolgen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{array}{crcrccrcrc} p(f|x_{0})\\ & \searrow\\ p(f|x_{1}) & \rightarrow & p(f|x_{0},x_{1})\\ & \searrow & & \searrow\\ p(f|x_{2}) & \rightarrow & p(f|x_{1},x_{2}) & \rightarrow & p(f|x_{0},x_{1},x_{2})\\ \vdots & & \vdots & & \vdots & \ddots\\ & \searrow & & \searrow & & & \searrow\\ p(f|x_{n-1}) & \rightarrow & p(f|x_{n-2},x_{n-1}) & \rightarrow & p(f|x_{n-3},x_{n-2},x_{n-1}) & \cdots & \rightarrow & p(f|x_{0},\dotsc,x_{n-1})\\ & \searrow & & \searrow & & & \searrow & & \searrow\\ p(f|x_{n}) & \rightarrow & p(f|x_{n-1},x_{n}) & \rightarrow & p(f|x_{n-2},x_{n-1},x_{n}) & \cdots & \rightarrow & p(f|x_{1},\dotsc,x_{n}) & \rightarrow & p(f|x_{0},\dotsc,x_{n}) \end{array}}

Vergleich der Lösungsverfahren

Möchte man alle Koeffizienten des Interpolationspolynoms Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} bestimmen, so bietet der Newtonsche Algorithmus hierfür den geringsten notwendigen Aufwand von ${\mathcal {O}}\left(n^{2}\right)$ . Das so bestimmte Polynom lässt sich dann mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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

Tangensfunktion (blau) und ihre Polynominterpolante dritten Grades (rot)

Interpoliere die Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x) = \tan(x)} bei gegebenen Punkten

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0 = -1{,}5}	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x_0) = -14{,}101420}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_1 = -0{,}75}	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x_1) = -0{,}931596}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_2 = 0}	$f(x_{2})=0$
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_3 = 0{,}75}	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x_3) = 0{,}931596}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_4 = 1{,}5}	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x_4) = 14{,}101420}

Lösung mit Lagrange

Die Lagrange-Basisfunktionen sind

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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

Die dividierten Differenzen sind hier

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{array}{rrrrrr} x_i & f\left(x_i\right) & & & &\\ -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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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\left(x_{i}\right)$ , verschwinden der erste und der dritte Koeffizient.

Interpolationsgüte

Fehlerabschätzung

Gegeben sei eine Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} , deren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n+1} Funktionswerte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_i} an den Stellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} durch das Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} interpoliert werden. Mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I} sei das kleinste Intervall bezeichnet, das die Stützstellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} und eine Stelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} enthält. Ferner sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n+1} )-mal stetig differenzierbar auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I} . Dann existiert ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Maximumsnorm auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [a,b]} und mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w_n(x) = \prod_{i=0}^n (x-x_i)} :

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |f(x)-P(x)| \leq\frac{\|f^{(n+1)}\|_\infty}{(n+1)!} \prod_{i=0}^n |x-x_i| \leq \frac{\|f^{(n+1)}\|_\infty}{(n+1)!} \|w_n\|_\infty}

Fehleroptimierung nach Tschebyschow

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

Der Fehler hängt also von einer Ableitung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 die Maximumsnorm Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|w_n\|_{\infty}} minimal wird.^[2]

Für einen Beweis betrachtet man normalerweise normierte Stützstellen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} w_n: [-1,1] \rightarrow \R, \ w_n(x)=\prod_{i=0}^n (x-x_i) \\ \text{mit} \qquad \forall \, i=0,\ldots,n : \quad x_i \in [-1,1] \, . \end{align} }

Nun kann man die Maximumsnorm der Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w_n} wie folgt abschätzen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|w_n\|_{[-1,1],\infty} =\max_{x\in[-1,1]} |w_n(x)| \geq 2^{-n} \, . }

Tschebyschow hat gezeigt, dass die Nullstellen der Tschebyschow-Polynome („Tschebyschow-Punkte“) optimale Stützstellen sind. Die Polynome Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T_{n+1}(x)=\cos((n+1) \arccos(x) )} haben die Nullstellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t_k=\cos\left(\frac{2k+1}{2n+2} \pi\right)} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k\in\{0,1,\ldots,n\}} . So gewählte Stützstellen liefern eine scharfe Grenze der oberen Abschätzung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|w_n\|_{[-1,1],\infty} = 2^{-n} \, . }

Diese Aussage kann dann mit der Transformation

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [a,b]\subset\mathbb{R}} übertragen werden. Der Beweis liefert auch die Abschätzung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} \|w_n\|_{[a,b],\infty} =\max_{x\in[a,b]} |w_n(x)| =2\left(\frac{b-a}{4}\right)^{n+1}. \end{align}}

Polynom-Interpolation 6 äquidistanter Stützstellen (rote Punkte), die auf der Rungefunktion liegen (blau)

Das gleiche mit 11 Stützstellen

Runges Phänomen

Verbessert sich die Interpolationsgüte, wenn mehr Stützpunkte hinzugefügt werden? Im Allgemeinen nicht: Bei äquidistanten Stützstellen und 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x)=\frac{1}{1+x^2}\,,\quad x\in[-5;5]}

Konvergenzverhalten

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} eine analytische Funktion auf dem Intervall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I=[a,b] \subset \R} . Für eine Intervallteilung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta_m = \{a=x_0^{(m)} < x_1^{(m)} < \dotsb < x_{n_m}^{(m)}=b\}, \qquad m\in \N}

sei ihre Norm definiert durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|\Delta_m\| = \max_i|x_{i+1}^{(m)} - x_i^{(m)}|.}

Zu jeder Intervallteilung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta_m} gibt es ein eindeutig bestimmtes Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P_{\Delta_m}} , das Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} an den Stützstellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta_m} interpoliert. Gilt für eine Folge von Intervallteilungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|\Delta_m\| \rightarrow 0} , so folgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P_{\Delta_m} \rightarrow f} gleichmäßig.

Allerdings lässt sich zu jeder Folge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{\Delta_m\}_{m \in \N}} auch eine auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I} stetige Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} finden, so dass $\{P_{\Delta _{m}}\}_{m\in \mathbb {N} }$ nicht gleichmäßig gegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} konvergiert (Satz von Faber^[3]).

Bestapproximation

Der Zusammenhang zwischen dem Interpolationpolynom und dem Polynom, welches die Funktion am besten bezüglich der Maximumsnorm Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \| \cdot \|_\max} annähert, ist wie folgt gegeben:

Seien dazu folgende Objekte gegeben

eine stetige, zu nähernde Funktion: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f \in C([a,b])}
Stützstellen: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0,\ldots,x_n \in [a,b]}
Lebesgue-Konstante: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Lambda_n}
Interpolationspolynom: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P \in P_n} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(x_i) = f(x_i)}
Bestapproximation: $Q\in P_{n}$ mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \| f-Q \|_\max = \min_{R \in P_n} \| f-R \|_\max } .

Dann gilt die Abschätzung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \| f-P \|_\max = (1+\Lambda_n) \| f-Q \|_\max \, . }

Verallgemeinerung

Bisher wurden die Stützstellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} des Interpolationspolynoms Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} als paarweise verschieden angenommen. Bei der Hermiteinterpolation ist das nicht der Fall. An mehrfach vorkommenden Stützstellen werden dabei nicht nur die Funktionswerte, sondern auch die Werte der Ableitungen des Interpolationspolynoms vorgegeben.

Lebesgue-Konstante

Sei der Operator, der einer Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} sein Interpolationspolynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(f)} zuordnet, definiert durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \phi_n \colon C([a,b]) \rightarrow P_n \, , \, f \mapsto P(f) = \sum_{i=0}^n f(x_i) l_i \, , }

wobei $l_{i}$ das $i$ -te Lagrange-Polynom ist.

Als Lebesgue-Konstante $\Lambda _{n}$ wird die Operatornorm von $\phi _{n}$ bezeichnet. Dafür wird eine Norm benötigt und oft wird hier auf die Maximumsnorm $\|\cdot \|_{\max }$ zugegriffen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Lambda_n := \| \phi_n \|_\max \, . }

Die Norm kann explizit evaluiert werden

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Lambda_n = \max_{x\in[a,b]} \sum_{i=0}^n |L_i(x)| \, . }

Literatur

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).
Carl Runge: Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten. In: Zeitschrift für Mathematik und Physik. Band 46. B. G. Teubner, Leipzig 1901, S. 224–243 (hdl:1908/2014 – Runge-Phänomen).
Martin Hermann: Numerische Mathematik, Band 2: Analytische Probleme. 4., überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag, Berlin und Boston 2020. ISBN 978-3-11-065765-4.

Weblinks

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

Seite zu Newton, Lagrange und Cubic Spline mit Java-Applet
Erläuterungen und Beispiel zur Lagrange-Interpolation

Einzelnachweise

↑ Martin J. Marsden: An Identity for Spline Functions with Applications to Variation-Diminishing Spline Approximation. In: Journal of Approximation Theory, 3, 1970, S. 7–49.
↑ Jochen Werner: 10.4. In: Numerische Mathematik, 1. Auflage, Vieweg Studium, Nr.32, Vieweg Verlagsgesellschaft, 1992, ISBN 3-528-07232-6. – 4.1.3. (PDF; 11,7 MB) sam.math.ethz.ch
↑ Andrei Nikolajewitsch Kolmogorow et al.: 4. In: Mathematics of the 19th Century, 1. Auflage, Birkhäuser, 1998, ISBN 3-7643-5845-9. – books.google.de

[1] Martin J. Marsden: An Identity for Spline Functions with Applications to Variation-Diminishing Spline Approximation. In: Journal of Approximation Theory, 3, 1970, S. 7–49.

[2] Jochen Werner: 10.4. In: Numerische Mathematik, 1. Auflage, Vieweg Studium, Nr.32, Vieweg Verlagsgesellschaft, 1992, ISBN 3-528-07232-6. – 4.1.3. (PDF; 11,7 MB) sam.math.ethz.ch

[3] Andrei Nikolajewitsch Kolmogorow et al.: 4. In: Mathematics of the 19th Century, 1. Auflage, Birkhäuser, 1998, ISBN 3-7643-5845-9. – books.google.de

[1]

[2]

[3]

Anonym

Suche

Polynominterpolation

Namensräume

Mehr

Seitenaktionen

Inhaltsverzeichnis

Anwendungen

Problemstellung