Interpolation, numerische Integration - 8. Vorlesung ...institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli08s14.pdf · Rechenverfahren zur polynomialen Interpolation •

Interpolation, numerische Integration

8. Vorlesung170 004 Numerische Methoden I

Clemens Brand und Erika Hausenblas

Montanuniversität Leoben

8. Mai 2014

Gliederung

1 InterpolationpolynomialSpline

2 Numerische IntegrationKlassisch: Newton-CotesWeitere Quadraturformeln

InterpolationDefinition der Aufgabenstellung

Gegeben:

Datenpunkte

Gesucht:

• Eine Funktion, die durch die gegebenen Datenpunkte verläuft.

• Ein Wert zwischen den Datenpunkten

• Trend über den gegebenen Datenbereich hinaus: Extrapolation

Anwendung:

Zwischenwerte in Tabellen, „glatte“ Kurven für Graphik. . .

C.B & E.H. (MUL) Interpolation, numerische Integration 20.III.2014 3 / 23

Beispiel: Interpolation in Tabellen

Spezifische Wärmekapazitätvon kohlenstoffarmem Stahl inJ/kg K für 20 C ≤ T ≤ 700,C

T cp

20 447173 500200 509400 595543 700600 763626 800700 909

0 100 200 300 400 500 600 700 800 900400

500

600

700

800

900

1000

1100

1200

1300

Die Abbildung illustriert stückweise lineare Interpolation zwischen denStützstellen und Extrapolation bis 900 C.

Polynomiale InterpolationDie einfachsten Interpolations-Funktionen sind Polynome...

Durch zwei Punkte der xy -Ebene geht genau eine Gerade. Durch dreibeliebige Punkte lässt sich eindeutig eine Parabel legen. Durch n + 1Punkte ist ein Polynom n-ten Grades eindeutig bestimmt. (Ausnahme,wenn x-Werte zusammenfallen)

Aufgabenstellung:

• gegeben n + 1 Wertepaare (xi , yi ), i = 0, . . . , n, wobei die xi

paarweise verschieden sind.

• gesucht ist das eindeutig bestimmte Polynom n-ten Grades p, dasdurch die gegebenen Datenpunkte verläuft:

p(xi ) = yi für i = 0, . . . , n

.


Interpolationspolynome hohen Grades sind

ungeeignet!

Durch die achtDatenpunkte lässt sich einPolynom siebten Gradesexakt durchlegen.

Aber:Polynome so hohen Gradesneigen zu Oszillationen undzu extrem unrealistischerExtrapolation

0 100 200 300 400 500 600 700 800 900400

500

600

700

800

900

1000

DatenpunkteInterpolationspolynom

Rechenverfahren zur polynomialen Interpolation

• Alle Verfahren für polynomiale Regression liefern für entsprechendhohen Polynomgrad das Interpolationspolynom. Rechenaufwand isthöher als bei den folgenden Methoden.

• Lagrangesches Interpolationspolynom: Eine Formel, die das Polynomdirekt hinschreibt.

• Newtonsches Interpolationspolynom: besonders rechengünstig.

• Es gibt noch einige andere Rechenschemen (im Skript:Neville-Verfahren; wir lassen es heuer aus)

Trotz unterschiedlicher Namen und Schreibweisen liefern alle Verfahrendasselbe (eindeutig bestimmte) Polynom.


Lagrangesche Interpolationsformel

Das Interpolationspolynom durch die n + 1 Wertepaare(xi , yi ), i = 0, . . . , n ist gegeben durch

p(x) = L0(x)y0 + L1(x)y1 + ...+ Ln(x)yn,

wobei

Li(x) =(x − x0)(x − x1)...(x − xi−1)(x − xi+1)...(x − xn)

(xi − x0)(xi − x1)...(xi − xi−1)(xi − xi+1)...(xi − xn)

Es ist für die rechnerische Durchführung nicht ratsam, nach Einsetzen der Datenpunkte

die Li (x) durch symbolisches Ausmultiplizieren noch weiter zu „vereinfachen“. Die

x-Werte direkt einsetzen!


Weitere InterpolationsverfahrenNicht alle Funktionen lassen sich vorteilhaft durch Polynome interpolieren

Andere wichtige Verfahren sind

• Rationale Interpolation

• Spline-Interpolation (Kubisch, Bezier,...)

• Stückweise Hermite-Interpolation (MATLAB pchip)

• Trigonometrische Interpolation

• Interpolation in zwei oder mehr Dimensionen


Biegsame Latte als Kurvenlineal

Ursprünglich im Schiffsbau verwendet, heißt Straklatte, englisch Spline.Funktionen, die das Verhalten biegsamer Latten nachbilden: Natürlichekubische Spline-Funktionen.


Natürlicher kubischer Spline

Eine dünne, an einzelnen Punkten festgehaltene Latte biegt sich inder Form eines kubischen Splines

1 2 3 4

0.1

0.2

0.3

0.4

Natürlicher kubischer Spline

Ein kubischer Spline s(x) durch die n + 1 Wertepaare (xi , yi ),i = 0, . . . , n ist folgendermaßen charakterisiert:

• In den einzelnen Intervallen (xi−1, xi ) ist s(x) jeweils ein kubischesPolynom

• An den Intervallgrenzen stimmen die Funktionswerte, die ersten unddie zweiten Ableitungen rechts- und linksseitig überein.

