Universität Stuttgart Wissensverarbeitung und Numerik I nstitut für K ernenergetik und E nergiesysteme Numerische Methoden, SS 2003Teil II: Kp. 4 4/1 Diese

4/1

Universität Stuttgart W

isse

nsv

erar

be

itu

ng

un

d N

um

erik

Institut für Kernenergetikund Energiesysteme

Numerische Methoden, SS 2003 Teil II: Kp. 4

Diese Fragen sollten Sie beantworten können

Was ist das Ziel der Vorlesung -

Rechner zur Unterstützung der Berechnung technischer Vorgänge Was ist ein Modell - Abstraktion Was sind die mathematischen Grundbeziehungen technischer Modelle

- Erhaltungsgleichungen in integraler und differenzieller Form Was ist ein Abstrakter Datentyp - Kapselung von Daten Was ist ein Modul - Kapselung von Funktionalitäten Drei Auswirkungen der Endlichkeit von Rechnern

Rundung, Diskretisierung, Abbruch Was bedeuten Kondition, Konsistenz und Konvergenz

Rundungsfehler, Diskretisierungsfehler, Abbruchfehler beherrscht Wie diskretisieren wir Funktionen

4/2


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

4/3


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.

xi

Ni iayy ~

xxfxf *

y~ xf * x

4/4


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Diskretisierung der abhängigen Variablen

Durch die Diskretisierung der Unabhängigen nähert man y so, daß 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

4/5


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Methode der gewichteten Residuen

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 a i 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.

Mit der Abkürzung

hat das Gleichungssystem folgende Form

ywNwaNwaNwa

ywNwaNwaNwa

ywNwaNwaNwa

nnnnnn

nn

nn

1100

11111010

00101000

........

jjij NwdxNw

4/6


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispiel: Näherung von y =x2

6/56/1

4/13/16/1

12/16/13/1

6/1

3/1

11

10

10

10

10

0110

1100

111

010

10

aa

aa

aa

NwNw

NwNw

xx

xx

xundx

4/7


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Stückweise Näherung

Hä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 Anschlußstellen und erreicht das dadurch, daß 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

4/8


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Alternative Wahlen der Entwicklungskoeffizienten

Folgende Wahlen sind besonders häufig:

,

,

,

,

dxxydx

da

dxxya

xxydx

da

xya

i

xi

ii

ii

i

d.h. Lösung an einem Punkt. Dann sind die Basisfunktionen die Lagrange-Funktionen

d.h. Steigung an einem Punkt. Dann sind die Basisfunktionen Polynome (Ableitungen an einer Stelle) oder Hermitesche Funktionen (Ableitungen am linken und rechten Rand).

d.h. mittlere Lösung im Gebiet. Dann sind die Basisfunktionen in der Regel problemabhängige Spezialfunktionen.

d.h. mittlere Steigung (häufig für ein Oberflächenelement definiert).

4/9


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispiel: Taylor-Reihenentwicklung

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~

4/10


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

4/11


isse

nsv

erar

be

itu

ng

un

d N

um

erik



V 4: Nullstellensuche

Teil II: Rechner als endliche Maschine

Kap. 4: Operationen auf diskrete Werte am Beispiel iterativer Verfahren

Inhalt: Nullstellensuche Nichtlineare Gleichungen

Experimente: Bestimmung von x aus x2 - a = 0 nach verschiedenen Verfahren Lösung von x3 = 1 mit verschiedenen Startwerten

4/12


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Das sollten Sie heute lernen

Grundverständnis iterativer Verfahren Umsetzung in ein Programm zur Nullstellensuche für beliebige

Funktionen (Übungen) Schwierigkeiten nichtlinearer Probleme

4/13


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Nullstellensuche

Zu jedem Problem

existiert ein Umkehrproblem

Die Bestimmung des Wertes xp zu einem vorgegebenen Wert yp heißt Nullstellensuche.

Zu lösen ist das Problem

Für komplizierte Verläufe von f(x) kann dies nur näherungsweise geschehen. Folgender Algorithmus hat sich bewährt:

Nähere xp durch

Berechne

Für

sonst

