Computernumerik am WWW

[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

6.7.6 Verfahrensfehler der Polynom-Interpolation

Einführung in die Verfahrensfehler der Polynom-Interpolation
Satz (Fehlerdarstellung)
Schranken für den Interpolationsfehler
Beispiele zu 'Schranken für den Interpolationsfehler'
- Interpolation der Sinusfunktion
- Lineare Interpolation

Einführung in die Verfahrensfehler der Polynom-Interpolation

Zunächst soll der Fehler eines Interpolationspolynoms P_d, das durch

$P_d(x_i) = f_i := f(x_i), \quad i = 0, 1, \dots, d,$ Formel (7.6.1)

definiert ist, untersucht werden. Die Fehlerfunktion

e_d(x) := P_d(x) - f(x)

besitzt entsprechend der Interpolationsbedingung (7.6.1) an den Interpolationsknoten x₀ ,x₁ ,...,x_d Nullstellen; dazwischen können die Werte des Interpolationsfehlers e_d aber beliebig groß werden. Nur wenn zusätzliche Information über f vorliegt, kann man auch dort Aussagen über die Größe des Fehlers machen.

Satz (Fehlerdarstellung)

Wird eine Funktion f $\in$ C^d+1[a,b] an den paarweise verschiedenen Knoten a <= x₀ ,x₁ , ...,x_d <= b durch das Polynom P_d interpoliert, so gibt es fü jedes x $\in$ [a ,b] eine Zahl aus dem kleinsten Intervall, das alle xi und x enthält, sodaß sich der Fehler des Interpolationspolynoms an der Stelle x durch

$e_d(x) := P_d(x) - f(x) = \frac{f^{(d+1)}(\xi)}{(d+1)!} (x-x_0) (x-x_1) \cdots (x-x_d)$ Formel (7.6.2)

ausdrücken läßt.

Beweis: Die Eigenschaft der Fehlerfunktion e_d, an den Interpolationsknoten x₀ , ...,x_d zu verschwinden, läßt sich durch

$e_d(x) = (x-x_0) (x-x_1) \cdots (x-x_d) \cdot q(x) = \omega_{d+1}(x) \cdot q(x)$ Formel (7.6.3)

mit einer passenden Funktion q und dem Knotenpolynom w_d+1 $\in$ $\P$ _d+1

$\omega_{d+1}(x) := \prod_{j=0}^d (x-x_j)$
ausdrücken. Für ein festes $\xquer$ $\in$ [a ,b] mit $\xquer$ $\not\in$ { x₀ ,x₁ , ...,x_d } kann man mit w_d+1 folgende Hilfsfunktion definieren:

$s(x) := P_d(x) - f(x) - \omega_{d+1}(x) \cdot q(\xquer)$
Diese Funktion besitzt d+2 Nullstellen, denn es gilt

s( $\xquer$ ) = 0 und s>(x_i) = 0, i = 0,1,...,d
Im kleinsten Intervall I, das alle Punkte $\xquer$ ,x₀ ,x₁ , ...,x_d enthält, hat die Funktion s also d+2 verschiedene Nullstellen. Da ausreichende Differenzierbarkeit vorausgesetzt wurde, folgt aus dem Satz von Rolle, daß s' in I mindestens d+1 Nullstellen besitzt. Weiteres Differenzieren und neuerliche Anwendung des Satzes von Rolle zeigt , daß s'' mindestens d Nullstellen in I besitzt. Dementsprechend hat schließlich s^(d+1) mindestens eine Nullstelle in I, die im folgenden mit bezeichnet wird.
Da q( $\xquer$ ) eine Konstante ist und

$P_d^{(d+1)}(x) \equiv 0$
gilt, erhält man

$s^{(d+1)}(x) = f^{(d+1)}(x) - (d+1)!\, q(\xquer)$
Diese Gleichung kann man an der Nullstelle x = von s^(d+1) nach q( $\xquer$ ) auflösen:

$q(\xquer) = \frac{f^{(d+1)}(\xi)}{(d+1)!}$
Durch Einsetzen in die Formel (7.6.3)erhält man schließlich die Fehlerdarstellung

$e_d(x) = \frac{f^{(d+1)}(\xi)}{(d+1)!} \omega_{d+1}(x)$

Schranken für den Interpolationsfehler

Mit einer Betragsschranke für die (d+1)-te Ableitung von f,

$\max \limits_{x \in I} |f^{(d+1)}(x)| = \|f^{(d+1)}\|_{\infty} \le M_{d+1}$
erhält man eine Abschätzung für den Verfahrensfehler der Interpolation:

$|e_d(x)| \leq \frac{M_{d+1}}{(d+1)!} |\omega_{d+1}(x)| \qquad \mbox{f$ Formel (7.6.4)

bzw. für jede L_p-Norm mit 1 kleiner-gleich p kleiner gleich unendlich die Abschätzung

$\|P_d - f\| \le \frac{M_{d+1}}{(d+1)!} \| \omega_{d+1} \|$ Formel (7.6.5).

Wie man den Formeln (7.6.2) und (7.6.5) entnehmen kann, hängt die Größe des Interpolationsfehlers sowohl von der Eigenschaft der interpolierten Funktion f als auch von der Lage der Interpolationsknoten x₀ , ...,x_d charakterisiert durch w_d+1(x) bzw. $\| \omega_{d+1} \|$ ab. Die günstigste Knotenanordnung bezüglich der Fehlerabschätzung (7.6.5) erhält man, wenn $\| \omega_{d+1} \|$ so klein wie möglich ist. Für die -Norm sind wegen Satz 9.3.1 (Tschebyscheff) die Tschebyscheff-Nullstellen die optimalen Interpolationsknoten.

Die Fehlerformel (7.6.4) ist für praktische Anwendungen (zahlenmäße Fehlerabschätzungen) nur dann geeignet, wenn f hinreichend oft stetig differnzierbar ist und man Schranken für die Ableitung der zu approximierenden Funktion f auf dem Approximationsintervall I explizit kennt. Fehlerformeln des Typs (7.6.4) sind jedoch auch in Situationen interessant, in denen zahlenmäße Fehlerschranken nicht gewonnen werden können, da sie eine qualitative Beschreibung des Fehlerverhaltens ermöglichen. Nimmt man z.B. an, daß eine Funktion f $\in$ C²[a ,b] durch einen Polygonzug, d.h. durch eine stückweise lineare Interpolationsfunktion auf einer äquidistanten Knotenmenge (mit dem Stützstellenabstand h=(ba)/d) interpoliert wird, so folgt aus

daß der Fehler - in Abhängigkeit von der Schrittweite h - durch O(h²) beschrieben werden kann.

Beispiele zu 'Schranken für den Interpolationsfehler'

Es folgen nun zwei Beispiele die Ihnen die den Stoff des Kapitels "Schranken für den Interpolationsfehler" veranschaulichen sollen.

Beispiel 1 (Interpolation der Sinusfunktion)

Angenommen, man verwendet die Werte
f (x_i) := sin (x_i), x_i := 0, 0.1, 0.2, 0.3, 0.4
zur Interpolation mit einem Polynom P₄ $\in$ $\P$ ₄ und approximiert sin(0.14) durch P₄(0.14). Mit

$M_5 = \max \limits_{x \in [0, 0.4]} |\sin^{(5)}(x)| = \max \limits_I |\cos(x)| = 1$
erhält man eine obere Schranke für den Fehler

$|e_4(0.14)| \leq \frac{1}{5!} |0.14||0.14-0.1||0.14-0.2||0.14-0.3||0.14-0.4| \approx 1.17 \cdot 10^{-7}.$ .

Beispiel 2 (Lineare Interpolation)

Das Interpolationspolynom P₁ $\in$ $\P$ ₁, das durch die Punkte (x₀ , f( x₀)) und (x₁ , f( x₁)) geht, ist durch

$P_1(x) = f(x_0) + (x-x_0) \frac{f(x_1) - f(x_0)}{x_1-x_0}$
gegeben, und der Fehler ist

$e_1(x) = P_1(x) - f(x) = \frac{f''(\xi)}{2}(x-x_0)(x-x_1)$ .
Für x $\in$ [x₀ , x₁] und

$M_2 := \max \{ |f''(x)|: x \in [x_0,x_1] \}$
gilt die Abschätzung

$|e_1(x)| \leq M_2 \frac{|x-x_0||x-x_1|}{2} \leq M_2 \frac{(x_1-x_0)^2}{8}$ .
Wenn man also bei Beispiel 1 fünf äquidistante Werte von sin(x) auf [0,0.4] hat, dann ist dort der Approximationsfehler des Polygonzuges, der durch diese 5 Punkte geht, nicht größer als

$M_2 \frac{(x_{i+1} - x_i)^2}{8} = 0.4 \cdot \frac{0.1^2}{8} = 5 \cdot 10^{-4}$ .
Erst mit 500 äquidistanten Werten erhält man die Fehlerschranke 1.25 * 10 ^-7 , die mit jener des Interpolationspolynoms P₄ aus dem Beispiel 1 vergleichbar ist.

[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]