Vorlesung vom 6.12.13 Stabilitätsabschätzungen€¦ · Stabilitätsabschätzungen Vorlesung...

Stabilitatsabschatzungen Vorlesung vom 6.12.13

Auswertungsbaume zur systematischen StabilitatsabschatzungAuswertungsbaum: Knoten, gerichtete Kanten, Wurzel, Blatter

Zerlegung in Teilbaume

Von den Blattern zur Wurzel:

rekursive Funktionsauswertung und Stabilitatsabschatzung

Theoretische Grundlage: Satz 7.6 und Satz 7.9

Beispiele.

SummationsalgorithmenRekursive Summation, Auswertungsbaum, Stbilitatsanalyse

Hierarchische Summation.

CoMa I

bisher:

Auswirkung von (Rundungs)-Fehlern auf das Ergebnis:

Kondition eines Problems: Eingabefehler

Stabilitat eines Algorithmus: Auswertungsfehler

jetzt:

Rechenaufwand:

Komplexitat eines Problems

Effizienz eines Algorithmus

CoMa I

bisher:

Auswirkung von (Rundungs)-Fehlern auf das Ergebnis:

Kondition eines Problems: Eingabefehler

Stabilitat eines Algorithmus: Auswertungsfehler

jetzt:

Rechenaufwand:

Komplexitat eines Problems

Aufwand und Effizienz eines Algorithmus

CoMa I

Komplexitat und Effizienz

Wie lange muß ich auf das Ergebnis warten?

a) Ist das Problem schwierig? (Komplexitat)

b) Ist mein Algorithmus zu langsam? (Effizienz)

Theoretische Informatik/Diskrete Mathematik:

Komplexitatstheorie, Berechenbare Funktionen

CoMa I

Aufwand (Laufzeit) eines Algorithmus

hangt ab von: Algorithmus, Eingabedaten (”Große“ des Problems)

Aufwandsmaß: reine Rechenzeit

zusatzliche Parameter:

Implementierung, Programmiersprache, Compiler, Prozessor,...

Aufwandsmaß: Anzahl dominanter Operationen

allgemeingultige Resultate

CoMa I

Aufwand (Laufzeit) eines Algorithmus

hangt ab von: Algorithmus, Eingabedaten (”Große“des Problems)

Aufwandsmaß: reine Rechenzeit

zusatzliche Parameter:

Implementierung, Programmiersprache, Compiler, Prozessor,...

Aufwandsmaß: Anzahl dominanter Operationen (problemabhangig!)

implementierungsunabhangige Resultate

CoMa I

Rekursive Summation positiver Zahlen

rekursive Summation: S = a[1]; for i=2:1:m S = S + a[i]; end

Aufwandsmaß: Anzahl der Additionen

Aufwand des rekursiven Algorithmus: n− 1

CoMa I

Hierarchische Summationx1 x2 x3 x4 x5 x6 x7 x8

ցւ ցւ ցւ ցւs(1)1 s

(1)2 s

(1)3 s

ց ւ ց ւs(2)1 s

ց ւs(3)1

Aufwand des hierarchischen Algorithmus: (n = 2J):

2J−1 + · · ·+ 1 =J−1∑

2j =2J − 1

2− 1= 2J − 1 = n− 1

CoMa I

(1)2 s

(1)3 s

ց ւ ց ւs(2)1 s

ց ւs(3)1

2J−1 + · · ·+ 1 =J−1∑

2j =2J − 1

2− 1= 2J − 1 = n− 1

CoMa I

(1)2 s

(1)3 s

ց ւ ց ւs(2)1 s

ց ւs(3)1

2J−1 + · · ·+ 1 =J−1∑

2j= 2J−12−1 = 2J − 1 = n− 1

CoMa I

(1)2 s

(1)3 s

ց ւ ց ւs(2)1 s

ց ւs(3)1

2J−1 + · · ·+ 1 =J−1∑

2j =2J − 1

2− 1= 2J − 1= n− 1

CoMa I

(1)2 s

(1)3 s

ց ւ ց ւs(2)1 s

ց ւs(3)1

2J−1 + · · ·+ 1 =J−1∑

