08.1 – Newton-Interpolation

Bei der Newton-Interpolation verwendet man als Basis von ${\mathbb{P}_n}$ die Polynome

${\omega _i}\left( x \right) = \prod\limits_{j = 0}^{i-1} {\left( {x-{x_j}} \right)} ,\quad i = 0, \ldots ,n$

Nach Satz 3, Seite 41 der Vorlesung von Professor Greither hat das Interpolationspolynom ${p_n}$ in dieser Basis die Darstellung

${p_n}\left( x \right) = f\left[ {{x_0}} \right]{\omega _0}\left( x \right)+f\left[ {{x_1},{x_1}} \right]{\omega _1}\left( x \right)+ \ldots +f\left[ {{x_0},{x_1}, \ldots ,{x_n}} \right]{\omega _n}\left( x \right)$

wobei die Koeffizienten der Rekursionsformel

$f\left[ {{x_i}} \right] = f\left( {{x_i}} \right)$

$f\left[ {{x_i}, \ldots ,{x_{i+k}}} \right] = \frac{{f\left[ {{x_{i+1}}, \ldots ,{x_{i+k}}} \right]-f\left[ {{x_i}, \ldots ,{x_{i+k-1}}} \right]}}{{{x_{i+k}}-{x_i}}}$

genügen.

a )

Geben Sie das Gleichungssystem zur Berechnung der Koeffizienten an und lösen Sie es für den Fall $n = 2$ .

b )

Geben Sie einen Algorithmus zur Berechnung der Koeffizienten (dividierte Differenzen) des Interpolationspolynoms an.

c )

Wir betrachten im Folgenden die Funktion $f\left( x \right) = \sin \left( {\pi x} \right)$

Berechnen Sie die Koeffizienten des Newton’schen Interpolationspolynoms $p\left( x \right)$ ausgehend von den Stützstellen ${x_0} = 0,\:\:{x_1} = \frac{1}{2},\:\:{x_2} = 1$ und geben Sie das Polynom an.

d )

Für $f \in {c^{n+1}}\left( {\left[ {a,b} \right]} \right)$ existiert ein $\xi \in \left[ {a,b} \right]$ mit

$f\left( x \right)-p\left( x \right) = {\omega _{n+1}}\left( x \right)\frac{{{D^{n+1}}f\left( \xi \right)}}{{\left( {n+1} \right)!}}$

Schätzen Sie mit Hilfe dieser Fehlerformel den Fehler $\left| {f\left( x \right)-p\left( x \right)} \right|$ in Aufgabe c) ab

Lösung

a )

${p_n}\left( x \right) = {c_0}{\omega _0}\left( x \right)+{c_1}{\omega _1}\left( x \right)+ \ldots +{c_n}{\omega _n}\left( x \right)\quad \quad \left( * \right)$

${\omega _i}\left( x \right) = \prod\limits_{j = 0}^{i-1} {\left( {x-{x_j}} \right)} ,\quad i = 0, \ldots ,n$

Aus $\left( * \right)$ folgen n+1 Gleichungen für die gegebenen Stützstellen ${x_i}$ :

${c_0}{\omega _0}\left( {{x_i}} \right)+{c_1}{\omega _1}\left( {{x_i}} \right)+ \ldots +{c_n}{\omega _n}\left( {{x_i}} \right) = {f_i},\quad \quad i = 0, \ldots ,n$

In Matrixschreibweise:

$\left( {\begin{array}{*{20}{c}}{{\omega _0}\left( {{x_0}} \right)} & {{\omega _1}\left( {{x_0}} \right)} & \cdots & {{\omega _n}\left( {{x_0}} \right)} \\{{\omega _0}\left( {{x_1}} \right)} & {{\omega _1}\left( {{x_1}} \right)} & \cdots & {{\omega _n}\left( {{x_1}} \right)} \\ \vdots & \vdots & \ddots & \vdots \\{{\omega _0}\left( {{x_n}} \right)} & {{\omega _1}\left( {{x_n}} \right)} & \cdots & {{\omega _n}\left( {{x_n}} \right)} \\ \end{array} } \right)\left( {\begin{array}{*{20}{c}}{{c_0}} \\ \vdots \\ \vdots \\{{c_n}} \\ \end{array} } \right) = \left( {\begin{array}{*{20}{c}}{{f_0}} \\ \vdots \\ \vdots \\{{f_n}} \\ \end{array} } \right)$

Es gilt allerdings ${\omega _i}\left( {{x_k}} \right) = 0\quad \forall k < i$ . Die Matrix ist damit eine untere linke Dreiecksmatrix. Speziell für den Fall $n = 2$ gilt:

$\left( {\begin{array}{*{20}{c}}{{\omega _0}\left( {{x_0}} \right)} & 0 & 0 \\{{\omega _0}\left( {{x_1}} \right)} & {{\omega _1}\left( {{x_1}} \right)} & 0 \\{{\omega _0}\left( {{x_2}} \right)} & {{\omega _1}\left( {{x_2}} \right)} & {{\omega _2}\left( {{x_2}} \right)} \\ \end{array} } \right)\left( {\begin{array}{*{20}{c}}{{c_0}} \\{{c_1}} \\{{c_2}} \\ \end{array} } \right) = \left( {\begin{array}{*{20}{c}}{{f_0}} \\{{f_1}} \\{{f_2}} \\ \end{array} } \right)$