Der Algorithmus heißt Iteration.

xfy xFxyfyfx 11

0pyxfxg

0

0 xxp

np

n

pxFx 1

Ende,1 n

p

n

pxx

1 nn

4/14


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Nullstellensuche -2

Die Iteration wird also abgebrochen, wenn kleiner als eine vorgegebene Schranke ist. Wird diese Schranke unterschritten, so sagt man, die Folge der sei konvergent.

Folgende Fragen sind zu klären:

a) Wie findet man eine passende Iterationsvorschrift?

b) Welche Anfangswerte sind zu wählen?

c) Unter welchen Bedingungen konvergiert die Folge der ?

d) Wie schnell konvergiert die Folge der ?

np

np xx 1

n

px

n

px

n

px

4/15


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispiel: x2 - a = 0 - iterative Lösung

Aufgabe:

Bestimme x so, daß x2 = a erfüllt ist, d.h.

Mögliche Iterationsvorschriften:

02)(2)( axxgapyxxf

xFipx

gipx

ipxg

pxg

ipxi

pxi

pxgausund

ipxgi

pxi

pxi

pxgi

pxgxg

xFipxi

pxai

pxxa

xFipxai

pxax

32

22

101

110.3

)(2

2)(102.2

)(1

/12.1

Das Verfahren 3 heißt Newton Methode

4/16


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispiel: x2 - a = 0 - Konvergenzabschätzung

Für die drei Iterationsvorschriften gilt:

02

12

1

2

1x3.

212122

212

.1

x

axF

x

axF

axxFxxaxF.

axwegenx

aaF

x

axF

Die Iterationsvorschrift ist also nicht konvergent.

Die Iterationsvorschrift ist nur für Werte a <1 konvergent

Die Iterationsvorschrift ist immer konvergent. Ihr Konvergenzverhalten wird von

F‘‘ und x2 bestimmt.

4/17


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Beispiel: x2 - a = 0 - KonvergenzabschätzungDurch eine Fehleranalyse können die drei Verfahren unterschieden werden.

ipi

p xFxAus 1

i

p

i

p xxx mit Folgt

xFdx

dipxxF

dx

dipxxF

ip

xxFipxxi

px

2

22

!2

1

11

10

1 oder

ixFx

xFipxi

px

x

FxFcondi

pxFcondi

pxbzw 1.

4/18


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Kondition bei BeispielansätzenDas bedeutet für die drei Iterationsvorschriften

axx

axF

x

axFa 2

21 wegen1)

Die Iterationsvorschrift ist also nicht konvergent

axxFxxaxFa 2121)() 22

Die Iterationsvorschrift ist nur für Werte a > 1 konvergent.

012

1

2

1)

23

x

axF

x

axxFa

Die Iterationsvorschrift ist immer konvergent.

Ihr Konvergenzverhalten wird von F“ und x2 bestimmt.

4/19


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Konvergenzabschätzung

Für die Konvergenzabschätzung ist also die Kondition

am aktuellen Lösungspunkt zu bestimmen.

Daraus folgt:

a) Konvergenz ist nur möglich, wenn

b) Gilt spricht man von monotoner, sonst von alternierender Konvergenz.

c) Ändert sich stark, so kann die Konvergenzgeschwindigkeit durch den Anfangswert bestimmt werden.

d) Bei monotoner Konvergenz kann aus der relativen Genauigkeit

auf Konvergenz geschlossen werden.

FFx

Fcond

