Universität Stuttgart Wissensverarbeitung und Numerik I nstitut für K ernenergetik und E nergiesysteme Numerik partieller Differentialgleichungen, SS 03Teil

Universität Stuttgart W

isse

nsv

erar

be

itu

ng

un

d N

um

erik

Institut für Kernenergetikund Energiesysteme

Numerik partieller Differentialgleichungen, SS 03 Teil 1: V2 Diskretisierung

V2: Diskretisierung von Funktionen

Teil 1: Grundverfahren der Numerik

V2 Diskretisierung von Funktionen

InhaltLagrange PolynomeFunktionsentwicklungenStatistische Approximation

Experimente:Lagrange Interpolation


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Das sollten Sie heute lernen

Wie diskretisieren wir Funktionen Was ist ein Lagrange Polynom der Ordnung n Was ist eine Taylorreihe Was ist der Zentrale Grenzwertsatz Welche Fehler macht man bei der Diskretisierung von Funktionen und

wie kann man sie verringern


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Neben der diskreten Darstellung der Zahlen interessieren in der Numerik vor allem die diskrete Darstellung von Verläufen (Funktionen) und der darauf möglichen Operationen (vor allem Integration und Differentiation).

Drei Möglichkeiten der Diskretisierung von Verläufen sollen im Rahmen dieser Vorlesung behandelt werden. Ausgang ist

y = f(x)

x steht für die unabhängigen Variablen,

y steht für die abhängigen Variablen,

f gibt den Verlauf an und wird im Folgenden als Operation auf x gedeutet, die die Gerade y ergibt.

a) Diskretisierung der unabhängigen Variablen

wird durch Werte yi = f(xi) dargestellt.

Für weitere Operationen kann zwischen den Werten yi interpoliert werden. Als Interpolationsfunktion werden häufig Lagrange-Polynome verwendet.

yyixx

~

y~

Diskretisierung von Funkionen -1


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Diskretisierung von Funktionen -2

b) Diskretisierung der abhängigen Variablen

Wählbar sind die Entwicklungsfunktionen Ni(x), die Bedeutung der Entwicklungskoeffizienten ai und die Art der Näherung von

c) Diskretisierung durch statistische Methode

wird über Werte beschrieben, wo xi zufällig bestimmt und nach verteilt sind.

xiN

i iayy ~

xxfxf *

y~ xf * x


isse

nsv

erar

be

itu

ng

un

d N

um

erik



1. Festlegung des Approximationsbereichs

xa x xb

2. Festlegung der Stützstellen

a) Einschluss der Ränder x1 = xa, xn+1 = xb

b) Gebietsmitte

3. Berechnung der Werte der abhängigen Variablen

yi = y (xi)

4. Interpretation

a) Wert gültig im Bereich (Basisgebiet) um Stützstellen

b) Werte interpolieren mit Lagrange-Polynomen

b1) Polynom durch alle Punkte (wenig Stützstellen, hohe Interpolationsordnung)

b2) stückweise Näherung (viele Stützstellen, mehrere Polynome niederer Ordnung).

Diskretisierung der unabhängigen Variablen- Näherung von Funktionen


isse

nsv

erar

be

itu

ng

un

d N

um

erik



y wird durch zwei Punkte xo und x1 beschrieben. ist eine Gerade durch die Punkte (xo, yo) und (x1, y1)

Fasst man die Glieder mit yo und y1 zusammen, so gilt

Die Ausdrücke vor den Werten yo und y1 sind Funktionen von x. Wir bezeichnen sie mit

Offensichtlich gilt

und

1001

01

0

0

~ xxxyyxx

xxyy

1

01

0

0

01

1~ yxx

xxy

xx

xxy

xx 1

1

1

0 und

y~

xyyi

ii

11

0

~

100

1

01

1

0

01

11

0

xundxmitxx

xx

010

1

11

1

1

01

01

1

xundxmitxx

xx

Lineare Interpolation -1


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Ihre allgemeine Form lautet:

Für n = 3

Lagrange Polynome -1

))...()()...((

))...()()...((

110

110

0 niiiiii

nii

mi

mn

imm

nm xxxxxxxx

xxxxxxxx

xx

xxx


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Lagrange Polynome -2

Mit diesen Interpolationsfunktionen lässt sich eine Funktion y(x) etwa folgendermaßen nähern:

)()3

o ii

(xy(x)y~(x)y xi

x0 x1 x2 x3

xyxy~


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Quadratische Interpolation

x wird durch drei Punkte x0, x1, x2 beschrieben.

Ist eine Parabel durch die Punkte 221100 ,,,,, yxyxyxy~

2210

~ xaxaay Mit

und 22

11

00

~

~

~

yxy

yxy

yxy

können die Koeffizienten a0, a1 und a2 bestimmt werden.


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Quadratische InterpolationDas Ergebnis ist

12

1

02

02

21

2

01

01

20

2

10

10

~

xx

xx

xx

xxy

xx

xx

xx

xxy

xx

xx

xx

xxyy

Die Ausdrücke vor den Werten y0, y1 und y2 sind jetzt ebenfalls Parabeln. Wir bezeichnen sie mit

xxx 22

21

20 ,,

Offensichtlich gilt 100

000

001

2221

220

22

22

112

102

1

2201

200

20

xxx

xxx

xxx

und xyy iii

22

0

~


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Höhere Interpolation

xyy nii

n

i

0

~

xni Heißen Lagrange-Polynome.

Es gilt analog der linearen und der quadratischen Interplation

1

0j

ni x für i j,

für i = j

Ihre allgemeine Form lautet

nk

n

kk

k

kk

k

mk

n

kmm mk

mk xx

xx

xx

xx

xx

xx

xx

xx

xx

xxx

1

1

1

10

0


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Stückweise NäherungHäufig möchte man sich bei der Näherung auf Polynome niederer Ordnung beschränken. Um trotzdem kompliziertere Verläufe darstellen zu können, unterteilt man den Bereich, in dem die Funktion genähert werden soll, in m-Teilbereiche (Basisgebiete, Elemente), für die man je separat eine Näherung bestimmt. Man fordert Stetigkeit der Näherungen an den Anschlussstellen und erreicht das dadurch, dass je eine Stützstelle auf dem Rand liegt. Es gilt dann

xnji

m

j

nj

iiyy

1 0

~

sind die im Teilbereich j gültigen Interpolations- oder Ansatz-Funktionen je der Ordnung nj

Die Näherung heißt stückweise stetig.

xnj

Diskretisierung von x

0

0,2

0,4

0,6

0,8

1

1 3 5 7 9 11 13 15 17 19 21Diskretisierung von y

-0,2

0

0,2

0,4

0,6

0,8

1


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Diskretisierung der abhängigen Variablen

Der im letzten Abschnitt beschriebene Ansatz nähert y so, dass y und an den Knoten übereinstimmen. Für viele Anwendungen sind andere Anpassungen besser. Man erhält sie durch Diskretisierung der abhängigen Variablen

Ni(x) sind bekannte Entwicklungs- oder Basisfunktionen.

ai sind die Entwicklungskoeffizienten. Zu ihrer Bestimmung ist ein Kriterium, das angibt, wie die Näherung erfolgen soll, nötig.

Eine häufig verwendete Anpassungsmethode ist die Methode der gewichteten Residuen. Sie versucht, den Gesamtfehler integral zu minimieren. Dazu führt man Wichtungsfunktionen wi ein und fordert

xNayy ii

n

i

0

y

00

dxxNaywdxyywn

iiijj


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Diskretisierung der abhängigen Variablen

Die Zahl der Wichtungsfunktionen entspricht dabei der Zahl der anzupassenden Unbekannten ai. j läuft also wie i von 0 bis n.

Mit dieser Beziehung erhält man durch Einsetzen der n+1 Wichtungsfunktionen w j gerade n+1-Gleichungen. Aus diesen können die Entwicklungskoeffizienten ai bestimmt werden. Voraussetzung dafür ist, dass die Wichtungsfunktionen linear unabhängig sind, d.h. nicht durch lineare Transformationen ineinander überführt werden können.

Das Gleichungssystem hat folgende Form (wir verwenden die Abkürzung)

ywNwaNwaNwa

ywNwaNwaNwa

ywNwaNwaNwa

nnnnnn

nn

nn

1100

11111010

00101000

........

jjij NwdxNw


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispiel: Diskretisierung der Unabhängigen -1 Beispiel

Der Unterschied zwischen Näherung von unabhängigen und abhängigen Variablen soll anhand eines einfachen Beispiels verdeutlicht werden.

Es sei

Zunächst diskretisieren wir x.

2 Werte mit linearer Interpolation.nähernzu103 xinxy

xy

xxxx

yy

xx

11

10

10

10

1

10

10

3xy


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispiel: Diskretisierung der Unabhängigen -2

Jetzt dasselbe nach Näherung über y. Wir wählen dabei als Basisfunktionen die Lagrange-Polynome, die auch schon den Näherungen a verwendet wurden. Als Wichtugnsfunktionen sollen ebenfalls die Lagrange-Polynome verwendet werden. Dann gilt

xwxw

xx

aymit

xyy ii

i

10

11

10

11

11

0

1

1

tenKoeffizienen bestimmendzu den


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Methode der gewichteten Residuen

Über die Methode der gewichteten Residuen erhalten wir folgendes Gleichungssystem:

5

1

3

1

6

120

1

6

1

3

1

1

111

10

10

1

0

41

9

21

1

00

1

0

31

01

1

0

20

yy

yy

oder

dxxdxxydxxxy

dxxxdxxxydxxy


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Diskretisierung der Unabhängigen: Ergebnis

Die Lösung ist

Damit wird

2,09,0

7,012,0

7,02,0 10

x

xxy

yy

Aus dem Beispiel sieht man:

• Die Galerkin-Methode führt auf symmetrische Gleichungssysteme zur Bestimmung der ai

• Lokale Werte können extrem falsch sein (z.B. negative Temperaturen). Im Beispiel für x < 2/a.

• Konvergenz erfolgt im Sinne der Wichtung.

• Es gibt Punkte (Gauß-Punkte), an denen Funktion und Näherung exakt übereinstimmen.

Im Beispiel 2 Punkte, die in 0 x 1 die Gleichung x3 = 0,9x - 0,2 erfüllen.


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Taylor-Reihe als alternative Entwicklungsfunktion

Folgende Festlegungen führen zur Taylor-Entwicklung: Entwicklungsfunktionen Polynome von (x - xo)

Entwicklungkoeffizienten Wert und Ableitung an Stelle x0:

xn

n

n

x

x

xfdx

d

na

xfdx

da

xfdx

da

xfa

/)(!

1

..........

/)(!2

1

/)(

)(

2

2

2

1

00

• Art der Näherung y und stimmen an der Stelle x0 in Wert und allen Ableitungen bis zur Ordnung n überein.

y~


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Taylor-Reihenentwicklung -2

Ergebnis der Näherung

• Verstümmelungsfehler gleich erstes vernachlässigtes Glied

• Konvergenz

xoxf

ndx

nd

n

noxx

xoxf

dx

dxxxfxyxy /)(

!

)(.../)(

!10)

0()(~)(

1)(0ˆ/)(1

1

)!1(

1)( noxx

oxxf

ndx

nd

n

noxx

)1(0ˆ)1(0ˆ1)(0

nhnxn

oxx


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Statistische Approximation

Eine dritte Methode, um Verläufe zu diskretisieren, kennen wir aus der Messtechnik. Dort werden Verläufe mit Hilfe von Messpunkten dargestellt. Dabei gibt es zwei Grenzfälle:

a) Die Messpunkte sind zufällig (Stichprobe), aber der Messwert ist exakt. Dies entspricht einer zufälligen Diskretisierung der unabhängigen Variablen.

b) Die Messpunkte sind vorgebbar, aber der Messwert ist mit großer Unsicherheit behaftet (Messung mit Messfehler). Jetzt sind die Werte der abhängigen Variablen zufällig.