2j =2J − 1

2− 1= 2J − 1 = n− 1

CoMa I

Komplexitat der Summation positiver Zahlen

Kann es einen Algorithmus geben, der weniger als n−1 Additionen benotigt?

Folgerung: Die Komplexitat der Addition von n Zahlen ist n− 1

CoMa I

Folgerung: Die Komplexitat der Addition von n Zahlen ist n− 1

CoMa I

Folgerung: Die Komplexitat der Addition von n Zahlen ist n− 1.

CoMa I

Aufwand und KomplexitatDefinition 2.4

Problem (P), Algorithmen A(P ) zur Losung von (P)

Eingabedaten der Lange n, Referenzoperation (problemspezifisch!)

Der Aufwand TA(n) eines Algorithmus A ∈ A(P ) ist das

Maximum der benotigten Anzahl von Referenzoperationen

uber alle zulassigen Eingabedaten der Lange n.

Definition 2.5

Die Komplexitat KP (n) von (P) ist

KP (n) = infA∈A(P )

TA(P )

CoMa I

Definition 2.5

TA(P )

CoMa I

Definition 2.5

TA(P )

CoMa I

Effiziente Algorithmen

Problem (P), Algorithmus A ∈ A(P ) zur Losung von (P)

Effizienz eines Algorithmus’ A:

Theoretische Informatik: TA = O(np)

Numerische Mathematik: TA(n) = O(KP (n))

Definition Landau-Symbol O(·) fur f(n), g(n) → ∞ fur n → ∞

f(n) = O(g(n)) fur n → ∞ ⇐⇒ lim supn→∞

Beispiel: 18n3 + 3n2 + sin(en) = O(n3)

CoMa I

Definition Landau-Symbol O(·) fur f(n), g(n) → ∞ fur n → ∞

CoMa I

Definition: Landau-Symbol O(·) fur f(n), g(n) → ∞ fur n → ∞

CoMa I

Definition: Landau-Symbol O(·) fur f(n), g(n) → ∞ fur n → ∞

CoMa I

Sortieren

gegeben: z1, z2, . . . , zn ∈ R

gesucht: Permutation (Umordnung) π: zπ(1), zπ(2), . . . , zπ(n)

Algorithmus: TumbSort: Alle Umordnungen durchprobieren.

Aufwandsmaß: Vergleich zweier Zahlen

Aufwand von TumSort: O(nn)

CoMa I

Sortieren

gegeben: z1, z2, . . . , zn ∈ R

CoMa I

Sortieren

gegeben: z1, z2, . . . , zn ∈ R

CoMa I

Sortieren

gegeben: z1, z2, . . . , zn ∈ R

CoMa I

Sortieren

gegeben: z1, z2, . . . , zn ∈ R

CoMa I

BubbleSort

Algorithmus: BubbleSort: Sukzessive Maximierung

Beispiel:

S = {7, 1, 5} , k = 3 : SMax = max{7, 1, 5} = 7, iMax = 1

S = {5, 1, 7} , k = 2 : SMax = max{5, 1} = 5, iMax = 1

S = {1, 5, 7}

Aufwand von BubbleSort:

(n− 1) + (n− 2) + · · ·+ 1 =n−1∑

k = 12n(n− 1) = O(n2)

CoMa I

BubbleSort

Beispiel:

S = {7, 1, 5} , k = 3 : SMax = max{7, 1, 5} = 7, iMax = 1

S = {5, 1, 7} , k = 2 : SMax = max{5, 1} = 5, iMax = 1

S = {1, 5, 7}

(n− 1) + (n− 2) + · · ·+ 1 =n−1∑

k = 12n(n− 1) = O(n2)

CoMa I

BubbleSort

Beispiel:

S = {7, 1, 5} , k = 3 : SMax = max{7, 1, 5} = 7, iMax = 1

S = {5, 1, 7} , k = 2 : SMax = max{5, 1} = 5, iMax = 1

S = {1, 5, 7}

(n− 1) + (n− 2) + · · ·+ 1 =n−1∑

k = 12n(n− 1) = O(n2)

CoMa I

BubbleSort

Beispiel:

