Beispiel: f(x) = 1 - cos(x) für x ≈ 0:

f(x) ist wieder gut konditioniert bei 0, da

Aber bei 0 ist cos(x) nahe bei 1 wieder Auslöschung!

66

0,2)2/1(1)cos(1

)sin(2

2

x

x

x

x

xx

f

fxcond x

In MATLAB: 1 - cos(10^(-8)) ergibt 0;

und mit cos(10^(-3)) = 0.99999950000004

verliert man bei der Differenz 6 signifikante Stellen

67

Anderer Berechnungsweg:

1 - cos(x) = 2 sin2(x/2)

!6!42

)!6!42

1(1)cos(1642642 xxxxxx

x

oder Reihenentwicklung des Cosinus

1 – cos(x) für x=2π ? |𝑥𝑓′ 𝑥

𝑓 𝑥| = |

𝑥𝑠𝑖𝑛 𝑥

1 − cos 𝑥|

Beispiel: y = a2 – b2 bei |a|=|b|

Anwendung der Epsilontik; seien a,b Maschinenzahlen:

Berechne erst beide Produkte, dann die Differenz.

68

3222

2

122

2

22

2

22

2 22appbay

ba

b

ba

a

ba

b

ba

a

Fehler: Eingabefehler Produktfehler Differenzfehler

Relativer Fehler:

Nun seien auch a und b fehlerhaft: a(1+a), b(1+b)

321 111 app bbaa

32

2

1

2 11)1(1)1( apbpa bbaa

Andere Art der Berechnung: y = ( a – b )( a + b )

69

)1()1()1()1()1()1()1( * baba babaf

)1()21()21( *

22 ba ba

*22

2

22

2 22

ba

ba

b

ba

a

22

2

22

2

ba

a

ba

da

dya

conda

22

2

22

2

ba

b

ba

db

dyb

condb

Konditionszahlen:

,

Problem ist schlecht konditioniert für |a| |b|

Relativer Fehler in erster Näherung:

Vergleich mit erstem Algorithmus:

Das neue Verfahren ist besser, da i.W. nur der

unvermeidbare Fehler (durch Eingabefehler) auftritt!

Grund: Auslöschung in a - b geringer als in a2 – b2 ,

da Fehler in a und b kleiner als in a2 und b2 .

70

Zusammenfassung

Endlichkeit des Computers führt zu endlicher Menge von

Maschinenzahlen.

In jedem Schritt treten Rundungsfehler auf.

Gefährlich sind Operationen, bei denen man signifikante

Stellen verliert, wie z.B.:

- Auslöschung (Differenz fast gleicher, fehlerhafter Zahlen)

- Summe zwischen großer Zahl und sehr kleiner Zahl,

bei der die signifikanten Stellen in der kleinen

Zahl stecken (vgl. wiederholtes Wurzelziehen)

- Allgemein Operationsfolgen mit großen Zwischen-

werten und kleinen Endwerten

(vgl. exp, Teilfunktion schlecht konditioniert).71

Vorsicht! Gesundes Misstrauen!

Algorithmus ist OK, wenn die Größenordnung der

relativen Fehler im Resultat ungefähr gleich der

Größenordnung der Eingabefehler bleibt.

Umformen eines numerisch instabilen Verfahrens durch

- andere Reihenfolge der Berechnung

- Anfang der Taylorentwicklung

- Trigonometrische Formeln

- algebraische Umformung (binomische F.)

- ....

- Ev. double precision rechnen, damit trotz schlechter

Kondition oder Rundungsfehler noch brauchbares

Resultat übrigbleibt.72

Systematische Fehler und große Zahl der Operationen können

zu schlechten Ergebnissen führen!

(Siehe Beispiel Börsenindex)

Ev. Modellfehler gegen Rundungsfehler abwägen:

Feineres Modell Mehr Rechnung Mehr Rundungsfehler!

Man muss die optimale Balance finden!

Beispiel Übungsaufgabe Differenzenquotient.

Gesamtfehler:

73

Grob diskretisiert Optimum fein diskretisiert

Modellfehler Rundungsfehler

Beispiel: Verbesserte Fehleranalyse für den numerisch

instabilen Fall großer Zwischenwerte

Zerlege Problem f(x) in zwei Schritte

y = f(x) = f2(f1(x)) = f2(z)

wobei z = f1(x) großer Zwischenwert und

y = f2(z) kleiner Endwert.

74

Daher ist Teilproblem f2(z) für diese Werte schlecht

konditioniert,

da |z / f2 (z)| groß ist!

Daher ist Gesamtverfahren nicht numerisch stabil für x.

ff1 f2

x z y

Beispiel f(a,b)=a+b. a+b+…+z = f(…f(f(a,b),c),…,z)

75

Verfahren ist numerisch stabil, wenn für jede Zerlegung

in Teilprobleme f2(f1(x)) = f2(z), z = f1(x) , f2(z) stets

gut konditioniert ist! Keine großen Zwischenwerte!

Konditionszahl Gesamtproblem

Numerisch stabil Berechnungsform

Genauere Analyse der numerischen Stabilität durch Bestim-

mung der Konditionszahlen und Ableitungen aller Teilschritte:

Zerlege Algorithmus in Teilprobleme f(x) = f2(f1(x)) und

berechne alle auftretenden Konditionszahlen cond(f2)!

Meist zu aufwändig oder unmöglich.

76

Epsilontik genügt für uns:

(i) (Ersetze xx(1+ε), x op y (x op y)(1+ε)

(ii) Streiche Terme höherer Ordnung in ε2, ε3, ε4, …

(iii) Bestimme damit den rel. Fehler des Resultats (f – y)/f

in erster Näherung und schätze Beträge ab nach oben

(iv) Diskutiere die einzelnen Terme.

Ziel:

Erkenne aus Formel (Programm), bzw. berechneten (Zwischen)werten,

- ob das Problem gut konditioniert ist, und

- ob das verwendete Verfahren numerisch stabil ist,

- bzw. wie das Verfahren ev. verbessert werden kann.

77

Klausuraufgabe: f(x)=exp(x)-1, g(x)=1-x+x2-x3, h(x)=(1+x2)(1-cos2(x))

78

Schlecht konditionierte Probleme:

- Wettervorhersage- Aktienentwicklung: Black-Scholes Gleichungen- Chaos-Theorie in dynamischen Gleichungen- …

Sprunghaft, chaotisch, parameterabhängig, selbstbezüglichBlack Swan - Effekt

Vorsicht mit Vorhersagen:“Die einzigen Vorhersagen, die wirklich zutreffen sind die, dieman nachträglich macht.”Vorsicht bei nachträglicher Bewertung von Vorhersagen!Psychologische Effekte.

9

Neuronale Netze

9

Eingabe

x1

x2

x3

x4

y4

w1

w2

w3

w4

𝑦4 = 𝑤1𝑥1 + 𝑤2𝑥2+𝑤3𝑥3+𝑤4𝑥4 = 𝑤𝑇𝑥

𝑓(𝑥)

𝑦 = 𝑊𝑥 Vektor y,x; Matrix W

W1W2 W3 W4

10

Anwendung

Mit bekannten Testdaten werden die Gewichte w so justiert,

dass für die Testdaten möglichst die richtigen Ergebnisse geliefert werden.

Eingabe: Bilder

Ausgabe: Panzer ist auf dem Bild ja/nein.

11

Anwendung

Mit bekannten Testdaten werden die Gewichte w so justiert,

dass für die Testdaten möglichst die richtigen Ergebnisse geliefert werden.

Probleme: - welche Kriterien benutzt das Netz?

- Undurchschaubarkeit

- nur Wahrscheinlichkeiten

- ethische Klassifizierung

Erkennung von Kriminellen.

Handwerkliche Fehler!

80% kriminell?

12

Anwendung

Probleme: - welche Kriterien benutzt das Netz?

- Undurchschaubarkeit

- nur Wahrscheinlichkeiten

- ethische Klassifizierung

Erkennung von sexueller Neigung.

Handwerkliche Fehler!

Wozu?

3.1 Dreiecksgleichungssysteme

Beispiel: Unbekannte x1, x2, x3:

13

2.62.6

5.255.2

70710

3

32

321

x

xx

xxx

2.6

5.2

7

2.600

55.20

0710

3

2

1

x

x

x

In Matrixschreibweise:

Wegen der Dreiecksform lässt sich das System leicht von

unten her auflösen:

14

;0,0777710

;1,5.255.25.2

;1;12.6/2.6

121

232

33

xalsoxx

xalsoxx

xalsox

;

1

1

0

3

2

1

x

x

x

Lösungsvektor:

Probe durch Einsetzen!

Allgemein:

wird gelöst mittels Programm 3.1.1.:

15

nnnn

n

n

b

b

b

x

x

x

a

aa

aaa

2

1

2

1

222

11211

ii

n

ij jiji

i

nnnn

a

xabx

nnifür

abx

1

:1,,2,1

;/

Genauso wird das untere Dreieckssystem

von oben her gelöst mit dem Programm:

16

nnnnn b

b

b

x

x

x

aa

aa

a

2

1

2

1

1

2221

11

ii

i

j jiji

ia

xabx

nifür

abx

1

1

1111

:,,3,2

;/

Wichtig: Alle , da sonst System nicht eindeutig lösbar!0iia

0)det( 2211 nnaaaA

Immer lösbar?

3.2 Einschub: Rechnen mit Matrizen

Matrix

beschreibt Abbildung

x f(x) = Ax = b .

17

mn

nmn

m

aa

aa

A ,

1

111

Matrizen bilden kommutative Gruppe bzgl. +, bzw.

Invertierbare nxn-Matrizen bilden sogar Gruppe bzgl. *(aber nicht kommutativ! AB≠BA)

A–1 * A = I = Einheitsmatrix = Identität = 1

Spezialfall:

18

Rba

b

b

aaban

j

jj

n

n

T

1

1

1

Matrix-Multiplikation: A * B = C

k

r

rjirij bac1

ist Skalarprodukt (Inneres Produkt) der Vektoren a und b

i

19

mnn

m

m

n

T

baba

baba

bb

a

a

ba

1

111

1

1

nm

ijij

Tmn

jiji

T aaA,

1,,

,

1,,

Spiegelung an der Hauptdiagonalen

Eine invertierbare n x n–Matrix A hat vollen Rang n und det(A) ≠ 0

als Äußeres Produkt von a und b.

A = a bT ist Rang-1-Matrix, d.h. die durch A beschriebene

Abbildung f(x) hat eindimensionalen Bildraum:

f(x) = A x = (a bT ) x = (b T x ) a = r(x)*a

bildet die 2-dim. Ebene auf die Gerade durch den Vektor a ab.

3.2.1. Beispiele:

Abbildung

20

2

1

2

1*

11

11

2

1)(

y

y

x

xxf

2/1

1

0

1*

11

11

2

1

2/

1

1

1

0*

11

11

2

1

Daher: und

Weitere Beispiele

21

Google Page-Rank Matrix: Tabelle von Webseiten-Verlinkung:

0320

2010

1101

0010

4

3

2

1

4321

w

w

w

w

wwww

21

21

2

1

2

1

dxcx

bxax

x

x

dc

ba

y

y

Matrix beschreibt lineare Abbildung:

Bild filtern: oder eindimensional

010

141

010

8

1

210

1

1

012

1214

1

3.2.2. Orthonormalbasis:

Vektoren uj , j=1,...,n mit ujTuk = 0 für j ≠ k

ujTuk = 1 für j = k

Dies sind n linear unabhängige Vektoren, also eine

Basis des Rn oder ein Koordinatensystem.

22

Norm: ||x||2 = xTx ist die euklid’sche Länge.

Eigenschaften: ||x|| > 0 für x ≠ 0

||a*x|| = |a|*||x|| für aR

||x+y|| <= ||x|| + ||y||

und

|xT y| <= ||x||*||y|| Gleichheit möglich?

23

Q ist orthogonale Matrix, wenn stets

||Qx||2 =||x||2 oder xTQTQx = xTx , d.h.

QTQ = I oder Q–1 = QT

Die Spalten (Zeilen) von Q bilden eine Orthonormalbasis!

Dann ist

x = inv(A)*b = A–1 * b

Ein lineares Gleichungssystem hat entweder

eindeutige/keine/unendlich viele Lösungen! Beispiele?

nnxAxAb

,11,

Ein lineares Gleichungssystem Ax = b ist lösbar, falls

Rang(A) = Rang(A | b), d.h.

b ist durch Spalten von A darstellbar.

Denn mit der Lösung x (falls sie existiert) ist b = Ax eine

Linearkombination von Spalten von A:

Exkurs: Eigenwerte und Eigenvektoren

Ein Vektor u heißt Eigenvektor zu Eigenwert λ, wenn gilt:

Richtung u beschreibt Fixgerade der Abbildung y=Ax

24

MatrixnnAuAuu ,:0

Ist A reell symmetrisch, A=AT, so gilt sogar:

Es existieren n paarweise orthogonale Eigenvektoren,

also eine Orthonormal-Basis des |Rn,

u1,…,un , Auj = λj uj , ui ┴ uj für i ≠ j, || uj || = 1

Uuuuu

AuAuuuAAU

n

nnn

nn

1

111

11

AUU TU liefert ideale Basis für A:

Tacoma Narrows/London Millenium Bridge

3.3 Gauss-Elimination

3.3.1. Beispiel:

25

655

4623

70710

321

321

321

xxx

xxx

xxx

Grundidee: Zurückführung auf den bekannten Fall

eines Dreiecksgleichungssystems.

6

4

7

515

623

0710

3

2

1

x

x

x

In Matrixschreibweise:

3.3.2. Erlaubte Transformationen:

- Multiplizieren einer Zeile (Gleichung) mit einer Zahl

verschieden von Null.

- Addieren eines Vielfachen einer Zeile zu einer

anderen Zeile (Gleichung).

- Vertauschen von Zeilen (Gleichungen), bzw. Spalten

(Unbekannten) (entspricht Umnummerierung).

26

Operationen sind dabei nicht nur an der Matrix durchzuführen,

sondern ev. auch an der rechten Seite (Vektor b) und dem

Lösungsvektor x!

Benutze diese Regeln, um in der Matrix die Subdiagonal-

Elemente der Reihe nach von oben nach unten, bzw.

von links nach rechts, zu Null zu machen

Dreieckssystem.

Zu Eliminieren: -3

Addiere dazu zur zweiten Zeile die erste, multipliziert mit 3/10.

27

10/3

,

6

4

7

515

623

0710

3

2

1

x

x

x

|

10/5

,

6

1.6

7

515

61.00

0710

3

2

1

x

x

x

Danach soll 5 zu Null werden:

Dritte Zeile - 5/10 * Erste Zeile

Ergibt:

28

1.0/5.2,

5.2

1.6

7

55.20

61.00

0710

3

2

1

x

x

x

Dieses System kann nun von unten her aufgelöst werden,

wie in Abschnitt 3.1. beschrieben.

,

155

1.6

7

15500

61.00

0710

3

2

1

x

x

xResultat:

Eliminiere 2.5 in letzter Zeile.

Lösung: ( 0 -1 1); was fällt auf?

Benutze also jeweils das Diagonalelement, um die

darunter liegenden Einträge Spalte für Spalte zu

eliminieren, und zwar von a11 , a22 , bis an-1,n-1.

29

|

10/510/3

,

6

4

7

515

61.23

0710

3

2

1

x

x

x

Im Beispiel: Ersetze a22 = 2 durch a22 = 2.1

Problem: Es könnte irgendwann eine Null auf der

Diagonalen auftreten: aii=0 !!!???

Was dann?

Immer lösbar?

30

.

5.2

1.6

7

55.20

600

0710

3

2

1

x

x

x

1.6

5.2

7

600

55.20

0710

3

2

1

x

x

x

Problem gelöst!

Um Fortfahren zu können, ist eine Vertauschung

notwendig, z.B. vertausche zweite Zeile mit dritter Zeile.

Betrachten wir das ursprüngliche System, so sehen wir,

dass wir zwar ohne Vertauschung durchkommen, aber

der Wert -0.1 auf der Diagonalen a22 führt zu der großen

Zahl 155 in der letzten Zeile.

31

Erinnerung: Zu vermeiden sind große Zwischenwerte!

Daher ist es auch im ursprünglichen System besser, die

Vertauschung von zweiter und dritter Zeile vorzunehmen.

32

5.2/1.0

1.6

5.2

7

61.00

55.20

0710

3

2

1

x

x

x

Es treten keine großen Zwischenwerte mehr auf.

2.6

5.2

7

2.600

55.20

0710

3

2

1

x

x

x

Dann lautet der letzte Eliminationsschritt

Allgemeines Vorgehen: Pivotsuche

Sieht im k-ten Eliminationsschritt so aus:

33

nnnk

nkkk

kk

n

aa

aa

a

aa

00

00

0

,

1,1

111

Suche in Untermatrix ‚großen’ Eintrag und vertausche

entsprechend Zeilen und Spalten, so dass diese große

Zahl an die Diagonal-Position akk kommt.

Dieses Element heißt Pivotelement.

Gebräuchlichste Variante:

3.3.3. Spaltenpivotsuche:

Durchsuche nur die Spalte von akk bis ank nach

betragsgrößtem Element ajk und vertausche dann

die gefundene Zeile j mit der k-ten Zeile.

Der Zusatzaufwand ist gering, da nur jeweils eine Spalte

durchsucht werden muss, und zwei Zeilen (Gleichungen)

vertauscht werden müssen.

Vertausche also zwei Zeilen in der Matrix und entsprechend

in der rechten Seite b.

34

Weniger üblich - Zeilenpivotsuche:

Durchsuche die k-te Zeile nach betragsgrößtem Element

und vertausche zwei Spalten (= Umnummerierung in

Vektor x), so dass das betragsgrößte Element der k-ten

Zeile an die Diagonalposition kommt.

Keine Vertauschungen in b nötig!

35

Totalpivotsuche:

Durchsuche die gesamte n-k+1 x n-k+1 – Untermatrix und

vertausche sowohl Spalten, als auch Zeilen, um das betrags-

größte Element an die Diagonalposition zu versetzen.

Aufwändig! Nur sinnvoll, wenn das Gleichungssystem sehr

schlecht konditioniert ist! (Mehr dazu später)

3.3.4. Umwandlung auf Dreiecksform mit

Spaltenpivotsuche:

Algorithmus der Gauss-Elimination.

1. Teil des Programms: Pivotsuche und –vertauschung

FOR k=1,...,n-1 DO

alpha = |a(k,k)|; j=k;

FOR s=k+1,...,n DO

IF |a(s,k)| > alpha THEN

alpha = |a(s,k)|; j=s;

ENDIF

ENDFOR

# Pivotelement ist a(j,k) und Pivotzeile ist j

FOR i=k,...,n DO

alpha = a(k,i); a(k,i) = a(j,i); a(j,i) = alpha;

ENDFOR

alpha = b(j); b(j) = b(k); b(k) = alpha;36

2. Teil: Eigentliche Elimination

# Eliminationsschritt

FOR s=k+1,...,n DO

l(s,k) = a(s,k)/a(k,k);

b(s) = b(s) - l(s,k)b(k);

FOR i=k+1,...,n DO

a(s,i) = a(s,i) - l(s,k)a(k,i);

ENDFOR

ENDFOR

ENDFOR

37

Dadurch ist das System auf obere Dreiecksform gebracht,

und kann wie in 3.1 beschrieben einfach von unten her

gelöst werden.