Um diese Technik auch auf dem Rechner verfügbar zu haben, ist es nötig, zufällige Zahlen zu erzeugen. Dies geschieht durch spezielle Funktionen (Zufallszahlgeneratoren). Diese Funktionen liefern in der Regel Zufallszahlen, die in einem Intervall (0,1) gleichverteilt sind, d.h. die auftretenden Zahlenwerte können alle aus diesem Intervall darstellbaren Zahlen mit gleicher Wahrscheinlichkeit annehmen. Abweichungen von dieser Aussage dürfen im Rahmen der Verwendung der Zufallszahlen nicht nachweisbar sein.

Um nun eine Funktion f (x) im Intervall (a, b) zu nähern, wird f (x) aufgespalten in

f x) = fx (x) • (x)Die Näherung von f (x) erfolgt dann durch n Realisationen x i , wo die xi aus der Verteilung (x) stammen und jedem xi ein Wert fx (xi) zugeordnet ist. Ist (x) eine Gleichverteilung, so gilt (x) = 1 / (b - a) und fX (x) = (b - a) • f (x).


isse

nsv

erar

be

itu

ng

un

d N

um

erik




Kann man direkt von f (x) Zufallszahlen ziehen, ist also f (x) - evtl. nach einer Normierung - eine verfügbare Dichtefunktion, so gilt:

(x) = f (x)

fx (x) = 1

Allen Beiträgen xi wird also derselbe Wert zugeordnet.

Eine Interpolation zwischen den zufälligen Werten kann nicht direkt erfolgen. Operationen werden über das Gesetz der großen Zahlen realisiert. Dies wird später weiter beschrieben.Näherungsweise kann man einen Punkteschwarm mit der Methode der kleinsten Fehlerquadrate in einen Verlauf (Regression) umsetzen. Dabei hat man aus Messungen oder einem statistischen Computerexperiment Wertepaare x i, yi erhalten. Sie sollen durch eine Funktion , in der die Parameter a0 bis an noch zu bestimmen sind

möglichst gut approximiert werden. Dies erreicht man etwa, indem man die quadratische Abweichung Q zwischen Messwerten yi und Näherung zum Minimum macht:

naaaxyy ,,,, 10 y

y Qn

i iy

naa

ixyMin

0

2,,0

,


isse

nsv

erar

be

itu

ng

un

d N

um

erik




Wie aus der Analysis bekannt, wird ein Extremwert berechnet, indem man die 1. Ableitung = 0 setzt. Damit kann man für

genau n+1-Gleichungen folgender Art bilden:

Dies entspricht der Methode der gewichteten Residuen in der Galerkin-Formulierung, wenn wie dort gilt:

nj 0

0,,;,,2 00

0

nij

n

iini

j

aaxda

ydyaaxy

da

dQ

n

iii xNay

0


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Diese Fragen sollten Sie beantworten können

Geben Sie für eine Funktion f(x) die zugehörige Taylor-Reihe an

Empfehlen Sie einen Ansatz zur Näherung einer Funktion f(x), wenn deren Verlauf optimal beschrieben werden soll. Wie ändert sich Ihre Empfehlung, wenn es sich bei der zu nähernden Funktion im Näherungsintervall um ein Polynom der Ordnung 2 handelt

Was ist zu tun, wenn die Funktion 2 unabhängige Variablen hat

Geben Sie Kriterien für die Auswahl einer Diskretisierungsvorschrift an

Documents

Universität Stuttgart Wissensverarbeitung und Numerik I nstitut für K ernenergetik und E nergiesysteme Numerik partieller Differentialgleichungen, SS 03Teil