Computer Based Engineering Mathematics - uni-due.de€¦ · Institut für Angewandte Materialtechnik Prof. Dr. rer. nat. Johannes Gottschling Dr.-Ing. Bernhardt Weyh Computer Based

Institut für Angewandte Materialtechnik Prof. Dr. rer. nat. Johannes GottschlingDr.-Ing. Bernhardt Weyh

Computer Based

Engineering Mathematics

-2-1

01

2

-2-1

0

12

-2

-1

0

1

2

Version 1.0 / 17.06.2005 1

Lineare Gleichungssysteme

1. Lineare Gleichungssysteme

Lineare Gleichungssysteme haben in der Ingenieurmathematik seit Einführung moderner Numerischer Verfahren eine sehr große Bedeutung bekommen.

The simplest model in applied mathematics is a system of linear equations.It is also by far the most important.GILBERT STRANG

1.1 Erste Motivation

Das Finite Differenzenverfahren ist eines der ältesten Verfahren zur Lösung partieller Differentialgleichungen.Dieses Verfahren soll an Hand des folgenden Beispiels der Laplace-Gleichung erläutert werden.Sei = [0;1] x [0;1] das zweidimensionale Einheitsquadrat und der Rand von Ω. Gesucht ist eineFunktion , die folgende Bedingungen erfüllt:

ΩΓ ∂=IR:u →Ω

Ω

Ω=∂∂

+∂∂

=∆ infyu

xuu 2

2

2

2

(1.1)

(Dirichlet Randbedingung)(1.2) Ω∂=Γ= aufgu

2


:INN,N

h ∈+

=1

1Diskretisierung von Ω mit der Gitterweite

• • • •• • • •• • • •• • • •

• • • •• • • •• • • •• • • •

• • • •• • • •• • • •

• • • •• • • •• • • •• • • •

• • • •1

1 - h

1 - 2h

y

x

2h

h

0h0 2h 1 - 2h 1 - h 1

[ ] [ ] ( ) ( ) hhhhh \,N,...,,l,k:lh,kh,N,...,,,l,k:lh,kh;; ΩΩ=Ω∂==Ω+==Ω→⊗=Ω 2112101010

••

- Randpunkt

- Innerer Punkt

3


Eine Diskretisierung generiert aus dem Quadrat eine diskrete Menge mit (N+2)2 Elementen.Ω hΩ

Beispiel 1.1.1:Für N = 3 erhalten wir als Gitterweite und somit die diskrete Menge mit 25 Elementen. 250

131 .h =+

= 250.Ω

x

y

• •

• •

•

•

• • • ••00

0.25

0.5

0.75

1

0.25 0.5 0.75 1

• • •

4

• ••

• • •

Gitterpunkt (x3,y2) = (3⋅0.25,2⋅0.25) = (0.75,0.5)

( ) ( ) ( )

( ) ( ) ( ) ⎪⎭

⎪⎬

⎫

⎪⎩

⎪⎨

⎧=Ω

11250101

10250000

250

,;...;.,;,

;,;...;.,;,

. MM•

•• ••


Aus der Differentialgleichung (1.1) erzeugen wir nun eine sogenannte Differenzengleichung.

Für ein festes y ∈[0;1] erhalten wir als Taylorentwicklung von u(x,y) bzgl. x:

( ) ( ) ( ) ( ) ( ) ( ) [ ]hx;x,y,xuhy,x

xuhy,x

xuhy,x

xuhy,xuy,hxu +∈

∂∂

+∂∂

+∂∂

+∂∂

+=+ ξξ4

44

3

33

2

22

2462(1.3)

( ) ( ) ( ) ( ) ( ) ( ) [ ]x;hx,y,xuhy,x

xuhy,x

xuhy,x

xuhy,xuy,hxu −∈

∂∂

+∂∂

−∂∂

+∂∂

−=− θθ4

44

3

33

2

22

2462(1.4)

Durch Addieren der beiden Gleichungen (1.3) und (1.4) folgt:

( ) ( ) ( ) ( ) ( ) ( )⎟⎠

⎞⎜⎝

⎛∂∂

+∂∂

+∂∂

+=−++ y,xuy,

xuhy,x

xuhy,xuy,hxuy,hxu θξ 4

4

4

44

2

22

122(1.5)

Auflösen der Gleichungen (1.5) nach der zweiten partiellen Ableitung von u bzgl. x liefert:

( ) ( ) ( ) ( ) ( ) ( )⎟⎠

⎞⎜⎝

⎛∂∂

+∂∂

−−−++

=∂∂ y,

xuy,

xuh

hy,xuy,hxuy,hxuy,x

xu θξ 4

4

4

42

22

2

122(1.6)

5


Analog erhalten wir für die zweite partielle Ableitung von u bzgl. y:

( ) ( ) ( ) ( ) ( ) ( ) [ ]hy;hy,,,xxu,x

xuh

hy,xuhy,xuhy,xuy,x

yu

+−∈⎟⎠

⎞⎜⎝

⎛∂∂

+∂∂

−−−++

=∂∂ µδµδ 4

4

4

42

22

2

122(1.7)

Damit folgt:

( ) ( ) ( ) ( ) ( ) ( )

( ) ( ) ( ) ( )4444444444 34444444444 21

⎟⎠

⎞⎜⎝

⎛∂∂

+∂∂

+∂∂

+∂∂

−

−+++−−++=∆

y,xuy,

xu,x

xu,x

xuh

hhy,xuhy,xuy,xuy,hxuy,hxuy,xu

θξµδ 4

4

4

4

4

4

4

42

2

12

4(1.8)

DiskretisierungsfehlerDiskretisierungsfehler

Diskretisierung des Laplace-Operators im R2:

( ) ( ) ( ) ( ) ( ) ( )2

4h

hy,xuhy,xuy,xuy,hxuy,hxuy,xuh

−+++−−++=∆(1.9)

6


Auf den Gitterpunkten setzen wir ( ) 110 +=Ω∈ N,...,,j,i,y,x hji

( ) j,iji uy,xu =(1.10)

( )ji y,x•

Mit dieser Notation gilt für dieinneren Gitterpunkte miti, j = 1,…,N:

( ) j,iji uy,hxu 1+=+

( ) ( )hy,xy,x jiji +=+1

•h

( ) ( )jiji y,hxy,x −=−1

•( )ji y,x 1+• ( ) j,iji uy,hxu 1−=−

( ) 1+=+ j,iji uhy,xu

( ) 1−=− j,iji uhy,xu

h( )1−ji y,x

•

7


Somit können wir für die inneren Gitterpunkte von den diskretisierte Laplace-Operator schreiben als:hΩ

( ) N,...j,i,h

uuuuuy,xu j,ij,ij,ij,ij,i

jih 121111 4

=−+−+ ++−+=∆(1.11)

Mit erhalten wir schließlich die Differenzengleichung:( ) j,iji fy,xf =

( ) N,...j,i,fh

uuuuuy,xu j,i

j,ij,ij,ij,ij,ijih 12

1111 4==

++−+=∆ −+−+(1.12)

mit den diskretisierten Randbedingungen

( ) ( )( ) ( )( ) ( )( ) ( )⎪

⎪⎩

⎪⎪⎨

⎧

======

======

+=

+=

+=

+=

+

++

10

10

10

10

11

00

11

00

1100

1100

N,...,i

N,...,i

N,...,j

N,...,j

,g,xgu,xu,g,xgu,xu

,gy,guy,u,gy,guy,u

N,ii,ii

,ii,ii

j,Njj,Nj

j,jj,j

(1.13)

8


Die Gleichung (1.12) kann vereinfacht geschrieben werden als

N,...,j,i,fhuuuuu j,ij,ij,ij,ij,ij,i 121111 4 ==++−+ −+−+(1.14)

(1.14) mit den Randbedingungen (1.13) bildet ein lineares Gleichungssystem mit N2 Gleichungen und Unbekannten. Randpunkte mit den Indizes , die in (1.14) auf der linkenSeite stehen, werden durch die Randfunktion g ausgewertet und können auf die rechte Seite derGleichung gebracht werden. Damit erhalten wir:

j,Nj,N,i,i u,u,u,u 1010 ++

(1.15) Gleichungen mit zwei Randpunkten:

0110112

112112 4 ,,,,,, ggfhuuu −−=−+

01112

1211 4 ,N,N,N,N,N,N ggfhuuu −−=−+ +−

11012

1211 4 +− −−=−+ N,N,N,N,N,N, ggfhuuu

112

21 4 ++− −−=−+ N,NN,NN,NN,NN,N,N ggfhuuu

(1.16) Gleichungen mit einem Randpunkt:

12012

212111 4 −=−=+−+ −+ N,...,i,gfhuuuu ,i,i,i,i,i,i

1212

111 4 −=+−−+ −=+−+ N,...,i,gfhuuuu N,iN,iN,iN,iN,iN,i

1212

111 4 −=+−+− −=+−+ N,...,j,gfhuuuu j,Nj,Nj,Nj,Nj,Nj,N

12012

111112 4 −=−=+−+ −+ N,...,j,gfhuuuu j,j,j,j,j,j,

1221111 4 −==++−+ −+−+ N,...,j,i,fhuuuuu j,ij,ij,ij,ij,ij,i

(1.17) Gleichungen ohne Randpunkt:

9


Wir ordnen den Lösungsvektor u des Systems (1.14) wie folgt:

( ) NNNNNNN IRu,...,u,...,u,...,u,u,...,uu ×∈= 1221111(1.18)

Beispiel 1.1.2:Wie wir bereits wissen, ist für N = 3 die Gitterweite 250

131 .h =+

=

x

y

•

•

•

•

• • • ••00

0.25

0.5

0.75

1

0.25 0.5 0.75 1

( ) 9333123211311 IRu,...,u,u,...,u,u,...,uu

Der Lösungsvektor hat dann die Komponenten

• •• •∈=

bAu

• •• •Durch einfaches Einsetzen in (1.15) – (1.17) erhalten wirdann ein Gleichungssystem der Form

• •• •=

•• •• mit der Koeffizientenmatrix A und der rechten Seite

( ) 9333123211311 IRb,...,b,b,...,b,b,...,bb ∈=

10


Die Koeffizientenmatrix A ist dabei gegeben durch

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

−−

−−

−−

−−

−

=

410100000141010000014001000100410100010141010001014001000100410000010141000001014

A

Für die rechte Seite b gilt:

(1.19)

)(

4334332

24232

0314132

42322

222

02122

4130312

20212

0110112

,,,,,,,,

,,,,,,,,,,,,,

ggfh,gfh,ggfh,gfh,fh,gfh,ggfh,gfh,ggfh

−−−−−

−−−−−−−=b

11


Hat der Lösungsvektor u die Anordnung wie in (1.18), dann ist die Koeffzientenmatrix A eine dünn besetzteBandmatrix mit Halbbandbreite N, symmetrisch und irreduzibel diagonal-dominant. Die Matrix –A ist regulärund positiv definit. A hat immer folgende Form, wobei I die Einheitsmatrix in IRNxN ist:

NNIR ×∈

⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜

⎝

⎛

−−

−−

=

410141

141

014

OO

O

B

⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜

⎝

⎛

=

BIIBI

IBIIB

0

0

OO

O

A mit

12

Definition 1.1.1:(i) Eine nxn-Matrix A = (aij) heißt Bandmatrix, falls es eine Zahl m < n gibt mit aij = 0 für alle Indexpaare mit |i – j| > m. Die Zahl m heißt Bandbreite. Eine Bandmatrix hat also nur in der Hauptdiagonalen undin den Nebendiagonalen Elemente ungleich Null.

(ii) Eine nxn-Matrix A heißt diagonal-dominant, wenn gilt:

(iii) Eine nxn-Matrix A heißt irreduzible, falls es keine Permutationsmatrix P gibt, so dass gilt:

n,...,i,aan

ijj

ijii 11

=∑≠=

≥

⎟⎟⎠

⎞⎜⎜⎝

⎛=

22

1211

0 AAA

PAPT , wobei A11 eine kxk-Matrix und A22 eine (m-k)x(m-k)-Matrix ist.


Dieses Muster der Bandmatrix können wir bei unserer Koeffizientenmatrix in Beispiel 1.1.2 sehr schön erkennen.

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

−−

−−

−−

−−

−

=

410100000141010000014001000100410100010141010001014001000100410000010141000001014

A

13


Mit Kenntnis dieser Struktur ist es nicht mehr schwierig, das Ausgangsproblem (1.1) mit der Randbedingung(1.2) als MATLAB-Funktion in Abhängigkeit von der Gitterweite (also von N), der Funktion f und der Rand-funktion g zu implementieren. In der Übung zur Vorlesung wird das für den vereinfachten Fall f = 0 und für konstante Randwerte (aber beliebige Gitterweite) realisiert werden.

Beispiel 1.1.3:Die stationäre Temperatur (das ist die Temperatur, die sich nach einer längeren Zeit einstellt) einerquadratischen homogen Platte, deren Ränder auf den Temperaturen

( ) 3212001 44 ,,i,Cg,xgu ,iii =°===

x

y

u14

00

0.25

0.5

0.75

1

0.25 0.5 0.75 1

u24 u34

u13 u23 u33 u43u03

100° C

0° C

150° C

200° C

14

u12 u22 u32 u42u02

u11 u21 u31 u41u01

u10 u20 u30

•

• •

• ( ) 3211001 44 ,,j,Cgy,gu j,jj =°===

( ) 3211500 00 ,,j,Cgy,gu j,jj =°===

( ) 32100 00 ,,i,Cg,xgu ,iii =°===

gehalten werden, wird durch die Gleichung

( ) ( ) ( ) 02

2

2

2

=∂∂

+∂∂

=∆ y,xyuy,x

xuy,xu(1.20)

beschrieben.

Die Gleichung (1.20) beschreibt ebenfalls denPotentialverlauf in einer quadratischen Ebene,


deren Ränder auf den Potentialen gehalten werden. Um die genäherte Temperatur an den diskreten Gitterpunkten zu berechnen, müssen wir nach Beispiel 1.1.2 das lineare Gleichungssystem

3210 ϕϕϕϕ ,,,

bAu =

lösen. Der Lösungsvektor hat die Komponentenund die Koeffizientenmatrix ist wieder

( ) 9333123211311 IRu,...,u,u,...,u,u,...,uu ∈=

Da f(x,y) = 0 erhalten wir mit (1.19) für die rechte Seite der Gleichung

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

−−

−−

−−

−−

−

=

410100000141010000014001000100410100010141010001014001000100410000010141000001014

A( )30010010020000350150150 −−−−−−−= ,,,,,,,,b

Somit müssen wir insgesamt das folgende lineareGleichungssystem (1.2.1) lösen:

15


⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

−−−−

−−−

=

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

−−

−−

−−

−−

−

30010010020000350150150

410100000141010000014001000100410100010141010001014001000100410000010141000001014

33

32

31

23

22

21

13

12

11

uuuuuuuuu

(1.21)

Wir lösen dieses Gleichungssystem mit MATLAB, ohne die besondere Struktur der KoeffizientenmatrixA, die ja sehr viele Nullen als Einträge hat, zu berücksichtigen. Eine solche Matrix wird als Sparsematrixbezeichnet und MATLAB bietet spezielle Verfahren für solche dünn bestzten Matrizen.

16


ErgebnisInput-File für MATLAB

17

u =

85.7143126.3393157.142966.5179

112.5000152.232167.8571

104.9107139.2857

A = [-4 1 0 1 0 0 0 0 0;1 -4 1 0 1 0 0 0 0;0 1 -4 0 0 1 0 0 0;1 0 0 -4 1 0 1 0 0;0 1 0 1 -4 1 0 1 0;0 0 1 0 1 -4 0 0 1;0 0 0 1 0 0 -4 1 0;0 0 0 0 1 0 1 -4 1;0 0 0 0 0 1 0 1 -4]

b=[-150;-150;-350;0;0;-200;-100;-100;-300]

u=A\b

Lösen des Gleichungssystems Au = b in MATLAB mit demBackslash-Operator


Bemerkung :Es ist natürlich nicht sinnvoll, eine Matrix so in MATLAB einzugeben, wie es auf der vorangehenden Seite gemacht wurde. Das kann bei einer sehr großen Matrix ziemlich lange dauern und ist darüberhinaus noch sehr fehleranfällig. Der folgende MATLAB-Quellcode generiert die Koeffizientenmatrix A in Abhängigkeit von der Gitterweite (also in Abhängigkeit von N).

%Generieren der Koeffizientenmatrix A in Abhängigkeit von N%--------------------------------------------------------------------------------N = 3;

B = -diag(ones(1,N)*4)+diag(ones(1,N-1),1)+diag(ones(1,N-1),-1);

C = zeros(N^2);for k = 0:N-1

for i=1:Nfor j =1:N

C(i+k*N,j+k*N)=B(i,j);end

end end

A = C + diag(ones(1,N^2-N),N) + diag(ones(1,N^2-N),-N)

Ein Ziel der Vorlesung und den zu-geordneten Übungen und Praktikawird sein, solche Strukturen zu er-kennen und damit auch große Daten-mengen zu bearbeiten.

Mit Hilfe des Lösungsvektors u, denwir mit MATLAB ermittelt haben, können wir nun die Lösung unseresProblems wie folgt visualisieren.

Hinweis: Der MATLAB-Quellcode ist nicht optimiert. Ziel des Praktikums ist unter anderem auch, solche Programme zu optimieren und zu diskutieren, wann eine Optimierung sinnvoll ist.

18


Temperaturverteilung in den Gitterpunkten für N = 3, also h = 0.25

x

y

200,00

0 0.25 0.5 0.75 10° C

150° C

200° C

0

•

• •

•1

19

0

0.25

0.5

0.75

100° C

200,00 200,00

150,00

150,00

150,00

0 0

100,00

100,00

100,00

157,14

126,34

85,71

152,23

112,50

66,52

139,29

104,91

67,86


Der diskrete Lösungsvektor u gibt nur die Temperatur in den Gitterpunkten an. Wollen wir die Temperaturin Punkten der Platte Ω approximieren, die nicht in der diskreten Menge liegen, so müssen wir diese Werte interpolieren. Dazu gibt es verschiedene Möglichkeiten von denen wir im Folgenden zwei angeben.

hΩ

20

• ( ) 5011222 .y,xu =

( ) 50112.y,xu =

( ) ( )22 y,xy,x −

•

•• ( ) 526612 .y,xu =

( ) ( ) 2526650112 /..y,xu +=

Möglichkeit 1:Dem Punkt (x,y) wird die Temperatur u(x,y) zugeordnet, die dem Gitterpunkt zugeordnet ist, der zum Punkt (x,y) den kleinsten Abstand hat. Haben n Gitterpunktedenselben Abstand, so wird der Mittelwertder Temperatur genommen (s. Fig. 1.1).

( )ji y,x

Fig. 1.1 Interpolation 1 der Temperatur


Möglichkeit 2:

21

•

• •( ) 2315232 .y,xu =

Jede quadratische Zelle Ωi,j des Gitters wird in zweiDreiecke unterteilt. Jedem dieser Dreiecke könnenwir nun eine Ebene im IR3 zuordnen, die durch die drei Punkte

Fig. 1.2 Interpolation 2 der Temperatur

• ( ) 5011222 .y,xu =

( ) 3412621 .y,xu =

( ) 1415731 .y,xu =

Zelle 22,Ω

( )( ) ( )( ) ( )( ) jijijijijiji y,xu,y,x,y,xu,y,x,y,xu,y,x 1111 −−++

( )( ) ( )( ) ( )( ) jijijijijiji y,xu,y,x,y,xu,y,x,y,xu,y,x 11111111 −−+++−+−

bzw.

bestimmt ist. In Fig. 1.2 sind das die Punkte

( ) ( ) ( ) 34126502502315275050501125050 .,.,.,.,.,.,.,.,.

bzw.( ) ( ) ( ) 3412650250231527505014157750250 .,.,.,.,.,.,.,.,.

Für die Zelle Ωi,j, i,j =1,…,N+1 des Gitters erhalten wir dielineare Interpolationsfunktion:

( ) ( ) ( )( ) ( )⎩

⎨⎧

≤≤+−+∧≤≤+−+≤≤∧≤≤

=+−

−

11

1

11

jiiij

jiiijij yyhijxxxx,y,xg

hijxyyxxx,y,xfy,xϕ

( ) ( ) ( ) ( ) ( )yuuh

xuuh

uyuuh

xuuh

y,xf j,ij,iijj,iijjj,ij,iiijj,iij −−−−+−+−= +−+− 1111

1111wobei

( ) ( ) ( ) ( ) ( )yuuh

xuuh

uyuuh

xuuh

y,xg j,ij,ij,ij,ij,ijj,ij,iij,ij,iij 1111111111111111

1111+−−+−++−++−−−+−+ −−−++−+−−=und


Für die Zelle Ω2,2 in Fig. 1.2 ist

( )⎩⎨⎧

≤≤+∧≤≤−−+≤≤∧≤≤+−

=75025050250201236419656925050502509215836557260

22 .y.x.x.,y.x...xy..x.,y.x..

y,xϕ

Es kann gezeigt werden, dass das Problem(1.1) mit der Randbedingung (1.2) eine Lösung besitzt und dass diese Lösung in Abhängigkeit von der rechten Seite f, der Randfunktion g und der Geometrie des Randes Γ von Ω hinreichend glatt ist;d.h. hinreichend oft partiell differenzierbarund damit auch stetig. A priori Aussagen über die Stetigkeit und Differenzierbarkeit (also über die Regularität)einer Lösung gehören zum Bereich derRegularitätstheorie partieller Differential-gleichungen. Ist die exakte Lösung u hinreichend glatt, sokonvergiert die diskrete Lösung uh, die wirbisher aus bequemlichkeitsgründen ebenfallsu genannt haben, gegen die exakte Lösung.

Fig. 1.3 Lineare Interpolation ( )y,x22ϕ

22


Eine Interpolation konvergiert dann ebenfalls gegen die exakte Lösung u. Die diskrete Lösung uh oderdie auf ganz definierte interpolierende Funktion approximiert die exakte Lösung u natürlich um sobesser, je kleiner die Gitterweite h = 1/(N+1) , also je größer N ist.Eine Verkeinerung der Gitterweite h hat aber zur Folge, dass die Rechenzeit ansteigt. Im Folgenden einigeBeispiele, die auf einem AMD Athlon XP2000+ (512 MB RAM) mit MATLAB berechnet wurden.

hu~Ω hu~

Die Rechenzeit beinhaltet auch dasGenerieren der KoeffizientenmatrixA und nicht nur das Lösen desGleichungssystems.

Temperaturverteilung der innerenPunkte Ωh für N = 60, also für dieGitterweite h = 0.0164.Die Koeffizientenmatrix A ist in diesem Fall eine (3600x3600)-Matrixund hat somit 12,960,000 Knoten-punkte.

Rechenzeit: ~ 0.34 sec

23Fig. 1.4 Temperaturverteilung für N = 60


Lineare Interpolation der Lösung einschließlich Randwerte für N = 60, Gitterweite h = 0.0164,Grafik: x = linspace(0,1,100), y = linspace(0,1,100), GrafikZeit: ~ 6.6 sec

24Fig. 1.5 Lineare Interpolation der Temperaturverteilung für N = 60


Lineare Interpolation der Lösung einschließlich Randwerte für N = 60, Gitterweite h = 0.0164,Grafik: x = linspace(0,1,500), y = linspace(0,1,500), GrafikZeit: ~ 60 sec

25Fig. 1.6 Lineare Interpolation der Temperaturverteilung für N = 60, engeres Gitter für die Grafik


Temperaturverteilung im Inneren der Platte für N = 100, Gitterweite h = 0.0099. Die Koeffizientenmatrix Aist in diesem Fall eine (10,000 x 10,000)-Matrix und hat somit 100,000,000 Knotenpunkte. Rechenzeit: ~ 1.03 sec.

Fig. 1.7 Innere Temperaturverteilung für N = 10026


Lineare Interpolation der Lösung einschließlich Randwerte für N = 100, Gitterweite h = 0.0099,Grafik: x = linspace(0,1,100), y = linspace(0,1,100), GrafikZeit: ~ 8 sec.



Temperaturverteilung im Inneren der Platte für N = 500, Gitterweite h = 0.001996. Die Koeffizientenmatrix A ist in diesem Fall eine (250,000 x 250,000)-Matrix und hat somit 62,500,000,000 Knotenpunkte.Rechenzeit: ~ 764 sec.

Fig. 1.9 Innere Temperaturverteilung für N = 500 28


Lineare Interpolation der Lösung einschließlich Randwerte für N = 500, Gitterweite h = 0.001996.Grafik: x = linspace(0,1,100), y = linspace(0,1,100), GrafikZeit: ~ 1550 sec



Lineare Interpolation der Lösung einschließlich Randwerte für N = 500, Gitterweite h = 0.001996.Grafik: x = linspace(0,1,500), y = linspace(0,1,500), GrafikZeit: ~ 4750 sec



Das hier beschriebene Differenzenverfahren kann auch auf Gebiete Ω mit gekrümmten Rand ange-wendet werden, wobei es verschiedene Möglichkeiten der Approximation entlang des Randes gibt.

Fig. 1.12 Approximation eines gekrümmtem Randes

Fig. 1.11 Gebiet mit gekrümmten Rand mit grober und feinererDiskretisierung

31


1.2 Zweite Motivation

Wir wollen die eindimensionale Gleichung für die ungedämpfte Schwingung mit Hilfe einer Finiten-Element-Methode diskretisieren. Wir betrachten dazu das Problem

( ) ( ) ( ) [ ]10;t,tftkutum ∈=+′′(1.22) , m und k reelle Konstanten,

mit den Randbedingungen

( ) ( ) 10 10 gu,gu =′=(1.23)

Zunächst unterteilen wir das Intervall [0;1] in N gleichgroße Teilintervalle mit t0 = 0 und tN = 1.

Das Galerkin-Verfahren:Ausgangspunkt des Galerkin-Verfahrens ist eine sogenannte schwache Formulierung des Problems (1.22)mit den Anfangsbedingungen (1.23). Die approximierende Lösung u liegt in einem Funktionenraum, dervon gewissen Basisfunktionen aufgespannt wird. Diese Basisfunktionen müssen die Randbe-dingung

[ ]ii t;t 1−

N,...,ϕϕ1

( ) N,...,i,i 100 ==ϕ(1.24)

( ) ( ) ( ),tutgtuN

iii∑

=

+=1

00 ϕϕ(1.25)erfüllen. Als approximierende Lösung setzen wir dann:

32


wobei ϕ0 eine Funktion ist, die die Randbedingung

( ) 100 =ϕ(1.26)

erfüllt. Sei ϕ nun eine beliebige Testfunktion mit der Eigenschaft ϕ(0) = 0. Ferner sei ϕ bis auf endlich vieleStellen differenzierbar (das kann man wesentlich präziser formulieren, für unsere Zwecke reicht das aber aus). Mit (1.22) erhalten wir dann:

( ) ( ) ( ) ( ) ( ) ( ) [ ]10;t,ttfttkuttum ∈=+′′ ϕϕϕ(1.27)

Integrieren wir (1.27) so folgt:

( ) ( ) ( ) ( ) ( ) ( )dtttfdtttukdtttum ∫∫∫ =+′′1

0

1

0

1

0

ϕϕϕ

Partielle Integration liefert:

( ) ( )[ ] ( ) ( ) ( ) ( ) ( ) ( )

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )dtttfdtttukdtttumum

