1.1. Existenz und Eindeutigkeit der Polynominterpolation

Gesucht ist eine Funktion F(x), die die sogenannte Interpolationbedingung erfüllt: F soll an den Knoten oder Stützpunkten xi mit der Funktion f übereinstimmen.
F(j)(xi) = f(j)(xi) für alle i, j.
Die Werte f(j)(xi) heißen daher auch Stützwerte.

Bemerkung 1.1: Bei gegebenen (n + 1) Stützstellen (xi,  f (xi)), i = 0, 1 ,.., n lautet die Interpolationsforderung:
F(xi) = a0 + a1xi1 + a2xi2 + ... + anxin = f(xi) = fi, i = 0, 1, ..., n.

Bei der Polynominterpolation ist daher ein Polynom n-ten Grades gesucht, das die Interpolationsforderung erfüllt. Es werden Polynome betrachtet, da diese einfach zu handhaben und zu berechnen sind.
Im folgenden gilt daher
F(x) = pn(x) = a0 + a1x + a2x2 + ... + an-1xn-1 + anxn (1.1)
Für gegebene (n + 1) Stützstellen (xi, f(xi)), i = 0, 1, ..., n, ergibt sich aus der Interpolationsforderung folgendes Gleichungssystem.
1  x0 x02 ...  x0n   a0  =  f0
1  x1 x12 ...  x1n a1 f1
1  x2 x22 ...  x2n a2 f2
: : : : : :
1  xn xn2 ...  xnn an fn (1.2)
Koeffizientenmatrix / Vandermonde'sche Matrix

Existiert eine eindeutige Lösung des Gleichungssystems, so gibt es genau ein Polynom n-ten Grades das die Aufgabe erfüllt.

Bemerkung 1.2: Eindeutigkeit
Ein lineares quadratisches Gleichungssystem ist genau dann eindeutig lösbar, wenn die Determinate der Koeffizientenmatrix ungleich null ist.
1 x0 x02 ... x0n = n-1prod i=0 nprod j=i+1 (xj - xj)
1 x1 x12 ... x1n
: : : :
1 xn xn2 ... xnn

Falls alle xi paarweise verschieden sind, ist die Determinante der Koeffizientenmatrix ungleich null.
Þ Das Gleichungssystem (1.2) ist damit eindeutig lösbar.

Mit dem GAUSS-Verfahren lässt sich das Gleichungssystem lösen und man erhält die Koeffizienten des gesuchten Polynoms pn(x).
Das HORNER-Schema ist eine effiziente Möglichkeit den Funktionswert eines Polynoms an einer Stelle xi zu berechnen.

Bemerkung 1.3: HORNER-Schema: Das Polynom wird durch fortlaufendes Ausklammern von x umgeformt und man erhält dadurch folgende Darstellung.
pn(x) = a0 + a1x + a2x2 + ... + an-1xn-1 + anxn (1.3)
= a0 + x(a1 + a2x1 + ... + an-1xn-2 + anxn-1)
= a0 + x(a1 + x(a2 + ... + an-1xn-3 + anxn-2))
    .
    .
    .
= a0 + x(a1 + x(a2 + x(... + x(an-1 + xan)...)))(1.4)
Aus der Darstellung (1.4) ergibt sich folgender, leicht zu programmierender Algorithmus zur Berechnung des Funktionswertes eines Polynoms an einer Stelle x.
Algorithmus:
x0:=x
bn:=an;
for i:=n-1 downto 0 do
bi:=bi+1x0+ai;
fn(x0)=b0

Das HORNER-Schema lässt sich auch formal darstellen:
HORNER-Schema

Das HORNER-Schema hat den Vorteil, dass weniger Rechenschritte braucht werden als bei der Berechnung des Funktionswert eines Polynoms der Form (1.3). Um den Funktionswert eines Polynoms dritten Grades zu berechnen, muss man zum Beispiel neun Schritte (3 Additionen und 6 Multiplikationen) ausführen und nach dem HORNER-Schema braucht man nur sechs Operationen (3 Multiplikationen und 3 Additionen).
Weiterhin kann man das HORNER-Schema auch für die Berechnung von Ableitungen benutzen. (Dazu benötigt man die im Beispiel 1.1 eingeführten Variablen c, d, e.)

Beispiel 1.1:
Berechne den Funktionswert des Polynoms p3(x) = x3 + 2x2 + x + 1 an der Stelle x = x0 = (-1)
1 = a3 2 = a2 1 = a1 1 = a0
↓ -1 = b3x0 -1 = b2x0 0 = b1x0
1 = b3 1 = b2 0 = b1 1 = b0
↓ -1 = c3x0 0 = c2x0
1 = c3 0 = c2 0 = c1
↓ -1
1 = d3 -1 = d2
↓
1 = e3

Berechne den Funktionswert des Polynoms p5(x) = x5 + x3 + x + 1 an der Stelle x = x0 = 1
1 0 1 0 1 1
↓ 1 1 2 2 3
1 1 2 2 3 4
1 2 4 6
1 2 4 6 9
↓ 1 3 7
1 3 7 13
↓ 1 4
1 4 11
1
1 5
↓
1

Berechne den Funktionswert des Polynoms p3(x) = a3x3 + a2x2 + a1x + a0 an der Stelle x = x0 =
a3 a2 a1 a0
↓
↓
↓
↓

.. Inhalt
<- Polynom-Interpolation
-> LAGRANGE-Interpolation

Hosted by www.Geocities.ws

1