Technopedia Center
PMB University Brochure
Faculty of Engineering and Computer Science
S1 Informatics S1 Information Systems S1 Information Technology S1 Computer Engineering S1 Electrical Engineering S1 Civil Engineering

faculty of Economics and Business
S1 Management S1 Accountancy

Faculty of Letters and Educational Sciences
S1 English literature S1 English language education S1 Mathematics education S1 Sports Education
teknopedia

teknopedia

teknopedia

teknopedia

teknopedia
  • Registerasi
  • Brosur UTI
  • Kip Scholarship Information
  • Performance
  1. Weltenzyklopädie
  2. Polynominterpolation – Wikipedia
Polynominterpolation – Wikipedia
aus Wikipedia, der freien Enzyklopädie
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 | Quelltext 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 | Quelltext bearbeiten]

Für n + 1 {\displaystyle n+1} {\displaystyle n+1} gegebene Wertepaare ( x i , f i ) {\displaystyle (x_{i},\,f_{i})} {\displaystyle (x_{i},\,f_{i})} mit paarweise verschiedenen Stützstellen x i {\displaystyle x_{i}} {\displaystyle x_{i}} wird ein Polynom P {\displaystyle P} {\displaystyle P} maximal n {\displaystyle n} {\displaystyle n}-ten Grades gesucht, das alle Gleichungen