dtttfdtttukdtttumttum

∫∫∫

∫∫∫

=+′′−′⇒

=+′′−′

1

0

1

0

1

0

1

0

1

0

1

0

10

11 ϕϕϕϕ

ϕϕϕϕ

Somit erhalten wir die schwache Formulierung:

( ) ( ) ( ) ( ) ( ) ( ) ( )dtttfmgdtttukdtttum ∫∫∫ −=−′′1

01

1

0

1

0

1 ϕϕϕϕ(1.28)

33


Wählen wir als Testfunktion unsere Basisfunktionen , so erhalten wir die Gleichungen N,...,ϕϕ1

( ) ( ) ( ) ( ) ( ) ( ) ( ) N,...,j,dtttfmgdtttukdtttum jjjj 111

01

1

0

1

0

=−=−′′ ∫∫∫ ϕϕϕϕ(1.29)

In (1.29) setzen wir nun die approximierende Lösung aus (1.25) ein. Damit folgt:

( ) ( ) ( ) ( )

( ) ( ) ( ) ( ) ( ) ( ) ( ) N,...,j,dtttfdtttmgdtttkgmg

dtttukdtttum

jjjj

N

ijii

N

ijii

111

0

1

000

1

0001

1

1

01

1

0

=−′′−+=

−′′

∫∫∫

∑ ∫∑ ∫==

ϕϕϕϕϕϕ

ϕϕϕϕ

Also:

( ) ( ) ( ) ( )

( ) ( ) ( ) ( ) ( ) ( ) ( ) N,...,j,dtttfdtttmdtttkgmg

dtttkdtttmu

jjjj

N

ijijii

111

0

1

00

1

0001

1

1

0

1

0

=−⎟⎠⎞

⎜⎝⎛ ′′−+=

⎟⎠⎞

⎜⎝⎛ −′′

∫∫∫

∑ ∫∫=

ϕϕϕϕϕϕ

ϕϕϕϕ(1.30)

34


( ) ( ) ( ) ( )dtttkdtttma jijiij ∫∫ −′′=1

0

1

0

ϕϕϕϕ ( ) ( ) ( ) ( ) ( ) ( ) ( ) ,dtttfdtttmdtttkgmgb jjjjj ∫∫∫ −⎟⎠⎞

⎜⎝⎛ ′′−+=

1

0

1

00

1

0001 1 ϕϕϕϕϕϕund Sei

dann können wir (1.30) schreiben als

N,...,j,bua j

N

iiij 1

1==∑

=also bAu =(1.31)

( ) ( )NNj,iij u,...,uu,aA 11==

≤≤( ).b,...,bb N1=wobei und

Wir wählen als Testfunktionen ϕi stückweise lineare Funktionen; und zwar:

ti-1 ti ti+1

h h0 1

1ϕi

( )( )

( )N,...,i,

tt,

ttt,tth

ttt,tth

tt,

t

i

iii

iii

i

i 0

10

1

1

00

1

11

11

1

=

⎪⎪⎪⎪⎪

⎩

⎪⎪⎪⎪⎪

⎨

⎧

≤≤

<≤−−

<<−

≤≤

=

+

++

−−

−

ϕ

Fig. 1.13 Stückweise lineareTestfunktionwobei h = |ti – ti-1|. 35


1

t1

ϕ0

1

tN-1

ϕN

1

Fig. 1.14 Stückweise lineareTestfunktionen ϕ0 und ϕN

Wir berechnen die Koeffizienten aij.

1. Fall :NijNji ≤<+∨≤<+ 11

ti-1 ti0

ti+1

1

tj-1 tj tj+1

( ) ( ) ( ) ( ) [ ]1000 ;ttttt jiji ∈∀=′′∧= ϕϕϕϕ

( ) ( ) ( ) ( ) 01

0

1

0

=−′′= ∫∫ dtttkdtttma jijiij ϕϕϕϕ

Also:

36


2. Fall :Nji ≤=+ 1

ti-1 ti0

ti+1= tj

1

tj+1

( ) ( )

⎪⎪⎪

⎩

⎪⎪⎪

⎨

⎧

≤≤

<<−

≤≤

=′′

10

1

00

2

tt,

ttt,h

tt,

tt

j

ji

i

ji ϕϕ

( ) ( ) ( ) ( ) ( )h

tth

dtttdttt ij

t

tjiji

j

i

112

1

0

−=−−=′′=′′⇒ ∫∫ ϕϕϕϕ

( ) ( ) ( ) ( ) ⎟⎠⎞

⎜⎝⎛ +−=−′′= ∫∫ 6

1

0

1

0

khhmdtttkdtttma jijiij ϕϕϕϕ

Also:

( ) ( ) ( )( )

⎪⎪⎪

⎩

⎪⎪⎪

⎨

⎧

≤≤

<<−−−

≤≤

=

10

1

00

2

tt,

ttt,tttth

tt,

tt

j

jiij

i

ji ϕϕ

( ) ( ) ( ) ( ) ( )( ) ( ) htth

dttttth

dtttdttt ij

t

tij

t

tjiji

j

i

j

i61

611 3

22

1

0

=−=−−−==⇒ ∫∫∫ ϕϕϕϕ

37


3. Fall :Nji 1−≤=

ti-1 ti = tj0

38

ti+1= tj+1

1

( ) ( )

⎪⎪⎪

⎩

⎪⎪⎪

⎨

⎧

≤≤

<<

≤≤

=′′

−

10

1

00

2

1

tt,

ttt,h

tt,

tt

j

ji

i

ji ϕϕ

( ) ( ) ( ) ( ) ( )h

tth

dtttdttt ii

t

tjiji

i

i

21112

1

1

0

1

=−=′′=′′⇒ +−−∫∫+

ϕϕϕϕ

( ) ( )( )( )

( )( )

⎪⎪⎪⎪⎪

⎩

⎪⎪⎪⎪⎪

⎨

⎧

≤≤

<≤−−

<<−−

≤≤

=

+

+++

−−−

−

10

1

1

00

1

1112

1112

1

tt,

ttt,tttth

ttt,tttth

tt,

tt

j

jiji

jiji

i

ji ϕϕ( ) ( ) ( ) ( )

3221

0

1

0

khhmdtttkdtttma jijiij −=−′′= ∫∫ ϕϕϕϕ

Also:

( ) ( ) ( )( ) ( )( ) ( ) ( ) htth

tth

dttttth

dttttth

dttt iiii

t

tji

t

tjiji

i

i

i

i32

31

3111 3

123

12112112

1

0

1

1

=−+−=−−+−−=⇒ +−++−− ∫∫∫+

−

ϕϕ


4. Fall :Nji ==

( ) ( )⎪⎪⎩

⎪⎪⎨

⎧

≤<

≤≤

=′′

−

−

NN

N

NN

ttt,h

tt,

tt12

1

1

00

ϕϕ

1

tN-1 1

( ) ( ) ( ) ( ) ( )h

tth

dtttdttt NN

t

tjiji

N

N

1112

1

1

0

=−=′′=′′⇒ −−∫∫ ϕϕϕϕ

( ) ( ) ( ) ( )3

1

0

1

0

khhmdtttkdtttma NNNNNN −=−′′= ∫∫ ϕϕϕϕ

Also:

( ) ( )( )⎪

⎪⎩

⎪⎪⎨

⎧

≤<−

≤≤

=

−−

−

11

00

12

12

1

tt,tth

tt,

ttNN

N

NN ϕϕ

( ) ( ) ( ) ( )33

11 312

212

1

0 1

htth

dttth

dttt NN

t

tNNN

N

N

=−=−=⇒ −−∫∫−

ϕϕ

39


5. Fall :Nij 11 −≤−=

tj-1 ti-1= tj0

ti

1

ti+1

( ) ( )

⎪⎪⎪

⎩

⎪⎪⎪

⎨

⎧

≤≤

<<−

≤≤

=′′

10

1

00

2

tt,

ttt,h

tt,

tt

i

ij

j

ji ϕϕ

( ) ( ) ( ) ( ) ( )h

tth

dtttdttt ji

t

tjiji

i

j

112

1

0

−=−−=′′=′′⇒ ∫∫ ϕϕϕϕ

( ) ( ) ( ) ( ) ⎟⎠⎞

⎜⎝⎛ +−=−′′= ∫∫ 6

1

0

1

0

khhmdtttkdtttma jijiij ϕϕϕϕ

Also:

( ) ( ) ( )( )

⎪⎪⎪

⎩

⎪⎪⎪

⎨

⎧

≤≤

<<−−−

≤≤

=+−

10

1

00

112

tt,

ttt,tttth

tt,

tt

i

ijji

j

ji ϕϕ

( ) ( ) ( ) ( ) ( )( ) ( ) htth

dttttth

dtttdttt ii

t

tii

t

tjiji

i

i

i

j61

611 3

1212

1

0 1

=−=−−−==⇒ −−∫∫∫−

ϕϕϕϕ

40


Insgesamt erhalten wir mit h = 1/N:

⎪⎪⎪⎪⎪⎪⎪⎪⎪

⎩

⎪⎪⎪⎪⎪⎪⎪⎪⎪

⎨

⎧

−≤−=⎟⎠⎞

⎜⎝⎛ +−

==−

−≤=−

≤=+⎟⎠⎞

⎜⎝⎛ +−

≤<+

≤<+

=

116

3

13

22

16

10

10

Nij,khhm

Nji,khhm

Nji,khhm

Nji,khhm

Nij,

Nji,

aij

41


Beispiel 1.2.1:

h=1/N;for i = N:-1:1

for j = N:-1:1if (i+1 < j) & (j <= N)

A(i,j) = 0;elseif (j+1 < i) & (i <= N)

A(i,j) = 0;elseif (i+1 == j) & (j <= N)

A(i,j) = -(1/h +h/6);elseif (i == j) & (j <= N - 1)

A(i,j) = 2/h - 2*h/3;elseif (i == j) & (j == N)

A(i,j) = 1/h - h/3;elseif (i - 1 == j) & (j <= N - 1)

A(i,j) = -(1/h +h/6);end

end end

MATLAB-Code zur Generierung der Koeffizientenmatrix A mit m = k = 1:

Für N = 4, m = k = 1, erhalten wir die Koeffizientenmatrix

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

=

3.91673.9583-003.9583-7.83333.9583-0

03.9583-7.83333.9583-003.9583-7.8333

A

42


( ) ( ) ( ) ( ) ( ) ( ) ( ) .dtttfdtttmdtttkgmgb jjjjj ∫∫∫ −⎟⎠⎞

⎜⎝⎛ ′′−+=

1

0

1

00

1

0001 1 ϕϕϕϕϕϕWir berechnen die rechte Seite

Die Funktion f approximieren wir dabei durch

( ) ( ) ( ) N,...,i,tff,tftf~ ii

N

iii 0

0=== ∑

=

ϕ

Die Werte fj sind die Funktionswerte von f an den Knoten tj. Es gilt:

( ) ( ) ( ) ( )⎪⎪⎩

⎪⎪⎨

⎧

≤<

=+=′′− ∫∫

Nj,

j,h

h

dtttdttt jj

10

1161

00

1

00 ϕϕϕϕ

und

( ) ( ) ( ) ( )

⎪⎪

⎩

⎪⎪

⎨

⎧

=+

<≤++

=≈

−

+−

=∑ ∫∫

Nj,fhfh

Nj,fhfhfh

dtttfdtttf

NN

jjjN

ijiij

36

163

26

1

11

0

1

0

1

0

ϕϕϕ

43


Insgesamt gilt mit h = 1/N:

Nj,fhfhfhb jjjj <<⎟⎠⎞

⎜⎝⎛ ++−= +− 1

632

6 11

⎟⎠⎞

⎜⎝⎛ ++−⎟

⎠⎞

⎜⎝⎛ += 21001 63

266

fhfhfhghmkhb

⎟⎠⎞

⎜⎝⎛ +−= − NNN fhfhmgb

36 11

44


Wir erhalten ein lineares Gleichungssystem, wobei die Koeffzientenmatrix A wieder eine dünn besetzteBandmatrix ist. Die Bandbreite ist hier gleich 1.

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

⎟⎠⎞

⎜⎝⎛ +−

⎟⎠⎞

⎜⎝⎛ ++−

⎟⎠⎞

⎜⎝⎛ ++−⎟

⎠⎞

⎜⎝⎛ +

=

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

⎟⎠⎞

⎜⎝⎛ −⎟

⎠⎞

⎜⎝⎛ +−

⎟⎠⎞

⎜⎝⎛ +−⎟

⎠⎞

⎜⎝⎛ −⎟

⎠⎞

⎜⎝⎛ +−

⎟⎠⎞

⎜⎝⎛ +−⎟

⎠⎞

⎜⎝⎛ −⎟

⎠⎞

⎜⎝⎛ +−

⎟⎠⎞

⎜⎝⎛ +−⎟

⎠⎞

⎜⎝⎛ −

−

+−

−

