Mathematik 3 - fma2.math.uni-magdeburg.defma2.math.uni-magdeburg.de/~averkov/mathe3info_page/Mathe_3_fuer_In... · Mathematik 3 f ur Informatik G. Averkov Institut fur Mathematische

Mathematik 3fur Informatik

G. AverkovInstitut fur Mathematische Optimierung

Fakultat fur Mathematik

OvGU Magdeburg

19. Dezember 2018

ii

Inhaltsverzeichnis

I Stochastik 31 Stochastik im endlichen Fall . . . . . . . . . . . . . . . . . . . . . . . 32 Stochastik im allgemeinen Fall . . . . . . . . . . . . . . . . . . . . . . 133 Parameter stochastischer Verteilungen . . . . . . . . . . . . . . . . . 194 Der Zoo stochastischer Verteilungen . . . . . . . . . . . . . . . . . . . 285 Mittelwert umfangreicher Stichproben . . . . . . . . . . . . . . . . . . 376 Ausblick und Literaturhinweise . . . . . . . . . . . . . . . . . . . . . 41

II Statistik 431 Statistische Schatzung . . . . . . . . . . . . . . . . . . . . . . . . . . 432 Zahlwahrscheinlichkeit einer unfairen Munze . . . . . . . . . . . . . . 463 Schatzungen fur Normalverteilung . . . . . . . . . . . . . . . . . . . . 504 Lineare Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545 Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

IIINumerische Mathematik 611 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612 Numerische Integration . . . . . . . . . . . . . . . . . . . . . . . . . . 703 Diskrete Fourier-Transformation . . . . . . . . . . . . . . . . . . . . . 744 Faktorisierungen von Matrizen . . . . . . . . . . . . . . . . . . . . . . 825 Gestorte Matrizen und Lineare Gleichungssysteme . . . . . . . . . . . 936 Iterative Losungsverfahren fur Gleichungsysteme . . . . . . . . . . . . 977 Numerische Losung nichtlinearer Gleichungssysteme . . . . . . . . . . 101

IV Gewohnliche Differentialgleichungen 1031 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1032 Lineare Gleichungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

V Kurven und Flachen 107

iii

iv INHALTSVERZEICHNIS

INHALTSVERZEICHNIS 1

Bezeichnungen

Z die Menge der ganzen ZahlenZ+ die Menge der nichtnegativen ganzen ZahlenN die Menge positiver ganzen Zahlen (wir nennen die Elemente von N

naturliche Zahlen).R die Menge der reellen ZahlenR+ die Menge der nichnegativen reellen Zahlen

2 INHALTSVERZEICHNIS

Kapitel I

Stochastik

Wir behandeln zufallige Ereignisse, Zufallsvariablen und Verteilungen, bedingte War-hscheinlichkeit, den Erwartungswert und die Varianz, die Kovarianz und die Korre-lation.

1 Stochastik im endlichen Fall

1.1. Die Stochastik (= Wahrscheinlichkeitstheorie) ist die Theorie der zufalligen Er-eignisse und der Zufallsvariablen. Neben den Zufallsvariablen kann man auch weiterezufallige Strukturen betrachten

(a) zufallige Funktionen (stochsastische Prozesse, Zufallsfelder)

(b) zufallige Graphen

(c) randomisierte Algorithmen (Quick Sort, randomisierte Primzahltests und vieleandere).

Stochastik auf endlichen Wahrscheinlichkeitraume wird auf elementarer Mathematikaufgebaut. Daher ist es praktisch, zuerst den endlichen Fall kennenzulernen.

1.2. Stochastik und Statistik haben zahlreiche Anwendungen in verschiedensten An-wendungsbereichen:

(a) Wirtschaft und Finanzen

(b) Medizin

(c) Ingenieurwesen

(d) Robotik

(e) Geologie

(f) Bildverarbeitung

(g) Machine Learning und Kunstliche Intelligenz (stochastic gradient descent usw.)

(h) Data Science (vgl. Machine Learning)

Die Liste der Anwendungen kann man beliebig fortsetzen und prazisieren.

3

4 KAPITEL I. STOCHASTIK

1.3 Def (Grundbegriffe). Im Folgenden werden immer wieder die folgendenGrundbegriffe benutzt:

(a) Ein endlicher Wahrscheinlichkeitsraum ist ein Paar (Ω, P ), mit einer end-lichen nichtleeren Menge Ω und einer Funktion P : Ω→ R mit

P (ω) ≥ 0

fur alle ω ∈ Ω und ∑ω∈Ω

P (ω) = 1.

(b) Die Elemente ω ∈ Ω bzw. die Mengen ω heißen Elementarereignisse.

(c) Die Menge Ω heißt Ereignisraum.

(d) Teilmengen von Ω heißen Ereignisse,

(e) Der Wert

P (A) :=∑ω∈A

P (ω)

heißt die Wahrscheinlichkeit des Ereignis A ⊆ Ω.

(f) Das Ereignis Ω heißt sicheres Ereignis,

(g) Die leere Menge heißt unmogliches Ereignis.

(h) Fur ein Ereignis A heißt A := Ω \ A das Gegenereignis von A.

(i) Fur Ereignisse A,B kann man ihr Durchschnitt

AB := A ∩B

und die Vereinigung A ∪ B betrachten. (Es ist praktisch, fur den Durch-schnitt die Kurze Bezeichnung AB einzufuhren, um spater die Formel etwaskompakter zu halten.)

(j) Ereignisse A, B mit A ∩B = ∅ heißen disjunkt.

Im Folgenden beziehen wir uns auf einen zugrundeliegenden Wahrscheinlich-keitsraum.

TODO: Zufallsexperiment: Bild und Beschreibung. ω ist eine Art Bericht uberden Ausgang des Zufallsexperiments

1.4 Bsp. Einige oft benutzte endliche Wahrscheinlichkeitsraume:

(a) Munzwurf : Ω = Kopf,Zahl = 0, 1 und P (ω) = 12

fur die beiden ω aus Ω.

(b) Wurfeln: Ω = 1, . . . , 6 und P (ω) = 16

fur alle ω ∈ Ω.

(c) Zweifaches Wurfeln: Ω = 1, . . . , 62 und P (ω) = 136

fur alle ω ∈ Ω.

1. STOCHASTIK IM ENDLICHEN FALL 5

Finden Sie Beispiele verschiedener Ereignisse im Rahmen dieser Ereignisraume.

1.5. Man betrachtet oft Ereignisraume mit P (ω) = 1|Ω| (alle Elementarereignisse

haben die gleiche Wahrscheinlichkeit). Fur solche Raume gilt

P (A) =|A||Ω|

.

Um P (A) zu ermitteln reicht es die Anzahl der Elemente in A und Ω zu zahlen. Mankann also die Kombinatorik (= Theorie des Zahlens) benutzen.

1.6 Bsp (Berechnung der Wahrscheinlicheiten durch einfaches Zahlen). Hier ein sehreinfaches Beispiel zur Bemerkung 1.5. Wir betrachten das Ereignis

A := “Augenzahlen unterscheiden sich genau um eins”

beim zweifachen Wurfeln. Fur das zweifache Wurfeln ist der Ereignisraum

Ω := 1, . . . , 62 = (i, j) : i, j = 1, . . . , 6

mit den Wahrscheinlichkeiten P (ω) = 1|Ω| = 1

36der Elementarereignisse ω ∈ Ω. Nun

ist das Ereignis A, das wir mit Worten beschrieben haben, – mathematisch gesehen– die Menge

A := (1, 2), (2, 3), (3, 4), (4, 5), (5, 6)︸︷︷︸5 Elementarereignisse

, (2, 1), (3, 2), (4, 3), (5, 4), (6, 5)︸︷︷︸5 Elementarereignisse

.

aus genau 10 Elementarereignissen. Die Wahrscheinlichkeit von A ist somit

P (A) =|A||Ω|

=10

36.

Wenn man das Zahlen gut beherrscht, kann man ziemlich viele Aufgaben zur Be-rechnung der Wahrscheinlichkeiten im endlichen Fall nach diesem Muster losen. Manbeachte dabei: der Wahrscheinlichkeitsraum (Ω, P ) ist nicht unbedingt durch die Auf-gabe vorgegeben. Man hat manchmal eine Wahl zwischen mehreren Moglichkeiten.Die Moglichkeiten hangen davon ab, wie viel Information man in den Elementarer-eignissen ω ∈ Ω behalten will.

1.7 Bsp. Eine Urne enthalt zwei weiße und zwei schwarze Balle. Man zieht zufallighintereinander alle 4 Balle aus der Urne. Wie groß ist die Wahrscheinlichkeit, dassman die Balle in der Reihenfolge weiß, schwarz, weiß, schwarz zieht?

1.8. Ubungsblatter 0, 1 und 2 enthalten Aufgaben zum Zahlen und Aufgaben aus derWahrscheinlichkeitstheorie, die durch das Zahlen gelost werden konnen. Beim Losendieser Aufgaben konnen die Anzahl folgender Objekte nutzlich sein:

(a) Eine n-elementige Menge hat 2n Teilmengen.

(b) Eine n-elementige Menge besitzt(nk

)k-elementige Teilmengen. Hierbeit ist

(nk

)der Binomialkoeffizient, gegeben als(

n

k

)=

n!

k!(n− k)!=n · . . . · (n− k + 1)

k!.


(c) Man hat |B||A| Abbildungen von A nach B. Mit anderen Worten: wenn k un-terscheidbare Personen je eine Kugel Eis kaufen, wobei man n Eissorten zurAuswahl hat, so gibt es nk Kaufmoglichkeiten.

(d) Es gibt |B| · (|B| − 1) · . . . · (|B| − |A|+ 1) injektive Abbildungen von A nach B.Mit anderen Worten: wenn k Personen n Sitzplatze belegen, so gibt es n · (n−1) · . . . · (n− k + 1) mogliche Sitzordnungen.

(e) Es gibt |A|! bijektive Abbildungen von A nach A. Mit anderen Worten: wenn nPersonen n Sitzplatze belegen, so gibt es n! mogliche Sitzordnungen.

(f) Elemente in der Vereinigung von Mengen A1, . . . , Ak (das sogenannte Prinzipvon Inklusion und Exklusion). Etwa fur k = 2:

|A1 ∪ A2| = |A1|+ |A2|+ |A1 ∪ A2|.

TODO: Bild zu Inklusion-Exklusion

1.9. Fur beliebige Ereignisse A und B gilt:

(a) P (A) = 1− P (A),

(b) P (A ∪B) = P (A) + P (B)− P (A ∩B).

(b) ist das Prinzip von Inklusion und Exklusion fur die Wahrscheinlichkeiten im Fallvon Vereinigung von zwei Mengen. Wie sieht eine entsprechende Formel P (A∪B∪C)im Fall von drei Ereignissen A,B,C aus?

1.10 Def. Fur Ereignisse A,B mit P (B) > 0 heißt

P (A|B) :=P (AB)

P (B)

die Wahrscheinlichkeit von A unter der Bedingung B bzw. die bedingte Wahr-scheinlichkeit von A, vorausgesetzt B.

1.11. Die Berechnung der Bedingten Wahrscheinlichkeit unter einer Bedingung Bkann man als einen Ubergang in einen anderen Wahrscheinlichkeitsraum interpretie-ren. In diesem neuen Raum geht man von der Annahme aus, dass das Ereignis Bangetreten sei, sodass man die Wahrscheinlichkeiten aller anderen Ereignisse mit derBerucksichtigung dieser Annahme berechnet.

1.12. Untersuchung von Abhangkeiten bzw. Unabhangigkeit verschiedener zufalligenEreignisse und Werte ist die Lieblingsbeschaftigung von Stochastikern und Statisti-kern. Sogar ganz normale Menschen sind oft daran interessiert (vergleiche verschie-dene Beitrage in den Medien). Hier eines der sehr vielen Beispiele aus den Medien:


Die sogenannte bedingte Wahrscheinlichkeit ist eines der Hauptmittel, Abhangigkeitenformal im Rahmen der Stochastik zu behandeln. Man kann also formal Frage wie dieFolgende stellen:

P (guter Chirurg | guter Zocker) > P ( guter Chirurg | kein guter Zocker) ?

1.13 Thm. Seien A1, . . . , Am, B endlich viele Ereignisse mit m ≥ 1, fur welcheP (Ai) > 0 fur alle i = 1, . . . ,m und

⋃mi=1 Ai = Ω gilt und A1, . . . , Am paarweise

disjunkt sind. Dann gilt:

(a) P (B) =∑m

i=1 P (Ai)P (B|Ai).

(b) Im Fall P (B) > 0 gilt die sogenannte Formel von Bayes

P (Ai|B) =P (Ai)P (B|Ai)

P (B)=

P (Ai)P (B|Ai)∑mi=1 P (Ai)P (B|Ai)

fur alle i = 1, . . . ,m.

1.14 Bsp (Berechnung der Wahrscheinlichkeiten mit Hilfe bedingter Wahrschein-lichkeiten). In der Schule wird Thm 1.13(a) oft benutzt, um die ‘Urnen-Aufgaben’zu losen. Hier ein Beispiel einer solchen Aufgabe. In einer Urne liegen 2 weiße und 3schwarze Balle. Man zieht zwei Balle zufallig und soll die Wahrscheinlichkeit berech-nen, dass die Balle verschieden Farbe haben. Dies ist unser Ereignis

B := “die beiden gezogenen Balle haben verschiedene Farbe”.

Nun betrachten wir zusatzlich die Ereignisse

A1 := “der erste gezogene Ball ist weiß”


undA2 := “der erste gezogene Ball ist schwarz”.

Die Ereignisse A1 und A2 sind disjunkt (konnen nicht gemeinsam antreten). Also sinddie Voraussetzungen von Thm 1.13 (mit m = 2) erfullt. Die Wahrscheinlichkeit vonA1 ist 2

2+3= 2

5. Die Wahrscheinlichkeit von A2 ist 3

2+3= 3

5. Unter der Voraussetzung,

dass A1 angetreten ist, liegen in der Urne beim Ziehen des zweiten Balls genau 1weißer und 3 schwarze Balle. Unter dieser Voraussetzung ist die Wahrscheinlichkeitvon B gleich 3

1+3= 3

4, oder formal P (B|A1) = 3

4. Unter der Voraussetzung, dass A2

angetreten ist, ist die Wahrscheinlichkeit von B – nach ahnlichen Uberlegungen –gleich 2

2+2= 1

2, oder formal P (B|A2) = 1

2. Wir haben somit alle Daten um P (B)

nach Thm 1.13(a) zu berechnen:

P (B) = P (A1)P (B|A1) + P (A2)P (B|A2) =2

5· 3

4+

3

5· 1

2=

6

10.

1.15. Wie bereits erwahnt verwendet man das Rechenmuster aus Bsp 1.14 oft in derSchule. Alternativ kann man aber auch das Zahlen wie in Bsp 1.6 verwenden. Hier einkleiner Hinweis, wie man es genauer umsetzen kann. Jeder Ball in der Urne bekommteine Nummer oder ein Label: erster weiße Ball, zweiter weiße Ball, erster schwarzeBall, zweiter weißer Ball, dritter weißer Ball. Somit kennen wir alle 5 Balle quasi beiNamen. Wir verwenden lieber Nummern 1, 2, 3, 4, 5 (etwa, 1, 2 sind die weißen Balle,und 3, 4, 5 die Schwarzen). Nun kann man den Ereignisraum Ω als die Menge derPaare (i, j) mit i, j ∈ 1, . . . , 5 mit i 6= j festlegen. D.h.,

Ω := (i, j) : i, j = 1, . . . , 5 mit i 6= j .

Es gilt P (ω) = 1|Ω| . Man kann nun zahlen, wie viele Elemente Ω hat und aus wie

vielen Elementen das B – modelliert als Teilmenge von Ω – besteht, um P (B) nach

der Formel P (B) = |B||Ω| zu berechnen.

Umgekehrt kann man die Wahrscheinlichkeit aus Bsp 1.6 mit Hilfe bedingterWahrscheinlichkeit ausrechnen. Sie konnen sich gerne uberlegen, wie man das tunkonnte.

1.16 Bsp. k Personen steigen im Erdgeschoss eines Gebaudes in einen Aufzug ein.Jede Person druckt (zufallig) einen der Knopfe 1, 2, 3. Wie hoch ist die Wahrschein-lichkeit, dass der Aufzug in jedem der drei Stockwerke halt? Beantworten Sie dieseFrage in den Fallen:

(a) k = 3,

(b) k = 4,

(c) fur ein beliebiges k ≥ 3.

Hier einige Losungsansatze:

• Alle drei Teile (a), (b) und (c) lassen sich direkt durch das Zahlen losen (manunterscheidet die k Personen und setzt dabei Ω = 1, 2, 3k, sodass durch ω ∈ Ωfur jede der k Personen 1, . . . , k notiert wird, welche der 3 Knopfe diese Persongedruckt hat).


• Es gab auch einen Vorschlag aus dem Publikum, Teil (a) auf die folgende Wei-se zu losen. Sei A die Wahrscheinlichkeit, dass Person 2 einen anderen Knopfals Person 1 druckt, und B die Wahrscheinlichkeit, dass Person 3 eine Knopfdruckt, der nicht von den anderen beiden Personen gedruckt wurde. Uns in-teressiert somit die Wahrscheinlichkeit von AB. Wir konnen nun die FormelP (AB) = P (A)P (B|A) verwenden, die sich direkt aus der Definition der be-dingten Wahrscheinlichkeit ergibt, um P (AB) zu berechnen. Die Wahrschein-lichkeit von A ist 2

3und die Wahrscheinlichkeit von B unter der Bedingung A

ist 13. Somit ist P (AB) = 2

3· 1

3= 2

9.

• Auch den Teil (b) kann mit Hilfe von Theorem 1.13 losen, indem man innerhalbvon einzelnen Fallen noch Unterfalle betrachtet (denn man kann Theorem 1.13‘rekursiv’ benutzen, indem man innerhalb einer Bedingung Ai noch verschiedeneUnterbedingungen einfuhrt und wieder die Formel von Bayes benutzt).

1.17 Bsp. Berechne die Wahrscheinlichkeit, dass ein zufalliges Wort der Lange 4des Alphabets a, . . . , z aus 26 Buchstaben mit einem Vokal a, e, o, u anfangt oder miteinem Vokal endet.

1.18 Bsp. Wie hoch ist die Wahrscheinlichkeit beim Lotto 6 aus 49 zu gewinnen?

1.19 Def (Unabhangigkeit fur zwei Ereignisse). EreignisseA undB mit P (AB) =P (A)P (B) heißen unabhangig.

1.20. A und B mit P (B) > 0 sind genau dann unabhangig, wenn P (A|B) = P (A)gilt. D.h., die Wahrscheinlichkeit von A andert ist unabhangig davon, ob B antritt.

1.21 Def (Unabhangigkeit eines Systems von Ereignissen). Allgemeiner heißt einSystem von n Ereignissen A1, . . . , An unabhangig, wenn

P (⋂i∈I

Ai) =∏i∈I

P (Ai)

fur jede Teilmenge I von 1, . . . , n erfullt ist. Z.B. sind drei Ereignisse A,B,Cunabhangig, wenn P (AB) = P (A)P (B), P (AC) = P (A)P (C), P (BC) = P (B)P (C)und P (ABC) = P (A)P (B)P (C) gilt.

1.22 Def (Begriffe fur Zufallsvariablen). In der Stochastik betrachtet man nichtnur Ereignisse sondern auch ‘zufallige Werte’, die man in der Fachsprache derStochastik Zufallsvariablen nennt.

(a) Fur endliche Wahrscheinlichkeitsraume, ist eine Zufallsvariable eine Funk-tion

X : Ω→ R.


(b) Fur x ∈ R, sei