S = {7, 1, 5} , k = 3 : SMax = max{7, 1, 5} = 7, iMax = 1

S = {5, 1, 7} , k = 2 : SMax = max{5, 1} = 5, iMax = 1

S = {1, 5, 7}

(n− 1) + (n− 2) + · · ·+ 1 =n−1∑

k = 12n(n− 1) = O(n2)

CoMa I

BubbleSort

Beispiel:

S = {7, 1, 5} , k = 3 : SMax = max{7, 1, 5} = 7, iMax = 1

S = {5, 1, 7} , k = 2 : SMax = max{5, 1} = 5, iMax = 1

S = {1, 5, 7}

(n− 1) + (n− 2) + · · ·+ 1 =n−1∑

k= 12n(n− 1) = O(n2)

CoMa I

BubbleSort

Beispiel:

S = {7, 1, 5} , k = 3 : SMax = max{7, 1, 5} = 7, iMax = 1

S = {5, 1, 7} , k = 2 : SMax = max{5, 1} = 5, iMax = 1

S = {1, 5, 7}

(n− 1) + (n− 2) + · · ·+ 1 =n−1∑

k = 12n(n− 1)= O(n2)

CoMa I

BubbleSort

Beispiel:

S = {7, 1, 5} , k = 3 : SMax = max{7, 1, 5} = 7, iMax = 1

S = {5, 1, 7} , k = 2 : SMax = max{5, 1} = 5, iMax = 1

S = {1, 5, 7}

(n− 1) + (n− 2) + · · ·+ 1 =n−1∑

k = 12n(n− 1) = O(n2)

CoMa I

BubbleSort

Beispiel:

S = {7, 1, 5} , k = 3 : SMax = max{7, 1, 5} = 7, iMax = 1

S = {5, 1, 7} , k = 2 : SMax = max{5, 1} = 5, iMax = 1

S = {1, 5, 7}

(n− 1) + (n− 2) + · · ·+ 1 =n−1∑

k = 12n(n− 1) = O(n2) ≪ O(nn)

CoMa I

Merging (cont.)

3 10 23 54 1 5 25 75 X: Y:

Result:

Merging (cont.)

3 10 23 54 5 25 75

Result:

Merging (cont.)

10 23 54 5 25 75

Result:

Merging (cont.)

10 23 54 25 75

Result:

Merging (cont.)

23 54 25 75

1 3 5 10

Result:

Merging (cont.)

54 25 75

1 3 5 10 23

Result:

Merging (cont.)

1 3 5 10 23 25

Result:

Merging (cont.)

1 3 5 10 23 25 54

Result:

Merging (cont.)

1 3 5 10 23 25 54 75

Result:

Divide And Conquer

l  Merging a two lists of one element each is the same as sorting them.

l  Merge sort divides up an unsorted list until the above condition is met and then sorts the divided parts back together in pairs.

l  Specifically this can be done by recursively dividing the unsorted list in half, merge sorting the right side then the left side and then merging the right and left back together.

Merge Sort Algorithm

Given a list L with a length k: l  If k == 1 à the list is sorted l Else:

–  Merge Sort the left side (1 thru k/2) –  Merge Sort the right side (k/2+1 thru k) –  Merge the right side with the left side

Merge Sort Example 99 6 86 15 58 35 86 4 0

99 6 86 15 58 35 86 4 0

86 15 99 6 58 35 86 4 0

99 6 86 15 58 35 86 4 0

86 15 99 6 58 35 86 4 0

99 6 86 15 58 35 86 4 0

86 15 99 6 58 35 86 4 0

99 6 86 15 58 35 86 4 0

Merge Sort Example

99 6 86 15 58 35 86 0 4

4 0 Merge

Merge Sort Example

15 86 6 99 58 35 0 4 86

99 6 86 15 58 35 86 0 4

Merge Sort Example

6 15 86 99 0 4 35 58 86

15 86 6 99 58 35 0 4 86

6 15 86 99 0 4 35 58 86

Implementing Merge Sort l  There are two basic ways to implement merge sort:

–  In Place: Merging is done with only the input array l  Pro: Requires only the space needed to hold the array l  Con: Takes longer to merge because if the next

