Numerische Methoden - einstein.informatik.uni-oldenburg.deeinstein.informatik.uni-oldenburg.de/.../grund/04ss/ad2/Numerik-ohne.pdf · Algorithmen für nicht ganzzahlige Probleme –

Numerische Methoden

● Algorithmen für nicht ganzzahlige Probleme– Probleme aus Bereich der numerischen Mathematik

● Lösungen meistens eine reelle Zahl● in Informatik eine Gleitpunktzahl

1) Nullstellen einer reellen Funktion2) Extremwerte einer reellen Funktion3) Werte analytischer Funktionen

sin(x), arcsin(x), ex

4) Fourier-Analyse5) Lösungen eines linearen Gleichungssystems

sehr viele UnbekannteLösung eines nichtlinearen Gleichungssystems

7) Erzeuge eine Folge von Zufallszahlen

Numerische Algorithmen


● Algorithmen für nicht ganzzahlige Probleme

7) Transformation einer Wertefolge Fouriertransformation

8) möglichst glatte Kurve zwischen je zwei PunktenSpline-Approximation

9) numerische Differentiation oder Integration10) Optimum eines Systems linearer Ungleichungen11) Numerische Differenzen- / Differentialgleichungen

● Hier nur einige dieser Probleme behandelt

● Nullstellen einer Funktion– Polynom als spezielle Funktion

f(x) = a0 + a1·x + a2·x2 + ... + an·x

n.– Klassisches Problem des Mathematik

● Suche alle x, so dass f(x) = 0. ● Wurzeln ziehen: a ist Nullstelle der Funktion f(x) = x2-a

– algebraische Lösungsansätze● Nullstellen spezieller Polynome ● Polynome bis zum Grad vier ● Polynome höheren Grads im allgemeinen nicht mehr lösbar● Erkenntnis wenig hilfreich


● Beispiel: Polynom zweiten Grades

– Algebraische Lösung

– Numerische Ergebnisse● P1(x) = x2-5x-6

x1=6, x2= – 1.

● P2(x) = x2 – 48·109·x - 49·109

x1=-1,0208320617675781, x2 = 48000000001,02083P2(-1,0208320617675781) = -61.034,11415190167,P2(48000000001,02083) = -262.144

● Ungenauigkeit der Differenzen im Wurzelausdruck ● Ungenauigkeit beim Wurzelziehen

Numerische Algorithmenf 2 x =a⋅x2b⋅xd

x1,2=−b2⋅a±b2−4⋅a⋅b

2⋅a


● Regula Falsi, Binärteilung

Funktion

f(x)

X


● Regula Falsi, Binärteilung

// Nullstelledouble links = 0;double rechts = 400;double wertLinks = funk(links);double wertRechts = funk(rechts);for(int i=0;i<=64;i++) {// wiederhole so oft nötig double mitte = (rechts+links)/2; double wertMitte = funk(mitte); if(wertMitte==0) break; if(wertMitte*wertLinks>0) {// gleiches Vorzeichen links = mitte; // linke Grenze verrücken


● Regula Falsi, Proportionales Teilen

Funktion

f(x)

X


● Regula Falsi, Proportionales Teilen// Nullstelledouble links = 0;double rechts = 400;double wertLinks = funk(links);double wertRechts = funk(rechts);for(int i=0;i<=64;i++) {// wiederhole so oft nötig double mitte = links + (rechts-links)*Math.abs(wertLinks)/ (Math.abs(wertLinks)+Math.abs(wertRechts)); double wertMitte = p.getPol(mitte); if(wertMitte==0)break; if(wertMitte*wertLinks>0) {// gleiches Vorzeichen links = mitte; // linke Grenze verrücken

Funktionf(x)

X


● Regula Falsi, Proportionales Teilen

– Konvergenz nur von einer Seite

– Abfrage aufMitte==0

– Auch KombinationBinäres und Proportinales Teilensinnvoll

