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!}}

Da \left| {\cos \left( x \right)} \right| \leq 1\quad \forall x, folgt

\left| {f\left( x \right)-p\left( x \right)} \right| \leq \frac{{{\pi ^3}}}{6}\left| {{x^3}-\frac{3}{2}{x^2}+\frac{1}{2}x} \right|

Wir bestimmen die globalen Extremstellen von {x^3}-\frac{3}{2}{x^2}+\frac{1}{2}x:

\omega _3^\prime \left( x \right) = 3{x^2}-3x+\frac{1}{2} = 0\quad \Rightarrow \quad {x_{1,2}} = \frac{1}{2} \pm \frac{1}{{2\sqrt 3 }}

{\omega _3}\left( {{x_1}} \right) \approx -0,048

{\omega _3}\left( {{x_2}} \right) \approx 0,048

An den Rändern gilt:

{\omega _3}\left( 0 \right) = {\omega _3}\left( 1 \right) = 0

\quad \Rightarrow \quad \left| {f\left( x \right)-p\left( x \right)} \right| \leq \frac{{{\pi ^3}}}{6} \cdot 0,048 \approx 0,248

Ähnliche Artikel

Kommentar verfassen