NN

jjj

N

Nfhfhmg

fhfhfh

fhfhfhghmkh

uu

uu

khhmkh

hm

khhmkh

hmkh

hm

khhmkh

hmkh

hm

khhmkh

hm

36

632

6

632

66

3600

6322

6

00

6322

6

0063

22

11

11

2100

1

2

1

M

M

M

M

L

LM

OL

ML

L

45


Beispiel 1.2.2:

(i) Wir betrachten die Gleichung

( ) ( ) ( ) [ ]1024 ;t,tsintutu ∈=+′′ π


( ) ( ) 1100 =′= u,u

Die exakte Lösung der Gleichung ist (vgl. Mathematics II, Kapitel 4.3.3):

( ) ( ) ( )tsintsin.tu 244

1233650−

+⋅−=π

π Fig. 1.14 Stückweise lineareTestfunktionen für N = 3

Wir wollen die exakte Lösung mit der approximierendenLösung vergleichen:

A =3.2075 -3.6981 0

-3.6981 3.2075 -3.69810 -3.6981 1.6037

b =-0.1914 -0.3009 0.8450

u =-0.2313 -0.1489 0.1836

Koeffizientenmatrix A und rechte Seite b für N = 3: Lösungsvektor u für N = 3:

Approximierende Lösung u(t) für N = 3:

( ) ( ) ( ) ( )t.t.t.tu 321 183601489023130 ϕϕϕ ⋅+⋅−⋅−=

46


Fig. 1.15 Exakte und approximierende Lösung N = 3

exakte Lösung

approximierende Lösung47



Fig. 1.17 Stückweise lineareTestfunktionenfür N = 10

exakte Lösung




exakte Lösung



function y = phi(N,j,t)%---------------------------------------------------------------------------% Funktionswerte einer stückweisen zusammengesetzten % Funktion%---------------------------------------------------------------------------h = 1/N;y1 = 0 * (t <= (j-1)*h);y2 = (1/h)*(t - (j-1)*h).* ((t<j*h) - (t<(j-1)*h));y3 = -(1/h)*(t - (j+1)*h).* ((t<(j+1)*h) - (t<j*h));y4 = 0 * (1 - (t<(j+1)*h));y = y1 + y2 + y3 + y4; function y = uapprox(N,g0,u,t)

%--------------------------------------------------------------------------------------% Approximierende Lösungsfunktion%% Eingabe: N - Anzahl der Teilintervalle% g0 - Randwert für t = 0% u - Lösungsvektor des diskretisierten Problems%% Ausgabe: y = g0*phi(N,0,t)+ u(1)*phi(N,1,t) + ... + u(N)*phi(N,N,t)%--------------------------------------------------------------------------------------y1 = g0*phi(N,0,t);y = 0;for j = 1:N

y = y + u(j)*phi(N,j,t);endy = y + y1;

MATLAB-Code für die approximierende Lösungsfunktion, die von den Basis-funktionen und dem Lösungsvektor u des diskretisierten Problems erzeugt wird.

MATLAB-Code für die stückweise linearenFunktionen ϕj in Abhängigkeit von der An-zahl der Teilintervalle.

50

Aufruf der Funktion phi


(ii) Wir betrachten die Gleichung

( ) ( ) ( ) [ ]102400 ;t,tsintutu ∈=+′′ π


( ) ( ) 10110 =′= u,u

( )

Die exakte Lösung der Gleichung ist (vgl. Mathematics II, Kapitel 4.3.3):

51

( ) ( )( )tsin

tcostsin.tu

24400

1202078950

−+

+⋅=

π

ππ Fig. 1.19 Exakte und approximierende Lösung N = 100


exakte Lösung

approximierende Lösung


MATLAB kann „einfach strukturierte“ DGL mit der Funktion dsolve aus der Symbolic Toolbox explizit lösen. Das geht wie folgt:

%-------------------------------------------------------------------------%Lösung einer DGL mit dsolve%-------------------------------------------------------------------------z = dsolve('D2u + 400*pi*u = sin(2*t)','u(0)=1','Du(1)=10');u = inline(char(z));x = linspace(0,1,100);y = u(x);plot(x,y);

Die symbolische Variable z wirdkonvertiert und die auf z ausgege-bene Funktion wird als inline-Funktionerzeugt.

52


Bemerkung 1.2.1:(i) Das Galerkin-Verfahren funktioniert auch, wenn keine äquidistanten Teilintervalle benutzt werden.Die Koeffizientenmatrix A und die rechte Seite b werden dann allerdings ein wenig komplizierter. Für das Problem

[ ]ii t;t 1−

( ) ( ) [ ],;t,tftu 10∈=′′− ( ) ( ) 10 10 gu,gu =′=

erhalten wir beispielsweise mit hi = |ti – ti-1| die Diskretisierung

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

++

++

+

+++

=

⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

−

−⎟⎟⎠

⎞⎜⎜⎝

⎛+−

−⎟⎟⎠

⎞⎜⎜⎝

⎛+

−

++

+−++

11

11

11

10

12

11

10

1

11

221

36

336

1336

1100

1111

00111

ghfhf

hfhhfhf

hghfhfhf

u

u

u

hh

hhhh

hhh

NN

NN

ii

iii

ii

N

i

NN

iiii

M

M

M

M

L

LOLM

LL

MLL

L

53


(ii) Das Galerkin-Verfahren kann auch auf höher dimensionale Probleme angewendet werden.

54


1.3 Lösen linearer quadratischer Gleichungssysteme mit MATLAB

Der Backslash-Operator (\ -Operator) in MATLAB beinhaltet verschiedene Algorithmen zur Lösung linearer Systeme Ax = b. Welcher Algorithmus von MATLAB zum Lösen eines speziellen Problems ausgewählt wird, hängt von der Struktur der Koeffizientenmatrix A ab. Bevor die Lösungsstrategiendargelegt werden, sollen einige spezielle Koeffizientenmatrizen vorgestellt werden.

1.3.1 Dünn besetzte Matrizen

MATLAB geht zunächst davon aus, dass eine Matrix dicht besetzt ist; d.h. nur wenige Matrixelemente sind gleich Null. Sind aber in einer Matrix viele Elemente gleich Null (wie wir das in der ersten und zweiten Motivation gesehen haben), so spricht man von einer dünn (schwach) besetzen Matrix oder von einer Sparsematrix. Sparsematrizen entstehen bei der Diskretisierung partieller oder gewöhnlicher Differentialgleichungen oder auch bei der Modellierung von Netzwerkproblemen. Hat die Matrix dazu noch eine Bandstruktur (wie es bei unseren Differentialgleichungen der Fall war) oder kann sie auf eine solche transformiert werden, so gibt es effektive Bandalgorithmen, die solche Gleichungssysteme lösen.Bei der Modellierung von Netzwerkproblemen liegt im Allgemeinen keine regelmäßige Struktur vor, so dass Bandalgorithmen meistens nicht geeignet sind. Das gilt auch, wenn die Banbreite sehr groß ist und innerhalb des Bandes viele Nullen vorhanden sind. Hier sollten spezielle Varianten des GaussschenAlgorithmus für Sparsematrizen angewendet werden (vgl. [1]). Für Sparsematrizen können meistens Gleitpunktoperationen auf den Nullelementen eingespart werden. Ferner muss nicht die gesamte Matrix abgespeichert werden, sondern nur die von Null verschiedenen Elemente mit den zugehörigen Indizes. Somit lassen sich Speicher-und Zeitaufwand reduzieren. Daher können mit Sparsematrizen Probleme einer Größenordnung gelöst werden, die sonst nicht lösbar wären.

55


MATLAB benutzt die beiden Speichermodi full und sparse, wobei full default ist. Mit den implementierten Funktionen full und sparse kann zwischen diesen beiden Modi hin und her geschaltet werden.

>> S = sparse(A)S =

(1,1) 3(2,1) 1(1,2) 1(2,2) 3(3,2) 1(2,3) 1(3,3) 3(4,3) 1(3,4) 1(4,4) 3(5,4) 1(4,5) 1(5,5) 3(6,5) 1(5,6) 1(6,6) 3(7,6) 1(6,7) 1(7,7) 3

Die Anweisung

>> A = triu(tril(ones(7),1),-1) + 2*eye(7)

erzeugt die (7x7)-Matrix

A =3 1 0 0 0 0 01 3 1 0 0 0 00 1 3 1 0 0 00 0 1 3 1 0 00 0 0 1 3 1 00 0 0 0 1 3 10 0 0 0 0 1 3

Speichern der Matrix A imSparsemodus:

Zeilen- und Spaltenindex Die von Null verschiedenenElemente werden zusammenmit den Indizes spaltenweiseangeordnet.

triu - Obere Dreiecksmatrixtril - Untere Dreiecksmatrixones - Matrix mit allen Elementen 1eye - Einheitsmatrix

56


Mit der Anweisung

>> A = full(S)

können wir das rückgängig machen. Der Funktionsaufruf nnz(A) zeigt die Anzahl der von Null verschiedenen Elemente der Matrix A. Für unsere Beispielsmatrix gilt:

>> nnz(A)ans =

19

MATLAB bietet viele Möglichkeiten, Sparsematrizen direkt zu erzeugen. Mit der implementierten Funktion spdiags können beispielsweise schwach besetzte Bandmatrizen generiert werden.

>> m = 7; n=7; e = ones(n,1); d = 3*e;>> S = spdiags([e,d,e],[-1,0,1],m,n);>> A=full(S)A =

3 1 0 0 0 0 01 3 1 0 0 0 00 1 3 1 0 0 00 0 1 3 1 0 00 0 0 1 3 1 00 0 0 0 1 3 10 0 0 0 0 1 3

Der Vektor [-1, 0, 1] gibt an,in welcher Diagonalen dieSpalten von [e,d,e] stehen

Mit spy(A) kann die Strukturder Matrix A grafisch betrachtetwerden

57


Die zu eye, zeros, ones, rand und randn analogen Sparsefunktionen sind

speye, sparse, spones, sprand, sprandn.

zeros - Nullmatrixrand - Gleichmäßigverteilte Zufallsmatrixrandn - Normalverteilte Zufallsmatrix

Ist S eine Sparsematrix, A eine vollbesetzte Matrix und r ein Skalar, dann gilt:

Sparse S + S, S * S, S .* S, S .* A, S^n, S.^n, S \ s, r * S, r \ S

inv(S), chol(S), lu(S), diag(S), max(S), sum(S)Sparse

S + A, S * A, S\A, A\SFull

inv - Inverse Matrixchol - Cholesky Faktorisierunglu - LU Faktorisierungmax - größtes Element jeder Spaltesum - Summe jeder Spalte

58


Das folgende Script-File 1.3.1 vergleicht das Lösen eines linearen Gleichungssystems in beiden Speichermodi. Gelöst wird ein 4000 x 4000 tridiagonales lineares Gleichungssystem sowohl imSparse- als auch im vollen Speichermodus.

Für n = 10 hat die Koeffizientenmatrix folgende Gestalt:

S =

(1,1) 2(2,1) -1(1,2) -1(2,2) 2(3,2) -1(2,3) -1(3,3) 2(4,3) -1(3,4) -1(4,4) 2(5,4) -1(4,5) -1(5,5) 2(6,5) -1(5,6) -1(6,6) 2(7,6) -1(6,7) -1(7,7) 2(8,7) -1(7,8) -1(8,8) 2(9,8) -1(8,9) -1(9,9) 2

(10,9) -1(9,10) -1

(10,10) 2

Koeffizientenmatrixim Sparsemodus

A =

2 -1 0 0 0 0 0 0 0 0-1 2 -1 0 0 0 0 0 0 00 -1 2 -1 0 0 0 0 0 00 0 -1 2 -1 0 0 0 0 00 0 0 -1 2 -1 0 0 0 00 0 0 0 -1 2 -1 0 0 00 0 0 0 0 -1 2 -1 0 00 0 0 0 0 0 -1 2 -1 00 0 0 0 0 0 0 -1 2 -10 0 0 0 0 0 0 0 -1 2

Die Koeffizientenmatrix A im Full-Modus

59


%--------------------------------------------------------------------------% Zeitvergleich -> Sparse vs. Full%--------------------------------------------------------------------------

n = 4000; e = ones(n,1); d = 2*e;%Sparse- und Full-Matrix generierenS = spdiags([-e,d,-e],[-1,0,1],n,n);tic;disp('Transform Sparse -> Full')A = full(S);trans_sp_full = toc% Rechte Seite des Gleichungssystems generierendisp('Gen -> b')b = ones(n,1); s = sparse(b);b_generated = toctic;%Sparsesystem mit dem Backslash-Operator lösendisp('Start -> Sparse')us = S\s;Sparse_time = toctic;%Fullsystem mit dem Backslash-Operator lösendisp('Start -> Full')uf = A\b;Full_time = toc

Output des Script-Files 1.3.1

Transform Sparse -> Full

trans_sp_full =

0.3130

Gen -> b

b_generated =

0.3130

Start -> Sparse

Sparse_time =

0

Start -> Full

Full_time =

22.0150

Script-File 1.3.1 Zeitvergleich Sparsematrix vs. Fullmatrix 60


1.3.2 Symmetrische und positiv definite Matrizen

Ist die Koeffizientenmatrix A symmetrisch und positiv definit, dann kann in einer LU-Faktorisierung U = LT

gesetzt werden, so dass gilt:

A = LTL.

Dabei ist L eine untere Dreiecksmatrix mit positiven Diagonalelementen, die im Allgemeinen aber keineEinsen in der Diagonalen hat. Eine solche Zerlegung heißt bekanntlich Cholesky-Faktorisierung. DieMATLAB-Funktion chol berechnet die Cholesky-Zerlegung.

b =

-150-150-350

00

-200-100-100-300

A =

-4 1 0 1 0 0 0 0 01 -4 1 0 1 0 0 0 00 1 -4 0 0 1 0 0 01 0 0 -4 1 0 1 0 00 1 0 1 -4 1 0 1 00 0 1 0 1 -4 0 0 10 0 0 1 0 0 -4 1 00 0 0 0 1 0 1 -4 10 0 0 0 0 1 0 1 -4

L = chol(-A)

2.0000 -0.5000 0 -0.5000 0 0 0 0 00 1.9365 -0.5164 -0.1291 -0.5164 0 0 0 00 0 1.9322 -0.0345 -0.1380 -0.5175 0 0 00 0 0 1.9319 -0.5546 -0.0092 -0.5176 0 0 0 0 0 0 1.8457 -0.5833 -0.1555 -0.5418 00 0 0 0 0 1.8417 -0.0519 -0.1716 -0.54300 0 0 0 0 0 1.9249 -0.5679 -0.01460 0 0 0 0 0 0 1.8315 -0.6014 0 0 0 0 0 0 0 0 1.8285

u = A \ b u =

85.7143126.3393157.142966.5179112.5000152.232167.8571104.9107139.2857

x =

85.7143126.3393157.142966.5179112.5000152.232167.8571104.9107139.2857

y = L‘ \ (-b); x = L \ y Die Matrix –A ist positiv definit. Der Aufrufchol(A) liefert folgende Fehlermeldung:

Error using ==> cholMatrix must be positive definite.

MATLAB-Notation: LT = L‘.

61


Gegeben sei das lineare Gleichungssystem Ax = b. Falls die Koeffizientenmatrix A symmetrisch undpositiv definit ist, dann kann das Gleichungssystem wie folgt gelöst werden:

1. Berechne die Cholesky-Zerlegung von A: A = LTL (MATLAB: L = chol(A))

2. Löse das untere Dreieckssystem LTy = b nach y (MATLAB: y = L‘ \ b)

3. Löse das obere Dreieckssystem Lx = y nach x (MATLAB: x = L \ y)

Hinweis: Ist die Koeffizientenmatrix symmetrisch und positiv definit, so verwendet der Backslash-Operatorautomatisch diesen Algorithmus; es sei denn, es gibt einen einfacheren.

Bemerkung 1.3.1:Die Verfahren, die hier für reelle Matrizen beschrieben wurden, haben komplexe Analoga und könnenfür den komplexe Fall entsprechend entwickelt werden.

62


1.3.3 Lösungsstrategien des Backslash-Operators

Der spezifische Algorithmus, der zum Lösen eines linearen Gleichungssystems durch den Operator x = A \ b verwendet wird, hängt -wie bereits erwähnt- von der Struktur der Koeffizientenmatrix A ab.Um die Struktur der Matrix A zu erkennen und den entsprechenden optimalen Algorithmus zu wählen,geht MATLAB wie folgt vor (im MATLAB Function Reference zur Funktion mldivide \ kann nachgelesenwerden, welcher Algorithmus in Abhängigkeit der im Folgenden aufgeführten Bedingungen ausgeführtwird):

1. Wenn A eine Sparse- und Diagonalmatrix ist, dann …

2. Wenn A schwach besetzt (sparse), quadratisch und eine Bandmatrix ist, dann …

3. Wenn A eine obere oder untere Dreiecksmatrix ist, dann …

4. Wenn A eine Permutation einer Dreiecksmatrix ist, dann …

5. Wenn A symmetrisch oder hermitisch ist und reelle positive Diagonalelemente hat, dann …

6. Wenn A eine Hessenbergmatrix ist, aber keine Sparsematrix, dann …

7. Wenn A eine quadratische Matrix ist, die nicht die Kriterien 1 bis 6 erfüllt, dann …

8. Wenn A nicht quadratisch ist, dann …

63


Wir wollen auf die effizienten Lösungsalgorithmen nicht näher eingehen, sondern merken uns:

In MATLAB löst man lineare Gleichungssysteme mit dem \ - Operator.Ist allerdings das System zu groß, zu müssen iterative Methoden benutztwerden (s. Kapitel 1.3.6).

Wichtig ist, dass für dünn besetzten Matrizen der Sparsemodus eingestellt wird.

64


1.3.4 Inverse Matrizen

Sei A eine reguläre Matrix. Dann können wir beide Seiten des linearen Gleichungssystems Ax = b mit der inversen Matrix A-1 multiplizieren und erhalten somit als Lösung des linearen Systems:

x = A-1b.

Das explizite Berechnen der Inversen einer regulären Matrix sollte allerdings vermieden werden, da es sehr zeitaufwending ist.

Merke:Lineare Gleichungssystem sollten nicht dadurch gelöst werden, dass die Systemmatrix A invertiert wird.

Ist es aber dennoch notwendig, die Inverse einer Matrix explizit zu kennen, so kann diese mit dem GAUSS-Verfahren berechnet werden. Es gilt nämlich:

Satz 1.3.1:Das Berechnen der Inversen A-1 einer regulären Matrix A ist äquivalent zum Lösen der n Gleichungs-systeme

Axi = ei, i = 1,…,n,

wobei ei der i-te Einheitsvektor und xi der i-te Spaltenvektor der inversen Matrix A-1 ist.

65


Beispiel 1.3.1:Wir betrachten die Matrix

66

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

−−

−−

−−

−−

−

=

410100000141010000014001000100410100010141010001014001000100410000010141000001014

A

A-1 =-0.2991 -0.0982 -0.0313 -0.0982 -0.0625 -0.0268 -0.0313 -0.0268 -0.0134-0.0982 -0.3304 -0.0982 -0.0625 -0.1250 -0.0625 -0.0268 -0.0446 -0.0268-0.0312 -0.0982 -0.2991 -0.0268 -0.0625 -0.0982 -0.0134 -0.0268 -0.0312-0.0982 -0.0625 -0.0268 -0.3304 -0.1250 -0.0446 -0.0982 -0.0625 -0.0268-0.0625 -0.1250 -0.0625 -0.1250 -0.3750 -0.1250 -0.0625 -0.1250 -0.0625-0.0268 -0.0625 -0.0982 -0.0446 -0.1250 -0.3304 -0.0268 -0.0625 -0.0982-0.0313 -0.0268 -0.0134 -0.0982 -0.0625 -0.0268 -0.2991 -0.0982 -0.0313-0.0268 -0.0446 -0.0268 -0.0625 -0.1250 -0.0625 -0.0982 -0.3304 -0.0982-0.0134 -0.0268 -0.0313 -0.0268 -0.0625 -0.0982 -0.0313 -0.0982 -0.2991

b = zeros(9,1); b(1)=1;b'