Aus der ersten Zeile folgt sofort:

${c_0} = \frac{{{f_0}}}{{{\omega _0}\left( {{x_0}} \right)}} = {f_0} = f\left[ {{x_0}} \right]$

Dies können wir in der zweiten Zeile einsetzen und auflösen:

${c_1} = \frac{{{f_1}-{\omega _0}\left( {{x_1}} \right){c_0}}}{{{\omega _1}\left( {{x_1}} \right)}} = \frac{{f\left[ {{x_1}} \right]-f\left[ {{x_0}} \right]}}{{{x_1}-{x_0}}} = f\left[ {{x_0},{x_1}} \right]$

Damit erhalten wir aus der letzten Zeile:

${c_2} = \frac{{{f_2}-{c_0}{\omega _0}\left( {{x_2}} \right)-{c_1}{\omega _1}\left( {{x_2}} \right)}}{{{\omega _2}\left( {{x_2}} \right)}}$

$= \frac{{{f_2}-{f_0}-f\left[ {{x_0},{x_1}} \right]\left( {{x_2}-{x_0}} \right)}}{{\left( {{x_2}-{x_1}} \right)\left( {{x_2}-{x_0}} \right)}}$

$= \frac{{{f_2}-{f_1}+{f_1}-{f_0}}}{{\left( {{x_2}-{x_1}} \right)\left( {{x_2}-{x_0}} \right)}}-\frac{{f\left[ {{x_0},{x_1}} \right]\left( {{x_2}-{x_0}} \right)}}{{\left( {{x_2}-{x_1}} \right)\left( {{x_2}-{x_0}} \right)}}$

$= \frac{{{f_2}-{f_1}+{f_1}-{f_0}}}{{\left( {{x_2}-{x_1}} \right)\left( {{x_2}-{x_0}} \right)}}-\frac{{f\left[ {{x_0},{x_1}} \right]}}{{\left( {{x_2}-{x_1}} \right)}}$

$= \frac{1}{{{x_2}-{x_0}}}\left\{ {\frac{{{f_2}-{f_1}}}{{{x_2}-{x_1}}}+f\left[ {{x_0},{x_1}} \right]\left( {\frac{{{x_1}-{x_0}}}{{{x_2}-{x_1}}}-\frac{{{x_2}-{x_0}}}{{{x_2}-{x_1}}}} \right)} \right\}$

$= \frac{1}{{{x_2}-{x_0}}}\left\{ {f\left[ {{x_1},{x_2}} \right]-f\left[ {{x_0},{x_1}} \right]} \right\}$

$= f\left[ {{x_0},{x_1},{x_2}} \right]$

b )

Schema zur Veranschaulichung der Rekursionsformel:

system-berechnung-koeffizienten

Das Tableau wird also spaltenweise aufgebaut.

Zusätzliche Stützstellen können durch zusätzliche Zeilen berücksichtigt werden. Dadurch können alle bisherigen Ergebnisse wieder verwendet werden.

Algorithmus:

for i = 0 : n
	f(x(i)) = f(i)
end
for k = 1 : n
	for i = k : n
		f(x(i-k),...,x(i)) = (f(x(i-k+1),...,x(i)) - f(x(i-k),...,x(i-1))) / (x(i)-x(i-k))
	end
end

c )

$f\left[ {{x_0}} \right] = 0$

$f\left[ {{x_1}} \right] = 1\quad \quad f\left[ {{x_0},{x_1}} \right] = \frac{{1-0}}{{\frac{1}{2}-0}} = 2$

$f\left[ {{x_2}} \right] = 0\quad \quad f\left[ {{x_1},{x_2}} \right] = \frac{{0-1}}{{1-\frac{1}{2}}} = -2\quad \quad f\left[ {{x_0},{x_1},{x_2}} \right] = \frac{{-2-2}}{{1-0}} = -4$

Unser Polynom lautet damit:

${p_2}\left( x \right) = f\left[ {{x_0}} \right]{\omega _0}\left( x \right)+f\left[ {{x_0},{x_1}} \right]{\omega _1}\left( x \right)+f\left[ {{x_0},{x_1},{x_2}} \right]{\omega _2}\left( x \right)$

$= 0 \cdot 1+2\left( {x-\underbrace {{x_0}}_{ = 0}} \right)-4\left( {x-\underbrace {{x_0}}_{ = 0}} \right)\left( {x-\underbrace {{x_1}}_{ = 0.5}} \right)$

$= 4x-4{x^2}$

d )

$f\left( x \right)-p\left( x \right) = {\omega _{n+1}}\left( x \right)\frac{{{D^{n+1}}f\left( {{\xi _x}} \right)}}{{\left( {n+1} \right)!}}$

Die n+1-te Ableitung (in unserem Fall die dritte) lautet $-{\pi ^3}cos\left( {\pi \xi } \right)$ .

$n = 2$

$f\left( x \right) = \sin \left( {\pi x} \right) = \left( {x-0} \right)\left( {x-\frac{1}{2}} \right)\left( {x-1} \right)\frac{{-{\pi ^3}\cos \left( {\pi {\xi _x}} \right)}}{{3!}}$