P ( x i ) = f i , i = 0 , … , n {\displaystyle P(x_{i})=f_{i},\quad i=0,\dotsc ,n} {\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 {\displaystyle P} {\displaystyle P} im Vektorraum Π n {\displaystyle \Pi _{n}} {\displaystyle \Pi _{n}} der Polynome mit Grad n {\displaystyle n} {\displaystyle n} oder kleiner zu suchen, kurz P ∈ Π n {\displaystyle P\in \Pi _{n}} {\displaystyle P\in \Pi _{n}}. Ist ϕ 0 , … , ϕ n {\displaystyle \phi _{0},\dotsc ,\phi _{n}} {\displaystyle \phi _{0},\dotsc ,\phi _{n}} eine Basis von Π n {\displaystyle \Pi _{n}} {\displaystyle \Pi _{n}}, so ergeben die Gleichungen P ( x i ) = f i {\displaystyle P(x_{i})=f_{i}} {\displaystyle P(x_{i})=f_{i}} ein lineares Gleichungssystem für die Koeffizienten der Basisdarstellung P = ∑ k = 0 n a k ϕ k {\displaystyle P=\sum _{k=0}^{n}a_{k}\phi _{k}} {\displaystyle 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 Π n {\displaystyle \Pi _{n}} {\displaystyle \Pi _{n}} gewählt wird, kann man ganz verschiedene Gleichungssysteme erhalten. Wählt man für Π n {\displaystyle \Pi _{n}} {\displaystyle \Pi _{n}} die Standardbasis { x k ∣ 0 ≤ k ≤ n } {\displaystyle \left\{x^{k}\mid 0\leq k\leq n\right\}} {\displaystyle \left\{x^{k}\mid 0\leq k\leq n\right\}}, also für P {\displaystyle P} {\displaystyle P} die Darstellung P ( x ) = ∑ k = 0 n a k x k {\displaystyle P(x)=\sum _{k=0}^{n}a_{k}x^{k}} {\displaystyle P(x)=\sum _{k=0}^{n}a_{k}x^{k}}, so erhält man ein Gleichungssystem mit der Vandermonde-Matrix:

( 1 x 0 ⋯ x 0 n ⋮ ⋮ ⋱ ⋮ 1 x n ⋯ x n n ) ( a 0 ⋮ a n ) = ( f 0 ⋮ f n ) {\displaystyle {\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}}} {\displaystyle {\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 {\displaystyle x_{i}} {\displaystyle x_{i}} paarweise verschieden sind, das Gleichungssystem lässt sich dann eindeutig lösen. Somit ist die Existenz und Eindeutigkeit des gesuchten Polynoms P ∈ Π n {\displaystyle P\in \Pi _{n}} {\displaystyle 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

[Bearbeiten | Quelltext bearbeiten]

Obiges Gleichungssystem ließe sich beispielsweise mit dem Gaußschen Eliminationsverfahren lösen. Der Aufwand dafür wäre mit O ( n 3 ) {\displaystyle {\mathcal {O}}\left(n^{3}\right)} {\displaystyle {\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 {\displaystyle P} {\displaystyle P} kann der Aufwand verringert werden.

Lagrangesche Interpolationsformel

[Bearbeiten | Quelltext bearbeiten]
Beispielhafte lagrangesche Basisfunktionen für x0 = 0, x1 = 1, x2 = 2, x3 = 3 (n = 3)

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

ℓ i ( x ) = ∏ j = 0 j ≠ i n x − x j x i − x j = x − x 0 x i − x 0 ⋯ x − x i − 1 x i − x i − 1 ⋅ x − x i + 1 x i − x i + 1 ⋯ x − x n x i − x n , {\displaystyle \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}}}\,,} {\displaystyle \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

ℓ i ( x k ) = ∏ j = 0 j ≠ i n x k − x j x i − x j = δ i k = { 1 falls  i = k 0 falls  i ≠ k {\displaystyle \ell _{i}(x_{k})=\prod _{\begin{smallmatrix}j=0\\j\neq i\end{smallmatrix}}^{n}{\frac {x_{k}-x_{j}}{x_{i}-x_{j}}}=\delta _{ik}=\left\{{\begin{matrix}1&{\text{falls }}i=k\\0&{\text{falls }}i\neq k\end{matrix}}\right.} {\displaystyle \ell _{i}(x_{k})=\prod _{\begin{smallmatrix}j=0\\j\neq i\end{smallmatrix}}^{n}{\frac {x_{k}-x_{j}}{x_{i}-x_{j}}}=\delta _{ik}=\left\{{\begin{matrix}1&{\text{falls }}i=k\\0&{\text{falls }}i\neq k\end{matrix}}\right.}

gilt, wobei δ i k {\displaystyle \delta _{ik}} {\displaystyle \delta _{ik}} das Kronecker-Delta darstellt. Damit entspricht die Matrix ( ℓ i ( x j ) ) i , j = 0 , 1 , … , n {\displaystyle \left(\ell _{i}\left(x_{j}\right)\right)_{i,j=0,1,\dotsc ,n}} {\displaystyle \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 ) = ∑ i = 0 n f i ℓ i ( x ) {\displaystyle P(x)=\sum _{i=0}^{n}f_{i}\ell _{i}\left(x\right)} {\displaystyle P(x)=\sum _{i=0}^{n}f_{i}\ell _{i}\left(x\right)}

mit den Stützwerten f i {\displaystyle f_{i}} {\displaystyle 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 ℓ i {\displaystyle \ell _{i}} {\displaystyle \ell _{i}} von den Stützwerten f i {\displaystyle f_{i}} {\displaystyle f_{i}} unabhängig sind. Dadurch lassen sich verschiedene Sätze von Stützwerten f i {\displaystyle f_{i}} {\displaystyle f_{i}} mit gleichen Stützstellen x i {\displaystyle x_{i}} {\displaystyle x_{i}} schnell interpolieren, wenn die Basisfunktionen ℓ i {\displaystyle \ell _{i}} {\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

[Bearbeiten | Quelltext bearbeiten]

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

P ( x ) = ∑ j = 1 n λ j f j x − x j ∑ j = 1 n λ j x − x j {\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}}}}}\,} {\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 x ≠ x 1 , … , x n {\displaystyle x\neq x_{1},\ldots ,x_{n}} {\displaystyle x\neq x_{1},\ldots ,x_{n}}, wobei die Baryzentrischen Gewichte wie folgt definiert sind

λ j := ∏ i = 1 i ≠ j n 1 x j − x i . {\displaystyle \lambda _{j}:=\prod _{\begin{smallmatrix}i=1\\i\neq j\end{smallmatrix}}^{n}{\frac {1}{x_{j}-x_{i}}}\,.} {\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 ( x i ) i {\displaystyle \left(x_{i}\right)_{i}} {\displaystyle \left(x_{i}\right)_{i}} können die Gewichte ( λ i ) i {\displaystyle \left(\lambda _{i}\right)_{i}} {\displaystyle \left(\lambda _{i}\right)_{i}} vorberechnet werden, sodass der Aufwand für die Auswertung von P ( x ) {\displaystyle P(x)} {\displaystyle P(x)} nur noch bei O ( n ) {\displaystyle {\mathcal {O}}(n)} {\displaystyle {\mathcal {O}}(n)} liegt. Beim Hinzufügen einer neuen Stützstelle müssen die Gewichte neu bestimmt werden. Dies hat einen Aufwand von O ( n ) {\displaystyle {\mathcal {O}}(n)} {\displaystyle {\mathcal {O}}(n)} im Vergleich zum Neubestimmen der Lagrangepolynome von O ( n 2 ) {\displaystyle {\mathcal {O}}\left(n^{2}\right)} {\displaystyle {\mathcal {O}}\left(n^{2}\right)}.

Newtonscher Algorithmus

[Bearbeiten | Quelltext bearbeiten]

In diesem Verfahren wird das Polynom P {\displaystyle P} {\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

[Bearbeiten | Quelltext bearbeiten]

Als Ansatz für das gesuchte Interpolationspolynom P {\displaystyle P} {\displaystyle P} wählt man die Newton-Basisfunktionen N 0 ( x ) = 1 {\displaystyle N_{0}(x)=1} {\displaystyle N_{0}(x)=1} und N i ( x ) = ∏ j = 0 i − 1 ( x − x j ) = ( x − x 0 ) ⋯ ( x − x i − 1 ) {\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)} {\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 , … , n {\displaystyle i=1,\dotsc ,n} {\displaystyle i=1,\dotsc ,n}, so dass P {\displaystyle P} {\displaystyle P} dargestellt wird mit der Newtonschen Interpolationsformel

P ( x ) = ∑ i = 0 n c i ⋅ N i ( x ) = c 0 + c 1 ( x − x 0 ) + c 2 ( x − x 0 ) ( x − x 1 ) + ⋯ + c n ( x − x 0 ) ⋯ ( x − x n − 1 ) {\displaystyle 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)} {\displaystyle 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 {\displaystyle P(x_{i})=f_{i}} {\displaystyle P(x_{i})=f_{i}} hat dann die Form

( 1 0 1 ( x 1 − x 0 ) 1 ( x 2 − x 0 ) ( x 2 − x 0 ) ( x 2 − x 1 ) ⋮ ⋮ ⋱ 1 ( x n − x 0 ) ⋯ ∏ i = 0 n − 1 ( x n − x i ) ) ⋅ ( c 0 ⋮ c n ) = ( f 0 ⋮ f n ) {\displaystyle {\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}}} {\displaystyle {\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 { x k ∣ 0 ≤ k ≤ n } {\displaystyle \left\{x^{k}\mid 0\leq k\leq n\right\}} {\displaystyle \left\{x^{k}\mid 0\leq k\leq 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

[Bearbeiten | Quelltext bearbeiten]

Die Koeffizienten c i {\displaystyle c_{i}} {\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 c i {\displaystyle c_{i}} {\displaystyle c_{i}} gilt

c i = [ x 0 , … , x i ] f {\displaystyle c_{i}=\left[x_{0},\dotsc ,x_{i}\right]f} {\displaystyle c_{i}=\left[x_{0},\dotsc ,x_{i}\right]f}.

Dabei sind für i < j {\displaystyle i<j} {\displaystyle i<j} die dividierten Differenzen [ x i , … , x j ] f {\displaystyle \left[x_{i},\dotsc ,x_{j}\right]f} {\displaystyle \left[x_{i},\dotsc ,x_{j}\right]f} rekursiv definiert durch

[ x i ] f = f i {\displaystyle \left[x_{i}\right]f=f_{i}\qquad } {\displaystyle \left[x_{i}\right]f=f_{i}\qquad }
[ x i , … , x j ] f = [ x i + 1 , … , x j ] f − [ x i , … , x j − 1 ] f x j − x i {\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}}}} {\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 f {\displaystyle f} {\displaystyle f} erklärt sich dadurch, dass oft eine unbekannte Funktion f {\displaystyle f} {\displaystyle f} angenommen wird, die bei bekannten Funktionswerten f i = f ( x i ) {\displaystyle f_{i}=f\left(x_{i}\right)} {\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 c i {\displaystyle c_{i}} {\displaystyle c_{i}} genau die oberste Schrägzeile:

[ x 0 ] f ↘ [ x 1 ] f → [ x 0 , x 1 ] f ↘ ↘ [ x 2 ] f → [ x 1 , x 2 ] f → [ x 0 , x 1 , x 2 ] f ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ↘ ↘ ↘ [ x n − 1 ] f → [ x n − 2 , x n − 1 ] f → [ x n − 3 , x n − 2 , x n − 1 ] f ⋯ → [ x 0 , … , x n − 1 ] f ↘ ↘ ↘ ↘ [ x n ] f → [ x n − 1 , x n ] f → [ x n − 2 , x n − 1 , x n ] f ⋯ → [ x 1 , … , x n ] f → [ x 0 , … , x n ] f {\displaystyle {\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}}} {\displaystyle {\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 {\displaystyle n+1} {\displaystyle n+1} Wertepaare ( x i , f i ) {\displaystyle \left(x_{i},f_{i}\right)} {\displaystyle \left(x_{i},f_{i}\right)} um einen weiteren Punkt ( x n + 1 , f n + 1 ) {\displaystyle \left(x_{n+1},f_{n+1}\right)} {\displaystyle \left(x_{n+1},f_{n+1}\right)} in obigem Schema nur eine weitere Zeile hinzuzufügen, um den zusätzlichen Koeffizienten c n + 1 = [ x 0 , … , x n + 1 ] f {\displaystyle c_{n+1}=\left[x_{0},\dotsc ,x_{n+1}\right]f} {\displaystyle c_{n+1}=\left[x_{0},\dotsc ,x_{n+1}\right]f} zu berechnen. Die zuvor bestimmten Koeffizienten c 0 , … , c n {\displaystyle c_{0},\dotsc ,c_{n}} {\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 [ x 0 , … , x n ] f {\displaystyle \left[x_{0},\dotsc ,x_{n}\right]f} {\displaystyle \left[x_{0},\dotsc ,x_{n}\right]f} einer hinreichend oft differenzierbaren Funktion f {\displaystyle f} {\displaystyle f} als der eindeutige Koeffizient zur höchsten Potenz von x {\displaystyle x} {\displaystyle x} eines Polynoms n {\displaystyle n} {\displaystyle n}-ten Grads p ( x ) {\displaystyle p(x)} {\displaystyle p(x)} definiert, das f {\displaystyle f} {\displaystyle f} an den Stellen x 0 , … , x n {\displaystyle x_{0},\dotsc ,x_{n}} {\displaystyle x_{0},\dotsc ,x_{n}} interpoliert. Tritt dabei ein Wert in der Sequenz x 0 , … , x n {\displaystyle x_{0},\dotsc ,x_{n}} {\displaystyle x_{0},\dotsc ,x_{n}} mit der Vielfachheit ν ≥ 1 {\displaystyle \nu \geq 1} {\displaystyle \nu \geq 1} auf, so sollen die Ableitungen des Polynoms die Ableitungen der Funktion f {\displaystyle f} {\displaystyle f} an dieser Stelle bis zur Ordnung ν − 1 {\displaystyle \nu -1} {\displaystyle \nu -1} interpolieren. Es gilt somit

[ x 0 , … , x k ] f = f ( k ) ( x ∗ ) k ! falls x ∗ := x 0 = ⋯ = x k . {\displaystyle \left[x_{0},\dotsc ,x_{k}\right]f={\frac {f^{(k)}(x^{*})}{k!}}\qquad {\text{falls}}\quad x^{*}:=x_{0}=\dotsb =x_{k}\,.} {\displaystyle \left[x_{0},\dotsc ,x_{k}\right]f={\frac {f^{(k)}(x^{*})}{k!}}\qquad {\text{falls}}\quad x^{*}:=x_{0}=\dotsb =x_{k}\,.}

Eine weitere Möglichkeit, um die dividierten Differenzen unabhängig von der Vielfachheit der Stützstellen auszudrücken, ist die Hermite-Genocchi-Formel, welche auf einer Integraldarstellung basiert.

Auswertung des Polynoms: Horner-Schema

[Bearbeiten | Quelltext bearbeiten]

Wenn die Koeffizienten c i {\displaystyle c_{i}} {\displaystyle c_{i}} des Interpolationspolynoms P {\displaystyle P} {\displaystyle P} einmal bekannt sind, kann man es effizient mithilfe des Horner-Schemas auswerten. Dazu schreibt man P {\displaystyle P} {\displaystyle P} in der Form (einfache Umformung der Newtonschen Interpolationsformel)

P ( x ) = ( … ( c n ( x − x n − 1 ) + c n − 1 ) ( x − x n − 2 ) + ⋯ + c 1 ) ( x − x 0 ) + c 0 {\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}} {\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 P ( x ) {\displaystyle P(x)} {\displaystyle P(x)} rekursiv berechnet werden kann durch

b n = c n b i = b i + 1 ( x − x i ) + c i , i = n − 1 , … , 0 P ( x ) = b 0 {\displaystyle {\begin{aligned}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{aligned}}} {\displaystyle {\begin{aligned}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{aligned}}}

Dies erfordert einen Aufwand von O ( n ) {\displaystyle {\mathcal {O}}(n)} {\displaystyle {\mathcal {O}}(n)}.

Algorithmus von Neville-Aitken

[Bearbeiten | Quelltext bearbeiten]

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

p ( f | x i ) ( x ) = f i , p ( f | x i , … , x j ) ( x ) = ( x − x i ) p ( f | x i + 1 , … , x j ) ( x ) − ( x − x j ) p ( f | x i , … , x j − 1 ) ( x ) x j − x i . {\displaystyle {\begin{aligned}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{aligned}}} {\displaystyle {\begin{aligned}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{aligned}}}

Beweisen lässt sie sich durch Einsetzen von x i , … , x j {\displaystyle x_{i},\ldots ,x_{j}} {\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 p ( f | x i , … , x j ) {\displaystyle p\left(f|x_{i},\dotsc ,x_{j}\right)} {\displaystyle p\left(f|x_{i},\dotsc ,x_{j}\right)} zur Potenz x j − i {\displaystyle x^{j-i}} {\displaystyle x^{j-i}} als Differenz der Koeffizienten von p ( f | x i + 1 , … , x j ) {\displaystyle p\left(f|x_{i+1},\dotsc ,x_{j}\right)} {\displaystyle p\left(f|x_{i+1},\dotsc ,x_{j}\right)} und p ( f | x i , … , x j − 1 ) {\displaystyle p\left(f|x_{i},\dotsc ,x_{j-1}\right)} {\displaystyle p\left(f|x_{i},\dotsc ,x_{j-1}\right)} zu x j − i − 1 {\displaystyle x^{j-i-1}} {\displaystyle x^{j-i-1}} dividiert durch x j − x i {\displaystyle x_{j}-x_{i}} {\displaystyle x_{j}-x_{i}}. Dies zeigt, dass die Diagonalelemente [ x 0 , … , x j ] f {\displaystyle [x_{0},\ldots ,x_{j}]f} {\displaystyle [x_{0},\ldots ,x_{j}]f} im Schema der dividierten Differenzen genau die Koeffizienten c j {\displaystyle c_{j}} {\displaystyle c_{j}} des Interpolationspolynoms P {\displaystyle P} {\displaystyle P} nach dem Ansatz von Newton liefern.

Mit dem Schema von Neville kann außerdem die Auswertung von p ( f | x 0 , … , x n ) ( x ) = P ( x ) {\displaystyle p\left(f|x_{0},\dotsc ,x_{n}\right)(x)=P(x)} {\displaystyle p\left(f|x_{0},\dotsc ,x_{n}\right)(x)=P(x)} an einer Stelle x {\displaystyle x} {\displaystyle x} rekursiv erfolgen:

p ( f | x 0 ) ↘ p ( f | x 1 ) → p ( f | x 0 , x 1 ) ↘ ↘ p ( f | x 2 ) → p ( f | x 1 , x 2 ) → p ( f | x 0 , x 1 , x 2 ) ⋮ ⋮ ⋮ ⋱ ↘ ↘ ↘ p ( f | x n − 1 ) → p ( f | x n − 2 , x n − 1 ) → p ( f | x n − 3 , x n − 2 , x n − 1 ) ⋯ → p ( f | x 0 , … , x n − 1 ) ↘ ↘ ↘ ↘ p ( f | x n ) → p ( f | x n − 1 , x n ) → p ( f | x n − 2 , x n − 1 , x n ) ⋯ → p ( f | x 1 , … , x n ) → p ( f | x 0 , … , x n ) {\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}}} {\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

[Bearbeiten | Quelltext bearbeiten]

Möchte man alle Koeffizienten des Interpolationspolynoms P {\displaystyle P} {\displaystyle P} bestimmen, so bietet der Newtonsche Algorithmus hierfür den geringsten notwendigen Aufwand von O ( n 2 ) {\displaystyle {\mathcal {O}}\left(n^{2}\right)} {\displaystyle {\mathcal {O}}\left(n^{2}\right)}. Das so bestimmte Polynom lässt sich dann mit O ( n ) {\displaystyle {\mathcal {O}}(n)} {\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

[Bearbeiten | Quelltext bearbeiten]
Tangensfunktion (blau) und ihre Polynominterpolante dritten Grades (rot)

Interpoliere die Funktion f ( x ) = tan ⁡ ( x ) {\displaystyle f(x)=\tan(x)} {\displaystyle f(x)=\tan(x)} bei gegebenen Punkten

x 0 = − 1 , 5 {\displaystyle x_{0}=-1{,}5} {\displaystyle x_{0}=-1{,}5} f ( x 0 ) = − 14,101 420 {\displaystyle f(x_{0})=-14{,}101420} {\displaystyle f(x_{0})=-14{,}101420}
x 1 = − 0 , 75 {\displaystyle x_{1}=-0{,}75} {\displaystyle x_{1}=-0{,}75} f ( x 1 ) = − 0,931 596 {\displaystyle f(x_{1})=-0{,}931596} {\displaystyle f(x_{1})=-0{,}931596}
x 2 = 0 {\displaystyle x_{2}=0} {\displaystyle x_{2}=0} f ( x 2 ) = 0 {\displaystyle f(x_{2})=0} {\displaystyle f(x_{2})=0}
x 3 = 0 , 75 {\displaystyle x_{3}=0{,}75} {\displaystyle x_{3}=0{,}75} f ( x 3 ) = 0,931 596 {\displaystyle f(x_{3})=0{,}931596} {\displaystyle f(x_{3})=0{,}931596}
x 4 = 1 , 5 {\displaystyle x_{4}=1{,}5} {\displaystyle x_{4}=1{,}5} f ( x 4 ) = 14,101 420 {\displaystyle f(x_{4})=14{,}101420} {\displaystyle f(x_{4})=14{,}101420}

Lösung mit Lagrange

[Bearbeiten | Quelltext bearbeiten]

Die Lagrange-Basisfunktionen sind

ℓ 0 ( x ) = x − x 1 x 0 − x 1 ⋅ x − x 2 x 0 − x 2 ⋅ x − x 3 x 0 − x 3 ⋅ x − x 4 x 0 − x 4 = 1 243 x ( 2 x − 3 ) ( 4 x − 3 ) ( 4 x + 3 ) ℓ 1 ( x ) = x − x 0 x 1 − x 0 ⋅ x − x 2 x 1 − x 2 ⋅ x − x 3 x 1 − x 3 ⋅ x − x 4 x 1 − x 4 = − 8 243 x ( 2 x − 3 ) ( 2 x + 3 ) ( 4 x − 3 ) ℓ 2 ( x ) = x − x 0 x 2 − x 0 ⋅ x − x 1 x 2 − x 1 ⋅ x − x 3 x 2 − x 3 ⋅ x − x 4 x 2 − x 4 = 3 243 ( 2 x + 3 ) ( 4 x + 3 ) ( 4 x − 3 ) ( 2 x − 3 ) ℓ 3 ( x ) = x − x 0 x 3 − x 0 ⋅ x − x 1 x 3 − x 1 ⋅ x − x 2 x 3 − x 2 ⋅ x − x 4 x 3 − x 4 = − 8 243 x ( 2 x − 3 ) ( 2 x + 3 ) ( 4 x + 3 ) ℓ 4 ( x ) = x − x 0 x 4 − x 0 ⋅ x − x 1 x 4 − x 1 ⋅ x − x 2 x 4 − x 2 ⋅ x − x 3 x 4 − x 3 = 1 243 x ( 2 x + 3 ) ( 4 x − 3 ) ( 4 x + 3 ) {\displaystyle {\begin{aligned}\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{aligned}}} {\displaystyle {\begin{aligned}\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{aligned}}}

also ist das Interpolationspolynom

P Lagrange ( x ) = 1 243 ( f ( x 0 ) x ( 2 x − 3 ) ( 4 x − 3 ) ( 4 x + 3 ) − 8 f ( x 1 ) x ( 2 x − 3 ) ( 2 x + 3 ) ( 4 x − 3 ) + 3 f ( x 2 ) ( 2 x + 3 ) ( 4 x + 3 ) ( 4 x − 3 ) ( 2 x − 3 ) − 8 f ( x 3 ) x ( 2 x − 3 ) ( 2 x + 3 ) ( 4 x + 3 ) + f ( x 4 ) x ( 2 x + 3 ) ( 4 x − 3 ) ( 4 x + 3 ) ) = − 1,477 474 x + 4,834 848 x 3 {\displaystyle {\begin{aligned}P_{\text{Lagrange}}(x)=&{\tfrac {1}{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{aligned}}} {\displaystyle {\begin{aligned}P_{\text{Lagrange}}(x)=&{\tfrac {1}{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{aligned}}}

Lösung mit Newton

[Bearbeiten | Quelltext bearbeiten]

Die dividierten Differenzen sind hier

x i f ( x i ) − 1 , 50 − 14,101 40 − 0 , 75 − 0,931 596 − 0,931 596 − ( − 14,101 4 ) − 0 , 75 − ( − 1 , 5 ) = 17,559 7 0 , 00 0,000 00 0 − ( − 0,931 596 ) 0 − ( − 0 , 75 ) = 1,242 13 1,242 13 − 17,559 7 0 − ( − 1 , 5 ) = − 10,878 4 0 , 75 0,931 596 0,931 596 − 0 0 , 75 − 0 = 1,242 13 1,242 13 − 1,242 13 0 , 75 − ( − 0 , 75 ) = 0,000 00 0 − ( − 10,878 4 ) 0 , 75 − ( − 1 , 5 ) = 4,834 84 1 , 50 14,101 40 14,101 40 − 0,931 596 1 , 5 − 0 , 75 = 17,559 7 17,559 7 − 1,242 13 1 , 5 − 0 = 10,878 4 10,878 4 − 0 1 , 5 − ( − 0 , 75 ) = 4,834 84 4,834 84 − 4,834 84 1 , 5 − ( − 1 , 5 ) = 0 {\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}}} {\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

P Newton ( x ) = − 14,101 4 + 17,559 7 ( x + 1 , 5 ) − 10,878 4 ( x + 1 , 5 ) ( x + 0 , 75 ) + 4,834 84 ( x + 1 , 5 ) ( x + 0 , 75 ) x + 0 ( x + 1 , 5 ) ( x + 0 , 75 ) x ( x − 0 , 75 ) = − 0,000 05 − 1,477 5 x − 0,000 01 x 2 + 4,834 84 x 3 {\displaystyle {\begin{aligned}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{aligned}}} {\displaystyle {\begin{aligned}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{aligned}}}

Verwendet man genauere Startwerte f ( x i ) {\displaystyle f\left(x_{i}\right)} {\displaystyle f\left(x_{i}\right)}, verschwinden der erste und der dritte Koeffizient.

Interpolationsgüte

[Bearbeiten | Quelltext bearbeiten]

Fehlerabschätzung

[Bearbeiten | Quelltext bearbeiten]

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

f ( x ) − P ( x ) = f ( n + 1 ) ( ξ ) ( n + 1 ) ! ∏ i = 0 n ( x − x i ) {\displaystyle f(x)-P(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i})} {\displaystyle 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 [ a , b ] {\displaystyle [a,b]} {\displaystyle [a,b]} und mit w n ( x ) = ∏ i = 0 n ( x − x i ) {\displaystyle w_{n}(x)=\prod _{i=0}^{n}(x-x_{i})} {\displaystyle w_{n}(x)=\prod _{i=0}^{n}(x-x_{i})}:

| f ( x ) − P ( x ) | ≤ ‖ f ( n + 1 ) ‖ ∞ ( n + 1 ) ! ∏ i = 0 n | x − x i | ≤ ‖ f ( n + 1 ) ‖ ∞ ( n + 1 ) ! ‖ w n ‖ ∞ {\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 }} {\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 }}

Es gibt auch noch eine andere Fehlerformel, welche auf den oben eingeführten dividierten Differenzen beruht[2]:

f ( x ) − P ( x ) = f [ x 0 , … , x n , x ] ∏ i = 0 n ( x − x i ) {\displaystyle f(x)-P(x)=f[x_{0},\dots ,x_{n},x]\prod _{i=0}^{n}(x-x_{i})} {\displaystyle f(x)-P(x)=f[x_{0},\dots ,x_{n},x]\prod _{i=0}^{n}(x-x_{i})}

Fehleroptimierung nach Tschebyschow

[Bearbeiten | Quelltext bearbeiten]
Für größere n clustern die Tschebyschow-Punkte an den Intervallrändern.

Der Fehler hängt also von einer Ableitung von f {\displaystyle f} {\displaystyle f} ab und von dem Produkt w n ( x ) := ∏ i = 0 n ( x − x i ) {\displaystyle w_{n}(x):=\prod _{i=0}^{n}(x-x_{i})} {\displaystyle w_{n}(x):=\prod _{i=0}^{n}(x-x_{i})}, also den Stützstellen x i {\displaystyle x_{i}} {\displaystyle 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 ‖ w n ‖ ∞ {\displaystyle \|w_{n}\|_{\infty }} {\displaystyle \|w_{n}\|_{\infty }} minimal wird.[3]

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

w n : [ − 1 , 1 ] → R ,   w n ( x ) = ∏ i = 0 n ( x − x i ) mit ∀ i = 0 , … , n : x i ∈ [ − 1 , 1 ] . {\displaystyle {\begin{aligned}w_{n}:[-1,1]\rightarrow \mathbb {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{aligned}}} {\displaystyle {\begin{aligned}w_{n}:[-1,1]\rightarrow \mathbb {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{aligned}}}

Nun kann man die Maximumsnorm der Funktion w n {\displaystyle w_{n}} {\displaystyle w_{n}} wie folgt abschätzen

‖ w n ‖ [ − 1 , 1 ] , ∞ = max x ∈ [ − 1 , 1 ] | w n ( x ) | ≥ 2 − n . {\displaystyle \|w_{n}\|_{[-1,1],\infty }=\max _{x\in [-1,1]}|w_{n}(x)|\geq 2^{-n}\,.} {\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 T n + 1 ( x ) = cos ⁡ ( ( n + 1 ) arccos ⁡ ( x ) ) {\displaystyle T_{n+1}(x)=\cos((n+1)\arccos(x))} {\displaystyle T_{n+1}(x)=\cos((n+1)\arccos(x))} haben die Nullstellen t k = cos ⁡ ( 2 k + 1 2 n + 2 π ) {\displaystyle t_{k}=\cos \left({\frac {2k+1}{2n+2}}\pi \right)} {\displaystyle t_{k}=\cos \left({\frac {2k+1}{2n+2}}\pi \right)} für k ∈ { 0 , 1 , … , n } {\displaystyle k\in \{0,1,\ldots ,n\}} {\displaystyle k\in \{0,1,\ldots ,n\}}. So gewählte Stützstellen liefern eine scharfe Grenze der oberen Abschätzung

‖ w n ‖ [ − 1 , 1 ] , ∞ = 2 − n . {\displaystyle \|w_{n}\|_{[-1,1],\infty }=2^{-n}\,.} {\displaystyle \|w_{n}\|_{[-1,1],\infty }=2^{-n}\,.}

Diese Aussage kann dann mit der Transformation

ξ ∈ [ − 1 , 1 ] ⇝ x = a + b 2 + b − a 2 ξ ∈ [ a , b ] x ∈ [ a , b ] ⇝ ξ = 2 x − a − b b − a ∈ [ − 1 , 1 ] {\displaystyle {\begin{aligned}\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{aligned}}} {\displaystyle {\begin{aligned}\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{aligned}}}

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

‖ w n ‖ [ a , b ] , ∞ = max x ∈ [ a , b ] | w n ( x ) | = 2 ( b − a 4 ) n + 1 . {\displaystyle {\begin{aligned}\|w_{n}\|_{[a,b],\infty }=\max _{x\in [a,b]}|w_{n}(x)|=2\left({\frac {b-a}{4}}\right)^{n+1}.\end{aligned}}} {\displaystyle {\begin{aligned}\|w_{n}\|_{[a,b],\infty }=\max _{x\in [a,b]}|w_{n}(x)|=2\left({\frac {b-a}{4}}\right)^{n+1}.\end{aligned}}}
Polynom-Interpolation 6 äquidistanter Stützstellen (rote Punkte), die auf der Rungefunktion liegen (blau)
Das gleiche mit 11 Stützstellen

Runges Phänomen

[Bearbeiten | Quelltext bearbeiten]

Verbessert sich die Interpolationsgüte, wenn mehr Stützpunkte hinzugefügt werden? Im Allgemeinen gilt dies 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 x → ± ∞ {\displaystyle x\to \pm \infty } {\displaystyle x\to \pm \infty } gegen ± ∞ {\displaystyle \pm \infty } {\displaystyle \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 ) = 1 1 + x 2 , x ∈ [ − 5 ; 5 ] {\displaystyle f(x)={\frac {1}{1+x^{2}}}\,,\quad x\in [-5;5]} {\displaystyle f(x)={\frac {1}{1+x^{2}}}\,,\quad x\in [-5;5]}

Konvergenzverhalten

[Bearbeiten | Quelltext 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 {\displaystyle f} {\displaystyle f} eine analytische Funktion auf dem Intervall I = [ a , b ] ⊂ R {\displaystyle I=[a,b]\subset \mathbb {R} } {\displaystyle I=[a,b]\subset \mathbb {R} }. Für eine Intervallteilung

Δ m = { a = x 0 ( m ) < x 1 ( m ) < ⋯ < x n m ( m ) = b } , m ∈ N {\displaystyle \Delta _{m}=\{a=x_{0}^{(m)}<x_{1}^{(m)}<\dotsb <x_{n_{m}}^{(m)}=b\},\qquad m\in \mathbb {N} } {\displaystyle \Delta _{m}=\{a=x_{0}^{(m)}<x_{1}^{(m)}<\dotsb <x_{n_{m}}^{(m)}=b\},\qquad m\in \mathbb {N} }

sei ihre Norm definiert durch

‖ Δ m ‖ = max i | x i + 1 ( m ) − x i ( m ) | . {\displaystyle \|\Delta _{m}\|=\max _{i}|x_{i+1}^{(m)}-x_{i}^{(m)}|.} {\displaystyle \|\Delta _{m}\|=\max _{i}|x_{i+1}^{(m)}-x_{i}^{(m)}|.}

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

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

Bestapproximation

[Bearbeiten | Quelltext bearbeiten]

Der Zusammenhang zwischen dem Interpolationpolynom und dem Polynom, welches die Funktion am besten bezüglich der Maximumsnorm ‖ ⋅ ‖ max {\displaystyle \|\cdot \|_{\max }} {\displaystyle \|\cdot \|_{\max }} annähert, ist wie folgt gegeben:

Seien dazu folgende Objekte gegeben

  • eine stetige, zu nähernde Funktion: f ∈ C ( [ a , b ] ) {\displaystyle f\in C([a,b])} {\displaystyle f\in C([a,b])}
  • Stützstellen: x 0 , … , x n ∈ [ a , b ] {\displaystyle x_{0},\ldots ,x_{n}\in [a,b]} {\displaystyle x_{0},\ldots ,x_{n}\in [a,b]}
  • Lebesgue-Konstante: Λ n {\displaystyle \Lambda _{n}} {\displaystyle \Lambda _{n}}
  • Interpolationspolynom: P ∈ P n {\displaystyle P\in P_{n}} {\displaystyle P\in P_{n}} mit P ( x i ) = f ( x i ) {\displaystyle P(x_{i})=f(x_{i})} {\displaystyle P(x_{i})=f(x_{i})}
  • Bestapproximation: Q ∈ P n {\displaystyle Q\in P_{n}} {\displaystyle Q\in P_{n}} mit ‖ f − Q ‖ max = min R ∈ P n ‖ f − R ‖ max {\displaystyle \|f-Q\|_{\max }=\min _{R\in P_{n}}\|f-R\|_{\max }} {\displaystyle \|f-Q\|_{\max }=\min _{R\in P_{n}}\|f-R\|_{\max }}.

Dann gilt die Abschätzung

‖ f − P ‖ max ≤ ( 1 + Λ n ) ‖ f − Q ‖ max . {\displaystyle \|f-P\|_{\max }\leq (1+\Lambda _{n})\|f-Q\|_{\max }\,.} {\displaystyle \|f-P\|_{\max }\leq (1+\Lambda _{n})\|f-Q\|_{\max }\,.}

Verallgemeinerung

[Bearbeiten | Quelltext bearbeiten]

Bisher wurden die Stützstellen x i {\displaystyle x_{i}} {\displaystyle x_{i}} des Interpolationspolynoms P {\displaystyle P} {\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

[Bearbeiten | Quelltext bearbeiten]
→ Hauptartikel: Lebesgue-Konstante

Sei der Operator, der einer Funktion f {\displaystyle f} {\displaystyle f} sein Interpolationspolynom P ( f ) {\displaystyle P(f)} {\displaystyle P(f)} zuordnet, definiert durch

ϕ n : C ( [ a , b ] ) → P n , f ↦ P ( f ) = ∑ i = 0 n f ( x i ) l i , {\displaystyle \phi _{n}\colon C([a,b])\rightarrow P_{n}\,,\,f\mapsto P(f)=\sum _{i=0}^{n}f(x_{i})l_{i}\,,} {\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 {\displaystyle l_{i}} {\displaystyle l_{i}} das i {\displaystyle i} {\displaystyle i}-te Lagrange-Polynom ist.

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

Λ n := ‖ ϕ n ‖ max . {\displaystyle \Lambda _{n}:=\|\phi _{n}\|_{\max }\,.} {\displaystyle \Lambda _{n}:=\|\phi _{n}\|_{\max }\,.}

Die Norm kann explizit berechnet werden:

Λ n = max x ∈ [ a , b ] ∑ i = 0 n | l i ( x ) | . {\displaystyle \Lambda _{n}=\max _{x\in [a,b]}\sum _{i=0}^{n}|l_{i}(x)|\,.} {\displaystyle \Lambda _{n}=\max _{x\in [a,b]}\sum _{i=0}^{n}|l_{i}(x)|\,.}

Literatur

[Bearbeiten | Quelltext 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). 
  • 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

[Bearbeiten | Quelltext bearbeiten]
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

[Bearbeiten | Quelltext bearbeiten]
  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. ↑ a b Rolf Rannacher: Numerik 0: Einführung in die Numerische Mathematik. Heidelberg University Publishing. Heidelberg University Publishing, Heidelberg 2017, ISBN 978-3-946054-27-6, 2.1 Polynominterpolation, S. 24–34, doi:10.17885/heiup.206.281. 
  3. ↑ Jochen Werner: Numerische Mathematik. 1. Auflage. Vieweg Studium, Nr.32, Vieweg Verlagsgesellschaft, 1992, ISBN 3-528-07232-6, 10.4.  – 4.1.3. (PDF; 11,7 MB) sam.math.ethz.ch
  4. ↑ Andrei Nikolajewitsch Kolmogorow et al.: Mathematics of the 19th Century. 1. Auflage. Birkhäuser, 1998, ISBN 3-7643-5845-9, Kap. 4 (englisch, google.de). 
Normdaten (Sachbegriff): GND: 4175264-8 (GND Explorer, lobid, OGND, AKS)
Abgerufen von „https://de.teknopedia.teknokrat.ac.id/w/index.php?title=Polynominterpolation&oldid=259834601“
Kategorien:
  • Numerische Mathematik
  • Theorie der Polynome

  • indonesia
  • Polski
  • العربية
  • Deutsch
  • English
  • Español
  • Français
  • Italiano
  • مصرى
  • Nederlands
  • 日本語
  • Português
  • Sinugboanong Binisaya
  • Svenska
  • Українська
  • Tiếng Việt
  • Winaray
  • 中文
  • Русский
Sunting pranala
Pusat Layanan

UNIVERSITAS TEKNOKRAT INDONESIA | ASEAN's Best Private University
Jl. ZA. Pagar Alam No.9 -11, Labuhan Ratu, Kec. Kedaton, Kota Bandar Lampung, Lampung 35132
Phone: (0721) 702022
Email: pmb@teknokrat.ac.id