Zu n + 1 vorgegebenen Stützpunkten (alle xi verschieden) existiert genau ein Polynom mit Grad £ n, das durch alle Punkte geht.
Die ci sind die Koeffizienten. Falls cn ¹ 0 ist, heißt n Grad des Polynoms und cn höchster Koeffizient. Polynome haben den Vorteil, daß sie selbst und alle ihre Ableitungen stetig sind. Zur Berechnung der Koeffizienten aus den Stützpunkten gibt es z.B. folgende Verfahren:
- Gleichungssystem:
- Durch Einsetzen der Punktkoordinaten der n + 1 Stützpunkte erhält man ein lineares Gleichungssystem mit n + 1 Gleichungen für die n + 1 Unbekannten c0 , c1 , ...., cn .
für i = 0, 1, ....., n
- Idee von Lagrange:
- Dieses Verfahren zerlegt das Polynom p(x) in eine Summe von n + 1 Polynomen n-ten Grades, wobei das i-te Polynom durch den Punkt Pi geht und an allen anderen Stützstellen xj ( j = 0 , ...., n; j ¹ i) Nullstellen hat. Dazu definiert man die Lagrange - Faktoren Li (x) das sind Polynome n-ten Grades mit folgenden Eigenschaften:
Li (xi) = 1
Li (xj) = 0 für j ¹ i
Die Formel für die Lagrange - Faktoren lautet:
Daraus erhält man sofort das gesuchte Interpolationspolynom
- Dividierte Differenzen nach Newton:
Es stellt sich allerdings die Frage, ob die Interpolation (durch Polynome hohen Grades) in der Praxis überhaupt sinvoll verwendet werden kann. Polynome sind wohl stetig und stetig differenzierbar; aber sind sie auch immer schön und glatt, wie das in der Computergraphik erwünscht ist?
Weierstraßscher Approximationssatz:
- Jede stetige Funktion ist in einem endlichen Intervall durch ein Polynom beliebig genau approximierbar. (Je höher der Grad des Polynoms ist, desto besser kann man approximieren.)
Theoretisch ist also eine beliebig gute Approximation mit Polynomen für jede stetige Funktion möglich, in der Praxis ergeben sich jedoch oft Probleme; Interpolationspolynome neigen sehr zum Überschwingen.
Runge (ca. 1900):
Eine stetige Funktion f(x) mit x Î [a,b] soll durch ein Polynom n-ten Grades pn(x) approximiert werden. Dazu wählt man n + 1 äquidistante Stützstellen im Intervall [a,b] und berechnet das Interpolationspolynom. Man versucht, die Güte der Approximation durch Erhöhen der Anzahl der Stützstellen zu verbessern. Runge hat gezeigt, daß das Interpolationspolynom pn(x) für n® ¥ nicht immer gegen die Funktion f(x) konvergiert. Das gilt auch bei sehr einfachen f (x) :
mit x Î [-5, 5]
Das Überschwingen wird mit wachsendem n immer stärker.
Eine grafische Darstellung können Sie wieder mit Ipax II erhalten.
Interpolation durch ein Polynom hat also mehrere gravierende Nachteile:
- Es kann Überschwingen auftreten, dadurch ist die Kurve nicht glatt.
- Sind viele Stützpunkte vorhanden, ist der Grad des Polynoms sehr hoch. Polynome hohen Grades können empfindlich gegenüber geringfügigen Änderungen der Daten (Koordinaten der Stützpunkte) sein.
- Der Rechenaufwand steigt mit der Anzahl der Stützpunkte stark an.
Eine Alternative zur Verwendung eines durchgehenden Interpolationspolynoms hohen Grades ist die stückweise Interpolation durch Polynome niedrigen Grades. Spezielle Verfahren dieser Art, z.B. Natürliche Splines oder B-Spline-Kurven, werden später ausführlich behandelt.