ans =

1 0 0 0 0 0 0 0 0

>> x=A\b

x =

-0.2991-0.0982-0.0313-0.0982-0.0625-0.0268-0.0313-0.0268-0.0134

A1 = zeros(9);for i = 9:-1:1

b = zeros(9,1);b(i) = 1;A1(:,i) = A\b

end

A1 = A\eye(9);

Das gleiche Ergebnis,aber eleganter formuliertund schneller in der Ausführung


Die MATLAB-Funktion inv berechnet die Inverse einer Funktion, wenn diese existiert.

>> inv(A)

ans =

-0.2991 -0.0982 -0.0312 -0.0982 -0.0625 -0.0268 -0.0313 -0.0268 -0.0134-0.0982 -0.3304 -0.0982 -0.0625 -0.1250 -0.0625 -0.0268 -0.0446 -0.0268-0.0313 -0.0982 -0.2991 -0.0268 -0.0625 -0.0982 -0.0134 -0.0268 -0.0312-0.0982 -0.0625 -0.0268 -0.3304 -0.1250 -0.0446 -0.0982 -0.0625 -0.0268-0.0625 -0.1250 -0.0625 -0.1250 -0.3750 -0.1250 -0.0625 -0.1250 -0.0625-0.0268 -0.0625 -0.0982 -0.0446 -0.1250 -0.3304 -0.0268 -0.0625 -0.0982-0.0313 -0.0268 -0.0134 -0.0982 -0.0625 -0.0268 -0.2991 -0.0982 -0.0313-0.0268 -0.0446 -0.0268 -0.0625 -0.1250 -0.0625 -0.0982 -0.3304 -0.0982-0.0134 -0.0268 -0.0312 -0.0268 -0.0625 -0.0982 -0.0313 -0.0982 -0.2991

Wiederholung:Der Rang einer Matrix A (Notation: Rang(A)) ist die Dimension des Spaltenraums von A. Eine quadratische(nxn)-Matrix heißt regulär, wenn Rang(A) = n ist; ansonsten singulär. Eine invertierbare Matrix ist eine reguläre Matrix und umgekehrt.Eine (mxn)-Matrix hat vollen Spaltenrang, wenn die Spalten linear unabhängig sind. Der volle Zeilenrang istanalog definiert. Eine Matrix A hat vollen Rang, wenn sie vollen Spalten- und Zeilenrang hat. Eine Matrixheißt rangdefekt, wenn ihr Rang nicht voll ist.

rank(A)

ans =

9

Der Rang einer Matrix wird in MATLAB mit der Funktion rank berechnet

67


Mit der Symbolic Toolbox lassen sich Matrixoperationen auch auf symbolischen Matrizen durchführen.

>> A1 = inv(sym(A))

A1 =

[ -67/224, -11/112, -1/32, -11/112, -1/16, -3/112, -1/32, -3/112, -3/224][ -11/112, -37/112, -11/112, -1/16, -1/8, -1/16, -3/112, -5/112, -3/112][ -1/32, -11/112, -67/224, -3/112, -1/16, -11/112, -3/224, -3/112, -1/32][ -11/112, -1/16, -3/112, -37/112, -1/8, -5/112, -11/112, -1/16, -3/112][ -1/16, -1/8, -1/16, -1/8, -3/8, -1/8, -1/16, -1/8, -1/16][ -3/112, -1/16, -11/112, -5/112, -1/8, -37/112, -3/112, -1/16, -11/112][ -1/32, -3/112, -3/224, -11/112, -1/16, -3/112, -67/224, -11/112, -1/32][ -3/112, -5/112, -3/112, -1/16, -1/8, -1/16, -11/112, -37/112, -11/112][ -3/224, -3/112, -1/32, -3/112, -1/16, -11/112, -1/32, -11/112, -67/224]

Symbolisches Rechnen mit MATLAB

>> syms a b c d>> A=[a b; c d]

A =

[ a, b][ c, d]

>> inv(A)

ans =

[ d/(a*d-b*c), -b/(a*d-b*c)][ -c/(a*d-b*c), a/(a*d-b*c)]

Symbolisches Rechnen, also das Rechnen mit Formel, und dasnumerische Rechnen, das heißt das Rechnen mit reellen oder auch komplexen Zahlen, sind die beiden Säulen, auf denen daswissenschaftliche Rechnen (Scientific Computing) basiert.Einfach gesagt ist das symbolische Rechnen der Versuch, dasRechnen mit Bleistift und Papier auf den Rechner abzubilden(vgl. [1], 389 ff).

68


1.3.5 Die Konditionszahl und Genauigkeit einer Lösung

Definition 1.3.1:Die Konditionszahl einer quadratischen Matrix A ist definiert als:

( ) .AAAcond 1−⋅=(1.3.1)

Ist A singulär, dann setzen wir ( ) .Acond ∞=

Da 1

00

1

−

≠≠

−

⎟⎟⎠

⎞⎜⎜⎝

⎛⋅⎟⎟

⎠

⎞⎜⎜⎝

⎛=⋅

xAx

minx

AxmaxAA

xx

misst die Konditionszahl einer Matrix das Verhältnis der maximalen Dehnung zur minimalen Stauchung. Klar ist: ( ) .Acond 1≥

Definition 1.3.2:Eine Matrix A heißt gut konditioniert, wenn ist. A heißt schlecht konditioniert, wenn

ist.( ) 1≈Acond

( ) 1>>Acond

69


Die Konditionszahl ist eine normabhängige Zahl, daher schreibt man cond2(A), wenn die 2-Norm zugrunde gelegt wird (allgemein condp(A) für die p-Norm), und cond∞(A) im Falle der Maximumnorm.

>> cond(A,inf)ans =

24

>> cond(A,1)ans =

24

>> cond(A)ans =

19.6157

>> norm(A)ans =

7.6712

>> norm(inv(A))ans =

2.5571

>> svd(A)ans =

7.67120.3911

>> svd(inv(A))ans =

2.55710.1304

>> A=[3 3;4 5]

A =

3 34 5

>> inv(A)

ans =

1.6667 -1.0000-1.3333 1.0000

>> inv(sym(A))

ans =

[ 5/3, -1][ -4/3, 1]

Beispiel 1.3.2: >> norm(A,1)ans =

8

>> norm(inv(A),1)ans =

3

>> norm(A,inf)ans =

9

>> norm(inv(A),inf)ans =

2.6667

Wir betrachten die Matrix

⎟⎟⎠

⎞⎜⎜⎝

⎛=

5433

A

mit der inversen Matrix

.A ⎟⎟⎠

⎞⎜⎜⎝

⎛−

−=−

3435

311 MATLAB Notation:

cond(A,2) = cond(A)norm(A,2) = norm(A)

Es gilt:

82

1211== ∑

== i

ij,jamaxA

32

12111 == ∑

==

−

iij,j

amaxA

7.6712A =2

2.5571A =−

21

92

121== ∑

==∞j

ij,iamaxA

382

121

1 == ∑==∞

−

jij,i

amaxA

Maximumnorm:Größte Zeilensumme

1-Norm:Größte Spaltensumme

2-Norm:Größter Singulärwert

70


Definition 1.3.3:Ein lineares Gleichungssystem Ax = b heißt schlecht konditioniert, wenn cond(A) sehr groß ist, und gutkonditioniert, wenn cond(A) relativ klein ist; und zwar cond(A) ≤ 10t/2, wenn t die Anzahl der verfügbaren Dezimalstellen ist (vgl. [1], S. 218).

Die Kondition der Koeffizientenmatrix A eines Gleichungssystems Ax = b hat einen entscheidenden Einfluss auf die numerische Lösung eines solchen Systems.

Sei eine Lösung des Gleichungssystem Ax = b, die mit einem numerischen Verfahren berechnet wurde.

x~

Wir setzen

bAr −= x~(1.3.2)

x~ ist eine exakte Lösung des Systems, wenn gilt: r 0=

Der Vektor heißt Residuenvektor.Definition 1.3.4:

bAr −= x~

Merke:Die Größe des Residuums ist alleine kein Maß für die Güte einer Näherungslösung.

71


Das wird durch folgende Ungleichung begründet:

( )brAx

xxcond

~≤

−(1.3.3)

Das Abschätzen der Genauigkeit einer numerischen Lösung erfodert neben dem Residuenvektor auch eine Abschätzung der Konditionszahl der Koeffizientenmatrix.

Beispiel 1.3.3:Gegeben seien die numerischen Näherungslösungen

⎟⎟⎠

⎞⎜⎜⎝

⎛

−=

08703410.

.~y⎟⎟⎠

⎞⎜⎜⎝

⎛

−=

00119990.

.~x und

des linearen Systems

254065909130217056307800

21

21.x.x..x.x.

=+=+

( ) ⎟⎟⎠

⎞⎜⎜⎝

⎛−=

00000000000010

..~yrDann gilt: ( ) ⎟⎟

⎠

⎞⎜⎜⎝

⎛−−

=00157200013430..~xr und

72


Die exakte Lösung ist allerdings

⎟⎟⎠

⎞⎜⎜⎝

⎛−

=11

x

und ist viel weiter entfernt von der exakten Lösung x als . x~y~

Beweis der Abschätzung (1.3.3):

Wegen

xxbAxAArA 111 −=−= −−− ~~

gilt:

( ) xrAxrAAAxrAbxx 11 cond~ =≤=− −−

Also:

( )brAx

xxcond

~≤

−

73


Eine berechnete Lösung ist also nur dann genau genug, wenn sowohl das relative Residuum als auch die Konditionszahl klein sind. In Beispiel 1.3.1 ist cond(A) = 2.1932e+06. Somit sagt die Kleinheit von

nichts über die relative Genauigkeit von bzw. aus. b/r x~ y~

>> A = [0.78 0.563;0.913 0.659]

A =

0.7800 0.56300.9130 0.6590

>> cond(A)

ans =

2.1932e+006

.~

Oft sind sind die Koeffizientenmatrix A oder die rechte Seite b eines linearen Gleichungssystems nicht exakt bekannt, da die Koeffizienten Messwerte sind oder auch mit dem Computer berechnet wurden und somit Rundungsfehler enthalten. Ist das der Fall, so löst man nicht das exakte Gleichungssystem Ax = b, sondern das gestörte System

x~~ bA =

Natürlich möchte man dann Abschätzungen dafür haben, wie nahe der berechnete Lösungsvektor zum wahren Vektor x liegt.x~

Störung der rechten Seite b:Sei x die exakte Lösung des Systems Ax = b und die Lösung des Systems Dann gilt:

x~ .x~ bbA ∆+=

( )bb

Ax

xx ∆≤

−cond

~

Beweis:

Mit ist und somit folgt:( ) bAxxxxAxAAxxAbb 1∆−=−−=−=−=∆ ~~~~

( ) xbAxbAAAxbAbxx 11 ∆=∆≤∆=− −− cond~74


Störung der Systemmatrix A:Sei x die exakte Lösung des Systems Ax = b und die Lösung des Systems Dann gilt:

x~ ( ) .x~ bAA =∆+

( )AA

Ax

xx ∆≤

−cond~

~

Beweis:

Wegen ist( ) xAAxAbAxx 11 ~~~ ∆=−=− −−

( ) xAA

AxAAxx 1 ~cond~~ ∆=∆≤− −

Die Koeffizientenmatrix A sei bis auf die Maschinengenauigkeit εM bekannt. Dann ist , wobei |εij| ≤ εM, und es gilt:

( )ijijij aa~ ε+= 1

.M AA ε≤∆

Wird das Gleichungssystem ohne weitere Fehler gelöst, so erhalten wir eine Lösung mit der Eigenschaft:

bA =x~~

( ) Mcond~~

εAx

xx≤

−

75


Beispiel 1.3.4:>> A = [1 1;1 1.01]b = [2;2.01]bs = [2;2.015]x = A\bxs = A\bs

A =1.0000 1.00001.0000 1.0100

b =2.00002.0100

bs =2.00002.0150

x =1.00001.0000

xs =0.50001.5000

(i) Die Koeffizientenmatrix sei gegeben durch

.. ⎟⎟

⎠

⎞⎜⎜⎝

⎛=

0122

b⎟⎟⎠

⎞⎜⎜⎝

⎛=

011111.

A und

.⎟⎟⎠

⎞⎜⎜⎝

⎛=

11

xDann hat das lineare Gleichungssystem Ax = b die Lösung

Eine kleine Störung der Komponente b2 der rechten Seite um0.25% von b zu

⎟⎟⎠

⎞⎜⎜⎝

⎛=

01522

.~b >> n = norm(bs-b)/norm(b)

n =0.0018

>> cond(A)

ans =402.0075

>> cond(A)*n

ans =0.7089

>> norm(x-xs)/norm(x)

ans =0.5000

bewirkt eine Verkleinerung der Kompnente x1 um 50% und eine Vergrößerung von x2 um ebenfalls 50%. Als Lösung des gestörtenSystems

bA ~x =

...~

⎟⎟⎠

⎞⎜⎜⎝

⎛=

5150

xerhalten wir nämlich:

76


(ii) Wir stören die Koeffizientenmatrix>> A = [1 1;1 1.01]b = [2;2.01]A = [1 1.005;1 1.01]x = A\bxs = A\bs

A =1.0000 1.00001.0000 1.0100

b =2.00002.0100

As =1.0000 1.00501.0000 1.0100

x =1.00001.0000

xs =- 0.01002.0000

⎟⎟⎠

⎞⎜⎜⎝

⎛+⎟⎟

⎠

⎞⎜⎜⎝

⎛=⎟⎟

⎠

⎞⎜⎜⎝

⎛=

0000500

011111

011100511 .

...~A

..~

⎟⎟⎠

⎞⎜⎜⎝

⎛−=

2010

xund erhalten als Lösung:

Auch hier bewirkt eine kleine Veränderung der Koeffizientenmatrix eine große Änderung der Lösung.

>> n = norm(As-A)/norm(A)

n =0.0025

>> cond(A)

ans =402.0075

>> cond(A)*n

ans =1.0025

>> norm(x-xs)/norm(xs)

ans =0.7106

Die Genauigkeit einer berechneten Näherungslösung kann durchSkalierung verbessert werden. Das soll folgendes Beispiel zeigen:

Das lineare System

⎟⎟⎠

⎞⎜⎜⎝

⎛=⎟⎟

⎠

⎞⎜⎜⎝

⎛⎟⎟⎠

⎞⎜⎜⎝

⎛εε1

001

2

1

xx

.⎟⎟⎠

⎞⎜⎜⎝

⎛=

11

xLösung:

ist für kleine ε schlecht konditioniert, da cond(A) = 1/ε. Somit können kleine Störungen der Koeffizientenmatrix A oder auch der rechten Seite b zu großen relativen Änderungen der Lösung führen. Stören wir z.B. die rechte Seite mit (0,-ε)T, so ist die Störung für kleine ε klein, die Lösung ändert sich aber ziemlich 77


stark zu .~⎟⎟⎠

⎞⎜⎜⎝

⎛=

01

x

Multiplikation der der zweiten Gleichung des Systems mit 1/ε führt aber zu dem äquivalenten System

.xx

⎟⎟⎠

⎞⎜⎜⎝

⎛=⎟⎟

⎠

⎞⎜⎜⎝

⎛⎟⎟⎠

⎞⎜⎜⎝

⎛11

1001

2

1

Dieses System ist perfekt konditioniert (cond(A) = 1) und eine kleine Störung der rechten Seite verursacht nun auch nur eine kleine Änderung der Lösung.

Merke:Eine Skalierung hat Einfluss auf die Konditionierung eines linearen Systems.

78


1.3.6 Iterative Lösungsmethoden für lineare Gleichungssystem

Iterative Verfahren lösen lineare Gleichungssysteme, indem sie mit einem Startwert beginnen und diesensukzessiv so lange verbessern, bis die gewünschte Genauigkeit der Lösung erreicht ist. In der Praxis wird die Iteration gestoppt, sobald das Residuum ||b – Ax|| oder ein anderes Fehlermaß hinreichend klein ist. Für dünn besetzte lineare Gleichungssystems (solche Systeme treten ja beim numerischen Lösen von Differentialgleichungen auf) sind iterative Methoden oft besser geeignet als direkte, da solche Methoden die dünne Struktur der Koeffizientenmatrix nicht zerstören. Sie sind ferner für schlecht konditionierte Systeme geeignet und reagieren weniger empfindlich auf fehlerbehaftete Koeffizienten als das Gauss-Verfahren. Der Nachteil ist, dass die Rechenzeit größer ist, als bei direkten Algorithmen. Aber ein weitererwichtiger Vorteil: Die iterativen Methoden funktionieren auch dann noch, wenn der Backslash-Operator wegen Speichermangel die Berechnung der Lösung beendet. Wir werden im Folgenden drei iterative Methoden vorstellen.

1.3.6.1 Das Gauss-Seidel-Verfahren

Der folgende Algorithmus berechnet eine Näherungslösung des quadratischen linearen Systems Ax = b, A = [aij], 1 ≤ i, j ≤ n.

Eingabe: A, b, Startvektor x0, Genauigkeit ε und die maximale Anzahl von Iterationen N.

Ausgabe: Näherungslösung

x~

( )mn

mm x,...,x~1== xx

oder, falls die maximale Anzahl von Iterationen durchlaufen wurde, die Fehlermeldung:

xN erfüllt nicht die geforderte Genauigkeit.

79


Pseudo-Code Gauss-Seidel-AlgorithmusNachteil der Index-Variante:Die Vektormultiplikationen werdenin Schleifen durchgeführt; dasverlängert die Rechenzeit erheblich.

Wesentlich besser geeignet für dasiterative Berechnen einer Lösungmit MATLAB ist die folgende Matrix-Variante des Gauss-Seidel-Alogrithmus.

For m = 0,1, …, N -1

For i = 1, …, n

⎟⎠⎞

⎜⎝⎛ −−= ∑∑

+=

−

=

++n

ij

mjij

i

j

mjiji

ii

mi xaxab

ax

1

1

1

11 1

end

If

output xm+1

breakend

endOutput: „No solution satiyfying the tolerance

condition obtained ofter N iterationsteps“

ε<−+

≤≤

mi

mini

xxmax 1

1

(1.3.4)

Gauss-Seidel-Algorithmus in Index-Notation: Aufgabe in den Labs wird sein, diesen Algorithmusin MATLAB zu implementieren.

80


Sei D = diag(diag(A)) - Diagonalmatrix, L = tril(A,-1) - strenge untere Dreiecksmatrix undU = triu(A,1) - strenge obere Dreiecksmatrix.

Dann gilt:

A = D + L + U

und

(D + L)x = b – Ux.

Damit erhalten wir die folgendeIterationsvorschrift:

Dxm+1 = b – Lxm+1 – Uxm,

also

(1.3.5) xm+1 =D-1( b – Lxm+1 – Uxm).

Diese Gleichung entspricht der Gleichung(1.3.4) in Matrix-Notation. Gleichung(1.3.5) können wir auch schreiben als

(1.3.6) xm+1 =(D + L)-1( b – Uxm).

For m = 0,1, …, N -1( ) ( )mm UxbLDx −+= −+ 11

If output xm+1

breakend



ε<−+ mm xx 1

Gauss-Seidel-Algorithmus in Matrix-Notation:Wird in MATLAB wesentlich schneller ausgeführtals die Index-Variante.

Gleichung (1.3.6) in MATLAB-Notation:

xm1 =(D + L)\( b – U*xm).

81


Sei C = -(D + L)-1U. Eine hinreichende Konvergenzbedingung für das Gauss-Seidel-Verfahren ist

(1.3.7) .1<C

Hierbei ist ||C|| irgendeine Matrix-Norm; z.B.:

∑∑= =

=n

i

n

jijc

1 1

2C

∑=

=n

iijj

cmax1

C

(1.3.8)

(1.3.9)

(1.3.10) ∑=

=n

jiji

cmax1

C

Frobenius Norm

Spalten-Summen Norm (1-Norm)

Zeilen-Summen Norm (Maximumnorm)

Sucessive Overrelaxation - SOR-Verfahren für Gauss-Seidel:

Wir führen nun einen sogenannten Relaxationsfaktor ω zur Beschleunigung der Konvergenz ein.

