Modellierung und Simulation Approximation durch Polynome Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Anwendungen: zur Vereinfachung einer gegebenen Funktion durch einen Polynomausdruck. Dann sind übliche Rechenoperation +, −, ·, / möglich. zur Interpolation von Daten einer Tabelle Modellierung und Simulation Britta Nestler Beispiel Approximation mit Polynomen Trotz guter Verkaufslage verringern sich die Gewinne G(x) ab einer bestimmten Stückzahl x aufgrund steigender Produktionskosten. Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Anzahl xi 0 10 20 30 40 50 60 70 Kosten K(xi ) 20 80 100 140 260 370 520 980 Erlös E(xi ) 0 180 360 540 720 810 900 1080 Gewinn G(xi ) - 20 100 260 400 460 440 380 100 Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Kurvenverlauf von K(x), E(x), G(x) als Geradenstücke Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Frage: Wo liegt die Gewinnzone ? Wo liegt das Gewinnmaximum? Nullstellenproblem Interpolationspolynom Taylorreihen Antwort: Splines Gewinnzone: Nullstelle der Funktion, d.h. G(x) = 0 Gewinnmaximum: Extremstelle der Funktion, d.h. G0 (x) = 0 Fazit: Man benötigt eine Funktionsdarstellung für G(x), z.B. durch Approximation der Daten über eine Polynominterpolation. Modellierung und Simulation Polynome Britta Nestler Approximation mit Polynomen besonders geeignet in der Numerik, da die Auswertung nur einfache Addition und Multiplikation bedeutet. Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Definition (1.1.1) Interpolationspolynom Taylorreihen Splines Eine Funktion f (x) für f : R → R der Form f (x) = an xn + an−1 xn−1 + . . . + a1 x + a0 mit an 6= 0 heißt Polynom vom Grad n. Die reellen Zahlen a0 , a1 , . . . , an heißen Koeffizienten des Polynoms. Beispiel f (x) = 4x8 − x5 − 10 Modellierung und Simulation Rechnen mit Polynomen Britta Nestler Definition (1.1.2) Approximation mit Polynomen Gegeben sind zwei Polynome f (x) und g(x) der Form f (x) = am xm + . . . + a1 x + a0 und g(x) = bn xn + . . . + b1 x + b0 vom Grad m und n mit m ≤ n. Dann ist: Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines f (x) + g(x) = bn xn + . . . + bm+1 xm+1 + (am + bm )xm + . . . + (a1 + b1 )x + (a0 + b0 ) und f (x) · g(x) = (am bn )xn+m + . . . + (a1 bn + . . . +am bn−m+1 )xn+1 + (a0 bn + . . . + am bn−m )xn + . . . + (a0 b1 + a1 b0 )x + a0 b0 Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Teilbarkeit durch einen Linearfaktor Satz (1.2.1) Für jedes Polynom f (x) und jeden Wert x0 gilt: f (x) = an xn + ....a1 x + a0 = (x − x0 )(bn xn−1 + ... + b2 x + b1 ) + f (x0 ) Nullstellenproblem Interpolationspolynom Taylorreihen Splines mit f (x0 ) = r. Beweis. (Herleitung des Horner - Schemas) (x − x0 ) · (bn xn−1 + ... + b2 x + b1 ) + r = bn xn + bn−1 xn−1 + . . . + b2 x2 + b1 x −x0 bn xn−1 − . . . − x0 b2 x − x0 b1 + r = an xn + . . . + a1 x + a0 Modellierung und Simulation Britta Nestler Approximation mit Polynomen Beweis. Ein Koeffizientenvergleich nach Potenzen von x ergibt Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines bn = an bn−1 = an−1 + x0 bn bn−2 = an−2 + x0 bn−1 .. .. . . b1 = a1 + x0 b2 r = a0 + x0 b1 Modellierung und Simulation Horner - Schema Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Verfahren zur systematischen Auswertung von Polynomen: Taylorreihen Splines an + bn % an−1 ... x0 bn ... bn−1 % . . . a2 x0 b3 b2 % a1 a0 x0 b2 x0 b1 b1 % r = f (x0 ) Modellierung und Simulation Britta Nestler Beispiel Approximation mit Polynomen Gegeben ist die Funktion f (x) = 2x4 − 6x3 − 35x + 10. Gesucht ist der Funktionswert an der Stelle x0 = 4 über das Horner-Schema. Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines −6 0 −35 10 + 2 · 4 2 · 4 +8 · 4 −3 · 4 2 2 +8 −3 −2 = f (4) 2 =⇒ f (4) = −2. Bemerkung: Das Horner-Verfahren ist besonders effektiv, da es Potenzieren vermeidet; Daher ist es für numerische Anwendungen geeignet. Modellierung und Simulation Nullstellenproblem Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Satz (1.3.1) Nullstellenproblem Interpolationspolynom Taylorreihen Splines Wenn x1 eine Nullstelle des Polynoms n-ten Grades f (x) ist, dann gilt: f (x) = (x − x1 )(bn xn−1 + . . . + b1 x) Bemerkung: Das Horner - Schema liefert die Zerlegung von f (x). Modellierung und Simulation Britta Nestler Approximation mit Polynomen Beispiel Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Gegeben ist die Funktion f (x) = x3 + 2x2 − 13x + 10. Gesucht ist das Restpolynom bei Abspaltung des Linearfaktors um x1 = 1. 1 2 −13 10 + 1 3 −10 1 3 −10 0 =⇒ f (x) = (x − 1) · (x2 + 3x − 10). Modellierung und Simulation Polynomdivision Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Dasselbe Ergebnis ergibt sich durch Polynomdivision: Nullstellenproblem Interpolationspolynom Taylorreihen Splines x3 + 2x2 − 13x + 10 : x − 1 = x2 + 3x − 10 −(x3 − x2 ) 3x2 − 13x −(3x2 − 3x) −10x + 10 −10x + 10 0 Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Bemerkung: Dividiert man f (x) durch (x − x1 ) ohne Rest, so ist das Resultat ein Polynom vom Grad n − 1. Interpolationspolynom Taylorreihen Splines Satz (1.3.2) Jedes Polynom n-ten Grades hat höchstens n verschiedene Nullstellen. Modellierung und Simulation Interpolationspolynom Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Satz (1.4.1) Zu n + 1 verschiedenen Wertepaaren (x1 , y1 ), (x2 , y2 ), . . . , (xn+1 , yn+1 ) gibt es genau eine Polynomfunktion f (x) mit f (xi ) = yi , i = 1, . . . , n + 1, deren Grad nicht größer als n ist. Das Polynom heißt Interpolationspolynom. Bemerkung: Aus den diskreten Werten (xi , yi ) lassen sich durch das Interpolationspolynom näherungsweise beliebige Zwischenwerte berechnen (interpolieren). Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Schematische Darstellung des Interpolationspolynoms Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Vandermondsche Matrix Die Bestimmung des Interpolationspolynoms erfolgt durch Einsetzen der diskreten Werte (xi , yi ) in die Funktion f (x) = an xn + an−1 xn−1 + . . . + a1 x + a0 und durch Bestimmung der Koeffizienten a0 , . . . , an aus den n + 1 Bedingungen f (xi ) = yi : Taylorreihen Splines an xn1 .. . + ... + a2 x21 .. . + a1 x1 .. . + a0 = .. . y1 .. . an xnn+1 + . . . + a2 x2n+1 + a1 xn+1 + a0 = yn+1 Eigenschaften: zu lösen ist ein lineares Gleichungssystem mit den Unbekannten a0 , . . . , an das Verfahren ist numerisch ungünstig, insbesondere für große n Modellierung und Simulation Britta Nestler Methode 2: Lagrange Formel Ansatz: Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor (x − x2 )(x − x3 )....(x − xn+1 ) + (x1 − x2 )(x1 − x3 )...(x1 − xn+1 ) (x − x1 )(x − x3 )....(x − xn+1 ) + y2 (x2 − x1 )(x2 − x3 )...(x2 − xn+1 ) .. .. .. . . . (x − x1 )(x − x2 )....(x − xn ) yn+1 (xn+1 − x1 )(xn+1 − x2 )..(xn+1 − xn ) f (x) = y1 Nullstellenproblem Interpolationspolynom Taylorreihen Splines Eigenschaften: ⇒ f (xi ) = yi das Verfahren ist ebenfalls für große Datenmengen rechenzeitaufwendig Modellierung und Simulation Methode 3: Newton - Algorithmus Britta Nestler (numerisch geschickteste Methode) Approximation mit Polynomen Ansatz: Polynome Teilbarkeit durch einen Linearfaktor f (x) = a0 + a1 (x − x1 ) + a2 (x − x1 )(x − x2 ) + . . . Nullstellenproblem +an (x − x1 )(x − x2 ) · · · (x − xn ) Interpolationspolynom Taylorreihen Splines Die Koeffizienten a0 , a1 , . . . , an können iterativ bestimmt werden. Einsetzen von x1 in die Funktion f (x) ergibt: y1 = f (x1 ) = a0 ⇒ a0 = y1 y2 − y1 x2 − x1 = f (x3 ) = a0 + a1 (x3 − x1 ) + a2 (x3 − x1 )(x3 − x2 ) y3 − a0 − a1 (x3 − x1 ) . . . . . . ⇒ a2 = (x3 − x1 )(x3 − x2 ) y2 = f (x2 ) = a0 + a1 (x2 − x1 ) y3 ⇒ a1 = Modellierung und Simulation Newton - Algorithmus (fortgesetzt) Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Algebraisches Umstellen ergibt: y3 − a0 − a1 (x3 − x1 ) (x3 − x1 )(x3 − x2 ) = ... y2 − y1 1 y3 − y2 − = x3 − x1 x3 − x2 x2 − x1 a2 = ⇒ a2 = D3,2 − D2,1 x3 − x1 mit den Abkürzungen: D2,1 = y2 − y1 x2 − x1 und D3,2 = y3 − y2 x3 − x2 Modellierung und Simulation Newton - Algorithmus (fortgesetzt) Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Mit den Abkürzungen: Nullstellenproblem Interpolationspolynom Taylorreihen Splines D4,3,2 = D4,3 − D3,2 x4 − x2 und D3,2,1 = D3,2 − D2,1 x3 − x1 und über vollständige Induktion kann man zeigen, dass gilt: ak−1 = Dk,...,1 das sogenannte Verfahren der dividierten Differenzen. Modellierung und Simulation Berechnungsschema: Newton - Algorithmus Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor k 1 xk x1 yk y1 2 x2 y2 3 x3 y3 Nullstellenproblem Interpolationspolynom Taylorreihen Splines 4 .. . x4 .. . y4 .. . = a0 & → D2,1 = & → D3,2 = & → D4,3 = y2 −y1 x2 −x1 y3 −y2 x3 −x2 y4 −y3 x4 −x3 = a1 & → D3,2,1 = & → D4,3,2 = D3,2 −D2,1 x3 −x1 D4,3 −D3,2 x4 −x2 .. .. . . wobei a0 = y1 , a1 = D2,1 , a2 = D3,2,1 , . . . , an = Dn+1,...,1 die gesuchten Koeffizienten des Interpolationspolynoms sind. & → Modellierung und Simulation Britta Nestler Beispiel Gegeben ist die folgende Wertetabelle: k xk yk Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor 1 0 -12 2 2 16 3 5 28 Nullstellenproblem Interpolationspolynom Taylorreihen Splines Gesucht ist das Interpolationspolynom f (x) der Form f (x) = a0 + a1 (x − x1 ) + a2 (x − x1 )(x − x2 ). Lösung über den Newton-Algorithmus: k 1 2 3 xk 0 2 5 yk -12 16 28 = 12 D2,1 = 16+12 2 D3,2 = 28−16 =4 3 D3,2,1 = 4−14 5 ⇒ f (x) = −12 + 14x − 2x(x − 2) = −2x2 + 18x − 12 = −2 Modellierung und Simulation Britta Nestler Approximation mit Polynomen Beispiel Gegeben ist ein zusätzlicher Messpunkt (x4 , y4 ) = (7, −54). Gesucht ist wieder das Interpolationspolynom, das durch alle Messpunkte verläuft. Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Lösung über den Newton-Algorithmus: k 1 2 3 4 xk 0 2 5 7 yk -12 16 28 -54 D2,1 = 14 D3,2 = 4 D4,3 = −41 D3,2,1 = −2 D4,3,2 = −9 D4,3,2,1 = −1 ⇒ f (x) = −12 + 14x − 2x(x − 2) − x(x − 2)(x − 5) = ... = −x3 + 5x2 + 8x − 12 Modellierung und Simulation Taylorreihen Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem √ Fast jede elementare Funktion (wie z.B. ex , sin x, x, ln x usw.) lässt sich in der Umgebung eines Punktes x0 durch einen Polynomausdruck f (x) = an xn + an−1 xn−1 + . . . + a1 x + a0 beliebig genau annähern. Interpolationspolynom Taylorreihen Splines Beispiel 1 Gegeben ist die Funktion f (x) = 1−x für |x| < 1. Gesucht ist ein Polynomausdruck, der f (x) annähert. Lösung ∞ X 1 = 1 + x + x2 + . . . + xn + . . . = xn 1−x n=0 Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Herleitung der Taylorformel Gegeben ist eine Funktion f (x) und gesucht ist eine Näherung in der Umgebung von x0 ∈ D. Modellierung und Simulation Herleitung der Taylorformel (fortgesetzt) Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullte Näherung p0 (x) p0 (x) = f (x0 ) Nullstellenproblem Interpolationspolynom Taylorreihen Splines zwischen p0 (x) und f (x) stimmt nur der Funktionswert an der Stelle x0 überein. Erste (lineare) Nährung p1 (x) p1 (x) = f (x0 ) + f 0 (x0 )(x − x0 ) (Tangente an die Funktion f (x) im Punkt x0 ) der Funktionswert und die erste Ableitung sind im Punkt x0 identisch. Modellierung und Simulation Herleitung der Taylorformel (fortgesetzt) Britta Nestler Approximation mit Polynomen Polynome Zweite (quadratische) Nährung p2 (x) Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines 00 f (x0 ) p2 (x) = f (x0 ) + f (x0 )(x − x0 ) + (x − x0 )2 2! 0 p2 (x) hat zusätzlich die gleiche Krümmung wie f (x) im Punkt x0 . Hieraus lässt sich eine Formel für das n-te Näherungspolynom, das sogenannte Taylorpolynom n-ten Grades entwickeln. Modellierung und Simulation Taylorpolynom Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Satz (1.5.1) (Satz von Taylor 1685 - 1731) Gegeben sei eine in x0 ∈ D (n + 1)-mal stetig differenzierbare Funktion f (x). Dann gilt die Taylor-Formel: Splines (pn (x) =)f (x) = f (x0 ) + f 0 (x0 )(x − x0 ) + . . . 1 . . . + f (n) (x0 )(x − x0 )n + Rn (x) n! mit dem Restglied Rn (x) = 1 f (n+1) (ζ)(x − x0 )n+1 (n + 1)! und ζ einem Zwischenwert zwischen x und x0 . mit x ∈ D Modellierung und Simulation Bemerkungen zur Taylorformel Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem der Wert von ζ ist nicht näher bekannt Interpolationspolynom Taylorreihen Splines das Restglied Rn (x) gibt die Abweichung zwischen der Nährungsfunktion pn (x) und der Funktion f (x) an; d.h. Rn (x) ist ein Maß für den Fehler für Rn (x) → 0 erhält man die sogenannte Taylorreihe für die Funktion f (x) im Entwicklungspunkt x0 . Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Beispiel Gegeben ist die Funktion f (x) = ex . Gesucht ist die Taylorentwicklung im Punkt x0 = 0. Zur Bestimmung der Taylorreihe wird der Funktionswert f (x0 ) und die Werte der Ableitungen f 0 (x0 ) = ex , f 00 (x0 ) = ex , . . . im Punkt x0 benötigt. Mit f (0) = 1, f 0 (0) = 1, . . . , f (n) (0) = 1 folgt f (x) = 1 + x + ⇒ ex = 1 2 1 1 x + x3 + . . . + xn + . . . 2! 3! n! ∞ X 1 n x n! n=0 Taylorreihe der Funktion ex für alle x ∈ R Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Beispiel (fortgesetzt) Modellierung und Simulation Britta Nestler Beispiel (fortgesetzt) Approximation mit Polynomen Polynome An der Stelle x = 1 ergibt sich die Eulersche Zahl e. Einsetzen in die Taylorformel für f (x) = ex liefert: Teilbarkeit durch einen Linearfaktor 1 1 e1 ∼ = pn (1) = 1 + 1 + 1 + . . . + 1n 2! n! Nullstellenproblem Interpolationspolynom Taylorreihen Splines Mit n = 9: e ∼ = 1 9 X 1 = 2.7182815 n! n=0 Bemerkung: Für eine Genauigkeit von 6 Dezimalstellen werden nur neun Summationsglieder benötigt. Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Beispiel Gegeben ist die Funktion f (x) = sin x. Gesucht ist die Taylorentwicklung im Punkt x0 = 0. Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Die Ableitungen von f (x) = sin x sind: Taylorreihen Splines f 0 (x) = cos x, f 000 (x) = − cos x, f 00 (x) = − sin x, f (4) (x) = sin x, ... Damit ergeben sich an der Stelle x0 = 0 die Werte: f 0 (0) = 1, f 00 (0) = 0, f 000 (0) = −1, f (4) (0) = 0, . . . Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Beispiel (fortgesetzt) Kürzer formuliert: f (2n) (0) = 0 und f (2n+1) (0) = (−1)n Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Daraus ergibt sich für die Funktion f (x) = sin x folgende Taylorreihe f (x) = x − 1 3 1 1 x + x5 − x7 + . . . − . . . 3! 5! 7! und in Summenschreibweise ∞ X (−1)n 2n+1 sin x = x (2n + 1)! n=0 Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Splines - stückweise definierte Polynome Eigenschaft der Interpolationspolynome: Je mehr Messdaten vorhanden sind, umso höher ist der Grad des interpolierenden Polynoms. Daher ist es bei großen Datensätzen in der Praxis nicht möglich, diese beliebig genau durch eine einzelne Funktion f (x) zu approximieren. Nullstellenproblem Interpolationspolynom Taylorreihen Splines Alternative: Die Funktion f (x) wird durch stückweise definierte Polynome niedrigen Grades, sogenannte Splines definiert. Vorgehen: Die Funktion f (x) soll in einem Intervall [a, b] bestimmt werden. Dazu wird das Intervall [a, b] in n Teilintervalle [xi , xi+1 ] unterteilt mit a = x0 < x1 < . . . < xn = b Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Dann definieren wir eine Funktion g(x), die sich in jedem Teilinterwall [xi , xi+1 ] aus Polynomausdrücken zusammensetzt. g(x) ist eine stückweise definierte Polynomfunktion. Beispiel Modellierung und Simulation Quadratische Splines Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Beispiel Approximation von Messwerten durch stückweise quadratische Polynome: Gegeben ist ein Intervall I = [0, 1] und die Wertetabelle Taylorreihen x f (x) Splines 0 1 1 6 1 3 1 2 2 3 5 6 3 2 1 0 2 1 1 Lösung −54x2 + 21x + 1 −6x + 4 g(x) = −54x2 + 93x − 38 0 ≤ x ≤ 13 1 2 3 ≤x≤ 3 2 3 ≤x≤1 g(x) ist eine stückweise definierte Funktion mit g(xi ) = f (xi ). Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Lösung (fortgesetzt) −54x2 + 21x + 1 −6x + 4 g(x) = −54x2 + 93x − 38 0 ≤ x ≤ 13 1 2 3 ≤x≤ 3 2 3 ≤x≤1 Modellierung und Simulation Problem: g(x) ist nicht überall differenzierbar an den Schnittstellen. Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines ⇒ Splines: Im gesamten Intervall differenzierbare, stückweise definierte Funktion. Beispiel: Herleitung quadratischer Splines Vorgehensweise zur Bestimmung quadratischer Splines am Beispiel für n = 4 Messpunkte. Es gibt drei Teilintervalle Ii = [xi , xi+1 ], i = 1, 2, 3 und entsprechend drei quadratische Funktionen gi (x) = ai2 x2 + ai1 x + ai0 , i = 1, 2, 3. Gesucht ist eine Funktion g(x) mit g(x) = gi (x) für x ∈ Ii , i = 1, 2, 3. Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Beispiel: Herleitung quadratischer Splines (fortgesetzt) Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Zur Bestimmung von g(x) müssen die Funktionen gi (x), i = 1, 2, 3 definiert werden; d.h. es müssen die neun Koeffizienten a12 , a11 , a10 , a22 , a21 , a20 , a32 , a31 , a30 bestimmt werden. Hierzu sind 9 Bedingungen erforderlich: 1. Stetigkeit von g(x) an den Knotenpunkten: Taylorreihen Splines g1 (x1 ) = f1 , g2 (x2 ) = f2 , g3 (x3 ) = f3 g1 (x2 ) = f2 , g2 (x3 ) = f3 , g3 (x4 ) = f4 2. Differenzierbarkeit von g(x) an den Knotenpunkten: g10 (x2 ) = g20 (x2 ) g20 (x3 ) = g30 (x3 ) 3. Zusätzliche 9. Bedingung, die vorgegeben ist: z.B. g10 (x1 ) = c1 mit c1 ≈ f 0 (x1 ) (Approximation) =⇒ g(x) festgelegt. Modellierung und Simulation Allgemeiner: Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem n Knoten ⇒ n − 1 Intervalle und n − 1 Parabeln gi (x) Bedingungen: 1. Stetigkeit: Interpolationspolynom Taylorreihen Splines gi (xi ) = fi , i = 1, . . . , n − 1 gi (xi+1 ) = fi+1 , i = 1, . . . , n − 1 2. Differenzierbarkeit: 0 gi0 (xi+1 ) = gi+1 (xi+1 ), i = 1, . . . , n − 2 ⇒ Das sind 3n − 4 = (n − 1) + (n − 1) + (n − 2) lineare Gleichungen für die Bestimmung der 3n − 3 unbekannten Koeffizienten der Polynome g1 (x), . . . , gn−1 (x). Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem 3. Zusätzliche Bedingung: Interpolationspolynom Taylorreihen Splines g 0 (x1 ) = c1 Zu lösen ist ein System aus 3n − 3 linearen Gleichungen. Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Beispiel Gegeben sind folgende Messpunkte x f (x) 1 2 2 3 3 5 Splines und die Nebenbedingung g10 (1) = 0. Gesucht ist die quadratische Spline-Funktion: g1 (x) = a12 x2 + a11 x + a10 1≤x≤2 g(x) = g2 (x) = a22 x2 + a21 x + a20 2≤x≤3 Modellierung und Simulation Beispiel (fortgesetzt) Britta Nestler Quadratische Spline-Funktion anschaulich: Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Lösung Es werden die Ableitungen g10 (x) und g20 (x) benötigt: g10 (x) = 2a12 x + a11 und g20 (x) = 2a22 x + a21 1. Stetigkeit: g1 (1) = 2 g1 (2) = 3 g2 (2) = 3 g2 (3) = 5 2. Differenzierbarkeit: g10 (2) = g20 (2) 3. Zusätzliche Bedingung: g10 (1) = 0 Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Lösung (fortgesetzt) Aus drei der Bedingungen kann ein Gleichungssystem für die Koeffizienten a12 , a11 und a10 der Funktion g1 (x) aufgestellt werden. a12 + a11 + a10 = 2 4a12 + 2a11 + a10 = 3 2a12 + a11 = 0 Splines Mit dem Gaußalgorithmus: 1 1 1 2 4 2 1 3 2 1 0 0 .. .. . . ⇒ a10 = 3, a11 = −2, und a12 = 1 ⇒ g1 (x) = x2 − 2x + 3 Modellierung und Simulation Britta Nestler Approximation mit Polynomen Lösung (fortgesetzt) Aus den übrigen drei Bedingungen kann ein Gleichungssystem für die Koeffizienten a22 , a21 und a20 der Funktion g2 (x) aufgestellt werden. Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines 4a22 + 2a21 + a20 = 3 9a22 + 3a21 + a20 = 5 4a22 + a21 = 2 Mit dem Gaußalgorithmus: 4 2 1 3 9 3 1 5 4 1 0 2 .. .. . . ⇒ a20 = −1, a21 = 2, und a22 = 0 ⇒ g2 (x) = 2x − 1 Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Kubische Splines Bemerkung: Die quadratischen Splines besitzen an den Punkten, an denen die Teilintervalle zusammenstoßen, im allgemeinen keine zweite Ableitung. Nullstellenproblem Interpolationspolynom Taylorreihen Splines Hierzu benötigt man Polynome dritten Grades, sogenannte kubische Splines. Diese sind auf dem ganzen Intervall zweimal stetig differenzierbar. Vorgehensweise: analog wie im Fall der quadratischen Splines, d.h. für die Koeffizienten der kubischen Polynome wird ein Gleichungssystem aufgestellt. Alternative: Die gesuchte Funktion wird als Linearkombination aus kubischen Basis-Splines (B-Splines) ausgedrückt. Modellierung und Simulation Britta Nestler Approximation mit Polynomen Kubische Splines Kubische Splines finden unter anderem in der graphischen Datenverarbeitung Einsatz, da sie vom Menschen subjektiv als glatt empfunden werden. Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Computermodell eines menschlichen Kopfes Modellierung und Simulation Kubische Splines Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Gegeben sind n Knoten x1 , . . . , xn . Ein kubischer Spline ist eine glatte Kurve, die durch die gegebenen Punkte verläuft und in jedem Teilstück durch eine kubische Parabel Taylorreihen Splines gi (x) = ai3 x3 + ai2 x2 + ai1 x + ai0 mit geeigneten Koeffizienten ai3 , ai2 , ai1 und ai0 definiert ist. Zu jedem Abschnitt gibt es also 4 Unbekannte. Bei n − 1 Abschnitten (d.h. n Knoten) müssen 4(n − 1) Unbekannte durch Lösen eines Gleichungssystems bestimmt werden. Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Vorgehensweise: An den Knoten werden folgende Bedingungen formuliert: die Funktionswerte sowie die Werte der ersten und zweiten Ableitungen der angrenzenden Teilkurven müssen übereinstimmen. Bedingungen: Stetigkeit: Interpolationspolynom Taylorreihen Splines gi (xi ) = fi , i = 1, . . . , n − 1 gi (xi+1 ) = fi+1 , i = 1, . . . , n − 1 Differenzierbarkeit 1. Ableitung: Gleiche Steigung 0 (xi+1 ), gi0 (xi+1 ) = gi+1 i = 1, . . . , n − 2 Differenzierbarkeit 2. Ableitung: Gleiche Krümmung 00 gi00 (xi+1 ) = gi+1 (xi+1 ), i = 1, . . . , n − 2 Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen ⇒ Das sind (4n − 6) = (n − 1) + (n − 1) + (n − 2) + (n − 2) lineare Gleichungen für die Bestimmung der (4n − 4) unbekannten Koeffizienten der kubischen Polynome g1 (x), . . . , gn−1 (x). Splines Also ist die Interpolationsaufgabe für kubische Splines unterbestimmt, so dass zwei zusätzliche Freiheitsgrade zur Verfügung stehen. Durch weitere Zusatzbedingungen lässt sich die Eindeutigkeit herstellen. Modellierung und Simulation Randbedingungen für kubische Splines Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Natürliche Randbedingungen: Die zweite Ableitung des Splines am Anfangs- und Endpunkt wird Null gesetzt. Das bewirkt, dass der Spline eine minimale Gesamtkrümmung hat. Taylorreihen Splines g100 (x1 ) = 0 00 und gn−1 (xn ) = 0 Vorgabe von Randableitungen: Die erste Ableitung am Anfangs- und Endpunkt wird vorgegeben. g10 (x1 ) = cl 0 und gn−1 (xn ) = cr Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Spline-Interpolation Erstellen einer Geschwindigkeitskurve: Gemessen sind die Zeiten eines Sprintläufers an verschiedenen charakteristischen Messpunkten, z.B. nach 5m, 15m, 30m, 75m, 85m und 100m. Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Strecke in m 5 15 30 75 85 100 Zeit in sec 1,5 2,5 4,6 9,5 11 13,5 Durch eine Spline-Interpolation läßt sich eine Geschwindigkeitskurve aufstellen und berechnen, nach wieviel Sekunden der Läufer z.B. die 50-Meter-Marke erreicht hat. Modellierung und Simulation Britta Nestler Approximation mit Polynomen Spline-Interpolation (fortgesetzt) Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Beispielprogramm Modellierung und Simulation Britta Nestler Approximation mit Polynomen Beispiel Gegeben sind folgende Messpunkte Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom x f (x) 0 4 1 1 2 2 Taylorreihen Splines und es soll die natürliche Randbedingung angesetzt werden, 00 (x ) = 0. d.h. g100 (x1 ) = 0 und gn−1 n Gesucht ist die kubische Spline-Funktion: g1 (x) = a13 x3 + a12 x2 + a11 x + a10 g(x) = g2 (x) = a23 x3 + a22 x2 + a21 x + a20 0≤x≤1 1≤x≤2 Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Lösung Es werden die Ableitungen g10 (x), g20 (x) und g100 (x), g200 (x) benötigt: g10 (x) = 3a13 x2 + 2a12 x + a11 , g100 (x) = 6a13 x + 2a12 g20 (x) = 3a23 x2 + 2a22 x + a21 , g200 (x) = 6a23 x + 2a22 Interpolationspolynom Taylorreihen Splines 1. Stetigkeit: g1 (0) = 4 g1 (1) = 1 g2 (1) = 1 g2 (2) = 2 2. Differenzierbarkeit: g10 (1) = g20 (1) und g100 (1) = g200 (1) 3. Natürliche Randbedingungen: g100 (0) = 0 und g200 (2) = 0 Modellierung und Simulation Britta Nestler Approximation mit Polynomen Lösung (fortgesetzt) Aus diesen 8 Bedingungen kann ein Gleichungssystem für die 8 Koeffizienten a13 , a12 , . . . , a21 , a20 der beiden kubischen Funktionen g1 (x) und g2 (x) aufgestellt werden: Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines 0 1 0 0 3 6 0 0 0 1 0 0 2 2 1 0 .. . 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 8 −3 −6 0 12 .. . 0 0 1 4 −2 −2 0 2 0 0 1 2 −1 0 0 0 0 0 1 1 0 0 0 0 .. . 4 1 1 2 0 0 0 0 .. . ⇒ a13 = 1, a12 = 0, a11 = −4, a10 = 4 und a23 = −1, a22 = 6, a21 = −10, a20 = 6 ⇒ g1 (x) = x3 − 4x + 4 und g2 (x) = −x3 + 6x2 − 10x + 6. Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Alternative: Kubische Basis-Splines (B-Splines) Eine kubische Spline-Funktion wird als Linearkombination der Basis-Splines dargestellt. Definition Seien x1 , . . . , xn äquidistante Punkte mit Abstand h. Dann ist der um xi zentrierte kubische B-Spline Bi definiert durch: Taylorreihen Splines 1 (x − xi−2 )3 , xi−2 ≤ x ≤ xi−1 4h3 1 3 3 3 + (x − xi−1 ) + 2 (x − xi−1 )2 − 3 (x − xi−1 )3 , xi−1 ≤ x ≤ xi 4 4h 4h 4h 3 3 3 1 + (xi+1 − x) + 2 (xi+1 − x)2 − 3 (xi+1 − x)3 , xi ≤ x ≤ xi+1 4 4h 4h 4h 1 (xi+2 − x)3 , xi+1 ≤ x ≤ xi+2 4h3 0, sonst Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Darstellung des kubischen B-Splines Modellierung und Simulation Kubische B-Splines Britta Nestler Eigenschaften: Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Bi (xi ) = 1, Bi (xi±1 ) = 1 4 und Bi (xi±2 ) = 0 Nullstellenproblem Interpolationspolynom Taylorreihen Vorgehensweise: Splines Gesucht ist ein kubischer Spline c(x), der durch die gegebenen Knoten verläuft, d.h. c(xi ) = fi , i = 1, . . . , n Lösungsansatz: c(x) wird als Linearkombination der B-Splines dargestellt n X c(x) = αi Bi . i=1 Modellierung und Simulation Kubische B-Splines (fortgesetzt) Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Da Bi (xj ) = 0 für |i − j| ≥ 2, führen die Bedingungen c(xi ) = fi , i = 1, . . . , n auf: Nullstellenproblem Interpolationspolynom Taylorreihen Splines α1 B1 (x1 ) + α2 B2 (x1 ) = f1 α1 B1 (x2 ) + α2 B2 (x2 ) + α3 B3 (x2 ) = f2 .. .. . . αn−2 Bn−2 (xn−1 ) + αn−1 Bn−1 (xn−1 ) + αn Bn (xn−1 ) = fn−1 αn−1 Bn−1 (xn ) + αn Bn (xn ) = fn Dies ist ein lineares Gleichungssystem zur Berechnung der Linearfaktoren αi . Modellierung und Simulation Britta Nestler Approximation mit Polynomen Polynome Teilbarkeit durch einen Linearfaktor Nullstellenproblem Interpolationspolynom Taylorreihen Splines Mit Bi (xi ) = 1, und Bi (xi±1 ) = 41 ergibt sich die Matrixschreibweise: 4 1 f1 α1 . . α2 f2 . 1 1 4 . = . . . 4 .. .. 1 .. .. fn αn 1 4 Dieses System besitzt eine eindeutige Lösung für die Koeffizienten αi . Somit gibt es eine Lösung für die kubische Splinefunktion c(x) mit c(xi ) = fi . c(x) ist ein kubisches Polynom, das es sich als Linearkombination kubischer Funktionen ergibt.
© Copyright 2024 ExpyDoc