element is in the right side then all of the elements must be moved down.

–  Double Storage: Merging is done with a temporary array of the same size as the input array. l  Pro: Faster than In Place since the temp array holds

the resulting array until both left and right sides are merged into the temp array, then the temp array is appended over the input array.

l  Con: The memory requirement is doubled.

Merge Sort Analysis The Double Memory Merge Sort runs O (N log N) for all cases, because of its Divide and Conquer approach.

T(N) = 2T(N/2) + N = O(N logN)

MergeSort

U(1)1 U

ւ ց ւ ց

U(2)1 U

(2)2 U

(2)3 U

ւց ւց ւց ւց

U(3)1 U

(3)2 U

(3)3 U

(3)4 U

(3)5 U

(3)6 U

(3)7 U

Aufwand von MergeSort: TMergeSort(n) ≤ n log2 n optimal!

CoMa I

MergeSort

U(1)1 U

ւ ց ւ ց

U(2)1 U

(2)2 U

(2)3 U

ւց ւց ւց ւց

U(3)1 U

(3)2 U

(3)3 U

(3)4 U

(3)5 U

(3)6 U

(3)7 U

CoMa I

MergeSort

U(1)1 U

ւ ց ւ ց

U(2)1 U

(2)2 U

(2)3 U

ւց ւց ւց ւց

U(3)1 U

(3)2 U

(3)3 U

(3)4 U

(3)5 U

(3)6 U

(3)7 U

CoMa I

Berechnung von ggT (a, b)

Definition 4.1 (großter gemeinsamer Teiler – ggT)

Eine Zahl d, die zwei ganze Zahlen a, b ∈ N teilt (d|a und d|b),heißt gemeinsamer Teiler von a und b.

Die großte positive Zahl d, die gemeinsamer Teiler von a und b ist,

heißt großter gemeinsamer Teiler von a und b oder kurz ggT (a, b).

Problem (P): Berechne ggT (a, b) fur Eingabedaten a ≥ b ∈ N \ {0}

CoMa I

Ausprobieren: TumbGGT (Algorithmus 4.3)

Input: positive Zahlen a >= b>0

Output: ggT(a,b)

ggT := 1

for i = 2:b

if i|a and i|b

ggT := i

endfor

return ggT

Aufwandsmaß: Anzahl der Divisionen mit Rest Aufwand: 2(b−1)

CoMa I

Output: ggT(a,b)

ggT := 1

for i = 2:b

if i|a and i|b

ggT := i

endfor

return ggT

CoMa I

Output: ggT(a,b)

ggT := 1

for i = 2:b

if i|a and i|b

ggT := i

endfor

return ggT

CoMa I

Geschickteres Ausprobieren: TumbGGT++

Output: ggT(a,b)

for i := b:2

if i|a and i|b

return i

endfor

return 1

Aufwandsmaß: Anzahl der Divisionen Aufwandsschranke: 2(b− 1)

CoMa I

Output: ggT(a,b)

for i := b:2

if i|a and i|b

return i

endfor

return 1

CoMa I

Output: ggT(a,b)

for i := b:2

if i|a and i|b

return i

endfor

return 1

CoMa I

Strukturelle Einsicht

Definition 4.6 (Kongruenzen)Der bei Division von a durch b bleibende Rest heißt

a mod b = a− ⌊a/b⌋b .

m, n ∈ Z heißen kongruent modulo b, falls m mod b = n mod b.

modulo-Funktion: mod(a, b) = a mod b

Satz 5.5 (Rekursionssatz fur den ggT)Es gilt

ggT (a, b) = ggT (b,mod(a, b)) ∀a, b ∈ N .

CoMa I

Strukturelle Einsicht

Definition 4.6 (Kongruenzen)Der bei Division von a durch b bleibende Rest heißt

a mod b = a− ⌊a/b⌋b .

m, n ∈ Z heißen kongruent modulo b, falls m mod b = n mod b.

modulo-Funktion: mod(a, b) = a mod b

Lemma 4.12 (Rekursionssatz fur den ggT)Es gilt