( ) ( ) .,mmmm 201111 <<−+−−= +−+ ωωω xUxLxbDx(1.3.11)

Für ω = 1 erhalten wir wieder das ursprüngliche Gauss-Seidel-Verfahren.

82


Durch einfaches Umformen der Gleichung (1.3.11) erhalten wir:

( ) ( )( ) mm xUDbxLD ωωω −−−=+ + 11

und somit

( ) ( )( )( )mm xUDbLDx ωωω −−−+= −+ 111(1.3.12)

For m = 0,1, …, N -1

If output xm+1

breakend



ε<−+ mm xx 1


xm1 =(D + L)\(ω*b – ((1 - ω)*D - ω * U)xm)( ) ( )( )( )mm xUDbLDx ωωω −−−+= −+ 111

Ein Richtwert für ω ist z.B.

ρω

−+=

112

wobei ρ der Spektral-Radius der Matrix C in(1.3.7) ist. Dieser Wert kann wegen Speicher-mangels nicht immer berechnet werden. Ein geeigneter Wert für ω muss dann durch Probierengefunden werden.

SOR-Algorithmus für das Gauss-Seidel-Verfahren

83


1.3.6.2 Das Jacobi-Verfahren

Die Gauss-Seidel Iteration ist ein Verfahren (Einzelschrittverfahren) der sukzessiven Berichtigung, da wir(i -1) Komponenten der neuen Iteration xm+1 bereits benutzen, um die i-te Komponente zu berechnen. Ein Verfahren der simultanen Berichtigung dagegen benutzt keine Komponente der neuen Iteration bevor alle Komponenten von xm+1 berechnet wurden. Ein solches Verfahren ist die Jacobi Iteration (Gesamt-schrittverfahren).

Iterationsvorschrift für das Jacobi-Verfahren:

(1.3.13) xm+1 = D-1( b – (L + U)xm) ⇔ xm+1 = D-1( b – (A - D)xm) .

For m = 0,1, …, N -1

( )( )mm xULbDx +−= −+ 11

If output xm+1

breakend



ε<−+ mm xx 1 Das Jacobi-Verfahren konvergiert für jedenStartwert x0 genau dann, wenn der Spektral-Radius von D-1(D – A) kleiner als 1 ist.

Die Jacobi Iteration hat den Vorteil, dass auf parallelen Prozessoren Gleichungen simultan in jedem Iterationsschritt berechnet werden können.

Pseudo-Code für die Jacobi-Iteration in Matrix-Notation.

84


Sucessive Overrelaxation - SOR-Verfahren für Jacobi:

Wie beim Gauss-Seidel-Verfahren führen wir ebenfalls einen Relaxationsfaktor ω zur Beschleunigung der Konvergenz ein.

( )( ) ( ) .,mmm 20111 <<−++−= −+ ωωω xxULbDx(1.3.14)

Für ω = 1 erhalten wir wieder das ursprüngliche Jacobi-Verfahren.

For m = 0,1, …, N -1

If output xm+1

breakend



ε<−+ mm xx 1


xm1 = ω *(D\(b – (L + U)xm)) + (1 - ω)*xm ( )( ) ( ) mmm xxULbDx ωω −++−= −+ 111

Ein optimaler Wert für ω ist

maxmin

2ωω

ω+

=

wobei ωmin der kleinste und ωmax der größte Eigen-wert der Matrix D-1A ist, falls diese positive reelle Eigenwerte besitzt. Dieser Wert kann wegen Spei-chermangel nicht immer berechnet werden. Ein geeigneter Wert für ω muss dann wieder durch Probieren gefunden werden.

SOR-Algorithmus für das Jacobi-Verfahren

85


1.3.6.3 Die Methode der konjugierten Gradienten

Diese Methode ist anwendbar auf lineare Systeme mit symmetrischen und positiv definiten Koeffizienten-matrizen A. Ist die symmetrische Matrix A positiv definit, dann hat die quadratische Funktion

( ) nTT IR,q ∈−= xbxAxxx21(1.3.14)

ihr eindeutiges Minimum an der Stelle x* an der gilt Ax* = b. Damit ist das Lösen eines linearen Systems,dessen Koeffizientenmatrix symmetrisch und positiv definit ist, gleichbedeutend mit der Aufgabe, das Minimum der quadratischen Funktion q zu bestimmen. Mehrdimensionale Optimierungsmethoden berechneneine neue Näherung xk+1 = xk + αsk indem sie zu einer Schrittrichtung sk eine Schrittweite α festlegen, sodass die Zielfunktion q(xk + αsk) entlang sk minimal wird. Für die in (1.3.14) definierte Funktion q gilt nun:

( ) ( )xrAxbx =−=∇− q(1.3.15) (negativer Gradient ist der Residuenvektor)

( ) ( ) ( ) ( ) ( ) kTkk

Tkk

Tkkk

Tkkkk q

ddqq

dd srsbAxsxsxsxsx 1110 +++ −=−=∇=++∇=+= α

ααα

α(1.3.16)

Mit (1.3.16) folgt, dass das Minimum über α dort angenommen wird, wo das neue Residuum senkrechtzur Schrittrichtung steht. Ferner gilt:

( ) ( ) kkkkkkk AsrAsAxbsxAbr ααα −=−−=+−=+1(1.3.17)

86


Setzen wir das in (1.3.16) ein so folgt:

( ) kTkk

Tkk

Tkk AsssrsAsr αα −=−=0(1.3.18)

Lösen wir die Gleichung in (1.3.18) nach α auf, so ist:

kTk

kTk

Asssr

=α(1.3.19)

Damit erhalten wir die konjugierte Gradientenmethode, mit der symmetrische positiv definite lineareGleichungssysteme gelöst werden können.

Sei x0 der Startpunkt und s0 = r0 = b – Ax0, dann werden folgende Schritte wiederholt, bis diegewünschte Genauigkeit erreicht ist:

1.k

Tk

kTk

k Asssr

=α

2. kkkk sxx α+=+1

3. kkkk Asrr α−=+1

(Schrittweite)

(Approximierte Lösung)

(Residuum)

4.k

Tk

kTk

k rrrr 11

1++

+ =β

(Schrittrichtung)5. kkkk srs 111 +++ += β

87


Die Schrittweite α kann auch noch anders berechnet werden. Mit

( ) kTkkk

Tkk

Tkkk

Tkkkk

Tkk

Tk rrrrsrrrsrrsr =⋅+=+=+= −− 011 βββ

erhalten wir nämlich:

kTk

kTk

k Assrr

=α

Für die konjugierte Gradientenmethode müssen wir keine eigene Funktion schreiben, da dieses Verfahrenmit den Funktionen pcg und cgs bereits in MATLAB realisiert ist.

Aufruf: pcg(A,b,tol,maxit) bzw. cgs(A,b,tol,maxit),

A Koeffizientenmatrixb rechte Seite des Systemstol Toleranz (Genauigkeit)maxit Maximale Anzahl an Iterationen

Das P in der pcg-Funktion steht für die Konvergenzbeschleunigung des konjugierten Gradientenverfahrens;pcg – Preconditioned Conjugate Gradients Method. Eine schnellere Konvergenz wird durch eine sogenannteVorkonditionierung der Koeffizientenmatrix A erzielt. Ziel der Vorkonditionierung: Reduktion der Konditionszahl cond(A) durch Transformation des SystemsAx = b in A*x = b* mit einer leicht zu invertierbaren regulären Matrix M.

88


oderTransformation: bMxAMM 11 −−− =*TbMAxM 11 −− =

mit .,, bMbxMx*AMMA* 1TT1 −−− ===

Die Funktionsnamen bleiben gleich, nur das jetzt noch ein Argument im Aufruf hinzugefügt wird.

Aufruf mit Vorkonditionierung: pcg(A,b,tol,maxit,M) bzw. cgs(A,b,tol,maxit,M),

A Koeffizientenmatrixb rechte Seite des Systemstol Toleranz (Genauigkeit)maxit Maximale Anzahl an Iterationen M Vorkonditionierer

Aufruf der Funktion cgs in MATLABmit Vorkonditionierung

M = diag(diag(A));u = pcg(A,b,10^(-10),10000,M);

Aufruf der Funktion pcg in MATLABmit Vorkonditionierung

M = diag(diag(A));u = cgs(A,b,10^(-10),10000,M);

Vorkonditionierer MVorkonditionierer M

89


1.3.6.4 Vergleich der iterativen Methoden

Im Folgenden werden die beschrieben Verfahren bzgl. ihrer Konvergenzeigenschaften miteinanderverglichen. Dazu soll ein Gleichungssystem gelöst werden, dessen Koeffizientenmatrix A eine schwachbesetzte 20,000 x 20,000 Matrix ist; und zwar:

Hauptdiagonale - die ersten 20,000 PrimzahlenNebendiagonalen - aij = 1 ⇔ | i – j | = 2n, n = 0,1,2,…,14.

Ein Speichern der Matrix A im Full-Modus würde ca. 1,6 GB Hauptspeicher benötigen. Als rechte Seitedes Systems wählen wir den Spaltenvektor b, der als Einträge an allen Stellen die Zahl 100 hat. Dieses System kann mit dem Backslash-Operator nicht gelöst werden, da MATLAB wegen Speichermangelden Lösungsvorgang abbricht.

??? Error using ==> mldivideOut of memory. Type HELP MEMORY for your options.

Da die meisten Matrixeinträge gleich Null sind, kann die Matrix aber im Sparse-Modus gespeichert werden.

Im folgenden Script-File wird die Koeffizientenmatrix A erzeugt und die verschiedenen Verfahren werdenin Abhängigkeit eines Parameters aufgerufen.

90


%-------------------------------------------------------------------------% Testing Iteration Methods solving linear Systems Ax = b%% Input: meth - 1 Gauss-Seidel Index, 2 Gauss-Seidel Matrix% 3 SOR - GS, 4 Jacobi, 5 SOR - Jacobi % 6 Conjugate Gradients % 7 Preconditioned Conjugate Gradients (PCG)% tol - Tolerance% N - max. Iterations% w - Relaxation-Parameter omega%-------------------------------------------------------------------------function it_method_test(meth,tol,N,w)%The first 20,000 prime numbersp = primes(224740);n = length(p);d = [];for i = 14:-1:0

d = [d,-2^i];endd = [d,0];for i = 0:14

d = [d,2^i];endO = ones(n,15);B(1:n,1:15) = O; B(:,16) = p'; B(1:n,17:31) = O;% Generating a 20,000 x 20,0000 Matrix having the first 20,000% prime numbers as diagonalA = spdiags(B,d,n,n);b = 100*ones(n,1);b = sparse(b);x0 = b;tic;switch methcase 1

disp(' ') disp('Method: Gauss-Seidel (Index)')u = gs_ind(A,b,x0,tol,N);

case 2disp(' ') disp('Method: Gauss-Seidel (Matrix)')u = gs_mat(A,b,x0,tol,N);

case 3disp(' ') disp('Method: SOR -> Gauss-Seidel (Matrix)')disp(' ')display(['Relaxation: ',num2str(w)])u = SOR(A,b,x0,tol,N,w);

case 4disp(' ') disp('Method: Jacobi (Matrix)')u = jacobi(A,b,x0,tol,N);

case 5disp(' ') disp('Method: SOR - Jacobi (Matrix)')disp(' ')display(['Relaxation: ',num2str(w)])u = SOR_jacobi(A,b,x0,tol,N,w);

case 6disp(' ') disp('Conjugate Gradients Squared Method')% Using MATLAB built-in-function pcgu = pcg(A,b,tol,N);Time = toc

case 7disp(' ') disp('Preconditioned Conjugate Gradients Squared Method')% Using MATLAB built-in-function pcg with preconditioner MM = diag(diag(A));u = pcg(A,b,tol,N,M);Time = toc

end

Script-File 1.3.2 Test für iterative Methoden

91


2 1 1 0 1 0 0 0 1 0 …1 3 1 1 0 1 0 0 0 1 …1 1 5 1 1 0 1 0 0 0 …0 1 1 7 1 1 0 1 0 0 …1 0 1 1 11 1 1 0 1 0 …0 1 0 1 1 13 1 1 0 1 …0 0 1 0 1 1 17 1 1 0 …0 0 0 1 0 1 1 19 1 1 …1 0 0 0 1 0 1 1 23 1 …0 1 0 0 0 1 0 1 1 29 …. .. .. .

2 1 1 0 1 0 0 0 1 0 …1 3 1 1 0 1 0 0 0 1 …1 1 5 1 1 0 1 0 0 0 …0 1 1 7 1 1 0 1 0 0 …1 0 1 1 11 1 1 0 1 0 …0 1 0 1 1 13 1 1 0 1 …0 0 1 0 1 1 17 1 1 0 …0 0 0 1 0 1 1 19 1 1 …1 0 0 0 1 0 1 1 23 1 …0 1 0 0 0 1 0 1 1 29 …. .. .. .

>> it_method_test(1,10^(-10),10000,1)

Method: Gauss-Seidel (Index)start_it = 0.0940step = 0time = 0.0940step = 1time = 282.0630step = 2time = 544.7660step = 3time = 807.7030step = 4time = 1.0704e+003step = 5time = 1.3325e+003step = 6time = 1.5939e+003step = 7time = 1.8554e+003

.

.

.step = 24time = 6.3073e+003Total_Time = 6575Number of iterations : 24

Die ersten Einträge der Koeffizientenmatrix A

Das Gauss-Seidel-Verfahren in Index-Notationbenötigt ~ 1 h 50 min um die erfoderlichen 24Iterationen zu berechnen.

92


>> it_method_test(2,10^(-10),10000,1)

Method: Gauss-Seidel (Matrix)

Time =

1.9840

Number of iterations: 24

Das Gauss-Seidel-Verfahren in Matrix-Notation benötigt nur~ 2 sec, um die erfoderlichen 24 Iterationen zu berechnen.

Folgerung:Wenn möglich, sollte die Matrix-Notation in MATLAB benutzt werden, um Rechenzeit zu sparen.

>> it_method_test(3,10^(-10),10000,1.05)

Method: SOR -> Gauss-Seidel (Matrix)

Relaxation: 1.05

Time =

3.5460


Das Gauss-Seidel-Verfahren mit SOR in Matrix-Notation benötigt zwar ~ 3.5 sec; allerdings nur 16 Iterationen.

Der Relaxationsfaktor ω = 1.05 wurde durch Probieren gefunden. Das Berechnen des Spektralradius der Matrix C = -inv(D+L)U ist wegen Speichermangel nicht möglich.

??? Error using ==> invOut of memory. Type HELP MEMORY for your options.

93


>> it_method_test(4,10^(-10),10000,1)

Method: Jacobi (Matrix)

Time =

23.9840

Anzahl Iterationen: 203

Das Jocobi-Verfahren (Gesamtschrittverfahren) ohne SOR in Matrix-Notation benötigt ~ 24 sec und 203 Iterationen, um eine approximierende Lösung mit der geforderten Genauigkeitzu berechnen.

>> it_method_test(5,10^(-10),10000,0.84)

Method: SOR - Jacobi (Matrix)

Relaxation: 0.84

Time =

7.9530


Das Jacobi-Verfahren mit SOR in Matrix-Notation benötigt dage-gen nur ~ 8 sec und nur 62 Iterationen.

Der Relaxationsfaktor ω = 0.84 wurde durch Probieren gefunden.

>> it_method_test(5,10^(-10),1000000,0.92)


Relaxation: 0.92

Time =

11.4370


>> it_method_test(5,10^(-10),1000000,0.7)


Relaxation: 0.7

Time =

9.8120


Jacobi-Verfahren mit SOR: Unterschiedlich Relaxationsfaktoren ω 94


>> it_method_test(6,10^(-10),10000,1)

Conjugate Gradients Squared Methodpcg converged at iteration 1881 to a solution with relative residual 1e-010Time =

106.9690

Das konjugierte Gradientenverfahren benötigt ~ 107 sec und 1881 Iterationen, um eine approximierende Lösung mit der geforderten Genauigkeit zu berechnen.

>> it_method_test(7,10^(-10),10000,1)

Preconditioned Conjugate Gradients Squared Methodpcg converged at iteration 12 to a solution with relative residual 1.8e-011Time =

0.8590

Das vorkonditionierte konjugierte Gradientenverfahren benötigt nur ~ 1 sec und 12 Iterationen.

Dabei wurde die Diagonale der Koeffizientenmatrix A für die Vorkonditionierung benutzt; also M = diag(diag(A)).

95


Zusammenfassung:

Verfahren Iterationen Zeit

Gauss-Seidel in Index-Notationohne SOR

24 ~ 1h 50 min

Gauss-Seidel in Matrix-Notationohne SOR

24 ~ 2 sec

Gauss-Seidel in Matrix-Notationmit SOR

16 ~ 3.5 sec

Jacobi in Matrix-Notationohne SOR

203 ~ 24 sec

Jacobi in Matrix-Notationmit SOR

62 ~ 8 sec

Konjugiertes Gradientenverfahren 1881 ~ 107 sec

Vorkonditionierteskonjugiertes Gradientenverfahren

12 ~ 1 sec

96


Wir wenden nun die iterativen Verfahren auf Gleichungssysteme an, die bei der Diskretisierung des Laplace-Operators im R2 entstehen. Wie wir aus dem Kapitel 1.1 Erste Motivation wissen, hat die Koeffizientenmatrix A dann folgendes Aussehen:

NNIR ×∈

⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜

⎝

⎛

−−

−−

=

410141

141

014

OO

O

B

⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜

⎝

⎛

=

BIIBI

IBIIB

0

0

OO

O

A mit

Wir wählen 6,400 innere Knotenpunkte und erhalten somit eine 6,400 x 6,400 dünne besetzte Koeffizientenmatrix A. Die rechte Seite b des Systems enthält die Temperaturverteilung auf dem Plattenrand. Die Genauigkeit ist tol = 0.0001.

Method: Gauss-Seidel (Matrix)

Time =44.0470


Das Gauss-Seidel-Verfahren in Matrix-Notation benötigt~ 44 sec und 5268 Iterationen.

97


Anders als in der vorhergehenden Untersuchung können wir nun den Spektralradius ρ der Matrix C = -(D + L)-1U mit MATLAB ermitteln; nämlich: ρ = 0.9985.

Damit ist ω = 2/(1+(1-0.9985)^0.5) = 1.9254.


Relaxation: 1.9254

Time =3.4060


Das Gauss-Seidel-Verfahren in Matrix-Notation mit SOR benötigt ~ 3.5 sec und nur 222 Iterationen.

Andere Werte für ω liefern mehr Iterationen.


Relaxation: 1.8165

Time =10.4840



Relaxation: 1.5

Time =31.1880



Relaxation: 1.99

Time =23.2820


98


Das Jacobi-Verfahren in Matrix-Notation benötigt ~ 53 sec und 9590 Iterationen.

Wegen ω = 2/(1.9992+0.0008) = 1 bringt das SOR-Verfahrenkeine Verbesserung des Konvergenzverhaltens.

Method: Jacobi (Matrix)

Time =52.5780



Relaxation: 0.9

Time =63.0160



Relaxation: 1.0024

Time =59.2820


No solution after max. iterations


Relaxation: 0.8

Time =68.8280


99


Conjugate Gradients Squared Methodcgs converged at iteration 125 to a solutionwith relative residual 8.4e-005

Time =1.1100

Das konjugierte Gradientenverfahren cgs benötigt ~ 1 sec und 125 Iterationen, um eine approximierende Lösung mit der geforderten Genauigkeit zu berechnen.

Mit der Vorkonditionierung M = 0.25*(-A) erhalten wir sogar das folgende Ergebnis:

Preconditioned Conjugate Gradients Squared Methodpcg converged at iteration 1 to a solution with relative residual 2.9e-015

Time =0.2970

Mit der Vorkonditionierung M = diag(diag(-A)) erhalten wir:

Preconditioned Conjugate Gradients Squared Methodpcg converged at iteration 139 to a solution with relative residual 9.8e-005

Time =0.9690

100


1.4 Lineare Ausgleichsrechnung (Linear Curve fitting)