Numerische Algorithmen // Nullstelle: Regula Falsi, Proportionales Teilendouble links = 0, rechts = 400;double wertLinks=funk(links),wertRechts=funk(rechts);for(int i=0;i<=64;i++) { double mitte = links + (rechts-links)*Math.abs(wertLinks)/ (Math.abs(wertLinks)+Math.abs(wertRechts)); double wertMitte = p.getPol(mitte); if(wertMitte==0) break; if(wertMitte*wertLinks>0) { links = mitte; wertLinks = wertMitte; double v = p.getPol((links+rechts)/2); if(v*wertMitte<0) {//schiebe auch andere Grenze rechts = (links + rechts) / 2; wertRechts = v;

Funktionf(x)

x

f(x0 )

x0x1x2

f(x1 )

f(x2 )f ' x0=

f x0x0−x1

x1=x0−f x0f ' x0


● Newton Verfahren

– Schnittpunkt aus Tangente in Punkt xk

– Hohe Konvergenz-Geschwindigkeit– Nur bei möglichst

glatten Kurven– Schlechte Konvergenz bei großer

Entfernung vom Nullpunkt– Ableitung muss bekannt sein!

Funktionf(x)

x

f(x0 )

x0x1x2

f(x1 )f(x2 )

f ' x0=f x0

x0−x1

x1=x0−f x0f ' x0

Numerische Algorithmen // Nullstelle: Newton Verfahren