• Zusatzbedingung: zweite Ableitung an den Rändern wird Null gesetzt.


Interpolation in Matlab: spline und pchipx = -3:3;

y = [-1 -1 -1 0 1 1 1];

t = -3:.01:3;

p = pchip(x,y,t);

s = spline(x,y,t);

plot(x,y,’o’,t,p,’-’,

t,s,’-.’)

−3 −2 −1 0 1 2 3−1.5

−1

−0.5

0

0.5

1

1.5

Datenpchipspline

MATLAB bietet verschiedene stückweise kubische Interpolationsverfahren.spline ist für glatte Daten genauer.pchip überschwingt nicht und neigt weniger zu Oszillationen.

Beispiel: cp-Daten mit spline und pchip

Innerhalb desDatenbereiches stimmenbeide Verfahren sichtlichüberein.

Extrapolation ist einwesentlich riskanteresGeschäft. . .. . . wie man sieht: hier sindweitere Datenpunkteeingetragen. Keine derbeiden Methodenextrapoliert dentatsächlichen Verlauf derspez. Wärme korrekt.

−200 0 200 400 600 800 1000300

400

500

600

700

800

900

1000

1100

1200

1300

Runge-PhänomenInterpolationspolynome mit äquidistenten Stützstellen konvergieren nicht

x

y

y

Tschebysheff-StützstellenNicht äquidistant, sondern zu den Rändern hin dichter

x

y

y

Optimale Lage der StützstellenProjektion von n gleichmäßig am Halbkreis verteilten Punkten

Bei dieser Wahl der Stützstellen („Tschebysheff-Stützstellen“) ist diemaximale Abweichung Funktion–Polynom am kleinsten

Lage auf Intervall [−1; 1]

xi = cos

(

2i − 1

2nπ

)

für i = 1, . . . , n

InterpolationsverfahrenÜbersicht und Zusammenfassung

• Newton-Polynom: rechengüstig; zusätzliche Datenpunkte lassen sichleicht anfügen

• Lagrange-Polynom: y -Werte lasen sich leicht ändern

• Polynome mit hohem Grad und äquidistanten Stützstellen:Ungeeignet! (Runge-Phänomen).

• Tschebysheff-Stützstellen: optimale Approximation

• Natürliche kubische Splines: meist bessere Anpassung als Polynome.

• Es gibt viele weitere Spline-Varianten

Numerische Integration

Gegeben:

eine Funktion f (x) in einem Intervall a ≤ x ≤ b.

Gesucht:

deren Integral∫

b

a

f (x)dx

Oft lässt sich das Integral nicht durch elementare Funktionen ausdrücken,oder die Funktion selbst ist nur tabellarisch gegeben. −→ Numerische

Verfahren


Integrationsformeln nach Newton-Cotes

Gegeben:

Eine Funktion f (x) in einem Intervall (a, b) durch ihre Werte fi an n + 1äquidistanten Stützstellen,

fi = f (a + ih), mit h =b − a

n, i = 0, . . . , n.

Prinzip:

Interpoliere f (x) durch ein Polynom p(x). Nähere das Integral von f durchdas Integral von p. Die Näherung ist gegeben als gewichtete Summe der fi ,

∫

b

a

f (x)dx ≈ (b − a)n

∑

i=0

αi fi

mit fixen Gewichten αi


Newton-Cotes-FormelnKlassische Beispiele mit Fehlertermen

Trapezregel∫

b

a

f (x)dx =b − a

2(f (a) + f (b)) −

(b−a)3

12f′′(ξ)

Simpson-Regel∫

b

a

f (x)dx =b − a

6

(

f (a) + 4f (a + b

2) + f (b)

)

−

(b−a)5

2880f

IV (ξ)

3/8-Regel („pulcherrima“)

∫

b

a

f (x)dx =b − a

8(f (a) + 3f (a + h) + 3f (a + 2h) + f (b)) −

(b−a)5

6480f

IV (ξ)

Zusammengesetzte N.-C.-FormelnWenn feinere Intervallteilung vorliegt

Achtung bei Intervallbreite h! Es sind n + 1 Datenpunkte, und um einsweniger Intervalle. n= Anzahl Datenpunkte-1, und h = (b − a)/n

Zusammengesetzte Trapezregel∫

b

a

f (x)dx =h

2(f0 + 2f1 + 2f2 + · · · + 2fn−1 + fn) + E

Zusammengesetzte Simpson-Regel

∫

b

a

f (x)dx =h

3(f0 + 4f1 + 2f2 + 4f3 + · · · + 2fn−2 + 4fn−1 + fn) + E

(Nur für gerades n möglich!)


Weitere Quadraturformeln

Gauß-Quadratur, Gauß-Lobatto-Formeln

Nicht äquidistante Stützstellen, dafür höhere Genauigkeit. (TypischeAnwendung: Finite Elemente)

Romberg-Verfahren

berechnet mit zusammengesetzter Trapezregel mehrere Werte zuverschiedenen h und extrapoliert auf h = 0.

MATLAB

bietet zwei Verfahren: quad (adaptive Simpson-Regel) und quadl

(trickreichere Gauß-Lobatto Methode)


Documents

Interpolation, numerische Integration - 8. Vorlesung ...institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli08s14.pdf · Rechenverfahren zur polynomialen Interpolation •