Die Ausgleichsrechnung, in der Statistik auch unter dem Begriff Regressionsmethode bekannt, ist ein wichtiges Verfahren, um aus Messwerten funktionale Zusammenhänge herzuleiten. Gegeben seien mBeobachtungen (Messwerte) (ti,bi), i = 1,…,m, der Zustandsgrößen (t,y), t ∈ Rk, y ∈ R. Sei ferner

( )xt,fy,IRIRIR:f nk =→×(1.4.1)

eine Funktion (Modellfunktion) mit n unbekannten Parametern x = (x1,x2,…,xn)T. Ist die Funktion linear in x, so können wir f schreiben als

( ) ( ) ( ) ( ) ( ) ( ) ,t,...,t,tx...xx,f Tk

Tnn xxttttxt ⋅=⋅=+++= 212211 ϕϕϕϕϕ(1.4.2)

wobei ϕ = (ϕ1,ϕ2,…,ϕn), mit bekannten Funktionen ϕi: D ⊂ Rk → R. Falls die Funktion f nicht linear in x ist, so erhalten wir ein nichtlineares Ausgleichsproblem.

Wegen Mess- und Beobachtungsfehler werden immer mehr Messungen durchgeführt als Parameter zu bestimmen sind. In der Praxis gilt im Allgemeinen sogar m >> n. Werden nun die Messwerte in die Funktion f eingesetzt, so müssen Parameter x = (x1,x2,…,xn)T bestimmt werden, so dass gilt:

( ) ( ) ( ) ( ) m,...,i,t,...,tx...x,fb Tik

iinniii 1111 =⋅=++== xttxt ϕϕϕ(1.4.3)

(1.4.3) ist ein lineares Gleichungssystem mit m Gleichungen und n unbekannten Parametern xi. In Matrix-Notation können wir dieses System schreiben als:

101


( ) ( ) ( )( ) ( ) ( )

( ) ( ) ( ) ⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

mnmnmm

n

n

b

bb

x

xx

MM

L

MM

L

L

2

1

2

1

21

22221

11211

ttt

tttttt

ϕϕϕ

ϕϕϕϕϕϕ

(1.4.4)

Da m > n handelt es sich um ein überbestimmtes Gleichungssystem, das im Allgemeinen inkonsistent ist, das heißt, es gibt keine Lösung x mit Ax = b, wobei A die Koeffizientenmatrix aus (1.4.4) ist. Daher wird in der Ausgleichsrechnung zu einem vorgegebenen Funktionstyp f(t,x) der Parametervektor x gesucht, der den Residuenvektor r = Ax – b minimiert. Bei Ausgleichsproblemen verwendet man die Euklidische Norm und vereinfacht das Problem noch dadurch, dass die Fehlerquadrate betrachtet werden. Dann bestimmt man die Parameter x = (x1,x2,…,xn)T so, dass die Funktion

( ) ( ) ( ) ( ) ( )( )∑=

−+++==m

iiinniin bx...xxx,...,xFF

1

222111 tttx ϕϕϕ(1.4.5)

an der Stelle x = (x1,x2,…,xn)T ein Minimum hat. In Matrix-Notation lautet die Ausgleichsaufgabe:

Gegeben sei eine mxn-Matrix A mit m > n und ein m-Vektor b. Gesucht ist ein n-Vektor x, der folgendes Problem löst:

2

2bAx

x−

∈ nIRMin

102


Klar ist: Wenn die Abstandsquadrate für einen Parametervektor x minimal werden, so auch der Abstand. Das heißt, die Probleme

2

2bAx

x−

∈ nIRMin 2

bAxx

−∈ nIR

Minund

haben dieselbe Lösung (die Wurzelfunktion ist eine streng monoton wachsende Funktion für positive Zahlen).

Aus der Vorlesung Mathematics II wissen wir, dass eine notwendige Bedingung für ein Minimum der Funktion F im Punkt x ist, dass x ein stationärer (kritischer) Punkt ist. Also muss gelten:

( ) ( ) ( ) ( ).,...,xF,...,

xFF

n

001

=⎟⎟⎠

⎞⎜⎜⎝

⎛∂∂

∂∂

=∇ xxx(1.4.6)

Wir erhalten somit folgendes nxn-System:

( ) ( ) ( ) ( )( ) ( ) ,n,...,j,bx...xxxF m

iijiinnii

j

1021

2211 ==−+++=∂∂

∑=

ttttx ϕϕϕϕ(1.4.7)

welches äquivalent ist mit

( ) ( ) ( ) ( ) ( ) ( ) ( ) n,...,j,bx...xxm

iiij

m

iijinn

m

iiji

m

iiji 1

11122

111 ==+++ ∑∑∑∑

====

ttttttt ϕϕϕϕϕϕϕ(1.4.8)

103


Ferner gilt, dass die Funktion F im stationären Punkt x ein Minimum annimmt, da die Hesse-Matrix HF(x) positiv definit ist.

Das Gleichungssystem (1.4.8) heißt Normalgleichungssystem und lautet in Matrix-Notation:

(1.4.9) bAAxA TT =

Das Lösen eines linearen Ausgleichsproblems ist somit äquivalent zur Aufgabe, das Normalgleichungs-system (1.4.9) zu lösen. Dies hat aber immer eine Lösung, da ATb im Bildraum von ATA liegt. Die Lösung ist eindeutig, wenn der Rang der Matrix A gleich n ist. In diesem Fall ist die eindeutige Lösung des Ausgleichproblems gegeben durch

( ) bAbAAAx TT +− == 1(1.4.10)

Die Matrix A+ = (ATA)-1AT wird verallgemeinerte Inverse, Pseudoinverse oder auch MOORE-PENROSE-Inverse von A genannt.

Das Normalgleichungssystem ist ein lineares nxn-Gleichungssystem und somit mit den Methoden, die wirin den vorangehenden Kapiteln erläutert haben, lösbar. Da die Koeffizientenmatrix ATA symmetrisch und im regulären Fall positiv definit ist, kann mit der CHOLESKY-Zerlegung Zeit und Speicherplatz eingespart werden.

Das Lösen eines linearen Ausgleichsproblems durch Lösen des Normalgleichungssystems ist aber im Allgemeinen nicht zu empfehlen, da es Orthogonalisierungsverfahren (QR- und SVD-Verfahren) gibt, die numerisch wesentlich bessere Eigenschaften haben.

104


Eine Situation, in der das Lösen des Normalgleichungssystem vorgezogen wird:

Liegen viel mehr Beobachtungen (Messwerte) als Parameter vor, so ist das Lösen des Normalsystemsvorteilhaft. Beispiel: 10,000 Messwerte (m = 10,000) und zwei Parameter (n = 2). Dann ist ATA eine 2x2-Matrix, während A eine 10,000x2-Matrix ist.

Numerische Probleme beim Verwenden der Normalgleichungsmethode:

Wir betrachten die Matrix

,⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛=

εε0

011

A

wobei ε eine kleine positive Zahl ist, die kleiner als die Quadratwurzel aus der Maschinengenauigkeit εMist. Damit gilt in der Gleitpunktarithmetik: fl(ε2) = 0. Für die Matrix ATA erhalten wir dann:

( ) .fl TT⎟⎟⎠

⎞⎜⎜⎝

⎛=⇒⎟⎟

⎠

⎞⎜⎜⎝

⎛+

+=

1111

1111

2

2

AAAAε

ε

In der Gleitpunktarithmetik ist die Matrix ATA also singulär. Merke: In der Gleitpunktarithmetik gehen bei der expliziten Berechnung von ATA wichtige Information verloren. Das Normalsystem ist auch sehr viel anfälliger gegenüber Störungen, denn es gilt: ( ) ( ) .condcond T 2

22 AAA =

Diese Sensitivität kann die Genauigkeit der mittels des Normalsystems berechneten Lösung über das Maß, welches die Messdaten vermuten lassen, hinaus verschlechtern.

105


Orthogonale Transformationen

Betrachten wir den Fall, dass die Koeffizientenmatrix A eine Dreiecksmatrix ist; und zwar sei

,⎟⎟⎠

⎞⎜⎜⎝

⎛=

0T

A

wobei T eine nxn obere Dreiecksmatrix ist. Das Ausgleichsproblem lautet in diesem Fall:

.Min n

IRn

2

200 ⎟⎟⎠

⎞⎜⎜⎝

⎛−⎟⎟

⎠

⎞⎜⎜⎝

⎛∈ b

bx

Tx

Als Residuenvektor erhalten wir dann

( )mnnnnnnnnn b,...,b,bxT...xT,...,bxT...xT −−−++−++=⎟⎟⎠

⎞⎜⎜⎝

⎛−⎟⎟

⎠

⎞⎜⎜⎝

⎛= +11111111

00 bb

xT

r

2

20

2

2

2

2bbTxr +−= n⇒ (1.4.11)

Auf den Summanden ||b0||22 haben wir keinen Einfluss und können ihn somit nicht minimieren. Der erste Summand in (1.4.11) kann aber zu Null gemacht werden, indem wir das lineare Gleichungssystem Tx = bn lösen.

106


Da T eine obere Dreiecksmatrix ist, erhalten wir die Lösung x durch Rückwärtseinsetzen, falls die Diagonalelemente der Matrix T von Null verschieden sind. Ferner ist:

.2

20

2

2br =(1.4.12)

Wir könnten jetzt auf den Gedanken kommen, die Ausgangsmatrix A unseres Ausgleichproblems mittels GAUSS-Transformation auf eine Dreiecksmatrix T zu transformieren, um dann das transformierte SystemTx = bn zu lösen. Das geht aber nicht, da die GAUSS-Transformation nicht längeninvariant bzgl. der Euklidische Norm ist. Das heißt, das Minimum des Ausgangsproblems ist im Allgemeinen nicht gleich der Lösung des transformierten Problems. Hier kommen nun die orthogonalen Transformationen ins Spiel.

Orthogonale Transformationen sind Transformationen, die die Euklidische Norm beibehalten.

Wiederholung:Eine Quadratische Matrix heißt orthogonal, falls gilt:

I== QQQQ TT

Orthogonale Matrizen können Vektoren auf verschiedene Weisen transformieren, z.B. drehen oder spiegeln. Sie bewahren aber immer die Länge des Vektors, denn es gilt:

( ) .TT 2

2

2

2xxxQxQxQx ===

107


Orthogonale Matrize sind im numerischen Rechnen von großer Bedeutung. Durch die Invarianz gegen-über der 2-Norm können Fehler nicht verstärkt werden.

Es gibt in der numerischen linearen Algebra einen Algorithmus, der wichtiger ist als alle anderen: Der Algorithmus zur QR-Zerlegung einer Matrix. Die QR-Zerlegung gehört zu den stabilsten Algorithmen, da cond2(Q) = 1 (vgl. [1]).

Lösen der linearen Ausgleichsaufgabe mit der QR-Zerlegung, falls A vollen Rang hat

Sei A eine beliebige mxn-Matrix mit m > n. Dann gibt es eine orhtogonale mxm-Matrix Q und eine obere nxn Dreiecksmatrix R, so dass gilt:

.⎟⎟⎠

⎞⎜⎜⎝

⎛=

0R

QA

Eine solche QR-Faktorisierung transformiert ein lineares Ausgleichsproblem in ein dreiecksförmiges System mit der selben Lösung. Es gilt nämlich:

2

2

2

2

2

2 00bQx

Rbx

RQbAx T−⎟⎟

⎠

⎞⎜⎜⎝

⎛=−⎟⎟

⎠

⎞⎜⎜⎝

⎛=−

Wir teilen die Matrix Q in zwei Matrizen Q1 und Q2 auf, wobei Q1 aus den ersten n Spalten und Q2 aus denrestlichen m – n Spalten besteht.

108


Wir erhalten damit die sogenannte reduzierte QR-Zerlegung:2

22

1

0 ⎟⎟⎠

⎞⎜⎜⎝

⎛−⎟⎟

⎠

⎞⎜⎜⎝

⎛bQbQ

xR

T

T

(1.4.13)

Um das Minimum unseres Ausgleichspoblems zu finden müssen wir also

Lösungsalgorithmus für das lineare Ausgleichsproblem (A hat vollen Rang)

1. Berechne die reduzierte QR-Zerlegung von A: A = Q1R

2. Löse das obere Dreieckssystem nach xbQRx T1=

(1.4.14) bQRx T1=

nach x auflösen. Ferner ist

.T 2

22

2

2bQr =(1.4.15)

% ---------------------------------------------------------------% Linear Curve Fitting with QR-Decomposition% Input: A mxn-Matrix, b m-Columnvector% Output: x n-Solutionvector%---------------------------------------------------------------function [x] = LAQR(A,b);[Q1,R] = qr(A,0);x = R\(Q1‘*b);

MATLAB-Implementierung des Lösungsalgorithmus

Function-File 1.4.1 Löst Ausgleichsaufgabe mit QR-Zerlegung109


Kommen wir endlich zur Anwendung und zu einem ersten Beispiel.

Beispiel 1.4.1:Eine chemische Reaktion wird bei verschiedenen Temperaturen durchgeführt. Die Vollständigkeit der Reaktion ist von der Temperatur abhängig. Folgende Messwerte wurden erfasst.

110

t (°C) b(%)

150 77.4

150 76.7

150 78.2

200 84.1

200 84.5

200 83.7

250 88.9

250 89.2

250 89.7

300 94.2

300 94.7

300 95.9

Wir wollen untersuchen, ob die Messdaten mit einer Geraden, oder mit einemquadratischen Polynom besser beschrieben werden.

1. Gerade:Modellfunktion f(t,x) = x1 + x2t. Für A und b erhalten wir:

A =1 150 1 150 1 150 1 200 1 200 1 200 1 250 1 250 1 250 1 300 1 300 1 300

b =77.400076.700078.200084.100084.500083.700088.900089.200089.700094.200094.700095.9000

A= [1 150;1 150;1 150;1 200;1 200;1 200;1 250;1 250;1 250;1 300;1 300;1 300];

b =[77.4;76.7;78.2;84.1;84.5;83.7;88.9;89.2;89.7;94.2;94.7;95.9];

x = LAQR(A,b)

x =60.48330.1153

Die Gerade, die die Messdaten im Sinne derMethode der kleinsten Quadrate am bestenapproximiert, ist somit y = 60.4833 + 0.1153t.


2. Quadratisches Polynom (Version 1):Modellfunktion f(t,x) = x1 + x2t + x3t2. Für A und b erhalten wir:

Parameter: x1 = 55.7333; x2 = 0.16033; x3 = -0.0001

Best fitting curve: f(t) = (55.7333)*1 + (0.16033)*t + (-0.0001)*t^2

A =1 150 225001 150 225001 150 225001 200 400001 200 400001 200 400001 250 625001 250 625001 250 625001 300 900001 300 900001 300 90000

b =77.400076.700078.200084.100084.500083.700088.900089.200089.700094.200094.700095.9000

Das quadratische Polynom, das die Messdaten im Sinne der Methode der kleinsten Quadrate am besten approximiert, ist y = 55.7333 + 0.16033t - 0.0001t2.

Fig. 1.22 y = 55.7333 + 0.16033t - 0.0001t2Fig. 1.21 y = 60.4833 + 0.1153t. 111


2. Quadratisches Polynom (Version 2):Modellfunktion f(t,x) = x1 + x2t2. Für A und b erhalten wir:

Parameter: x1 = 72.8447; x2 = 0.00025281

Best fitting curve: f(t) = (72.8447)*1 + (0.00025281)*t^2

A =1 225001 225001 225001 400001 400001 400001 625001 625001 625001 900001 900001 90000

b =77.400076.700078.200084.100084.500083.700088.900089.200089.700094.200094.700095.9000

Der Repräsentant des oben vorgegebenen Kurventyps, der die Messdaten im Sinne der Methode der kleinsten Quadrate am besten approximiert, ist y = 72.8447 + 0.00025281t2.

Aus den Abbildungen Fig. 1.21 –Fig. 1.23 kann entnommen werden, dass das quadratische Polynom der Version 1 die Messdaten wohl amBesten approximiert. Auf solche optischen Aussagen können wir unsnatürlich nicht verlassen. Daher führenwir nun ein Maß für die Güte ein, mit der eine Modellfunktion gegebeneMessdaten approximiert; das sog.Bestimmtheitsmaß R2 (RSquared).

Fig. 1.23 y = 72.8447 + 0.00025281t2 112


Bestimmtheitsmaß R2 (Rsquared)

Gegeben seien m Beobachtungen (Messwerte) (ti,yi), i = 1,…,m, der Zustandsgrößen (t,y), t ∈ Rk, y ∈ R. Der Mittelwert der Zustandsgröße y ist gegeben durch:

.ym

ym

ii∑

=

=1

1

( )( )

( )∑

∑

=

=

−

−= m

ii

m

i

yy

y,fR

1

2

1

2

2xt

Das Verhältnis von geschätzter Streuung um den Mittelwert zu totaler Streuung um wird Bestimmtheitsmaß genannt. Da diesesVerhältnis immer nicht-negativ ist wird es mit R2 bezeichnet. Es gilt:

y

Definition 1.4.1: %-------------------------------------------------------------------------% Find RSquared for a given model function and measured data% % Input: mdata - Measured data as a nxm-matrix% fdata - Values of the model function f(t,x) with computed % parameter x1,...,xn and the k columns of mdata % Output: r2 %--------------------------------------------------------------------------function r2 = RS(mdata,fdata)[Q,P] = size(mdata);yq = mean(mdata(:,P));sf = sum((fdata - yq).^2);mf = sum((mdata(:,P) - yq).^2)r2 = sf/mf;Das Bestimmtheitsmaß liegt immer zwischen

Null und Eins, also 0 ≤ R2 ≤ 1. Liegen alle gemessenen Punkte auf der berechneten Kurve, so ist R2 = 1. Je näher R2 an der ZahlEins liegt, desto besser approximiert dieberechnete Funktion die gemessenen Daten.

Function-File 1.4.2 Berechnet das Bestimmtheitsmaß

113


Die Bestimmtheitsmaße für die Modellfunktionen im Beispiel 1.4.1 sind:

Parameter: x1 = 60.4833; x2 = 0.11533

Best fitting curve: f(t) = (60.4833)*1 + (0.11533)*t

RSquared: 0.99071

Ein Bestimmtheitsmaß nahe Eins sagt zwaraus, dass eine Modelfunktion die Messwertegut approximiert; es sagt aber nichts darüberaus, ob mit Hilfe dieser Modellfunktion die Messwerte gut interpoliert oder sogar auchextrapoliert werden können. Das Inter- undExtrapolieren von Messwerten mit einer Modellfunktion wird aber in den Ingenieur-wissenschaften sehr häufig benötigt.Es kann durchaus vorkommen, dass eineModellfunktion mit kleinerem R2 wesentlichbesser zur Interpolation oder Extrapolationvon Messwerten geeignet ist.

Mit der Methode der kleinsten Quadrate kannnur innerhalb eines vorgegeben Kurventyps diejenige Funktionsgleichung ermittelt werden,

Parameter: x1 = 72.8447; x2 = 0.00025281

Best fitting curve: f(t) = (72.8447)*1 + (0.00025281)*t^2

RSquared: 0.97351

Parameter: x1 =55.7333; x2 =0.16033; x3 =-0.0001


RSquared: 0.99220

deren Graph im obigen Sinne die Messwerte approximiert. Eine Art von Modellfunktion (Kurventyp), derenParameter mit Hilfe der Methode der kleinsten Quadrate bestimmt werden kann, haben wir im obigen Bei-spiel kennen gelernt; nämlich Polynome n-ter Ordnung. Es gibt natürlich unendlich viele mögliche Modell-funktionen. Welche Modellfunktion für ein gegebenes Problem die bessere ist, ist (abgesehen vom Be-stimmtheitsmaß R2) nicht Gegenstand der Mathematik. Diese Entscheidung muss aus der Anwendungs-disziplin, die die zu untersuchenden Daten modelliert hat (z.B. Ingenieurwissenschaften), entschieden

114


werden. Sagt die Theorie oder die Erfahrung ein lineares Verhalten bzgl. t voraus, so ist dieser Ansatzvermutlich der bessere, auch wenn der Gesamtfehler größer ist als bei einem nichtlinearen Ansatz.Also: Unterscheidet sich das Bestimmtheitsmaß R2 bei einem linearen Verhalten von t nur gering vomBestimmtheitsmaß eines nichtlinearen Ansatzes (s. Beispiel 1.4.1), so ist zu prüfen, ob der lineare Ansatz nicht vorzuziehen ist.