double x = 0; for(int i=0;i<=100;i++) { double funk = f(x); // Funktionswert in x if(funk==0) break; // Falls Nullstelle double ablt = fd(x);// Ableitung double diff = f(x)/ablt;// Differenz x -= diff; // Neuer Wert für x }

● Lösung analytischer Gleichungen – Löse Gleichung: x/2 = sin x.

● Lösung: finde Nullstelle x0 zu: f(x) = sin x – x/2.● Wegen

sin x0 – x0/2 = 0ist x0/2 = sin x0.

– Finde Quadratwurzel aus 2● Lösung: finde Nullstelle x0 zu: f(x) = x2 – 2.● Wegen

x02 – 2 = 0

ist x02 = 2 oder x0 = 2.


● Lösung analytischer Gleichungen – Anderer Lösungsansatz: Fixpunktgleichung

● Ziehe Quadratwurzel aus a.– Lösung:

● iteriere

solange, bis Ergebnis konstant● Gleichung entstand aus Newton-Verfahren

● Diese Methode löst viele Spezialfunktionen f(x):

wobei A ein geeignet Faktor ist (meist |A|<1)


x= x2a2⋅x

x k1=x k−x k

2−a2⋅x k

=x k

2a2⋅x k

x k1=x kA× f x k

Funktionf(x)

X

f(x0 )

X0x1x2

f(x1 )f(x2 )

● Fixpunktgleichung● Koeffizient A 'dynamisch' anpassbar:● Idee: Sei An gegeben, so erhält man mit neuem Parameter B:

An+1 = An·q + Bn·(1-q).● Es gilt also für ein q<1

A1 = B1·(1-q),A2 = A1·q + B2·(1-q) = B1·(1-q)·q + B2·(1-q) ,A3 = A2·q + B3·(1-q) = B1·(1-q)·q2 + B2·(1-q)·q + B3·(1-q)A4 = B1·(1-q)·q3 + B2·(1-q)·q2 + B3·(1-q)·q + B4·(1-q).

● 'Ältere' Terme werden also durch qk gewichtet:Exponential Weighted Average.

● Bk lässt sich aus der Steigung der Sekante in xk-1 und xk abschätzen.


● Fixpunktgleichung – Beispiel:

f(x) = 3 ∙x2 + 2∙x – 2mit A=0,2 bzw. A=-0,2 erhalten wir mit x0=0,0

–


0 0,000000 -2,0000001 -0,400000 -2,4800002 -0,896000 -2,1863683 -1,333274 -1,1113104 -1,555536 -0,2716895 -1,609873 -0,0363626 -1,617146 -0,0039707 -1,617940 -0,0004218 -1,618024 -0,0000449 -1,618033 -0,00000510 -1,618034 0,00000011 -1,618034 0,00000012 -1,618034 0,000000

0 0,000000 -2,0000001 0,400000 -0,8800002 0,576000 -0,1844483 0,612890 -0,0229534 0,617480 -0,0024765 0,617975 -0,0002626 0,618028 -0,0000287 0,618033 -0,0000038 0,618034 0,0000009 0,618034 0,00000010 0,618034 0,00000011 0,618034 0,00000012 0,618034 0,000000


● Extremwerte– Minima und Maxima– Zweiteilung

● Keine Eindeutige Zuordnung des Intervalls zum Maximum

Funktion

f(x)

X

Funktion


● Extremwerte– Minima und Maxima

● Kurve muss im Intervall konvex von unten sein

Funktion

f(x)

X


● Extremwerte– Minima und Maxima– Relative Minima (m) und Maxima (M)

Funktion

f(x)

X

mm

M

M

konvex von oben

konvex von unten


● Extremwerte– Minima und Maxima– Dreiteilung

● größere der mittleren Ordinaten muss erhalten bleiben

Funktion

f(x)

X


● Extremwerte– Minima und Maxima– Dreiteilung

● größere Ordinate wird Mittelpunkt des neuen Intervalls

Funktion

f(x)

X

Numerische Algorithmen // Maximum double links = 0; double rechts = 400; for(int i=0;i<=96;i++) { double mitteL = (rechts+2*links)/3; double mitteR = (2*rechts+links)/3; double wertMitteL = funk(mitteL); double wertMitteR = funk(mitteR); if(wertMitteL<wertMitteR){//rechte Mitte links = mitteL; // ist größer } else if(wertMitteL>wertMitteR){//linke rechts = mitteR; // Mitte ist größer } else { // beide gleich groß links = mitteL; rechts = mitteR; } }

Numerische Algorithmen● Werte für analytische Funktionen– Beispiele

● sin(x), cos(x), tan(x)● 10x, log10 x● usw.

– Annahme: Reelle Funktion durch Polynom approximierbar

– Koeffizienten

f x =a0a1⋅ x−x0a2⋅x−x02ak⋅ x−x0

kRk x

f k x0=ak⋅k !⇒ak=f x0k !

f x = f x0 f ' x0⋅ x−x0f " x0

2⋅ x−x0

2f k x0

k !⋅ x−x0

k


● Werte für analytische Funktionen– Taylor-Reihe

– Beispiel: sin(x)sin'(x) = cos(x), cos'(x) = - sin(x); x0 = 0.

– Beispiel: cos(x)cos'(x) = - sin(x), sin'(x) = cos(x); x0 = 0.

– Beispiel: ex

f x = f x0 f ' x0⋅ x−x0f " x0

2⋅ x−x0

2f k x0

k !⋅x−x0

k

sin x =x− x3

3 ! x5

5!− x7

7! x9

9 !− x11

11!

cos x =1− x2

2! x 4

4 !− x6

6 ! x8

8 !− x10

10 !

e x x =1 x1! x2

2! x3

3 ! x 4

4 ! x5

5 !


● Numerische Integration (Numerische Quadratur)– Berechnung einer Fläche unter einer Kurve, die

● nicht analytisch integrierbar ist● nur numerisch vorliegt

– hier nur: äquidistante Unterteilung (Breite h)– Integration 0-ter Ordnung

● Funktionswerte in Intervall h als konstant angenommenf(x)

xh ba

F ab=∑

x=a

b−1

f x ⋅h=h⋅∑x=a

b

f x −h⋅ f b=

=h⋅∑i=0

N−1

f aih , N=b−ah

.


● Numerische Integration (Numerische Quadratur)– Sei die Ordinatensumme mal der Intervallbreite, so

lässt sich ein Korrekturterm bestimmen:

– Im folgenden werden die Ergebnisse verglichen gegen

– Ergebnis

– Korrekturterm

f(x)

xh ba

F ab=h⋅∑

x=a

b

f x −h⋅ f b=K ab−h⋅ f b.

K ab=h⋅∑

x=a

b

f x

K ab

E F ab=−h⋅ f b.

F ab=K a

b−h⋅ f b

f(x)

xh ba

Numerische Algorithmen● Numerische Integration– Integration 1-ter Ordnung

● Funktionswert steigt gleichmäßig von f(c) bis f(c-h).

● Ergebnis

● Korrekturterm

Gab=∑

x=a

b−h f x f xh2

⋅h =

=h2⋅∑

x=a

b−h

f x f xh=

=h2⋅2⋅∑x=a

b

f x − f a f b= =h⋅∑

x=a

b

f x −h2⋅ f a f b=K a

b−h2⋅ f a f b=F a

b−h2⋅ f a− f b.

E Gab=−h

2⋅ f a f b.

Gab=K a

b−h2⋅ f a f b


● Numerische Integration– Integration 2-ter Ordnung

● Simpsonsche Regel– Funktionswerte gegeben durch

Parabel in den Funktionswerten f(c), f(c+h), f(c+2h).

– Beweis durch Addition benachbarter Doppelflächen

f(x)p(h)

p(4h)

p(0)

h

p(2h)p(3h)

p(6h)p(5h)

S ab=h

3⋅ f 04⋅ f 12⋅ f 24⋅ f 32⋅ f 4 f N

mit f k= f ak⋅h , N=b−ahgerade!

S ab=h

3⋅2⋅F a

b

h f b− f a− f b2⋅F ah ,2h

b−h

2⋅h f b−h

=23

F ab1

3⋅F ah ,2h

b−h h3⋅ f b− f a2 f b−h



● Interpolation d. Polynom 2 Grades

p x =a⋅x2b⋅xcp 0= f 0=c ,p h= f h=a⋅h2b⋅hc ,p 2⋅h= f 2⋅h=a⋅2 h2b⋅2⋅hc .

H 02=∫

0

2h

p x dx=13⋅a x 31

2⋅b x2c x=1

3⋅a 2 h31

2⋅b 2 h2c 2 h=

=2 h6⋅2⋅a 2 h23⋅b 2 h6⋅c=h

3⋅8⋅a h26⋅b h6⋅c=

=h3⋅ p 04⋅p h p 2 h=h

3⋅ f 04⋅ f h f 2 h.

f(x)p(h)

p(2h)

p(0)

hh

S ab=h

3⋅ f 04⋅ f 12⋅ f 24⋅ f 32⋅ f 4 f N

mit f k= f ak⋅h , N=b−a gerade!

1

2

a b



● f2i=2, f2i+1=1, i=0,..,N

● Integration über [a,b]

● Verkleinerung des Integrationsintervalls [a+h,b-h]

S ab=h

3⋅ f 04⋅ f 12⋅ f 24⋅ f 32⋅ f 4 f N=

=h3⋅24⋅12⋅24⋅12⋅22=h

3⋅N⋅4= 4

3⋅b−a .

S ahb−h=h

3⋅ f 14⋅ f 22⋅ f 34⋅ f 42⋅ f 5 f N−1=

=h3⋅14⋅22⋅14⋅22⋅11=h

3⋅N−2

2⋅10=5

3⋅b−a−10

3⋅h .


● 'Mittelung' überlappter Flächen● numerisch einfacher zu berechnen2⋅T a

b=F 0H 02H 1

3H 24H b−2

b F b−1=

F 0F b−1h3⋅ f a4⋅ f ah f a2 h f ah4⋅ f a2 h f a3 h=

= F 0F b−1h3⋅6⋅K a

b

h−5⋅ f a− f ah− f b−h−5⋅ f b=

= 2⋅K ab h

125 f a8 f ah− f a2 h5 f b8 f b−h− f b−2 h[s.u. ]

h3⋅−5⋅ f a− f ah− f b−h−5⋅ f b=

= 2⋅K ab h

12−15 f a4 f ah− f a2 h−15⋅ f b4 f b−h− f b−2 h.

T ab=K a

b− h2415⋅ f a f b−4 f ah f b−h f a2 h f b−2 h.

f(x)p(h)

p(4h)

p(0)

h

p(2h)p(3h)

p(6h)p(5h)

Hb-1bH0

1 H12 H2

3

f(x)p(h)

p(4h)

p(0)

h

p(2h)p(3h)

p(6h)p(5h)

Hb-1bH0

1 H12 H2

3


● 'Mittelung' überlappter Flächen– daher u.U. genauer

● numerisch einfacher zu berechnen als Simpsonsche Regel– Summe über alle Ordinaten - Korrektur– Korrekturterm hängt ab von

ersten und letzten drei Ordinaten

● Ergebnis

● Korrekturterm

T ab=K a

b− h2415⋅ f b f a−4⋅ f ah f b−h f a2 h f b−2 h.

E T ab=− h

24 15⋅ f b f a−4⋅ f ah f b−h f a2 h f b−2 h.



1

2

a b

F ab=K a

b−h⋅ f b=32⋅b−a,

Gab=K a

b−h2⋅ f a f b= 3

2⋅b−a.

K ab=h⋅3⋅n /2h=3 b−a/2h ,

K ah ,2hb−h =h⋅2⋅n /2=b−a

S ab=2

3K a

b13⋅K ah ,2h

b−h −h3⋅ f a f b=b−a2

3⋅hb−a

3= 4

3⋅b−a2

3⋅h .

T ab=K a

b− h2415⋅ f a f b−4 f ah f b−h f a2 h f b−2 h=

=3 b−a/2h− h2415⋅2−4⋅42=3 b−a/2h−2

3⋅h= 3

2⋅b−a1

3⋅h .


● Numerische Integration (Numerische Quadratur)– Integration 2-ter Ordnung einer Fläche (F0)

F 0=H 01=∫

0

h

p x dx=

=13⋅a x31

2⋅b x2c x=

=13⋅a h31

2⋅b h2c⋅h =

=h6⋅2⋅a h23⋅b h6 c=

=h6⋅−1

2⋅ f 24⋅ f 15

2⋅ f 0=

= h12⋅5⋅ f 08⋅ f 1− f 2

f(x)p(h)

p(4h)

p(0)

h

p(2h)p(3h)

p(6h)p(5h)

F0 F1 F2 Fb-1


● Fourier-Analyse– Zerlege eine Funktion in 'orthogonale' Summanden:– Beispiel: Periodische Funktion in Summe von

trigonometrische Funktionen








● Fourier-Analyse– Fourierreihe

– Koeffizienten

f x =a0

2∑

k=1

∞

ak⋅cos k⋅xbk⋅sin k⋅x

ak=1⋅∫−

f x ⋅cos k⋅x dx , k = 0, 1, 2,

bk=1⋅∫−

f x ⋅sin k⋅x dx , k = 1, 2, 3,


● Fourier-Analyse– Fourierreihe: Beispiel ak=1/k

– Summenkurve

f x =a0

2∑

k=1

∞

ak⋅cos k⋅xbk⋅sin k⋅x

-1,7

-1,

-1,2

-1

-0,7

-0,

-0,2

0

0,2

0,

0,7

1

1,2

1,

1,7


● Fouriertransformation– Verallgemeinerung der Fourier-Analyse auf nicht

periodische Funktionen

– mit den Koeffizienten

– Abbildung der Zeitdarstellung in Frequenzdarstellung– Fouriertransformation in komplexer Darstellung

f x =∫0

∞

a y ⋅cos x⋅yb y ⋅sin x⋅y dy

a y =1⋅∫

0

∞

f u⋅cos y⋅udu ,

b y =1⋅∫

0

∞

f u⋅sin y⋅udu. }F y = 1