1)( FcondxF

1)(0 xF

)(xF

i

p

i

p

i

pxxx /1

4/20


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Konvergenzverbesserung bei Iterationen

Bei monotoner Konvergenz kann man aus aufeinanderfolgenden Schritten auf die Konvergenzrate schließen. Definiert man

Konvergenzmonotonex

x

x

x

xxx

i

i

i

i

iii

1

1

1

und gilt

so folgt, daß man aus xi eine neue Lösung bestimmen kann. i

xx

1

2

i

i

ii

x x

xxx

ix* Konvergiert schneller als xi, wenn man ersetzt

(Aitken-Methode).

Für monotone Konvergenz muß gelten:

ist der Überrelaxationsfaktor.

121 iii xxdurchx

112

ii

i

xx

x

4/21


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Verfahren zur Lösung nichtlinearer Gleichungen

1. Newton-Verfahren

Bei nichtlinearen Problemen kann es schwierig sein, zu bestimmen.

Geschieht dies durch eine lineare Interpolation

erhält man das Sekantenverfahren.

2. Einschließungsverfahren

Liegt die Lösung in einem Intervall , so kann man die Lösung verbessern, indem man

einen Zwischenpunkt bildet und als neues Intervall dasjenige nimmt, für das das

Produkt der Funktionswerte an den Randpunkten negativ ist:

1

1

ii

ii

i

xx

xfxfxf

ixf

ii

ii

xf

xfxx

1

ii xx21

, iii xxx

215,0

0,

0,

22

11

iiii

iiii

xfxfwennxxinLösung

xfxfwennxxinLösung

Zur Lösung einer nichtlinearen Gleichung mit einer Variablen x der Gestalt f x) = 0gibt es verschiedene Typen von Verfahren zur iterativen Lösung.

4/22


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Konvergenzordnung der Iterationsverfahren

Beim Iterationsverfahren werden durch eine Iterationsvorschrift der Gestalt

0,vorgegeben, 01 kxxgx kk

Folgen bestimmt, für welche

gelten soll.

Ohne weitere Voraussetzung ist ihre Konvergenzordnung linear - also verhältnismäßig langsam. Als typisches Verfahren von quadratischer Konvergenz gilt das

kx 0 xfmitxx k

0,vorgegeben,Verfahren-NEWTON 01 kxxf

xfxx

k

kkk

Von überlinearer Konvergenzordnung ist das damit verwandte

kxxVorgabe

xxxfxf

xfx

kk

kk

kk ,,,x 10

1

11krfahrenSekantenve

4/23


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Diese Fragen sollten Sie beantworten können

Was ist ein iteratives Verfahren Wie findet man eine passende Iterationsvorschrift? Welche Anfangswerte sind zu wählen? Unter welchen Bedingungen konvergiert eine Iterationsfolge Wie schnell konvergiert eine Iterationsfolge Was ist eine Newton Iteration Welche Probleme treten bei nichtlinearen Gleichungen auf

4/24


isse

nsv

erar

be

itu

ng

un

d N

um

erik



Iterationsverfahren

Viele Probleme lassen sich umformulieren in eine Nullstellenbestimmung. So

auch die Aufgabe x²=a in f(x)=x²-a=0, gesucht wird x. Indem f(x)=0 so umge-

formt wird, daß x=(x) gilt, ergibt sich die Iterationsvorschrift xneu=(xalt) wo-

bei xneu für den neu berechneten Wert steht der rekursiv in xalt eingesetzt

wird. Für den ersten Wert xalt muß ein Startwert vorgegeben werden. Für x²=a

ergibt sich z.B.

a) (x) = a/x

b) (x) = a+x-x² (Es sind unendlich viele Umformungen möglich)

c) (x) = (x²+a)/2x die letzte Iterationvorschrift (Newton) ergibt sich aus (x)=x-f(x)/f'(x)

Der Versuch wird durchKlick gestartet

4/25


isse

nsv

erar

be

itu

ng

un

d N

um

erik



0

Die Funktion f sei zweimal stetig differenzierbar im I=[a,b] und besitze in (a,b) eine einfache Nullstelle , es seien also f()=0 und f'=() .Die Schrittfunktion lautet (x)= x - f(x)/f'(x).Versuch: Nullstellensuche bei nichtlinearer Gleichung: y=x³ mit y=1 ergibt (x)= x - (x³-1)/3x².Lösungen sind:

x = 1

x = 12

i

x = 12

i

1

2

3

( )

( )

1 3

1 3

Der Versuch wird durchKlick gestartet

Das Newtonsche Verfahren für einfache Nullstellen

Documents

Universität Stuttgart Wissensverarbeitung und Numerik I nstitut für K ernenergetik und E nergiesysteme Numerische Methoden, SS 2003Teil II: Kp. 4 4/1 Diese