Dazu ein sehr einfaches Beispiel für eine falsche Modellierung aus [1].

Beispiel 1.4.2:Ein junger Sportler notiert über die Jahre hinweg seine 100-Meter-Zeiten

Alter [a] 13 14 15 16 17

Zeit [sec] 14.3 13.8 12.9 12.4 11.9

und versucht aus diesen Daten die Leistungsfähigkeit im Alter von 25 Jahren vorherzusagen (alsozu extrapolieren).

Unter Annahme einer linearen Leistungsentwicklung erhalten wirdie Funktion y = 22.36 – 0.62t. Das ergibt im Alter von 25 Jahren

einen Fabelweltrekord von6.86 sec (22.36 – 0.62*25).Bei einem kubischen Ansatzerhalten wir:

Parameter: x1 = 22.36; x2 = -0.62

Best fitting curve: f(t) = (22.36)*1 + (-0.62)*t

RSquared: 0.98767

115


Parameter: x1 = -82.0686; x2 = 20.9095; x3 = -1.4714; x4 = 0.033333

Best fitting curve: f(t) = (-82.0686)*1 + (20.9095)*t + (-1.4714)*t^2 + (0.033333)*t^3

RSquared: 0.99471

Dieser kubische Ansatz sichert voraussichtlich immernoch die Endlaufteilnahme bei der deutschen Meister-schaft, denn für t = 25 erhalten wir den Wert 10.36 sec.

Obwohl die beiden Ansätze die Messdaten ziemlichgut approximieren, sind die daraus abgeleiteten Extra-polationen mit hoher Wahrscheinlichkeit nicht richtig.

Merke:Die Mathematik stellt die Methoden zur Verfügung, derIngenieur muss die Ergebnisse richtig interpretierenund die richtige (oder besser gesagt eine geeignete)Modellfunktion finden.

Für eine größere Anzahl von Messdaten benötigen wir ein Script-File, mit dem die KoeffizientenmatrixA und die rechte Seite b mit Hilfe der Basisfunktionen ϕi, i = 1,…,n, aus den Messdaten generiert werden.Ferner soll dieses Script-File die Parameter x berechnen und das Bestimmtheitsmaß zur vorgegebenenModellfunktion ausgeben. Das leistet das folgende Script-File LA.m für Modellfunktionen mit eindimen-sionalen Zustandsgrößen t, also t ∈ R.

116


%--------------------------------------------------------------------------% Linear Curve Fitting%% Input: data - File of the measured data% prt - 1 Plot of the fitting curve and the data points% 0 No plot% phi - Basic-Functions phi_i as 'phi_1','phi_2',...,'phi_n'% Example: Fitting Curve is a polynom of 2nd degree% => phi = '1','t','t^2'%% Output: R2 - Rsquared% Coefficients x1,...,xn of the model function, bfc,% Plot of the fitting curve and the data points if prt = 1%% Example: LA('data_01.m',1,'1','t','t^2') finds the coefficients of the% best fitting 2nd order polynomial function regarding the % measured data in the file data_01.m%--------------------------------------------------------------------------function [x,bfc] = LA(data,prt,phi)displ(' ');disp(['Curve Fitting - Start -> ',char(datestr(now))]);disp(' ');in = load(data);q = length(phi);m = length(in);%Generate Matrix AA = zeros(m,q);for j = 1:q

for i = 1:mphij = inline(char(phi(j))); A(i,j) = phij(in(i,1));

endend%Generate bb = in(:,2);%Solve the problem using QR-Decomposition x = LAQR(A,b);

%Format the outputC = '';F = '(';for i = 1:q

v1 = num2str(i);v2 = num2str(x(i));if i == 1

C = strcat('x',v1,' = ',v2);F = strcat(F,v2,')*',char(phi(i)));

elseC = strcat(C,'; x',v1,' = ',v2);F = strcat(F,' + (',v2,')*',char(phi(i)));

endend%Represent the best fitting curve as inline functionbfc = inline(F);%Format the outputdisplay(['Parameter: ',C]);display(' ');display(['Best fitting curve: f(t) = ',F]);%Compute R2for i = 1:m

fdat(i) = bfc(in(i,1)); end r2 = RS(in,fdat);v = num2str(r2);display(' ');display(['RSquared: ', v])display(' ');%Plot the points of the dataset and the best fitting curveif prt == 1

%Generate points for plotting using the best fitting curve%Find the Minimum and Maximum of the t-values of input datamin12 = min(in); max12 = max(in);

117


t = (min12(1): 0.1: max12(1)); [k,l] = size(t); for p = l:-1:1

fdat(p) = bfc(t(p));end plot(in(:,1),in(:,2),'o',t,fdat,'-')grid on

end

>> LA('data_01.m',1,'1' 't' 't^2')

Curve Fitting - Start -> 15-May-2005 10:48:27

Parameter: x1 =55.7333; x2 =0.16033; x3 =-0.0001


RSquared: 0.9922Function-File 1.4.3 Löst lineare Ausgleichsproblemefür Basisfunktionen einer Veränderlichen

118

150 77.4150 76.7150 78.2200 84.1200 84.5200 83.7250 88.9250 89.2250 89.7300 94.2300 94.7300 95.9

Die Datei data_01.m beinhaltet dieMessdaten (TAB-separated oder comma-separated)

Aufruf des Function-Files LA.m in MATLAB. Input:

Datei mit den Messdaten. Der Name wird in Hochkommataübergeben. Liegt die Datei nicht im Current-Directory, so muss der Pfad angegeben werden.

Sollen die Messwerte und die approximierendeKurve geplottet werden, so muss die Variableprt gleich 1 gesetzt werden.

Die Basisfunktionen ϕi werden in einer Mengen-klammer mit Hochkommata und durch einLeerzeichen getrennt übergeben.


Als Basisfunktionen können beliebige Funktionen einer Veränderliche miteinander kombiniert werden.Hier sei nochmals angemerkt, dass der Begriff Lineare Ausgleichsrechnung sich nur auf den Para-metervektor x bezieht. Das heißt, die Modellfunktion f(t,x) muss linear in x sein. Die Basisfunktionenϕi, i = 1,…,n, können natürlich nicht-linear sein.

Das Script-File LA.m gibt nun für jede Kombination von Basisfunktionen eine Lösung aus. Ob eine solche Lösung sinnvoll ist, muss der Ingenieur entscheiden (das haben wir ja bereits schon diskutiert). Hier einige Beispiele:

>> LA('data_01.m',1,'1' 't^2' 'sin(t)')


Parameter: x1 =58.9666; x2 =0.00016881; x3 =-20.6753

Best fitting curve: f(t) = (58.9666)*1 + (0.00016881)*t^2 + (-20.6753)*sin(t)

RSquared: 0.99206

119


120

>> LA('data_01.m',1,'1' 't^2' 'exp(t)')


Warning: Matrix is close to singular or badly scaled.Results may be inaccurate. RCOND = 2.119744e-130.

> In LAQR at 9In LA at 40

Parameter: x1 =71.4022; x2 =0.00029275; x3 =-1.4498e-130

Best fitting curve: f(t) = (71.4022)*1 + (0.00029275)*t^2 + (-1.4498e-130)*exp(t)

RSquared: 0.9847


>> LA('data_01.m',1,'1' 't^2' 'log(t)')


Parameter: x1 =-11.1137; x2 =7.8972e-005; x3 =17.331

Best fitting curve: f(t) = (-11.1137)*1 + (7.8972e-005)*t^2 + (17.331)*log(t)

RSquared: 0.99269

121


Betrachten wir nun den Fall, dass die Zustandsgröße t zwei oder mehr Dimensionen hat; z.B. hängt t von der Zeit und der Temperatur ab. Dann hat die Datei, die die Messdaten enthält, drei oder mehr Spalten. Mit dem Script-File MLA.m (das M steht für multiple) können wir Modellfunktionen mit mehr-dimensionalen Zustandsgrößen t ∈ Rk bestimmen.

t2 [sec] y [µm]t1 [°C]

Messdaten zur Bestimmung der Aufkohlungstiefe y [µm] in Abhängigkeit von Temperatur t1 [°C] und Zeit t2 [s] (beim Härten von Stahl).

Betrachten wir zunächst das Script-File MLA4.m. Der Nachteildieses Script-Files ist, dass wir Funktionen mit maximal vierUnbekannten als Basisfunktionen verwenden können. Nun kann esnatürlich vorkommen, dass wir Basisfunktionen benutzen müssen, die wesentlich mehr Unbekannte haben. Dann müssten wir dasScript-File MLA4.m anpassenoder so umprogrammieren, dasses unabhängig von der Anzahl der freien Variablen ist.

1220 23 85 1240 40 1451250 38 1801215 225 3701245 245 3951230 67 1751260 115 2401280 125 2751240 210 3401270 280 4201220 81 2801240 83 2851220 227 3651245 245 3851290 37 1901325 57 2151345 54 2301250 227 4101280 317 4601305 319 5401305 114 3451340 159 425

122Die Datei data_03.m enthält dieMessdaten


123