2⋅∫−∞

∞

f x ⋅ei⋅xydx


● Schnelle Fourier-Transformation– Aufwand quadratisch in Anzahl der Punkte

● u.U. zu groß– Schnelle Fourier-Transformation

FFT Fast Fourier Transformation● Schnelle Hartley-Transformation– Äquivalent wie Fourier-Transformation– keine komplexen Zahlen!– weniger Rechenoperationen (im 'Normalfall').– kann in Fourier-Transformierte umgerechnet werden

(trotz vieler Vorteile eher selten benutzt)


● Lineares Gleichungssystem– Lineare Gleichung ersten Grades

● a1·x1 + a2·x2 + … + ak·xk + … + aN·xN = a0

– Lineares Gleichungssystem● Mehrere Gleichungen mit gleichen Variablen x1, x2, …, xN

– Finde x1, x2, …, xN, die alle Gleichungen erfüllen

– Systematische Lösung durch Gaußsches Eliminationsverfahren


● Lineares Gleichungssystem– Gaußsches Eliminationsverfahren● Beispiel

● Erweitere Gleichung 1 mit 2 und 3 und subtrahiere von Gleichung 2 und 3

● Erweitere Gleichung 2 mit -1 und subtrahiere von Gleichung 3

x + 2⋅y + 3⋅z = 142⋅x + 2⋅y + 1⋅z = 93⋅x + 4⋅y + 2⋅z = 17