ggT (a, b) = ggT (b,mod(a, b)) ∀a, b ∈ N .

CoMa I

Umsetzung: Der Euklidische Algorithmus

Output: ggT(a,b)

m = a;

n = b;

while n>0

r = m modulo n

endwhile

return m

Satz: Der Euklidische Algorithmus terminiert nach hochstens b Schritten.

CoMa I

Umsetzung: Der Euklidische Algorithmus

Output: ggT(a,b)

m = a;

n = b;

while n>0

r = m modulo n

endwhile

return m

Satz: Der Euklidische Algorithmus terminiert nach hochstens b Schritten.

CoMa I

AufwandsanalyseDefinition (Fibonacchi–Zahlen)Die durch die Drei–Term–Rekursion

Fn+1 − Fn − Fn−1 = 0 , F0 = 1 , F1 = 1

definierten Zahlen Fk, k = 0, 1, . . . , heißen Fibonacchi–Zahlen.

Lemma 4.14Es sei a > b. Terminiert der Euklidische Algorithmus nach genau k ≥ 1Schritten, so gilt a ≥ Fk+1 und b ≥ Fk.

Satz 4.15 (Lame, 1848)Gilt a > b und b < Fk+1 mit k ∈ N, so terminiert der EuklidischeAlgorithmus nach hochstens k Schritten.

Bemerkung (Lemma 5.8):Im Falle b = Fk, a = Fk+1 braucht man k Schritte.

CoMa I

Fn+1 − Fn − Fn−1 = 0 , F0 = 1 , F1 = 1

Bemerkung :Im Falle b = Fk, a = Fk+1 braucht man k Schritte.

CoMa I

Fn+1 − Fn − Fn−1 = 0 , F0 = 1 , F1 = 1

Bemerkung :Im Falle b = Fk, a = Fk+1 braucht man k Schritte.

CoMa I

Fn+1 − Fn − Fn−1 = 0 , F0 = 1 , F1 = 1

Bemerkung:Im Falle b = Fk, a = Fk+1 braucht man k Schritte.

CoMa I

Aufwandsschranke fur den Euklidischen Algorithmus

Moivre-Binet: Fk = (φk − (1− φ)k)/√5 φ = 1+

Satz 4.16Fur den Aufwand TEA des Euklidische Algorithmus gilt

TEA(n) = logΦ(b) + 1, Φ =1 +

Bemerkung:

Das ist eine exponentielle Verbesserung gegenuber dem naiven Algorith-mus!

Beispiel: logΦ(10.000) < 20 ≪ 10.000

CoMa I

Satz 4.16Fur den Aufwand TEA(n) des Euklidische Algorithmus gilt

TEA(n) ≤ logφ(b) + 1

Bemerkung:

Das ist eine exponentielle Verbesserung gegenuber dem naiven Algorith-mus!

Beispiel: logΦ(10.000) < 20 ≪ 10.000

CoMa I

Satz 4.16Fur den Aufwand TEA(n) des Euklidische Algorithmus gilt

TEA(n) ≤ logφ(b) + 1

Bemerkung:

Das ist eine exponentielle Verbesserung gegenuber TUMBGGT!

Beispiel: logΦ(10.000) < 20 ≪ 10.000

CoMa I

Principal component analysis

Speicherbedarf o(n2)

• If we want to optimize we must start at the most expensive step.

• Here: calculation of the correlation matrix.

• In complex programs, 99% of the runtime are spent in 1% of the code.

Vorlesung vom 6.12.13 Stabilitätsabschätzungen€¦ · Stabilitätsabschätzungen Vorlesung...

Documents

Getrennte Parameter- und Zustandssch atzung zur …tuprints.ulb.tu-darmstadt.de/370/1/Dis_Pf.pdfErkl arung Hiermit versichere ich an Eides statt, daˇ ich die vorliegende Arbeit mit

Beitr¤ge zur Baustatik, Elastizit¤tstheorie, Stabilit¤tstheorie, Bodenmechanik

Quantile - Fakultät für Wirtschaftswissenschaften · Quantile Andreas Handl Inhaltsverzeichnis 1 Was sind Quantile und wozu ben¨otigt man sie? 2 2Sch¨atzung von Quantilen 5 2.1