%--------------------------------------------------------------------------% Linear Curve Fitting for Basis Functions having max. 4 Var.%% Input: data - File of the measured data% prt - 1 Plot of the fitting curve and the data points% 0 No plot% phi - Basic-Functions phi_i as 'phi_1','phi_2',...,'phi_n'% Example: Fitting Curve is a polynom of 2nd degree% of two variables% => phi = '1' 't1*t2' 't1^2' 't2^2'% var - Variables 't1' 't2' %% Output: R2 - Rsquared% Coefficients x1,...,xn of the model function% Plot of the fitting curve and the data points if prt = 1%% Example: MLA4('data.m',1,'1' 't1' 't2' 't1*t2','t1^2' 't2^2,'t1' 't2') % finds the coefficients of the best fitting 2nd order polynomial% function of two variables regarding the measured data in the % file data.m% %--------------------------------------------------------------------------function [x,bfc] = MLA4(data,prt,phi,var)disp(' ');disp(['Multiple Curve Fitting - Start -> ',char(datestr(now))]);disp(' ');in = load(data);q = length(phi);m = length(in);lvar = length(var);%Generate Matrix AA = zeros(m,q);for j = 1:q

for i = 1:mswitch lvar

case 1phij = inline(char(phi(j)),char(var(1)));A(i,j) = phij(in(i,1));

case 2 phij = inline(char(phi(j)),char(var(1)),char(var(2)));A(i,j) = phij(in(i,1),in(i,2));

case 3phij = inline(char(phi(j)),char(var(1)),char(var(2)),...

char(var(3)));A(i,j) = phij(in(i,1),in(i,2),in(i,3));

case 4phij = inline(char(phi(j)),char(var(1)),char(var(2)),...

char(var(3)),char(var(4)));A(i,j) = phij(in(i,1),in(i,2),in(i,3),in(i,4));

endend

end%Generate bb = in(:,lvar+1);%Solve the problem using QR-Decompositionx = LAQR(A,b);%Formatting the outputC = '';F = '(';for i = 1:q




endend%Represent the best fitting curve as inline functionbfc = inline(F);%Format the outputdisp(['Parameter: ',C]);disp(' ');


124

switch lvarcase 1 display(['Best fitting curve: f(',char(var(1)),') = ',F]);

case 2 display(['Best fitting curve: f(',char(var(1)),',',char(var(2)),') = ',F]);

case 3 display(['Best fitting curve: f(',char(var(1)),',',char(var(2)),...

',',char(var(3)),') = ',F]);case 4 display(['Best fitting curve: f(',char(var(1)),',',char(var(2)),...

',',char(var(3)),',',char(var(4)),') = ',F]);end %Compute R2for i = 1:m

switch lvarcase 1fdat(i) = bfc(in(i,1));

case 2fdat(i) = bfc(in(i,1),in(i,2));

case 3fdat(i) = bfc(in(i,1),in(i,2),in(i,3));

case 4fdat(i) = bfc(in(i,1),in(i,2),in(i,3),in(i,4));

endendr2 = RS(in,fdat);v = num2str(r2);disp(' ');disp(['RSquared: ', v])disp(' ');%Plot the points of the dataset and the best fitting curveif lvar > 2

prt = 0endif prt == 1

%Generate points for plotting using the best fitting curve%Find the Minimum and Maximum of the t-values of input datamin12 = min(in);

max12 = max(in);hold onplot3(in(:,1),in(:,2),in(:,3),'.','MarkerSize',15);ezmesh(bfc,[min12(1),max12(1),min12(2),max12(2)],70); title(['RSquared: ', v]);view(39,29);shading interp;colormap hot;grid onhold off

end

Script-File 1.4.4 Löst lineare Ausgleichsproblemefür Basisfunktionen mit bis zu vier Veränderlichen

eval(s)eval führt den im String sgespeicherten MATLAB-Befehlaus

Wir werden im Folgenden ein Script-File angeben,das unabhängig von der Anzahl der Variablen derBasisfunktionen ist. Der Programmiertrick ist:Wir erzeugen einen MATLAB-Befehl mittels String-Operationen und führen ihn dann mit dem eval-Befehl aus.

Betrachten wir aber zunächst das oben aufgeführteBeispiel, das wir mit dem Script-File MLA4.m lösen.


Die Messdaten in der Datei data_03.m sollen durch ein Polynom zweiter Ordnung mit zwei Veränderlichen approximiert werden. Ein solches Ploynom hat die allgemeine Form:

( ) 11223214225

21621 atatattatatat,tp +++++=

Die Basisfunktionen die der Funktion MLA4 übergeben werden müssen, sind somit:

( ) ( ) ( ) ( ) ( ) ( ) 22216

212152121422131212211 1 tt,t;tt,t;ttt,t;tt,t;tt,t;t,t ==⋅==== ϕϕϕϕϕϕ

Basisfunktionen

>> MLA4('data_03.m',1,'1' 't1' 't2' 't1*t2' 't1^2' 't2^2','t1' 't2')

Multiple Curve Fitting - Start -> 19-May-2005 07:11:02

Parameter: x1 =8558.8888; x2 =-13.3567; x3 =-4.5406; x4 =0.005297; x5 =0.0052591; x6 =-0.0031943

Best fitting curve: f(t1,t2) = (8558.8888)*1 + (-13.3567)*t1 + (-4.5406)*t2 + (0.005297)*t1*t2 + (0.0052591)*t1^2 + (-0.0031943)*t2^2

RSquared: 0.93797

Aufruf und Output der Funktion MLA4

125


Grafik-Output der Funktion MLA4: Gemessene Werte und das approximierendePolynnom 2ter-Ordnung mit zwei Veränderlichen.

126


127

%--------------------------------------------------------------------------% Linear Curve Fitting%% Input: data - File of the measured data% prt - 1 Plot of the fitting curve and the data points% 0 No plot% phi - Basic-Functions phi_i as 'phi_1 'phi_2'...'phi_n'% Example: Fitting Curve is a polynom of 2nd degree% => phi = '1' 't1*t2' 't1^2' 't2^2'% var - Variables as 't1' 't2‘ ...‘tn‘ %% Output: R2 - Rsquared% Coefficients x1,...,xn of the model function, bfc,% Plot of the fitting curve and the data points if prt = 1%% Example: MLA('data.m',1,'1' 't1' 't2' 't1*t2','t1^2' 't2^2','t1' 't2') % finds the coefficients of the best fitting 2nd order polynomial% function of two variables regarding the measured data in the % file data.m% %--------------------------------------------------------------------------function [x,bfc] = MLA(data,prt,phi,var)disp(' ');disp(['Multiple Curve Fitting - Start -> ',char(datestr(now))]);disp(' ');in = load(data);q = length(phi);m = length(in);lvar = length(var);%Generating strings for the eval-command. The inline function is%assembled depending on the number of variables of the input -> vars1 = 'phij = inline(char(phi(j)),';for k = 1:lvar

if k < lvar s1 = strcat(s1,'''',char(var(k)),'''',',');

elses1 = strcat(s1,'''',char(var(k)),'''',');');

endend

s2 = 'A(i,j) = phij(';for k = 1:lvar

if k < lvars2 = strcat(s2,'in(i,',num2str(k),')',',');

elses2 = strcat(s2,'in(i,',num2str(k),')',');');

endend%Generate Matrix AA = zeros(m,q);for j = 1:q

for i = 1:meval(s1);eval(s2);

endend%Generate bb = in(:,lvar+1);%Solve the problem using QR-Decomposition x = LAQR(A,b);%Formatting the outputC = '';F = '(';for i = 1:q




endend%Represent the best fitting curve as inline functionbfc = inline(F);%Format the outputdisplay(['Parameter: ',C]);

Die MATLAB-Befehle, die mit denString-Operationen erzeugt wurden,werden ausgeführt

s1 =phij = inline(char(phi(j)),'t1','t2');

s2 =A(i,j) = phij(in(i,1),in(i,2));

Beispiel


128

display(' ');s1 = 'Best fitting curve: f(';for k = 1:lvar

if k < lvars1 = strcat(s1,char(var(k)),',');

elses1 = strcat(s1,char(var(k)),') = ',F);

endenddisp(s1);%Compute R2s2 = 'fdat(i) = bfc(';for k = 1:lvar

if k < lvars2 = strcat(s2,'in(i,',num2str(k),')',',');

elses2 = strcat(s2,'in(i,',num2str(k),')',');');

endendfor i = 1:m

eval(s2);endr2 = RS(in,fdat);v = num2str(r2);display(' ');display(['RSquared: ', v])display(' ');%Plot the points of the dataset and the best fitting curveif lvar > 2

prt = 0endif prt == 1

%Generate points for plotting using the best fitting curve %Find the Minimum and Maximum of the t-values of input datamin12 = min(in);max12 = max(in);hold on

plot3(in(:,1),in(:,2),in(:,3),'.','MarkerSize',15);ezmesh(bfc,[min12(1),max12(1),min12(2),max12(2)],70); title(['RSquared: ', v]);view(39,29);shading interp;colormap default;grid onhold off

end

Function-File 1.4.5 Löst lineare Ausgleichsproblemefür Basisfunktionen mit beliebig vielen Veränderlichen


Linearisierung von Modellfunktionen, die nicht-linear bzgl. x sind

Einige Modellfunktionen, die in den Parametervariablen x = (x1,…,xn) nicht-linear sind, können durchgeeignete Transformationen linearisiert werden. Dazu ein Beispiel aus der Umformtechnik:

Die Kenntnis der Warmfließkurve eines Werkstoffes ist eine unverzichtbare Voraussetzung für jedeBerechnung im Bereich der Umformtechnik. Bestimmte Abhängigkeiten der Fließspannung kf von den Umformparametern, wie der Formänderung φ, der Umformgeschwindigkeit und der Temperatur T, sind seit langem experimentell bekannt. Wenn man diese bekannten Abhängigkeiten in Form einermathematischen Funktion kombiniert, erhält man Modellfunktionen

bei denen die Temperaturabhängigkeit T, die Abhängigkeiten der Umformgeschwindigkeit und derFormänderung φ sowie die Effekte der dynamischen Entfestigung in Form multiplikativer Verknüpfungenvon Exponential- und Potenzfunktionen beschrieben wird.

Eine der wichtigsten dieser Modellfunktionen ist:

( ),,,T,gkf ϕϕ &x=

ϕ&

ϕ&

( ) ϕϕϕϕϕ ⋅⋅+⋅ ⋅⋅⋅⋅== 435216

xxTxxTxf eex,,T,gk &&x(1.4.16)

Klar ist, die Modellfunktion ist nicht linear in x.

129


Linearisierung von (1.4.16) durch logarithmische Transformation:

( ) ϕϕϕϕϕ ⋅⋅+⋅ ⋅⋅⋅⋅== 435216

xxTxxTxf eex,,T,gk &&x

( ) ( ) ( ) ( ) ( ) ϕϕϕ ⋅+⋅+⋅⋅++⋅+= 435216 xlnxlnTxxTxxlnkln f &Logarithmische Transformation

( ) ykln f = ( ) 1tln =ϕ& ( ) 2tln =ϕ 3t=ϕSei und T = t4, so erhalten wir eine Modellfunktion f(x,t), die ,, ,

in x linear ist; und zwar:

( ) .xttxtxtxtxtxt,t,t,t,fy 6415342312414321 +⋅⋅+⋅+⋅+⋅+⋅== x(1.4.17)

Man kann nun zeigen, dass die Parameter x = (x1,…,xn), die für die linearisierte Modellfunktion berechnetwerden, für monotone Transformationen auch minimal (im Sinne der Methode der kleinsten Quadrate) fürdie Ausgansfunktion sind. Wichtig ist, dass die Messdaten ebenfalls transformiert werden. In unseremBeispiel müssen wir den Messdaten sogar eine weitere Spalte hinzufügen; nämlich: ( ).lnt ϕ=2

Auf der folgenden Seite sind einige Zeilen der Messdaten und der trans-formierten Eingabedatei für die Funktion MLA abgebildet.

130


131

%-------------------------------------------------------------------------% Measured data for steel grade 100Cr6% % Phip Phi Temperature Kf%-------------------------------------------------------------------------1,5 0,05 900 130,021,5 0,05 1000 92,2031,5 0,05 1100 61,781,5 0,05 1200 41,41,5 0,075 900 143,721,5 0,075 1000 94,891,5 0,075 1100 68,0161,5 0,075 1200 46,0451,5 0,1 900 154,31,5 0,1 1000 105,351,5 0,1 1100 72,0371,5 0,1 1200 50,5161,5 0,125 900 161,481,5 0,125 1000 110,431,5 0,125 1100 75,011,5 0,125 1200 54,1161,5 0,15 900 167,531,5 0,15 1000 114,641,5 0,15 1100 78,5071,5 0,15 1200 56,5541,5 0,175 900 172,771,5 0,175 1000 117,911,5 0,175 1100 81,3621,5 0,175 1200 58,7031,5 0,2 900 176,941,5 0,2 1000 120,781,5 0,2 1100 83,519...

%------------------------------------------------------------------------------------------% Transformed data for steel grade 100Cr6% % Log(Phip) Log(Phi) Phi Temperature Log(Kf)%------------------------------------------------------------------------------------------0,40547 -2,9957 0,05 900 4,86770,40547 -2,9957 0,05 1000 4,5240,40547 -2,9957 0,05 1100 4,12360,40547 -2,9957 0,05 1200 3,72330,40547 -2,5903 0,075 900 4,96790,40547 -2,5903 0,075 1000 4,55270,40547 -2,5903 0,075 1100 4,21970,40547 -2,5903 0,075 1200 3,82960,40547 -2,3026 0,1 900 5,03890,40547 -2,3026 0,1 1000 4,65730,40547 -2,3026 0,1 1100 4,27720,40547 -2,3026 0,1 1200 3,92230,40547 -2,0794 0,125 900 5,08440,40547 -2,0794 0,125 1000 4,70440,40547 -2,0794 0,125 1100 4,31760,40547 -2,0794 0,125 1200 3,99110,40547 -1,8971 0,15 900 5,12120,40547 -1,8971 0,15 1000 4,74180,40547 -1,8971 0,15 1100 4,36320,40547 -1,8971 0,15 1200 4,03520,40547 -1,743 0,175 900 5,15190,40547 -1,743 0,175 1000 4,76990,40547 -1,743 0,175 1100 4,39890,40547 -1,743 0,175 1200 4,07250,40547 -1,6094 0,2 900 5,17580,40547 -1,6094 0,2 1000 4,79390,40547 -1,6094 0,2 1100 4,4251...

Messdaten für die Fließspannung kf der Stahlsorte100Cr6 in der Datei kf100Cr6.m (432 Datensätze)

Die transformierte Messdaten sind der Input für die FunktionMLA


%-------------------------------------------------------------------------% Flow curve for steel grade 100Cr6 (phi constant)%-------------------------------------------------------------------------%insert constant value for phiphi = 0.5;%load datamdata = load('kf100CR6.m');mdata = [log(mdata(:,1)) log(mdata(:,2)) mdata(:,2) mdata(:,3) log(mdata(:,4))];[x,bfcl] = MLA(mdata,0,'t4' 't1' 't2' 't3' 't1*t4' '1','t1' 't2' 't3' 't4');%Non linear modeldisp(' ');disp('Transformed parameters for the non linear model function');disp(' ');x(6) = exp(x(6));for i = 1:6

v1 = num2str(i);v2 = num2str(x(i));C = strcat('x',v1,' = ',v2);disp(C);C = '';

enddisp(' ');disp('Best fitting curve for the non linear model function');disp(' ');v1 = num2str(x(1));v2 = num2str(x(2));v3 = num2str(x(3));v4 = num2str(x(4));v5 = num2str(x(5));v6 = num2str(x(6));C = 'kf = g(T,phi,phip) = ';F = strcat(v6,'*exp(',v1,'*T)*phip^(',v2,'+',v5,'*T)*phi^',v3,'*exp(',v4,'*phi)');disp(strcat(C,F));bfc = inline(F,'T','phi','phip');% Plots

j = 0;for i = 1:length(mdata)

if mdata(i,3) == phij = j + 1;in(j,1) = mdata(i,4);in(j,2) = exp(mdata(i,1));in(j,3) = exp(mdata(i,5));

endendmin12 = min(in);max12 = max(in);F = strcat(v6,'*exp(',v1,'*T)*phip^(',v2,'+',v5,'*T)*',num2str(phi),'^',v3,...

'*exp(',v4,'*',num2str(phi),')');bfc1 = inline(F,'T','phip');hold onplot3(in(:,1),in(:,2),in(:,3),'.','MarkerSize',15);ezmesh(bfc1,[min12(1),max12(1),min12(2),max12(2)],70);title(['phi = ',num2str(phi)]);view(106,29);%shading interp;colormap default;grid onhold off

Der Parametervektor x für die linearisierteModellfunktion wird mit der Funktion MLAermittelt

Das Script-File bfc100Cr6.m liest die Messdaten einund transformiert sie. Die transformierten Daten sindInput für die Funktion MLA, die für die linearisierteModellfunktion auf Basis der transformierten Daten dieParameter x1 bis x6 berechnet. Die Parameter werden dann, wenn nötig, zurücktransformiert. Die nichtlineareModellfunktion wird mit diesen Parametern ausgegeben.

132


>>bfc100Cr6

Multiple Curve Fitting - Start -> 24-May-2005 19:48:51

Parameter: x1 =-0.0037043; x2 =-0.078897; x3 =0.23147; x4 =-0.50591; x5 =0.00021138; x6 =8.9143

Best fitting curve: f(t1,t2,t3,t4) =(-0.0037043)*t4 + (-0.078897)*t1 + (0.23147)*t2 + (-0.50591)*t3 + (0.00021138)*t1*t4 + (8.9143)*1

RSquared: 0.99507

Transformed parameters for the non linear model function

x1 =-0.0037043x2 =-0.078897x3 =0.23147x4 =-0.50591x5 =0.00021138x6 =7437.8475

Best fitting curve for the non linear model function

kf = g(T,phi,phip) =7437.8475*exp(-0.0037043*T)*phip^(-0.078897+0.00021138*T)*phi^0.23147*exp(-0.50591*phi)

Aufruf und Output des Script-Files bfc100Cr6.m

Die Modellfunktion

( ) ϕϕϕϕϕ ⋅⋅+⋅ ⋅⋅⋅⋅== 435216

xxTxxTxf eex,,T,gk &&x

ist für die Umformtechnik sehr wichtig, da sie sehr gute Inter- und Extrapolationseigenschaften besitzt.

133


Grafik-Output des Script-Files bfc100Cr6.m: Gemessene Werte und die approximierendeFunktion

( ) ϕϕϕϕϕ 50591023147000021138007889700037043084757437 ..T..T. ee.,,Tgkf −+−−== &&

wobei ϕ = 0.5 ist.

134


Soll die Fließspannung für den Werkstoff 100Cr6 zu vorgegebener Temperatur, Formänderung und Umformgeschwindigkeitberechnet werden, so muss natürlich die Lineare Ausgleichsrechnung nicht immer wieder durchgeführt werden. Nachdem derParametervektor für einen Werkstoff bestimmt wurde, so wird die ermittelte Funktion in einem Function-File gespeichert undkann somit immer wieder aufgerufen werden.

%-------------------------------------------------------------------------% Returns the kf-value for steel grade 100Cr6%% Input: T - Temperature% phi - Strain% phip - Strain rate%% Example: func100cr6(900,1.5,0.5)%-------------------------------------------------------------------------function kf = func100cr6(T,phi,phip)kf = 7437.8475*exp(-0.0037043*T)*phip^(-0.078897+0.00021138*T)*phi^0.23147*exp(-0.50591*phi);

Transformed parameters for the non linear model function

x1 =-0.0037043x2 =-0.078897x3 =0.23147x4 =-0.50591x5 =0.00021138x6 =7437.8475

Best fitting curve for the non linear model function

kf = g(T,phi,phip) =7437.8475*exp(-0.0037043*T)*phip^(-0.078897+0.00021138*T)*phi^0.23147*exp(-0.50591*phi)

Aus dem Output desScript-Files bfc100cr6.mmit Copy und Paste dieFunktion übernehmen

Function-File func100cr6.m

135


Die Funktion func100cr6 können wir dazu benutzen, verschiedene zwei- oderdreidimensionale Grafiken zu erstellen, indem wir ein oder zwei Werte konstantsetzen. Zum Beispiel können wir zu einer fest vorgegebenen Temperatur diekf-Werte in Abhängigkeit von phi und phip ausgeben. Die folgenden Grafikenwurden mit dem Function-File funcplotkf erzeugt. Hier einige Ausschnitte aus diesem File:

>> kf = func100cr6(1000,0.05,1.5)

kf =

94.1639

Bestimmung beliebiger kf-Werte mitder Funktion func100cr6

%------------------------------------------------------------------------% kf-value Plotter for steel grades%%Input: fun - Function e.g. func100cr6 % var - Variables e.g. 'phi' or 'phi' 'phip'% con - Constants e.g. 'T' or 'T' 'phi'% val - Value of the constants [900] or [2.5 3]% dom - Interval of the variables e.g. [0;2.5] or [0 0;2.5 3.5]% if there are two variables % dat - data file of the measured data (optional)% -> for plotting the measured points% -> if '' then no plot of the measured points%-------------------------------------------------------------------------function funcplotkf(fun,var,con,val,dom,dat)%function handleeval(strcat('bfc = @',fun,';')); %No plot of measured data if mdp == 0mdp = 0;if dat ~= ' '

mdata = load(dat);mdp = 1;

endlvar = length(var);if lvar == 1

min12 = min(dom);max12 = max(dom);if strcmp(char(var(1)),'phi') == 1

if strcmp(char(con(1)),'T') == 1 136

T = val(1);phip = val(2);

elseT = val(2);phip = val(1);

endif mdp == 1

j = 0;for i = 1:length(mdata)

if (mdata(i,3) == T) & (mdata(i,1) == phip)j = j + 1;in(j,1) = mdata(i,2);in(j,2) = mdata(i,4);

endendif j == 0

disp(' ');disp('Error -> No measured values found for given constants');disp(' ');disp('Hint -> Change values of constants');disp(['Current values: ',char(con(1)),' = ',num2str(val(1)),...

'; ',char(con(2)),' = ',num2str(val(2))]); return

endinmin = min(in);inmax = max(in);a = min(min12(1),inmin(1));b = max(max12(1),inmax(1));


elsea = min12(1);b = max12(1);

endt = (a: 0.01: b);[k,l]=size(t); for p = l:-1:1

fdat(p) = bfc(T,t(p),phip);endif mdp == 1

plot(in(:,1),in(:,2),'o',t,fdat,'-')else

plot(t,fdat,'-')endgrid onxlabel('phi');ylabel('kf');s = ['kf-values for ',char(con(1)),' = ',num2str(val(1))...

,'; ',char(con(2)),' = ',num2str(val(2))];title(s);

.

.

.elseif lvar == 2

min12 = min(dom);max12 = max(dom);...elseif strcmp(char(con(1)),'T') == 1

T = val(1);j = 0;if mdp == 1

for i = 1:length(mdata)if mdata(i,3) == T

j = j + 1;in(j,1) = mdata(i,2);in(j,2) = mdata(i,1);

in(j,3) = mdata(i,4);end

endif j == 0

disp(' ');disp('Error -> No measured values found for given constant');disp(' ');disp('Hint -> Change value of the constant');disp(['Current value: ',char(con(1)),' = ',num2str(val(1))]); return

endinmin = min(in);inmax = max(in);

endif strcmp(char(var(1)),'phi') == 1

if mdp == 1a = min(min12(1),inmin(1));b = max(max12(1),inmax(1));c = min(min12(2),inmin(2));d = max(max12(2),inmax(2));

elsea = min12(1);b = max12(1);c = min12(2);d = max12(2);

endelse

disp(' ');disp('Error -> phi must be the first variable');disp(' ');return

endhold onif mdp == 1plot3(in(:,1),in(:,2),in(:,3),'.','MarkerSize',15);

endq = 70;x = linspace(a,b,q);y = linspace(c,d,q);

137


[X,Y] = meshgrid(x,y);Z = zeros(q);for j=1:q

for i=1:qZ(j,i) = bfc(T,x(i),y(j));

endend

endsurf(X,Y,Z)shading interp;colormap default;%surf(X,Y,Z,'FaceColor','red','EdgeColor','none')%camlight left; lighting phongxlabel(char(var(1)));ylabel(char(var(2)));zlabel('kf');s = ['kf-values for ',char(con(1)),' = ',num2str(val(1))];title(s);view(39,29);grid onhold off

end

>> funcplotkf('func100cr6','phip','T' 'phi',[900 0.05],[0;100],'kf100CR6.m')

Datei derMesswerte

Intervalle der Variablen:[i1;i2] oder [i11 i21;i12 i22]

Werte der Konstanten:[w1] oder [w1 w2]

Name der Konstanten: ‘c1‘ für eine, ‘c1‘ ‘c2‘ für zwei Variablen

Namen der Variablen: ‘v1‘ für eine,‘v1‘ ‘v2‘ für zwei Variablen

Name des m-Files. in dem die Funktiongespeichert istFunction-File 1.4.6 Plottet zwei- und dreidimensionale

Grafiken von approximierenden Funktionen mit dreiVeränderlichen. Eine oder zwei der Variablen werdenkonstant gesetzt.

138


>> funcplotkf('func100cr6','phip','T' 'phi',[900 0.05],[0;100],'kf100CR6.m')

139


>> funcplotkf('func100cr6','T','phi' 'phip',[0.05 1.5],[800;1200],'kf100CR6.m')

140


>> funcplotkf('func100cr6','phi','T' 'phip',[900 1.5],[0;2],'kf100CR6.m')

141


>> funcplotkf('func100cr6','T' 'phip','phi',[0.05],[800 1;1400 100],'kf100CR6.m')

142


>> funcplotkf('func100cr6','phi' 'phip','T',[900],[0 1;1 100],'kf100CR6.m')

143


1.4 Noch einige Bemerkungen zu Backslash-Operator

Zum Lösen von linearen Ausgleichproblemen haben wir in den vorhergehenden Kapitel die Funktion LAQR benutzt. Wir hätten auch den Backslash-Operator benutzen können, denn dieser Operator

% ---------------------------------------------------------------% Linear Curve Fitting with QR-Decomposition% Input: A mxn-Matrix, b m-Columnvector% Output: x n-Solutionvector%---------------------------------------------------------------function [x] = LAQR(A,b);[Q1,R] = qr(A,0);x = R\(Q1‘*b);

Funktion LAQR

beinhaltet verschiedene Algorithmen zur Lösung linearerGleichungssysteme. Es werden folgende Fälle durch Diagnoseder Koeffizientenmatrix A erkannt:

Quadratische reguläre Matrizen

Rechteckige überbestimmte System

Rechteckige unterbestimmte System

Symmetrische positiv definite Matrizen

Dreiecksmatrizen und Permutationen von Dreiecksmatrizen

%Solve the problem using QR-Decomposition x = LAQR(A,b);

%Solve the problem using QR-Decomposition x = A\b;

Äquivalente Formulierungen

Ist A eine reguläre quadratische Matrix, so findetMATLAB die Lösung x = A\b mit Methoden, diewir bereits besprochen haben. Im Falle überbe-stimmter bzw. unterbestimmter Systeme geht MATLAB wie folgt vor:

144


Überbestimmte lineare Gleichungssysteme

Ist Koeffizientenmatrix A ∈ Rmxn und m > n, so liegt ein überbestimmtes System vor.

1. Rang(A) = n und

(i) b ∈ Bild(A) ⇒ Ax = b hat genau eine Lösung

(ii) b ∉ Bild(A) ⇒ Ax = b ist nicht universell lösbar und MATLAB löst die Ersatzaufgabe

Die Ersatzaufgabe ist eindeutig lösbar und x* = A+b =(ATA)-1ATb ist die eindeutige Lösung.

2. Rang(A) < n (A ist rangdefekt) und

(i) b ∈ Bild(A) ⇒ Ax = b hat unendlich viele Lösungen. MATLAB: x = A\b oder x = pinv(A)*b.

(ii) b ∉ Bild(A) ⇒ Ax = b ist nicht universell lösbar und MATLAB löst die Ersatzaufgabe

Die Ersatzaufgabe hat unendlich viele Lösungen. Lösung der Ersatzaufgabe mit kleinster Länge mit MATLAB: x = pinv(A)*b. Basislösung der Ersatzaufgabe mit MATLAB: x = A\b.

.MinnIRx 2

bAx −∈

.MinnIRx 2

bAx −∈

145


146

Unterbestimmte lineare Gleichungssysteme

Ist Koeffizientenmatrix A ∈ Rmxn und m < n, so liegt ein unterbestimmtes System vor.

1. Rang(A) = m ⇒ b ∈ Bild(A) ⇒ Ax = b hat unendlich viele Lösungen.

(i) x* = A+b =AT (AAT)-1b ist die Lösung kleinster Länge.

(ii) x = A+b + y mit y ∈ Null(A) sind alle Lösungen von Ax = b.

(iii) Die Ersatzaufgabe Min||x||2 | x ∈ Rn ∧ Ax = b hat genau eine Lösung, die Lösung mit derkleinsten Euklidischen Länge. Diese Ersatzaufgabe löst MATLAB mit x = pinv(A)*b.

(iv) Der Backslash-Operator x = A\b liefert eine Basislösung.

2. Rang(A) < m (A ist rangdefekt) und

(i) b ∈ Bild(A) ⇒ Ax = b hat unendlich viele Lösungen. MATLAB: x = A\b Basislösung bzw.x = pinv(A)*b Lösung mit kleinster Länge.

(ii) b ∉ Bild(A) ⇒ Ax = b hat keine Lösung und MATLAB löst die Ersatzaufgabe

Die Ersatzaufgabe hat unendlich viele Lösungen. Lösung der Ersatzaufgabe mit kleinster Länge in MATLAB: x = pinv(A)*b. Basislösung der Ersatzaufgabe in MATLAB: x = A\b.

.MinnIRx 2

bAx −∈


Der Backslash-Operator löst die linearen Ausgleichsaufgabe

.MinnIRx 2

bAx −∈

mit Hilfe der QR-Zerlegung mit Spaltenpivotierung. Bisher wurde noch nicht erwähnt, wie dieQR-Zerlegung berechnet wird. Dazu gibt es mehrere Möglichkeiten. Die wichtigsten sind:

Spiegelung mit HOUSEHOLDER-Matrizen

Drehungen mit GIVENS-Matrizen

GRAM-SCHMIDTSCHE Orthogonalisierungen.

Diese Verfahren kann man in den Lehrbüchern zur numerischen Algebra finden. Die QR-Zerlegung mitHOUSEHOLDER-Matrizen wird z.B. in [1] beschrieben.

Merke:

Der Backslash-Operator íst zum Lösen linearer Systeme universell einsetzbar.

147

Documents

Computer Based Engineering Mathematics - uni-due.de€¦ · Institut für Angewandte Materialtechnik Prof. Dr. rer. nat. Johannes Gottschling Dr.-Ing. Bernhardt Weyh Computer Based