x + 2⋅y + 3⋅z = 14−2⋅y + −5⋅z = −19−2⋅y + −7⋅z = −25

x + 2⋅y + 3⋅z = 14−2⋅y + −5⋅z = −19

−2⋅z = −6

Numerische Algorithmen● Lineares Gleichungssystem– Gaußsches Eliminationsverfahren● Setze 'rückwärts' ein

● Probleme– Rundungsfehler aufgrund großer Anzahl von Differenzen● möglichst kleines Element nullsetzen

– Aufwand O(N3)● verschiedene Ansätze in Spezialsituationen für geringeren Aufwand● z.B. dünn besetzte Matrix (d.h. viele Koeffizienten = 0)

−2⋅z = −6 ⇒ z=3

−2⋅y + −5⋅z = −19 ⇒ y=−1915−2

=2

x + 2⋅y + 3⋅z = 14 ⇒ x=14−9−41

=1


● Gaußsches Eliminationsverfahren

static void triangle1() { for(int zeile=1; zeile<anzGl; zeile++) // 2. bis letzte Zeile for(int rest=zeile;rest<anzGl;rest++) // restliche Zeilen for(int spalte=anzVar+1; spalte>=zeile; spalte--) // subtrahiere Zeile Feld[rest][spalte] -= Feld[zeile-1][spalte]* Feld[rest][zeile]/

Numerische Algorithmen● Gaußsches Eliminationsverfahrenstatic void triangle2() { for(int zeile=1;zeile<anzGl;zeile++) { int max=zeile; for(int rest=zeile+1;rest<anzGl;rest++) if(Math.abs(Feld[rest][zeile])< Math.abs(Feld[max][zeile])) max = rest; // max. Element if(max!=zeile) // vertausche Zeilen for (int spalte = 0; spalte<=anzVar+1; spalte++) { double swap = Feld[zeile][spalte];

Numerische Algorithmen● Gaußsches Eliminationsverfahren– Partielles Pivotieren

● nur unten links Nullen● Dreiecksmatrixa b c d e = f0 g h i j = k0 0 l m n = p0 0 0 q r = s0 0 0 0 t = u

● Lösung durch 'Rückwärtseinsetzen'.X5 = u/tX4 = (s-r∙x5)/qusw.

Numerische Algorithmen● Gaußsches Eliminationsverfahren– Vollständiges Pivotieren

● unten und oben Nullen● Diagonalmatrixa 0 0 0 0 = b; x1 = b/a0 c 0 0 0 = d; x2 = d/c0 0 e 0 0 = f; x3 = f/e0 0 0 g 0 = h; x4 = h/g0 0 0 0 i = j; x5 = j/i

for(int rest = 0; rest<zeile-1; rest++) for(int spalte = anzVar + 1; spalte >= zeile; spalte--) Feld[rest][spalte] -= Feld[zeile - 1][spalte] *

Numerische Algorithmen● Lineare Optimierung– Reale Systeme modellieren durch

● System linearer Ungleichungen● Beipiel

– Herstellung verschiedener Waren Wn auf Maschinen Mm

– Lmn: Laufzeiten je produzierter Einheit

– Zm: Gesamtlaufzeiten der Maschinen je Woche

– Gn: Gewinne je Produkteinheit

– Welche Mengen xn auf welchen Maschinen produzieren – Gewinn soll maximiert werden!

● Mathematisches Modell (n = 1…4, m = 1…3) – x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x4 ≥ 0;

– L11·x1 + L12·x2 + L13·x3 + L14·x4 ≤ Z1,


● Lineare Optimierung– effiziente Verfahren zur Lösung solcher Probleme – Simplexverfahren nach Dantzig– Problem in Normalform als System von Ungleichungen

x1≥0 ; x2≥0 ; x v≥0 ;a11⋅x1 + a12⋅x2 + + a1 v⋅x v ≤b1 ,

ak1⋅x1 + ak2⋅x2 + + akv⋅x v ≤b1

ag1⋅x1 + ag2⋅x2 + + agv⋅x v ≤b1

e1⋅x1 + e2⋅x2 + + ev⋅x v =Zielfunktion (zu maximieren)


● LineareOptimierung–Mathematisches Problem

graphisch formulieren–Lösung durch Verschieben

der Zielgeraden–Alle Lösungen liegen in

Eckpunkten

–Lösung: (x1=4, x2=7)x1≥0 ; x2≥0 ; −x1 + x2 ≤ 4 ,−x1 + 2⋅x2 ≤ 10 ,

14⋅x1 + 8⋅x2 ≤ 112 ,3⋅x1 + 2⋅x2 ≤ 30 ,x1 + x2 = Zielfunktion

● Mathematische Lösung des Optimierungsproblems– graphisch Lösungen nur bei zwei Variablen möglich– rein mathematische Lösungsmethode – Ungleichungen zu Gleichungen machen– Einführung von g „Schlupfvariablen“ xv+1, ... , xv+g


x1≥0 ; x2≥0 ; x v≥0 ;a11⋅x1 + a12⋅x2 + + a1 v⋅x v + x v1 + + 0 =b1 ,

ak1⋅x1 + ak2⋅x2 + + akv⋅x v + + x vk + =bk ,

ag1⋅x1 + ag2⋅x2 + + agv⋅x v + 0 + + x vg =bg ,e1⋅x1 + e2⋅x2 + + ev⋅x v + 0⋅x v1 + + 0⋅x vg =ziel .


● Mathematische Lösung des Optimierungsproblems– Beispiel:

– Hyperebene im v-dimensionalen Raum v ● Menge der Punkte

a1·x1 + a2·x2 + … + av·xv = b.● Hyperebene im 2 ist Gerade ● Hyperebene im 3 ist Ebene usw.

x1≥0 ; x2≥0 ; −x1 + x2 + x 3 = 4 ,−x1 + 2⋅x2 + x 4 = 10 ,

14⋅x1 + 8⋅x2 + x5 = 112 ,3⋅x1 + 2⋅x2 + x6 = 30 ,1⋅x1 + 1⋅x2 = Zielfunktion.

z0 0 4 10 112 30 00 4 0 2 80 22 40 5 -1 0 72 20 54 7 1 0 0 4 11

x1 x2 x3 x4 x5 x6


● Lineare Optimierung– Schlupfvariablen

● Gewichteter Abstand zu einer Hyperebene


● Lineare Optimierung– 1. Lösungsansatz

● Setze von den v+g Variablen jeweils v auf null● Löse das Gleichungssystem aus g Gleichungen mit g Variablen● Berechne jeweils Zielfunktionswert● Bestimme maximalen Wert und daraus Optimum

● Es gibt verschiedene Gleichungssysteme

● Für großes v und g zu viel!

vgv =vg

g 2v

Numerische Algorithmen● Lineare Optimierung– Ecke im v-dimensionalen Raum v

● Schnittpunkt von v Hyperebenen.

– Nichtbasisvariable● v Variablen xi mit Wert null

● Wir sagen auch Nullvariable

– Basisvariable● g Variable mit Wert größer als null (in der Regel)


● Lineare Optimierung– Effiziente Lösung des Optimierungsproblems

● Ecken heißen 'benachbart' wenn sie sich nur in einer Hyperebene unterscheiden

● Austauschverfahren:Ersetze eine Basisvariable durch Nullvariable und umgekehrt

● Wähle neue Basisvariable aus bisherigen Nullvariablen– maximaler Anstieg der Zielfunktion

● Wähle Nullvariable aus bisherigen Basisvariable– Zulässigkeit bei Umformung


● Gleichungssystem

● Zulässige Anfangswerte: x1=x2=...=xv=0.

● Lösungxv+1=b1; xv+2=b2;...=xv+g=bg.

● Zielfunktionswert = 0.


x1≥0 ; x2≥0 ; x v≥0 ;a11⋅x1 + a12⋅x2 + + a1 v⋅x v + x v1 + + 0 =b1 ,

ak1⋅x1 + ak2⋅x2 + + akv⋅x v + + x vk + =bk ,

ag1⋅x1 + ag2⋅x2 + + agv⋅x v + 0 + + x vg =bg ,e1⋅x1 + e2⋅x2 + + av⋅x v + 0⋅x v1 + + 0⋅x vg =ziel .


● Simplextableau

● BV: Basisvariable● in erster Spalte eingetragen● Wert der Basisvariablen in vorletzter Spalte (b)


B x1 x k x v x v1 x vg b qx v1 a11 a1 k a1 v 1 0 b1

x v j a j1 a jk a jv 1 b j

x vg ag1 agk agv 0 1 bg , x v1 e1 ek ev 0 0 ziel


● Wert aller Nichtbasisvariablen null– Nullvariablen

● Koeffizienten von Nichtbasisvariablen i.d.R. nicht null● Für jede Basisvariablen gilt

– genau eine Gleichung mit Koeffizient 1– alle anderen Gleichungen haben Koeffizienten null – Werte der Basisvariablen aktuelle Lösung des Gleichungssystems

● Koeffizienten der Zielfunktion – nur bei Nullvariablen Wert ungleich null – Wert der Zielfunktion ist -be, zu Anfang null


● Lineare Optimierung● Austauschalgorithmus

● Suche Spalte k mit maximalem Wert ek

– Maximaler Zuwachs der Zielfunktion (nicht garantiert)

● Wähle Minimum aller nicht negativen bn/bk.– In nachfolgender Operation bleiben rechte Seiten nicht negativ

● Kürze Zeile k durch akn

● Subtrahiere ajk∙Zeile k von allen Zeilen j=1..k-1, k+1...g.

● xk wird neue Basisvariable

● Neue Nullvariable wird xn, (In Spalte n ist ajn=1)


● Lineare Optimierung– Austauschalgorithmus

– Austausch wiederholen, bis alle eK ≤ 0.

– Optimum sind Werte der Variablen x1, x2, ..., xv.● Nullvariablen erhalten den Wert null● Basisvariablen erhalten den Wert bk.


B x1 xk x v x v1 x vg b qx v1 a11−a1k a j1/a jk 0 a1 v−a1k a jv /a jk 1 −a1k /a jk 0 b1−a1k b j /a jk

x v j a j1/a jk 1 a jv /a jk 1/a jk b j /a jk

x vg ag1−agk a j1/a jk 0 agv−agk a jv /a jk 0 1 bg−agk b j /a jk , x v1 e1−ek a j1/a jk 0 ev−ek a jv /a jk 0 −ek /a jk 0 z−ek b j /a jk

● Lineare Optimierung– Erweiterungen

● nehme auch >-Bedingungen auf– setze Koeffizienten auf -1 (statt + 1)– Basisvariable (stets ≥ 0), also rechte Seite unter Schranke

● nehme auch =-Bedingungen auf– füge Gleichung ohne Schlupfvariable ein – daher ist 'Schlupfvariable' stets null– es muss eine andere Basisvariable gesucht werden

● ändere Anfangsbedingungen: – x1≥c1>0, x2≥c2>0, ..., xv≥cv>0.

– durch Anfangstransformation

– Algorithmus sollte Konsistenz der Daten überprüfen!



● Spline-Interpolation– Gegeben N Messwerte (xi,yi)i=0,..,N-1.

– Gesucht: Möglichst glatte Kurve durch die Messwerte

x0 x1 x2 xN-2 xN-1

y0

y1

y2 yN-2yN-1


● Spline-Interpolation– Mathematisch aufwändige Analyse (s. Web-Skript)

● Erstelle für je zwei Punkte (xi,xi+1) Polynom dritten Grades● Polynom stimmt in Endpunkten überein.● 1. und 2. Ableitung der Polynome in (xi-1,xi) und (xi,xi+1)

stimmen in xi überein.

x0 x1 x2 xN-2 xN-1

y0

y1

y2

yN-2 yN-1

Documents

Numerische Methoden - einstein.informatik.uni-oldenburg.deeinstein.informatik.uni-oldenburg.de/.../grund/04ss/ad2/Numerik-ohne.pdf · Algorithmen für nicht ganzzahlige Probleme –