P (X = x) := P (ω ∈ Ω : X(w) = x

die Wahrscheinlichkeit, dass X den Wert x ∈ R annimmt. Die Abbildung

PX(x) := P (X = x)

auf der Menge aller x ∈ R mit P (X = x) > 0 in die Menge [0, 1] heißt dieVerteilung von X.

(c) Die Menge aller x ∈ R mit P (X = x) > 0 heißt die Menge der Reali-sierungen von X. Die Realisierungen sind die Werte von X, die mit einerpositiven Wahrscheinlichkeit antreten. Als R(X) bezeichnen wir die Mengeder Realisierungen von X.

(d) Fur x ∈ R ist

P (X ≤ x) := P (ω ∈ Ω : X(w) ≤ x ,

dass der Wert x nicht uberschritten wird. Die Funktion

FX(x) := P (X ≤ x)

von R nach R heißt die Verteilungsfunktion von X.

1.23 Bsp. Hier Beispiel einer Zufallsvariablen mit endlicher Anzahl von Realisierun-gen.

(a) Irgendeine Verteilung:

1 2 4Realisierungen

1/5

3/10

1/2

Wah

rsch

einl

ichke

iten


1 2 4Realisierungen

0

1

Wah

rsch

einl

ichke

iten

(b) X aus dem Munzwurf mit X = 0 bei Kopf und X = 1 bei Zahl.

0 1Realisierungen

1/21/2

Wah

rsch

einl

ichke

iten

0 1Realisierungen

0

1

Wah

rsch

einl

ichke

iten

(c) Augenzahl beim Wurfeln:


1 2 3 4 5 6Realisierungen

1/61/61/61/61/61/6

Wah

rsch

einl

ichke

iten

1 2 3 4 5 6Realisierungen

0

1

Wah

rsch

einl

ichke

iten

1.24. Die Verteilungsfunktion FX und die Verteilung PX enthalten die gleiche Infor-mation. Die Verteilungsfunktion FX ist aus verschiedenen Grunden bequemer als dieVerteilung.

(a) Mit Hilfe von FX lasst sich die Wahrscheinlichkeit von P (a < X ≤ b) direktausrechnen, denn

P (a < X ≤ b) = FX(b)− FX(a)

fur alle a, b ∈ R mit a ≤ b. Die Fragen nach der Wahrscheinlichket von X ≤ b,X > a oder a < X ≤ b stellt man immer wieder in verschiedensten Kontextenin der Praxis.

2. STOCHASTIK IM ALLGEMEINEN FALL 13

(b) Wenn man die Verteilungen von zwei Zufallsvaraiblen X und Y vergleichen will,so sollte man in der Regel lieber vergleichen, wie unterschiedlich FX und FYsind. Sind FX und FY nah zueinander, so heißt es, dass die Variablen X und Y“ahnlich verteilt” sind.

1.25 Bsp. Sei Xi die Augenzahl beim i-ten Wurfelwurf. Wir konnen die Verteilungund die Verteilungsfunktion von X = maxX1, X2 ausrechnen. Die moglichen Reali-sierungen von X sind die Werte 1 bis 6. Die Wahrscheinlichkeiten dieser Werte konnendurch die Formel

PX(x) = P (X = x) =2x− 1

36.

beschrieben werden. Der Ereignisraum fur zwei Wurfe ist (Ω, P ) mit Ω = 1, . . . , 62

und P (ω) = 136

. Vgl. das folgende Bild, in dem die Ereignisse X = x fur jedesmogliche x ∈ 1, . . . , 6 farblich hinterlegt sind.

1

1

2

2

3

3

4

4

5

5

6

6

Erster Wurf

Zweiter Wurf

2 Stochastik im allgemeinen Fall

2.1 Bsp. Wenn man Situationen modellieren mochte, in denen man unendlich vieleElementarereignisse hat bzw. Zufallsvariablen mit unendlich vielen Realisierungen,braucht man allgemeine Wahrscheinlichkeitsraume. Bevor wir eine genaue Definitiongeben, betrachten wir einige Beispiele:

(a) Man kann zum Beispiel einen zufalligen gleichmaßig verteilten Punkt aus demSegment [0, 1] betrachten. Die Menge der Realisierung ist das gesamte Segment[0, 1] – eine nicht-abzahlbare Menge. So einen Punkt kann man ubrigens durcheine unendliche Folge der Munzwurfe modellieren. Sei Xi = 1, wenn man beimi-ten Munzwurf eine Zahl hat und Xi = 0 sonst. Dann ist

P :=∞∑i=1

Xi

2i

ein in [0, 1] gleichmaßig verteilter zufalliger Punkt. Die Wahrscheinlichkeit desEreignis a ≤ X ≤ b fur 0 ≤ a ≤ b ≤ 1 ist b− a.

(b) Man kann auch einen zufalligen gleichmaßig verteilten Punkt P = (P1, P2)im Quadrat [0, 1]2 betrachten. Die Wahrscheinlichkeit von P ∈ M fur eineTeilmenge M ⊆ [0, 1]2 ist der Flacheninhalt von M .


(c) Bei einem gleichmaßig verteilten Punktk P = (P1, P2, P3) aus dem Einheitswurfel[0, 1]3 ist die Wahrscheinlichkeit von P ∈ M fur eine Teilmenge M von [0, 1]3

gleich dem Volumen von M .

TODO: Bild zu (a): Ein Baum aus Segmenten, die in in je zwei Halften zerlegtwerden. Ein ganzes Segment, zwei Halften, 4 Viertel usw.

2.2. Der technische Aspekt der Stochastik im allgemeinen Fall kann man im Rahmender Beispiele 2.1 illustrieren. Man weiß aus der Analysis:

(a) nicht jede Teilmenge von [0, 1] besitzt eine Lange.

(b) nicht jede Teilmenge von [0, 1]2 besitzt einen Flacheninhalt.

(c) nicht jede Teilmenge von [0, 1]3 besitzt ein Volumen.

Das klingt seltsam, ist aber ein bekannter mathematischer Fakt. Anderseits kummernsich die Anwender um solche subtile Aspekte gar nicht, da sie die ‘merkwurdigen’Mengen ohne Lange/Flacheninhalt/Volumen niemals in der Praxis sehen.

Hier noch eine etwas andere Moglichkeit die nachfolgenden Definitionen allgemei-ner Wahrscheinlichkeitsraume zu motivieren. Im Fall von endlichen Ereignisraumenwar Ω eine endliche Menge und jede Teilmenge von Ω war ein Ereignis. Fur allgemeineWahrscheinlichkeitsraume kann Ω unendlich sein. Wir wollen nicht die Definition soeinfuhren, dass alle Teilmengen laut der Definition Ereignisse sind. Bei unendlichen Ωsind viele Teilmengen von Ω fur niemanden interessant, sodass wir nun die Definitioneines Ereignis so einschranken wollen, dass die uninteressanten Teilmengen von Ωkeine Ereignisse sind. Andererseits muss die Familie der Ereignisse vollstandig genugsein, sodass man fur jedes Ereignis das Gegenereignis bilden kann und endliche sowieunendliche System von Ereignisse durch Durchschnitt und Vereinigung kombinierenkann. Diese Voruberlegungen fuhren nun zur folgenden Definition.

2.3 Def (Allgemeiner Wahrscheinlichkeitsraum). Sei Ω nichtleere Menge undP : U → R eine Funktion auf einer Menge U , deren Elemente Teilmengen von Ωsind.

(a) U heißt σ-Algebra, wenn

• die leere Menge und das gesamte Ω Elemente von U sind,

• fur jedes A aus U auch das Komplement A = Ω \A Element von U istund

• fur Folge von ElementenA1, A2, . . . aus U , liegen die Vereingung⋃∞i=1Ai

und der Durchschnitt⋂∞i=1 Ai ebenfalls in U .

(b) P : U → R heißt Wahrscheinlichkeitsmaß, wenn

• der Definitionsbereich eine U eine σ-Algebra ist,

• P (∅) = 0 und P (Ω) = 1 gilt,


• fur jede Folge A1, A2, . . . der Elemente aus U die Ungleichung

P (∞⋃i=1

Ai) ≤∞∑i=1

P (Ai) (I.1)

erfullt ist und

• fur jede Folge A1, A2, . . . mit Ai ∩ Aj = ∅ fur i 6= j die Gleichung

P (∞⋃i=1

Ai) =∞∑i=1

P (Ai) (I.2)

erfullt ist.

(c) Ist U σ-Algebra auf Ω und P : U → R Wahrscheinlichkeitsmaß, so nenntman das Paar (Ω, P ) ein Wahrscheinlichkeitsraum. Elemente von U heißenEreignisse und P (A), fur A ∈ U , heißt die Wahrscheinlichkeit von A.

2.4. Wenn man Ai = ∅ fur i > k, enthalt man den endlichen Fall

P (k⋃i=1

Ai) ≤k∑i=1

P (Ai)

von (I.1) sowie den endlichen Fall

P (k⋃i=1

Ai) =k∑i=1

P (Ai)

von (I.2). Fur die Wahrscheinlichkeitstheorie ist es aber wichtig, dass man auch mitFolgen von Ereignissen arbeiten kann und die entsprechenden allgemeineren Bedin-gungen wie (I.1) und (I.2) erfullt sind.

2.5 (Begrundung der Einschrankung auf eine σ-Algebra). Bei allgemeinen Wahr-scheinlichkeitsraumen will man nicht beliebige Teilmengen von Ω als Ereignisse dekla-rieren, sondern nur diejenigen, die interessant sein konnten. Daher fuhrt die σ-AlgebraU ein, die einerseits alle interessanten Ereignisse enthalt und andererseits vollstandiggenug ist, sodass man bei der Anwendung der Standardoperation wie Komplementeines Ereignis sowie Vereinigung und Durchschnitt einer Folge von Ereignissen nichtaus der Menge U ‘herausfallt’.

2.6. Wir bemerken Folgendes:

(a) Die Begriffe wie Bedingte Wahrscheinlichkeit und Unabhangigkeit von Ereig-nissen werden fur allgemeine Wahrscheinlichkeitsraume genauso eingefuhrt.

(b) Die oben prasentierten Formel fur Wahrscheinlichkeiten und bedingte Wahr-scheinlichkeiten gelten auch in dem Rahmen der allgemeinen Wahrscheinlich-keitsraume.


2.7. Nun wollen wir auch Zufallsvariablen in allgemeinen Wahrscheinlichkeitsraumeneinfuhren. Fur eine Zufallsvariable X mochte man oft P (X ∈ B) fur verschiede-ne Mengen B ⊆ R ausrechnen. Allerdings interessieren einen nicht alle Teilmen-gen von R. Man interessiert sich aber auf jeden Fall fur Intervalle wie [a, b], [a,∞)usw. Wir wollen also, dass die Teilmengen von R wie etwa a ≤ X ≤ b :=ω ∈ Ω : a ≤ X(ω) ≤ b Ereignisse sind. Da wir aber Gegenereignisse bilden konnensowie Folgen von Ereignissen durch Vereinigung und Durchschnitt verknupfen, so in-teressiert soll man P (X ∈ B) auch fur B’s definieren, die aus Intervallen durch Kom-plement bilden sowie Vereinigung und Durchschnitt abzahlbarer Folgen von Mengenentstehen. All diese Uberlegungen fuhren uns zur folgenden Definition einer Zufalls-variablen.

2.8 Def (Borel-Mengen und Zufallsvariablen). (a) Als B bezeichnen wir die in-klusionskleinste σ-Algebra, welche alle offenen Mengen enthalt. Insbesonde-re sind in B alle offene, abgeschlossene und halboffene Intervalle enthalten.Elemente von B heißen Borel-Mengen.

(b) Ist (Ω, P ) Wahrscheinlichkeitsraum mit Wahrscheinlichkeitsmaß P : U → Rauf einer σ-Algebra U und X : Ω→ R eine Funktion, so heißt X Zufallsva-riable, wenn fur jede Borel-Menge B, die Menge ω ∈ Ω : X(ω) ∈ B zurσ-Algebra U gehort.

2.9. Der Begriff einer Zufallsvariablen X ist oben so eingefuhrt, dass die Wahrschein-lichkeit

P (X ∈ B) = P (ω ∈ Ω : X(ω) ∈ B .

fur ‘sinnvolle’ Teilmengen von R (dass sind die Borel-Mengen) definiert ist. Insbe-sondere sind die Wahrscheinlichkeiten P (X ≥ a), P (X > a), P (X ≤ b), P (X < b),P (a ≤ X ≤ b), P (a < X < b) fur a, b ∈ R definiert.

2.10 Def (Verteilung). Sei X : Ω→ R Zufallsvariable.

(a) Ist die X(Ω) endlich oder abzahlbar, so nennt man X diskret.

(b) Ist X diskret, so nennt man die Menge R(X) aller x ∈ R mit P (X = x) > 0die Menge der Realisierungen von X und die Funktion PX : R(X)→ [0, 1]mit

PX(x) := P (X = x)

die Verteilung von X.

2.11 Bsp. (Ω, P ) beschreibt unendliche Folge der Munzwurfe (erster, zweiter, dritterusw.). Sei X die Nummer des Wurfes, bei dem die Zahl das erste mal antritt. Indiesem Fall ist X(Ω) ist die Menge aller positiven ganzen Zahlen. Die Menge X(Ω)ist unendlich aber abzahlbar. Sei

Ai := “Zahl im i-ten Wurf”


Dann erhalt man

PX(i) = P (X = i) = P (A1 · · ·Ai−1Ai)

= P (A1) · · ·P (Ai−1)P (Ai)

=1

2i.

mit der Berucksichtigung der Unabhangigkeit der Ereignisse A1, . . . , Ai−1, Ai. DieVerteilungsfunktion kann man mit Hilfe von PX(i) ausrechnen, aber auch auf diefolgende Weise: FX(i) = P (X ≤ i) = 1− P (X > i). Man hat

X > i = “In den ersten i Wurfen nur den Kopf geworfen”.

Das ergibt P (X > i) = 2i, woraus man

FX(i) = 1− 1

2i.

erhalt.

2.12 Def. Ist X eine Zufallsvariable, bei der die Verteilungsfunktion durch dieFormel

FX(x) = P (X ≤ x) =

∫ x

−∞w(t)dt

mit Hilfe einer integrierbaren Funktion w : R→ R+ beschrieben werden kann, soheißt X stetig. Die Funktion w heißt Dichte von X.

2.13. Die Intuition hinter der Dichte ist, dass die Wahrschenlichkeit von P (X ∈ ∆x)fur ein kleines Intervall ∆x mit der Lange |∆x|, welches x enthalt ungefahr w(x)|∆|ist:

P (X ∈ ∆x) ≈ w(x)|∆x|.Oder, wenn man formal mit unendlich kleinen Langenelementen d arbeitet:

P (X ∈ dx) = w(x)|dx|.

Rein formal kann man daraus nun Formel wie

P (X ∈ B) =

∫B

w(x)dx

herleiten.

2.14. Fur stetige Zufallsvariablen X ist die Wahrscheinlichkeit von X = a fur jedesa ∈ R gleich 0. Daher sind die Wahrscheinlichkeiten von X ≥ a und X > a gleich(sowie die Wahrscheinlichkeiten von X ≤ b und X < b).

2.15. Fur eine stetige Variable mit Dichte w gilt:

(a) Ist FX in an einer Stelle x ∈ R differenzierbar, so gilt F ′X(x) = w(x).

(b) P (a ≤ X ≤ b) = FX(b)− Fx(a) =∫ baw(x)dx fur alle −∞ ≤ a ≤ b ≤ ∞.


2.16 Def. Ein System endlich vieler ZufallsvariablenX1, . . . , Xn heißt unabhangig,wenn fur alle Borel-Mengen B1, . . . , Bn die Gleichung

P((X1 ∈ B1) · · · (Xn ∈ Bn)

)=

n∏i=1

P (Xi ∈ Bi)

erfullt ist.

2.17. Wenn wir zu einem System X1, . . . , Xn unabhangiger Zufallsvariablen Funktio-nen f1, . . . , fn anwenden, so erhalten wir ein System der Variablen f1(X1), . . . , fn(Xn),das ebenfalls unabhangig ist.

2.18 Def. Seien a, b ∈ R und a < b. Eine Zufallsvariable X mit Dichte

w(x) :=

0, x 6∈ [a, b]

1b−a , x ∈ [a, b]

heißt stetig gleichverteilt in [a, b].

2.19. Wenn wir die Werte der Dichte w einer Zufallsvariablen X an endlich vielenStellen andern, so bleibt w nach dieser Anderung Dichte von X, da diese Anderungvon w die Integrale

∫Bw(x)dx nicht beeinflusst. Wir konnten zum Beispiel in 2.18,

die Dichte durch

w(x) :=

0, x 6∈ (a, b)

1b−a , x ∈ (a, b)

definieren. In Bezug auf die Fragestellungen aus der Wahrscheinlichkeitstheorie, gabees dann keinen Unterschied.

2.20 Bsp. Seien X1, X2 zwei unabhangige Zufallsvariablen, die im Segment [0, 1]gleichverteilt sind. Wir berechnen nun die Dichte w von X = maxX1, X2. Es gilt

FX(x) := P (X ≤ x)

= P ((X1 ≤ x)(X2 ≤ x)) (wegen Unabhangigkeit)

= P (X1 ≤ x)P (X2 ≤ x)

mit der Berucksichtigung von Unabhangigkeit von X1 und X2 (vgl. 2.16). Da X1

sowie X2 in [0, 1] gleichverteilt sind, gilt P (X1 ≤ x) = P (X2 ≤ x). Wir erhalten also

FX(x) = P (X1 ≤ x)2.

Es gilt P (X1 ≤ x) = 0 fur x ≤ 0 und P (X ≤ x) = 1 fur x ≥ 1. Fur 0 < t < 1 giltP (X ≤ x) = x und wir erhalten somit FX(x) = x2. Durch Differenzieren (vgl. 2.15(a))ermitteln wir nun die Dichte w von X:

w(x) :=

0, x ≤ 0,

2x, 0 < x < 1,

0, x ≥ 1.

3. PARAMETER STOCHASTISCHER VERTEILUNGEN 19

2.21 Bsp. Claus aus dem Paketdienst kommt bei Amelie und Ben vorbei, um einPaket zu liefern. Seine Ankunfstzeit ZC ist eine gleichverteilte Zufallsvariable in [0, 1](z.B., 0 steht fur 15 Uhr, und 1 steht fur 16 Uhr). Amelie und Ben kommen ebenfallsim Zeitraum [0, 1] nach Hause, und ihre Ankunftseitzen ZA und ZB sind ebenfallsgleichverteilt in [0, 1]. Die Ankunfszeiten von Amelie, Ben und Claus sind unabhangigvoneinander. Das Paket wird geliefert, wenn bei der Ankunft von Claus Amilie oderBen zu Hause ist. Wie wahrscheinlich ist es, dass das Paket geliefert wird?

2.22 (Sicher vs. fast sicher). Spatestens wenn man zu allgemeinen Wahrscheinlich-keitsraumen ubergeht, sieht man, dass man zwischen den sicheren und fast sicherenEreignissen unterscheiden muss. Bei einer unendlichen Folge von Munzwurfen, diewir durch den Raum Ω = 0, 1∞ modellieren, ist es sicher, dass man beim erstenWurf Kopf oder Zahl bekommt. Denn tatsachlich ist bei jedem ω ∈ Ω die erste Kom-ponente von ω entweder die 0 oder die 1. Im Gegenteil dazu, ist das Ereignis A, dassman bei einer unendlichen Folge von Munzwurfen mindestens ein Mal Zahl wirft, fastsicher. Denn ω = (0, 0, 0, 0, . . .) ist Element von Ω, das nicht zu A gehort, sodass manA 6= Ω hat. Andererseits ist die Wahrscheinlichkeit von ω = (0, 0, 0, 0, . . .) gleich 0,sodass die Wahrscheinlichkeit von A gleich 1 ist. Diese Uberlegungen motivieren diefolgenden Definition.

2.23 Def. Ein Ereignis A heißt

(a) fast sicher, wenn P (A) = 1 gilt.

(b) fast unmoglich, wenn P (A) = 0 gilt.

Naturlich ist das sichere Ereignis Ω auch fast sicher, und das unmogliche Ereignis∅ auch fast unmoglich. Im Allgemeinen kann ein Wahrscheinlichkeitsraum (Ω, P )auch weitere fast sichere und fast unmogliche Ereignisse besitzen.

3 Parameter stochastischer Verteilungen

3.1 Def (Erwartungswert). Sei X Zufallsvariable. Der Erwartungswert E(X) vonX ist als

E(X) =

∫Ω

X(ω)P (dω). (I.3)

definiert. E(X) wird also als das Integral von X bzgl. des Warhscheinlichkeits-maßes P uber den Ereignisraum Ω eingefuhrt. Im Fall einer endlichen Zufallsva-riablen X mit einer endlichen Menge R(X) von Realisierungen wird die rechteSeite als die Summe

E(X) =∑

x∈R(X)

xP (X = x)

definiert. Fur allgemeine X wird die rechte Seite von (I.3) durch eine Art Grenz-wertubergang mit Hilfe der Approximation von X durch die Zufallsvariablen


mit endlich vielen Realisierungen eingefuhrt. Die mathematischen Details dazuhangen mit der Maßtheorie zusammen (vgl. z.B. [Rud76, Ch. 11]). Diese Detailssind relativ technisch werden daher weggelassen.

3.2 (Wahrscheinlichkeitsmaße mit einer Dichte). Wir haben zwar hier der rechtenSeite von (I.3) keine genauere Bedeutung gegeben, (I.3) ist aber trotzdem zur ‘Ori-entierung’ nutzlich, weil die fur uns wichtigen Spezialfalle davon der Formel (I.3)ziemlich ahnlich aussehen. Man kann z.B. die Situation betrachten, in der Ω Teilmen-ge von Rn ist, die ein positives Volumen besitzt und das Wahrscheinlichkeitmaß Pdurch das Integral

P (A) :=

∫A

wP (ω)dω

definiert ist bzgl. einer Funktion wP : Ω → R mit wP (ω) ≥ 0 fur alle ω ∈ Ω und∫ΩwP (ω)dω = 1. Die Funktion wP heißt Dichte des Wahrscheinlichkeitsmaßes P . In

diesem Fall kann (I.3) als

E(X) =

∫Ω

X(ω)wP (ω)dω

umformuliert werden.

3.3 Bsp. Betrachten wir die Kreisscheibe Ω := (x, y) ∈ R2 : x2 + y2 ≤ 1. Der Zu-fallsexperiment ist die Wahl eines zufalligen gleichverteilten Punktes in ω ∈ Ω. Ωhat den Flacheninhalt π. Somit ist unser P durch die Dichte wP (x, y) = 1

πgegeben.

Betrachten wir die Zufallsvariable

D := “Etnfernung des gleichverteilten Punktes in Ω vom Zentrum der Kreisscheibe Ω”

Fur das Elementarereignis ω = (x, y) gilt D =√x2 + y2. Somit ist

E(D) :=

∫Ω

√x2 + y2︸︷︷︸

Wert der Z.V.

1

π︸︷︷︸Dichte von P

dxdy︸︷︷︸dω

=1

π

∫Ω

√x2 + y2dxdy.

Das Integral kann durch den Ubergang zu Polarkoordinaten ausgerechnet werden.

3.4. Im Fall von endlichen Wahrscheinlichkeitsraumen (Ω, P ) gilt

E(X) =∑ω∈Ω

X(ω)P (ω).

3.5 Thm (Formel zur Berechnung des Erwartungswerts). Sei X Zufallsvariable

(a) Ist X diskret mit der Menge der Realisierungen R(X), so gilt

E(X) :=∑

x∈R(X)

xP (X = x)


(b) Ist X stetig mit Dichte w, so gilt

E(X) :=

∫ ∞−∞

xw(x)dx

3.6. Die Formel fur den diskreten und stetigen Fall sind analog. Im diskreten Fallbenutzt man die Summe und die Verteilung, im stetigen Fall – das Integral und dieDichte.

3.7. Der Erwartungswert kann auch +∞ oder −∞ sein. Um die Diskussion etwaszu vereinfachen wird in den nachfolgenden Formeln implizit vorausgesetzt, dass allezugrundeliegenden Erwartungswerte existieren und endliche Werte sind.

3.8 Bsp. Wir betrachten die ZufallsvariableX aus 2.11: die Nummer des Munzwurfes,bei dem die Zahl das erste Mal antritt. Wir wissen bereits, dass die Menge R(X) derRealisierungen von X aus allen positiven ganzen Zahlen besteht und P (X = i) = 2−i

erfullt ist. Wir ermitteln nun den Erwartungswert E(X). Nach 3.5(a) gilt

E(X) =∞∑i=1

i2−i

Hier zwei Losungsmoglichkeiten

1. Wir ermitteln nun den Wert auf der rechten Seite auf die folgende Weise

n∑i=1

i2−i =1

2+

1

4+

1

4+

1

8+

1

8+

1

8+

· · ·

Nun fuhren wir die unendliche Summe S = 12

+ 14

+ 18

+ · · · ein. Es ist bekannt,dass S = 1 gilt. Wir erhalten somit

n∑i=1

i2−i =S +1

2S +

1

4S + · · ·

=(1 +1

2+

1

4+ · · · )S

=(1 + S)S

=2.

2. Betrachten wir eine andere Zufallsvariable Y : die Nummer des Munzwurfes, beidem die Zahl das zweite Mal antritt. Wie hoch ist die Wahrscheinlichkeit vonY = i. Fur Y = i muss man im i-ten Wurf die Zahl haben und in den i − 1vorigen Wurfen genau ein mal die Zahl. Unter den 2i moglichen Ausgangender ersten i Wurfe gilt bei genau i − 1 Ausgangen Y = i. Also erhalt man


P (Y = i) = (i− 1)2−i. Da man mit Wahrscheinlichkeit 1 einen der Falle Y = imit i ≥ 1 erhalt, gilt

1 =∞∑i=1

(i− 1)2−i =∞∑i=2

(i− 1)2−i.

Die Summe auf der rechten Seite sieht der Summe in der Formel fur E(X)ziemlich ahnlich. Wir ersetzen i durch j + 1 und erhalten

1 =∞∑j=1

j2−(j+1) =1

2

∞∑j=1

j2−j.

Das zeigt, dass die Summe in der Formel fur E(X) gleich 2 ist.

3.9 Bsp. Wir berechnen den Erwartungswert der Exponentialverteilung mit derDichte

w(x) =

λe−λx x ≥ 0,

0 x < 0

fur λ > 0. Mit Hilfe von 3.5(b) erhalten wir

E(X) =

∫ ∞0

xλe−λxdx (wir wollen partiell Integrieren)

=

∫ ∞0

xd(−e−λx) (Stammfunktin von λe−λx wurde ermittelt)

= x(−e−λx)∣∣∞x=0−∫ ∞

0

(−e−λx)dx (Partielle Integrierung)

=

∫ ∞0

e−λxdx (Vereinfachung)

= −1

λe−λx

∣∣∣∣∞x=0

=1

λ.

3.10 (Zur Existenz von E(X)). Die Summen bzw. Integrale in 3.5 mussen nichtexistieren. Stellen sie sich das folgende Spiel vor. Sie werfen eine faire Munze solange,bis Sie eine Zahl werfen. Sei X die Nummer des Wurfes, in dem Sie das erste mal dieZahl geworfen haben. Die Spielregel sind so: ist X ungerade, so haben Sie 2X Euroverloren, ist X gerade so haben Sie 2X Euro gewonnen. Ist nun das Spiel profitabelfur Sie oder eher nicht? Ihr Gewinn betragt Y = (−2)X Euro (wobei wir den Verlustals Gewinn mit dem negativen Vorzeichen darstellen). Die Wahrscheinlichkeit vonX = i ist 1

2i, wie bereits besprochen wurde. Somit ergibt sich fur den Erwartungswert

von Y die Formel

E(Y ) =∞∑i=1

(−2)i1

2i=∞∑i=1

(−1)i.

Es ist eine divergente Reihe: E(Y ) ist also undefiniert.

3.11. Die Verteilung einer Zufallsvariablen ist die Verteilung eines Einheitsmaßes aufder reellen Achse. Der Erwartungswert ist der Schwerpunkt dieser Verteilung.


3.12 (Einsetzen von Zufallsvariablen in Funktionen). Wenn man eine ZufallsvariableY als Funktion Y = f(X) einer anderen Zufallsvariablen X einfuhrt (d.h., in eineFunktion f : R → R wird X eingesetzt), so kann man den Erwartungswert von Yfolgendermaßen berechnen:

(a) Ist X diskret mit der Menge der Realisierungen R(X), so gilt

E(f(X)) =∑

x∈R(X)

f(x)P (X = x)

(b) Ist X stetig mit Dichte w, so gilt

E(f(X)) =

∫ ∞−∞

f(x)w(x)dx.

Wenn man etwa f(x) = xk benutzt, so erhalt man Formel fur sogenannte Momente

E(X), E(X2), E(X3), . . .

einer Zufallsvariablen X. Wenn man f(x) = ax + b mit a, b ∈ R benutzt, so siehtman, dass

E(aX + b) = aE(X) + b

gilt.

3.13. Fur endlich viele Zufallsvariablen X1, . . . , Xn gilt:

(a) E ist ein lineares Funktional. das heißt:

E(n∑i=1

αiXi) =n∑i=1

αiE(Xi)

gilt fur alle α1, . . . , αn ∈ R. Wenn also eine Zufallsvariable als Summe andererZufallsvariablen darstellbar ist, so kann man eine solche Darstellung oft zurVereinfachung der Berechnung des Erwartungswerts benutzen (wir sehen imFolgenden Beispiele dazu).

(b) Bilden X1, . . . , Xn ein unabhangiges System, so gilt

E(n∏i=1

Xi) =n∏i=1

E(Xi).

Hier sei darauf hingewiesen, dass diese Produktformel nur fur unabhangige Zu-fallsvariablen gilt.

3.14 Def. Ist X Zufallsvariable, so heißt

V (X) := E((X − E(X))2)

die Varianz von X. Mit Worten: Die Varianz ist der Erwartungswert des qua-drierten Abstandes von X und E(X). Der Wert√

V (X)


heißt die Standardabweichung von X.

3.15. Ist V (X) = 0 so gilt X = E(X) mit Wahrscheinlichkeit 1. In der Fachspracheder Wahrscheinlichkeit Theorie sagt man: X ist fast sicher gleich E(X). Je kleinerV (X) ist, desto ‘enger’ ist de Beziehung zwischen X und E(X) (eine genauere Be-grundung kommt in 3.26(b)).

3.16. Aus der Linearitat von X folgt

V (aX + b) = a2V (X).

fur a, b ∈ R. Insbesondere andert sich die Varianz von X nicht, wenn man X ‘ver-schiebt’ (d.h., X durch X + b fur ein b ∈ R ersetzt).

3.17. Die folgenden Formel konnen zur Berechnung der Varianz verwendet werden:

(a) Ist V (X) endlich, so gilt

V (X) = E(X2)− E(X)2.

Die Varianz erhalt man also aus den ersten zwei Momenten E(X1) und E(X2)von X. Die Formel erhalt man durch das Ausmultiplizieren von (X − E(X))2

und die anschließende Anwendung der Linearitat von X.

(b) Ist X diskret mit der Menge der Realisierungen R(X), so gilt

V (X) =∑

x∈R(X)

(x− E(X))2P (X = x)

Diese Formel erhalt man direkt aus der Bemerkung 3.12 uber das Einsetzen derZufallvariablen in Funktionen. Die Varianz ist der Erwartungswert der Variablen(X−E(X))2 die durch das Einsetzen von X in die Funktion f(x) = (x−E(X))2

entsteht.

Alternativ kann man auch die Formel

V (X) =

∑x∈R(X)

x2P (X = x)

︸︷︷︸

=E(X2)

−E(X)2

benutzen.

Diese Formel ergibt sich direkt aus (a) und der Anwendung der Bemerkung 3.12im Fall f(x) = x2.

(c) Ist X stetig mit Dichte w, so gilt

V (X) =

∫ ∞−∞

(x− E(X))2w(x)dx

=

(∫ ∞−∞

x2w(x)dx

)︸︷︷︸

=E(X2)

−E(X)2.


3.18. Bilden Zufallsvariablen X1, . . . , Xn ein unabhangiges System, so gilt

V (X1 + · · ·+Xn) = V (X1) + · · ·+ V (Xn)

3.19 Bsp. Sei Xi = 1 bei Zahl im i-ten Munzwurf und Xi = 0 sonst. Dann istX = X1+· · ·+Xn die Anzahl der gewofenen Zahlen bei n Munzwurfen. Wir berechnenE(X) und V (X). Da

E(Xi) =1

2.

fur alle i gilt, erhalt man aus der Linearitat des Erwartungswerts

E(X) =n

2.

Die Varianz von Xi kann direkt ausgerechnet werden:

V (Xi) = (0− E(Xi))2P (Xi = 0) + (1− E(Xi))

2P (Xi = 1) =1

4.

Da X1, . . . , Xn ein unabhangiges System bilden, kann (3.18) angewendet werden,sodass man

V (X) =n

4

erhalt. (Das war die Berechnung fur eine faire Munze. Fur allgemeine Munze mitWahrscheinlichkeit der Zahl gleich p ∈ [0, 1] sind die Berechnungen ziemlich analog.Je weiter p vom Wert 1

2entfernt ist, desto kleiner ist die Varianz. Mehr dazu im

nachsten Abschnitt).

3.20 (Abhangigkeit von Zufallvaraiblen). In der Praxis benotigt man oft ein Maßder Abhangigkeit von zwei Zufallsvariablen. Wenn zwei Zufallsvariablen X und Yabhangig sind, so mochte man die Abhangigkeit von X und Y durch einen Parameterbestatigen, und mit Hilfe dieses Parameters auch den Grad der Abhangigkeit quan-tifizieren. Bei der Kovarianz und der Korrelation, die wir unten einfuhren, geht esum Wert die bei der Beantwortung der folgenden Frage unterstutzen: inwieweit kannman die Zufallsvariable aX+b mit einer geeigneten Wahl von a, b ∈ R als Voraussagefur eine Zufallsvariable Y benutzen?

3.21 Def. Seien X, Y Zufallsvariablen.

(a) Der WertCov(X, Y ) = E((X − E(X))(Y − E(Y ))

die Kovarianz von X und Y .

(b) Im Fall V (X), V (Y ) > 0 heißt der Wert

Cor(X, Y ) =Cov(X, Y )√V (X)

√V (Y )

die Korrelation von X und Y .


3.22. Hier einige Eigenschaften der Kovarianz und Korrelation:

(a) −1 ≤ Cor(X, Y ) ≤ 1.

(b) Cov(X,±X) = ±V (X) und Cor(X,±X) = ±1

(c) Fur alle a, b, c, d ∈ R gilt

Cov(aX + b, cY + d) = acCov(X, Y )

Insbesondere andert die ‘Verschiebung’ von X und Y die Kovarianz nicht, d.h.,Cov(X + b, Y + d) = Cov(X + b, Y + d).

(d) Fur alle a, b ∈ R \ 0 und alle c, d ∈ R gilt

Cor(aX + b, cY + d) = sign(ab) Cor(X, Y ).

(e) Ist Y = aX + b mit a ∈ R \ 0 und b ∈ R so ist Cor(X, Y ) = sign a.

3.23. Je naher |Cor(X, Y )| zu 1 ist, desto besser kann man Ausdrucke vom TypaX + b mit a, b ∈ R zum Voraussagen von Y benutzen. Mehr dazu in Kapitel II.

3.24. Hier einige Formel und Beobachtungen fur Varianz und Kovarianz:

(a) Die FormelCov(X, Y ) = E(XY )− E(X)E(Y ).

erhalt man aus 3.21(a) durch das Ausmultiplizieren.

(b) Die FormelV (X + Y ) = V (X) + 2 Cov(X, Y ) + V (Y )

kann man folgendermaßen erhalten. Die Varianz und die Kovarianz sind inva-riant bzgl. Verschiebungen. Es reicht also die Formel im Fall E(X) = 0 undE(Y ) = 0 herzuleiten (da man X durch X − E(X) und Y durch Y − E(Y )ersetzen kann). In diesem Fall ergibt sich die Formel direkt aus den Definitionender Varianz und der Kovarianz.

(c) Sind X und Y unabhangig, so gilt

Cov(X, Y ) = 0

Die Umkehrung gilt im Allgemeinen nicht.

3.25 Bsp (Unteschied von unkorreliert und unabhangig). Hier ein Beispiel vonabhangigen aber unkorrelierten Variablen. Wir haben X1, X2 mit Xi = 1 bei Zahlim i-ten Munzwurf und Xi = 0 sonst und betrachten X = X1 und Y = X1(2X2− 1).Eine Intuition dazu, warum man X1(2X2− 1) mit X1 schlecht durch einen Ausdruckder Form aX1+b mit a, b ∈ R voraussagen kann, ist die folgende. X1(2X2−1) ist ±X1,mit einem Vorzeichen, das zufallig und unabhangig von X1 durch einen Munzwurffestgelegt wird. X1 kann nicht ‘wissen’, wie das Vorzeichen ausfallt. Ist X1 = 0, sospielt das Vorzeichen keine Rolle, und man hat X1 = X1(2X2 − 1). Ist X1 = 1, so istdas Vorzeichen entscheidend, sodass die Kenntnis davon, dass X1 = 1 nicht wirklichweiterhilft.


(a) Um Cov(X, Y ) zu berechnen, berechnen wir zuerst E(X) und E(Y ). Man hatE(X) = 1

2. Da X1 und X2 unabhangig sind, sind auch X1 und 2X2 − 1 un-

abhangig, sodass man wegen 3.13(b) auf den Wert

E(Y ) = E(X1)E(2X2 − 1) = E(X1) (2E(X2)− 1)︸︷︷︸=0

= 0

kommt. Nun konnen wir die Kovarianz von X und Y berechnen:

Cov(X, Y ) = E((X − 1

2)(Y − 0)) = E((X1 −

1

2)X1(2X2 − 1))

Da X1 und X2 unabhangig sind sind (X1− 12)X1 und 2X2− 1 unabhangig. Wir

konnen also 3.13(b) wieder anwenden und erhalten

Cov(X, Y ) = E((X1 −1

2)X1)E(2X2 − 1)︸︷︷︸

=0

= 0.

Das heißt, die Zufallsvariablen X und Y sind unkorreliert.

(b) Wir zeigen nun, dass die Variablen X und Y abhangig sind.

P ((X = 0)(Y = 1)) = P ((X1 = 0)(X1(2X2 − 1) = 1)) = 0,

denn, wenn X1 = 0 ist, ist X1(2X2 − 1) ebenfalls 0. Anderseits haben wirP (X = 0) > 0 und P (Y = 1) > 0. Das heißt

P ((X = 0)(Y = 1)) 6= P (X = 0)P (Y = 1).

3.26 Thm. Ist X Zufallsvariable und c > 0 so gilt

(a) P (|X| ≥ c) ≤ E(|X|)c

. (Ungleichung von Markov)

(b) P (|X − E(X)| ≥ c) ≤ V (X)c2

. (Ungleichung von Tschebyscheff)

3.27 Bsp. Die Ungleichung von Markov wird in der Regel im Fall von nichtnegativenZufallsvariablen verwendet (Zufallsvariablen, bei denen X ≥ 0 mit Wahrscheinlichkeit1 gilt).

(a) Z.B., sei X zufallige Sprungweite eines Sportlers. Wenn E(X) = 4 ist, so konnenwir P (X ≥ 8) mit Hilfe von 3.26(a) abschatzen. Da X nichnegativ ist, konnendie Betrage in 3.26(a) weggelasen werden

P (X ≥ 8) ≤ 4

8=

1

2.

Man sieht, dass die Wahrscheinlichkeit hochstens 50% ist. So eine Abschatzungmag ziemlich schwach zu erscheinen. Tatsachlich ist die oben prasentierte Abschatzungaus der Ungleichung von Markov die beste Abschatzung, die man erhaltenkann, wenn man uber die Verteilung von X nichts außer den Erwartungswertkennt. Wenn wir etwa die Dichte w von X kennen wurden, dann wurden wirwahrscheinlich die Formel P (X ≥ 8) =

∫∞8w(x)dx benutzen, um den Wert

P (X ≥ 8) exakt zu ermitteln.


(b) Wenn wir etwa wissen, dass die Sprungweite X eines Sportlers den Erwartungs-wert E(X) = 4 hat, und dass X ≥ 3 immer erfullt ist, so konnen wir P (X ≥ 8)besser abschatzen:

P (X ≥ 8) = P (X − 3 ≥ 5)

≤ E(X − 3)

5nach der Ungleichung von Markov

=E(X)− 3

5

=1

5.

Somit ist die Wahrscheinlichkeit hochstens 20%.

3.28. Die Ungleichung von Tschebyscheff ist eine direkte Folgerung aus der Un-gleichung von Markov. Die Ungleichung |X − E(X)| ≥ c kann ohne Betrage als(X − E(X))2 ≥ c2 umformuliert werden. Nun kann die Ungleichung von Markov furdie Variable (X − E(X))2 und die Schranke c2 angewendet werden, woraus sich dieUngleichung von Tschebyscheff ergibt.

3.29 Bsp. Sei X die Anzahl der geworfenen Zahlen bei 100 Munzwurfen. Wie wirbereits gesehen haben, gilt E(X) = 50 und V (X) = 25, vgl. 3.19.

Schatzenr wir die Wahrscheinlichkeit, dass die Anzahl der geworfenen Zahlen zwi-schen 40 und 60 liegt nach unten ab. Es gilt

P (40 ≤ X ≤ 60) = 1− P (|X − E(X)| ≥ 11).

Nach der Ungleichung von Tschebyscheff gilt

P (|X − E(X)| ≥ 11) ≤ 25

121.

Somit ist

P (40 ≤ X ≤ 60) ≥ 1− 25

121=

96

121= 0,7933 . . .

Die Wahrscheinlichkeit, dass X zwischen 40 und 60 liegt, ist also mindestens 79%.Wenn wir diese Wahrscheinlichkeit genauer abschatzen oder vielleicht sogar exakt be-rechnen mussten, so mussten wir mehr Information uber die Verteilung von X benut-zen. Aus der Ungleichung von Tschebyschev erhalt man zwar nur eine Abschatzung,man braucht dafur aber die Verteilung nicht exakt zu wissen, es reicht lediglich dieAngabe des Erwartungwertes und der Varianz.

4 Der Zoo stochastischer Verteilungen

4.1 Def. Zufallsvariablen X1, . . . , Xn heißen iid (engl. independent, identicallydistributed, de. unabhangig identisch verteilt), wenn sie ein unabhangiges Systembilden und ihre Verteilungsfunktionen gleich sind (d.h., FX1 = FX2 = · · · = FXn).Unendlich viele Zufallsvariablen X1, X2, X3, . . . heißen iid, wenn jedes endlichUntersystem dieser Variablen iid ist.

4. DER ZOO STOCHASTISCHER VERTEILUNGEN 29

4.2. Systeme von iid Variablen entsprechen der n-fachen unabhangigen Wiederho-lung eines Zufallsexperiments und der Beobachtung des Wertes einer Zufallsvariablenwahrend dieser n Experimente. Man kann etwa einen Munzwurf betrachten und eineZufallsvariable X mit X = 1 bei Zahl und X = 0 bei Kopf. Das n-faches Munzwurfergibt n iid Variablen X1, . . . , Xn mit Xi = 1 bei Zahl im i-ten Munzwurf und Xi = 0bei Kopf im i-ten Munzwurf. Diese n Variablen sind iid.

4.3 Def. Zufallsvariable X mit einer endlichen Menge R(X) von Realisierungenund P (X = x) = 1

|R(X)| (alle der moglichen Realisierungen sind gleich wahr-

scheinlich) heißt diskret gleichverteilt.

4.4 Bsp. Sei X diskret gleichverteilt mit R(X) = 1, . . . , n. Wir berechnen E(X)und V (X). Es gilt

E(X) =n∑i=1

iP (X = i) =n+ 1

2.

Wir berechnen V (X) mit Hilfe von E(X2). Es gilt:

E(X2) =n∑i=1

i2P (X = i)

=1

n

n∑i=1

i2

=(n+ 1)(2n+ 1)

6. (nach einer bekannten Formel).

Es folgt

V (X) = E(X2)− E(X)2

=(n+ 1)(2n+ 1)

6− (n+ 1)(n+ 1)

4

=(n+ 1)(n− 1)

12.

4.5 Bsp (Erwartungswert und Varianz gleichverteilter stetiger Zufallsvariablen).Steige gleichverteilte Variablen haben wir bereits eingefuhrt. Ist X stetig gleichverteiltin [a, b], so gilt:

(a) E(X) = a+b2

. Diese Formel ist auch intuitiv klar. Die exakte Herleitung geht

mit Hilfe der Berechnung des Integrals∫ baxdx.

(b) V (X) = (b−a)2

12. Wir konnen zuerst E(X2) berechnen:

E(X2) =1

b− a

∫ b

a

x2dx =b3 − a3

3(b− a)=

1

3(b2 + ab+ a2).


Das ergibt

V (X) = E(X2)− E(X)2

=1

3(a2 + ab+ b2)− 1

4(a+ b)2

=1

12(4a2 + 4ab+ 4b2 − 3a2 − 6ab− 3b2)

=1

12(b− a)2.

Interessanterweise sieht man die in den Formeln fur E(X) und V (X) die Werte 2bzw. 12 im Nenner, genau wie bei dem Erwartungswert und der Varianz der disrketengleichverteilten Zufallsvariablen aus 4.4.

4.6 Def. Sei p ∈ [0, 1] und seien X1, . . . , Xn iid Zufallsvariablen mit P (Xi =1) = p und P (Xi = 0) = 1 − p. Die Verteilung von X = X1 + · · · + Xn heißtBinomialverteilung mit Parametern p und n.

4.7. Man macht n Unabhangige Schusse ins Ziel und macht bei einem Schuss Treffermit Wahrscheinlichkeit p. Die Anzahl der Treffer bei n Schussen ist binomialverteiltmit Parametern p und n. Weitere praktische Beispiele lassen sehen analog aus. Etwa:Anzahl der geworfenen Zahlen bei einem n-fachen Wurf einer unfairen Munze mitWahrscheinlichkeit der Zahl gleich p.

4.8. Eine binomialverteilte Variable X mit Parametern p und n hat die folgendenEingeschaften:

(a) Die moglichen Realisierungen sind k ∈ 0, . . . , n, die Verteilung ist durch dieFormel

P (X = k) =

(n

k

)pk(1− p)n−k.

(b) E(X) = pn

(c) V (X) = p(1− p)n.

4.9 Def. Eine diskrete Zufallsvariable X mit nichtnegativen ganzzahligen Rea-lisierungen heißt Poisson-verteilt mit Parameter λ > 0, wenn ihre Verteilungdurch

P (X = k) =λk

k!e−λ.

fur alle k ∈ Z+ gegeben ist.

4.10. Die Poisson-Verteilung erinnert einen an die Taylor-Reihe

eλ =∞∑k=0

λk

k!


der Exponentialfunktion. Diese Formel kann man als 1 =∑∞

k=0λk

k!e−λ umformulieren,

woraus folgt, dass die Funktion

k 7→ λk

k!e−λ

tatsachlich die Verteilung einer Zufallsvariable ist.

4.11 Bsp. Wir berechnen den Erwartungswert und die Varianz einer Poisson-verteiltenZufallsvariablen X mit Parameter λ > 0.

(a) Der Erwartungswert ergibt sich aus der Verteilung:

E(X) =∞∑k=0

kλk

k!e−λ

Der Term fur k = 0 kann weggelassen werden. Der Term e−λ hangt nicht von kab und kann ausgeklammert werden. Die Fakultat k! enthalt den Faktor k. MitBerucksichtigung dieser Tatsachen kommt man auf die Darstellung

E(X) = e−λ∞∑k=1

λk

(k − 1)!

Die Summe kann durch geringfugige Anderungen in zur Reihe der Exponential-funktion uberfuhrt werden. Bei λk einen Faktor λ abspalten und ausklammern,k − 1 durch i ersetzen. Das ergibt:

E(X) = e−λλ∞∑i=0

λi

i!

= e−λλeλ

= λ

(b) Zur Berechnung von V (X) benutzen wir die Formel

V (X) = E(X2)− E(X)2.

Den Wert E(X) kennen wir bereits. Es bleibt, E(X2) auszurechnen. Man hat

E(X2) =∞∑k=0

k2P (X = k)

=∞∑k=0

k2λk

k!e−λ

= e−λ∞∑k=1

kλk

(k − 1)!

Hier wollen wir die Summe mit Hilfe der Taylor-Reihen der Exponentialfunktiondarstellen. Das geht folgendermaßen:

∞∑k=1

kλk

(k − 1)!=∞∑k=1

(k − 1)λk

(k − 1)!+∞∑k=1

λk

(k − 1)!

=∞∑k=2

λk

(k − 2)!︸︷︷︸λ2eλ

+∞∑k=1

λk

(k − 1)!︸︷︷︸=λeλ

.


Das ergibtE(X2) = λ2 + λ,

woraus man nunV (X) = E(X2)− E(X)2 = λ

folgert.

Fassen wir unsere Ergebnisse zusammen. Fur eine Poisson-verteilte Zufallsvariable Xmit Parameter λ > 0 gilt:

E(X) = V (X) = λ.

4.12 (Zusammenhang der Binomial- und Poisson-Verteilungen). Poisson-VerteilteZufallsvariablen kann man als Grenzwert von Binomialverteilten Zufallsvariablen er-halten. Wir wissen, der Erwartungswert einer Binomialverteilten Variablen ist pn unddie Varianz ist p(1− p)n. Nun stellen wir uns vor, dass wir p und n variieren konnen.Wir schicken n gegen unendlich und setzen dabei p = λ

n. Dann bleibt der Erwartungs-

wert der Binomialverteilten Zufallsvariablen gleich λ. Die Varianz p(1−p)n = (1−p)λkonvergiert gegen λ, da p = λ

nbei n→∞ gegen 0 geht. Es stellt sich heraus, man im

Grenzwert dieses Prozesses aus der Binomialverteilter Zufallsvariablen eine Poisson-verteilte Variable mit Parameter λ > 0 erhalt.

4.13. Aus der Interpretation in 4.12 ergeben sich praktische Kontexte, in denen diePoisson-Verteilung auftauchen kann. Nehmen wir als Beispiel die Anzahl der Nach-richten, die Sie per WhatsApp innerhalb einer Stunde erhalten. Warum konnte daseine Poisson-Verteilte Zufallsvariable sein? Wie in den meisten praktischen Kontextenmuss man die Situation etwas idealisieren. Stellen wir uns vor, es gibt 1000 Personen,die Sie kontaktieren konnen, und die Wahrscheinlichkeit, dass eine dieser PersonenSie innerhalb einer gegebener Stunde kontaktiert gleich 1

100ist. Des Weiteren ideali-

sieren wir die Situation durch die Annahme, dass diese 1000 potenzielle Kontaktan-fragen unabhangig voneinander sind. Der Erwartungswert der Anzahl der Anfragenist 1

1001000 = 10. In diesem idealisierten Modell ist die Anzahl der Anfragen eine bi-

nomialverteilte Variable. Da aber 1000 so groß ist, und der Erwartungswert 10 nichtallzu groß ist, konnen wir die Situation noch weiter idealisieren und Einfachheit hal-ben annehmen, dass die Zufallsvariable Poisson-verteilt ist, mit Parameter λ = 10.Die Praxis bestatigt, dass dieser Gedankenweg tatsachlich plausibel ist. Experimentebestatigen, dass Modellierung als Poisson-verteilte Zufallsvariable in Kontexten wieoben tatsachlich zulassig ist. Was man sich sonst vorstellen kann ist:

• Anzahl der Server-Anfragen bei bahn.de innerhalb einer Minute,

• Anzahl der Krank-Meldungen an einem großen Unternehmen,

• Anzahl der Rosinen in einem Rosinenbrotchen,

• Anzahl parkender Autos in einer Straße.

4.14 Def. Sei 0 < p < 1. Und seien X1, X2, . . . eine System unabhangigen Varial-ben mit Realisierungen aus 0, 1 und mit P (Xi = 1) = p und P (Xi = 0) = 1−p.Sei

X := min i : Xi = 1 ,

bahn.de


der kleinste Index i mit Xi = 1. Die Variable X heißt geometrisch verteilt mitParameter p.

4.15. Als Beispiel kann man eine Folge von unabhangigen Schussen ins Ziel betrach-ten, mit Xi = 1 beim Treffer im i-ten Schuss und der Wahrscheinlichkeit eines Treffersgleich p. Dann ist X die Anzahl der Schusse bis zum ersten Treffer.

4.16 Bsp. Wir berechnen die Verteilung und den Erwartungswert der geometrischenVerteilung.

(a) Man hat:

PX(X = i) := P (X = i)

= P ((X1 = 0) · · · (Xi−1 = 0)(Xi = 1))

= P (X1 = 0) · · ·P (Xi−1 = 0)P (Xi = 1) (wegen Unabhangigkeit)

= (1− p)i−1p.

(b) Der Erwartungswert ist

E(X) =∞∑i=1

iP (X = i)

=∞∑i=1

i(1− p)i−1p

= p∞∑i=1

i(1− p)i−1.

Die letzte Summe konnen wir ausrechnen, wenn wir

S =∞∑k=0

(1− p)k =1

p

verwenden. Es gilt

∞∑i=1

i(1− p)i−1 =(1− p)0+

(1− p)1 + (1− p)1+

(1− p)2 + (1− p)2 + (1− p)2+

· · ·= S + (1− p)1S + (1− p)2S + · · ·= (1 + (1− p)1 + (1− p)2 + · · · )S= S2

=1

p2.

Somit ist

E(X) =1

p.


4.17. Ein weiteres Hilfsmittel zur Berechnung der Erwartungswerte, das wir nochgar nicht diskutiert haben, basiert auf bedingten Erwartungswerten. Mit bedingtenErwartungswerten kann der Erwartungswert von geometrische verteilten Zufallsva-riablen recht einfach ausgerechnet werden (ohne unendliche Summen!). Wir fuhrenbedingten Erwartungswert fur disrkete Zufallsvariablen ein.

4.18 Def. Sei X diskret verteilte Zufallsvariable mit der Menge der Realisierun-gen R(X) und sei A Ereignis mit P (A) > 0. Dann nennen wir

E(X|A) =∑

x∈R(X)

xP (X = x|A)

bedingten Erwartungswert von X unter der Bedingung A.

4.19. Der bedingte Erwartungswert E(X|A) ist der Erwatungswert von X bzgl.Wahrscheinlichkeitsraums, in dem das Antreten des Ereignis A vorausgesetzt ist.

4.20. Sei X Zufallsvariable und seien A1, . . . , Am Ereignisse mit Ai ∩Aj = ∅ fur allei und j mit i 6= j und A1 ∪ . . . ∪ Am = Σ. Dann gilt:

E(X) = E(X|A1)P (A1) + · · ·+ E(X|Am)P (Am).

Diese Formel ist analog zur Formel von Bayes.

4.21 Bsp. Fur die Verteilung X aus 4.14 konnen wir E(X) folgendermaßen ausrech-nen:

E(X) = E(X|X1 = 1)P (X1 = 1) + E(X|X1 = 0)P (X1 = 0)

= E(X|X1 = 1)p+ E(X|X1 = 0)(1− p)= p+ E(X|X1 = 0)(1− p).

Wir benutzen die Interpretation aus 4.15. Unter der Bedingung, dass der erster Schussgleich ein Treffer ist, ist der Erwartungswert fur die Anzahl der Schusse bis zum erstenTreffer gleich 1. Denn unter der Bedingung X1 = 1 ist X immer gleich 1.

Unter der Bedingung, dass der erste Schuss kein Treffer ist, haben wir einen Schussverbraucht, aber ansonsten sind wir in einer ahnlichen Situation wie vor dem erstenSchuss. Das ergibt:

E(X|X1 = 0) = 1︸︷︷︸vebrauchter Schuss

+E(X)

Nun setzen wir diese Darstellung von E(X|X1 = 0) in die Formel fur E(X) ein underhalten

E(X) = p+ (1 + E(X))(1− p).Das ergibt

E(X) = p+ 1− p+ E(X)(1− p),woraus man

E(X) =1

p

erhalt.


4.22 Def. Seien µ ∈ R und σ > 0. Eine stetige Zufallsvariable X heißt Gauß-verteilt, wenn sie die Dichte

w(x) =1

σ√

2πe−

12(x−µσ )

2

besitzt. Man schreibt in diesem Fall X ∼ N(µ;σ2). Die Variablen X ∼ N(0; 1)heißen Standardnormalverteilt.

4.23. Normalverteilungen mit µ = 0 und unterschiedlichen Werten von σ2:

4 2 0 2 4

0.00

0.05

0.10

0.15

0.20

0.25

0.30

0.35

0.40 sigma^2=1sigma^2=2sigma^2=3sigma^2=4sigma^2=5sigma^2=6

4.24. Gauß-Verteilte Zufallsvariablen sind in Stochastik und Statistik sehr beliebt.Im nachsten Abschnitt prasentieren den sogenannten zentralen Grenzwertsatz, deruns erklart, warum das so ist.

4.25. Wir diskutieren zuerst die Standardnormalverteilten Zufallsvariablen X ∼N(0; 1). Die Dichte einer solchen Zufallsvariablen wird als φ bezeichnet. Mit An-wendung der vorigen Definition erhalten wir:

φ(x) =1√2πe−

12x2 .

Hier einige Bemerkungen:

(a) A priori ist es nicht klar, warum φ(x) tatsachlich Dichte einer Zufallsvariablenist. Man musste dafur

∫∞−∞ φ(x)dx = 1 verifizieren. Es stellt sich heraus, dass

man ‘keine Formel’ fur die Stammfunktion von φ hat. Das heißt, die Stamm-funktion von φ lasst sich nicht durch elementare Funktion darstellen. Daherwird

∫∞−∞ φ(x)dx nicht durch die Berechnung von Stammfunktion sonder durch

andere Ansatze berechnet (die wir hier nicht diskutieren).

(b) Wie man aus der Formel sieht, ist φ symmetrisch (d.h., φ(x) = φ(−x)). Desweiteren Weiteren konvergiert φ(x) sehr schnell gegen 0, bei |x| → ∞. Etwa

φ(4) = 0.00013383022576488537 . . .

(c) Aus der Symmetrie φ(x) = φ(−x) folgt, dass E(X) = 0 ist.


(d) Zur Berechnung der Varianz von X:

V (X) = E((X − E(X))2)

= E(X2)

=

∫ ∞−∞

x2φ(x)dx

=1√2π

∫ ∞−∞

x2e−12x2dx

=1√2π

∫ ∞−∞

(−x)(e−12x2)′dx (partielle Integration)

=1√2π

(−x)e−12x2∣∣∣∣∞−∞− 1√

2π

∫ ∞−∞

(−x)′(e−12x2)dx

=

∫ ∞−∞

φ(x)dx

= 1.

Also ist V (X) = 1.

(e) Die Verteilungsfunktion von X ∼ N(0; 1) wird als Φ bezeichnet. Es gilt

Φ(x) =

∫ x

−∞φ(t)dt.

Der Wert Φ(x) ist die Wahrscheinlichkeit von X ≤ x. Φ ist Stammfunktion vonφ. Wie oben besprochen hat man fur Φ ‘keine einfache Formel’. Trotzdem kannΦ(x) mit Anwendung numerischer Verfahren auswerten (mehr zu numerischenVerfahren in Kapitel III). Da die Funktion Φ fur Anwendungen (insb. in Stati-stik) wichtig ist, ist sie in vielen Systemen direkt verfugbar (Excel, OpenOfficeCalc sowie statistische Bibliotheken verschiedener Programmiersprachen).

(f) Aus der Symmetrie von φ ergeben sich die folgende Eigenschaft von Φ:

Φ(−x) + Φ(x) = 1.

Sei etwa x ≥ 0. Dann ist Φ(x) = P (X ≤ x) und Φ(−x) = P (X ≤ −x). Daaber φ(x) = φ(−x) gilt, ist P (X ≤ −x) = P (X ≥ x). Die linke Seite ist alsodie Summe der Wahrscheinlichkeiten von X ≤ x und X ≥ x. Das ist naturlich1.

4.26 (N(µ, σ) ausN(0, 1)). Allgemeine normalverteilte ZufallsvariablenX ∼ N(µ, σ2)konnen aus standardnormalverteilten Zufallsvariablen X∗ ∼ N(0, 1) durch

X = σX∗ + µ (I.4)

hergeleitet werden.

(a) Fur den Erwartungswert und die Varianz hat man:

E(X) = E(σX∗ + µ) = σE(X∗) + µ = µ.

V (Y ) = V (σX∗ + µ) = σ2V (X∗) = σ2.

5. MITTELWERT UMFANGREICHER STICHPROBEN 37

(b) Um zu uberprufen, dass X ∼ N(µ, σ2) gilt, mussen wir die Dichte von Xausrechnen und feststellen, dass das die Dichte aus Definition 4.22 ist. Wirkonnen etwa die Verteilungsfunktionen benutzen:

FX(x) = P (X ≤ x)

= P (σX∗ + µ ≤ y).

= P (X∗ ≤ y − µσ

)

= FX∗(x− µσ

).

= Φ(x− µσ

)

Wir haben die Verteilungsfunktion von X durch die Verteilungsfunktion von X∗

ausgedruckt. Die Dichte einer stetigen Zufallsvariablen ist die Ableitung ihrerVerteilungsfunktion. Somit ist F ′X∗ = φ. Durch die Kettenregel sehen wir also,dass

F ′X(x) =1

σΦ′(

x− µσ

)

=1

σφ(x− µσ

)

=1

σ√

2πe−

12(x−µσ )

2

Dichte von X ist.

4.27. Die Bemerkung 4.26 zeigt: Fur X ∼ N(µ;σ2) gilt E(X) = µ und V (X) = σ2.

4.28. In Bemerkung 4.26 haben wir aus der Verteilung N(0, 1) die allgemeine Vertei-lung N(µ, σ2) hergeleitet. Diesen Prozess kann man auch umkehren. Ist X ∼ N(µ, σ2)so ist die Variable

X∗ :=X − µσ

standardnormalverteilt (vgl. auch (I.4)). Im folgenden Abschnitt werden wir die Nor-malisierungsabbildung X 7→ X∗ fur allgemeine Zufallsvariablen einfuhren.

4.29. Unser Zoobesuch ist nun zu Ende. Mit den Verteilungen, die wir uns angeschauthaben, haben wir uns ausgiebig beschaftigt, damit wir sie besser verstehen. Naturlichgibt es sehr viele weitere Verteilungen, die fur Anwendungen und Theorie wichtigsind.

5 Satze uber den Mittelwert umfangreicher Stich-

proben

5.1 Def. Eine folge X1, . . . , Xn aus n iid Zufallsvariablen heißt Stichprobe vomUmfang n.


5.2 Thm (Das Gesetz der großen Zahlen). Seien µ ∈ R und σ > 0. SeienX1, X2, X3, . . . unendlich viele iid Zufallsvaralben mit dem Erwartungswert µ undder Varianz σ2. Dann gilt fur ein beliebiges ε > 0 die Gleichung

limn→∞

P

(∣∣∣∣∣(n∑i=1

1

nXi)− µ

∣∣∣∣∣ < ε

)= 1.

5.3. Hier Illustration von Theorem 5.2 fur mehrere endliche Verteilungen. Jedes Bildprasentiert die Originalverteilung und die Verteilung von (X1 + · · ·+Xn)/n fur eineWahl von n. Man sieht, dass sich die Verteilung von (X1 + · · · + Xn)/n um denErwartungswert der Originalverteilung konzentriert.

Munze Wurfel beliebige endl. Verteilung

n = 10

0 1E=1/2 1 2 3 4 5 6E=7/2 1 2 4E=14/5

n = 20

0 1E=1/2 1 2 3 4 5 6E=7/2 1 2 4E=14/5

n = 100

0 1E=1/2 1 2 3 4 5 6E=7/2 1 2 4E=14/5

Fur stetige Verteilungen sehen entsprechende Bilder ahnlich aus (Thm 5.2 gilt furallgemeine Verteilungen). Hier Beispiele fur stetige zwei Verteilungen und mehrere n:

5. MITTELWERT UMFANGREICHER STICHPROBEN 39

n = 2

E0.0000

0.0025

0.0050

0.0075

0.0100

0.0125

0.0150

0.0175

0.0200

E0.000

0.005

0.010

0.015

0.020

n = 30

E0.000

0.005

0.010

0.015

0.020

0.025

0.030

E0.000

0.005

0.010

0.015

0.020

0.025

0.030

0.035

n = 50

E0.00

0.01

0.02

0.03

0.04

0.05

0.06

0.07

E0.00

0.02

0.04

0.06

0.08

Man merkt auch, dass mit dem wachsenden n die Verteilung von (X1 + · · ·+Xn)/nihre ‘Personlichkeit’ verliert. Bei n = 2 ist die Form der Verteilung in den beidenvorigen Beispielen unterschiedlich. Ab n ≥ 30 ist die Form einfach nur eine Glocke.Die letztere Beobachtung fuhrt zu unserem nachsten Theorem (vgl. 5.8).

5.4. Die Botschaft des vorigen Theorems: bei iid Variablen ‘verschwindet der Zufall’aus der Summe 1

n

∑ni=1Xi, wenn n sehr groß ist. Diese Summe ist annahernd µ und

weist nur sehr geringe zufallige Abweichungen von µ auf. Das Gesetz der großen Zah-len passt in das folgende allgemeine Muster: anhand einer großen Stichproben wirdeine ‘akkumulierende’ Zufallsvariable gebildet, die nur geringfugig zufallige Abwei-chungen von ihrem Mittelwert aufweist. Der Mittelwert dieser Variable ist fur unsinteressant (im Fall des Gesetzes der Großen Zahl ist das der Erwartungswert derzugrundeliegenden Verteilung). Aussagen mit diesem Muster bilden die Grundlagerder mathematischen Statistik, die wir im folgenden Kapitel diskutieren werden.

5.5 (Monte-Carlo-Integration). Nehmen wir an, wir wollen das Integral

If :=

∫[0,1]n

f(x)dx

berechnen, konnen aber keine Formel dafur ermitteln (fur die ‘meisten’ f wurde mankeine Formel haben). Was wir machen konnten ware die numerische Approximation.Wir konnten [0, 1] durch eine endliche Menge

S :=

i

k: i = 0, . . . , k

diskretisieren und If durch die Summe

1

(k + 1)n

∑x∈Sn

f(x)


approximieren. Das Problem ist nur, dass bei einem großen n die Summe sehr vieleSummanden hat. Denn Sn hat (k + 1)n Elemente. Wenn unser n = 20 ist und wirk = 9, so ist (k + 1)n = 1020 – eine riesige Zahl.

In einigen Problemenbereichen muss man tatsachlich hoch-dimensionale Integralausrechnen (Physik, Biologie, Finanzmarkte). Die sogenannte Monte-Carlo-Integrationhat sich mittlerweile als Standardtechnik etabliert. Wir betrachtenN zufallige gleichmaßigverteilte Punkte X1, . . . , XN im n-dimensional Wurfel [0, 1]n. Das heißt

Xi = (Xi,1, . . . , Xi,n),

wobei die Nn Variablen Xi,j unabhangig und gleichverteilt in [0, 1] sind. Es kann mitHilfe des Gesetzes der großen Zahlen gezeigt werden, dass die Zufallsvariable

QN =1

N

n∑i=1

f(Xi)

den Wert If approximiert (d.h., der Abstand von QN und If ist mit großer Wahr-scheinlichkeit klein.)

5.6 Def. Ist X Zufallsvariable mit endlichen E(X), V (X) und V (X) > 0, soheißt

X∗ :=X − E(X)√

V (X)

die standardisierte Zufallsvariable von X.

5.7. Fur X∗ gilt E(X∗) = 0 und V (X∗) = 1.

5.8 Thm (Zentraler Grenzwertsatz). Seien µ ∈ R und σ > 0. Seien X1, X2, . . .unendlich viele iid Zufallsvariablen mit einer Verteilung mit dem Erwartungswertµ und der Varianz σ2. Sei Fn die Verteilungsfunktion von(

X1 + · · ·+Xn

n

)∗=X1 + · · ·+Xn − nµ

σ√n

.

Dann giltlimn→∞

Fn(x) = Φ(x)

fur alle x ∈ R.

5.9. Die Botschaft des vorigen Theorems: Die Verteilungsfunktion von(X1 + · · ·+Xn

n

)∗ist annahernd eine Standardnormalverteilte Zufallsvariable, wenn n groß ist, ganzunabhangig davon, wie die Verteilung der Ausgangsvariablen X1, X2, X3, . . . aussah.Mit anderen Worten: wenn man das arithmetische Mittel der ersten n iid Variablen

6. AUSBLICK UND LITERATURHINWEISE 41

X1, . . . , Xn ‘passend skaliert’, so erhalt man fur große n annahernd eine Standard-normalverteilte Zufallsvariable. Wenn also n groß ist, so kann man

P (a ≤ X1 + · · ·Xn − nµσ√n

≤ b)

mit a, b ∈ R und a < b durch

Φ(b)− Φ(a),

Hier ist Φ(b)−Φ(a) die Wahrscheinlichkeit davon, dass eine StandardnomralverteilteZufallsvariable im Segment [a, b] liegt. Diese Approximation werden wir in Kapitel IImehrfach benutzen.

6 Ausblick und Literaturhinweise

6.1 (Maßtheorie). Manchmal erschien es mir, dass ich einige Konzepte indirekt be-schreiben muss, weil ich das Integral

∫f(x)µ(dx) einer Funktion bzgl. eines allge-

meinen Maßes nicht benutzen konnte (Sie kennen diesen Begriff ja nicht). Mit Hilfedieses Begriffs kann man z.B. Summieren und Integrieren einheitlich behandeln, wasdie Prasentation der Grundkonzepte der Stochastik auch einheitlich macht.

6.2 (Weitere Themen). Was wir noch diskutieren konnte, wenn wir mehr Zeit hatten:

(a) Als Verallgemeinerung von Zufallsvariablen kann man auch zufallige Vekto-ren betrachten. Das ware der Ubergang vom ein-dimensionalen Fall zum Falleiner allgemeinen Dimension. Z.B. kann man auch die n-dimensionale Gauß-Verteilung einfuhren.

(b) Die Theorie stochastischer Zeitreihen spielt in vielen Anwendungen eine wichti-ge Rolle. Zu dieser Theorie gehort auch die Untersuchung von Markov-Ketten.

(c) Formel fur die Dichte der Summe von zwei unabhangigen stetigen Zufallsvaria-blen (Faltung).

6.3 (Allgemeine Quellen zur Stochastik). Zu allgemeiner Stochastik gibt es sehr vielLiteratur. Ich wurde empfehlen, Quellen zu benutzen, in denen einerseits die Theorieexakt diskutiert wird und andererseits spezielle Situationen und Beispiele diskutiertwerden.

(a) Einer der Kursteilnehmer hat auf das Buch [BT02] hingewiesen. Das Buchscheint ziemlich beliebt zu sein (knapp 800 Zitate laut Google Scholar). Dieprasentierte Theorie ist an vielen Beispielen illustriert. Das Buch ist als Vorle-sungskript online verfugbar.

(b) Kapitel 2 von [Eva13] prasentiert kurz die Grundlagen allgemeiner Wahrschein-lichkeitsraume. Eine Version dieses Buchs ist auch in der Form eines Vorlesungs-skripts online verfugbar.

(c) Ein Kollege aus der Stochastik hat mir die “Stochastik fur Einsteiger” vonHenze [Hen12] empfohlen.


(d) Das Buch von Szekely [Sze90, Sze86] gibt verbluffende und lehrreiche Beispielezu verschiedenen Aspekten der Wahrscheinlichkeitstheorie.

6.4 (Quellen zu speziellen Themen aus der Stochastik). (a) Wer sich fur randomi-sierte Algorithmen interessiert, kann etwa uber die Analyse der Laufzeit vonQuickSort in [CLRS09] nachlesen.

(b) Das Buch [AB09] uber die Komplexitatstheorie enthalt ein Kapitel uber dierandomisierten Berechnungen und einen Anhang mit Grundlagen der endlichenWahrscheinlichkeitsraume.

Kapitel II

Statistik

In der Statistik geht es allgemein um die Analyse der umfangreichen Daten, dieZufall beinhalten. Somit ist Statistik ein naturlicher Bestandteil der Data Science.Wir behandeln in diesem Kapitel Parametershatzung und lineare Regression.

1 Statistische Schatzung

1.1 Bsp (Grundprinzipien der Statistik an einem Beispiel). Abfullgewicht einerzufallig gewahlten Tafel Schokolade aus einer Lieferung ist eine Zufallsvariable. IhreVerteilung ist naturlich eindeutig durch die Lieferung gegeben, wenn aber die Liefe-rung groß ist, wurde man wahrscheinlich die Verteilung nicht exakt berechnen wollen(zu aufwandig). Man wiederholt also das Experiment ‘Zufallige Wahl einer Tafel Scho-kolade’ n mal und erhalt somit eine Stichprobe X1, . . . , Xn im Umfang n. Man hat dieFreiheit, n so zu wahlen, dass die Stichprobe einerseits informativ und andererseitsnicht zu groß ist. Die Werte X1, . . . , Xn kann man a priori nicht voraussagen (sie sindzufallig, denn man weiß nicht welche Tafel gewahlt werden, und die Wahl ist zufallig),aber sobald die Stichprobe erhoben ist, hat man mit konkreten Werten zu tun.

1.2 (Statistische Schatzung). Die Aufgabe der statistischen Schatzung besteht darin,verschiedene unbekannte Parameter der zugrundeliegenden Verteilung, wie etwa denErwartungswert oder die Varianz, mit Hilfe der erhobenen Stichprobe zu schatzen.Man interessiert sich vor allem fur den Erwartungswert und die Varianz.

1.3 Def. Eine Schatzfunktion ist eine Funktion, die man zur Stichprobe anwendetum, einen gegebene Parameter der Verteilung zu schatzen. Die Zufallsvariable,die man durch die Einsetzung der Stichprobe erhalt, wenn man die Stichprobe indie Schatzfunktion einsetzt, nennen wir Schatzer.

1.4 Bsp. Hier einige sehr verbreitete Schatzer:

(a) Den Schatzer

X :=1

n

n∑i=1

Xi

43

44 KAPITEL II. STATISTIK

aus der Stichprobe X1, . . . , Xn benutzt man oft zur Schatzung des Erwar-tungswerts. An diesem Beispiel kann man nun auch verdeutlichen was ein eineSchatzfunktion und was ein Schatzer ist. Die Schatzfunktion ist die Funktion

x = (x1, . . . , xn) ∈∞⋃n=1

Rn 7−−−→ x :=x1 + · · ·+ xn

n∈ R,

welche den Mittelwert einer beliebigen Folge von Werten aus R bildet. Hier z.B.die Umsetzung in Python:

Average=lambda x : sum(map( f loat , x ) ) / len ( x )

Wenn wir eine StichprobeX1, . . . , Xn bzgl. einer Verteilung betrachten, so erhal-ten wir durch das Einfugen der Stichprobe in die Schatzfunktion den SchatzerX fur den Erwartungswert der zugrundeliegenden Verteilung. Das X1, . . . , Xn

Zufallsvariablen sind, ist auch X eine Zufallsvariable. Hier die Umsetzung inPython im Fall einer Gleichverteilung in [0, 1]:

from random import ∗Xbar = lambda n : Average ( [ uniform (0 , 1 ) for i in xrange (n) ] )

(b) Der Schatzer

S2 :=1

n− 1

n∑i=1

(Xi −X)2

wird oft zur Schatzung der Varianz benutzt. Es ist tatsachlich so, dass man alsFaktor vor der Summe 1

n−1und nicht 1

n.

(c) Oft muss man die Wahrscheinlichkeit p des Auftretens eines Merkmals schatzen.Etwa die Wahrscheinlichkeit das ein zufallig gewahltes Gerat (aus einer An-sammlung von Geraten) defekt ist. Man kann die Zufallsvariable einfuhren, dieden Wert 1 bei einem defekten Gerat annimmt und 0 sonst. Die Stichprobebesteht nun aus n Zufallsvariablen X1, . . . , Xn, mit Realisierungen aus 0, 1.Der Schatzer von p fur die Wahrscheinlichkeit, dass ein zufallig gewahltes Geratdefekt ist, ist dann der Anteil der defekten Gerate in der Stichprobe (d.h., dieAnzahl der defekten Gerate in der Stichprobe geteilt durch den Umfang derStichprobe). Das heißt, p ist nichts anderes als X im Fall einer Verteilung mitzwei Realisuerungen 0 und 1.

1.5. Wenn man sich eine Weise uberlegt hat, einen Schatzer T zur Abschatzung ei-nes unbekannten Parameters θ (Erwartungswert, Varianz usw.) aus der StichprobeX1, . . . , Xn zu konstruieren, kann man die Frage stellen, ob der Schatzer T den Pa-rameter θ tatsachlich schatzt. Man will, dass mit dem wachsenden Umfang n derStichprobe, der Schatzer T den Parameter T immer besser voraussagt. In der folgen-den Definition werden Bedingungen vorgeschlagen, die man vom Schatzer T fordernkann.

1. STATISTISCHE SCHATZUNG 45

1.6 Def. Sei eine Verteilung gegeben. Man betrachte eine Schatzfunktion

T :∞⋃n=1

Rn → R

die einer Folge reeller Werte beliebiger Lange n ∈ N einen Wert aus R zuordnet.Fur jedes n ∈ N, betrachte einen Schatzer

Tn = T (X1, . . . , Xn)

aus der Stichprobe X1, . . . , Xn im Umfang n bzgl. der zugrundeliegenden Vertei-lung. Sei θ ∈ R. Die Folge (Tn)n∈N heißt in Bezug auf θ:

(a) erwartungstreu, wennE(Tn) = θ

fur alle n gilt.

(b) konsistent, wennlimn→∞

P (|Tn − θ| < ε) = 1

fur alle ε > 0 gilt.

(c) konsistent im Quadratischen Mittel, wenn

limn→∞

E((Tn − θ)2) = 0

gilt.

In Bezug auf (a), (b) und (c) wird θ der durch (Tn)n∈N geschatzte Parametergenannt.

1.7. Die Ungleichung von Markov 3.26(a) ergibt, dass die Konsistenz im quadrati-schen Mittel die Konsistenz impliziert.

1.8. Wenn man mathematisch prazise bleiben mochte so, musste man eigentlich zwi-schen den folgenden drei Konzepten unterscheiden:

(a) Die Schatzfunktion

T :∞⋃n=1

Rn → R.

(b) Eine Folge der Schatzer (Tn)n∈N zu einer Schatzfunktion T .

(c) Ein Schatzer Tn fur einen gegebenen Umfang n der Stichprobe.

In der ‘Umgangssprache’ macht man allerdings oft keinen Unterschied und benutztdas Wort Schatzer in allen drei Fallen. Es wird meistens aus dem Kontext klar,welches der oben angefuhrten drei Konzepte man meint.

1.9 Bsp. Betrachten die Stichrprobe X1, . . . , Xn aus einer Gleichverteilung auf demSegment [0, u] mit u > 0. Wie kann man den Parameter u schatzen?


(a) Man weiß, dass der Mittelpunkt u/2 des Segments der Erwartungswert dieserGleichverteilung ist. Somit ist

Tn :=2

n(X1 + · · ·+Xn)

ein erwartungstreue Schatzer fur u. Des weiteren gilt

E((Tn − u)2) =2

n

n∑i=1

E((Xi − E(Xi))2) =

2

nV (X1).

Das heißt, der Schatzer Tn ist konsistent im quadratischen Mittel.

(b) Gibt es bessere Moglichkeiten u zu schatzen? Schatzer mit einer hoheren Kon-sistenz? Hier ein weiterer Vorschlag. Wir konnen das Maximum der Stichprobebilden:

Mn := maxX1, . . . , Xn.

Es stellt sich heraus, dass man auf der Basis von Mn einen erwartungstreuenSchatzer fur u aufbauen kann. Wir mochten zunachst den Erwartungswert vonMn ermitteln. Die Verteilungsfunktion ist

FMn(x) = P (Mn ≤ x)

= P ((X1 ≤ x) · · · (Xn ≤ x))

= P (X1 ≤ x) · · ·P (Xn ≤ x)

= P (X1 ≤ x)n

= (x

u)n

fur 0 ≤ x ≤ u. Die Dichte wMn(x) von Mn ist die Ableitung

wMn(x) = F ′Mn(x) =

n

unxn−1.

Somit ist der Erwartungswert gleich

E(Mn) =

∫ u

0

xwMn(x)dx =

∫ u

0

xn

unxn−1dx =

n

n+ 1u.

Das heißt,

Wn =n+ 1

nMn =

n+ 1

nmaxX1, . . . , Xn.

ist auch ein erwartungstreuer Schatzer fur u. Man kann sich nun uberlegen, obWn konsistent ist und, gegebenfalls, die Konsistenzen von Wn und Tn verglei-chen.

2 Zahlwahrscheinlichkeit einer unfairen Munze

2.1 (Aufgabenstellung). Wir betrachten eine Munze, bei der man die Zahl mit Wahr-scheinlichkeit p wird und Kopf mit Wahrscheinlichkeit 1 − p, wobei man 0 < p < 1hat. Im Fall p = 1

2haben wir eine faire Munze. Der Wert p ist uns unbekannt.

2. ZAHLWAHRSCHEINLICHKEIT EINER UNFAIREN MUNZE 47

Unsere Aufgabe besteht darin, den Wert p statistisch zu schatzen. Wir konnennun n ∈ N unabhangige Wurfe unsere Munze durchfuhren. Sei Xi die Zufallsvariablemit Xi = 1, wenn im i-ten Wurf Zahl und Xi = 0 wenn im i-ten Wurf Kopf geworfenwurde. Als Schatzer fur p setzen wir den Mittelwert

p :=X1 + · · ·+Xn

n

der StichprobeX1, . . . , Xn ein. Im Sinne der Definition 1.6(b) konnen wir uns uberlegen,wie wahrscheinlich es ist, dass der Abstand von p und p klein ist.

2.2. Wir haben unsere Aufgabe mit Hilfe von Munzen als eine Sachaufgabe formuliert.Naturlich kann man uber die Abschatzung eines beliebigen zufalligen Ereignis reden(ein Treffer bei einem Schuss usw.).

2.3. Der Erwartungswert von ist E(p) = p und die Varianz ist V (p) = p(1−p)n

. Derzentraler Grenzwertsatz sagt uns, dass die Zufallsvariable

p− E(p)√V (p)

annahernd standardnormalverteilt ist. Nach dem zentralen Grenzwertsatz 5.8

P(|p− p| ≤ g√

np(1− p)

)≈ 2Φ(g)− 1, (II.1)

fur g > 0, wenn n genugend groß ist. Wir tun so, also ob ≈ Gleichheit ware. UmBetrage in der Ungleichung unter P zu loschen, quadrieren wir die Ungleichung. Dasgibt die quadratische Ungleichung

(p− p)2 − g2

np(1− p)︸︷︷︸

Q(p)

≤ 0.

Die quadratische Funktion Q(p) beschreibt, wenn n ausreichend groß ist, eine ‘nachoben’ gerichtete Parabel. Es gilt Q(0) > 0 Q(1) > 0 und fur 0 ≤ p ≤ 1 gilt Q(p) ≤ 0.Daher kann die Ungleichung als

p1 ≤ p ≤ p2

aufgelost werden, wobei p1, p2 die linke und rechte Nullstellen der quadratischen Funk-tion Q(p) sind. Die Werte p1, p2 liegen im Segment [0, 1]. Die Nullstellen p1, p2 konnennach der bekannten Formel bestimmt werden zur Losung quadratischer Gleichungenbestimmt werden (in der Schule wird die Formel die p-q-Formel oder auch die Mit-ternachtformel genannt). Man hat

Q(p) =

(1− g2

n

)p2 −

(2p+

g2

n

)p+ p2.

Das heißt,

Q(p) = ap2 + bp+ c


mit

a := 1− g2

n

b := −(

2p+g2

n

)

c := p2.

Nach der Mitternachtformel gilt

p1 :=−b−

√b2 − 4ac

2a, p2 :=

−b+√b2 − 4ac

2a.

2.4. Damit wir ein Konfidenzintervall fur p nach der oben beschriebenen Metho-de erhalten wollen, muss fur n die unterere Schranke n > g2 gelten. Je hoher dasgewunschte Konfidenzniveau 1−α ist, desto großer die untere Schranke g2 an n sein.

2.5 Bsp. Hier einer Stichprobe aus der Verteilung, bei der 1 mit Wahrscheinlichkeitp = 0,3 und 0 mit Wahrscheinlichkeite 1− p vorkommt:

00100110100110001100001010110101001000000110010001010011010011000110000101011010100100000011001000101001101001100011000010101101010010000001100100010000110100110001100001010110101001000000110010001000011010011000110000101011010100100000011001000100001101001100011000010101101010010000001100100010000010100110001100001010110101001000000110010001000001010011000110000101011010100100000011001000100000111001100011000010101101010010000001100100010000011000110001100001010110101001000000110010001000001100

(Die Stichprobe sieht nicht ganz zufallig aus, weil das eigentlich Computer-generiertepseudozufallige Zahlen sind.) Wenn wir nur n erste Werte dieser Stichprobe berucksichtigen,konnen wir eine Stichprobe vom Umfang n fur verschiedene n bilden. So andert sichdas Konfidenzinvervall, wenn wir den Umfang n variieren:

50 100 150 200 250 300 350 400 450 500Groesse der Stichprobe

0.20

0.25

0.30

0.35

0.40

0.45

0.50

0.55

0.60

0.65

Wahrs

chein

lichke

iten u

sw

Der unbekannte Parameter pUntere Grenze des KonfindenzinvervallsObere Grenze des Konfidenzinvervalls

Das Konfidenzniveau wurder in diesem Beispiel gleich 0,9 gesetzt. Bei der Stich-probe vom Umfang 50 ist das Konfidenzintervall noch recht groß. Je großer der Um-fang ist, desto kleiner wird tendenziell das Konfidenzinvervall.

2. ZAHLWAHRSCHEINLICHKEIT EINER UNFAIREN MUNZE 49

2.6 Bsp. Zuricher Klinik Jahre 1948-1952, Operative Behandlung von Bronchektasi-en. Gegeben: 79 Patienten behandelt, 3 davon gestorben. Aus diesen Daten erhaltenwir

p =3/79 n = 79.

Man setztg = 1.95996398454

ermittelt auf p und n und g basierend die quadratische Gleichung

ap2 + bp+ c = 0

in einer Unbekannten p mit

a = 1.04862606102,

b = −0.12457542811,

c = 0.00144207659029

bestimmt die zwei Losungen p1, p2 mit 0 ≤ p1 ≤ p2 ≤ 1 dieser Gleichung und erhaltdas Konfidenzinvall

[p1, p2] = [0.0129980868894, 0.105800627677].

zum Konfidenzniveau 0,95.

2.7 (Open Office & Excel). Die Berechnung von g aus der Angabe von 2Φ(g)− 1 =0,95 kann in Open Office und Excel folgendermaßen durchgefuhrt werden. In einerTabellenzelle die Formel

=NORMINV((0,95+1)/2;0;1)

eingeben.

2.8 (Normalverteilung in Python). Bibliotheken laden:

from s c ipy . s t a t s import normimport matp lo t l i b . pyplot as p l timport numpy as np

Verteilungsfunktion:

x=np . l i n s p a c e (−5 ,5 ,100)p l t . p l o t (x ,map(norm . cdf , x ) )p l t . show ( )

Inverse Verteilungsfunktion:

p=np . l i n s p a c e ( 0 . 0 5 , 0 . 9 5 , 1 0 0 )p l t . p l o t (p ,map(norm . ppf , p ) )p l t . show ( )

Begriffe und Abkurzungen:

Englische Abkurzung Englisch Deutschpdf probability density function Dichtecdf cumulative density function Verteilungsfunktionppf percent point function Die Inverese der Verteilungsfunktion


2.9 Def (Konfidenzintervall). Sei θ ∈ R, sei X1, . . . , Xn eine Stichprobe aus einerVerteilung und

A = a(X1, . . . , Xn),

B = b(X1, . . . , Xn)

Schatzer. GiltP(θ ∈ [A,B]

)= 1− α,

so heißt [A,B] das Konfidenzintervall zum Konfidenzniveau 1− α fur den Para-meter θ. Der Wert α heißt Irrtumswahrscheinlichkeit.

2.10. Im Beispiel 2.6 war [p1, p2] das Konfidenzintervall fur Parameter p. Das gewahlteKonfidenzinveau war 0,95.

3 Schatzungen fur Normalverteilung

3.1 Def. Gilt fur die Verteilungsfunktion F einer Verteilung die Gleichung

F (x) = p,

so nennt man x das p-Quantil der Verteilung. Das 12-Quantil wird auch der Median

genannt.

3.2. Seien a ∈ R α/2-Quantil und b ∈ R (1 − α/2)-Quantil einer stetigen Zufallsva-riablen X und sei α ∈ [0, 1]. Dann gilt offensichtlich

P (a ≤ X ≤ b) = F (b)− F (a) = (1− α/2)− α/2 = 1− α.

Das heißt, X liegt im Segment [a, b] mit Wahrscheinlichkeit 1 − α. Diese einfacheBeobachtung werden wir zur Bestimmung von Konfidenzinvervallen benutzen. Ausder Beobachtung sieht man, das man bei der Berechnung von Konfidenzinvervalleneine gewisse Freiheit hat.

3.3 (Aufgabe der Schatzung des Mittelwerts bei bekannter Varianz im Fall der Nor-malverteilung). Gegeben sei eine Stichprobe einer normalverteilten Zufallsvariablenmit dem Erwartungswert µ und der Varianz σ2. Die Varianz sei bekannt. Wir schatzenden Erwartungswert µ durch den Mittelwert uber die Stichprobe. Es soll ein Konfi-denzinvervall fur µ zu einem gegebenen Konfidenzniveau 1− α bestimmt werden.

3.4 Thm. Die Summe unabhangiger normalverteilten Zufallsvariablen ist wiedernormalverteilt

3.5 (Losung der Schatzaufgabe 3.3). Aus Theorem 3.4 folgt, dass

X =X1 + · · ·+Xn

n

3. SCHATZUNGEN FUR NORMALVERTEILUNG 51

eine normalverteilte Zufallsvariable mit der Varianz σ2/n und dem Erwartungswertµ ist. Die Zufallsvariable

X − µσ/√n

ist also Standardnormalverteilt. Es folgt

P(∣∣∣∣X − µσ/

√n

∣∣∣∣ ≤ g)

= 2Φ(g)− 1

Wir fixieren ein g mit 2Φ(g)− 1 = 1− α (d.h., g = Φ−1(1− α/2)). Somit ist

[X − g σ√

n,X + g

σ√n

]

das Konfidenzinvervall zum Konfidenziniveau 1− α.

3.6 Bsp. Die folgende Stichprobe aus der Normalverteilung mit σ2 = 1 und einemunbekannten Erwartungswert µ ∈ R wird benutzt, um µ zu schatzen.

3 .91 4 .89 4 .61 5 .01 5 .87 5 .18 3 .58 4 .12 3 .77 5 .40 4 .38 4 .16 3 .75 5 .315 .32 6 .53 5 .05 4 .88 5 .98 4 .93 4 .36 5 .09 5 .21 7 .86 4 .88 5 .12 4 .724 .54 4 .07 7 .35 3 .26 4 .62 5 .79 4 .37 5 .09 6 .43 4 .68 5 .16 5 .59 4 .407 .50 6 .21 6 .96 4 .80 4 .87 6 .48 4 .16 5 .91 4 .75 4 .73 4 .79 5 .77 5 .625 .19 4 .27 6 .09 3 .57 5 .02 4 .24 4 .59 5 .87 4 .88 5 .13 4 .79 4 .10 5 .735 .86 5 .92 6 .69 3 .75 4 .75 6 .43 4 .01 5 .52 7 .06 4 .15 5 .24 5 .52 4 .405 .12 4 .91 6 .58 5 .13 3 .51 5 .41 6 .14 4 .19 5 .88 5 .39 3 .29 4 .48 6 .894 .96 5 .99 3 .79 4 .46 3 .81 5 .68 2 .82 6 .40 4 .10 4 .68 4 .80 5 .53 4 .866 .24 5 .36 4 .96 4 .67 3 .91 5 .24 4 .73 4 .91 4 .61 4 .71 4 .45 5 .52 6 .025 .56 6 .66 4 .90 4 .54 5 .01 5 .22 4 .45 4 .30 4 .02 4 .14 3 .77 5 .94 5 .152 .54 4 .03 5 .39 4 .19 4 .66 4 .27 5 .26 6 .00 5 .16 6 .27 4 .78 4 .98 6 .424 .85 4 .01 6 .64 5 .39 5 .10 5 .66 5 .31 5 .77 3 .92 4 .88 6 .02 4 .41 5 .375 .95 3 .67 5 .09 4 .17 4 .76 3 .92 4 .15 7 .35 5 .68 3 .76 3 .94 4 .60 6 .326 .99 3 .58 6 .67 4 .99 6 .95 3 .59 6 .36 2 .53 5 .68 5 .02 5 .20 5 .65 3 .664 .23 6 .63 4 .99 6 .04 4 .56 3 .45 6 .95 5 .80 4 .72 6 .33 5 .11 6 .36 4 .004 .61 4 .18 4 .80 5 .91 4 .75 5 .20 5 .04 5 .94 5 .52 3 .47 5 .42 5 .88 3 .285 .54 3 .61 3 .92 7 .08 4 .53 3 .90 4 .26 6 .66 5 .07 2 .84 6 .79 4 .50 4 .405 .20 5 .90 5 .03 4 .01 4 .59 4 .58 5 .33 4 .11 4 .12 2 .94 6 .11 3 .62 3 .986 .42 5 .98 5 .18 5 .82 4 .58 5 .49 3 .89 4 .15 3 .76 3 .62 3 .74 5 .69 6 .644 .91 4 .32 4 .75 4 .52 4 .58 4 .75 3 .61 5 .95 4 .28 3 .67 4 .46 5 .40 4 .954 .57 5 .50 3 .68 7 .02 4 .03 5 .21 4 .52 5 .72 5 .87 3 .68 3 .09 7 .01 5 .002 .68 3 .98 5 .82 5 .73 4 .55 6 .17 5 .25 5 .67 4 .17 6 .12 4 .30 6 .33 4 .936 .10 2 .97 4 .91 2 .85 5 .76 3 .72 4 .69 6 .69 4 .25 6 .10 5 .88 5 .90 6 .37

Hier das Histogramm der Stichprobe un die Dichte der Normalverteilung:


2 3 4 5 6 7 8Werte

0.00

0.05

0.10

0.15

0.20

0.25

0.30

0.35

0.40

Wah

rsch

einl

ichke

iten

usw

DichteHistogramm der Stichprobe

Das Konfidenzinvervall mit Konfidenzniveau 0,95 ist fur diese Stichprobe wie folgt:

[4.89, 5.11]

Der tatsachliche Wert von µ war gleich 5 gesetzt.

3.7 Def (χ2-Verteilung). Seien X1, . . . , Xn unabhangige standardnormalverteilteZufallsvariablen. Dann heißt die Verteilung von X2

1 + · · ·+X2n die χ2-Verteilung

mit n Freiheitsgraden.

3.8. Die Dichte w(x) der χ2-Verteilung mit hat die Form

w(x) =

xn/2−1e−x/2

2n/2Γ(n/2)x ≥ 0,

0 x < 0.

Hier ist Γ die sogenannte Gammafunktion. Fur die Gammafunktion gilt Γ(1) =1,Γ(1/2) =

√π und Γ(x + 1) = xΓ(x). Das ermoglicht die Werte Γ(n/2) fur n ∈ N

auszurechnen.

3.9 (Schatzung der Varianz der Normalverteilung). Sei X1, . . . , Xn Stichprobe auseiner Normalverteilung mit einem unbekannten Erwartungswert µ und einer unbe-kannten Varianz σ2. Die Aufgabe ist das Konfidenzinvervall fur die Varianz σ2 zueinem gegebenen Konfidenzniveau 1− α zu finden.

3.10 Thm. Seien X1, . . . , Xn iid Standardnormalverteilten Zufallsivariablen. Dannist die Zufallsvariable

n∑i=1

(Xi −X)2

χ2-verteilt mit n− 1 Freiheitsgraden.

3.11. Der Beweis des Theorems basiert auf zwei Beobachtungen

3. SCHATZUNGEN FUR NORMALVERTEILUNG 53

(a) Die Abbildung

x = (x1, . . . xn) ∈ Rn π7−−−→

(n∑i=1

(xi − x)

)i=1,...,n

∈ Rn

ist die orthogonale Projektion auf die Hyperebene x = 0.

(b) Wenn man den Vektor (X1, . . . , Xn) aus iid Standardnormalverteilten Zufalls-variablen ‘dreht’ (d.h., zum Vektor wird eine Orthogonaltransformation ange-wandt), bekommt man wieder einen Vektor aus iid StandardnormalverteiltenZufallsvariablen.

3.12 (Losung der Schatzaufgabe 3.9). Zur Schatzung von σ2 verwenden wir denSchatzer

S2 =1

n− 1

n∑i=1

(Xi −X)2.

(Es kann berechnet werden, dass E(S2) = σ2 gilt.) Aus der Xi erhalt man die Stan-dardnormverteilte Zufallsvariable

Xi − µσ

.

Wenn man den Mittelwert dieser n Standardverteilten Zufallsvariablen bildet, erhaltman

1

n

n∑i=1

Xi − µσ

=X − µσ

Wenn man fur diese Standardnormalverteilten Zufallsvariablen (und ihre Mittelwert)Theorem 3.10 anwendet, erhalt man, dass

n∑i=1

(Xi − µσ

− X − µσ

)2

=1

σ2

n∑i=1

(Xi −X)2 =(n− 1)

σS2

eine χ2-verteilte Zufallsvariable mit n− 1 Freiheitsgraden ist. Sei F die Verteilungs-funktion der χ2-Verteilung. Sei a das α/2-Quantil und b das (1 − α/2)-Quantil derχ2-Verteilung mit n− 1 Freiheitsgraden. Das heißt, F (a) = α/2 und F (b) = 1− α/2oder mit anderen Worten

a = F−1(α/2),

b = F−1(1− α/2).

Es folgt

P

(a ≤ (n− 1)S2

σ≤ b

)= F (b)− F (a) = 1− α.

Um das Konfidenzinvervall fur σ auszurechnen, reicht es nun die Ungleichungen

a ≤ (n− 1)S2

σ2≤ b


nach σ aufzulosen. Man hat

(n− 1)S2

b≤ σ2 ≤ (n− 1)S2

a

oder etwas expliziter(n− 1)S2

F−1(1− α/2)≤ σ2 ≤ (n− 1)S2

F−1(α/2)

Das Konfidenzinvervall fur σ2 ist also[(n− 1)S2

F−1(1− α/2),(n− 1)S2

F−1(α/2)

].

3.13. In OpenOffice calc kann die Verteilungsfunktion der χ2-Verteilung und ihreinverse Funktion mit Hilfe der Funktionen

CHIVERT(x; k)

und

CHIINV(p; k)

ausgerechnet werden (Warnung: man musste genauer nachlesen, wie diese Funktionenin OpenOffice definiert ist).

3.14 (χ2-Verteilung in Python). Beschreibung unter: https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.chi2.html Bibliotheken:

from s c ipy . s t a t s import ch i2import matp lo t l i b . pyplot as p l timport numpy as np

Verteilungsfunktion:

my cdf=lambda x : ch i2 . cd f (x , df=5)x=np . l i n s p a c e (−5 ,5 ,100)p l t . p l o t (x ,map(my cdf , x ) )p l t . show ( )

Inverse Verteilungsfunktion.

my ppf=lambda p : ch i2 . ppf (p , df=5)p=np . l i n s p a c e ( 0 . 0 5 , 0 . 9 5 , 1 0 0 )p l t . p l o t (p ,map(my ppf , p ) )p l t . show ( )

4 Lineare Regression

4.1 (Approximation eines Zufallsvariable durch einen reellen Wert). Zuerst beschaftigenwir uns mit der folgenden Hilfsfrage: welcher Wert aus R approximiert eine gegebeneZufallsvariable X am besten? Ist das der Erwartungswert E(X)? Um die Frage exaktbeantworten zu konnen, mussen wir festlegen, wie wir die Qualitat der Approximati-on messen mochten. In diesem Abschnitt messen wir die Qualitat der Approximationvon X durch b ∈ R mit dem Wert

q(b) := E((X − b)2).

https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.chi2.html

https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.chi2.html

4. LINEARE REGRESSION 55

Unsere Aufgabe ist somit, eine optimale Losung der Minimierungsaufgabe

min q(b) : b ∈ R

zu bestimmen. q(b) ist eine quadratische Funktion in b. Aus der zweiten binomischenFormel fur (X − b)2 und der Lineritat von E konnen wir ohne Probleme die expliziteDarstellung von q(b) ermitteln:

q(b) = E(X2)− 2bE(X) + b2.

Die Funktion ist an der Stelle b mit q′(b) = 0 minimal, also fur b = E(X). Somitist der Erwartungswert b = E(X) die beste Approximation von X bzgl. des Appro-ximationsmaßes q(b). Daruber hinaus ist q(b) fur b = E(X) die Varianz V (X) vonX. Das heißt, V (X) beschreibt, wie gut man X durch einen reellen Wert b bzgl. desApproximationsmaßes q(b) approximieren kann.

4.2 (Herleitung der linearen Regression). Seien X, Y zwei Zufallsvariablen. UnserZiel ist Y mit Hilfe des Ausdrucks der Form aX + b mit a, b ∈ R zu approximieren.Analog zu 4.1 messen wir die Qualitat der Approximation durch den Erwartungs-wert des Quadrats der Differenz. In diesem Fall wird eine Zufallsvariable nicht durcheinen reellen Wert approximiert sondern durch einen lineare Funktion einer anderenZufallsvariablen. Wir wollen also a, b ∈ R so wahlen, dass der Ausdruck

E((Y − aX − b)2)

am kleinsten ist. Das heißt, wir beschaftigen uns mit der Minimierungsaufgabe

minE((Y − aX − b)2) : a, b ∈ R

Wenn wir a beliebig festlegen, so wissen wir bereits aus 4.1, wie man b am besten

wahlt, und zwarb = E(Y − aX) = E(Y )− aE(X).

Also konnen wir das beste b gleich einsetzen und erhalten die Aufgabe der Minimie-rung von

E((Y − aX − E(Y ) + aE(X))2) = E

(((Y − E(Y )︸︷︷︸

=:Y0

)− a(X − E(X)︸︷︷︸

=:X0

))2)

= E((Y0 − aX0)2)

fur a ∈ R. Die Zielfunktion ist quadratisch in a, denn mit Hilfe der zweiten bi-nomischen Formel und mit Berucksichtigung der Linearitat von E kann die vorigeZielfunktion als

E((Y0 − aX0)2) = E(Y 20 )− 2aE(Y0X0) + a2E((X2

0 )

= V (Y )− 2aCov(X, Y ) + a2V (X)

dargestellt werden. Die Funktion erreicht ihr Minimum genau dann, wenn man

a =Cov(X, Y )

V (Y )


setzt. Jetzt konnen wir die Approximation von Y explizit hinschreiben. Die Zufalls-variable Y − E(Y ) wird durch

Cov(X, Y )

V (Y )(X − E(X))

approximiert. Das bedeutet, dass wir Y durch die Zufallsvariable

Y := E(Y ) +Cov(X, Y )

V (X)(X − E(X))

Diese Formel wird durch den Ubergang zu Standardisierten Zufallsvariablen

X∗ :=X − E(X)√

V (X),

und der Korrelation besonders einleuchtend:

Y = E(Y ) + Cor(X, Y )√V (Y )X∗. (II.2)

Wir sehen hier das Folgende. Wenn wir Y approximieren wollen, dann nehmen wirzuerst E(Y ) aus den ‘Ausgangswert’. Dann wird dieser Wert additiv mit Hilfe vonX korrigiert. Wenn X und Y unkorreliert sind, das heißt Cor(X, Y ) = 0, dann tragtX zur Korrektur gar nicht bei, und man bleibt bei der Approximation von Y mitdem festen Wert E(Y ). Je hoher der Betrag von Cor(X, Y ) ist, desto großer ist derBeitrag von X bei der Approximation von Y . Der Faktor Man merke noch, dass der√V (Y ) aus der Zufallsvariablen X∗ mit der Varianz 1, eine Zufallsvariablen mit der

Varianz V (Y ) (als der selben Varianz wie bei Y ) macht.

4.3 (Qualitat der Approximation durch lineare Regression). Wie gut wird Y durch

Y approximiert? Aus (II.2) erhalten wir

E((Y − Y )2) = E((√V (Y )Y ∗ − Cor(X, Y )

√V (Y )X∗)2)

= V (Y )E((Y ∗ − Cor(X, Y )X∗)2)

= V (Y )(1− 2 Cor(X, Y ) Cor(X∗, Y ∗) + Cor(X, Y )2)

= V (Y )(1− 2 Cor(X, Y )2 + Cor(X, Y )2)

= V (Y )(1− Cor(X, Y )2).

Die Qualitat der Approximation hangt logischerweise von V (Y ) ab, da die Qualitatder Approximation von der Großenordnung der ‘Schwankungen’ von Y abhangig ist.Das erklart den Faktor V (Y ) in der Formel fur den Fehler

E((Y − Y )2) = V (Y )(1− Cor(X, Y )2),

die wir oben erhalten haben. Anderseits hangt die Qualitat der Approximation vonder Korrelation von X und Y folgendermaßen ab: Je naher der Betrag der Korrelationzu 1 ist, desto besser ist die Approximation. Be unkorrelierten X und Y ist der Fehlereinfach nur die Varianz von Y . Bei Cor(X, Y ) = ±1 sind X und Y die gleiche Großebis auf lineare Transformationen und der Fehler ist gleich 0.

4. LINEARE REGRESSION 57

4.4 (Empirische Korrelation und Kovarianz). Im Kontext der Statistik wurde mandavon ausgehen, dass man die Werte E(Y ), V (E),Cor(X, Y ), die man zur Berechnungder linearen Regression benotigt, nicht direkt zur Verfugung hat. Stattdessen hat maneine Stichprobe (X1, Y1), . . . , (Xn, Yn) aus n unabhangigen Beobachtungen der Paareder beiden zufalligen Großen. Zur Berechnung der Abschatzung der Varianz, Kova-rianz und Korrelation benutzt man die sogenannten empirischen Varianz, Kovarianzund Korrelation (sie werden auch Stichprobenvarianz, -Kovarianz und -Korrelationgenannt). Sie basieren auf den Funktionen

s(x) :=

√√√√ 1

n− 1

n∑i=1

(xi − x)2

s(x, y) :=1

n− 1

n∑i=1

(xi − x)(yi − y)

r(x, y) =s(x, y)

s(x)s(y).

mit

x = (x1, . . . , xn), y = (y1, . . . , yn) ∈ Rn

s(x)2 ergibt die Stichprobenvarianz, s(x, y) die Stichprobenkovarianz und r(x, y) dieStichprobenkorrelation.

4.5 Bsp. Die lineare Regression fur die Daten

xi 1.5 3 4 1.5 1.5 0 4 4yi 5 1 6 1.5 5 5.5 6 1.5

sieht so aus:

0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0

1

2

3

4

5

6

4.6 Bsp. Lineare Regression fur die Daten

xi 1 2 4 5 7 8yi 1 2 5 5 6 7

ist


1 2 3 4 5 6 7 8

1

2

3

4

5

6

7

4.7 (Anwendungsmoglichkeit). Es gibt zahlreiche Anwendungsmoglichkeit (das The-ma ist in Data Science sehr popular). Fur Programmierung gibt es Software die denZusammenhang der folgenden Zufallsvaraiblen analysiert: x die vom Programmiergeschatzte Bearbeitungszeit fur ein Teilprojekt und y die tatsachliche Bearbeitungs-zeit. Es ist interessant den Zusammenhang zwischen x und y zu analyiseren um dieSchlusse zu ziehen, wie: in der Regel unterschatzt der Programmierer die Bearbei-tungszeit um Faktor 4. Wenn er also sagt, er braucht 1 Tag, braucht er meistens 4(also, reservieren wir 4 Tage).

4.8 (Lineare Regression und Euklidische Raume). Zufallsvariablen X und Y sindVektoren aus einem Vektorraum von Zufallsvariablen. Somit kann E(XY ) als Ska-laprodukt der Vektoren X und Y interpretiert werden. Mit dieser Interpretation istder Term Cov(X,Y )

V (Y )X0 in der linearen Regression die orthogonale Projektion von Y0

auf die Gerade durch 0 und X0. Das heißt, Y0 wird durch die Projektion Cov(X,Y )V (Y )

X0

approximiert un, dem entsprechend Y durch E(Y ) + Cov(X,Y )V (Y )

X0.

0

Y0

X0

Cov(X,Y )V (Y )

X0

5 Ausblick

5.1. Literatur zur Statistik.

TODO: Literaturliste befindet sich im Aufbau

Das Buch von Szekely [Sze90] enthalt auch Beispiele zur Statistik.

5.2. Weitere Themen:

5. AUSBLICK 59

(a) Histogramme (da ist nicht viel zu diskutieren).

(b) Maximum-Likelihood-Methode (eine allgemeine Methode der Parameterschatzung).

(c) Multidimensionale Regression (Verallgemeinerung der linearen Regression aufden Fall, in dem Y und X zufallige Vektoren sind, d.h., Y = (Y1, . . . , Xd) undX = (X1, . . . , Xk), wobei Y1, . . . , Yd, X1, . . . , Xk Zufallsvariablen sind).


Kapitel III

Numerische Mathematik

Berechnungen mit Gleitkommazahlen (d.h., Eingabe mit Approximationsfehlern). Eswerden numerische Verfahren, ihre Effizienz und die Approximationsegenschaften dis-kutiert. Wir behandelt die Polynominterpolation, numerische Losung linearer Glei-chungssystemen, Faktorisierungen von Matrizen und numerische Losung nichtlinearerGleichungen,

1 Interpolation

1.1 (Interpolationsaufgabe). Man erhalt n paarweise verschiedene Werte x1, . . . , xn ∈R und beliebige Werte y1, . . . , yn ∈ R. Das sind die Interpolationsdaten.

(a) Die Werte x1, . . . , xn heißen die Stutzstellen

(b) Die Werte y1, . . . , yn heißen Stutzwerte.

(c) Die Paare (x1, y1), . . . , (xn, yn) heißen Datenpunkte oder Stutzpunkte.

Sonst ist eine Menge Fn von Funktionen von R nach R vorgegeben. Gesucht wird eineFunktion f ∈ Fn, welche die Interpolationsbedingung

f(xi) = yi (i ∈ 1, . . . , n)

erfullt. Art der Interpolation hangt ist durch die Wahl von Fn festgelegt. uns aus-schließlich mit der Polynominterpolation. Bei der sogenannten Polynominterpolationist Fn die Menge aller Polynome vom Grad hochstens n− 1 (dies ist ein Vektorraumuber R der Dimension n).

1.2. Man kann auch allgemeiner Polynominterpolation bzgl. eines allgemeines KorpersK an der Stelle von R behandeln. Polynominterpolation bzgl endlicher Korper undbzgl. des Korpers komplexer Zahlen habe interessante Anwendungen.

1.3 (Anwendungsmoglichkeiten). (a) Man hat mit einer unbekannte Funktion zutun, deren Auswertung teuer ist (kostet Zeit, oder man man ein aufwandigesExperiment durchfuhren, um den Wert an einer Stelle zu ermitteln). Man kannversuchen, die Funktion an einigen Stellen zu ermitteln, und die Werte an an-deren Stellen durch Interpolation zu ‘raten’.

61

62 KAPITEL III. NUMERISCHE MATHEMATIK

(b) Durch Interpolation der Umkehrfunktion kann man nichtlineare Gleichungenannahernd losen.

(c) Die bekannte Fourier-Transformation ist eine Transformation, die eine spe-zielle Interpolationsaufgabe lost (der zugrundeliegender Korper ist in diesemFall nicht R wie bei uns sondern der Korper der komplexen Zahlen). Fourier-Transformationen und ihre Analoga werden in verschiedenen Kontexten be-nutzt, etwa

• Bild- und Audioverarbeitung

• Losung von Differentialgleichungen

• Schnelle Multiplikation von Polynomen

• Schnelle Multiplikation ganzer Zahlen

(d) In Codierungstheorie benutzt man Interpolation um Codes zu erstellen (derzugrundeliegender Korper ist nicht R wie bei uns sondern ein endlicher Korper).

1.4 Thm. Seien x1, . . . , xn ∈ R paarweise verschiedene Wert und y1, . . . , yn ∈ R.Dann existiert ein eindeutiges Polynom f vom Grad hochstens n−1 mit f(xi) = yifur alle i ∈ 1, . . . , n.

1.5. In dem Theorem wird die Existenz und die Eindeutigkeit behauptet.

(a) Die Existenz kann man durch Angabe einer expliziten Formel fur f zeigen (einesolche Formel werden wir unten geben).

(b) Zur Eindeutigkeit: wenn zwei verschiedene Polynome p und q vom Grad hochstensn− 1 an n Stellen gleich sind, dann ist das Polynom p− q, das ebenfalls Gradhochstens n − 1 hat, an diesen n Stellen gleich 0. Ein Nichtnullpolynom vomGrad hochstens n− 1 hat aber hochstens n− 1 Nullstellen. Daher gilt p = q.

1.6. Will man das Interpolationspolynom ohne Zusatztheorie berechnen so kann mandie Interpolationsaufgabe direkt mit Hilfe der linearen Algebra losen. Die Bedingun-gen f(xi) = yi sind n lineare Gleichungen in n unbekannten Koeffizienten von f . Wirerhalten also ein lineares System mit n Gleichungen in n Unbekannten. Die Theorie(Theorem 1.4) garantiert uns, dass dieses System eine eindeutige Losung hat.

1.7 Bsp. Wir berechnen das Interpolationspolynom fur

xi 1 2 3 5yi 2 3 4 7

mit linearer Algebra. Wir schreiben das Polynom in der Form

f(x) = ax3 + bx2 + cx+ d

1. INTERPOLATION 63

mit unbekannten Koeffizienten a, b, c, d ∈ R. Die Bedingungen f(1) = 2, f(2) =3, f(3) = 4, f(5) = 7 werden dementsprechend als das lineare System

13 12 11 10

23 22 21 20

33 32 31 30

53 52 51 50

abcd

=

2347

formuliert. Etwas expliziter:

a+ b+ c+ d = 2

8a+ 4b+ 2c+ d = 3

27a+ 9b+ 3c+ d = 4

125a+ 25b+ 5c+ d = 7

1 2 3 5

2

3

7

4

Im allgemeinem Fall lost man das lineare Gleichungssystemxn−11 · · · x0

1...

......

xn−1n · · · x0

n

︸︷︷︸

=:V

pn−1...p0

=

y1...yn

︸︷︷︸

y

in unbekannten Koeffizienten pn−1, . . . , p0 mit p(x) = pn−1xn−1 + · · · + p1x + p0 des

Polynoms p(x).

1.8 Bsp. Die Polynominterpolation durch die Losung eines linearen Gleichungssy-stems (wie oben beschrieben) ist im Fall von numerisch gegebenen Daten (Gleitkom-mazahlen) nicht empfehlenswert, da die Matrix des Systems schlecht kondizioniert ist.Schlecht kondizioniert heißt: kleine Fehler in der Eingabe fuhren zu großen Fehlernin der Ruckgabe.


1.9 (Das Interpolationspolynom in der Lagrange-Form). Betrachten wir fur ein i ∈1, . . . , n, das Polynom ∏

j∈1,...,n\i

(x− xj).

Dieses Polynom hat Grad n− 1 und ist auf allen Stellen x1, . . . , xn bis auf die Stellexi gleich 0. Wenn wir nun das vorige Polynom durch seinen Wert an der Stelle xiteilen, so erhalten wir das Polynom

pi(x) =∏

j∈1,...,n\i

x− xjxi − xj

.

Das Polynom pi(x) ist an der i-ten Stutzstelle gleich 1 und allen anderen Stutzstellengleich 0. Es ist nun klar, dass das Polynom

p(x) = y1p1(x) + · · ·+ ynpn(x)

Denn man hat p(xi) = y1p1(xi) + · · · + ynp(xn), wobei auf der rechten Seite dieserGleichung nur der Term yipi(xi) = yi ungleich null ist. Die Darstellung des Inter-polationspolynoms als Linearkombination der Polynome p1(x), . . . , pn(x) heißt dieLagrange-Form.

1.10 Bsp. Im Fall n = 2 hat das Interpolationspolynom eine besonders einfacheForm:

p(x) = y1x2 − xx2 − x1

+ y2x− x1

x2 − x1

.

Man sieht direkt, dass p(x1) = y1 und p(x2) = y2 gilt.

1.11 Bsp. Berechnen wir das Interpolationspolynom fur n = 3 und die Stutzstellen−1, 0, 1. Die Werte an den Stutstellen 0,±1 bezeichnen wir als y0, y1 und y−1 undden Wert an der Stutzstelle 0 als y0. Das Polynom 1−x2 ist gleich 0 an ±1 und gleich1 an der Stelle 0. Das polynom 1

2x(1 − x) ist gleich 1 an der Stelle −1 und gleich 0

an den Stelle 0 und 1. Das Polynom 12x(x+ 1) ist gleich 1 an der Stelle 1 und gleich

0 an den Stellen 0 und −1. Ergibt sich die Formel:

p(x) = y−11

2x(x+ 1) + y0(1− x2) + y1

1

2x(1− x).

1.12 Def. Als Flop, engl. floating point operation, bezeichnet man eine Grund-operation (plus, minus,mal, geteilt) auf Gleitkommazahlen.

1.13 (Laufzeit der Verfahren der Polynominterpolation). Die Effizienz eines Inter-polationsverfahrens bei der Polynominterpolation setzt sich aus den folgenden zweiAufgaben zusammen:

(a) Berechnung einer Darstellung des Polynoms. Es wird eine Basis f1(x), . . . , fn(x)im Vektorraum der Polynome vom Grad hochstens n − 1 festgelegt. Gesuchtwerden die Koeffizienten c1, . . . , cn ∈ R, fur welche das Polynom c1f1(x) + · · ·+cnfn(x) die Interpolationsaufgabe erfullt.

1. INTERPOLATION 65

• Eine mogliche Basis ist die Basis x0, . . . , xn−1 aller Monome vom Gradhochstens n− 1.

• Eine weitere mogliche Basis ist die Lagrange-Basis p1, . . . , pn aus 1.9.

• Im Folgenden werden wir noch die Newton-Basis einfuhren.

(b) Die Auswertung des Polynoms anhand der festgelegten Darstellung.

TODO: Stichworter: Parker-Traub-Algorithmus mit n2 flops.

Man hat sich die ... ergeben sich durch ein besonderen Gleichungssystems. Wird imworst case durch Gauß mit n3 flops losbar. Durch . (Wahrscheinlich hat Parker-Traubwas mit der Newton-Form zu tun.) Sobald die Koeffizienten bestimmt sind, geht dasAuswerten durch n flops (Horner-Schema).

1.14 (Horner-Schema). Bei einem Polynom, das als lineare Kombination der Monomexn−1, . . . , x0 beschrieben ist, kann das sogenannte Horner-Schema zur Auswertungdes Polynoms benutzen. Z.B., bei einem quadratischen Polynom wurde man in zweiIterationen so auswerten:

p(x) = ax2 + bx+ c = (ax+ b)︸︷︷︸1.

x+ c

︸︷︷︸2.

Bei einem kubischen Polynom wurde man in drei Iteration so auswerten:

p(x) = ax3 + bx2 + cx+ d = ((ax+ b)︸︷︷︸1.

x+ c

︸︷︷︸2.

)x+ d

︸︷︷︸3.

Allgemein ist die Anzahl Iterationen gleich dem Grad des Polynoms, wobei man proIteration 2 Flops verbraucht (eine Multiplikation und Addition von Gleitkommazah-len). Man kommt also bei einem Polynom vom Grad n − 1 auf n − 1 Gleitkomma-Multiplikationen und n− 1 Gleitkomma-Additionen.

1.15 (Fehlerschatzung). Der Fehler wird im Wesentlichen so geschatzt, wie man dieTaylorformel herleitet. In den beiden Fallen ist der Satz von Rolle das Werkzeug(vgl. Analysis).

1.16 Thm (Fehlerschatzung bei Polynominterpolation). Sei f : U → R eine nMal stetig differenzierbare Funktion auf einer offenen Teilmengen U von R, seiena, b ∈ U mit a < b und sei [a, b] ⊆ U . Wir setzen

Mn := maxx∈[a,b]

|f (n)(x)|.

Man betrachte paarweise verschiedene Stutzstellen x1, . . . , xn ∈ [a, b] und das In-terpolationspolynom p bzgl. dieser Stutzstellen mit p(xi) = f(xi) fur alle i ∈1, . . . , n. Dann gilt fur der Fehler der Approximation von f(x) mit p(x) die


Abschatzung

|f(x)− p(x)| ≤ Mn

n!|ωn(x)| (x ∈ [a, b])

mit

ωn(x) =n∏i=1

(x− xi).

1.17. Eigentlich zeigt der Beweis von Theorem 1.16 etwas mehr als die prasentierteAbschatzung. Und zwar existiert fur jedes x ∈ [a, b] ein ξx ∈ [a, b] mit

f(x)− p(x) =f (n)(ξx)

n!ωn(x).

Wenn also z.B. der Betrag der n-ten Ableitung von f auf [a, b] zwischen zwei Konstan-ten c1 und c2 liegt, mit 0 < c1 < c2, so liegt der Fehler der Approximation zwischenc1n!|ωn(x)| und c2

n!|ωn(x)|. In diesem Fall beschreibt |ωn(x)| im Wesentlichen wie groß

der Fehler der Approximation an einer gegebenen Stelle x ist. Hier ein Plot von ωn(x)im Fall von n equidistanten Stutzstellen.

0 1 2 3 4 5 6 7 8 942896

0

6553

omega_n(x)

1.18. Bei der Approximation einer Funktion f durch ein Polynom p mit Hilfe derPolynominterpolation (wie in Theorem 1.16) soll man Folgendes beachten: Ist Mn

groß oder f nicht n Mal stetig differenzierbar, so kann keine gute Approximationgarantiert werden. Man findet auch Beispiele, bei denen die Approximation schlechtist.

1.19 Bsp. Aus Bemerkung 1.18 folgt, dass fur große n die Polynominterpolation bzgl.der leichten Anderung der Werte y1, . . . , yn instabil ist. Denn man kann eine Funktionf durch eine Funktion mit betragsmaßig kleinen Werten und großen Ableitungenleicht storen. Die Werte von f an den fixierten Stutzstellen andern sich nur leicht, das

1. INTERPOLATION 67

Interpolationspolynom kann sich aber enorm andern. In diesem Beispiel werden an 20Stutzstellen 0, . . . , 19 zufallige Werte y0, . . . , y19 im Bereich 0 bis 0,1 vorgeschrieben:

xi yi0 0.0009326807318088221 0.08017604499992572 0.03426231672325663 0.01596232916682904 0.02823093988629335 0.05118063316065666 0.04569201266618407 0.04344720770214938 0.06780807339557479 0.0452027599610055

10 0.061090166336238411 0.016933371603808312 0.098322208959438313 0.053450213033472914 0.018935993962014515 0.073535666939683816 0.028518511227760917 0.014295295619205918 0.081653407145958419 0.0180722551596312

Obwohl die Werte an den Stutzstellen klein sind, nimmt das Interpolationspoly-nom im Bereich von 0 bis 19 auch recht große Werte an:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

72

0

84 InterpolationspolynomStuetzpunkte

1.20 Bsp. An diesem Beispiel sieht man, dass die Approximation der Betragsfunktion|x| durch ein Interpolationspolynom schlecht ist. Dies wird durch die Tatsache erklart,dass die Betragsfunktion nicht stetig differenzierbar ist.


0 1 2 3 4 525 4 3 1

00

5 Interpolationspolynom fuer |x||x|Stuetzpunkte

1.21 Bsp. Berechnen Sie das Maximum von |ωn(x)| auf [a, b] in den Fallen

(a) n = 2 mit x1 = a und x2 = b

(b) n = 3 mit x1 = a, x2 = (a+ b)/2, x3 = b.

Diese Abschatzungen konnen zur Abschatzung der Qualitat bei einer stuckweise li-neare und stuckweise quadratischen Approximation einer Funktion benutzt werden.

TODO: im Aufbau

1.22 (Eine Rekursion fur Interpolationspolynome). Bezeichen wir fur 1 ≤ i ≤ j ≤ nals pi,j(x) das Interpolationspolynom fur bzgl. der Stutzpunkte (xi, yi), . . . , (xj, yj).Fur i = j haben wir offensichtlich pi,j(x) = yi. Es stellt sich heraus, dass fur dasInterpolationspolynom pi,j(x) mit i < j die folgende rekursive Gleichung erfullt ist:

pi,j(x) =(xj − x)pi,j−1(x) + (x− xi)pi+1,j(x)

xj − xi(III.1)

erfullt ist. Die rechte Seite ist eine Linearkombination der Polynome pi,j−1 und pi+1,j,welche Interpolationsaufgabe den stark uberlappenden Mengen der Stutzpunkte xi, . . . , xj−1und xi+1, . . . , xj losen. Das heißt, die beiden Interpolationspolynome haben j−i−1Stuzpunkte gemeinsam, und jedes der beiden Polynome hat einen Stutzpunkt, dasdas andere Polynom nicht hat. Wenn wir ein xk mit i < k < j einsetzen, so werdendie beiden Interpolationspolynome auf der rechten Seite zu yk ausgewertet, sodass dierechte Seite zu yk ausgewertet wird. Fur x = xi wird das Polynom pi+1,j(x) auf derrechten Seite durch seinen Vorfaktor ‘ausgeschaltet’, und man erhalt pi,j−1(xi) = yibei der Auswertung der rechten Seite. Analog wird fur x = xj die rechte Seite zu yjausgewertet, weil bei der Auswertung der rechten Seite an dieser Stelle das Polynompi,j−1(x) durch den Vorfaktor xj − x ‘ausgeschaltet wird.

1. INTERPOLATION 69

1.23 (Neville-Algorithmus). Die rekursive Relation (III.1) konnte man direkt zurAuswertung oder Bestimmung des Interpolationspolynoms an einer gegeben Stellebenutzten. So eine rekursive Umsetzung ware aber zu teuer, und zwar wurde einerAuswertung eines Interpolationspolynoms zu n Stutzpunkten O(2n) Flops kosten.Stattdessen kann man auf (III.1) basierend den folgenden iterativen Algorithmusaufbauen:

Start: Setze pi,i := yi fur alle i ∈ 1, . . . , n.

Iteration: Fur s von 1 bis n − 1, werte alle pi,j mit j − i = s mit Hilfe von (III.1) ausund hebe die Werte auf. (Die rechte Seite kann direkt ausgewertet werden weilpi,j−1 und pi+1,j bereits zur Verfugung stehen.)

Hier eine Illustration fur n = 5. Man arbeitet in dem unten angegebenen Diagrammdie vertikalen Schichten von links nach rechts ab. Die letzte Schicht aus einem einzigenPolynom ist das Ergebnis. Die Polynome der ersten Schicht sind die Konstantenpi,i = yi. Die Polynome aller anderen Schichten ergeben sich aus je zwei Nachbarnder vorigen Schicht.

p1,1

p1,2

p2,2 p1,3

p2,3 p1,4

p3,3 p2,4 p1,5

p3,4 p2,5

p4,4 p3,5

p4,5

p5,5

1.24 Def. Die dividierten Differenzen bzgl. der Stutzpunkte (x1, y1), . . . , (xn, yn)sind eine Art diskrete Versionen der Ableitungen verschiedener Ordnungen, diefolgendermaßen eingefuhrt werden: Man legt die dividierte Differenz [xi] der Ord-nung 0 bzgl. eines Stutzpunkts (xi, yi) durch [xi] = yi fest. Fur 1 ≤ i < j ≤ nwird die dividierte Differenz [xi, . . . , xj] der Ordnung j − i rekursiv als

[xi, . . . , xj] =[xi, . . . , xj−1]− [xi+1, . . . , xj]

xi − xj

festgelegt. (Eine dividierte Differenz der Ordnung k ist ein diskretes Analagonder k-ten Ableitung.)

1.25 (Interpolationspolynom in der Newton-Form). Es stellt sich heraus, dass fur dasInterpolationspolynom p die folgende Darstellung gilt:

p(x) = [x1] + [x1, x2](x− x1) + · · ·+ [x1, . . . , xn](x− x1) · . . . · (x− xn−1).

Diese Darstellung nennt man die Newton-Form des Interpolationspolynoms. Um dieseDarstellung zu ermitteln benotigt man die dividierten Differenzen [x1, . . . , xi] mit


i ∈ 1, . . . , n. Die dividierten Differenz konnen iterativ auf der Basis der Idee desNeville-Algorithmus ermittelt werden. Hier die schematische Darstellung fur den Falln = 5:

[x1][x1, x2]

[x2] [x1, x2, x3][x2, x3] [x1, x2, x3, x4]

[x3] [x2, x3, x4] [x1, x2, x3, x4, x5][x3, x4] [x2, x3, x4, x5]

[x4] [x3, x4, x5][x4, x5]

[x5]

Wie im Neville-Algorithmus werden auch hier die vertikalen Schichten der divi-dierten Differenzen von links nach rechts abgearbeitet. Fur das oben prasentierteDarstellung in in Newton-Form benotigt man die obersten Elemente der vertikalenSchichten.

1.26 (Lineare und Nichtlineare Interpolation). Die von uns behandelte Polynominter-polation ist ein Beispiel der linearen Interpolation. Das heißt, das gesuchte Polynomist vom Vektor (y1, . . . , yn) der Stutzwerte linear abhangig. Bei einer nichtlinearenInterpolation ist diese Eigenschaft nicht gegeben. Nichtlineare Interpolation kann an-hand der Polynomfunktion und einer bijektiven nichtlinearen Funktion φ folgederma-ßen durchgefuhrt werden. Man findet das Interpolationspolynom p(x) fur Stutzpunkte(x1, φ(y1)), . . . , (xn, φ(yn)) und benutzt anschließend die Funktion φ−1(p(x)) als nicht-lineare Interpolationsfunktion fur die Stutzpunkte (x1, y1), . . . , (xn, yn).

1.27 (Iterpolation periodischer Funktionen). Wenn wir eine periodische Funktioninterpolieren wollen, eignen sich trigonometrische Polynome logischerweise besserals Polynome. Interessenterweise lasst sich die Interpolation periodischer Funktio-nen durch trigonometrische Polynome als Polynominterpolation bzgl. des KorpersC komplexer Zahlen interpretieren. Dafur braucht man lediglich die Euler-Formeleix = cosx+ i sinx (mit i =

√−1).

1.28 (Losung von Gleichungen mit Hilfe der Interpolation). Wenn wir Gleichungenvom Typ f(x) = y in einer Unbekannten x ∈ R und fur ein gegebenes y ∈ Rlosen wollen, so konnen wir ein Interpolationspolynom q(y) fur passend Stutzpunkte(f(x1), x1), . . . , (f(xn), xn) fur passend gewahlte x1, . . . , xn benutzen. Diese Methodenkann auch dann angewendet werden, wenn die Auswertung von f sehr teuer ist undman lediglich eine feste Anzahl der Auswertungen von f durchfuhren will oder wenndie Werte von f nicht fur alle x ausgewertet werden konnen.

2 Numerische Integration

2.1 Def. Die Numerische Itegration ist die Aufgabe der Approximation der In-tegrals

∫ baf(x)dx einer Funktion f fur gegebene a, b.

2. NUMERISCHE INTEGRATION 71

2.2 (Anwendungen der numerischen Integration). Numerische Integration benotigtman (unter anderem) in folgenden Situationen:

(a) Nicht jedes bestimmte Integral kann symbolisch ausgewertet werden. Zum Bei-spiel ist die Stammfunktion von e−x

2keine elementare Funktion, sodass man

fur das bestimmte Integral ∫ b

a

e−x2

dx

keine abgeschlossene Formel in a und b herleiten kann. Alternativ kann manbei gegebenen a und b eine numerische Approximation dieses Integrals mit zuermitteln.

(b) In praktischen Anwendungen hat man Situationen, in denen die integrierteFunktion f(x) nicht explizit gegeben ist (sondern durch einen Algorithmus,der f an einer gegebene Stelle auswerten oder durch Angabe der Werte an einerAuswahl von Stutzpunkten).

(c) Numerische Integration ist ein Hilfsmittel zur Losung weiterfuhrender Aufgabender numerischen Mathematik, wie z.B. Losung von Anfangswertproblemen undRandwertproblemen, Integralgleichungen, Steuerungsproblemen usw.

2.3 (Mittelpunktsregel). Seien a, b ∈ R mit a < b und sei f eine Funktion die auf[a, b] definiert und stetig ist. Die Mittelpunkte Regel approximiert das Integral

I(f) :=

∫ b

a

f(x)dx

durch den Wert

S(f) := (b− a)f

(a+ b

2

)Wir schatzen den Fehler der Approximation in Abhangigkeit von der Lange h = b−avon [a, b] ab fur h → 0. Dabei wird vorausgesetzt, dass f ausreichend oft stetigdifferenzierbar ist. Wir setzen ohne Beschrankung der Allgemeinheit voraussetzen,dass 0 der Mittelpunkt von [a, b] ist, d.h., a = −h/2 und b = h/2. Nun benutzen wirdie Taylor-Entwicklung an der Stelle 0:

f(x) = f(0) + f ′(0)x+1

2f ′′(ξx)x

2,

wobei hier ξx ein Wert zwischen 0 und x ist. Somit gilt die Abschatzung

|f(x)− f(0)− f ′(0)x| ≤ 1

2M2x

2

mit

M2 := maxx∈[a,b]

|f ′′(x)|


unter der Voraussetzung, dass f(x) auf [a, b] zweimal stetig differenzierbar ist. Dasergibt

|I(f)− S(f)| =

∣∣∣∣∣∫ h/2

−h/2(f(x)− f(0))dx

∣∣∣∣∣=

∣∣∣∣∣∫ h/2

−h/2(f(x)− f(0)− f ′(0)x)dx

∣∣∣∣∣≤∫ h/2

−h/2|f(x)− f(0)− f ′(0)x|dx

≤ 1

2M2

∫ h/2

−h/2x2dx

=M2

24h3.

Wir haben also die Abschatzung:∣∣∣∣∫ b

a

f(x)dx− (b− a)f

(a+ b

2

)∣∣∣∣ ≤ M2

24(b− a)3.

2.4 (Trapezregel). Das Integral I(f) wird durch

S(f) =f(a) + f(b)

2(b− a)

approximiert. Gilt f(a), f(b) > 0, so ist S(f) der Flacheninhalt vom Trapez mit denEcken (a, 0), (a, f(a)), (b, f(b)), (b, 0) (was den Namen der Regel erklart).

Der Wert S(f) ist das Integral∫ bap(x)dx fur das Interpolationspolynom

p(x) = f(a)x− ab− a

+ f(b)b− xb− a

zu Stutzpunkten (a, f(a)), (b, f(b)). Aus Theorem 1.16 folgt nun

|I(f)− S(f)| ≤∫ b

a

|f(x)− p(x)|dx =M2

2

∫ b

a

|ω2(x)|dx,

Hier ist |ω2(x)| = |(x− a)(x− b)| = (b− x)(x− a) fur x ∈ [a, b]. Somit ist∫ b

a

(b− x)(x− a)dx =

∫ b−a

0

(b− a− t)tdt (t = x− a)

=

[(b− a)

t2

2− t3

3

]b−at=0

=(b− a)3

6.

Also gilt

|I(f)− S(f)| ≤M2(b− a)3

12.

Wenn man sich bei der Wahl der Regel nach den vorigen Abschatzung richtet, sowurde man die Mittelpunktregel der Trapezregel vorziehen. Obwohl

2. NUMERISCHE INTEGRATION 73

2.5 (Mittelpunkregel vs. Trapezregel). Die Abschatzung der Mittelpunktregel ist umFaktor 2 besser die der Trapezregel. Die Mittelpunktregel benutzt einen Wert von fim Mittelpunkt, die Trapezergel die zwei Werte von f an den Endpunkten von [a, b].Ist der eine Wert im Mittelpunkt wichtiger (informativer) als die beiden Werte anden Endpunkten? Fur f = x2 und [a, b] = [0, h], erhalten wir

I(f) =h3

3.

SMittelpunkt(f) =h3

4

STrapez(f) =h3

2.

In diesem Fall ist die Approximation aus der Mittelpunktregel tatsachlich zwei malnaher zu I(f) als die Approximation aus der Trapezregel.

2.6 (Zusammegesetzte Regel). Die sogenannten zusammengesetzten Regel werdennach dem folgenden Prinzip aufgebaut. Ein Intervall [a, b] durch a = x0 < x1 < · · · <xn = b in n Intervalle unterteilen und auf jedem Intervall [xi, xi+1] mit 0 ≤ i < ndie gewunschte Regel benutzen (Mittelpunktregel, Trapezregel oder Ahnliches). DerGesamtfehler ist die Summer der Fehler auf den Intervallen der Unterteilung. Bei derTrapezregel erhalt man im Fall h = (b−a)/n und xi+1−xi = h fur alle i = 0, . . . , n−1z.B. die Summe

S(f) = h(f(x0) + 2f(x1) + · · ·+ 2f(xn−1) + f(xn))

als Approximation von I(f).

2.7 (Newton-Cotes-Regel). Polynome kann man bekannterweise exakt integrieren.Wenn wir also eine Funktion f auf [a, b] durch ein Polynom bzgl. der Stutzupunkte(x1, f(x1)), . . . , (xn, f(xn)) mit paarweise verschiedenen x1, . . . , xn ∈ [a, b] interpolie-ren, so konnen wir I(f) durch

S(f) =

∫ b

a

p(x)dx

approximieren. Wird p(x) in der Lagrange-Form

p(x) = f(x1)p1(x) + · · ·+ f(xn)pn(x),

so konnen wir S(f) als Linearkombination

S(f) =n∑i=1

f(xi)

∫ b

a

pi(x)dx.

der Werte f(x1), . . . , f(xn) darstellen. Die Koeffizienten dieser Linearkombinationhangen nur von [a, b] und den Stutzstellen x1, . . . , xn ab. Die Abschatzung des Ap-proximationsfehlers ergibt sich aus Theorem 1.16:

|I(f)− S(f)| ≤ Mn

n!

∫ b

a

|ωn(x)|dx.

Die Rechteckesregel und die Trapezregel sind beide spezielle Newton-Cotes-Regel mitjeweils n = 1 und n = 2. Die Regel mit bzgl. drei equidistanten Stutzstellen heißt dieSimpson-Regel, die Regel bzgl. vier equidistanten Stutzstellen heißt die 3/8-Regel.


2.8 Bsp (Simpson-Regel). Das ist die Newton-Cotes-Regel zu den 3 Stutzstellena, (a + b)/2, b. Man kann durch Variablentransformationen die Situation zum Falla = −1, b = 1 uberfuhren. Man berechnet in diesem Fall die Polynome aus derLagrange-Form der Interpolation, integriert diese, geht zum allgemeinen [a, b] uberund erhalt den Ausdruck

S(f) :=b− a

6

(f(a) + 4f

(a+ b

2

)+ f(b)

).

TODO: Im Aufbau

2.9 Bsp (3/8-Regel). Das ist die Newton-Cotes-Regel zu den 4 Stutzstellen a, 23a +

13b, 1

3a+ 3

4b, b. Berechnen Sie die Formel fur S(f) in diesem Fall.

2.10 (Fehler-Abschatzung fur Newton-Cotes-Formel). Wegen Theorem 1.16 (vgl.

2.7). Reicht es∫ ba|ωn(x)|dx nach oben abzuschatzen, ob eine Abschatzung in Ahbangigkeit

von [a, b] und den Stutzstellen und Mn herzuleiten. Wir ersetzen die Variable x durcht mit

x =a+ b

2+ t

b− a2

.

Zu jeder Stutzstelle xi hat man ein entsprechendes ti mit

x =a+ b

2+ ti

b− a2

.

Man erhalt ∫ b

a

|ωn(x)| dx =

(b− a

2

)n+1 ∫ 1

−1

∣∣∣∣∣n∏i=1

(t− ti)︸︷︷︸ν(t)

∣∣∣∣∣dtDer Wert |t − ti| ist hochstens 2, dodass |ν(t)| hochstens 2n ist. Wir erhalten dieAbschatzung

|I(f)− S(f)| ≤ Mn

n!(b− a)n+1 .

Man spricht in diesem Fall von der Approximation der Ordnung O(hn+1) auf einemIntervall der Lange h = b− a.

3 Diskrete Fourier-Transformation

3.1. In verschiedenen praktischen Anwendungen arbeitet man mit periodischen Funk-tionen. Wie Sie bereits aus der Analysis wissen, konnen periodische Funktionen aufR durch Fourier-Reihen beschrieben werden (naturlich, unter gewissen Vorausset-zungen, aber die Voraussetzungen sind nicht besonders einschrankend – Stetigkeitreich schon aus). Analog zu Stetigen periodischen Funktionen auf R kann man n-Periodische Funktionen auf Z betrachten. Die Diskrete Fourier-Transformation (DFT)ist eine Art Fourier reihe fur solche Funktionen. Bevor wir die DFT exakt einfuhren,machen wir einige Vorbemerkungen uber die Beschreibung trigonmetrischer Funktio-nen mit

3. DISKRETE FOURIER-TRANSFORMATION 75

3.2 (Komplexe Zahlen). Rein formal wird zu R eine weitere Zahl i (die imaginare Ein-heit) hinzugefugt, fur die i2 = −1 gilt. So ensteht die Menge C der komplexen Zahlenals die Menge aller Zahlen der Form z = a+ ib mit a, b ∈ R. Hierbei heißt a = Re(z)Realteil und b = Re(z) Imaginarteil von z. Die Zahlen z kann man als Vektoren derkomplexen Eben C zeichnen. Addition von zwei komplexen Zahlen entspricht der Vek-toraddition in der komplexen Ebene. Multiplikation lasst sich ebenfallsgeometrischveranschaulichen. Der Zahl z = a+ ib wird ihr Betrag |z| =

√a2 + b2 und das Argu-

ment Arg(z) zugeordnet (Arg(z) ist der Winkel, der die Komplexe Zahl als Vektor inder komplexen Eben zu der Achse der reellen Zahlen bildet). Bei der Multiplikationkomplexer werden die Betrage multipliziert und die Argumente zusammenaddiert.

Komplexe Zahlen sind ein nutzliches Werkzeug bei Behandlung mathematischerAufgaben.

3.3 (Funktionentheorie in a Nutshell). Funktionentheorie ist die Differential- undIntegralrechnung fur komplexe Funktionen:

(a) Funktionen wie ex, cosx und sinx, von R nach R, welche konvergente Taylor-Reihen besitzen, lassen sich zu Funktionen ez, cos z und sin z, von C nach C,erweitern. Hierbei werden die bekannten Formel aus der Algebra und Trigono-metrie wie etwa ex+y = exey, cos(x+ y) = cos(x) cos(y)− sin(x) sin(y) auch imallgemeineren Fall gelten.

(b) Durch Vergleich der entsprechende Taylor-Reihen lasst sich die sogenannte Euler-Formel herleiten:

eix = cos(x) + i sin(x), (III.2)

die fur alle x ∈ R erfullt ist. Das zeigt, dass die Exponentialfunktion und diebeiden trigonometrischen Funktionen miteinander verwandt sind.

3.4 (Euler-Formel als Konverter zwischen Algebra und Trigonometrie). AlgebraischeBerechnungen mit ez sind einfacher als trigonometrische Berechnungen mit cos(z)und sin(z). Die Euler-Formel ermoglicht einem die Trigonometrie durch Algebra zuersetzen.

(a) Die Bearbeitung der Funktion cos(x) etwa kann durch die Bearbeitung von eix =cos(x) + i sin(x) ersetzt werden. cos(x) erhalt man aus eix durch Re(eix). DieBearbeitung von cos(x) + 2 sin(5x) kann durch die Bearbeitung von eix− i2e5ix

ersetzt werden. cos(x) + 2 sin(5x) erhalt man als Re(eix − i2e5ix). Dies ist eineMoglichkeit, die Trigonometrie durch Algebra zu ersetzen. Solche Tricks benutztman in der Physik bei der Untersuchung von Wellen und Schwingungen und inder Theorie der Differentialgleichungen, um die Berechnungen zu vereinfachen.

(b) Eine weitere Moglichkeit ist die folgende. Wenn wir (III.2) fur ±x benutzen, sokonnen wir cos(x) und sin(x) aus den beiden Formeln bestimmen:

cos(x) =1

2(eix + e−ix). (III.3)

sin(x) = − i

2(eix − e−ix). (III.4)


3.5 (Konvertierung von Fourier-Reihen aus der trigonometrischen Form in die ’Alge-braische Form’). Wenn wir (III.3) und (III.3) zu einer Fourier-Reihe

∞∑j=0

(aj cos(jx) + bj sin(jx))︸︷︷︸reellwertige harmonische Funktion

mit Frequenz j

(III.5)

anwenden, erhalten wir die Darstellung der Fourier-Reihe als

∞∑k=−∞

ck eikx︸︷︷︸komplexe

harmonische Funktion

(III.6)

mit

ck =

ak−ibk

2, k > 0,

a0 k = 0,a−k+ib−k

2, k < 0.

ersetzen. Im Gegenteil zur Reihe (III.5), die auf zwei Arten von Funktionen basiert(Sinus-Funtionen und Cosinus-Funktionen), basiert (III.6) nur auf einer Art. Es istmeistens bequemer mit der Darstellung (III.6) zu arbeiten. Fur k > 0 werden durchdie Koeffizienten ck und c−k die Information uber die Frequenz k kodiert.

TODO: Konvertierung von (III.6) zu (III.5) (wenn ck ∈ C belieibig sind, werdenbei der Konvertierung

3.6 (Nebenbemerkung). Die Funktion aj cos(jx)+bj sin(jx) in (III.5) ist verschobene

und Skalierte Kosinus-Funktion. Fur Aj :=√a2j + b2

j find man ein φi mit cos(φj) =

aj/Aj und sin(φj) = bj/Aj. Dann gilt

aj cos(jx) + bj sin(jx) = Aj cos(jx− φj).

Aj ist die Amplitude, und φj ist die Phasenverschiebung.

3.7 (Diskretisierung analoger Signale). Eine genugend regulare 2π-periodische Funk-tion f : R→ C (etwa eine stetige Funktion) kann als Fourier Reihe

f(x) =∞∑

k=−∞

ckeikx (III.7)

beschrieben werden. Wenn x die Zeit und f ein Signal modelliert, so kann die vorigeDarstellung als Beschreibung eines analogen Signals f durch seine spektralen Da-ten (Phasenverschiebungen und Amplituden verschiedener Frequenzen) interpretiertwerden.

Etwas ahnliches kann man im Fall einer diskreten Zeit machen. Wir konnen einn ∈ N fixieren und darauf basierend die Zeitpunkte 2πj

nmit j ∈ Z betrachten (je

hoher n, desto feiner ist die Zeit-Diskretisierung). Haben wir fur jedes j ∈ Z denWert

vj := f(2πj

n)


in der Zeit 2πjn

abgelesen, so erhalten wir das diskrete Signal, das jedem j ∈ Z einenWert vj ∈ C zuordnet. Da f 2π-periodisch ist, ist uj in j n-periodisch. Das heißt,vj+n = vj.

Nun vergessen wir das analoge Signal komplett und arbeiten direkt mit dem Dis-kreten n-periodischen Signal (vj)j∈Z, fur welches wir ebenfalls eine Art Fourier-Reihebetrachten wollen. Es wird eigentlich keine Reihe sondern eine Summe sein, weil dasSignal aus einem n-dimensionalen Vektorraum stammt und die Fourier-Reihe die Zer-legung eines Vektors bzgl. einer sogenannten Fourier-Basis darstellt.

3.8 (Diskrete harmonische Funktionen und ‘diskrete Fourier-Reihen’). Den analogenharmonischen Funktionen eikx entsprechen in der Welt der n-periodischen diskretenSignale die Folgen

(e2πikjn )j∈Z

fur k ∈ 0, . . . , n − 1. Ein n-periodisches Signal (vj)j∈Z kann man mit dem Vektorv := (vj)j=0,...,n ∈ Cn identifizieren, weil es ausreicht die Werte in einer Periode zunotieren.

Die Zerlegung von v ∈ Cn in harmonische Signale ist somit eine Darstellung derForm

vj =n−1∑k=0

e2πijkn uk (III.8)

mit j = 0, . . . , n− 1 und u = (uk)k=0,...,n−1 ∈ Cn.

3.9 Def (Diskrete Fourier-Transformation). Gleichung (III.8) kann in der Vek-torform als die Gleichung

v = Fnu

mit Hilfe der Matrix

Fn =(e

2πijkn

)j,k=0,...,n−1

∈ Cn×n

dargestellt werden. Die Matrix Fn heißt die n× n Fourier-Matrix. Die Transfor-mation u 7→ v = Fnu auf Cn heißt die diskrete Fourier-Transformation, oder kurzDFT.

3.10 Bsp. Hier die Darstellung der komplexen harmonischen Funktionen. Der Real-teil der harmonischen Funktionen wird in Blau und der Imaginarteil in Rot dargestellt.Fall n = 8:


0 0

1 0

2 0

3 0

4 0

5 0

6 0

0 1 2 3 4 5 6 7

7

0 1 2 3 4 5 6 7

0

Fall n = 12:

0 0

1 0

2 0

3 0

4 0

5 0

6 0

7 0

8 0

9 0

10 0

0 1 2 3 4 5 6 7 8 9 1011

11

0 1 2 3 4 5 6 7 8 9 1011

0

Fall n = 16:


0 0

1 0

2 0

3 04 0

5 0

6 0

7 0

8 0

9 0

10 0

11 0

12 0

13 0

14 0

0 1 2 3 4 5 6 7 8 9101112131415

15

0 1 2 3 4 5 6 7 8 9101112131415

0

Bei n = 16 erkennt man in den harmonischen Funktionen mit Frequenzen 1 und 2immer noch die Kosinus- und Sinusfunktionen.

3.11 Def (n-te Wurzel aus 1). Die komplexen Zahlen e2πikn mit k = 0, . . . , n− 1

sind n Verschiedene Zahlen, deren n-te Potenz laut der Euler-Formel gleich 1 ist.Man nennt sie daher die n-ten Wurzel aus 1. Aus der Wurzel

wn := e2πin

kann man alle anderen Wurzel durch Potenzieren konstruieren.Tatsachlich sind

w0n, . . . , w

n−1n

alle n-te Wurzel aus 1.

TODO: Bild

(Die Multiplikation mit der Zahl wn dreht eine gegebene komplexe Zahl (alsVektor in der komplexen Ebene dargestellt) um ein n-tel des vollen Winkels imGegenuhrzeigersinn.)

Eine n-te Wurzel w aus 1 mit der Eigenschaft, dass die Folge

w0, . . . , wn−1

aus allen n-ten Wurzeln aus 1 besteht, nennt man primitiv.

3.12. Mit Hilfe der primitiven Wurzel wn kann die Fourier-Matrix als

Fn = (wjkn )j,k=0,...,n−1

beschrieben werden.


3.13. wn und w−1n sind primitive n-te Wurzel aus 1.

3.14 (Herleitung der inversen DFT). Wir zeigen, dass die DFT invertierbar ist. Dafurwird die Formel aus der Schule fur die Summe der geometrischen Reihe benotigt:

q0 + q1 + · · ·+ qn−1 =qn − 1

q − 1.

Die Formel gilt fur alle komplexen Zahlen q außer 1. Fur q = 1 ist gilt naturlichq0+· · ·+qn−1 = 1. Im Gegenteil zur reellwertiger Situation, in der man fur q ∈ R\1,als Summe der geometrischen Reihe nie eine Null bekommt, hat man fur mancheq ∈ C\1 die Gleichheit qn = 1, sodass in diesem Fall die Summe der geometrischenReihe gleich 0 ist. Genau das werden wir bei der Herleitung der inversen diskretenFourier-Transformation beobachten. Wir zeigen, dass Fn eine regulare Matrix ist mit

F−1n =

1

n(w−jkn )j,k=0,...,n−1.

Dafur reicht es das Produkt

Fn · (w−jkn )j,k=0,...,n−1

Die Komponente (j, s) dieses Produkts mit j 6= s ist die Summe

n−1∑k=0

wjkn w−ksn =

n−1∑k=0

w(j−s)kn

=(wj−sn )n − 1

wj−sn − 1(Summe geometrischer Reihe)

=(wnn)j−s − 1

wj−sn − 1

=1j−s − 1

wj−sn − 1

= 0.

Die Diagonalkomponente (j, j) des Produkts ist die Summe

n−1∑k=0

wjkn w−kjn =

n−1∑k=0

1 = n.

3.15 Def. Die Matrix F−1n heißt die inverse n×n Fourier-Matrix und die Trans-

formation v 7→ u = F−1n v auf Cn heißt die inverse Fourier-Transformation.

3.16. Die Struktur von Fn und F−1n ist gleich. Wenn man in der definierenden Formel

fur Fn die primitive n-te Wurzel wn gegen die primitive n-te Wurzel w−1n austauscht

und dann die Matrix mit Faktor 1n

multipliziert, so erhalt man F−1n . Das hat also

Folge, dass sich die Eigenschaften von Fn und F−1n kaum voneinander unterscheiden.

Wir beschaftigen uns mit Fn. Die Beobachtungen, die wir fur Fn machen werden,gelten auch fur F−1

n .


3.17 (Schnelle Fourier-Transformation). Die DFT ist eine sehr nutzliche Operation.Man ist daher an einer effizienten Berechnung von Fnu fur ein gegebenes u ∈ Cn

interessiert. Wenn man die Formel fur Produkt einer n × n Matrix und eines Vek-tors mit benutzt, so kommt man auf Θ(n2) Flops. Die sogenannte Schnelle Fourier-Transformation (engl. Fast Fourier Transform oder kurz FFT) ist viel effizienter undkommt mit lediglich Θ(n log n) Flops aus. Wir betrachten nur den Fall, in dem dieGroße n einer Zweierpotenz n = 2t ist. Die Idee ist, die Fourier Transformation derGroße 2n rekursiv mit Hilfe der Fourier-Transformation der Große n auszrechnen.Die Formel im Fall der Große 2n ist

vj =2n−1∑k=0

wjk2nuk

Wir zerlegen die Summe auf der rechten Seite in zwei, uber die geraden und uber dieungeraden k:

vj =n−1∑s=0

wj(2s)2n u2s +

n−1∑s=0

wj(2s+1)2n u2s+1

=n−1∑s=0

wj(2s)2n u2s + wj2n

n−1∑s=0

wj(2s)2n u2s+1 (ein Term ausgeklammert)

=n−1∑s=0

wjsn u2s + wj2n

n−1∑s=0

wjsn u2s+1 (wegen w22n = wn)

Wir konnen nach dieser Formel vj mit j = 0, . . . , n− 1 und vj+1 mit j = 0, . . . , n− 1ausrechnen: Mit berucksichtigung von wn2n = −1 und wnn = 1 erhalt man:

vj =n−1∑s=0

wjsn u2s + wj2n

n−1∑s=0

wjsn u2s+1

vj+n =n−1∑s=0

wjsn u2s − wj2nn−1∑s=0

wjsn u2s+1

Das heißt, dass der Vektor v folgendermaßen berechnet werden kann. Man Berech-net die Fourier-Transformationen die Fourier transformationen der Vektoren (u2s)s=0,...,n−1

und (u2s+1)s=0,...,n−1 ermittelt darauf basierend mit O(n) Flops den Vektor v. DieVoraussetzung dabei ist das, die Wurzeln wj2n aus 1 vorberechnet wurden und bereitsvorliegen.


Fur den Rechenaufwand A(n) in Flops ergibt sich aus den vorigen Uberlegungendie Rekursion

A(2n) = 2A(n) + Θ(n),

die zur asymptotischen Abschatzung A(n) = Θ(n log n) fuhrt. (Um die konstantenaus der Notation Θ(n) nicht mitschleppen zu mussen, kann man zum Beispiel exem-plarisch die Rekursion A(2n) = 2A(n) + 2n mit A(1) = 0 fur n = 2t auflosen.)

3.18. Die n × n inverse DFT kann nach dem selben Prinzip mit O(n log n) Flopsberechnet werden.

4 Faktorisierungen von Matrizen

4.1 (Multiplikation von Matrizen). Fur Herleigung verschiedener Faktorisierungenvon Matrizen ist es wichtig, Multiplikation von Matrizen unter verschiedenen Blick-winkeln zu betrachten. Sie erinnern sich bestimmt an die Formel fur die Multiplikationvon Matrizen. Das Muster zu dieser Formel ist:

·

=

4.2 (Darstellung der Multiplikation von Matrizen mit Hilfe von Spalten und Zeilen).Das Produkt von AB von zwei Matrizen von A und B lasst sich zeilenweise mit Hilfevon Zeilen von B beschreiben. Analog kann das Produkt auch spaltenweise mit Hilfevon Spalten der Matrix A beschrieben werden.

TODO: Bilder

4.3 Bsp. Wir betrachten die Matrix

A =

1 0 0 0 00 1 0 0 00 7 1 0 00 −3 0 1 00 4 0 0 1

Die Matrix AM entsteht aus M folgendermaßen:

• Zur dritten Zeile von M , 7-mal die zweite dazu addieren.

• Von der vierten Zeile von M , 3-mal die zweite abziehen.

• Zur vierten Zeile von M , 4-mal die zweite dazu addieren.

Das Ergebnis ist die Matrix AM .

4.4 Bsp. Wir konnen die Matrix A auch von links multiplizieren. Die Matrix MAentsteht aus M folgedermaßen:

4. FAKTORISIERUNGEN VON MATRIZEN 83

• Zur zweiten Spalte von M , 7-mal die dritte dazu addieren, 3-mal die vierteabziehen und 4-mal die funfte dazu addieren.

• Die anderen Spalten andern sich nicht.

Das Ergebnis ist die Matrix MA.

4.5 (Losung linearer Gleichungssysteme fur Systeme in der Dreiecksform). Betrach-ten wir ein LGS (lineares Gleichungssystem) Lx = b, fur das L eine n × n untereDreiecksmatrix ist, die auf der Diagonale keine Nullen hat. Das heißt, die erste Glei-chung involviert nur x1, die zweite Gleichung nur x1 und x2 und so weiter. Nun konnenwir aus der ersten Gleichung das x1 bestimmen und die zweite Gleichung einsetzen,dann x2 aus der zweiten Gleichung bestimmen usw. So kann das System Lx = b mitHilfe von O(n) Flops gelost werden. Dieses Verfahren nennt man Vorwartseinsetzen.

Die LGS der Form Ux = b mit einer oberen Dreiecksmatrix U (ohne Nullen aufder Diagonale) lassen sich komplett analog durch das Ruckwartseinsetzen losen.

4.6 Def. Eine LU-Faktorisierung ist eine Darstellung A = LU einer regularenMatrix A als Produkt einer unteren Dreicksmatrix L und einer oberen Dreicks-matrix U .

4.7 (Der praktische Nutzen der LU -Faktorisierung). In der Praxis braucht man ofterLGS Ax = b fur mehrere rechte Seiten b und die gleiche regulare Matrix A zu losen.

(a) Wenn man eine LU -Faktorisierung A = LU von A zur Verfugung hat, kannAx = b mit O(n2) Flops gelost werden. wir haben

L Ux︸︷︷︸=:v

= b.

Das v kann aus Lv = b bestimmt werden und anschließend das x aus dem Sy-stem Ux = v. Man benutzt als einmal das Vorwarts- und einmal das Ruckwarts-einsetzen.

(b) Ist die Matrix A riesengroß, sodass sie kaum in den Arbeitsspeicher passt, sokann man A ‘wegschmeißen’ und stattdessen L und U aufheben. Die SystemeAx = b kann man dann wie oben beschrieben mit Hilfe von L und U losen. Wennman A mit einem Vektor multiplizieren mochte, so ware es auch kein Problem,da man die Operation x 7→ Ax durch Multiplikation mit U und dann mit Ldarstellen kann. Zur Speicherung von U und L braucht man insgesamt ungefahrso viel Speicher wie zur Speicherung von A. Die Matrix U hat unterhalb derdiagonale nur die Nullen, die man nicht explizit speichern muss. Analog hat dieMatrix L oberhalb der Diagonale die Nullen, die man ebenfalls nicht explizitspeichern muss.

4.8 (LU -Faktorisierung und Gauß-Verfahren). Als Gauß-Verfahren bezeichnen wridas Gaußsche Eliminationsverfahren zur Losung von LGS.

Wenn wir ein LGS Ax = b mit einer regularen Matrix A mit Hilfe des Gauß-Verfahrens durch die Uberfuhrung der Matrix der linken Seite A in oberen Dreiecks-form losen, so benutzen wir im Laufe der Ausfuhrung dieses Verfahrens Zeilenopera-tionen der Form: Zur j-ten Zeile α mal die i-te Zeile dazu addieren. Die Koeffizienten


α, die im Laufe der Berechnungen entstehen sind eine Art Nebenprodukt des Gauß-Verfahrens. Sie werden im Gauß-Verfahren einfach weggeschmissen. Der Algorithmuszur Berechnung der LU -Faktorisierung ist eine Modifikation des Gauß-Verfahrens,welche die erwahnten Koeffizienten recyclt und darauf aufbauend die DarstellungA = LU berechnet.

4.9 (Berechnung der LU -Faktoriesierung). Wir erinnern daran, dass das Produktvon Matrizen zeilenweise dargestellt werden. Daher konnen die n Runden des Gauß-verfahrens durch Multiplikation der Matrizen dargestellt werden. Wir beschreiben dieIdee am Beispiel n = 4. Wir haben eine beliebige Matrix

A =

∗ ∗ ∗ ∗∗ ∗ ∗ ∗∗ ∗ ∗ ∗∗ ∗ ∗ ∗

und wollen diese mit Gauß-Verfahren in die obere Dreicksform uberfuhren. Die Kom-ponente (1, 1) wird als das Pivot-Element gewahlt mit Verwendung von Zeilen Ope-rationen Nullen in Positionen (2, 1) bis (5, 1). Als Matrix-Product kann das folgeder-maßen beschrieben werden:

1 0 0 0α2,1 1 0 0α3,1 0 1 0α4,1 0 0 1

︸︷︷︸

=:M1

A =

• ∗ ∗ ∗0 ∗ ∗ ∗0 ∗ ∗ ∗0 ∗ ∗ ∗

In der zweiten Runde ist (2, 2) das Povot-Element und wir erzeugen Nullen in Posi-tionen (3, 2) und (4, 2). Als Multiplikation von Matrizen

1 0 0 00 1 0 00 α3,2 1 00 α4,2 0 1

︸︷︷︸

=:M2

M1A =

• ∗ ∗ ∗0 • ∗ ∗0 0 ∗ ∗0 0 ∗ ∗

In der dritten Runde ist (3, 3) das Pivot-Element und es wird eine Null in derPosition (4, 3) erzeugt. Als Multiplikation von Matrizen

1 0 0 00 1 0 00 0 1 00 0 α4,3 1

︸︷︷︸

=:M3

M2M1A =

• ∗ ∗ ∗0 • ∗ ∗0 0 • ∗0 0 0 ∗

︸︷︷︸

=:U

.

Die Matrix U wird durch das Gauß-Verfahren direkt berechnet. Es stellt sichheraus, dass die Koeffizienten αi,j direkt die Matrix L ergeben.

Die Darstellung

M3M2M1A = U


kann alsA = M−1

1 M−12 M−1

3︸︷︷︸=:L

U.

umformuliert werden. Also haben wir nun jetzt eine Beschreibung von L mit Hilfevon M1,M2,M3. Es ist ganz einfach die Matrizen M1,M2,M3 zu invertieren, dafurmuss man lediglich αi,j durch −αi,j ersetzen. Wir erhalten also die Darstellung

L =

1 0 0 0

−α2,1 1 0 0−α3,1 0 1 0−α4,1 0 0 1

1 0 0 00 1 0 00 −α3,2 1 00 −α4,2 0 1

1 0 0 00 1 0 00 0 1 00 0 −α4,3 1

Wenn wir nun das Produkt der drei Matrizen auf der rechten Seite mit Hilfe vonZeilen oder Spalten interpretieren, so erhalten wir

L =

1 0 0 0

−α2,1 1 0 0−α3,1 −α3,2 1 0−α4,1 −α4,2 −α4,3 1

Dies ist die Darstellung von L mit Hilfe von αi,j.

4.10. Die LU -Faktorisierung wird nach dem gleichen Prinzip fur beliebige Großen nberechnet.

Wir haben in der Beschreibung von LU -Faktorisierung die Pivot-Elemente aufder Diagonale gewahlt. Eigentlich geht das nicht immer. Es kann zum Beispiel pas-sieren, dass das Element auf der Diagonale Null ist. Andererseits ist das nicht immererwunscht: betragsmaßig kleine Pivot-Elemente fuhren bei Berechnung mit Gleit-kommazahlen zu großen Fehlern bei der Ausfuhrung von Zeilenoperationen. DiesesProblem lasst sich durch die Einfuhrung von Darstellungen beheben, die etwas all-gemeiner als die LU -Faktorisierungen sind. Konkret werden wir im folgenden diesogenannte LUP -Zerlegung einfuhren.

4.11 Def. Eine Permutationsmatrix ist eine n×n Matrix die aus der Einheitsma-trix durch Vertauschen von Zeilen (oder Spalten) entsteht. Mit anderen Wortenist das eine Matrix, bei der in jeder Zeile und Spalten genau eine 1 vorkommtund alle anderen Komponenten gleich 0 sind.

4.12 Bsp. Was macht die Multiplikation mit einer Permutationsmatrix? Betrachtenwir die

P =

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

Die Operation M 7→ PM ist das Vertauschen der Zeilen von M :

• die dritte Zeile von M kommt an die erste Position,


• die erste Zeile an die zweite Position,

• die funfte Zeile an die dritte Position,

• die vierte Zeile bleibt in der vierten Position,

• die zweite Zeile kommt an die funfte Position.

Die Operation M 7→MP ist das Vertauschen der Spalten von M :

• die zweite Spalte kommt in an die erste Position,

• die funfte Spalte kommt an die zweite Position,

• die erste Spalte kommt an die dritte Position,

• die vierte Spalte bleibt in der vierten Position,

• die dritte Spalte kommt an die funfte Position.

4.13 (LUP-Zerlegung). Wir diskutieren wieder exemplarische den Fall n = 4. Wir er-haluben im Gauß-Verfahren 4.9 mehr Freiheit: Pivot-Element durfen nun nicht auf derDiagonale sondern in einer beliebige Position gewahlt werden. Nach der Ausfuhrungeines solchen modifizierten Verfahrens, erhalten wir keine obere Dreicksmatrix son-dern eine Matrix wie etwa diese:

U =

∗ • ∗ ∗∗ 0 ∗ •∗ 0 • 0∗ 0 0 0

.

Es gilt:A = LU,

wobei L wie in 4.9 definiert ist. Wenn man die Spalten von U ‘sortiert’, erhalt maneine obere Dreicksmatrix. Daher lasst sich U als

U = UP

mit Hilfe einer oberen Dreicksmatrix und einer Permutationsmatrix darstellen, sodassman aus A = LU die Darstellung

A = LUP

erhalt. Fur U wie oben, hat man∗ • ∗ ∗∗ 0 ∗ •∗ 0 • 0∗ 0 0 0

︸︷︷︸

U

=

• ∗ ∗ ∗0 • ∗ ∗0 0 • ∗0 0 0 ∗

︸︷︷︸

U

0 0 0 11 0 0 00 0 1 00 1 0 0

︸︷︷︸

P

Die Wahl von P wird klar, wenn man die vorige Formel mit Hilfe von Spalten von Uund U interpretiert.


4.14 Def. Eine Darstellung einer regularen Matrix A als A = LUP als Pro-dukt einer unteren Dreiecksmatrix U , einer oberen Dreicksmatrix U und einerPermuationsmatrix P nennt man die LUP -Faktoriesierung.

4.15. Die LUP -Faktorisierung kann kompakt gespeichert werden. Die Matrix P mussman nicht direkt speichert, es reicht die entsprechende Permutation zu speichern. DieMatrizen L und U konnen wie in der LU -Faktorisierung gespeichert werden.

4.16. Mit Hilfe der LUP -Faktorisierung kann analog zur LU -Faktorisierung das LGSAx = b schnell losen. Man hat

LU Px︸︷︷︸=:x︸︷︷︸

=:u

= b.

Aus Lu = b erhalt man u mit Hilfe von O(n2) Operationen. Dann erhalt man x ausUx = u mit Hilfe von O(n2) Operationen. Der Vektor x ist lediglich Permutation vonx. Man erhalt also x aus Px = x mit O(n) Operationen.

4.17 Def. Ist A eine regulare Matrix, so heißt die Darstellung A = QR von Aals Produkt einer orthogonalen Matrix Q und einer oberen Dreiecksmatrix R dieQR-Faktorisierung. (Wir erinnern daran, dass eine Matrix Q orthogonal ist, wennQ>Q = In gilt; das heißt Q> ist die inverse Matrix von Q.)

4.18 (QR-Faktoriesierung von Losung von LGS). Die QR-Faktorisierung und ihreVariationen hat verschiedene Anwendungen. Zum Beispiel kann das LGS Ax = bkann mit Hilfe der QR-Faktorisierung A = QR wie folgt gelost werden. Man hat

QRx = b.

Da Q orthogonal ist, kann diese Matrix mit Hilfe von lediglich O(n2) Operationeninvertiert werden. Die Gleichung kann also als

Rx = Q>b

umformuliert werden. Nun kann x durch das Ruckwartseinsetzen mit Hilfe von O(n2)Operationen ermittelt werden.

4.19 (Gram-Schmidt-Orthogonalisierung). Wenn man das Ergebnis der Gram-Schmidt-Orthogonalisierung mit Matrizen interpretiert, sieht man sofort, dass dieses Verfahrendie QR-Zerlegung einer regularen Matrix A berechnet. Wir erklaren das Prinzip imFall n = 4. Man betrachte die Matrix

A =

( ∗∗∗∗︸︷︷︸a1

∗∗∗∗︸︷︷︸a2

∗∗∗∗︸︷︷︸a3

∗∗∗∗︸︷︷︸a4

)


mit Spalten a1, a2, a3, a4. Wir bestimmen zuerst die Darstellung

( ∗∗∗∗︸︷︷︸a1

∗∗∗∗︸︷︷︸a2

∗∗∗∗︸︷︷︸a3

∗∗∗∗︸︷︷︸a4

)

︸︷︷︸=A

=

( ∗∗∗∗︸︷︷︸b1

∗∗∗∗︸︷︷︸b2

∗∗∗∗︸︷︷︸b3

∗∗∗∗︸︷︷︸b4

)

︸︷︷︸=B

1 c1,2 c1,3 c1,4

0 1 c2,3 c2,4

0 0 1 c3,4

0 0 0 1

︸︷︷︸

=C

,

in der die Spalten b1, . . . , b4 von B eine Orthgonalbasis bilden sollen. Das heißt, es soll〈bi, bj〉 fur i 6= j gelten. Interpretieren, wir das Produkt ABC als Relation zwischenSpalten von A und Spalten von B. Dann lasst sich das Produkt als die Bedingungen

a1 = b1,

a2 = b1c1,2 + b2,

a3 = b1c1,3 + b2c2,3 + b3,

a4 = b1c1,4 + b2c2,4 + b3c3,4 + b4.

ausschreiben. Wir haben den folgenden iterativen Prozess:

• Die Wahl von b1 ist b1 = a1.

• Der Vektor b2 wird durch b2 = a2 − b1c1,2, sobald wir c1,2 fixieren. Der Ko-effizient c1,2 muss so gewahlt werden, dass b2 orthogonal zu b1 ist. Das heißt〈a2 − b1c1,2, b1〉 = 0 muss gelten. Das ergibt

c1,2 =〈a2, b1〉〈b1, b1〉

.

Somit ist c1,2 und b2 festgelegt.

• Der Vektor b3 ist b3 = a3 − b1c1,3 − b2c2,3. Wir wahlen c1,3 und c2,3 so, dass derresultierende Vektor b3 zu b1 und b2 orthogonal sind. Da b1 und b2 zu einanderorthogonal sind, erhalt man aus den Bedingungen 〈a3 − b1c1,3 − b2c2,3, b1〉 = 0und 〈a3 − b1c1,3 − b2c2,3, b2〉 = 0 die Formel

c1,3 =〈a3, b1〉〈b1, b1〉

c2,3 =〈a3, b2〉〈b2, b2〉

fur c1,3 und c2,3. Somit werden c1,3, c2,3 und b3 festgelegt.

• Der Vektor b4 ist b4 = a4 − b1c1,4 − b2c2,4 − b3c3,4. Die Wahl der Koeffizientenc1,4, c2,4, , c3,4 wird vollig analog begrundet. Da die Vektoren b1, b2, b3 zueinanderpaarweise orthogonal sind und der Vektor b4 so gewahlt werden muss, dass erzu b1, b2 und b3 orthogonal ist, hat man

c1,4 =〈a4, b1〉〈b1, b1〉

c2,4 =〈a4, b2〉〈b2, b2〉

c3,4 =〈a3, b1〉〈b1, b1〉


Die Darstellung A = BC ist ‘fast’ eine QR-Faktosierung. In einer QR-Faktorisierungbilden die Spalten von Q eine Orthonormalbasis (d.h., die Spalten haben die Lange1 und sind zueinander paarweise orthogonal). Die Spalten von B bilden erstmal eineOrthogonalbasis (die Spalten sind zu einander orthgonal, sie mussen aber nicht dieLange 1 haben). Die QR-Faktorisierung erhalt man durch passendes Skalieren von Bund C. Und zwar

A = BC = B

1/‖b1‖ 0 0 0

0 1/‖b2‖ 0 00 0 1/‖b3‖ 00 0 0 1/‖b4‖

︸︷︷︸

=:Q

‖b1‖ 0 0 0

0 ‖b2‖ 0 00 0 ‖b3‖ 00 0 0 ‖b4‖

C

︸︷︷︸=:R

,

was die Konstruktion der QR-Zerlegung abschließt.

4.20. In dem oben beschriebenen Verfahren werden zuerst die Matrizen B und C kon-struiert. Die Berechnung der Normen macht man somit nicht in der ‘Hauptiteration’sondern kurz vor dem Abschluss in der ‘Skalierungsphase’. Fur die manuellen Berech-nungen hat es den folgenden Vorteil. Wenn A rationale Eintrage hat, so haben auchB und C rationale Eintrage. Also rechnet man in diesem Fall in der Hauptiterationnur mit den rationalen Zahlen. Die Standardumsetzung von Gram-Schmidt-Verfahrenberechnet die Spalten von Q und die Eintrage von R direkt (ohne die Spalten von Bund die entsprechenden Eintrage von C zu berechnen).

4.21 (Gram-Schmidt zur Bestimmung der orthogonalen Projektion). In verschiede-nen Anwendungen hat man die folgende Aufgabe: man erhalt einen UntervektorraumU von Rn und muss zu einem gegebenen Punkt x den nachsten Punkt von U bestim-men. Dieser nachste Punkt ist die orthogonale Projektion von x auf U . In der Regelwird U durch seine Basis oder durch ein homogenes Gleichungssystem gegeben. DieWahl der Darstellung fur U ist nicht so entscheidend. Ein einfaches Verfahren zurLosung dieser Aufgabe ist wie folgt. Wenn man aus einer gegebenen Basis von U eineorthogonale Basis b1, . . . , bk bildet, so hat die orthogonale Projektion von x auf dieForm

k∑i=1

bi〈bi, x〉〈bi, bi〉

.

Die Matrix dieser linearen Abbildung ist

P =k∑i=1

1

〈bi, bi〉bib>i .

4.22 Bsp. Der durch die Gleichung x1 + x2 + x3 = 0 definierte Untervektorraum Ukann durch die Vektoren

a1 =

1−10

a2 =

0−11

erzeugt werden. Wir wollen an diesem Beispiel illustrieren, wie man mit Gram-Schmidt die orthogonale Projektion auf U berechnen kann. (Fur dieses konkrete


Beispiel, gibt es auch einfachere Weisen, die orthogonale Projektion zu berechnen,wir wahlen aber Gram-Schmidt, um zu illustrieren wie man in anderen kompliziertenFallen vorgehen kann: etwa 4-dimensionaler Untervektorraum von R10).

4.23 Bsp (Verallgemeinerte Losungen uberdefinierter Gleichungssysteme). Die Posi-tion eines Punktes p = (x, y) ∈ R2 muss anhand der gestorten Angaben zu Abstandendieses Punktes zu n Bekannten Punkten p1 = (x1, y1), . . . , pn = (xn, yn). Das heißt,man erhalt die Werte di := ‖p − pi‖ + si, wobei si ∈ R eine Storung ist, und mussnun daraus einen Vorschlag zur Position von p ausrechnen. Wir haben also mit einemSystem von n Gleichungen ‖p − pi‖ = di in unbekannten Koordinaten x und y desPunktes, das evtl. gar keine Losung besitzt. Die Idee ist nun als p = (x, y) einenPunkt zu wahlen, bei dem die Diskrepanz zwischen ‖p − pi‖ und di moglichst kleinist. In diesem Fall kann man die Gleichungen quadrieren

‖p− pi‖2 = d2i

Komponentenweise als

(x− xi)2 + (y − yi)2 = d2i

ausschreiben, die Terme ausmultiplizieren und die Gleichungen zur Form

−2xi x︸︷︷︸=:α1

−2yi y︸︷︷︸=:α2

+ (x2 + y2)︸︷︷︸=:α3

= d2i − x2

i − y2i .

Nun konnen wir die Gleichung in der Vektorform mit Hilfe der Vektoren

a1 :=

−2x1...

−2xn

a2 :=

−2y1...−2yn

a3 :=

1...1

b :=

d21 − x2

1 − y21

...d2n − x2

n − y2n

als Gleichung

α1a1 + α2a2 + α3a3 = b

in unbekannten α1, α2, α3 ∈ R formulieren. Zwar hat diese Gleichung im allgemei-nen keine Losung, wir konnen aber als ‘Losung’ die α1, α2, α3 wahlen, bei denen derAbstand von α1a1 + α2a2 + α3a3 zu b minimal ist. Dafur kann man fur a1, a2, a3

Gram-Schmidt anwenden und dann b orthogonal auf die lineare Hulle von a1, a2 unda3 projizieren.

An stellen (xi, yi) mit i = 1, . . . , n befinden sich die Stationen, die den Abstandzu einem Unbekannten Punkt

4.24 (Multidimensionale lineare Regression). Kehren wir noch kurz zur Stochastikund Statistik zuruck. Wir haben die lineare Regression im Fall der Schatzung einerZufallsvariablen durch als affine Funktion einer andere Zufallsvariablen betrachtet.Man auch eine Zufallsvariable durch affine Funktion mehrerer anderen Zufallsvaria-blen voraussagen mochte. Betrachten wir exemplarische den Fall, in dem Wir eineZufallsvariable Z, die wir durch affine Funktion von zwei anderen ZufallsvariablenX1 und X2 voraussagen mochten. Setzen wir Einfachheit halber voraus, dass die Er-wartungswerte von X1, X2 und Z alle gleich 0 sind (diese Bedingung kann durch die


passende ‘Verschiebung’ der zugrundeliegenden Zufallsvariablen garantiert werden).Gesucht werden nun die Koeffizienten α1, α2 ∈ R, fur welche der Wert

E((Z − α1X1 − α2X2)2)

minimal ist. Im allgemeinen konnen X1 und X2 korreliert sein. Da wir E(Xi) =0 voraussetzen, ist die Korrelation von X1 und X2 gleich E(X1X2). Dies ist dasSkalarprodukt der Vektoren X1 und X2. In der Sprache der linearen Algebra ist unsereBemerkung einfach die Beobachtung, dass die Vektoren X1 und X2 nicht unbedingtorthogonal sind. Wir konnen aber mit Gram-Schmidt aus X1, X2 orthognale VektorenY1, Y2 folgendermaßen konstruieren. Wir setzen Y1 = X1 und bestimmen Y2 aus derGleichung X2 = Y1c1,2 + Y2 so, dass Y1 und Y2 unkorreliert sind. Wir haben Y2 =Y2 − Y1c1,2. Damit Y1 und Y2 unkorreliert sind, muss die Bedingung 0 = E(X2Y1) −E(Y 2

1 )c1,2 erfullt sein. Wir haben also

c1,2 =E(Y1X2)

E(Y 21 )

X1 und X2 werden also als lineare Kombinationen von unkorrelierten Zufallsavaria-blen Y1, Y2 beschrieben. Unsere Originalaufgabe reduziert sich somit zur Suche vonβ1, β2 ∈ R, fur welche

g(β1, β2) = E((Z − β1Y1 − β2Y2)2))

minimal ist. Durch Ausmultiplizieren und mit Berucksichtigung von E(Y1Y2) = 0erhalt man

g(β1, β2) = E(Z)2 + β21E(Y 2

1 ) + β22E(Y2)2 − 2β1E(ZY1)− 2β2E(ZY2)

Zur Bestimmung der optimalen Losung benutzen wir die Bedingungen ∂g∂β1

= 0 und∂g∂β2

= 0, aus denen man

β1 =E(ZY1)

E(Y 21 )

β2 =E(ZY2)

E(Y 22 )

erhalt. Wir konnen also Z durch

E(ZY1)

E(Y 21 )

Y1 +E(ZY2)

E(Y 22 )

Y2

voraussagen. In der Sprache der linearen Algebra ist dieser Ausdruck die Projektionvon Z auf den durch Y1, Y2 erzeugten Untervektorraum (der durch X1 und X2 erzeugteUntervektorraum ist der selbe Untervektorraum.)

4.25 Def. Wir nennen eine quadratische Matrix A ∈ Rn×n positiv definit, wennA symmetrisch ist (d.h. A = A>) und fur alle x ∈ Rn \ 0 die Bedingungx>Ax > 0 erfullt ist.


4.26 Def. Darstellung einer positiv definiten Matrix A als Produkt A = LL>,fur eine unteren Dreiecksmatrix L heißt Cholesky-Zerlegung von A.

4.27. In vielen praktischen Situation mochte man LGSs Ax = b losen, bei denendie Matrix A positiv definit ist. Das Standard-Verfahren basiert auf der Berechnungder sogenannten Cholesky-Zerlegung. Schreibt Ax = b als LL>x = b um lost dasdurch Vorwarts- und Ruckwartseinsetzen. Die Cholesky-Zerlegung ist die ‘Verbesse-rung’ von LU -Zerlegung fur positiv definite Matrizen. Bei der Cholesky Zerlegungreicht es eine Matrix L an der Stelle von zwei Matrizen L,U in der LU -Zerlegung zuspeichern. Des weiteren kann die Cholesky-Zerlegung schneller als die LU -Zerlegungberechnet werden (nicht im Asymptotischen Sinne, aber bei großen Instanzen ist auchdie Verbesserung der Konstanten bei O(n3)-Verfahren wichtig).

4.28 (Berechnung der Cholesky-Zerlegung). Die Cholesky-Zerlegung kann iterativaus der definierenden Gleichung A = LL> berechnet werden. Die Gleichung A = LL>

kann komponentenweise ausgeshrieben werden. Das ergibt ein Gleichungssystem furunbekannte Komponenten li,j von L (i ≥ j). Man soll lediglich herausfinden, inwelcher Reihenfolge man die Komponenten aus li,j bestimmen soll. Wir behandeltwieder exemplarisch den Fall n = 4. Die Bedingung ist

A =

l1,1 0 0 0l2,1 l2,2 0 0l3,1 l3,2 l3,3 0l4,1 l4,2 l4,3 l4,4

︸︷︷︸

L

l1,1 l2,1 l3,1 l4,10 l2,2 l3,2 l4,20 0 l3,3 l4,30 0 0 l4,4

︸︷︷︸

L>

.

Nun konnen wir folgendermaßen vorgehen:

(1, 1): l1,1 ergibt sich aus der Gleichung a1,1 = l21,1. (Da A positiv definit ist, gilta1,1 > 0.)

(i, 1): li,1 mit i > 2 ergeben sich aus den Gleichungen ai,1 = li,1l1,1, da l1,1 bereitsfestgelegt ist.

(2, 2): l2,2 ergibt sich aus der Gleichung a2,2 = l22,1 + l22,2, da l2,1 bereits festgelegt ist.

(i, 2): li,2 mit i > 2 ergeben sich aus den Gleichungen ai,2 = li,1l2,1 + li,2l2,2, da li,1 furalle i sowie l2,2 bereits festgelegt sind.

(3, 3): l3,3 ergibt sich aus a3,3 = l23,1 + l23,2 + l23,3.

(i, 3): l4,3 ergibt sich aus a4,3 = l4,1l3,1 + l4,2l3,2 + l4,3l3,3.

(4, 4): l4,4 ergibt sich aus a4,4 = l24,1 + l24,2 + l24,3 + l24,4.

4.29. Wir berechnen die Cholesky-Zerlegung der Matrix

A =

9 −3 −6 6−3 5 −4 2−6 −4 14 −9

6 2 −9 10

5. GESTORTE MATRIZEN UND LINEARE GLEICHUNGSSYSTEME 93

Wir werden in das folgende Muster

A =

• 0 0 0∗ • 0 0∗ ∗ • 0∗ ∗ ∗ •

︸︷︷︸

=L

• ∗ ∗ ∗0 • ∗ ∗0 0 • ∗0 0 0 •

︸︷︷︸

=:L>

sukzessiv konkrete Werte eintragen.

TODO: Im Aufbau

5 Gestorte Matrizen und Lineare Gleichungssy-

steme

5.1. Wenn wir ein LGS Ax = b zu einem anderen LGS (A+ ∆A)x = b+ ∆b storen,wie andern sich die Losung in Abhangigkeit von der Große der Storung? Wenn wir mitRundungsfehlern (und anderen Fehlern) rechnen, konnen wir durch die Beantwortungdieser Frage herausfinden, ob die berechnete numerische Losung sinnvoll ist. Desweiteren hilft uns die Beantwortung dieser Frage bei der Entwicklung von sogenannteniterativen Losungsverfahren fur LGS.

5.2 Def (Operatornorm). Ist ‖ · ‖ eine Norm auf Rn so definieren wir die soge-nannte Operatornorm zu dieser Norm auf Rn durch

‖A‖ := sup ‖Ax‖ : ‖x‖ ≤ 1 .

auf Rn×n.

5.3. Man kann sich vergewissern, dass die Operatornorm tatsachlich eine Norm aufRn×n ist und dass dafur die Ungleichungen ‖Ax‖ ≤ ‖A‖‖x‖ und ‖AB‖ ≤ ‖A‖‖B‖fur alle A,B ∈ Rn×n und alle x ∈ Rn erfullt sind.

5.4 (Geometrische Bedeutung der Operatornorm). Wenn wir als

Bn := x ∈ Rn : ‖x‖ ≤ 1

die Einheitskugel bezeichnen, so ist ‖A‖ der Umkugelradius des Ellipsoids

EA := Ax : x ∈ Bn .

5.5. Wir fixieren im folgenden fur Rn die Euklidische Norm

‖(x1, . . . , xn)‖ :=√x2

1 + · · ·+ x2n.

Der Stoff aus diesem Abschnitt gelten kann oft direkt auf den Fall einer allgemeinenzugrundeliegenden Norm auf Rn ubertragen werden. Die Operatornorm ‖A‖ bzgl. deroben eingefuhrten Euklidischen Norm auf Rn nennt man oft die Spektralnorm von A.


5.6. Wegen ‖Ax‖ =√〈Ax,Ax〉 =

√〈A>Ax, x〉 ist die Spektralnorm von A die

Wurzel des großten Eigenwert von A>A. (Die Wurzel aus den Eigenwerten von A>Aheißen Singularwerte von A.) Außerdem kann bei symmetrischen Matrizen A dieSpektralnorm von A als das Maximum der Betrage der Eigenwerte von A beschriebenwerden.

5.7 Def. Ist A ∈ Rn×n regular, so fuhren die Konditionszahl κ(A) von A als

κ(A) = ‖A‖ · ‖A−1‖

ein.

5.8 (Geometrische Bedeutung der Konditionszahl). Die Konditionszahl κ(A) bzgl.der Spektralnorm ist das Verhaltnis des Umkugel- und Inkugelradius von EA.

5.9. Die Konditionszahl κ(A) bzgl. der Spetktralnorm ist der Quotient des maxima-len und des minimalen Singularwertes von A. Bei symmetrischen Matrizen sind dieSingularwerte von A die Betrage der Eigenwerte von A.

5.10 Bsp. Berechnen wir die Spektralnorm und die Konditionszahl von

A =

(1 10 1

).

TODO: Im Aufbau

5.11 Thm (Relativer Fehler bei Storung der rechten Seite). Sei A ∈ Rn×n regularund seien b ∈ Rn \ 0 und ∆b ∈ Rn. Sei x∗ die Losung von Ax = b und x∗+ ∆xdie Losung von Ax = b+ ∆b. Dann ist x∗ 6= 0 und es gilt

‖∆x‖‖x∗‖

≤ κ(A)‖∆b‖‖b‖

5.12 (Herleitung der Abschatzung). Man hat ‖∆x‖ = ‖A−1∆b‖ ≤ ‖A−1‖ · ‖∆b‖. Esgilt ‖b‖ = ‖Ax∗‖ ≤ ‖A‖ · ‖x∗‖. Ist b 6= 0, dann ist x∗ 6= 0 da die Matrix A regular ist.Die Kombination der beiden vorigen Ungleichungen ergibt die Behauptung.

5.13. Wie man aus dem vorigen Theorem sieht, wirkt im Fall der Storung der rechtenSeite die Konditionszahl als eine Art Zoomfaktor fur den relativen Fehler. Je großerκ(A), desto schlechter ist die Qualitat (Approximationseigenschaften) der ermitteltennumerischen Losung.

5.14. Ist A Orthogonalmatrix, sodass A>A = In gilt, dann gilt κ(A) = 1. Das ist derkleinste mogliche Wert der Konditionszahl.

5.15. Wenn man die Matrix A mit einem Wert λ ∈ R \ 0 multipliziert, bleibt dieKonditionszahl unverandert: κ(λA) = κ(A). Bei der Konditionszahl geht also nichtdarum, wie groß die Komponenten von A sind.

5. GESTORTE MATRIZEN UND LINEARE GLEICHUNGSSYSTEME 95

5.16. Nun wollen wir analog absoluten und relativen Fehler bei der Storung der linkenSeite abschatzen. Dafur werden wir die folgende Hilfsaussage benotigen.

5.17 (Summe unendlicher geometrischer Reihen fur Matrizen). Sei B ∈ Rn×n mit‖B‖ < 1. Dann ist In −B regular und es gilt

(In −B)−1 =∞∑i=0

Bi

Das heißt, fur Sk :=∑k

i=0Bi gilt ‖(In −B)−1 − Sk‖ → 0 fur k →∞.

5.18 (Herleitung der Formel). In − B ist regular, denn sonst wurde man ein x 6= 0mit (In−B)x = 0 finden. Das ergibt Bx = x. OBdA konnen wir ‖x‖ = 1 annehmen.Das ergibt ‖B‖ ≥ 1, was der Annahme ‖B‖ < 1 widerspricht.

Es gilt

‖(In −B)−1 −k∑i=0

Bi‖ ≤ ‖(In −B)−1‖ · ‖In − (In −B)k∑i=0

Bi‖.

Hierbei ist

In − (In −B)k∑i=0

Bi = In − (In −Bk+1) = Bk+1.

Man hat‖Bk+1‖ ≤ ‖B‖k → 0 fur k →∞.

5.19. Ist A eine Matrix, die nah zu einer Einheitsmatrix ist, so konnen wir 5.17 zuriterativen Losung von Ax = b benutzen. Man fuhrt B mit A = In − B ein. Dann istdie Losung als

x = (In −B)−1b =∞∑i=0

Bib =

Wir konnen nun die Summe Skb =∑k

i=0Bib iterativ ausrechnen. Wenn wir Bkb und

Skb bereits ausgerechnet haben, so erhalten wir Sk+1b und Sk+1b aus Bk+1b = BBkbund Sk+1b = Skb + Bk+1b. Pro Iteration braucht man somit O(n2) Operationen.Die Qualitat der Abschatzung in der k-ten Iteration kann mit der Verwendung dervorigen Herleitung durch ‖(In − B)−1‖‖B‖k+1‖b‖ abgeschatzt werden. Ist ‖B‖ kleinund ‖b‖ nicht zu groß, so erhalten wir recht schnell eine gute Approximationsqualitat.Ahnliche allgemeinere Verfahren werden im nachsten Abschnitt behandelt.

5.20 Thm (Relativer Fehler bei Storung der linken Seite). Seien A,∆A ∈ Rn×n

und b ∈ Rn \ 0. Sei A regular und sei

‖∆A‖‖A‖

<1

κ(A).

Dann ist die Matrix A+∆A ebenfalls regular und, fur die Losungen x∗ von Ax = b


und x∗ + ∆x von (A+ ∆A)x = b, gilt die folgende Abschatzung:

‖∆x‖‖x∗‖

≤κ(A)2 ‖∆A‖

‖A‖

1− κ(A)‖∆A‖‖A‖

.

5.21 (Herleitung der Abschatzung). Wir zeigen zuerst, dass A+∆A regular ist. Dafurreicht es zu zeigen, dass A−1(A + ∆A) regular ist. Man hat A−1(A + ∆A) = In − Bmit B = −A−1∆A. Nach 5.17 reicht fur die Regularitat ‖A−1∆A‖ < 1 aus.

Die Voraussetzung ergibt ‖A−1∆A‖ ≤ ‖A−1‖ · ‖∆A‖ < 1.(a): Aus x∗ = A−1b und x∗ + ∆x = (A+ ∆A)−1b folgt

‖(A+ ∆A)−1b− A−1b‖ ≤ ‖(A+ ∆A)−1 − A−1‖ · ‖b‖.

Man hat A+ ∆A = A(In +A−1∆A). Das ergibt (A+ ∆A)−1 = (In +A−1∆A)−1A−1,woraus wir

‖(A+ ∆A)−1b− A−1b‖ ≤ ‖(In + A−1∆A)−1‖ · ‖A−1‖ · ‖b‖

erhalten. Mit der Verwendung von 5.17 erhalten wir die Abschatzung

‖(In + A−1∆A)−1 − In‖ = ‖(In −B)−1 − In‖

= ‖∞∑i=0

Bi − In‖

= ‖∞∑i=1

Bi‖

≤∞∑i=1

‖B‖i

≤∞∑i=1

(‖A−1‖ · ‖∆A‖)i

=‖A−1‖ · ‖∆A‖

1− ‖∆A‖ · ‖A−1‖

=κ(A)‖∆A‖‖A‖

1− κ(A)‖∆A‖‖A‖

Des Weiteren gilt ‖b‖ = ‖Ax∗‖ ≤ ‖A‖ ·‖x∗‖. Die Kombination der oben hergeleitetenUngleichungen ergibt die Behauptung.

5.22. Was stort die Losung mehr: Storung der linken Seite oder Storung der rechtenSeite?

5.23. Beispiel einer schlecht konditionierten Matrix.

TODO: Im Aufbau

6. ITERATIVE LOSUNGSVERFAHREN FUR GLEICHUNGSYSTEME 97

5.24 Thm (Relativer Fehler bei Storung der linken und rechten Seite). Sei A ∈Rn×n regular sei ∆A ∈ Rn×n Matrix mit

‖∆A‖‖A‖

≤ 1

κ(A).

sei b ∈ Rn \ 0 und ∆b ∈ Rn. Dann gilt: die Matrix A + ∆A is regular und furdie Losung x∗ von Ax = b und die Losung x∗+ ∆x von (A+ ∆A)x = b+ ∆b giltdie Abschatzung

‖∆x‖‖x∗‖

≤κ(A)2 ‖∆A‖

‖A‖

1− κ(A)‖∆A‖‖A‖

+ κ(A)‖∆b‖‖b‖

.

5.25. Theorem 5.24 folgt aus Theorem 5.11 und Theorem 5.20.

6 Iterative Losungsverfahren fur Gleichungsyste-

me

6.1. Wenn man die Losung einer Gleichung oder eines Gleichungsystem als die Fix-punktaufgabe F (x) = x formuliert (das heißt, F : Rn → Rn ist eine Abbildungund wir sind auf der Suche nach einem Fixpunkt dieser Abbildung, also nach einemPunkt, den die Abbildung nicht verandert), so kann man unter bestimmten Voraus-setzungen die folgende Methode zur Losung von F (x) = x benutzen. Man startet miteinem beliebigen x0 ∈ Rn und berechnen iterative xk durch xk+1 = F (xk). Auf die-ser Idee basieren viele iterative Verfahren zur Losung von linearen und nichtlinearenGleichungen und Gleichungssystemen.

6.2 Def. Eine Paar (X, ρ) mit einer nichtleerer Menge X und einer Funktionρ : X ×X → R+ heißt metrischer Raum, wenn

(a) ρ(x, y) = ρ(y, x) (Symmetrie)

(b) ρ(x, y) = 0 ⇐⇒ x = y

(c) ρ(x, y) ≤ ρ(x, t) + ρ(t, y) (Dreiecksungleichung)

fur alle x, y, t ∈ X erfullt ist. Die Funktion ρ heißt Metrik auf X.

6.3. Jeder normierte Raum mit einer Metrik ‖ . ‖ ist auch ein metrischer Raum mitder Metrik ρ(x, y) = ‖x− y‖. Es gibt aber auch viele andere metrische Raume.

6.4 Def. Man sagt, dass eine Folge (xk) gegen x∗ in der Metrik ρ konvergiert,wenn ρ(xk, x

∗)→ 0 fur k →∞ erfullt ist.


6.5 Def. Eine Folge (xk) heißt Cauchy-Folge, wenn fur alle jedes ε > 0 ein N ∈ Nexistiert derart, dass ρ(xk, xl) < ε fur alle k, l ≥ N erfullt ist.

6.6. Cauchy-Folge ist eine Folge mit der Eigenschaft, dass ρ(xk, xl) gegen 0 geht, wellk und l beide zusammen gegen 0 gehen.

6.7. Alle konvergenten Folgen sind Cauchy-Folgen.

6.8. Beispiel eines metrischen Raums, in dem man nichtkonvergente Cauchy-Folgenhat (rationale Zahlen mit Betragsmetrik usw.)

6.9. Ein metrischer Raum, in dem jede Cauchy-Folge konvergiert, heißt vollstandig.

6.10. Vollstandige metrische Raume sind Raume ohne ‘Locher’.

6.11 Def. Eine Abbildung F : X → X auf eines metrischen Raums (X, ρ) heißtKontraktion, wenn fur eine Konstante 0 ≤ c < 1 die Ungleichung ρ(F (x), F (y)) ≤cρ(x, y) fur alle x, y ∈ X erfullt ist.

6.12. Kontraktion bringt Punkte des metrischen Raums naher zueinander, wobei manfur den gesamten Raum einen uniformen Faktor hat, um welchen sich die Abstandemindestens verkurzen.

6.13 Def. x ∈ X heißt Fixpunkt einer Abbildung F : X → X wenn F (x) = xerfullt ist.

6.14. Ist (X, ρ) vollstandiger metrischer Raum und F : X → X kontrahierend, sogilt Folgendes:

(a) F besitzt einen eindeutigen Fixpunkt konvergiert

(b) jede Folge (xk) mit xk+1 = F (xk) gegen den Fixpunkt von F .

6.15. Man kann im folgenden Netzwerk die PageRanks durch das iterative Verfahrenwie oben ausrechnen.

1

2 3 4

5

TODO: Technisches Problem Bogen von 4 zu 2 und von 2 zu 1 ohne Pfeil, warum?

6. ITERATIVE LOSUNGSVERFAHREN FUR GLEICHUNGSYSTEME 99

Unser Raum ist x1 +x2 +x3 +x4 +x5 = 1, hierbei ist die xi der Anteil der Teilnehmerauf der Seite 1. Die Abbildung F ist F (x) = Mx, mit

M =

0.000000000000000 0.500000000000000 0.333333333333333 0.000000000000000 0.0000000000000000.500000000000000 0.000000000000000 0.000000000000000 0.500000000000000 0.0000000000000000.000000000000000 0.500000000000000 0.000000000000000 0.000000000000000 0.0000000000000000.000000000000000 0.000000000000000 0.333333333333333 0.000000000000000 1.000000000000000.500000000000000 0.000000000000000 0.333333333333333 0.500000000000000 0.000000000000000

Resultate des iterativen Verfahrens:

(1.00000000000000, 0.000000000000000, 0.000000000000000, 0.000000000000000, 0.000000000000000)(0.000000000000000, 0.500000000000000, 0.000000000000000, 0.000000000000000, 0.500000000000000)(0.250000000000000, 0.000000000000000, 0.250000000000000, 0.500000000000000, 0.000000000000000)

(0.0833333333333333, 0.375000000000000, 0.000000000000000, 0.0833333333333333, 0.458333333333333)(0.187500000000000, 0.0833333333333333, 0.187500000000000, 0.458333333333333, 0.0833333333333333)(0.104166666666667, 0.322916666666667, 0.0416666666666667, 0.145833333333333, 0.385416666666667)(0.175347222222222, 0.125000000000000, 0.161458333333333, 0.399305555555556, 0.138888888888889)(0.116319444444444, 0.287326388888889, 0.0625000000000000, 0.192708333333333, 0.341145833333333)(0.164496527777778, 0.154513888888889, 0.143663194444444, 0.361979166666667, 0.175347222222222)(0.125144675925926, 0.263237847222222, 0.0772569444444444, 0.223234953703704, 0.311125578703704)(0.157371238425926, 0.174189814814815, 0.131618923611111, 0.336877893518518, 0.199942129629630)(0.130967881944444, 0.247124565972222, 0.0870949074074074, 0.243815104166667, 0.290997540509259)(0.152593918788580, 0.187391493055556, 0.123562282986111, 0.320029176311728, 0.216423128858025)(0.134883174189815, 0.236311547550154, 0.0936957465277778, 0.257610556520062, 0.277498975212191)(0.149387689284336, 0.196246865354938, 0.118155773775077, 0.308730890721451, 0.227478780864198)(0.137508690602495, 0.229059290002893, 0.0981234326774691, 0.266864038789223, 0.268444547927919)(0.147237455893936, 0.202186364695859, 0.114529645001447, 0.301152358820409, 0.234894175588349)(0.139269730681745, 0.224194907357173, 0.101093182347930, 0.273070723922164, 0.262371455690988)(0.145795181127896, 0.206170227301955, 0.112097453678586, 0.296069183140298, 0.239867954751265)(0.140450931543839, 0.220932182134097, 0.103085113650977, 0.277233772644127, 0.258298000026959)(0.144827795617374, 0.208842352093983, 0.110466091067049, 0.292659704577285, 0.243204056644309)(0.141243206402674, 0.218743750097330, 0.104421176046992, 0.280026086999992, 0.255565780453013)(0.144178933730995, 0.210634646701333, 0.109371875048665, 0.290372839135343, 0.245441705383664)(0.141774615033555, 0.217275886433169, 0.105317323350667, 0.281898997066552, 0.253733178116058)(0.143743717666807, 0.211836806050053, 0.108637943216585, 0.288838952566280, 0.246942580500276)(0.142131050763888, 0.216291335116543, 0.105918403025027, 0.283155228239137, 0.252503982855405)(0.143451801899947, 0.212643139501513, 0.108145667558272, 0.287810117197080, 0.247949273843188)(0.142370125603514, 0.215630959548514, 0.106321569750756, 0.283997829695945, 0.251679515401271)(0.143256003024509, 0.213183977649729, 0.107815479774257, 0.287120038651523, 0.248624500899982)(0.142530482082950, 0.215188020838016, 0.106591988824865, 0.284562994158067, 0.251126514096102)(0.143124673360630, 0.213546738120509, 0.107594010419008, 0.286657177037723, 0.249077401062130)

6.16. Abschatzung der Konvergenz bei der iterativen Berechnung des Fixpunktes(vgl. Rudin)

TODO: Im Aufbau: ‖x∗ − xk‖ ≤ ck

1−c‖x0 − x1‖

6.17 (Jacobi-Verfahren). Wir losen das System Ax = y. Wir zerlegen die Matrix inden Diagonalanteil A und den Rest. Das heißt, A wird als Summe A = D + C einerDiagonalmatrix D dargestellt und einer Matrix C, die auf der Diagonale Nullen hat.Wir setzen voraus,dass alle Diagonalelemente von A ungleich Null sind. Diese Elemen-te werden in D aufgehoben. Das heißt, D hat auf der Diagonale Nichtnullelemente.Wir konnen also D invertieren (Inversion einer Diagonalmatrix ist einfach). Dadurchwird Ax = y in die Form D−1Ax = D−1y uberfuhrt, wobei D−1A = In + D−1Cgilt. Das heißt unsere Aufgabe ist die Fixpunktaufgabe F (x) = x fur die AbbildungF (x) = D−1(y − Cx). Ist die Norm von Operatornorm ‖D−1C‖ echt kleiner 1, dannist die Abbildung F kontrahierend, sodass das Verfahren aus 6.1 eine zur Losung vonAx = y konvergente Folge ergibt.

6.18 (Wahl der Operatornorm im Jacobi-Verfahren). Die Berechnung der Spektral-norm ist keine Einfache Aufgabe. Es ist also schwierig die Kontraktionseingenschaft


bezuglich der Spektralnorm zu testen. Der Test ist viel einfacher fur die Operatornormzur Maximumnorm in Rn. Die Maximum-Norm eines Vektors x = (x1, . . . , xn) ∈ Rn

ist‖x‖ = max|x1|, . . . , |xn|.

Die entsprechende Operatornorm von A = (aij) ∈ Rn×n ist

‖A‖ = maxi=1,...,n

n∑j=1

|aij|.

6.19 Def. Eine Matrix A heißt strikt diagonaldominant, wenn fur jede Zeile derBetrag des Diagonalelementes hoher als die Summer der Betrage der Elementeaußerhalb der Diagonale ist.

6.20. Die Abbildung F aus dem Jacobi-Verfahren ist kontrahierend bzgl. der Maxi-mumnorm, wenn die Matrix A strikt diagonaldominant ist.

6.21 Thm. Sei A ∈ Rn×n strikt diagonaldominant. Dann ist A regular und furalle b ∈ Rn konvergiert die Folge der Vektoren aus dem Jacobi-Verfahren gegendie eindeutige Losung des LGS Ax = b.

6.22 (Gauß-Seidel-Verfahren). Die Matrix A = (aij)i,j=1,...,n wird als Summe A =L + D + U dargestellt, wobei L die Matrix, die nur unterhalb der Diagonale nicht-nulleintrage haben kann, D eine Diagonmatrix und U ist die Matrix die nur ober-halb der Diagonale Nichnulleintrage haben kann. Wir setzen wieder voraus dass al-le Diagonalelemente von A ungleich null sind. Somit ist D + U eine invertierbareobere Dreicksmatrix, und ihre Inverse (D + U)−1 lasst sich schnell berechnen (derAufwand ist quadratisch in n). Wir schreiben das System Ax = y in der Form(D + U)−1Ax = (D + U)−1y um. Weil A die Summe von L und D + U ist, kanndie letzte Matrizengleichung als ((D + U)−1L + I)x = (D + U)−1y umgeschreibenwerden, oder auch als x = (D + U)−1(y − Lx).

Wir suchen also eine Losung x von x = F (x) mit F (x) = (D+U)−1(y−Lx). Manstartet mit einem Vektor x0 ∈ Rn und wendet die Operation xk+1 = F (xk) iterativan. xk+1 ist durch die Gleichung xk+1 = (D + U)−1(y − Lxk) gegeben. Das heißt,das unbekannte xk+1 wird durch das Losen des LGS (D + U)xk+1) = y − Lxk in deroberen Dreieckform mit Hilfe von O(n2) Operationen gelost.

6.23 Thm. Sei A ∈ Rn×n strikt diagonaldominant. Dann ist A regular und, furjedes b ∈ Rn konvergiert die folge der Vektoren aus dem Gauß-Seidel-Verfahrengegen die eindeutige von Ax = b.

6.24 (Vergleich mit nichtiterativen Verfahren). Zur Ausfuhrung von k Iterationen deriterativen Verfahren wie oben benotigen wir kΘ(n2) Operationen, weil jede Iterationden Rechenaufwand Θ(n2) hat. Das nichtiterative Gauß-Verfahren wie das Gauß-Verfahren benotigt Θ(n3) Operationen. Fur sehr große n ist das Gauß-Verfahren

7. NUMERISCHE LOSUNG NICHTLINEARER GLEICHUNGSSYSTEME 101

nicht mehr praktisch anwendbar. Bei iterativen Gauß-Verfahren dagegen, kann manschon nach recht wenigen Iterationen (3 − 5 Iterationen) gute Approximation derLosung erreichen und terminieren. Bei einer festen Anzahl der Iterationen ist derRechenaufwand der iterativen Verfahren quadratisch in n.

6.25. Oft muss man in der Praxis lineare Gleichungsysteme mit den dunnbesetztenlinken Seiten losen. Die oben prasentierten Verfahren lassen sich im dunnbesetztenFall direkt beschleunigen, da in diesen Fallen die Auswertung der zugrundeliegendenKontraktion F einen geringeren Rechenaufwand hat.

6.26 (Geht es besser als kubisch?). In der Theorie hat man sich mit der Fragebeschaftigt, ob man ein LGS der Große n mit einem geringeren Rechenaufwand alsΘ(n3) exakt losen kann. Erstaunlicherweise ist das tatsachlich der Fall. Es gibt Re-chenverfahren mit Aufwand Θ(np) mit 2 < p < 3. Solche Verfahren wird in dernumerischen Mathematik meistens nicht benutzt, weil sie numerisch instabil sind. Siekonnen aber im nichtnumerischen Kontext interessant sein (z.B., Losen der LGS bzgl.endlicher Korper oder in exakter Arithmetik).

6.27 (Verbluffende Vermutung). Fur jedes p > 2, gibt es ein Verfahren, dass einlineares Gleichungsystem der Große n mit O(np) Operationen lost (dazu gab es einenVortrag in SIAM Conference on Applied Algebra and Geometry). Salopp gesagt:es wird vermutet, dass man ein fast quadratisches Verfahren zur Losung von LGSexistiert.

7 Numerische Losung nichtlinearer Gleichungssy-

steme

7.1 Thm. Sei f : U → R Funktion auf einer offenen Teilmenge U von R undsei x∗ ∈ U eine Nullstelle von f (d.h., f(x∗) = 0). Angenommen, es existierteine Umgebung I = (x∗ − ρ, x∗ + ρ) ⊆ U von x∗ mit ρ > 0 derart, dass indieser Umgebung die Funktion f zweimal differenzierbar ist und daruber hinausdie folgenden zwei Bedingungen erfullt sind:

• Fur ein a > 0 gilt |f ′(x)| ≥ a fur alle x ∈ I.

• Fur ein b > 0 gilt |f ′′(x)| ≤ b fur alle x ∈ I.

Sei ρ0 := minρ, ab und sei x0 ∈ (x∗−ρ0, x

∗+ρ0). Dann existiert eine eindeutigeFolge (xk)k∈N mit Werten aus (x∗−ρ0, x

∗+ρ0), in welcher xk mit Hilfe von xk−1

aus der Gleichungf(xk−1) + f ′(xk−1)(xk − xk−1) = 0

bestimmt ist. Die Folge (xk)k∈N konvergiert gegen x∗ mit der Konvergenzgeschwin-digkeit

|xk − x∗| ≤ ρ0

(|x0 − x∗|

ρ0

)2k

. (III.9)

7.2 (Interpretation). Newton-Verfahren konvergiert, wenn dar Startwert bereits nahgenug an einer Nullstelle ist und die Funktion in der Umgebung der Nullstelle re-


gelmaßig genug ist (erste Ableitung betragsmaßig nicht zu kleine, und die zweiteAbleitung betragsmaßig nicht zu groß).

7.3 (Konvergenz-Geschwindigkeit). Grob beschrieben: die Anzahl der korrekten Nach-kommastellen verdoppelt sich (in etwa) mit jeder Iteration.

7.4 (Sekanten-Verfahren). Es ist nicht immer wunschenswert oder sogar moglich dieerste Ableitung von f zu berechnen. Z.B. ist f nicht immer explizit gegeben. DasNewton-Verfahren lasst sich zu einem sogenannten Sekanten-Verfahren modifizieren.Im Sekanten-Verfahren wird die die Ableitung f ′(xk) an der Stelle durch den Quoti-enten

f(xk)− f(xk−1)

xk − xk−1

approximiert. Somit ergibt sich xk+1 im Sekanten-Verfahren xk+1 aus der Gleichung

f(xk) +f(xk)− f(xk−1)

xk − xk−1

(xk+1 − xk) = 0.

Um die Iteration zu starten benotigt man zwei Anfangswerte x0 und x1. Die Rah-menbedingungen zur Anwendung des Sekanten-Verfahren sind ahnlich (Anfangswertenah genug an der Nullstellen, Funktion regelmaßig genug im Sinne von Newton-Verfahren). Die Konvergenz-Eigenschaften vom Sekanten-Verfahren sind ebenfallsahnlich (die Anzahl der korrekten Nachkommastellen vergroßert sich um einen fe-sten Faktor, der etwas kleiner als 2 ist, mit jeder Iteration).

Kapitel IV

GewohnlicheDifferentialgleichungen

1 Grundlagen

1.1 (GDGs). GDLs sind Gleichungen fur eine unbekannte Funktion einer Variablenund ihre Ableitungen. Wenn man zusatlich an an einer Stelle den Wert der Funktionund/oder ihrer Ableitungen vorgibt spricht man von einem Anfangswert problem.

Eine Gleichung der Form F (t, x(t), x′(t), . . . , x(n)(t)) = 0 nennt man eine GDL.

Formulierung einer Gleichung einer expliziten Gleichung, eines Anfangwertpro-blems. GDLs hat man direkt in physykalischen und okonomischen Anwendungen.

1.2 (Eine Interpretation der Gleichung x′(t) = F (x(t))). Man fahrt eine besondereAutobahn. x(t) ist die Position, in der man sich zum Zeitpunkt t befindet. In derPosition p wird vorgeschrieben genau F (p) kmh zu fahren. Angenommen, x(0) istbekannt. Wie sieht dann die Funktion x′(t) aus.

Grafik zeichnen. Achse t nach rechts, achse x (Position) nach oben. Cahse F (x)nach links. x 7→ F (x) zeichnen (etwa, Strecke 100 kmh, Strecke 50 kmh, Strecke100kmh) und dann das entrsprechende x herleiten.

1.3 (Eine Interpretation der Gleichung x′(t) = F (x(t), t))). Wie oben aber man hatauch Zeitregimen (sagen wir mal, in der Nach eine andere als am Tag).

1.4 (Losung der Gleichung x′(t) = kx(t)). Wenn x(t) auf [t0, t1] das die Bedingungx(t) 6= 0 erfullt, findet man die Losungen schnell. Es ist bekannt dass, wenn x(t) = 0ist, dann ist x(t) = 0 auf dem gesamten [t0, t1]. Aslo hat man alle Losungen gefunden.

1.5 Thm (Existenz und Eindeutigkeit).

1.6 (Trennung von Variablen).

103

104 KAPITEL IV. GEWOHNLICHE DIFFERENTIALGLEICHUNGEN

2 Lineare Gleichungen

2.1 (Lineare GDGs erster Ordnung).

2.2 (Homogene lineare Gleichungen mit Konstanten Koeffizienten). Wir benutzenden Korper C der komplexen Zahlen. Unter anderem steht i fur die imaginare Einheit;es gilt i2 = −1. In diesem Unterabschnitt behandeln wir GDGs fur Funktionen in einerreellen Variablen mit komplexen Werten. Wir fuhren die Funktion eit = cos(t)+i sin(t)

ein. Es gilt naturlich cos(t) = eit+e−it

2und sin(t) = eit−e−it

2i.

Seien a0, . . . , an−1 ∈ C geben. Wir wollen die Losungsmenge der GDG

y(n) + an−1y(n−1) + · · ·+ a0y

(0) = 0.

beschreiben.

2.3 Bsp. Losen wir die Gleichung

y′′ − 3y′ + 2y = 0.

Wir werden diese Gleichung erstmal umschrieben.Operatoren sind Transformationen, die Funktionen auf Funktionen abbilden. Wir

fuhren den idetnischen Operator I, der ‘nichts tut’: Iy = y. Wir fuhren den Opera-tor des Differenzierens: Dy = y′. Von Operatoren konnen wir Linearkombinationenbilden. Etwa (2D + 3I)y = 2Dy + 3Iy = 2y′ + 3y. Ansonsten kann man

Operatoren, das entspricht dem Hintereinanderausfuhren der Operatoren: Etwa(2D+ 3I)D macht Folgendes: (2D+ 3I)Dy = (2D+ 3I)y′ = 2Dy′+ 3Iy′ = 2y′′+ 3y′.

Unsere Differentialgleichung kann als

(D2 − 3D + 2I)y = 0.

Nun, die entscheidende Idee: der Operatora auf der linken Seite kann als Produktgeschrieben werden: D2 − 3D + 2I = (D − 2I)(D − I). D.h., wir losen

(D − 2I)(D − I)y = 0.

Man sieht, dass jede Losung von (D−I)y = 0 auch eine Losung unserer Gleichungist.

Denn aus (D − I)y = 0 folgt (D − 2I)(D − I)y = (D − 3I)0 = 0.Genau so ist jede Losung von (D− 2I)y eine Losung unserer Gleichung ist. Denn

(D−2I)(D−I)y = (D−I)(D−2I)y und aus (D−2I)y = 0 folgt (D−I)(D−2I)y =(D − I)0 = 0.

Es steht sich heraus, dass man im wesentlichen keien anderen Losungen hat. Jedelinear kombination einer Losung von (D − I)y und einer Losung von (D − 2I)y isteine Losung unserer Gleichung, andere Losung hat man nicht.

Wir wir wissen, hat jede Losunge von (D − I)y die Form y = cex mit c ∈ R undjede Losung von (D − 2I)y die Form y = ce2x mit c ∈ R. Daher ist c1e

x + c2e2x die

Losung unserer ursprunglichen Gleichung.

2.4 Bsp. Betrachten wir die Gleichung y′′ + y = 0. Die kann man wie im vorigenBeispiel als (D2 + I)y = 0 umschreiben. Man kann D2 + I nicht uber reellen Zahlenfaktorisieren, weil bei den reellen Zahlen die Wurzel aus −1 fehlt. Wir gehen deswegen

2. LINEARE GLEICHUNGEN 105

zu den komplexen Zahlen ruber und benutzen die imaginare Einheit i; die komplexeZahl mit i2 = −1. Mit dieser Zahl kann man D2 + I als D2 + I = (D + iI)(D − iI)faktorisieren. Nun reduziert sich, wie im vorigen Beispiel, das Losen von (D2+I)y = 0zum Losen von zwei Gleichungen (D + iI)y = 0 und (D − iI)y.

(D − iI)y = 0 ist y′ − iy = 0.Als wir noch bei den reellen Zahlen waren, war die Losung von y′ + ky = 0 die

Funktion y(x) = ce−kx mit c ∈ R. Das heißt die Losung von y′ − iy = 0 musste dieForm y(x) = ceix haben, es bleibt ‘nur’ noch zu klaren, wie eix definiert werden muss.Das hat Euler fur uns schon geklart: eix = cos(x)+i sin(x). Um zu testen, dass das eineSinnvolle Definition ist, nehmen wir die erste Ableitung: (eix)′ = cos(x)′ + i sin(x)′ =− sin(x) + i cos(x) = i(cos(x) + i sin(x)) = ieix. Die Formel (eix)′ = ieix ist unseigentlich bereits aus der ‘reellen Welt’ bekannt, wo man an der Stelle von i einereelle Zahl haben wurde.

So erhalten wir die folgende Losung fur unser usrpungliches System y(x) = c1eix+

c2e−ix. Das ist eine Schar von Funktionen. Die Variable x ist reell. Die Werte der Funk-

tion y(x) sind komplexe Zahlen. Wenn wir in die “reelle Welt” zuruckkehren wollen,dann mussen wir uns uberlegen, wie wir die komplexwertigen Funktion eix durch reell-wertige Funktion ersetzen konnen. eix = cos(x)+ i sin(x) und e−ix = cos(x)− i sin(x).Das zeigt, dass man die Losungen auch als y(x) = a1 cos(x) + a2 sin(x) schreibenkann. Hierbei sind a1, a2 Konstanten. Wenn wir nur die reellen Konstakten zulassen,haben wir eine reellwertige Funtkion als Losung.

Die Losungschar, die wir prasentiert haben, haben wir ein mal als lineare Hullevon Funktionen eix und e−ix und ein weiteres Mal als lineare Hulle von Funktionencos(x) und sin(x). Das sind zwei unterschiedliche Basen des selben Vektorraums allerLosungen von y′′ + y = 0.

2.5 Bsp. Man betrachte y′′−6y′+9y = 0. Wird umgeschrieben als D2−6Dy+9Iy =(D2 − 6D + 9I)y = 0, wobei D2 − 6D + 9I = (D − 3)2. Also (D − 3I)2y = 0 undjede Losung von (D − 3I)y = 0 ist auch eine Losung von (D − 3I)y, d.h., e3x isteine Losung. Gibt es eine andere wirklich andere Losung. Es ist intuitiv klar, das eseine anndere Losung geben muss. Denn man muss in der allgemeinen Losung zweiFreihatsgrade haben (Wahl von y(x0) und Wahl von y′(x0)).

Ja: xe3x. Wir testen sie: (D − 3I)(xe3x) = e3x + x3e3x − 3xe3x = e3x. Und (D −3I)(e3x) = 0, wie wir wissen. Die allgemeine Losung ist Linearkombination von e3x

und xe3x mit konstanten Koeffizienten.

2.6 Bsp (Inhomogene lineare Gleichungen mit konstanten Koeffizienten). y′′ + y =cos(x).

Die allgemeine Losung der homogenen Gleichung dazu ist Linearkombination voncos(x) und sin(x) mit Konstanten koeffizienten.

Nun sucht man die Losung der inhomogenen Gleichung auf folgende Weise: dieLosung sucht man in der Form C1(x) cos(x) +C2(x) sin(x). D.h., die konstanten wer-den variiert. Und fur c′1(x) und c′2(x) werden die folgenden Gleichungen aufgestellt:

cos(x)C ′1(x) + sin(x)C ′2(x) = 0 und (cos(x))′C1(x) + (sin(x))′C ′2(x) = cos(x).

106 KAPITEL IV. GEWOHNLICHE DIFFERENTIALGLEICHUNGEN

Kapitel V

Kurven und Flachen

107

108 KAPITEL V. KURVEN UND FLACHEN

Literaturverzeichnis

[AB09] Sanjeev Arora and Boaz Barak, Computational complexity, CambridgeUniversity Press, Cambridge, 2009, A modern approach. MR 2500087

[BT02] Dimitri P Bertsekas and John N Tsitsiklis, Introduction to probability,vol. 1, Athena Scientific Belmont, MA, 2002.

[CLRS09] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and CliffordStein, Introduction to algorithms, third ed., MIT Press, Cambridge, MA,2009. MR 2572804

[Eva13] Lawrence C. Evans, An introduction to stochastic differential equations,American Mathematical Society, Providence, RI, 2013. MR 3154922

[Hen12] Norbert Henze, Stochastik fur Einsteiger, expanded ed., Vieweg + TeubnerVerlag, Wiesbaden, 2012, Eine Einfuhrung in die faszinierende Welt desZufalls. [An introduction to the fascinating world of chance]. MR 2934636

[Rud76] Walter Rudin, Principles of mathematical analysis, third ed., McGraw-Hill Book Co., New York-Auckland-Dusseldorf, 1976, International Seriesin Pure and Applied Mathematics. MR 0385023

[Sze86] Gabor J. Szekely, Paradoxes in probability theory and mathematical stati-stics, Mathematics and its Applications (East European Series), vol. 15,D. Reidel Publishing Co., Dordrecht, 1986, Translated from the Hungarianby Marta Alpar and Eva Unger. MR 880020

[Sze90] , Paradoxa, Verlag Harri Deutsch, Thun, 1990, Klassische undneue Uberraschungen aus Wahrscheinlichkeitsrechnung und mathemati-scher Statistik. MR 1109919

109

Documents

Mathematik 3 - fma2.math.uni-magdeburg.defma2.math.uni-magdeburg.de/~averkov/mathe3info_page/Mathe_3_fuer_In... · Mathematik 3 f ur Informatik G. Averkov Institut fur Mathematische