GRUNDLAGEN UND ANWENDUNG EINES ...oceanrep.geomar.de/21892/1/IFM-BER_87.pdf1.3.3 Stabilit~tsschranken 1.3.4 Fehlerbetrachtungen 1.3.5 Die Abbildung der Ostsee auf eine Tar.· gentialebene

BMW 2er Gran Tourer Katalog Maerz 2020€¦ · – Dynamische Stabilit äts Control (DSC) inkl. Dynamische Traktions Control (DTC) – Performance Control – Auff ahrwarnung mit

Zur asymptotischen Stabilität linearer differential ... · Technische Universität Ilmenau Fakultät f ür Mathematik und Naturwissenschaften Fachgebiet Analysis und Systemtheorie

Anwendung der Extremwerttheorie zur Sch atzung des Value ... · Zusammenfassung Die vorliegende Masterarbeit besch aftigt sich mit der Sch atzung des Value at Risks und des Expected

Getrennte Parameter- und Zustandssch atzung zur … · FMEA Fehleranalyse (Failure Mode E ect Analysis) FMECA Gef ahrungsanalyse (Failure Mode E ect and Criticality Analysis) IBIT

Lineare gemischte Modelle zur Schätzung von strukturiert ... · – Stationäre Gauss-Felder können als Oberflächenschätzer mit speziellen Basisfunktionen betrachtet werden

BMW X3 Katalog April 2020€¦ · – Dynamische Stabilit äts Control (DSC) inkl. Dynamische Traktions Control (DTC) – Parkbremse elektr omechanisch – Auff ahrwarnung mit City-Bremsfunktion

Datenerhebung und Sch atzung bei sensitiven Merkmalenarchiv.ub.uni-marburg.de/diss/z2013/0349/pdf/dgh.pdf · Erstgutachter: Prof. Dr. Karlheinz Fleischer Zweitgutachter: Prof. Dr

Regenwassernutzung - premiertechaqua.de · Die besondere Geometrie macht NEO zu einem in Sachen Stabilit t, Gewicht und Haltbarkeit un bertroffenen Flachtank- Modell mit bis zu 35

Zur Stabilit - dynardo.de€¦ · Zur Stabilit ¨ at von SQP-Verfahren und zur L ¨ osung globaler und gemischt-ganzzahliger Optimierungsprobleme KlausSchittkowski FachgruppeAngewandteInformatik

Stabilität von Runge-Kutta-Verfahren · Stabilität von Runge-Kutta-Verfahren Tobias Jahnke Vorlesung Numerische Methoden fur¨ Differentialgleichungen Wintersemester 2011/12

2 Fehleranalyse: Kondition, Rundungsfehler, Stabilit¨at€¦ · Institut f¨ur Geometrie und Praktische Mathematik a RHEINISCH-WESTFALISCHE TECHNISCHE HOCHSCHULE AACHEN¨ 2 Fehleranalyse:

Simulation des Einsatzh artens und Absch atzung der ... · Danksagung Die vorliegende Arbeit entstand parallel zu meiner T atigkeit als wissenschaftlicher Angestellter der Materialforschungs-

Stabilit atsprobleme vollverkehrsabh angiger ...stefanlaemmer.de/en/Publications/Laemmer2009a.pdf · Stabilit atsprobleme vollverkehrsabh angiger Lichtsignalsteuerungen Kurzfassung

Bayessche Methoden zur Sch atzung von Stammb aumen mit ...evol.bio.lmu.de/_statgen/software/treetime/Dissertation.pdf · Methode zurechtgeschnitten und werden sp ater implementiert

Zur thermodynamischen Stabilit¨at von Proteinen ... · • Wie faltet sich das Protein zu seiner nat¨urlichen, nativen Form? • Unter welchen physikalischen Bedingungen ist die

Lyapunov Stabilitat¨ - Startseite TU Ilmenau · Kapitel 2 Lyapunov Stabilitat¨ In diesem Kapitel soll es um die Stabilit¨atstheorie von Gleichgewichten (siehe Deﬁnition 1.9)