Mathematik Für Informatiker
Mathematik Für Informatiker
Teil I Grundlagen
5 Konvergenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.1 Folgen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.2 Beispiele für Folgen in der Informatik . . . . . . . . . . . . . . . . . . . . . . 76
5.3 Landau–Symbole (O– und o–Notation) . . . . . . . . . . . . . . . . . . . . . 76
5.4 Aufwandsanalyse der Multiplikation . . . . . . . . . . . . . . . . . . . . . . . 77
5.5 Das Vollständigkeitsaxiom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.6 Quadratwurzeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.7 Zur Existenz der reellen Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.7.1 Cauchy–Folgen modulo Nullfolgen . . . . . . . . . . . . . . . . . . 85
5.7.2 Dedekindsche Schnitte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.8 Der Satz von Bolzano–Weierstrass . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.9 Mächtigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6 Reihen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.1 Definition und erste Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.2 Konvergenzkriterien für Reihen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.3 Umordnung von Reihen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
7 Potenzreihen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.1 Komplexe Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.2 Der Konvergenzradius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.3 Der Umordnungssatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Inhaltsverzeichnis IX
8 Stetigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
8.1 Definition und Folgenkriterium . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
8.2 Der Zwischenwertsatz und Anwendungen . . . . . . . . . . . . . . . . . 129
9 Differentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9.1 Differenzierbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9.2 Rechenregeln für Ableitungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
13 Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
13.1 (Riemann–)Integrierbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
13.2 Stammfunktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
13.3 Elementare Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
22 Determinanten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
22.1 Existenz und Eindeutigkeit der Determinante . . . . . . . . . . . . . . . 299
22.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
22.1.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
22.1.3 Der Determinanten–Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
22.2 Weitere Eigenschaften der Determinante . . . . . . . . . . . . . . . . . . . . 310
22.3 Berechnung von Determinanten . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
25 Hauptachsentransformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
25.1 Symmetrische Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
25.2 Klassifikation von Quadriken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
25.3 Klassifikation von Quadriken im Fall n = 3 . . . . . . . . . . . . . . . . . 356
25.4 Typen von Quadriken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
26 Skalarprodukte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
26.1 Das hermitesche Skalarprodukt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
26.2 Abstrakte Skalarprodukte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
26.3 Das Hurwitz–Kriterium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
26.4 Normen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
26.5 Orthogonale Projektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
27 Fourierreihen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
27.1 Zur Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
27.2 Fourierreihen und Konvergenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
27.3 Besselsche Ungleichung und Vollständigkeitsrelation . . . . . . . . 398
28 Singulärwertzerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
28.1 Die Singulärwertzerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
28.2 Die Pseudoinverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
XII Inhaltsverzeichnis
29 Kurven im Rn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
29.1 Elementare Definitionen und Beispiele . . . . . . . . . . . . . . . . . . . . . 417
29.2 Rektifizierbarkeit und Bogenlänge . . . . . . . . . . . . . . . . . . . . . . . . . 422
29.3 Krümmung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
29.4 Kurven im R3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
33 Integration im Rn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
33.1 Integrale über kompakten Mengen . . . . . . . . . . . . . . . . . . . . . . . . . 481
33.2 Uneigentliche Integrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
34 Grundbegriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
34.1 Wahrscheinlichkeit von Ereignissen . . . . . . . . . . . . . . . . . . . . . . . . 495
34.2 Bedingte Wahrscheinlichkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
34.3 Zufallsvariablen und deren Erwartungswert und Varianz . . . . 500
Inhaltsverzeichnis XIII
39 Statistik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
39.1 Testen von Hypothesen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
39.2 Schätzen von Parametern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
39.3 Parametrisierte Statistik, Konfidenzintervalle . . . . . . . . . . . . . . . 545
39.3.1 σ bekannt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
39.3.2 σ unbekannt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
39.4 Tests auf den Erwartungswert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550
39.4.1 Zweiseitiger Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550
39.4.2 Einseitiger Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551
39.5 χ2 –Test auf die Varianz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552
39.6 χ2 –Verteilungstest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554
39.7 χ2 –Test auf Unabhängigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555
Teil VI Numerik
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631
Symbolverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
Inhaltsverzeichnis XV
Sachverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 639
Abbildungsverzeichnis
4.1 Kommensurabilität. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2 Die Inkommensurabilität am regelmäßigen Fünfeck. . . . . . . . . . . 69
29.1 Die Parametrisierung eines Kreises mit Sinus und Cosinus. . . . 418
29.2 Eine Schraubenlinie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
29.3 Der Newtonsche Knoten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
29.4 Die Neilsche Parabel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
29.5 Eine logarithmische Spirale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
29.6 Ellipsen und Hyperbeln mit gemeinsamen Brennpunkten. . . . . 421
29.7 Polygonapproximation einer Kurve. . . . . . . . . . . . . . . . . . . . . . . . . . 422
29.8 Zur Berechnung der Bogenlänge eines Kreises. . . . . . . . . . . . . . . . 423
29.9 Die Zykloide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
29.10Eine nicht rektifizierbare Kurve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
29.11Zur Definition der Peano-Kurve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
29.12Normalen- und Tangentialvektor am Kreis. . . . . . . . . . . . . . . . . . . 429
29.13Das Fresnelsche Dreibein. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
Grundlagen
5
Einführung
1
Vorlesung vom:
Die Regeln der Logik bilden die Grundlagen der mathematischen Argumen- 22. Oktober 2008
tation. Zu den zentralen Anwendungen in der Informatik gehören: Qualitätsstand:
erste Version
• Schaltkreisentwurf,
• Entwicklung von Programmiersprachen,
• Verifikation von Hard- und Software,
• Suchen in Datenbanken,
• Automatisches Beweisen.
Definition 1.1. Eine logische Aussage ist ein Satz, dem genau ein Wahrheitswert
wahr (w) oder falsch (f) zugeordnet ist.
Beispiel 1.2.
A B ¬A A ∧ B A ∨ B A ⇒ B A ⇐⇒ B
w w f w w w w
w f f f w f f
f w w f w w f
f f w f f w w
Die Reihenfolge bei Ausführung von logischen Operationen legen wir durch
Klammern fest.
Beispiel 1.3.
(A ⇒ B) ⇐⇒ ((¬A) ∨ B) (1.1)
A B A ⇒ B ¬A (¬A) ∨ B (1.1)
w w w f w w
w f f f f w
f w w w w w
f f w w w w
(A ⇒ B) ⇐⇒ ¬A ∨ B.
1.2.2 Tautologien
Definition 1.6. Eine logische Formel ist eine logische Tautologie, wenn sie unab-
hängig von der Belegung von logischen Variablen mit Wahrheitswerten wahr ist.
Beispiel 1.7.
1. (A ⇒ B) ⇐⇒ ((¬A) ∨ B).
2. (A ⇐⇒ B) ⇐⇒ (A ∧ B) ∨ (¬A ∧ ¬B). Dies zeigt die Wahrheitstafel:
A B A ∧ B ¬A ∧ ¬B (A ∧ B) ∨ (¬A ∧ ¬B) A ⇐⇒ B
w w w f w w
w f f f f f
f w f f f f
f f f w w w
¬(A ∧ B) ⇐⇒ ¬A ∨ ¬B,
¬(A ∨ B) ⇐⇒ ¬A ∧ ¬B.
1. A ∨ B ⇐⇒ B ∨ A,
A ∧ B ⇐⇒ B ∧ A (Kommutativgesetz).
2. (A ∨ B) ∨ C ⇐⇒ A ∨ (B ∨ C),
(A ∧ B) ∧ C ⇐⇒ A ∧ (B ∧ C) (Assoziativgesetze).
Also macht A ∨ B ∨ C und A ∧ B ∧ C Sinn.
3. A ∧ (B ∨ C) ⇐⇒ (A ∧ B) ∨ (A ∧ C),
A ∨ (B ∧ C) ⇐⇒ (A ∨ B) ∧ (A ∨ C) (Distributivgesetze)
4. A ∨ f ⇐⇒ A,
A ∧ w ⇐⇒ A (Identitätsgesetze)
5. A ∨ (¬A) ⇐⇒ w (Satz vom ausgeschlossenen Dritten),
A ∧ (¬A) ⇐⇒ f (Satz vom Widerspruch)
6. ¬(A ∧ B) ⇐⇒ ¬A ∨ ¬B,
¬(A ∨ B) ⇐⇒ ¬A ∧ ¬B (de Morgansches Gesetz)
7. ¬(¬A) ⇐⇒ A (Doppelte Verneinung)
8. A ∨ A ⇐⇒ A,
A ∧ A ⇐⇒ A (Idempotenzgesetze)
9. A ⇒ B ⇐⇒ (¬B ⇒ ¬A) (Kontraposition)
10. (A ⇒ B) ∧ (B ⇒ C) ⇒(A ⇒ C) (Transitivität der Implikation)
11. (¬A ⇒ f ) ⇐⇒ A (Widerspruchsbeweis)
Korollar 1.11. Jede logische Formel lässt sich mit Hilfe der Tautologien 1. – 11. aus
dem Satz in konjunktive oder disjunktive Normalform bringen.
1.3 Beweismethoden
Vorlesung vom:
Beweise werden in der Mathematik verwendet, um nachzuweisen, dass ge- 24. Oktober 2008
wisse Sätze wahr sind. Dabei haben Tautologien eine wichtige Rolle. Qualitätsstand:
Wir können z.B. (A ⇒ B) ∧ (B ⇒ C) ⇒(A ⇒ C) benutzen, um aus einem be- erste Version
kannten Satz A den Satz C in zwei Schritten zu beweisen. In der Informatik
werden Beweise beispielsweise verwendet, um:
Der vielleicht älteste Beweis durch Widerspruch findet sich in Euklids Ele-
menten.1 Er handelt von Primzahlen, also natürlichen Zahlen p ∈ N, p > 1,
die nur durch 1 und sich selbst ohne Rest teilbar sind.
Gegeben sei eine Aussage A(n) für jede natürliche Zahl n ∈ N = {1, 2, . . . }.
Problem:
Um die Aussage A(n) für alle n zu zeigen, gehen wir wie folgt vor. Wir zeigen:
Der Begriff Menge
wird hier schon ge- 1. A(1) gilt. (Induktionsanfang),
braucht, obwohl wir
erst im zweiten Kapi- 2. Für beliebiges n folgt unter der Voraussetzung, dass A(n) gilt (genannt
tel darauf eingehen! Induktionsvoraussetzung oder kurz I.-V.), dass auch A(n + 1) zutrifft
(Induktionsschritt). Dies wird häufig auch kurz n → n + 1geschrieben.
Problem:
to do: mündlich: alle Ist dies getan, so wissen wir:
Hörer haben das glei-
che Geschlecht A(1) ist wahr ⇒ A(2) ist wahr ⇒ A(3) ist wahr ⇒ · · ·
Also ist A(n) wahr für alle n. Diese Beweistechnik heißt vollständige Induk-
tion.
n(n + 1)
A(n) : 1 + 2 + · · · + n = .
2
1·(1+1)
Beweis. A(1) : 1 = 2 , d.h. A(1) ist wahr.
Für den Induktionsschritt n → n + 1 dürfen wir also annehmen, dass die
Induktionsvoraussetzung A(n) für ein n ∈ N wahr ist. Damit folgt:
1 + 2 + · · · + n + n + 1 = (1 + 2 + · · · + n) + (n + 1)
I.−V. n(n + 1)
= + (n + 1)
2
n+2
= (n + 1) · .
2
Dies zeigt: A(n + 1).
Ein alternativer Beweis ist folgender:
1 +2 + ··· +n
n + (n − 1) + ··· +1
= (n + 1) + (n + 1) + ··· + (n + 1)
Bemerkung 1.14. Das Induktionsprinzip ist eine Aussage, die unsere Vorstel-
lung von natürlichen Zahlen präzisiert: Ist M ⊂ N,so dass gilt2 :
2
⊂ bezeichnet eine Teilmenge, ⊊ bezeichnet eine echte Teilmenge, d.h. eine Teil-
menge, die nicht die ganze Menge ist.
1.3 Beweismethoden 13
so folgt: M = N.
Eine dazu äquivalente Aussage ist: Jede nicht leere Teilmenge N ⊂ N hat ein
kleinstes Element. Betrachte N = N\M.
Problem:
zu knapp?
Definition 1.15. Sei M eine Menge. Dann bezeichnet
2M := {N | N ⊂ M}
die Menge aller Teilmengen von M, die sogenannte Potenzmenge von M. Manchmal
wird statt 2M auch P(M)geschrieben.
Ist M eine endliche Menge, dann bezeichnet |M| die Anzahl der Elemente von M.
|2M | = 2|M| .
Beispiel 1.17.
Beweis (von Satz 1.16). Ohne Einschränkung der Allgemeinheit können wir
annehmen, dass M = {1, 2, . . . , n}.
Induktionsanfang: ist bereits erbracht für n = 0 oder n = 1.
Induktionsschritt n → n + 1:
Dabei bezeichnet die Notation ∪· die Vereinigung zweier Mengen, die disjunkt
sind (also kein Element gemeinsam haben, siehe auch Abschnitt 2.4). Es folgt:
{ }
|2{1,...,n+1} | = 2{1,...,n} + N | N = N′ ∪ {n + 1}, N′ ∈ 2{1,...,n}
= |2{1,...,n} | + |2{1,...,n} |
I.−V.
= 2n + 2n = 2 · 2n = 2n+1
= 2|{1,...,n+1}| .
⊓
⊔
14 1 Logik und Beweismethoden
∑0
Präzise: k=1 ak := 0 (leere Summe) und rekursiv:
∑
n (∑
n−1 )
ak := ak + an .
k=1 k=1
∏
n (∏
n−1 )
ak = ak · an .
k=1 k=1
∑
n
n(n + 1)(2n + 1)
k2 = .
6
k=1
∑
1
! 1·2·3
k2 = n2 = ,
6
k=1
1.3 Beweismethoden 15
∑
n
h : Z → Z, n 7→ h(n) := k2
k=1
von eben, wobei Z = {0, 1, −1, 2, −2, . . . }die Menge der ganzen Zahlen be-
zeichnet. Wir fragen uns nun, wie wir selbst auf die Formel hätten kommen
können. Es erscheint klar, dass für n ≥ 0 gilt:
∑
n ∫ n
1 1
h(n) = k2 ≈ t2 dt = [ t3 ]n0 = n3 .
0 3 3
k=1
Daraus leiten wir die Hypothese ab, dass auch die Summe durch ein soge-
nanntes Polynom vom Grad 3 in n beschrieben wird:
∑
n
h(n) = k2 = a3 n3 + a2 n2 + a1 n + a0 , für gewisse ai ∈ Q,
k=1
wobei Q die Menge der rationalen Zahlen bezeichnet, die wir erst in Beispiel
3.12 sauber einführen werden. Natürlich kann dies nicht für alle ganzen Zah-
len n ∈ Z korrekt sein, da h(n) = 0 für alle n < 0 und da ein Polynom p, das für
unendlich viele Werte den Funktionswert 0 ergibt, schon das Nullpolynom
Problem:
(d.h. p(n) = 0 für alle n) sein muss. Wir können also nur hoffen, eine solche
Definition Funktion,
Formel für n ≥ 0 zu finden. Offenbar ist h(0) = 0 und g(0) = a0 , so dass sofort
Funktionswert
a0 = 0 folgt.
Eine Strategie, die weiteren ai zu bestimmen, ist folgende: Ist f : Z → Z eine
Abbildung, so definieren wir die erste Differenzfunktion
Problem:
Definition Abbildung
erst später!
16 1 Logik und Beweismethoden
g(n) = a3 n3 + a2 n2 + a1 n + a0 ,
(∆g)(n) = a3 (n3 − (n − 1)3 ) + a2 (n2 − (n − 1)2 ) + a1 (n − (n − 1))
= a3 (3n2 − 3n + 1) + a2 (2n − 1) + a1 ,
(∆ (g))(n) = 3a3 (n2 − (n − 1)2 ) + · · · = 6a3 n − 6a3 + 2a2 ,
2
Hierbei ist (∆k (g))(n) := (∆(· · · (∆(g))))(n) die k-fache Anwendung der Funk-
tion ∆ auf g. Wir sehen damit, dass ∆3 (g) nicht mehr von n abhängt, dass
wir also a3 direkt ablesen können, wenn wir nur Werte (∆3 (g))(n) für n genü-
gend groß
∑ berechnet haben. Dazu betrachten wir folgende Tabelle für unser
h(n) = nk=1 k2 :
Ist also wirklich h(n) = g(n) für alle n = 0, 1, 2, . . . , so muss gelten (bei ∆3 h(0),
∆3 h(1), ∆3 h(2) geht h(−1) ein):
1
2 = (∆3 (h))(3) = (∆3 (g))(3) = 6a3 , also a3 = .
3
Wir betrachten nun die neue Funktion i(n) := h(n) − 31 n3 , von der wir an-
nehmen, dass sie für n ≥ 0 durch ein quadratisches Polynom beschrieben
wird. Wir können a2 also wieder aus einem einzigen Wert aus einer Tabelle
ablesen, da ∆2 (g) nicht von n abhängt, falls a3 = 0 ist, und genauer den Wert
2a2 annimmt, wie wir weiter oben berechnet haben:
Dies liefert:
1
1 = 2a2 , also a2 = .
2
Wir fahren analog fort, definieren also j(n) := h(n) − 13 n3 − 12 n2 , von dem wir
annehmen, dass es ein Polynom vom Grad 1 in n ist für n ≥ 0. Wir wir oben
berechnet haben, ergibt sich für (∆g)(n) mit a3 = 0 und a2 = 0 aber der Wert
a1 , der unabhängig von n ist. Wir können demnach a1 aus folgender Tabelle
ablesen:
3 − 2 ·4= 6
7 1 2 1
2 6
3 5 − 12 · 9 = 12 = 36 1
6
4 26
3 − 1
2 · 16 = 2
3 = 4
6
1
6
1 3 1 2 1 n(n + 1)(2n + 1)
g(n) = n + n + n=
3 2 6 6
gefunden. Wie wir im vorigen Beispiel 1.20 schon bewiesen haben, ist dies
auch tatsächlich das gesuchte und es gilt für jedes n ∈ {0, 1, 2, . . . }:
∑
n
1 3 1 2 1 n(n + 1)(2n + 1)
k2 = n + n + n= .
3 2 6 6
k=1
Beweis. Es gilt:
1
f0 = √ (1 − 1) = 0,
5
√ √ √
1 (1 + 5 1 − 5) 1 (2 5)
f1 = √ − = √ · = 1.
5 2 2 5 2
Wir beweisen die Aussage
( √ √ )
1 ( 1 + 5 )k ( 1 − 5 )k
A(n) : fk = √ − für k = 0, . . . , n
5 2 2
mit vollständiger Induktion. Den Induktionsanfang A(1) haben wir oben
bereits erledigt.
Für den Induktionsschritt A(n) ⇒ A(n + 1) betrachten wir:
fn+1 = fn + fn−1 (nach Definition)
( √ √ ) ( √ √ )
I.−V. 1
( 1 + 5 )n ( 1 − 5 )n 1 ( 1 + 5 )n−1 ( 1 − 5 )n−1
= √ − + √ −
5 2 2 5 2 2
( √ √ √ √ )
1 ( 1 + 5 )n−1 ( 1 + 5 ) ( 1 − 5 )n−1 ( 1 − 5 )
= √ · +1 − · +1 .
5 2 2 2 2
√ √ ( √ ) √ √ √
1+ 5 2
Nun gilt: 1+2 5 + 1 = 3+ 5
2 und 2 = ··· = 3+ 5 1− 5
2 . Analog: 2 +1 = 3− 5
2 =
( √ )2
1− 5
2 und damit:
( √ √ )
1 ( 1 + 5 )n−1+2 ( 1 − 5 )n−1+2
fn+1 = √ · −
5 2 2
( √ √ )
1 ( 1 + 5 )n+1 ( 1 − 5 )n+1
= √ · − .
5 2 2
⊓
⊔
Wie wir auf diese Formel kommen konnten, werden wir im nächsten Semester
(Abschnitt 24.4.2) lernen.
Aufgaben
Aufgabe 1.2 (Vier Zeugen). Ein Kommissar hat zu einem Verbrechen 4 Zeu-
gen vernommen. Aus den Vernehmungen hat er folgende Schlussfolgerungen
gezogen:
• Wenn der Butler die Wahrheit sagt, dann auch der Koch.
• Koch und Gärtner können nicht beide die Wahrheit sagen.
• Gärtner und Hausmeister lügen nicht beide.
• Wenn der Hausmeister die Wahrheit sagt, dann lügt der Koch.
Aufgabe 1.3 (Zwei Investmentbänker). Ein Mann ist bei einer Kurz–Beratung
mit zwei Investmentbänkern, A und B genannt, in der er herausfinden möch-
te, ob er seine Erbschaft lieber in die Anlagemöglichkeit 1 oder in die An-
lagemöglichkeit 2 investieren soll. Leider lässt die kostenlose Beratung der
Bank nur eine einzige Ja/Nein–Frage an nur einen der beiden Berater zu.
Ein Freund hatte ihn zuvor davon informiert, dass einer der beiden immer
die Wahrheit sagt und dass der andere stets lügt. Der Freund wusste aber
unglücklicherweise nicht mehr, welcher der beiden welcher ist. Mit welcher
Frage kann der Mann herausfinden, welche die gute und welche die schlechte
Anlagemöglichkeit ist?
Aufgabe 1.4 (Logische Verknüpfungen). Sei ⊼ das Zeichen für nicht und, d.h.
für zwei logische Variablen A, B ist A ⊼ B = ¬(A ∧ B).
Aufgabe 1.5 (Induktion). Finden Sie eine geschlossene Formel, die nur von
n ∈ N abhängt, für
∑ n
k3
k=1
Aufgabe 1.6 (Die Türme von Hanoi). Das Spiel Die Türme von Hanoi besteht
aus 3 Spielfeldern, auf denen n ∈ N Scheiben paarweise verschiedener Größe
gestapelt werden können. Zu Beginn des Spiels sind alle Scheiben auf einem
der Spielfelder der Größe nach gestapelt (die unten liegende Scheibe ist die
größte, wie im Bild zu sehen). Ziel des Spiels ist es, den Anfangsstapel auf
ein anderes Feld zu versetzen, so dass er dort wieder in der gleichen Stapel–
Reihenfolge liegt. Dazu darf in jedem Spielzug die oberste Scheibe eines
beliebigen Turms auf einen anderen Turm, der keine kleinere Scheibe enthält,
gelegt werden.
Geben Sie einen Algorithmus an (Papierform genügt), der dieses Problem
löst, und beweisen Sie die Korrektheit Ihres Algorithmus. Stellen Sie eine
Formel für die Anzahl der notwendigen Züge auf und beweisen Sie diese mit
vollständiger Induktion.
Geben Sie für die zweite Aussage auch die konjunktive Normalform an.
2
Eine Menge M ist eine Kollektion wohlbestimmter Objekte, die wir Elemente
von M nennen. Mengen lassen sich auf zwei Weisen spezifizieren:
Beispiel 2.1.
Dies kann man beispielsweise mit der aus der Schule bekannten p, q–
Formel berechnen.
Problem:
p, q–Formel
Wichtige Mengen von Zahlen haben spezielle Notationen; einige davon ha-
ben wir bereits kennen gelernt:
Ist M eine Menge und a ein Element, so schreiben wir a ∈ M. a < M steht für:
a ist kein Element von M. M ∋ a steht für: M enthält das Element a.
Eine Teilmenge N einer Menge M ist eine Menge, für die gilt:
a ∈ N ⇒ a ∈ M.
Schreibweisen:
A ∩ B = {x ∈ M | x ∈ A und x ∈ B}
A B
M
A B
M
M
A
A ∪ B = {x ∈ M | x ∈ A oder x ∈ B}
Ā = M\A = {x ∈ M | x < A}
heißt Differenzmenge von A und B, siehe Abb. 2.4. Manchmal wird statt A\B
auch A − B geschrieben.
A B
M
1. A ∩ B = B ∩ A.
A ∪ B = B ∪ A, Kommutativgesetze
2. (A ∩ B) ∩ C = A ∩ (B ∩ C).
(A ∪ B) ∪ C = A ∪ (B ∪ C), Assoziativgesetze,
3. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), Distributivgesetze,
4. A ∪ ∅ = A, A ∩ M = A, Identitätsgesetze.
5. A ∪ (M\A) = A ∪ Ā = M,
A ∩ (M\A) = A ∩ Ā = ∅, Mengen und ihr Komplement.
6. (A ∩ B) = Ā ∪ B̄,
(A ∪ B) = Ā ∩ B̄, Gesetze von de Morgan.
2.4 Disjunkte Mengen 25
Beweis. Die Aussagen folgen unmittelbar aus den analogen Aussagen der
Logik. Alternativ mit Venn–Diagrammen (siehe Abb. 2.5 und 2.6): ⊓
⊔
A B
M
B C
M
A × B = {(a, b) | a ∈ A, b ∈ B}
die Menge der geordneten Paare von Elementen aus A und Elementen aus
B.
Beispiel 2.3.
|A × B| = |A| · |B|.
Die Potenzmenge 2M einer Menge M, die aus den Teilmengen von M besteht,
hatten wir schon eingeführt.
Beweis. Induktion nach n. Für n = 0 ist die Aussage richtig. Die leere Menge
()
∅ hat genau eine 0-elementige Teilmenge, nämlich ∅. Also: 00 = 1 = 0!·0!
0!
gilt.
Num zum Induktionsschritt n → n + 1: Für k = 0 ist die Aussage klar: Auch
{1, . . . , n + 1} hat genau eine 0-elementige Teilmenge, nämlich ∅, also gilt:
( )
n+1 (n + 1)!
=1= ,
0 0!(n + 1)!
Also: ( ) ( ) ( )
n+1 n n
= + .
k k k−1
Die Induktionsvoraussetzung gibt nun:
( ) ( ) ( )
n+1 n n
= +
k k k−1
n! n!
= +
k!(n − k)! (k − 1)!(n − k + 1)!
n!
= (n − k + 1 + k)
k!(n − k + 1)!
(n + 1)!
= .
k!(n − k + 1)!
⊓
⊔
n
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
()
Abbildung 2.7. Das Pascalsche Dreieck mit den Einträgen nk für k = 0, . . . , n. Diese
(n) (n−1) (n−1)
Darstellung suggeriert (siehe auch Lemma 2.6): k = k−1 + k für k ≥ 1.
Induktionsschritt n → n + 1:
⊓
⊔
2.8 Abbildungen 29
2.8 Abbildungen
Beispiel/Definition 2.9.
+1.5
+0.3
-1.5
G f = {(x, y) ∈ M × N | y = f (x)}
der Graph der Abbildung f . Aus dem Graphen lässt sich die Abbildung
zurückgewinnen:
G f ∩ ({a} × N) = {(a, f (a))}.
3. Der ganzzahlige Anteil einer reellen Zahl ist durch folgende Abbildung
gegeben (siehe auch Abb. 2.9):
{ }
entier : R → Z ⊂ R, x 7→ y = entier(x) = ⌊x⌋ = max n ∈ Z | n ≤ x .
⌈x⌉ = min{ n ∈ Z | n ≥ x }.
30 2 Mengen und Abbildungen
y
3
2
1
−3 −2 −1 1 2 3 x
−2
−3
Abbildung 2.9. Graph der entier Funktion. Ein kleiner, leerer Kreis zeigt dabei an,
dass der umkreiste Punkt nicht zum Graphen gehört.
f −1 (B) = {a ∈ M | f (a) ∈ B}
Im Verlaufe der Vorlesung werden wir sehen, dass die folgenden Eigenschaf-
ten von Abbildungen immer wieder eine zentrale Rolle spielen werden:
1
a
2
b
3
c
4
d
f
M N
Abbildung 2.10. Injektivität und Surjektivität: Die gezeigte Abbildung f ist weder
injektiv noch surjektiv.
Satz 2.13. Sei f : M → N eine Abbildung zwischen endlichen Mengen mit |M| =
|N|. Dann sind äquivalent:
1. f ist injektiv,
2. f ist surjektiv,
3. f ist bijektiv.
Q22
Q11 Q12
durch f (k) := (i, j), falls der Punkt Pk ∈ Qi j . Da wir eine disjunkte Vereinigung
haben, ist dies eine Abbildung. Nach dem Schubfachprinzip ist sie nicht
injektiv und die Behauptung folgt. ⊓ ⊔
2.8 Abbildungen 33
|NM | = |N||M| ,
daher die Notation. In der Tat müssen wir, um f festzulegen, für jedes a ∈ M
ein Bild f (a) auswählen. Hierfür haben wir |N| Wahlmöglichkeiten, insgesamt
also |N||M| Wahlmöglichkeiten.
h ◦ (g ◦ f ) = (h ◦ g) ◦ f,
kurz zusammengefasst:
h◦(g◦ f )
g◦ f
f g %/
M /N K
h / L.
9?
h◦g
(h◦g)◦ f
Beweis. Es gilt:
34 2 Mengen und Abbildungen
Die Phrasen für alle und es existiert tauchen in der Mathematik und in der
Informatik häufig auf. Wir verwenden daher die Notation ∀ für für alle und
∃ für es existiert ein.
Beispiel 2.22.
f : M → N ist surjektiv ⇐⇒ ∀b ∈ N ∃ a ∈ M mit b = f (a).
Bei der Negation von Aussagen mit All– und Existenzquantoren verwandelt
sich ∀ in ∃ und ∃ in ∀ ähnlich wie bei den Gesetzen von de Morgan.
2.10 Indizes
Häufig werden Notationen wie a1 , . . . , a101 ∈ Z verwendet. Was ist dies for-
mal? i 7→ ai ist eine Abbildung wie f : {1, . . . , 101} → Z, f (i) = ai .
Beispiel/Definition 2.24. Sei I eine beliebige Menge und (Ai )i∈I eine Familie
von Teilmengen Ai ⊂ M einer weiteren Menge M, d.h. eine Abbildung I →
2M , i 7→ Ai . Dann ist der Durchschnitt
∩
Ai = {x ∈ M | x ∈ Ai ∀ i ∈ I}
i∈I
Aufgaben
Aufgabe 2.3 (Potenzmengen). Sei M eine beliebige Menge und 2M ihre Po-
tenzmenge. Zeigen Sie: Es existiert keine bijektive Abbildung zwischen M
und 2M .
Aufgabe 2.5 (Induktion). Zeigen Sie mit vollständiger Induktion, dass für
n ∈ N mit n ≥ 2 gilt:
∑n ( ) ( )
k n+1
= .
2 3
k=2
36 2 Mengen und Abbildungen
Geben Sie eine Interpretation von Gleichung (2.1) über die Definition des
Binomialkoeffizienten.
3
Vorlesung vom:
In der Mathematik und Informatik hat man es oft mit Relationen zu tun. 05. November 2008
Qualitätsstand:
erste Version
3.1 Äquivalenzrelationen Problem:
ausführlichere Einlei-
tung zu Äquiv-Rel
Beispiel 3.1. ≥ (größer gleich) ist eine Relation auf R. Für je zwei Zahlen
x, y ∈ R ist die Relation x ≥ y entweder wahr oder falsch.
Definition 3.2. Sei M eine Menge. Eine Teilmenge R ⊂ M × M nennen wir eine
Relation. Für x, y ∈ M ist die Relation erfüllt, wenn (x, y) ∈ R. Manchmal schreibt
man dann auch xRy.
Beispiel 3.3.
Beispiel 3.4.
1. Reflexivität: a ∼ a ∀ a ∈ M.
2. Symmetrie: a ∼ b ⇒ b ∼ a ∀a, b ∈ M.
3. Transitivität: a ∼ b und b ∼ c ⇒ a ∼ c ∀a, b, c ∈ M.
Beispiel 3.6.
[a] := {b ∈ M | b ∼ a}
die Äquivalenzklasse von M und jedes Element b ∈ [a] heißt ein Repräsentant
von [a]. Je zwei Äquivalenzklassen [a] und [b] sind entweder gleich oder disjunkt
(d.h. sie haben leeren Durchschnitt).
Es gilt:
[0] ∪· [1] ∪· [2] = Z.
Beweis (des Satzes 3.7). Zu zeigen ist, dass aus [a] ∩ [b] , ∅ folgt, dass [a] = [b].
Sei dazu etwa c ∈ [a] ∩ [b] und d ∈ [a]. Dann gilt: d ∼ a ∼ c ∼ b, also wegen
der Transitivität d ∼ b und daher d ∈ [b]. Dies zeigt: [a] ⊂ [b]. Die umgekehrte
Inklusion [b] ⊂ [a] folgt analog. Also insgesamt: [a] = [b]. ⊓ ⊔
M/∼ = {[a] | a ∈ M} ⊂ 2M
Beispiel 3.10. Für (≡ mod 3) auf Z ist π : Z → {[0], [1], [2]} die Abbildung
n 7→ [Rest von n bei Division durch 3].
Jede Äquivalenzrelation ist also im Prinzip vom Typ 1 in Beispiel 3.6 mit f =
π : M → N = M/∼. Das Urbild des Elements [a] ∈ M/∼ ist π−1 ([a]) = [a] ⊂ M.
Beispiel 3.12. Die Konstruktion der Menge der rationalen Zahlen aus den
ganzen Zahlen Z. Dazu betrachten wir M = Z × (Z\{0}) und definieren eine
Äquivalenzrelation auf M durch:
Diese Definition ist nicht unproblematisch, da die rechten Seiten von der
p
Auswahl der Repräsentanten (p, q) ∈ q und (r, s) ∈ rs abhängen. Das Beispiel
1 1 1·3+2·1 5
+ = =
2 3 2·3 6
2 −1 2 · (−3) + 4 · (−1) −10
+ = =
4 −3 4 · (−3) −12
suggeriert aber, dass dies vielleicht doch kein Problem ist. Um allgemein
einzusehen, dass
3.2 Kongruenzen
Vorlesung vom:
Im Folgenden möchten wir die Relation (≡ mod n) auf Z näher studieren. 07. November 2008
Für Z/(≡ mod n) schreiben wir kürzer Z/n. Jedes Element [a] von Z/n hat Qualitätsstand:
einen ausgezeichneten Repräsentanten i ∈ {0, 1, . . . , n − 1}, nämlich den Rest i erste Version
bei Division von a durch n. Die Restklasse von i ist
[i] = {i + kn | k ∈ Z}.
i = [i]
hat also n Elemente. Elemente von Z/n lassen sich addieren und multiplizie-
ren:
i + j = i + j, i · j = i · j.
Beispiel 3.14. n = 6.
1. Es gilt: (2 + 2) + 5 = 4 + 5 = 9 = 3.
Außerdem ist: 2 + (2 + 5) = 2 + 7 = 2 + 1 = 3.
2. Es gilt: (2 · 2) · 5 = 4 · 5 = 20 = 2.
Außerdem ist: 2 · (2 · 5) = 2 · 10 = 2 · 4 = 8 = 2.
Diese Addition und Multiplikation genügt den üblichen Gesetzen von Ad-
dition und Multiplikation, z.B. den Assoziativgesetzen:
(i + j) + k = i + (j + k)
(i · j) · k = i · ( j · k).
Distributivgesetze:
(i + j) · k = i · k + j · k.
Kommutativgesetze:
i+ j = j+i
i · j = j · i.
i + j = i + j, i· j=i· j
das Ergebnis nicht von der Auswahl i ∈ i und j ∈ j abhängt: Sind also zwei
verschiedene Repräsentanten der gleichen Äquivalenzklasse i1 und i2 bzw. j1
und j2 gegeben, d.h.
i1 ≡ i2 mod n, j1 ≡ j2 mod n.
so folgt tatsächlich:
i1 + j1 ≡ i2 + j2 mod n, i1 · j1 ≡ i2 · j2 mod n.
Dann vererben sich nämlich die Rechengesetze direkt aus denen für + und ·
in Z. Sei also i1 ≡ i2 mod n, d.h. i1 − i2 = k · n für ein gewisses k ∈ Z. Daraus
folgt:
i1 + j − (i2 + j) = k · n, also i1 + j ≡ i2 + j mod n.
Analog:
3.2 Kongruenzen 43
i1 j − i2 j = jkn ⇒ i1 j ≡ i2 j mod n,
d.h. bei der Verknüpfung hängt das Ergebnis nicht von der Wahl eines Re-
präsentanten der Klasse i ab. Eine analoge Rechnung zeigt Entsprechendes
für die Klasse j.
2 · 3 = 6 = 0 ∈ Z/6,
a·b≡0 mod p
Es folgt:
Satz/Definition 3.16. Sei p eine Primzahl und a ∈ Z/p, a , 0. Dann gibt die
Multiplikation mit a eine bijektive Abbildung
Z/p → Z/p, b 7→ a · b.
Das Urbild von 1 bezeichnen wir mit a −1 und heißt Inverses von a. Das Inverse a −1
wird also durch ein Element u ∈ Z repräsentiert, so dass
u · a ≡ 1 mod p
Gegeben zwei natürliche Zahlen n, m ∈ Z>1 . Dann haben wir eine Abbildung
Wir fragen: Ist die Abbildung surjektiv? Mit anderen Worten: Gibt es für
gegebene a, b ∈ Z ein x ∈ Z mit
x≡a mod n,
x ≡ b mod m ?
Beispiel 3.18. In wie vielen Tagen fällt der nächste Vollmond auf einen Sonn-
tag?
Vollmond ist alle 30 Tage (in etwa), Sonntag alle 7 Tage. Der nächste Vollmond
ist Donnerstag, der 13.11., also in 6 Tagen. Ist x die gesuchte Anzahl (heute
ist Freitag, der 8.11.), so gilt:
x ≡ 6 mod 30,
x ≡ 2 mod 7.
x ≡ 0 mod 2,
x ≡ 1 mod 2,
Wie wir eben gesehen haben, sind simultane Kongruenzen nicht immer lösbar
und zwar ist
x≡a mod n,
x ≡ b mod m,
Wie berechnet man den ggT? Die Schulmethode ist folgende: Seien n, m ∈ N.
Dann schreibt man:
∏
r
e1 er
n = p1 · · · · · pr = pei i ,
i=1
und
∏
r
f f f
m = p11 · · · · · prr = pi i ,
i=1
Beispiel 3.20.
∑
r
n= ai · 10i , ai ∈ {0, . . . , 9},
i=0
∑
r
n ≡ Q(n) := ai mod 9,
i=0
genauer gilt: 143 = 11 · 13, wie wir dann leicht berechnen können.
46 3 Äquivalenzrelationen und Kongruenzen
Faktorisieren ist so schwierig, dass dieses als Grundlage eines der weit-
verbreitesten öffentlichen Verschlüsselungsverfahren herangezogen wird,
nämlich RSA (Rivest-Shamir-Adleman, 1978).
Um den kleinen Satz von Fermat, den wir erst im nächsten Semester beweisen,
zu formulieren, benötigen wir folgende Definition.
Satz 3.22 (kleiner Satz von Fermat). Sei x ∈ Z mit ggT(x, n) = 1. Dann gilt:
xφ(n) ≡ 1 mod n.
Beweis. später ⊔
⊓
Es gibt auch einen sogenannten (großen) Satz von Fermat, auch Fermats
letzter Satz genannt, obwohl Fermat ihn wohl nur vermutet hatte und erst
Wiles ihn beweisen konnte:
Satz 3.24 (Satz von Wiles (auch: Fermats letzter Satz), Vermutung: Fermat
(17. Jhdt.), Beweis: Wiles (1997)). Für n ≥ 3 hat die diophantische Gleichung
(d.h. eine Gleichung, für deren ganzzahlige Lösungen man sich interessiert)
an + bn = cn
Der kleine Satz von Fermat erlaubt es uns nun, das RSA–Verfahren zu erläu-
tern. Bevor Alice eine Nachricht schicken kann, muss Bob seinen öffentlichen
und seinen geheimen Schlüssel produzieren:
Dass φ(nB ) = (pB − 1) · (qB − 1) gilt, ist nicht besonders schwierig zu zeigen;
wir werden auf solche Fragen im nächsten Semester näher eingehen.
• Anschließend wählt Bob eine Zahl dB mit
ggT(dB , φ(nB )) = 1
dB · eB ≡ 1 mod φ(nB ).
Damit kann Alice nun die Nachricht verschlüsseln und Bob sie wieder ent-
schlüsseln:
• Alice codiert die Nachricht in eine Zahl x < nB und berechnet daraus die
verschlüsselte Zahl c:
c ≡ xdB mod nB .
Nun ist:
dB · eB = 1 + k · φ(nB ) und y ≡ x · (xφ(nB ) )k .
x und nB sind mit nahezu 100%-iger Wahrscheinlichkeit teilerfremd:
φ(nB ) nB − pB − qB + 1
= ≈ 1,
nB nB
da nB ≫ (pB + qB ) (d.h. nB ist wesentlich größer als pB + qB , ohne dass wir
das Wort wesentlich hier genauer spezifizieren, entsprechend benutzt man
≪ für wesentlich kleiner). Mit an Sicherheit grenzender Wahrscheinlichkeit
lässt sich der kleine Satz von Fermat anwenden, also:
y ≡ x · (xφ(nB ) )k ≡ x · 1k ≡ x mod nB .
Input: a, b ∈ Z.
Output: d = ggT(a, b) und u, v ∈ Z mit d = ua + vb.
1. Wir setzen x1 = a, x2 = b.
2. Für i ≥ 2 mit xi , 0 berechnen wir xi+1 = xi−1 − ci xi mit ci ∈ Z und
0 ≤ xi+1 < |xi |, bis schließlich xn+1 = 0.
3.5 Der euklidische Algorithmus 49
ui+1 = ui−1 − ci ui
vi+1 = vi−1 − ci vi .
d = ua + vb.
Damit ist x4 = d = ggT(a, b). Für den erweiterten Teil setzen wir u1 = 1, u2 = 0,
v1 = 0, v2 = 1. Weiter erhalten wir:
u3 = u1 − c2 · u2 = 1 − 1 · 0 = 1,
v3 = v1 − c2 · v2 = 0 − 1 · 1 = −1,
u4 = u2 − c3 · u3 = 0 − 4 · 1 = −4,
v4 = v2 − c3 · v3 = 1 − 4 · (−1) = 5.
wie behauptet.
Bevor wir die Korrektheit des Algorithmus beweisen, führen wir noch eine
Notation ein:
Definition 3.27. Seien x, y ∈ Z. Dann schreiben wir x | y, falls x die Zahl y teilt
(in Z), d.h. falls es ein k ∈ Z gibt mit x · k = y, und x ∤ y, falls nicht.
Also:
xn | x1 = a und xn | x2 = b,
d.h. xn ist ein gemeinsamer Faktor von a und b.
3. Sei e ein Teiler von a und b. Wir zeigen sogar: e | xk für alle k. Wieder ist
der Induktionsanfang klar: e | x1 und e | x2 . Für den Induktionsschritt
seien e | xi−1 und e | xi bekannt, woraus folgt:
e | (xi−1 − ci xi ) = xi+1 .
Der Fall i = n:
d = xn = un a + vn b = ua + vb,
was die letzte Behauptung beweist.
⊓
⊔
{x0 + l · kgV(n, m) | l ∈ Z}
Beweis. Die Notwendigkeit hatten wir bereits gesehen (vor dem RSA–
Algorithmus). Um, falls
a ≡ b mod ggT(n, m) = d
gilt, eine Lösung zu konstruieren, berechnen wir d mit dem erweiterten eu-
klidischen Algorithmus:
d = un + vm.
Ist nun a = b + kd für ein k ∈ Z, so ist x = a − kun eine Lösung, denn x ≡ a
mod n ist klar und
Beispiel 3.30. Ein Himmelskörper sei alle 30 Tage gut zu beobachten, das
letzte Mal vor 5 Tagen. Ich habe leider nur sonntags Zeit, heute ist Mittwoch.
Wann kann ich das nächste Mal den Himmelskörper sehen?
Wir modellieren dies zunächst mit Hilfe von Kongruenzen:
52 3 Äquivalenzrelationen und Kongruenzen
x ≡ 5 = a mod 30 = n, x ≡ 3 = b mod 7 = m.
Dann berechnen wir mit dem euklidischen Algorithmus gemäß des Beweises
des chinesischen Restsatzes u und v mit
1 = ggT(30, 7) = d = un + vm = u · 30 + v · 7.
Wir wissen nach dem Satz, dass dies geht, da a ≡ b mod 1 für alle ganzen
Zahlen gilt. Es ergibt sich: u = −3, v = 13. Nun schreiben wir:
5 = a = b + kd = 3 + 2 · 1,
ergibt. Also: in 25 Tagen kann ich den Himmelskörper beobachten (das hätten
wir übrigens auch zu Fuß recht einfach berechnen können).
Wäre heute aber ein Montag, d.h. b = 1, so würden wir folgendes erhalten:
5 = a = b + kd = 1 + 4 · 1,
also: x = 5 − 4 · (−3) · 30 = 365 ≡ 155 ≡ −55 mod 210. Ich müsste also noch
55 Tage warten.
Beispiel 3.31. Oft kann man mit Hilfe des chinesischen Restsatzes ganze Zah-
len schon an wenigen Kongruenzen erkennen. Wir berechnen hier die ganzen
Zahlen, die folgende Kongruenzen erfüllen:
x ≡ 1 mod 2,
x ≡ 2 mod 3,
x ≡ 3 mod 5,
x ≡ 2 mod 7.
eine simultane Lösung der ersten beiden Kongruenzen, also eine Zahl, für
die gilt: x12 ≡ −1 mod 2 · 3 = 6.
3.5 Der euklidische Algorithmus 53
Beweis. Die Äquivalenz der ersten beiden Aussagen ist die Definition einer
Primzahl; wir müssen also nur noch die Äquivalenz der letzten beiden Aus-
sagen zeigen:
3. ⇒ 2.: Angenommen, 2. ist nicht erfüllt. Dann existiert ein Teiler a | p mit
1 < a < p. Sei also a · b = p. Dann gilt p | a · b, aber p ∤ a und p ∤ b, da
1 < a, b < p. Also: 3. ist nicht erfüllt.
2. ⇒ 3.: Sei 2. erfüllt und p | a · b. Angenommen, p ∤ a. Wir müssen dann p | b
zeigen. Wegen p ∤ a gilt ggT(a, p) < p und wegen 2. folgt: ggT(a, p) = 1.
Nach dem erweiterten euklidischen Algorithmus existieren u, v ∈ Z mit
1 = ua + vp. Damit folgt:
p | ab ⇒ p | uab ⇒ p | (uab + vpb) = (ua + vp) · b = b,
also: p | b.
⊓
⊔
Wir können jetzt zeigen, dass jede ganze Zahl in Primfaktoren zerlegbar ist:
Die Darstellung ist eindeutig bis auf die Reihenfolge der Faktoren.
54 3 Äquivalenzrelationen und Kongruenzen
Beweis. Existenz: Induktion nach |n|. Ohne Einschränkung (oft o.E. abgekürzt)
sei n > 0, also ε = 1. Ist n = 1, so ist ε = 1 und r = 0. Ist n eine Primzahl, dann
können wir r = 1, p1 = n wählen.
Andernfalls existieren Faktoren a, b ∈ Z>1 mit a · b = n. Wegen |a|, |b| < |n| exis-
tieren für a und b Primfaktorzerlegungen nach der Induktionsvoraussetzung,
etwa
a = p1 · · · pra , b = q1 · · · qrb .
Dann ist r = ra + rb und
n = a · b = p1 · · · pra · q1 · · · qrb .
n = p1 · · · pr = q1 · · · qs
mit pi , q j Primzahlen. Wir müssen zeigen, dass dies bis auf Reihenfolge die
gleiche Faktorisierung ist. Insbesondere müssen wir r = s zeigen. Wieder
verwenden wir Induktion, und zwar nach r. Wegen
pr | n = q1 · · · qs
gilt pr | qk für ein gewisses k nach Eigenschaft 3. von Korollar 3.32 über die
Charakterisierung von Primzahlen. Da qk eine Primzahl ist, folgt pr = qk und
nach Umnummerierung der q j dürfen wir k = s annehmen. Wir haben also
p1 · · · pr−1 · pr = q1 · · · qs−1 · pr .
Es folgt:
p1 · · · pr−1 = q1 · · · qs−1 .
Dies ist ein Produkt aus weniger Faktoren, so dass nach der Induktionsvor-
aussetzung folgt:
r − 1 = s − 1, d.h. r = s
und
p1 · · · pr−1 = q1 · · · qr−1 ,
bis auf Reihenfolge der Faktoren. ⊓
⊔
Wir haben weiter oben das kleinste gemeinsame Vielfache schon kennen
gelernt; mit dem obigen Satz können wir es nun formal einführen:
Definition 3.34. Seien a, b ∈ Z>0 . Dann bezeichnet kgV(a, b) das kleinste ge-
meinsame Vielfache (englisch: lowest common multiple lcm(a, b)) von a und b.
Das kgV existiert und es gilt:
a·b
kgV(a, b) = .
ggT(a, b)
3.5 Der euklidische Algorithmus 55
Aufgaben
Aufgabe 3.2 (Der chinesische Schäfer). Ein chinesischer Schäfer hat ein Her-
de von höchstens 200 Tieren. Um sie exakt zu zählen, lässt er sie des Abends
immer zu zweit durch ein Gatter laufen und stellt fest, dass ein Tier übrig
bleibt. Am nächsten Abend lässt er die Tiere immer zu dritt durchs Gatter
laufen und stellt ebenfalls fest, dass eins übrigbleibt. Am dritten Tage macht
er dasselbe mit 5 Schafen und stellt wieder fest, dass eines übrig bleibt. Am
vierten Abend schließlich lässt er 7 Schafe auf einmal durchs Gatter, und es
bleibt kein Schaf übrig. Wie groß ist die Herde?
1. Sei a = 2387 und b = 2079. Bestimmen Sie ohne Computer den größten
gemeinsamen Teiler d = ggT(a, b) und die Bézoutkoeffizienten u und v,
d.h. finden Sie u und v mit au + bv = d.
2. Sei a = 139651 und b = 111649. Bestimmen Sie ohne Computer das
kleinste gemeinsame Vielfache von a und b.
1. Zeigen Sie: a ∈ Z/n hat genau dann ein multiplikatives Inverses u ∈ Z/n,
wenn a und n keinen gemeinsamen Teiler haben, d.h. wenn ggT(a, n) = 1
ist.
2. Zeigen Sie: Dieses Inverse u von a ist dann in Z/n eindeutig bestimmt.
Aufgabe 3.6 (Zur Qualität von Primzahltests mit Hilfe des kleinen Satzes
von Fermat). Nach dem kleinen Satz von Fermat gilt: p ist Primzahl =⇒
ap−1 ≡ 1 mod p ∀a mit ggT(a, p) = 1.
Verwenden Sie MAPLE, um zu zeigen, dass die Umkehrung nicht gilt, d.h.
finden Sie eine zusammengesetzte Zahl n, für die an−1 ≡ 1 mod n für alle a
mit ggT(a, n) = 1 gilt.
Aufgabe 3.8 (Zahnräder). In der unten stehenden Skizze sehen Sie drei Zahn-
räder, die ineinander greifen und die sich um ihren jeweiligen Mittelpunkt
drehen lassen. Gibt es eine Einstellung der Zahnräder, so dass alle drei Zeiger
(d.h. die dicken Striche) nach oben zeigen? Falls ja, geben Sie an, um wieviele
Zacken man das linke Rad in welche Richtung drehen muss, damit alle drei
Zeiger nach oben zeigen?
Teil II
Einführung
4
Mit R bezeichnen wir die Menge der (unendlichen) Dezimalzahlen, der reel-
len Zahlen. Wir fassen die Eigenschaften von R in einigen Axiomen zusam-
men, auf die wir alle weiteren Sätze aufbauen werden.
Problem:
mehr sinnvollen Ein-
leitungstext
4.1 Die Körperaxiome
+ : R × R → R, (a, b) 7→ a + b,
· : R × R → R, (a, b) 7→ a · b.
+ : K × K → K, (a, b) 7→ a + b,
· : K × K → K, (a, b) 7→ a · b.
heißt ein Körper (Achtung! englisch: field), wenn folgende Axiome erfüllt sind:
(a + b) + c = a + (b + c) ∀ a, b, c ∈ K.
a+b=b+a ∀ a, b ∈ K.
62 4 Die reellen Zahlen
Außer den reellen Zahlen kennen wir schon einige andere Körper:
Beispiel 4.2.
+ 01 · 01
0 01 0 00
1 10 1 01
4. (Z, +, ·) ist kein Körper, da das Axiome K2.4 nicht erfüllt ist, d.h. es exis-
tiert nicht für alle ganzen Zahlen ein Inverses in Z, beispielsweise für
2 ∈ Z. Genauer existiert hier nur für 1, −1 ein Inverses.
4.3 Folgerungen aus den Körperaxiomen 63
4.2 Ringe
Definition 4.3. Eine Menge (R, +, ·) mit zwei Verknüpfungen, für die alle Körpe-
raxiome bis auf K2.4 gefordert werden, heißt ein kommutativer Ring mit 1. Wir
werden meißt nur Ring dazu sagen, da bei uns allgemeine Ringe selten eine Rolle
spielen werden. Ein allgemeiner Ring ist eine Menge, bei der außer K2.4 auch K2.2
und K2.3 nicht gefordert werden.
Beispiel 4.4.
Aus den Körperaxiomen können wir recht schnell einige Folgerungen ziehen,
die uns im Fall der reellen Zahlen geläufig sind:
Proposition 4.5 (Eigenschaften von Körpern). Sei (K, +, ·) ein Körper. Dann
gilt:
Beweis.
0 = −(0 · a) + 0 · a = −0 · a + (0 · a + 0 · a)
= (−(0 · a) + 0 · a) + 0 · a = 0 + 0 · a
= 0 · a.
(a1 + a2 ) + a3 = a1 + (a2 + a3 )
(a1 + · · · + ak ) + (ak+1 + · · · + an )
a1 + · · · + ak = a1 + (a2 + · · · + ak ),
also:
4.4 Die Anordnungsaxiome 65
+ 0 1 −1 · 0 1 −1
0 0 1 −1 0 0 0 0
1 1 −1 0 1 0 1 −1
−1 −1 0 1 −1 0 −1 1
Die Verknüpfungstabellen von F2 und Z/2 sind identisch und jene von F3
und Z/3 gehen durch −1 7→ 2 ineinander über, d.h. die beiden Körper haben
die gleiche Struktur. Allgemein haben wir schon gesehen, dass Z/p genau
dann ein Körper ist, wenn p eine Primzahl ist.
Gibt es einen Körper mit genau 4 Elementen? Wie wir eben bemerkt haben,
kann Z/4 kein Körper sein, weil 4 keine Primzahl ist. Die Frage wird in den
Übungsaufgaben beantwortet werden.
Definition 4.7. Ein angeordneter Körper ist ein Körper K zusammen mit Teil-
mengen positiver Elemente
{x ∈ K | x > 0},
so dass folgende Axiome erfüllt sind:
66 4 Die reellen Zahlen
A1: Für jedes Element x ∈ K ist genau eine der Eigenschaften x > 0, x = 0 oder
−x > 0 erfüllt.
A2: Sind x > 0 und y > 0, so auch x + y > 0.
A3: Sind x > 0 und y > 0, so auch x · y > 0.
Bemerkung 4.8.
d.h. b = 0.
Diese Primzahl heißt Charakteristik von Fq , notiert: char(Fq ) = p. Ist
Q ⊂ K, so schreiben wir char(K) = 0.
x > y : ⇐⇒ x − y > 0.
4.5 Irrationale Zahlen 67
Die Relation < ist definiert durch: x < y : ⇐⇒ y > x und die Relation ≥
durch:
x ≥ y : ⇐⇒ x = y oder x > y.
≥ ist eine reflexive und transitive Relation: Offenbar ist nämlich x ≥ x ∀x ∈ K
und ferner folgt aus x ≥ y und y ≥ z, dass x ≥ z, da:
x − y ≥ 0, y − z ≥ 0 ⇒ x − y + y − z = x − z ≥ 0.
Durch {
x, falls x ≥ 0,
|x| :=
−x, falls − x ≥ 0,
ist der Betrag von x definiert. Es gilt:
1. |x| ≥ 0.
2. |x| = 0 genau dann, wenn x = 0.
3. |x · y| = |x| · |y| ∀x, y ∈ K.
4. ∆–Ungleichung:
|x + y| ≤ |x| + |y|.
Die ersten Aussagen sind klar oder einfach zu zeigen, die letzte zeigt man,
indem man alle Fälle von Vorzeichen durchspielt: x > 0, x = 0, −x > 0,
y > 0, y = 0, −y > 0.
erfüllt.
R und Q sind Beispiele für archimedisch angeordnete Körper. Ein Beispiel für
einen nicht archimedisch angeordneten Körper können wir hier noch nicht
geben. In einem nicht archimedisch angeordneten Körper gibt es Elemente
x ∈ K, die größer als jedes n ∈ N, also in gewissem Sinne unendlich groß sind.
Das letzte Axiom, das wir für die Charakterisierung von R benötigen, ist das
sogenannte Vollständigkeitsaxiom. Bevor wir dieses besprechen, sei daran
erinnert, warum wir mit Q nicht zufrieden waren.
68 4 Die reellen Zahlen
Beispiel 4.11. 1. Nach dem Satz des Pythagoras ist die Länge der Diagona-
len c in einem Quadrat der Kantenlänge a = b = 1 wegen a2 + b2 = c2
gerade
√
c = 2.
Es gilt:
√
2 < Q.
√
Man sagt auch, dass 2 irrational ist. Nehmen wir nämlich an, dass
√ p
2 = q mit p, q ∈ Z und ggT(p, q) = 1, dann folgt:
p2
2= ⇐⇒ 2q2 = p2 ⇒ p ist gerade ,
q2
2 ist daher ein gemeinsamer Teiler von p und q, was aber ein Widerspruch
zur Voraussetzung ggT(p, q) = 1 ist. Daher muss die Annahme falsch
gewesen sein.
2. Wir wollen allgemein zwei Strecken a, b vergleichen. Wir sagen, dass a und
b kommensurabel (lat. zusammen messbar) sind, falls es ganze Zahlen
k, l ∈ Z gibt, mit:
a = k · d, b = l · d,
wobei d eine gemeinsame Teilstrecke ist (Abb. 4.1). Zwei Strecken heißen
Aufgaben
1. Gibt es einen Körper mit genau 4 Elementen? Falls ja, so geben Sie die
Verknüpfungstafeln an. Beweisen Sie Ihre Antwort.
2. Gibt es einen Körper mit genau 6 Elementen? Falls ja, so geben Sie die
Verknüpfungstafeln an. Beweisen Sie Ihre Antwort.
Konvergenz
Definition 5.1. Eine Folge (an ) (= (an )n∈N ) reeller Zahlen ist eine Abbildung
N → R, n 7→ an .
Üblicherweise bekommt die Abbildung keinen Namen, sondern man verwendet In-
dizes: an heißt n-tes Folgenglied.
Beispiel 5.2.
1. (an ) = ( n1 ), d.h. an = n1 :
( 1 1 1 )
1, , , , . . . .
2 3 4
2. (an ) = (2n ):
2, 4, 8, 16, . . . .
Beispiele von Folgen kennen wir aus Intelligenztests. Dort besteht die Auf-
gabe oft darin, das nächste Glied einer begonnenen Folge anzugeben, z.B.:
2, 4, 3, 6, 5, 10, 9, 18, . . .
Weitere Beispiele:
72 5 Konvergenz
Beispiel 5.3.
In der Analysis werden Folgen verwendet, um eine gesuchte Zahl besser und
besser zu approximieren:
(3, 3.1, 3.14, 3.141, 3.1415, . . . )
approximiert die Kreiszahl
π = 3.141592 . . .
immer besser, je größer n ist. Wir geben dieser Idee einen präzisen Sinn:
Definition 5.4. Sei (an ) eine Folge reeller Zahlen und a ∈ R eine weitere Zahl. (an )
heißt konvergent gegen a, in Zeichen
lim an = a,
n→∞
Beispiel 5.5.
3. Die konstante Folge (an ) mit an = a für ein gewisses festes a konvergiert
gegen a.
4. Die Folge ((−1)n ) konvergiert nicht, denn: Ist limn→∞ (−1)n = a für ein a,
so existiert zu ε = 1 ein n0 , so dass
(−1)n − a < 1 ∀n ≥ n0 .
Insbesondere gilt:
2 = (−1)n0 − a + a + (−1)n0 +1
∆–Ungl.
≤ (−1)n0 − a + a − (−1)n0 +1
< 1 + 1 = 2.
Bemerkung 5.8. Der Grenzwert a = lim an einer konvergenten Folge ist ein-
deutig bestimmt.
Satz 5.9 (Rechenregeln für Grenzwerte). Es seien (an ), (bn ) zwei konvergente
Folgen mit Grenzwerten a = lim an , b = lim bn . Dann gilt:
74 5 Konvergenz
1. Auch die Folge (an +bn ) ist konvergent mit Grenzwert a+b. Mit anderen Worten:
lim (an + bn ) = lim an + lim bn ,
n→∞ n→∞ n→∞
an a ε · |b| 2 |b|2 2
|
− |< · + (|a| + 1) · ·ε· 2
bn b 4 |b| 4 · (|a| + 1) |b|
ε ε
= + = ε.
2 2
für alle n ≥ n0 = max(n1 , n2 , n3 ).
⊓
⊔
n2 + 2n − 1 1+ 2
n − 1
n2
an = = .
2n + 3n + 1 2 +
2 3
n + 1
n2
Nun gilt:
1 1 1 1
lim = 0 ⇒ 0 = lim · lim = lim 2 .
n→∞ n n→∞ n n→∞ n n→∞ n
Es folgt:
2 1 1 1
lim (1 + − ) = lim 1 + lim 2 − lim 2 = 1 + 2 · 0 − 0 = 1.
n→∞ n n2 n→∞ n→∞ n n→∞ n
Die Addition von zwei bzw. drei einstelligen Zahlen kann man in einer Tabelle
nachschlagen. Brauchen wir hierfür t Takte, so benötigen wir insgesamt n · t
Takte. Ist ein Takt s Sekunden lang, so erhalten wir:
an = n · t · s.
Sei (an ) eine Folge positiver reeller Zahlen und (bn ) eine weitere solche Folge.
Dann sagen wir:
|bn | ≤ c · an ∀n ≥ n0 .
Beispiel 5.12. n · t · s ∈ O(n). Die Aussage, dass sich zwei Zahlen mit n Stellen
in der Laufzeit O(n) addieren lassen, ist in vielerlei Hinsicht viel besser und
informativer als die genaue Formel, da sie über die Laufzeit für große n eine
gut vergleichbare Aussage macht.
Wir schreiben
(bn ) ∈ o(an ),
falls limn→∞ bann = 0, also:
{ bn }
o(n) = (bn ) lim =0 .
n→∞ an
O(n) und o(n) heißen auch Landau–Symbole (es gibt noch weitere davon,
wir beschränken uns hier aber auf diese beiden).
5.5 Das Vollständigkeitsaxiom 77
aus.
Der dritte Schritt involviert die Addition von mehreren Zahlen mit 2n/2 Bi-
närstellen, ist also von der Ordnung O( n2 ) = O(n). Entscheidend ist, dass im
zweiten Schritt nur drei statt vier Multiplikationen notwendig sind. Daher
ist nämlich der Aufwand für die Multiplikation von zwei n–stelligen Binär-
zahlen von der Ordnung
O(nlog2 3 ) ⊂ O(n1.59 ),
wie wir in einer Aufgabe zeigen werden. Dies ist viel besser als O(n2 ).
Multiplikation geht noch wesentlich schneller; es gilt nämlich sogar:
Satz 5.14 (Schönhage–Strassen, 1971). Zwei n–stellige Zahlen lassen sich mit
Aufwand O(n log n log log n) multiplizieren.
Definition 5.15. Sei (an ) eine Folge reeller Zahlen. (an ) heißt nach oben be-
schränkt, nach unten beschränkt bzw. beschränkt, wenn es eine Konstante k ∈ R,
genannt Schranke, gibt, so dass
an ≤ k ∀n ∈ N,
an ≥ k ∀n ∈ N bzw.
|an | ≤ k ∀n ∈ N.
(an ) heißt monoton fallend bzw. monoton steigend (auch monoton wachsend
genannt), wenn an ≥ an+1 ∀n ∈ N bzw. an ≤ an+1 ∀n ∈ N. Eine monotone Folge
ist eine Folge, die monoton steigend oder monoton fallend ist.
(an ) heißt streng monoton fallend, streng monoton wachsend bzw. streng mo-
noton, falls die entsprechenden Ungleichungen strikt sind.
Beweis. Sei (an ) eine konvergente Folge mit lim an = a. Dann gibt es zu ε = 1
ein n0 , so dass |an − a| ≤ 1 ∀n ≥ n0 . Es folgt: |an | ≤ |a| + 1 ∀n ≥ n0 . Also:
M = max{|a1 |, . . . , |an−1 |, |a| + 1} ist die Schranke für |an |. ⊓
⊔
Beweis. Sei (an ) eine konvergente Folge mit lim an = a und sei ε > 0 vorgege-
ben. Da (an ) gegen a konvergiert, ∃n0 , so dass |an − a| < 2ε ∀n ≥ n0 . Also:
∆–Ungl. ε ε
|an − am | = |an − a + a − am | ≤ |an − a| + |a − am | < + = ε ∀n, m ≥ n0 .
2 2
⊓
⊔
Wieder gibt es genau ein Teilintervall [i.i1 , i.(i1 + 1)[, welches unendlich vie-
le Elemente der Folge enthält. Dann ist i1 die erste Nachkommastelle (bzw.
Nachpunktstelle in der obigen Notation) des Grenzwerts. Als nächstes zer-
legen wir [i.i1 , i.i1 + 0.1[ in 10 Teilintervalle, um die zweite Nachkommastelle
i2 zu bestimmen usw. Auf diese Weise können wir sämtliche Dezimalstellen
ik des Grenzwertes
a = i.i1 i2 i3 . . .
bestimmen. ⊓
⊔
Warum ist das Vorige kein Beweis? Der Grund ist, dass in der Definition
der unendlichen Dezimalzahlen schon der Begriff Konvergenz eingeht. Dass
Folgen, die durch Dezimalbruchentwicklung definiert werden, wie
eine streng monoton wachsende Folge natürlicher Zahlen. Dann nennen wir die
Folge (ank )k∈N eine Teilfolge von (an ).
Beweis. Sei (an ) eine Folge. Wir nennen das Glied am einen Hochpunkt der
Folge, wenn
am > an ∀n ≥ m.
80 5 Konvergenz
Hat die Folge (an ) nur endlich viele Hochpunkte, dann besitzt (an ) eine mono-
ton wachsende Teilfolge. Ist nämlich am der letzte Hochpunkt, so setzen wir
n1 = m + 1 und zu an1 gibt es nach Voraussetzung ein n2 > n1 mit an1 ≤ an2 , zu
an2 ein n3 > n2 mit an2 ≤ an3 und rekursiv ein ank ein nk+1 > nk mit ank ≤ ank+1 .
(ank ) ist dann die gesuchte monoton wachsende Teilfolge.
Hat andererseits (an ) unendlich viele Hochpunkte, so bildet die Teilfolge der
Hochpunkte, n1 < n2 < · · · < nk < · · · mit nk definiert durch ank ist der k–te
Hochpunkt eine monoton fallende Teilfolge. ⊓ ⊔
Satz 5.23. Die zweite Version (Satz 5.20) des Vollständigkeitsaxioms impliziert die
erste (Satz 5.19).
Beweis (von Satz 5.23). Jede Teilfolge einer Cauchy–Folge (an ) ist ebenfalls eine.
Insbesondere gibt es eine monotone beschränkte Teilfolge (ank ) von (an ). Nach
der zweiten Version des Vollständigkeitsaxioms hat (ank ) einen Grenzwert
lim ank = a.
k→∞
Wir zeigen, dass auch limn→∞ an = a gilt. Sei dazu ε > 0 vorgegeben. Dann
existiert ein k0 mit
ε
|ank − a| < ∀ k ≥ k0
2
und es gibt ein n0 mit
ε
|am − an | < ∀n ≥ n0 .
2
Sei nun N = max{k0 , n0 }. Für n ≥ N gilt dann:
ε ε
|an − a| = |an − ank0 | + |ank0 − a| < + ,
2 2
was zu zeigen war. ⊓
⊔
5.5 Das Vollständigkeitsaxiom 81
Satz 5.25. Das Vollständigkeitsaxiom (Satz 5.19) impliziert die zweite Version des
Vollständigkeitsaxioms (Satz 5.20).
(N existiert nach dem archimedischen Axiom, siehe Def. 4.10). Dann ist
∪
2N−1
[−M, M[⊂ [−M, −M + 2εN[= [−M + kε, −M + (k + 1)ε[
k=0
eine disjunkte Zerlegung. Wegen der Monotonie der Folge (an ) gibt es genau
ein Teilintervall
[ −M + kε, −M + (k + 1)ε [,
das alle bis auf endlich viele an enthält. Gilt etwa
an ∈ [ −M + kε, −M + (k + 1)ε [ ∀n ≥ n0 ,
so folgt:
|an − am | < ε ∀n, m ≥ n0 .
Nach dem Cauchy–Kriterium hat die Folge (an ) einen Grenzwert a ∈ R.
Somit ist gezeigt, dass jede monotone, beschränkte Folge konvergiert, wenn
das Cauchy–Kriterium erfüllt ist. ⊓⊔
Weitere Axiome zur Charakterisierung der rellen Zahlen benötigen wir nicht:
Satz 5.26. Seien R und R′ zwei archimedisch angeordnete Körper, die beide das
Vollständigkeitsaxiom erfüllen. Dann gibt es genau eine bijektive Abbildung
φ : R → R′ ,
die alle Strukturen erhält. Etwa: φ(a + b) = φ(a) + φ(b), a > b ⇒ φ(a) > φ(b) usw.
? idQ ?
Q /Q
φ Q : Q → R′ , φ Q (x) = φ(x)
(man sagt φ eingeschränkt auf Q) die Identität idQ auf Q ist, d.h. φ Q = idQ .
Sei dazu a ∈ R gegeben. Zu ε = n1 wählen wir eine rationale Zahl an ∈]a − ε, a +
ε[. Zum Beispiel können wir an in der Form mn wählen mit einem geeigneten
m ∈ Z, denn da der Durchmesser des Intervalls (a + ε) − (a − ε) = 2ε = n2 ist,
enthält es wenigstens eine der Zahlen mn .
Die Folge (an ) konvergiert dann gegen a ∈ R: Zu ε > 0 existiert ein n0 > 1ε nach
dem archimedischen Axiom und |an − a| < n1 ≤ n10 < ε ∀n ≥ n0 . Die Bilder
φ(an ) ∈ Q ⊂ R′ sind schon definiert, da an ∈ Q. Die Folge (φ(an )) ist eine
Cauchy–Folge in R′ , da das Cauchy–Kriterium für ε der Gestalt ε = m1 ∈ Q
mit m ∈ N erfüllt ist. Nach dem archimedischen Axiom genügt es, solche ε
zu betrachten.
Sei a′ = limn→∞ φ(an ) ∈ R′ , der Grenzwert a′ existiert nach dem Vollständig-
keitsaxiom in R′ . Wir definieren dann φ(a) := a′ ∈ R′ . Man kann sich ohne
allzu große Mühe folgendes überlegen:
5.6 Quadratwurzeln
Vorlesung vom:
Die Einführung der reellen Zahlen haben wir beispielsweise motiviert durch
28. November 2008 √ √
Qualitätsstand: 2 < Q. Für jede reelle Zahl b > 0 existiert a = b ∈ R, d.h. eine reelle Zahl
erste Version a ≥ 0, genannt die Quadratwurzel von b, mit a2 = b. Wir können dies aus den
Axiomen folgern:
⊓
⊔
Beispiel 5.28. Wir wenden den im Beweis von Satz 5.27 angegebenen Algo-
rithmus zur Berechnung der Quadratwurzel an:
√
1. b = 4, a0 = 1. Der korrekte Grenzwert ist also b = 2. Es ergibt sich
folgende Tabelle:
b
n an an
0 1 4
1 2.5 1.6
2 2.05 1.95121
3 2.0006097 . . .
√
2. Für b = 2 und a0 = 1 erhalten wir als Grenzwert 2:
b
n an an
0 1 2
1 1.5 1.3333 . . .
2 1.41666 . . . 1.41176
3 1.4142 1.414211
4 1.414213 ...
1( b)
an+1 = an +
2 an
√
gegen a = b ist bemerkenswert schnell: Wir definieren den relativen Fehler
fn von an durch die Formel
an = a · (1 + fn ).
1 a2
a(1 + fn+1 ) = (a(1 + fn ) +
2 a(1 + fn )
bzw.
1( 1 ) 1 2 + 2 fn + fn2
1 + fn+1 = (1 + fn ) + = · .
2 1 + fn 2 1 + fn
Es folgt:
1 fn2 1
fn+1 = · ≤ · min{ fn , fn2 }.
2 1 + fn 2
5.7 Zur Existenz der reellen Zahlen 85
Nach Satz 5.26 ist es egal, wie wir uns von der Existenz von R überzeugen.
Zwei Konstruktionen von R aus Q sind gebräuchlich:
Definition 5.31. Eine Nullfolge (an ) ist eine Folge, die gegen 0 konvergiert. Wir
betrachten jetzt
Dies ist wohldefiniert, da die Summe zweier Nullfolgen eine Nullfolge ist. Die Mul-
tiplikation
[(an )] · [(bn )] := [(an · bn )]
ist wohldefiniert, da Cauchy–Folgen beschränkt sind und da das Produkt einer be-
schränkten Folge mit einer Nullfolge eine Nullfolge ergibt.
Mit diesen beiden Verknüpfungen wird M/∼ ein Körper:
1
|an | ≥ ∀n ≥ n0 .
N
Die Folge {
1, falls n < n0 ,
(bn ) mit bn =
an , falls n ≥ n0 ,
1
wobei r ∈ Q.
Den Schnitt
Ur′ = {x ∈ Q | x < r}, Vr′ = {x ∈ Q | x ≥ r}
nennen wir schlecht gewählt.
Alle anderen Dedekindschen Schnitte nennen wir irrational.
Gut gewählte Schnitte sind entweder irrationale Schnitte oder gut gewählte
rationale Schnitte. Dann können wir
zur Definition von R nehmen. Der Nachweis sämtlicher Axiome ist länglich,
aber nicht schwierig.
Problem:
Referenz angeben?
−M ≤ an ≤ M.
Mk+1 = +M
2
N k k
, sonst.
2
88 5 Konvergenz
Dann ist (ank ) eine Cauchy–Folge und damit die gesuchte konvergente Teil-
folge. ⊓
⊔
Definition 5.34. Sei M ⊂ R eine Teilmenge. Eine reelle Zahl A heißt obere Schran-
ke von M, wenn a ≤ A ∀a ∈ M gilt. M heißt nach oben beschränkt, wenn es eine
obere Schranke gibt.
Beweis (der Existenz des Supremums). Sei A0 eine obere Schranke von M und
a0 ∈ M, also a0 ≤ A0 . Wir definieren zwei Folgen
(an ) mit an ∈ M
und
(An ) obere Schranke von M,
so dass (an ) monoton wächst, (An ) monoton fällt und
0 ≤ An − an ≤ 2−n (A0 − a0 )
gilt. Dann konvergieren beide Folgen und es gilt:
lim an = lim An .
Dieser Grenzwert ist das Supremum von M.
Seien an , An schon gewählt. Dann wählen wir
{ A +a An +an
2 , falls 2
n n
eine obere Schranke ist,
An+1 =
An , sonst.
{
ein Element von M > An2+an , falls An2+an keine obere Schranke ist,
an+1 =
an , sonst.
Die Folgen (an ) und (An ) haben dann die gewünschte Eigenschaft, wie man
leicht nachprüfen kann. Das Infimum ergibt sich analog. ⊓⊔
5.9 Mächtigkeit 89
5.9 Mächtigkeit
Definition 5.37. Sei M eine Menge. M heißt abzählbar, wenn es eine surjektive
Abbildung φ : N → M gibt.
Beispiel 5.38.
Bemerkung 5.39. Ist M abzählbar unendlich, dann gibt es auch eine bijektive
Abbildung φ : N → M.
Beweis. Sei
ψ : N → N × N, n 7→ ψ(n) = (ψ1 (n), ψ2 (n))
die Abzählung von N × N und φk : N → Mk eine Abzählung von Mk . Dann
ist die Abbildung
∪
∞
Φ: N → Mk , Φ(n) = φψ1 (n) (ψ2 (n))
k=1
Beweis. Sei∪Mk = { nk | n ∈ Z} ⊂ Q. Dann gilt: Mk ← Z ← N ist abzählbar, also
auch Q = ∞ k=1 Mk . ⊔ ⊓
Definition 5.42. Eine Menge, die nicht abzählbar ist, heißt überabzählbar.
mit ank ∈ {0, . . . , 9} die k–te Nachkommastelle von an . Dann sei die Zahl
c = 0.c1 c2 . . . ck . . . mit Ziffern ck durch
{
1, ann , 1,
ck =
2, akk = 1.
N → [0, 1[, n 7→ an
Die Mengenlehre von Cantor beschäftigt sich mit beliebig großen Mengen.
2
1874 gab er schon einen anderen Beweis. Sein erstes Diagonalargument zeigt,
dass die rationalen Zahlen abzählbar sind.
5.9 Mächtigkeit 91
Definition 5.45 (Auswahlaxiom). Sei (Mi )i∈I eine Familie von nichtleeren Men-
gen. Dann existiert eine Abbildung
∪
a: I → Mi ,
i∈I
so dass a(i) ∈ Mi für alle i ∈ I gilt. Mit anderen Worten kann man aus den nicht
leeren Mengen Mi gleichzeitig je ein Element auswählen.
Man kann zeigen, dass die Potenzmenge 2M einer Menge M stets echt mäch-
tiger als M ist.
Aufgaben
n3 +n+1
1. 2n2 −5
∈ O(n).
n +n+1
3
2. 2n2 −5
∈ o(n).
( )
3. 2n−5
√
20n n+1000
∈O 1
n .
√
20n n+1000
4. 2n−5 ∈ O(n).
Aufgabe 5.2 (Quantoren und ε). Sei (an ) eine Folge in R und a ∈ R. Welche
Implikationen bestehen zwischen den folgenden sechs Aussagen?
Geben Sie Beispiele von Folgen an, die zeigen, dass weitere Implikationen
nicht bestehen.
Aufgabe 5.3 (Quantoren und ε). Für n ∈ N definieren wir die Folgen:
√ √
an = n + 1000 − n,
√
√ √
bn = n + n − n,
√
n √
cn = n + − n.
1000
1
lim an = 0, und lim bn = .
n→∞ n→∞ 2
Aufgabe 5.4 (Nullfolgen). Eine Folge (an ) heißt Nullfolge, falls limn→∞ an =
0. Sei (an ) eine Nullfolge, (bn ) eine Cauchy–Folge und (cn ) eine beschränkte
Folge. Zeigen Sie:
Aufgabe 5.5 (Konvergenz von Folgen). Wir definieren die Folge (an )n∈N0
durch a0 = 1 und √
an = 1 + an−1 ∀n ≥ 1.
Zeigen Sie, dass die Folge konvergiert, und bestimmen Sie den Grenzwert.
Welche dieser Mengen besitzt ein Supremum, welche ein Infimum? Geben
Sie es jeweils an, wenn es existiert.
Aufgabe 5.8 (Grenzwerte von Folgen / Teilfolgen). Zeigen Sie, dass die Folge
( √ ) ( )
an = sin π n + cos π log2 (n)
eine konvergente Teilfolge hat und geben Sie eine solche an.
Aufgabe 5.9 (Mächtigkeit). Zeigen Sie, dass die Potenzmenge 2R von R echt
mächtiger ist als die Menge R selbst.
6
Reihen
Vorlesung vom:
... 5. Dezember 2008
Qualitätsstand:
erste Version
Problem:
6.1 Definition und erste Eigenschaften sinnvollen Einlei-
tungstext
Definition 6.1. Sei (ak )k∈N0 eine Folge. Die Folge (sn ) der Partialsummen
∑
n
sn = ak
k=0
bezeichnen. Ist die Folge (sn ) konvergent, so verwenden wir für den Grenzwert
s = limn→∞ sn die Notation
∑∞
s= ak
k=0
Beispiel 6.2.
96 6 Reihen
∑∞ 1
1. n=1 n ,
∑∞ 1
2. n=0 2n ,
Eigentlich sind Reihen also gar nichts Neues. Gelegentlich lässt sich dies
verwenden, um Grenzwerte auszurechnen:
Idee:
1 1 1
= − .
n(n + 1) n n + 1
Also:
∑
k
1 ∑( 1
k
1 )
sk = = −
n(n + 1) n n+1
n=1 n=1
1 1 1 1 1 1
= 1− + − + − ··· + −
2 2 3 3 k k+1
1
= 1− .
k+1
Tatsächlich ist demnach limk→∞ sk = 1.
∑∞
Satz 6.4 (Cauchy–Kriterium für Reihen). Eine Reihe k=0 ak konvergiert genau
dann, wenn ∀ε > 0 ein n0 existiert, so dass:
∑
m
ak < ε ∀ m, n ≥ n0 .
k=n
∑
Insbesondere ist also bei einer konvergenten Reihe ak die Folge (ak ) eine Nullfolge.
Beweis. klar. ⊓
⊔
6.2 Konvergenzkriterien für Reihen 97
Die Konvergenz von Reihen einzusehen ist manchmal sehr einfach, wie wir
gleich an Beispielen sehen werden. Einige Kriterien für ihre Konvergenz sind
besonders leicht anzuwenden. Wir gehen hier auf die wichtigsten ein.
Definition 6.5. Eine alternierende Reihe ist eine Reihe der Gestalt
∑
∞
(−1)k ak ,
k=0
wobei ak ≥ 0 ∀k.
Satz 6.6 (Leibnizkriterium). Ist (an ) eine monoton fallende Nullfolge, so ist die
alternierende Reihe
∑∞
(−1)k ak
k=0
konvergent.
Beweis. Wir betrachten die Teilfolgen (s2n ) und (s2n+1 ) der geraden und unge-
raden Partialsummen. Dann gilt:
Ferner ist
s2n+1 = s2n − a2n+1 ≤ s2n .
Es folgt:
Daher ist (s2n ) eine monoton fallende, nach unten durch s1 beschränkte Folge
und (s2n+1 ) ist monoton wachsend, nach oben beschränkt durch s0 . Daher
existieren die Grenzwerte lim s2n und lim s2n+1 und
Daher sind beide Grenzwerte identisch, d.h. lim s2n = lim s2n+1 = s für ein
gewisses s ∈ R, also:
∑
∞
lim sk = s, also (−1)n an = s.
n=0
⊓
⊔
98 6 Reihen
und
∑
∞
1 1 1
(−1)n = 1 − + − ···
n=0
2n + 1 3 5
konvergieren nach dem Leibnizkriterium.
Schwieriger ist es, ihre Grenzwerte zu bestimmen. Es gilt:
∑
∞
1
(−1)n+1 = ln 2
n
n=1
und
∑
∞
1 1 1 1 π
(−1)n = 1 − + − + ··· = .
n=0
2n + 1 3 5 7 4
Wir werden dies erst zu einem späteren Zeitpunkt beweisen können.
∑∞
Satz 6.8 (Geometrische Reihe). Sei q ∈ R. Die Reihe n=0 qn konvergiert genau
dann, wenn |q| < 1. In dem Fall ist
∑
∞
1
qn = .
n=0
1−q
Beweis (des Satzes 6.8 über die geometrische Reihe). |q| < 1 ist notwendig, da
sonst (qn ) keine Nullfolge ist. Wir zeigen zunächst (q , 1 vorausgesetzt):
∑
n
1 − qn+1
sn = qn =
1−q
k=0
∑
0
1−q
s0 = qk = q0 = 1 = .
1−q
k=0
6.2 Konvergenzkriterien für Reihen 99
Induktionsschritt n → n + 1:
I.-V. 1 − qn+1
sn+1 = sn + qn+1 = + qn+1
1−q
1 − qn+1 + (1 − q)qn+1
=
1−q
1 − qn+2
= .
1−q
∑
n
1 − qn+1 n→∞ 1
qk = −→ .
1−q 1−q
k=0
⊓
⊔
Beispiel 6.10. Wie man aus der Schule weiß, gilt tatsächlich:
∑
∞
1 9 ∑ ( 1 )k
∞
9 1
0.99999 . . . =: 0.9 = 9· = · = · = 1.
10 n 10 10 10 1 − 10
1
n=1 k=0
1 1 1 1 1 1 1 1 1
1+ + ( + )+( + + + )+( + ··· + )+··· ,
2 3 4 5 6 7 8 9 16
| {z } | {z } | {z }
≥ 14 + 14 = 12 ≥ 48 = 12 ≥ 16
8
= 12
also:
∑2k
1 1 1 k k+2
s2k = ≥ 1 + + ··· + ≥ 1 + = .
n 2 2 2 2
k=1 | {z }
k Summanden
Die Folge der Partialsummen ist daher unbeschränkt und damit ∑ die Reihe
divergent (d.h. nicht konvergent). Beispielsweise ist die Reihe nk=0 (−1)k auch
divergent.
Die Idee, eine Folge mit einer einfacheren zu vergleichen, wollen wir genau
ausformulieren:
100 6 Reihen
∑∞ ∑∞ ∑
Definition 6.12.∑Es seien n=1 bn , n=1 an zwei Reihen. Dann heißt an eine
Majorante von bn , falls
|bn | ≤ an .
∑ ∑
an heißt Minorante von bn , wenn
an ≤ bn .
∑∞
∑∞ (Majorantenkriterium). Sei ∑
Satz 6.13 n=1 an eine konvergente Majorante der
Reihe n=1 bn . Dann konvergiert die Reihe ∞
n=1 bn .
Beweis. Das Cauchy–Kriterium für Reihen liefert: Für jedes ε > 0 existiert ein
n0 mit
∑m ∑m ∑
m
bk ≤ |bk | ≤ ak < ε,
k=n k=n k=n
∑
falls n,∑m ≥ n0 , da an konvergiert. Nun zeigt das Kriterium auch, dass die
Reihe bn konvergiert. ⊓ ⊔
∑∞
1
n=1
n2
konvergiert:
∑
Es reicht, zu zeigen dass ∞ 1
n=1 (n+1)2 konvergiert, da es auf den ersten Sum-
∑∞
1 π2
2
= .
n 6
n=1
Bemerkung 6.17.
an+1
1. < 1 ∀n ≥ n0 reicht nicht: Beispielsweise divergiert die harmonische
an
∑
Reihe ∞ 1
n=1 n , aber
1
n+1 n
= < 1 ∀n.
1
n
n+1
∑
2. Die Reihe n12 konvergiert, obwohl
1 2
( n+1 ) n2
= → 1 für n → ∞.
1
n2
(n + 1)2
∑
3. Offensichtlicherweise divergiert eine Reihe ∞ n=1 an , falls gilt:
an+1
lim = q > 1.
n→∞ an
∑∞
so ist n=0 an konvergent.
∑
Beweis. Nach Voraussetzung ist |an | ≤ qn ∀n. Also ist ∞ n
n=0 q eine konvergente
Majorante (geometrische Reihe). ⊓ ⊔
102 6 Reihen
Bei endlichen Summen spielt die Reihenfolge des Addierens keine Rolle. Bei
Reihen ist dies anders. In manchen Fällen, darf man dennoch umordnen, wie
wir sehen werden.
In dieser Reihe taucht jeder Stammbruch n1 genau einmal mit dem richtigen
1
Vorzeichen auf. Nun gilt 2k−1 − 4k−2
1
= 4k−2
1
, also:
∑
∞ (
1 1 1 ) ∑( 1
∞
1)
− − = −
2k − 1 4k − 2 4k 4k − 2 4k
k=1 k=1
1 ∑( 1
∞
1) 1
= − = s , s,
2 2k − 1 2k 2
k=1
da s > 0. Bei der alternierenden harmonischen Reihe kommt es daher auf die
Reihenfolge der Summanden an.
6.3 Umordnung von Reihen 103
konvergiert.
Bemerkung 6.21. Aus dem Cauchy–Kriterium folgt, dass aus absolut kon-
vergent schon konvergent folgt, denn:
∑
m
∆–Ungl. ∑
m
ak ≤ |ak |.
k=n k=n
∑
Satz 6.22 (Kleiner Umordnungssatz). Sei ∞ n=1 an eine
∑ absolut konvergente Reihe
und τ : N → N eine Bijektion. Dann ist auch die Reihe ∞ n=1 aτ(n) absolut konvergent
und es gilt:
∑∞ ∑
∞
an = aτ(n) .
n=1 n=1
∑
Satz 6.23 (Großer Umordnungssatz). Sei ∞ n=1 an eine absolut
∪konvergente Reihe
und (Ik )k∈N eine Familie von disjunkten Teilmengen Ik ⊂ N mit · ∞ k=1 Ik = N, ∑wobei
Ik sowohl endlich als auch abzählbar sein darf. Dann ist jede der Reihen j∈Ik a j
∑ ∑
absolut konvergent und für die Grenzwerte sk = j∈Ik a j ist die Reihe ∞ k=1 sk absolut
konvergent mit Grenzwert ebenfalls
∑
∞ ∑
∞
sk = an .
k=1 n=1
∑ ∑∞
Satz 6.24 (Cauchy–Produkt von Reihen). Es seien ∞ i=0 ai und j=0 b j zwei ab-
solut konvergente Reihen und die Folge (dk ) durch die Formel
∑
k
dk = ai bk−i
i=0
∑∞
definiert. Dann ist auch die Reihe k=0 dk absolut konvergent mit Grenzwert
∑
∞ (∑
∞ ) (∑
∞ )
dk = ai · bj .
k=0 i=0 j=0
104 6 Reihen
∑
N (∑
∞ ) (∑
∞ )
|aα(n) bβ(n) | ≤ |ai | · |b j | < ∞
n=0 i=0 j=0
i0 = max{α(0), . . . , α(N)},
j0 = max{β(0), . . . , β(N)}.
Dann gilt:
∑
N ∑
i0 ∑
j0
|aα(n) bβ(n) | ≤ |ai | · |b j |
n=0 i=0 j=0
(∑
∞ ) (∑
∞ )
≤ |ai | · |b j | < ∞
i=0 j=0
∑∞ ∑∞ ∑k
nach Voraussetzung. Die Reihe ∑ k=0 dk = k=0 i=0 ai bk−i ist eine
∑∞ Umordnung∑
der absolut konvergenten Reihe ∞ a b
α(n) β(n) , das Produkt ai · ∞ j=0 b j =
∑∞ ∑∞ n=1 i=0
i=0 j=0 ai b j ebenfalls. Nach dem großen Umordnungssatz sind ∑ alle diese
∞
Reihen
∑∞ absolut
∑∞ konvergent und haben den gleichen Grenzwert k=0 dk =
( i=0 ai )( j=0 b j ). ⊓⊔
Definition 6.25. Sei (qn ) eine Folge reeller Zahlen. Das unendliche
∏ ∏n Produkt
∞
q
k=1 k heißt konvergent, wenn der Grenzwert q = lim ∏
n→∞ q
k=1 k der Parti-
alprodukte existiert. Wir bezeichnen den Grenzwert mit q = ∞ q
k=1 k .
Satz 6.26∏(Euler). Sei s eine natürliche Zahl ≥ 2 und pk die k–te Primzahl.
∑∞ 1 Das
Produkt ∞ 1
k=1 1−p−s konvergiert und hat den gleichen Grenzwert wie n=1 ns . Für
k
s = 1 divergiert das Produkt und die Reihe. Insbesondere gibt es unendlich viele
Primzahlen.
Vorlesung vom:
12. Dezember 2008 Beweis. Wir zeigen dies in mehreren Schritten:
Qualitätsstand: ∑∞
erste Version 1. Für s ≥ 2 ist n1s ≤ n12 . Also konvergieren alle Reihen 1
absolut nach
∑ n=1 ns
dem Majorantenkriterium, da ∞ 1
n=1 n2 konvergiert.
6.3 Umordnung von Reihen 105
2. Die Reihe
1 ∑ 1 ∞
= ( s )l
1 − p1s l=0
p
Korollar 6.27. Sei N eine große Zahl und ωN die Wahrscheinlichkeit, dass zwei
zufällig gewählte Zahlen a, b ∈ N mit 0 < a ≤ N, 0 < b ≤ N keinen gemeinsamen
Faktor haben. Dann gilt:
6
lim ωN = = 0.60792 · · · ≈ 60%.
N→∞ π2
1 ∏ 1 ∑
Euler
∞
1 Fourierreihen π2
lim = = = .
N→∞ ωN 1 − p12 n 2 6
p Primzahl n=1
106 6 Reihen
Es folgt:
6
lim ωN =
= 0.60792 . . .
π2
N→∞
Leider können wir den Teil, der Fourierreihen verwendet, hier noch nicht
erklären, siehe dazu wiederum Kapitel 27 bzw. genauer Korollar 27.8. ⊓
⊔
Aufgaben
Aufgabe 6.1 (Grenzwerte von Reihen). Untersuchen Sie folgende Reihen auf
Konvergenz und geben Sie, falls er existiert, den Grenzwert an:
∑∞ 3n
1. n=0 4n+1
∑∞ 2
2. n=2 n2 −1
Aufgabe 6.3 (Konvergenz von Reihen). Sei (an ) eine monoton fallende Folge
in R>0 .
∑ ∑∞ k
Zeigen Sie: ∞n=0 an konvergiert genau dann, wenn k=0 2 a2k konvergiert.
∑∞
Aufgabe 6.4 (Umordnung). Sei n=0 an eine konvergente, aber nicht absolut
konvergente Reihe. Zeigen Sie:
1. Die Teilreihe der positiven Glieder wächst unbeschränkt, die Teilreihe der
negativen Glieder fällt unbeschränkt.
Hinweis: Integralkriterium.
7
Potenzreihen
Viele aus der Schule bekannte Funktionen wie exp, sin, cos werden am Besten
über Potenzreihen definiert. Hier werden wir die wichtigsten Eigenschaften
dieser Reihen kennen lernen. Insbesondere zählen dazu Resultate über deren
Konvergenz und Umordnungsmöglichkeiten. Da dies über den reellen Zah-
len nicht gut zu behandeln ist, beginnen wir nach ersten Beispielen mit einer
Einführung in die sogenannten komplexen Zahlen.
∑ 7.1. Sei
Definition (an )n∈N0 eine Folge reeller Zahlen und x ∈ R. Eine Reihe der
Gestalt ∞ n
n=0 an x heißt Potenzreihe.
∑∞
Beispiel 7.2. n=0 xn = 1
1−x , falls |x| < 1.
exp : R → R
Wir müssen uns noch überlegen, dass diese Reihe für jedes x ∈ R konvergiert.
Mit dem Quotientenkriterium
xn+1
(n+1)! |x|
= −→ 0
xn
n!
n + 1 n→∞
∑
∞
x2k+1 x3 x5
sin(x) := (−1)k =x− + − ···
(2k + 1)! 3! 5!
k=0
∑
∞
x2k x2 x4
cos(x) := (−1)k =1− + − ···
(2k)! 2! 4!
k=0
Definition 7.4. Die komplexen Zahlen C sind als Menge definiert durch C = R2 .
Addition und Multiplikation sind auf C wie folgt erklärt (siehe auch Abb. 7.1):
i · Im(z)
z + w = (x + u) + i(y + v)
w = u + iv
iy z = x + iy
x Re(z)
Das Nullelement ist damit 0 = (0, 0) und das Einselement der Multiplikation ist
1 = (1, 0) ∈ C.
Das Element
i := (0, 1) ∈ C
ist dann ein Element mit
7.1 Komplexe Zahlen 111
i2 = (−1, 0) = −1
und heißt imaginäre Einheit. Jede komplexe Zahl hat damit die eindeutige Darstel-
lung
z = x + iy = (x, y) mit x, y ∈ R.
x heißt Realteil von z und y Imaginärteil. Notation:
x = Re(z), y = Im(z).
Für das Rechnen mit komplexen Zahlen muss man sich nur i2 = −1 merken
und distributiv ausmultiplizieren:
Beweis. Nur die Existenz der multiplikativen Inversen ist nicht völlig trivial
nachzurechnen. Sei also z = x + iy ∈ C, z , 0, d.h. (x, y) , (0, 0). Was ist
z−1 = 1z ?
1 1 x − iy x − iy
= · = 2 ,
z x + iy x − iy x + y2
also:
1 x 1 −y
Re( ) = 2 , Im( ) = 2 .
z x + y2 z x + y2
In der Tat gilt:
1 x − iy x2 + y2
·z= 2 · (x + iy) = = 1.
z x + y2 x2 + y2
⊓
⊔
z = x − iy
i · Im(z)
iy |z| z = x + iy
x Re(z)
−iy z = x − iy
i · Im(z)
z+w
|w|
w
|z|
|w| |z + w|
z
|z|
Re(z)
Abbildung 7.3. Eigenschaften des Betrags komplexer Zahlen. Das Bild veranschau-
licht die Dreiecksungleichung |z + w| ≤ |z| + |w|.
Beweis. Wir zeigen nur die ∆–Ungleichung, die anderen Regeln sind einfach
nachzuweisen:
7.1 Komplexe Zahlen 113
|z + w|2 = (z + w)(z + w)
= zz + wz + zw +ww
| {z }
2·Re(wz)
= zz + 2Re(wz) + ww
≤ |z|2 + 2|z||w| + |w|2
= (|z| + |w|)2 .
Bemerkung 7.9. Äquivalent dazu, dass die Folge (zn ) komplexer Zahlen den
Grenzwert z ∈ C hat, ist:
i · Re(w)
)
w
e(
·R
√
2
|w| w
Re(w)
Abbildung 7.4. Obere und untere Schranke für den Betrag einer komplexen Zahl:
√
2 max{|Re(w)|, |Im(w)|} ≥ |w| ≥ max{|Re(w)|, |Im(w)|}. Im Bild ist der Fall |Re(w)| ≥
Im(w) veranschaulicht.
Ein ganz wesentlicher Grund, aus dem man komplexe Zahlen in der Mathe-
matik betrachtet, ist das folgende Resultat:
Problem:
Referenz für Funda-
Satz/Definition 7.12 (Fundamentalsatz der Algebra, ohne Beweis). Sei p(z) =
mentalsatz der Alge-
an zn + · · · + a1 z = a0 ein Polynom mit ai ∈ C vom Grad n, d.h. an , 0. Dann hat p
bra?
eine Nullstelle, d.h. ∃ z1 ∈ C : p(z1 ) = 0.
Für den Grad von p aus dem Satz schreiben wir auch deg(p) := n. Die Menge
aller Polynome in einer Variablen z und Koeffizienten in einem Körper K
bezeichnen wir mit K[z], also hier p ∈ C[z]. Die Teilmenge der Polynome in
einer Variablen z mit Koeffizienten in K vom Grad ≤ n schreiben wir K[z]≤n .
Wir geben für diesen Satz in dieser Vorlesung keinen Beweis. Man kann aber
leicht einsehen, dass aus der Existenz einer Nullstelle induktiv schon folgt:
p(z) = an · (z − z1 ) · (z − zn ),
für gewisse zi ∈ C, wobei die zi nicht unbedingt paarweise verschieden sein müssen.
In der Physik ist ein Hauptgrund, komplexe Zahlen zu verwenden, dass sich
die Quantenmechanik ohne komplexe Zahlen nicht beschreiben lässt.
konvergiert, dann konvergiert die Reihe für alle z ∈ {z ∈ C | |z| < |z0 |} absolut.
7.2 Der Konvergenzradius 115
∑∞
Beweis. Wir verwenden das Majorantenkriterium. Da die Reihe n=0 an zn0
konvergiert, bildet die Folge (an zn0 ) eine Nullfolge. Sie ist daher beschränkt,
etwa |an zn0 | ≤ M ∀n ≥ 0. Für z ∈ C mit |z| < |z0 | ergibt sich:
z n z n
|an zn | = |an | · |zn0 | · ≤M· .
z0 z0
∑∞
Da | zz0 | < 1 gilt, ist die geometrische Reihe n=0 M·| zz0 |n eine konvergente
Majorante. ⊓ ⊔
∑∞ n
Definition 7.15. Sei n=0 an z eine Potenzreihe. Dann heißt
{ ∑
∞ }
R := sup |z0 | an zn0 konvergiert ∈ [0, ∞]
n=0
(sup A = ∞, falls A nach oben nicht beschränkt ist) der Konvergenzradius der
Potenzreihe. Es gilt: Die Reihe konvergiert für alle z ∈ {z ∈ C | |z| < R} und
divergiert für alle z ∈ {z ∈ C | |z| > R} wegen Satz 7.14.
Beispiel 7.16.
∑∞
1. n=0zn hat Konvergenzradius R = 1.
∑
2. Die Reihe ∞ zn
n=1 n konvergiert im Punkt z0 = −1 und divergiert für z1 = 1
(alternierende) harmonische Reihe, daher folgt: R = 1.
∑
3. ∞ zn
n=0 n! hat Konvergenzradius R = ∞, da sie für beliebig große x ∈ R
konvergiert.
Satz 7.17. Sei (an )n∈N0 eine Folge komplexer Zahlen mit an , 0 ∀n. Existiert der
∑
Grenzwert q = limn→∞ aan+1 n
, so hat die Potenzreihe ∞ n
n=0 an z den Konvergenzradius
q, falls q > 0,
1
R=
∞, falls q = 0.
116 7 Potenzreihen
Beweis. Quotientenkriterium. ⊓
⊔
Vorlesung vom:
Die obige Formel ist nicht immer anwendbar (z.B. beim Sinus). Eine Formel, 19. Dezember 2008
die dagegen immer funktioniert, ist folgende: Qualitätsstand:
erste Version
Definition 7.18. Sei (an ) eine Folge reeller Zahlen. Dann heißt
{ }
lim sup(bn ) := lim sup bk k ≥ n
n→∞ n→∞
der Limes Superior von (bn ). Ist (bn ) nach oben nicht beschränkt, so setzen wir:
Analog ist
lim inf bn := lim inf{bk | k ≥ n},
n→∞ n→∞
radius
0, falls q = ∞,
1
R=
q, falls 0 < q < ∞,
∞, falls q = 0.
Beweis. Wurzelkriterium. ⊓
⊔
Beweis. Die Aussage von 1. ist ein Spezialfall von 2. mit Ik = {τ(k)}; wir müssen
also nur 2. beweisen. Zunächst zur absoluten Konvergenz von
∑ ( ∑ )
a j := lim aj ,
N→∞
j∈Ik j∈Ik , j≤N
∑ ∑
N ∑
∞
|a j | ≤ |an | ≤ |an | < ∞,
j∈I′ n=0 n=0
∑∞
wobei N = max{ j | j ∈ I′ }. Für die absolute Konvergenz von k=1 sk gehen
wir genauso vor:
∑
l ∑
l ∑
|sk | = lim aj
N→∞
k=1 k=1 j∈Ik , j≤N
∑
l ∑
≤ lim |a j |
N→∞
k=1 j∈Ik , j≤N
∑
= lim |a j |
N→∞ ∪
j∈ lk=1 Ik
∑
N ∑
∞
≤ lim |a j | = |an | < ∞.
N→∞
j=1 n=1
118 7 Potenzreihen
∑∞
Für die Gleichheit der Grenzwerte betrachten wir s = n=1 an und zu ε > 0
ein n0 , so dass
∑∞ n∑
0 −1
∑
k1 n∑
0 −1 ∑
k1 ∑
s− sk ≤ s − an + |an |
k=1 n=1 k=1 n∈Ik ,n≥n0
n∑
0 −1 ∑
≤ s− an + |an | < 2ε.
n=1 n≥n0
⊓
⊔
Eine der wichtigsten Potenzreihen ist jene, die die sogenannte Exponential-
funktion definiert. Beispielsweise existiert ein interessanter Zusammenhang
zu Sinus und Cosinus.
⊓
⊔
1. exp(0) = 1,
2. exp(−z) = exp(z)
1
und daher insbesondere exp(z) ∈ C∗ ∀z ∈ C, wobei C∗ :=
C\{0}. Die komplexe Exponentialfunktion ist also eine Abbildung C → C∗
(siehe auch Abb. 7.6).
Setzen wir für z einen rein imaginären Wert ein, d.h. z = iy, y ∈ R, so erhalten
wir:
∑
∞
(iy)n
exp(iy) =
n=0
n!
∑∞
y2k ∑ ∞
y2k+1
= (−1)k + i · (−1)k
2k! (2k + 1)!
k=0 k=0
= cos(y) + i sin(y),
ez := exp(z)
Die Additionstheoreme für Sinus und Cosinus folgen mit Hilfe der obigen
Formel aus denen der Exponentialfunktion:
Insbesondere gilt (mit der Notation sink α := (sin α)k und entsprechend für den cos):
1 = sin2 α + cos2 α.
Beweis. Es gilt:
wobei sich die letzte Gleichheit gemäß der Definition der Multiplikation in C
ergibt. Realteil und Imaginärteil dieser Formel ergeben die Behauptung.
Für den Zusatz betrachten wir
( )
1 = cos(0) = cos α + (−α) = cos(α) cos(−α) − sin(α) sin(−α).
Da cos(−α) = cos(α) und sin(−α) = − sin(α) gilt, weil die Potenzreihe des
Cosinus nur gerade Terme und jene des Sinus nur ungerade Terme hat, folgt
1 = cos2 α + sin2 α, wie behauptet. ⊓
⊔
Mit Hilfe des Satzes von Pythagoras kann man Sinus und Cosinus nun auf
dem Einheitskreis einzeichnen (Abb. 7.7).
Die Multiplikation der komplexen Zahlen ergibt sich direkt. Seien dazu z, w ∈
C. Dann existiert ein Winkel φ, genannt Argument von z und entsprechend
ψ, so dass
7.4 Die komplexe Exponentialfunktion 121
y
1
1
α
sin(α)
−1 1 x
cos(α)
−1
Aufgaben
1. Sei
k
j ≥ k,
j
a j,k =
k− j j < k.
k
Bestimmen Sie:
lim lim a j,k und lim lim a j,k .
k→∞ j→∞ j→∞ k→∞
1. Zeigen Sie, dass für jedes n ∈ N Polynome pn (x, y) und qn (x, y) in zwei
Variablen x, y mit reellen Koeffizienten existieren, so dass
Stetigkeit
Vorlesung vom:
... 7. Januar 2008
Qualitätsstand:
erste Version
8.1 Definition und Folgenkriterium Problem:
sinnvollen Einlei-
Definition 8.1. Sei D ⊆ R. Eine reellwertige Funktion auf D ist eine Abbildung tungstext
f : D → R.
Beispiel 8.2.
Definition 8.3. Sei f : D → R eine Funktion und x0 ∈ D ein Punkt. f heißt stetig
in x0 , wenn
+1.5
+0.3
-1.5
y
3
2
1
−3 −2 −1 1 2 3 x
−2
−3
Abbildung 8.2. Graph der entier Funktion. Ein kleiner, leerer Kreis zeigt dabei an,
dass der umkreiste Punkt nicht zum Graphen gehört.
Beispiel 8.4.
|x2 − x20 | = |x + x0 | · |x − x0 |
≤ |2x0 + 1| · |x − x0 | ∀x mit |x − x0 | < 1.
ε
Entsprechend ergibt sich |x2 − x20 | < ε ∀x mit |x − x0 | < 2|x0 |+1 . Also können
wir { ε }
δ = min 1,
2|x0 | + 1
wählen. δ hängt sowohl von ε also auch von x0 ab.
3. entier : R → R ist nicht stetig in x0 = 0: Zu ε = 1 und δ > 0 beliebig klein
existiert ein Punkt x mit |x − x0 | < δ und −1 < x < 0. Für diese gilt:
| entier(x) − entier(0)| = | − 1 − 0| = 1 ≥ ε.
8.1 Definition und Folgenkriterium 127
Allgemein gilt: entier ist in allen Punkten x0 ∈ R\Z stetig und in allen
Punkte x0 ∈ Z unstetig.
4. Die konstanten Funktionen f : R → R mit f (x) = c sind stetig.
Das Folgenkriterium ist oft gut geeignet, um Unstetigkeit zu zeigen, wie wir
am folgenden Beispiel sehen werden. Der Nachweis der Stetigkeit ist in der
Regel einfacher mit der ε-δ-Definition.
+0.75
+0.15
-0.75
falls x = 0,
0,
f (x) =
sin( 1x ), falls x , 0.
Bekanntlich gilt (wir werden in 11.14 und 11.15 die Zahl π ∈ R definieren
und die Aussage beweisen):
π (π )
1 = sin = sin + 2kπ
2 2
für jedes k ∈ Z. Also gilt für xk = π
1
zwar
2 +2kπ
Beweis (für das Folgenkriterium für Stetigkeit, Satz 8.5). f sei stetig in x0 und
(xn ) eine Folge in D mit lim xn = x0 . Da f in x0 stetig ist, existiert zu ε > 0 ein
δ > 0, so dass:
| f (x) − f (x0 )| < ε ∀x ∈ D mit |x − x0 | < δ.
Wegen lim xn = x0 gibt es zu δ > 0 ein n0 , so dass |xn − x0 | < δ ∀n ≥ n0 . Also:
Wir geben nun noch einige einfache Sätze, mit denen wir aus stetigen Funk-
tionen weitere bilden können:
f
: D′ → R
g
Korollar 8.8.
1. Polynome
f (x) = an xn + an−1 xn−1 + · · · + a1 x + a0
mit Konstanten a0 , . . . , an ∈ R sind stetige Funktionen f : R → R.
f
2. Rationale Funktionen, d.h. Abbildungen der Form g : D → R mit Polynomen
f, g, sind stetig im Definitionsbereich D = {x ∈ R | g(x) , 0}.
8.2 Der Zwischenwertsatz und Anwendungen 129
Einer der ganz zentralen Sätze über stetige Funktionen ist folgender:
Satz 8.9 (Zwischenwertsatz). Sei f : [a, b] → R eine stetige Funktion und c ein
Wert zwischen f (a) und f (b), d.h. f (a) ≤ c ≤ f (b), falls f (a) ≤ f (b) und f (b) ≤
c ≤ f (a), falls f (a) ≥ f (b). Dann existert ein ξ ∈ [a, b] (siehe auch Abb. 8.4), so dass
f (ξ) = c.
Insbesondere folgt, dass jede stetige Funktion mit f (a) < 0 und f (b) > 0 eine
Nullstelle in [a, b] hat.
a ξ b x
Abbildung 8.4. Offenbar ist im Bild f (a) ≤ c ≤ f (b), so dass nach dem Zwischenwert-
satz ein ξ mit f (ξ) = c existiert.
Beweis. Indem wir zu ±( f (x)±c) übergehen, genügt es, die zweite Aussage zu
zeigen. Sei also f (a) < 0 und f (b) > 0. Wir konstruieren induktiv monotone
Folgen, die gegen die Nullstelle konvergieren mit dem sogenannten Inter-
vallhalbierungsalgorithmus: Wir setzen zunächst x0 = a und y0 = b. Sind xn
x +y
und yn schon konstruiert, so betrachten wir x = n 2 n und f (x). Dann seien
falls f (x) < 0,
x,
xn+1 =
xn , sonst,
yn , falls f (x) < 0,
yn+1 =
x, sonst.
Bemerkung 8.11. Dass [a, b] abgeschlossen ist, ist wesentlich: Die Funktion
f (x) = 1x nimmt auf ]0, ∞[ kein Maximum und Minimum an.
Beweis (der Existenz von Maximum und Minimum, Satz 8.10). Sei
{ }
M = sup f (x) | x ∈ [a, b] ∈ R ∪ {∞}.
Wir wählen eine Folge (xn ) mit xn ∈ [a, b], so dass limn→∞ f (xn ) = M (bzw. f (xn )
unbeschränkt wächst, falls M = ∞). Nach dem Satz von Bolzano–Weierstrass
5.33 hat (xn ) eine konvergente Teilfolge (xnk ). Sei xmax := limk→∞ xnk . Dann gilt:
Bemerkung 8.12. Im vorigen Beweis kann man den Übergang zu einer Teil-
folge im Allgemeinen nicht vermeiden. Dies zeigt das Beispiel: f (x) =
1 − (x2 − 1)2 auf [−2, 2] (Abb. 8.5). Die Ausgangsfolge (xn ) könnte zwischen
den zwei Maxima xmax = ±1 hin und her springen.
8.2 Der Zwischenwertsatz und Anwendungen 131
xn xn+1 x
Abbildung 8.5. Eine Funktion mit zwei Maxima auf dem selben Niveau.
Beweis. 1. J ist ein Intervall, wenn mit y1 , y2 ∈ J auch alle Punkte zwischen
y1 und y2 in J liegen. Dies ist der Fall nach dem Zwischenwertsatz 8.9.
2. Ist f streng monoton, so ist f : I → R injektiv. Also ist f : I → J injektiv
und surjektiv, d.h. insbesondere bijektiv, so dass die Umkehrfunktion
f −1 : J → I erklärt ist.
⊓
⊔
Definition 8.15. Sei f : D → R eine Funktion und x0 ∈ R\D ein Punkt, für den es
eine Folge (xn ) mit xn ∈ D und limn→∞ xn = a gibt. Existiert für jede Folge (xn ) auf
D mit limn→∞ xn = a der Grenzwert limn→∞ f (xn ), so dass alle diese Grenzwerte
gleich sind, so bezeichnen wir mit
x2 − 1
f (x) =
x−1
ist zunächst nur auf D = R\{1} definiert. Da aber
(x − 1)(x + 1)
lim f (x) = lim = lim(x + 1) = 2
x→1 x→1 x−1 x→1
Definition 8.17. Die Notation limx↗a f (x) verwenden wir, wenn wir nur Folgen
(xn ) mit xn < a betrachten. Analog: limx↘a f (x).
Aufgaben
1
Zeigen Sie: f ist nur in 2 stetig, g ist nirgendwo stetig und h ist genau in allen
irrationalen x stetig.
Aufgabe 8.3 (Leinenwurf). In einem Raum ist eine Leine von der Fenster-
wand zur gegenüberliegenden Wand gespannt. Jetzt wird die Leine an beiden
Seiten gelöst und irgendwie in die Mitte des Raumes geworfen.
Zeigen Sie: Es gibt einen Punkt auf der Leine, der genauso weit von der
Fensterwand entfernt ist wie zuvor.
8.2 Der Zwischenwertsatz und Anwendungen 133
Differentiation
...
Problem:
sinnvollen Einlei-
tungstext
9.1 Differenzierbarkeit
Definition 9.1. Sei f : I → R eine Funktion auf einem Intervall und x0 ∈ I. f heißt
in x0 differenzierbar (kurz auch: diffbar), falls der Grenzwert
f (x) − f (x0 )
lim
x→x0 x − x0
existiert.
f (x) − f (x0 )
x − x0
als Steigung der Sekante durch die Punkte (x0 , f (x0 )) und (x, f (x)) des Gra-
phen G f interpretieren (Abb. 9.1). Der Grenzwert lässt sich also als Steigung
der Tangente an G f im Punkt (x0 , f (x0 )) interpretieren und f ist in x0 diffe-
renzierbar, wenn G f in (x0 , f (x0 )) vernünftig eine nicht senkrechte Tangente
zugeordnet werden kann.
f (x + h) − f (x)
f ′ : I → R, f ′ (x) = lim
h→0 h
nennen wir dann die Ableitung von f auf I.
136 9 Differentiation
Satz 9.4. Sei f : I → R eine Funktion und x0 ∈ I. Dann gilt: f ist differenzierbar in
x0 ⇒ f ist stetig in x0 .
f (x)− f (x0 )
Beweis. Existiert limx→x0 x−x0 , dann auch der Grenzwert
( f (x) − f (x0 ) )
lim · (x − x0 ) = lim ( f (x) − f (x0 ))
x→x0 x − x0 x→x0
und ist
f (x) − f (x0 )
lim ( f (x) − f (x0 )) = lim · lim x − x0 = 0.
x→x0 x→x0 x − x0 x→x0
Also: limx→x0 f (x) = f (x0 ), d.h. f ist stetig in x0 nach dem Folgenkriterium.
⊔
⊓
Beispiel 9.5.
′
Also: f (x) = 2x.
9.2 Rechenregeln für Ableitungen 137
fig:Betragsfunktion
In den Übungsaufgaben werden wir eine Funktion kennen lernen, die zwar
differenzierbar, aber nicht stetig differenzierbar ist.
f + g : I → R und f · g : I → R
f
: I \ { x | g(x) = 0 } → R
g
in x0 differenzierbar und es gilt die Quotientenregel:
( f )′ f ′ g − f g′
(x0 ) = (x0 ).
g g2
Beweis. Die Aussage zu f + g folgt direkt aus der Definition. Zum Nachweis
der Produktregel betrachten wir
Für die Aussage über den Quotienten untersuchen wir zunächst den Spezi-
( )′ −g′
alfall 1g = g2 :
1
g(x) − 1
g(x0 ) 1 g(x0 ) − g(x) 1
= −→ 2 (−g′ (x0 )).
x − x0 g(x)g(x0 ) x − x0 x−x0 g (x0 )
Die allgemeine Regel folgt aus dem Spezialfall mit der Produktregel:
( 1 )′ 1 −g′ f ′ g − f g′
f· = f′ · + f · 2 = .
g g g g2
⊓
⊔
Beispiel 9.8.
−kxk−1
f ′ (x) = = −kx−k+1 = nxn−1 .
(xk )2
f
2. Rationale Funktionen r = g sind auf ihrem Definitionsbereich diffbar. Ist
der Bruch gekürzt, so heißen die Nullstellen von g auch Polstellen der
rationalen Funktion.
9.2 Rechenregeln für Ableitungen 139
g ◦ f : I → R, (g ◦ f )(x) = g( f (x)),
diffbar mit
(g ◦ f )′ (x) = g′ ( f (x)) · f ′ (x).
Den Faktor f ′ (x) nennt man hierbei innere Ableitung.
Beweis. Es gilt:
(g ◦ f )(x + h) − (g ◦ f )(x) g( f (x + h)) − g( f (x)) f (x + h) − f (x)
= · .
h f (x + h) − f (x) h
Da mit h → 0 auch f (x + h) → f (x) gilt, da f stetig ist, folgt:
g( f (x + h)) − g( f (x))
−→ g′ ( f (x))
f (x + h) − f (x) h→0
und dann:
f (x + h) − f (x)
→ f ′ (x).
h
Dieses Argument ist gültig, sofern f (x+h)− f (x) , 0. Ist aber f (x+hn )− f (x) = 0
g( f (x+hn ))−g( f (x))
für eine Nullfolge (hn ), so folgt f ′ (x) = 0 und hn = 0, also gilt auch
in diesem Fall
g( f (x + hn )) − g( f (x))
lim = g′ ( f (x)) · f ′ (x) = 0.
n→∞ hn
⊓
⊔
Vorlesung vom:
Beispiel 9.10. Wir betrachten für f (x) = x2 + 1 und g(x) = x3 die Hintereinan- 14. Januar 2008
derausführung (g ◦ f )(x) = (x2 + 1)3 . Die Kettenregel ergibt: Qualitätsstand:
( )′ erste Version
(x2 + 1)3 = 3(x2 + 1)2 · 2x.
Beweis (des Satzes 9.11 über die Ableitung der Umkehrfunktion). Nach Voraus-
f (x)− f (x )
setzung ist f ′ (x0 ) , 0, also x−x0 0 , 0 für x nahe x0 . Da mit x → x0 auch
y = f (x) → y0 = f (x0 ) folgt, erhalten wir:
f −1 (y) − f −1 (y0 ) x − x0 1
= −→ .
y − y0 f (x) − f (x0 ) y→y0 f ′ (x0 )
⊓
⊔
√
Beispiel/Definition 9.12 (k–te Wurzel). Sei g(x) = k x = x1/k , k ∈ N, die
Umkehrfunktion von der streng monotonen Funktion f : R≥0 → R, f (x) = xk .
Dann erhalten wir: f ′ (x) = kxk−1 , 0 für x , 0. Es folgt: g : R≥0 → R ist auf
R>0 diffbar mit
1 1 1−k 1 1
g′ (x) = √k = x k = x k −1 .
k( x) k−1 k k
Erneut ist die Exponentenregel gültig.
Aufgaben
Ein lokales Extremum ist ein lokales Maximum oder Minimum. Gilt
Satz 10.2. Hat f : ]a, b[→ R in x0 ∈ ]a, b[ ein lokales Extremum und ist f in x0
diffbar, so gilt f ′ (x0 ) = 0.
f (x) − f (x0 )
0 ≥ lim = f ′ (x0 ) ≥ 0
x→x0 x − x0
und damit die Behauptung. ⊓
⊔
Bemerkung 10.3. f ′ (x) = 0 ist notwendig, aber nicht hinreichend für lokale
Extrema einer diffbaren Funktion, wie das folgende Beispiel (Abb. 10.2) zeigt:
f (x) = x3 erfüllt f ′ (0) = 0, aber x0 = 0 ist kein lokales Extremum.
Satz 10.4 (Satz von Rolle). Sei f : [a, b] → R eine stetige und auf ]a, b[ diffbare
Funktion mit f (a) = f (b). Dann existiert ein ξ ∈ ]a, b[ mit f ′ (ξ) = 0 (Abb. 10.3).
Beweis. Ist f konstant, dann hat jedes ξ ∈ ]a, b[ diese Eigenschaft. Anderen-
falls verwenden wir, dass f auf [a, b] sowohl Maximum als auch Minimum
annimmt. Da f (a) = f (b) und f nicht konstant ist, können Maximum und
Minimum nicht beide die Randpunkte sein. Es folgt, dass f auf ]a, b[ ein
Extremum an der Stelle ξ annimmt, das also f ′ (ξ) = 0 erfüllt. ⊓
⊔
Satz 10.5 (Mittelwertsatz (MWS)). Sei f : [a, b] → R stetig und auf ]a, b[ diffbar.
Dann existiert ein ξ ∈ ]a, b[ mit (siehe auch Abb. 10.4):
10.1 Die erste Ableitung 145
f (b) − f (a)
= f ′ (ξ).
b−a
Korollar 10.6. Sei f : [a, b] → R stetig und in ]a, b[ diffbar. Außerdem nehmen wir
an, dass m, M ∈ R existieren mit m ≤ f ′ (x) ≤ M ∀x ∈ ]a, b[. Dann gilt für x1 < x2
mit a ≤ x1 < x2 ≤ b (Abb. 10.5):
f (x2 )− f (x1 )
Beweis. Nach dem Mittelwertsatz gilt für x1 < x2 : m ≤ x2 −x1 ≤ M. ⊓
⊔
146 10 Mittelwertsatz und lokale Extrema
Korollar 10.7. Sei f : [a, b] → R stetig und in ]a, b[ diffbar. Gilt f ′ (x) = 0 ∀x ∈
]a, b[, so ist f konstant.
Beweis. Wäre f nicht konstant, so gäbe es x1 , x2 mit f (x1 ) , f (x2 ) und dann
mit dem Mittelwertsatz ein ξ ∈ ]a, b[ mit f ′ (ξ) , 0, im Widerspruch zur
Voraussetzung. ⊓ ⊔
Satz 10.8. Es sei f : [a, b] → R stetig und in ]a, b[ diffbar. Gilt f ′ (x) > 0 (bzw. ≥ 0,
< 0, ≤ 0) ∀x ∈ ]a, b[, dann ist f streng monoton wachsend (bzw. monoton wachsend,
streng monoton fallend, monoton fallend).
f (n) := ( f (n−1) )′
existiert.
Satz 10.10 (hinreichendes Kriterium für Extrema). Sei f : ]a, b[→ R zweimal
diffbar. Ist f ′ (x0 ) = 0 und f ′′ (x0 ) , 0, so hat f in x0 ein isoliertes lokales Extremum.
Dieses ist ein Maximum, wenn f ′′ (x0 ) < 0 und ein Minimum, wenn f ′′ (x0 ) > 0.
Beweis. Wir betrachten den Fall, dass f ′ (x0 ) = 0 und f ′′ (x0 ) < 0. Dann gilt:
f ′ (x) − f ′ (x0 )
lim < 0.
x→x0 x − x0
10.2 Höhere Ableitungen 147
f ′ (x) > 0 für x ∈ ]x0 − ε, x0 [ und f ′ (x) < 0 für x ∈ ]x0 , x0 + ε[.
Beispiel 10.11. Sei f (x) = x2 . Dann ist f ′ (x) = 2x, f ′′ (x) = 2 > 0 ∀x, also
f ′ (0) = 0, f ′′ (0) > 0. Daher ist 0 ein Minimum von f . Analog ist 0 ein Maximum
von g(x) = −x2 , da g′ (0) = 0 und g′ (0) < 0. Siehe auch Abb. 10.6.
Vorlesung vom:
Definition 10.12. Sei f : ]a, b[→ R dreimal diffbar. Ein Punkt x0 ∈ ]a, b[ mit 16. Januar 2008
f ′′ (x0 ) = 0, f ′′′ (x0 ) , 0 heißt Wendepunkt von f . Ist f ′ (x0 ) = 0, so heißt x0 Qualitätsstand:
Sattelpunkt von f . noch der Mitschrift an-
passen
Problem:
Was ist mit x 7→ x5 ?
Besser Definition mit
konkav zu konvex?
Beispiel 10.14. Sei f (x) = x3 − x. Es ist f ′′ (x) = 6x, f ′′′ (x) = 6 , 0. Diese
Funktion ändert sich im Wendepunkt x0 = 0 von konkav zu konvex.
Satz 10.15. Sei f : I → R eine zwei Mal diffbare Funktion auf einem Intervall I.
Dann gilt:
f ist konvex ⇐⇒ f ′′ (x) ≥ 0 ∀x ∈ I.
Mit den bisherigen Resultaten in diesem Kapitel können wir nun also die
aus der Schule bekannte Kurvendiskussion zum Studium des Aussehens re-
eller Funktionen in einer Variablen durchführen, sofernd diese ausreichend
oft differenzierbar sind. Ein Problem haben wir allerdings noch vernachläs-
sigt, nämlich die Berechnung der Nullstellen solcher Funktionen. Von einigen
speziellen Funktionen, wie beispielsweise Polynomen vom Grad ≤ 2 können
wir sie bestimmen, doch wie sieht es im Allgemeinen aus? Hierzu liefert ein
Iterationsverfahren, nämlich das sogenannte Newtonverfahren, näherungs-
weise eine Möglichkeit, zumindest, wenn man sich schon nahe genug an einer
der Nullstellen befindet.
Sei also f : [a, b] → R eine zweimal diffbare Funktion mit f (a) < 0, f (b) > 0.
Die Idee ist folgende: Ist x0 ein Startwert, so setzen wir:
f (xn )
xn+1 := xn − ,
f ′ (xn )
d.h. xn+1 ist die Nullstelle der Tangente in (xn , f (xn )) an den Graphen von f
(Abb. 10.9).
Satz/Definition 10.16. Sei f : [a, b] → R zweimal diffbar, f (a) < 0, f (b) > 0 und
konvex. Dann gilt:
2. Ist x0 ∈ [a, b] ein beliebiger Startwert mit f (x0 ) ≥ 0, so konvergiert die Folge
f (x )
(xn ) mit xn+1 = xn − f ′ (xnn ) monoton fallend gegen ξ.
3. Ist f ′ (x) ≥ c > 0 und f ′′ (x) < k ∀x ∈ [ξ, b], so gilt die Abschätzung:
k
|xn+1 − xn | ≤ |ξ − xn | ≤ |xn − xn−1 |2 .
2c
Man sagt deshalb, dass das Newtonverfahren quadratisch konvergiert.
x2n − a 1 ( a)
xn+1 = xn − = xn +
2xn 2 xn
√
unser Verfahren zur Berechnung der Quadratwurzel a aus Satz 5.27.
Dafür gilt:
ψ fällt also monoton. Da ψ′ (xn−1 ) = 0 ist, folgt: ψ′ (x) ≥ 0∀x ∈]ξ, xn−1 [. Da
außerdem ψ(xn−1 ) = 0 ist, gilt auch: ψ(x) ≤ 0 ∀x ∈]ξ, xn−1 [ und insbeson-
dere ψ(xn ) ≤ 0, d.h. f (xn ) ≤ 2k (xn −xn−1 )2 , da f (xn−1 )+ f ′ (xn−1 )(xn −xn−1 ) = 0.
Also: |xn+1 − xn | ≤ |ξ − xn | ≤ 2ck (xn − xn−1 )2 .
⊓
⊔
Aufgaben
x3 − 3x
f1 (x) =
x2 − 4
f2 (x) = xe− x
1
f3 (x) = 2 cos x − x2
10.3 Das Newtonverfahren zur Berechnung von Nullstellen 151
Aufgabe 10.2 (Extrema). Sei a ∈ R. Bestimmen Sie alle Minima und Maxima
der Funktion
f (x) = sin(x + a) sin(x − a).
11
Spezielle Funktionen
∑
N
xn
exp(x) = + rN+1 (x).
n=0
n!
Dann gilt:
|x|N+1 N
|rN+1 (x)| ≤ 2 für |x| ≤ 1 + .
(N + 1)! 2
154 11 Spezielle Funktionen
∑∞ xn
Beweis. Es ist rN+1 (x) = n=N+1 n! , also:
∑
∞
|xn |
|rN+1 (x)| ≤
n!
n=N+1
|x| N+1( |x| |x|2 )
= 1+ + + ···
(N + 1)! N + 2 (N + 2)(N + 3)
|x|N+1 ∑
∞ (
|x| )k
≤ ·
(N + 1)! N+2
k=0
|x|
N+1
1
≤ ·
(N + 1)! 1 − 1
2
|x|N+1
= 2· ,
(N + 1)!
wie behauptet. ⊔
⊓
Satz 11.2. Die Funktion exp : R → R ist diffbar mit exp′ (x) = exp(x).
Beweis. Wir zeigen zunächst, dass exp′ (0) = 1 gilt. Dazu bemerken wir, dass
exp(x)−1 ∑ xn−1 rN+1 (x)
x = N
n=1 n! + x . Wegen
folgt:
exp(x) − exp(0) (∑
N
xn−1 )
exp′ (0) = lim = lim + 0 = 1.
x→0 x x→0 n!
n=1
Direkt folgt:
Korollar 11.3. exp ist streng monoton steigend und konvex (Abb. 11.1).
Das häufige Auftreten der Exponentialfunktion bei der Beschreibung von Na-
turvorgängen liegt daran, dass y = ecx eine Lösung der Differentialgleichung
y′ = cy ist. Genauer gilt:
11.2 Der Logarithmus 155
Abbildung 11.1. Die Exponentialfunktion ist streng monoton steigend und konvex.
Satz 11.4. Sei f : I → R eine Funktion auf einem Intervall, die f ′ = c f erfüllt. Dann
gilt:
f (x) = f (x0 ) · ec(x−x0 ) ,
wobei x0 ∈ I ein beliebiger fester Punkt ist.
Beweis. Wir betrachten die Funktion h(x) = f (x) · e−cx . Dann gilt:
für jedes x ∈ I. Es folgt, dass h konstant ist. Setzen wir x0 ein, so erhalten wir:
Die Abbildung exp : R → R>0 ist bijektiv und wegen des Additionstheorems
ein sogenannter Isomorphismus von Gruppen (R, +) → (R>0 , ·), d.h. in die-
sem Spezialfall: exp(x + y) = exp(x) · exp(y) für alle x, y ∈ R. Genauer werden
wir Gruppen im zweiten Semester kennen lernen.
1. ln(x1 · x2 ) = ln x1 + ln x2 .
2. ln ist diffbar mit (ln x)′ = 1x .
156 11 Spezielle Funktionen
1 1
ln′ (x) = = .
exp(ln x) x
Definition 11.7. Sei a ∈ R>0 . Dann definieren wir die Exponentiation zu einer
beliebigen Basis durch
ax := ex·ln a .
Beweis. Die erste und letzte Aussage sind klar. Für die verbleibende betrach-
ten wir zunächst ganzzahlige positive Exponenten n ∈ Z>0 . Es gilt:
an (= a · · · a ) = (eln a )n = en ln a .
|{z}
n Mal
1 1
= k ln a = e−k ln a = en ln a .
an =
ak e
√q p
Im Allgemeinen Fall müssen wir zeigen, dass ap = e q ln a , was äquivalent ist
p
zu ap = (e q ln a )q und Letzteres ist tatsächlich gleich ep ln a = (eln a )p = ap . ⊓
⊔
loga : R>0 → R
1 1
(loga )′ (x) = = .
ln a · a a
log x x ln a
Besonders wichtig für die Informatik ist log2 n, die Anzahl der Binärstellen
einer natürlichen Zahl n, d.h. die Anzahl der Bits Information.
f : R>0 → R, f (x) = xx .
Wir hatten Sinus und Cosinus in Beispiel 7.3 bereits durch Potenzreihen
definiert:
Problem:
trigonometrisch defi-
nieren
158 11 Spezielle Funktionen
∑
∞
x2k+1 ∑ ∞
x2k
sin(x) = (−1)k und cos(x) = (−1)k .
(2k + 1)! (2k)!
k=0 k=0
Außerdem haben wir in Satz 7.25 bereits die Additionstheoreme und insbe-
sondere sin2 x + cos2 x = 1 ∀x ∈ R gezeigt.
Beweis. Zunächst zeigen wir: sin′ (0) = 1 = cos(0) und cos′ (0) = 0 = sin 0:
sin h − 0 (∑∞
h2k )
sin′ (0) = lim = lim (−1)k = 1,
h→0 h h→0 (2k + 1)!
k=0
cos h − 1 (∑
∞
h2k−1 )
cos′ (0) = lim = lim (−1)k = 0.
h→0 h h→0 (2k)!
k=1
⊓
⊔
Als nächstes werden wir die Zahl π definieren. Dazu zunächst ein Hilfssatz:
Beweis. 1. Da wir cos(0) = 1 schon im Beweis von Satz 11.12 gesehen ha-
ben, beginnen wir mit cos(2). Dies ist eine alternierende Reihe monoton
fallender Glieder, denn:
22k 22k+2
> ⇐⇒ (2k + 1)(2k + 2) > 22 ⇐⇒ k ≥ 1.
2k! (2k + 2)!
Es folgt:
22 22 24 16 2 1
−1 = 1 − ≤ cos 2 ≤ 1 − + =1−2+ = −1 + = − .
2 2 4! 24 3 3
11.3 Trigonometrische Funktionen 159
2. Es gilt:
x2k+1 x2k+3
> ⇐⇒ (2k + 2)(2k + 3) > x2 .
(2k + 1)! (2k + 3)!
Für k ≥ 0 und 0 ≤ x ≤ 2 ist aber tatsächlich: 2k + 3 ≥ 2k + 2 ≥ x ≥ 0, d.h.
(2k + 2)(2k + 3) > x2 . Für x ∈ ]0, 2] folgt:
x3 ( x2 ) ( 22 )
x ≥ sin x ≥ x − =x· 1− ≥x· 1− > 0,
6 6 6
was zu zeigen war.
⊓
⊔
Korollar/Definition 11.14. cos ist in [0, 2] monoton fallend und wegen cos(0) = 1,
cos(2) < 0 hat cos genau eine Nullstelle in [0, 2]. Wir definieren die (auch Kreiszahl
genannte) Zahl π durch: π2 ist die Nullstelle von cos in [0, 2]. Also:
(π) (π)
cos = 0, sin = 1.
2 2
Man sagt, dass Sinus und Cosinus periodische Funktionen mit Periode 2π
sind (Abb. 11.4). Der Wert von π ist
π = 3.1415 . . .
1 cos x
cot : R \ {kπ | k ∈ Z} → R, x 7→ cot x = =
tan x sin x
Cotangens. Siehe auch Abb. 11.5.
Satz/Definition 11.18.
2. Die Abbildung
[ π π]
sin : − , → [−1, 1]
2 2
ist streng monoton steigend. Die Umkehrfunktion
[ π π]
arcsin : [−1, 1] → − ,
2 2
heißt Arcussinus. Siehe dazu auch Abb. 11.6.
Satz 11.19.
1
arcsin′ (x) = √ .
1 − x2
Beweis.
1. Wir haben schon gesehen, dass sin′ = cos. Damit erhalten wir:
1
arcsin′ (x) =
cos(arcsin(x))
1
= √
1 − sin2 (arcsin(x))
1
= √ .
1 − x2
162 11 Spezielle Funktionen
1
= .
1 + x2
⊓
⊔
nicht oder nur knapp
Analog kann man auch einen Arcuscosinus definieren und dessen Ableitung
vorgetragen ...
ausrechnen, nämlich
arccos : [−1, 1] → [0, π]
als Umkehrfunktion von cos : [0, π] → [−1, 1]. Mit den Additionstheoremen
(Satz 7.25) sieht man recht leicht, dass man die Arcusfunktionen ineinander
umrechnen kann:
π
arccos(x) = − arcsin(x).
2
Analog zur Ableitung des Arcussinus erhält man jene des Arcuscosinus:
1
arccos′ (x) = − √ .
1 − x2
nicht oder nur knapp
vorgef"uhrt
Aufgaben
ln x + ln y x+y
≤ ln .
2 2
12
Vorlesung vom:
Grenzwerte rationaler Funktionen sind mit den bisherigen Mitteln oft nicht 23. Januar 2008
einfach zu berechnen. Die Regel von L’Hospital1 ist in solchen Situationen
Qualitätsstand:
oft hilfreich. Insbesondere werden wir damit das asymptotische Verhalten erste Version
rationaler Funktionen recht einfach untersuchen können.
Satz 12.1 (Regel von L’Hospital). Seien f, g : [a, b] → R stetige Funktionen, auf
]a, b[ differenzierbar mit g′ (x) , 0 ∀x ∈ ]a, b[ und f (a) = g(a) = 0. Existiert
f ′ (x) f (x)
limx↘a g′ (x) , dann existiert auch limx↘a g(x) und es gilt:
f (x) f ′ (x)
lim = lim ′ .
x↘a g(x) x↘a g (x)
f (0)
Beispiel 12.2. f (x) = sin(x), g(x) = ex − 1, [a, b] = [0, 1]. Der Quotient g(0) = 0
0
macht keinen Sinn, aber
f ′ (x) cos x
= x
g′ (x) e
ist stetig in x = 0 mit
1
Wikipedia sagt dazu: Die Regel ist nach Guillaume Francois Antoine, Marquis
de L’Hospital (1661–1704) benannt. L’Hospital veröffentlichte sie 1696 in seinem Buch
Analyse des infiniment petits pour l’intelligence des lignes courbes, dem ersten Lehrbuch
der Differentialrechnung. Er hatte sie aber nicht selbst entdeckt, sondern von Johann
Bernoulli übernommen.
164 12 Asymptotisches Verhalten und Regel von L’Hospital
f ′ (x) cos 0 1
lim = 0 = = 1.
x↘0 g′ (x) e 1
Also existiert
sin x cos x 1
lim = lim = = 1.
x↘0 ex − 1 x↘0 ex 1
Die Idee des Beweises der Regel von L’Hospital ist es, ein Analogon des
Mittelwertsatzes anzuwenden, nämlich folgendes:
Lemma 12.3. Seien f, g : [a, b] → R stetig, auf ]a, b[ diffbar mit g′ (x) , 0 ∀x ∈]a, b[
und g(a) , g(b). Dann existiert ein ξ ∈ ]a, b[, so dass:
f (b) − f (a) f ′ (ξ)
= ′ .
g(b) − g(a) g (ξ)
Beweis (von L’Hospitals Regel, Satz 12.1). Da g′ (x) , 0 ∀x ∈ ]a, b[ und g(a) = 0,
ist g(x) , 0 ∀x ∈ ]a, b[ nach dem Satz von Rolle. Ferner gilt nach dem Lemma:
f (x) f (x) − f (a) f ′ (ξ)
= = ′
g(x) g(x) − g(a) g (ξ)
für ein ξ ∈ ]a, x[. Mit x ↘ a strebt auch ξ ↘ a. Also:
f (x) f ′ (ξ) f ′ (ξ)
lim = lim ′ = lim ′ .
x↘a g(x) ξ↘a g (ξ) x↘a g (ξ)
⊓
⊔
Von der sehr nützlichen Regel von L’Hospital gibt es viele Varianten. Um ei-
nige wichtige davon formulieren zu können, benötigen wir folgende Grenz-
wertbegriffe:
12.1 Die Regel von L’Hospital 165
Definition 12.4 (Konvergenz für x → ∞). Sei f : [a, ∞[→ R eine Funktion. Wir
sagen, f (x) strebt gegen c ∈ R für x gegen ∞, in Zeichen
lim f (x) = c,
x→∞
falls
∀ε > 0 ∃ N : | f (x) − c| < ε ∀x ≥ N.
Wir sagen: limx→∞ f (x) = ∞, falls
∀M > 0 ∃ N > 0 : f (x) > M ∀x > N.
Für f : ]a, b] → R schreiben wir limx↘a f (x) = ∞, falls
∀M > 0 ∃ ε > 0 : f (x) > M ∀x > a mit |x − a| < ε.
Analog lassen sich limx→−∞ f (x) = c oder etwa limx↗b f (x) = −∞ definieren.
oder
lim f (x) = ∞ = lim g(x).
x→∞ x→∞
f ′ (x) f (x)
Existiert limx→∞ g′ (x) , dann existiert auch limx→∞ g(x) und es gilt:
f (x) f ′ (x)
lim = lim ′ .
x→∞ g(x) x→∞ g (x)
Beispiel 12.6. Wir zeigen: Für jedes n ∈ N ist
xn
= 0. lim
x→∞ ex
Für Folgen haben wir in Abschnitt 5.3 die O– und o–Notation eingeführt.
Analog nun für Funktionen, um Aussagen wie die obige, dass ex schneller als
jedes Polynom wächst, präzise formulieren zu können.
Definition 12.7 (O– und o– Notation für Funktionen). Seien f, g : [a, ∞[→ R
Funktionen. Wir schreiben
f ∈ O(g) für x → ∞,
Beispiel 12.8.
| f (x)| ≤ C · xn ∀x ≥ M.
f (x)
Sei h(x) = g(x) eine rationale Funktion mit Polynomen
f (x) = an xn + · · · + a0 ∈ R[x],
g(x) = bm xm + · · · + b0 ∈ R[x],
vom Grad n bzw. m, d.h. an , bm , 0. Dann gilt, beispielsweise mit der Regel
von L’Hospital:
f (x)
lim = 0, falls n < m,
x→∞ g(x)
f (x) an
lim = , falls n = m,
x→∞ g(x) bm
f (x) +∞, falls n > m und an
> 0,
lim =
bm
x→∞ g(x) −∞, falls n > m und an
bm < 0.
Satz 12.9 (Division mit Rest). Seien f, g ∈ R[x] Polynome in einer Variablen x
mit reellen Koeffizienten. Dann existieren eindeutig bestimmte Polynome q(x), r(x) ∈
R[x], so dass:
Beweis. Zunächst zur Existenz, mit Induktion nach deg f . Für deg f < deg g
können wir q = 0 und r = f wählen. Ist n = deg f ≥ deg g = m, etwa
f = an xn + · · · + a0 , g = bm xm + · · · + b0
f = f1 + q0 · g = (q0 + q1 ) · g + r1 .
Es folgt:
deg(q̄ · g) ≥ 0 + deg g > deg(r̄),
also q̄ · g + r̄ , 0, ein Widerspruch. Also: q = q̃ und r = r̃. ⊓
⊔
f (x) x3
h(x) = = 2 .
g(x) x − 1
Der Beweis des Satzes zur Division mit Rest gibt einen Algorithmus an, um
diese durchzuführen. Hier ergibt sich:
x3 : (x2 − 1) = x + x
x2 −1
,
x3 − x
x
Wie wir im Beispiel gesehen haben, liefert Division mit Rest sofort auch eine
Aussage über das asymptotische Verhalten rationaler Funktionen:
168 12 Asymptotisches Verhalten und Regel von L’Hospital
y
+3.75
+0.75
-3.75
Abbildung 12.1. Graph einer rationalen Funktion mit Polstellen bei x = ±1, einem
Sattelpunkt in x = 0 und asymptotischen Verhalten wie die Gerade x 7→ x.
f (x)
Korollar 12.11. Sei h(x) = g(x) eine rationale Funktion und
mit deg r < deg g. Dann verhält sich h für x → ±∞ wie q(x), genauer:
Problem:
kurzen Beweis geben
Um zu sehen, dass Asymptoten nicht immer Geraden sein müssen, betrachten
wir zum Abschluss noch ein etwas komplizierteres Beispiel:
x4 +1
Beispiel 12.12. Wir betrachten die rationale Funktion h(x) = x2 +1
. Division
mit Rest liefert:
(x4 + 1) : (x2 + 1) = x2 − 1 + x22+1 ,
x4 + x2
− x2 + 1
− x2 − 1
2
d.h. q = x2 − 1 und r = 2. Offenbar hat h(x) keine Polstelle. Wir bestimmen die
Extrema, um eine Skizze des Graphen von h(x) zeichnen zu können. Für die
Ableitung ergibt sich:
Man kann nachrechnen, dass x = 0 ein lokales Maximum und x1,2 lokale
Minima sind. Da sich h(x) für x → ±∞ wie q = x2 − 1 verhält, erhalten wir in
etwa das in Abb. 12.2 gezeigte Schaubild.
+2.5
+0.5
−2.5 +1 +2.5 x
-0.5
-2.5
Abbildung 12.2. Eine rationale Funktion mit der Parabel x 7→ x2 − 1 als Asymptote.
Aufgaben
2 cos x + ex + e−x − 4 1
lim 4
= ,
x→0 x 6
√ √
cos ax − cos bx b2 − a2
lim = für a, b ∈ R.
x→0 x2 4
( )
Aufgabe 12.4 (Die Eulersche Zahl). Zeigen Sie limn→∞ n ln(1 + n1 ) = 1 und
folgern Sie daraus:
( 1 )n
lim 1 + = e.
n→∞ n
13
Integration
Vorlesung vom:
Sei f : [a, b] → R eine Funktion auf einem abgeschlossenen Intervall. Wir 28. Januar 2008
wollen die Fläche unter dem Graphen von f bestimmen.
Qualitätsstand:
erste Version
13.1 (Riemann–)Integrierbarkeit
Für φ(ti ) ist nichts vorausgesetzt. Das Integral einer Treppenfunktion ist
∫ b ∑
n
φ(x) dx := ci (ti − ti−1 ).
a i=1
Eine solche Summe heißt Riemmannsche Summe. Mit deren Hilfe können wir
Integrale komplizierterer Funktionen definieren: Sei dazu f : [a, b] → R eine beliebige
beschränkte Funktion. Das Oberintegral von f ist
∫ ∗b {∫ b }
f := inf ψ dx ψ ≥ f, ψ Treppenfunktion ,
a a
das Unterintegral
∫ b {∫ b }
f := sup φ dx φ ≤ f, φ Treppenfunktion .
∗a a
gilt. In diesem Fall definieren wir das Integral der beschränkten Funktion
f : [a, b] → R durch:
∫ b ∫ ∗b ∫ b
f (x) dx := f = f.
a a ∗a
13.1 (Riemann–)Integrierbarkeit 173
Beweis. Sei f : [a, b] → R monoton steigend und ε > 0 vorgegeben. Wir wäh-
len n so groß, dass
1 ( )
ε > · (b − a) · f (b) − f (a) ,
n
setzen h = b−a
n und betrachten die Zerlegung
ti = a + i·h, i = 0, . . . , n.
φ [t = f (ti−1 ), ψ [t = f (ti )
i−1 ,ti [ i−1 ,ti [
und φ(b) = ψ(b) = f (b) gilt dann φ ≤ f ≤ ψ wegen der Monotonie. Anderer-
seits:
∫ ∫ ∑n ( )
ψ dx − φ dx = f (ti ) − f (ti−1 ) ·h
i=1
( ) b−a ( )
= h· f (b) − f (a) = · f (b) − f (a) < ε.
n
⊓
⊔
∫b
Beispiel 13.5. Seien 0 ≤ b. Was ist 0 x2 dx ? f (x) = x2 ist monoton auf [0, b],
also existiert das Integral. Zur sogenannten äquidistanten Unterteilung
b
ti = i · , i = 0, . . . , n,
n
des Intervalls [0, b] und der Treppenfunktion ψ mit ψ ]t ,t [ = f (ti ) und h = b
n
i−1 i
gilt:
∫ b ∑n
n(n + 1)(2n + 1) b3 b3
ψ dx = i2 ·h2 ·h = · 3 −→ .
0 6 n n→∞ 3
i=1
∫b 3
Also: 0 x2 dx = b3 .
174 13 Integration
ist nicht integrierbar, denn für jedes Paar φ, ψ von Treppenfunktionen mit
φ ≤ f ≤ ψ gilt:
∫ 1 ∫ 1
φ(x) dx ≤ 0, ψ(x) dx ≥ 1,
0 0
Für den Beweis benötigen wir mehr als nur die punktweise Stetigkeit:
Der entscheidende Unterschied zur Stetigkeit in allen Punkten ist, dass hier
δ = δ(ε) nicht von x0 abhängt, sondern nur von ε.
Satz 13.10. Sei f : [a, b] → R eine auf einem abgeschlossenen, beschränkten Inter-
vall stetige Funktion. Dann ist f gleichmäßig stetig.
13.1 (Riemann–)Integrierbarkeit 175
Nach Bolzano–Weierstrass hat die Folge (xn ) eine konvergente Teilfolge (xnk );
sei
x0 = lim (xnk ) ∈ [a, b]
k→∞
ε
deren Grenzwert. Da f in x0 stetig ist, existiert zu 2 ein δ, so dass
ε
| f (x) − f (x0 )| < für x ∈ [a, b] mit |x − x0 | < δ.
2
δ
Wir wählen jetzt k so groß, dass |xnk − x0 | < 2 und δnk < 2δ . Dann gilt auch:
δ
|ynk − x0 | ≤ |ynk − xnk | + |xnk − y0 | ≤ δnk + <δ
2
und
ε ε
| f (xnk ) − f (ynk )| ≤ | f (xnk ) − f (x0 )| + | f (ynk ) − f (x0 )| < + = ε,
2 2
im Widerspruch zu | f (xn ) − f (yn )| ≥ ε ∀n. ⊔
⊓
Beweis (von Satz 13.7 über die Integrierbarkeit stetiger Funktionen). Es sei
f : [a, b] → R stetig. Nach Satz 13.10 ist f sogar gleichmäßig stetig. Sei ε > 0
nun vorgegeben. Wir konstruieren Treppenfunktionen
∫ b
φ ≤ f ≤ ψ mit (ψ − φ) dx < ε.
a
ε
Zu b−a > 0 wählen wir ein δ > 0, so dass
ε
| f (x) − f (y)| < ∀ x, y ∈ [a, b] mit |x − y| < δ.
b−a
Wir wählen dann n so groß, dass h = b−a n < δ und ti = a + i·h. Dann sei
φ [t ,t [ = min{ f (x) | x ∈ [ti−1 , ti ]} und ψ [t ,t [ = max{ f (x) | x ∈ [ti−1 , ti ]}. Da
i−1 i i−1 i
Minimum und Maximum angenommen werden und h < δ ist, gilt
∫ b
ε ε
0 ≤ ψ(x) − φ(x) < ⇒ 0≤ (ψ(x) − φ(x)) dx < ·(b − a) < ε.
b−a a b−a
⊓
⊔
∫b ∫b
2. (Monotonie des Integrals) f ≤ g ⇒ a
f (x) dx ≤ a
g(x) dx.
3. Mit f sind auch die Funktionen f+ := max( f, 0), f− := max(− f, 0) und
| f | = f+ + f− integrierbar.
4. Zu p ∈ R>0 ist auch | f |p integrierbar. Insbesondere ist auch
1( )
f ·g= | f + g|2 − | f − g|2
4
integrierbar.
impliziert Gleichheit.
2. Aus f ≥ g folgt (φ ≤ f ⇒ φ ≤ g) und daher
∫ ∫
f dx ≤ g dx.
∗ ∗
∫∗ ∫∗
Analog: f dx ≤ g dx.
3. Mit φ ist auch φ+ = max(φ, 0) eine Treppenfunktion und φ ≤ f ≤
ψ ⇒ φ+ ≤ f+ ≤ ψ+ . Außerdem ist
∫ b ∫ b
0≤ (ψ+ − φ+ ) dx ≤ (ψ − φ) dx < ε
a a
Beweis. Seien
M = max{ f (x) | x ∈ [a, b]}, m = min{ f (x) | x ∈ [a, b]}.
Dann gilt:
mg(x) ≤ f (x)g(x) ≤ Mg(x),
da g ≥ 0. Die Monotonie des Integrals ergibt:
∫ b ∫ b ∫ b
m· g(x) dx ≤ f (x)g(x) dx ≤ M · g(x) dx.
a a a
∫b
Ist a g(x) dx = 0, dann ist nichts mehr zu zeigen. Andernfalls existiert nach
dem Zwischenwertsatz ein ξ, so dass
∫b
f (x)g(x) dx
m ≤ a∫ b = f (ξ) ≤ M.
a
g(x) dx
Die Behauptung folgt. Der Spezialfall ist der Fall g(x) = 1 ∀x ∈ [a, b]. ⊓
⊔
178 13 Integration
Die Berechnung von Integralen mittels Ober– und Untersumme und Grenz-
wertbildung ist mühselig. Die Hauptmethode, Integrale zu bestimmen, ist
es, sämtliche Integrale
∫ t
f (x) dx
a
Satz 13.13. Sei f : [a, b] → R eine integrierbare Funktion. Dann ist f auch über
jedem abgeschlossenen Teilintervall von [a, b] integrierbar und es gilt (s. Abb. 13.5):
∫ t ∫ b ∫ b
f (x) dx + f (x) dx = f (x) dx ∀t ∈]a, b[.
a t a
13.2 Stammfunktionen
(G − F)′ = f − f = 0,
F(x) − F(x0 )
F′ (x0 ) = lim = lim f (ξ) = f (x0 ).
x→x0 x − x0 ξ→x0
180 13 Integration
Beispiel 13.18. Wir haben bereits gesehen, dass die folgenden Stammfunk-
tionen tatsächlich die behaupteten Ableitungen haben:
∫ α+1
1. xα dx = xα+1 , α , −1.
∫
2. 1x dx = ln |x|.
∫
3. ex dx = ex .
∫
4. sin x dx = − cos x.
∫
5. cos x dx = sin x.
∫
2 dx = arctan x.
1
6. 1+x
∫
7. √ 2 dx = arcsin x.
1
1+x
Jede Ableitungsregel liefert eine Regel für die Berechnung von Stammfunk-
tionen. Die Kettenregel ergibt:
Beispiel 13.20. Recht häufig kann man folgenden Spezialfall der Substituti-
onsregel anwenden:
1
(ln(g(t))′ = · g′ (t).
g(t)
Bemerkung 13.21. Häufig merkt man sich die Substitutionsregel in der Form
dx
x = φ(t), = φ′ (t),
dt
also „dx = φ′ (t) dt”. Wir haben zwar nicht formal nachgewiesen, dass eine
solche Schreibweise sinnvoll ist, es liefert aber das richtige Ergebnis:
∫ ∫
F(x) = f (x) dx ⇒ F(φ(t)) = f (φ(t))·φ′ (t) dt,
bzw. ∫ ∫
b b
′ b
f (x)g(x) dx = f (x)g(x) a
− f (x)g′ (x) dx
a a
182 13 Integration
Beweis. Produktregel. ⊓
⊔
Beispiel 13.23.
1. Es gilt:
∫ π
π π
x sin x dx = (−x cos x) 0
+ sin x 0
= −π · (−1) = π,
0
da wir bei der partiellen Integration g(x) = x, d.h. g′ (x) = 1 und f ′ (x) =
sin x, d.h. f (x) = cos x wählen können.
∫
2. Wir berechnen e−x sin x dx. Dazu setzen wir f ′ (x) = e−x , d.h. f (x) = −e−x ,
g(x) = sin x, d.h. g′ (x) = cos x. Partielle Integration liefert:
∫ ∫
e−x sin x dx = −e−x sin x + e−x + cos x dx.
Auf das letzte Integral wenden wir wieder partielle Integration an und
erhalten:
∫ ∫
e−x cos x dx = −e−x cos x − (−e−x )(− sin x) dx.
Insgesamt folgt
∫
2· e−x sin x dx = −e−x (sin x + cos x),
also: ∫
1
e−x sin x dx = − e−x (sin x + cos x).
2
Zur Sicherheit machen wir die Probe:
( 1 )′ 1 1
− e−x (sin x + cos x) = e−x (sin x + cos x) − e−e (cos x + sin x),
2 2 2
was tatsächlich e−x sin x ergibt.
∫ 2π
3. Wir zeigen, dass 0 sin2 x dx = π. Dazu setzen wir f (x) = sin x, g′ = sin x,
so dass g = − cos x, f ′ = − cos x und erhalten:
∫ ∫
sin2 x dx = − sin x cos x + cos2 x dx.
Definition 13.24. Die Menge der elementaren Funktionen ist die kleinste Menge
von Funktionen, die folgendes erfüllt:
Satz 13.25 (ein Satz von Liouville). Nicht jede elementare Funktion hat eine
elementare Stammfunktion.
Problem:
Beweis–Referenz?
Beweis. Die Funktion e−x besitzt keine elementare Stammfunktion, wie be-
2
Leider können wir den Satz hier nicht nachweisen. Allerdings können wir
das folgende positive Resultat, zumindest in groben Zügen, herleiten:
y hat Polstellen bei ±1. Deren Partialbruchzerlegung ist dann eine Zerlegung
der Form:
1 A B
= + .
1 − x2 1−x 1+x
Dieser Ansatz liefert A(1 + x) + B(1 − x) = 1, d.h. A = B = 21 , also:
1 1 1 1 1
= · + · .
1 − x2 2 1−x 2 1+x
Auf unser ursprüngliches Problem angewendet erhalten wir:
∫
1 1( ) 1 1+x
dx = − ln |1 − x| + ln |1 + x| = ln .
1−x 2 2 2 1−x
Beweis (von Satz 13.26, nur Beweisidee). Wir gehen in drei Schritten vor:
Vorlesung vom:
1
Joseph Liouville (24. März 1809 in Saint-Omer – 8. September 1882 in Paris), 04. Februar 2008
französischer Mathematiker. Qualitätsstand:
erste Version
184 13 Integration
∫
2 ln(1 + x ),
falls n = 1,
1 2
x
dx =
(1 + x )
2(1−n) · (1+x2 )n−1 , falls n > 1.
2 n 1 1
weil die Integrale auf der rechten Seite induktiv bekannt sind, falls n ≥ 3.
Der Fall n = 2 ist dem Leser überlassen.
2. Wie im Beispiel berechnen wir eine Partialbruchzerlegung. Wir starten
g(x)
mit einer rationalen Funktion f (x) = h(x) . Division mit Rest liefert q(x)
und r(x), so dass:
g(x) r(x)
f (x) = = q(x) + .
h(x) h(x)
Den Nenner h(x) faktorisieren wir in k lineare Faktoren li (x) ∈ R[x] (d.h.
deg li (x) = 1) und l quadratische Faktoren q j (x) ∈ R[x] (d.h. deg q j (x) = 2),
wobei q j nicht mehr in Linearfaktoren zerlegbar sind:
∏
k ∏
l
h(x) = li (x)ei · q j (x) f j .
i=1 j=1
Dass eine solche Zerlegung über R immer existiert, können wir hier leider
Problem:
nicht beweisen.
Referenz! Beweis-
idee? Man kann nun zeigen, dass dann Konstanten aim , b jn , c jn ∈ R existieren,
so dass wir folgende Partialbruchzerlegung erhalten:
r(x) ∑ ∑ aim ∑ ∑ b jn x + c jn
ik e l fi
= + .
h(x) lm
i
qni
i=1 m=1 j=1 n=1
13.3 Elementare Funktionen 185
Aufgaben
Aufgabe 13.4 (Maximierung von Integralen). Bestimmen Sie den Wert bzw.
die Werte, an denen
∫ x2
H(x) = (9 − t2 ) · e−t dt
0
maximal wird.
186 13 Integration
Uneigentliche Integrale
Bisher haben wir Integrale nur dann ausgerechnet, wenn die Grenzen beide
endlich waren. Wir werden sehen, dass wir in einigen Fällen auch ∞ als
Grenze zulassen können und dass dies viele interessante Anwendungen hat,
beispielsweise auf die Konvergenz von Reihen.
Definition 14.1. Sei f : [a, ∞[→ R eine stetige Funktion. Dann setzen wir
∫ ∞ ∫ b
f (x) dx := lim f (x) dx,
a b→∞ a
falls der Grenzwert∫ existiert und nennen in diesem Fall f über [a, ∞[ uneigentlich
∞
integrierbar und a f (x) dx konvergent.
Beispiel 14.2. Wir betrachten die Funktion f (x) = x−s für s ∈ R. Der Grenz-
wert ∫ ∞ ( 1 b ) 1
x−s dx = lim x1−s 1 = lim (1 − b1−s )
1 b→∞ 1 − s b→∞ 1 − s
Beweis. Wegen der Monotonie von f erhalten wir für jedes k ∈ N offenbar
∫k
Schranken von oben und unten für 0 f (x) dx (siehe Abb. 14.1):
188 14 Uneigentliche Integrale
∑
k−1 ∫ k ∑
k
f (n) ≥ f (x) dx ≥ f (n).
n=0 0 n=1
Definition 14.5. Sei f : ]a, b] eine stetige Funktion auf einem halboffenen Intervall.
Dann schreiben wir ∫ b ∫ b
f (x) dx := lim f (x) dx,
a t↘a t
falls der Grenzwert existiert.
∫1
Beispiel 14.6. Das Integral 0 xα dx existiert, falls α < −1. Im Gegensatz dazu
∫1
existiert das Integral 0 x1 dx nicht, da: ln x −→ −∞.
x→0
Beispiel 14.8.
1. Es gilt: ∫
1 ∞ ( b) π
dx = lim arctan x a = .
−∞ 1 + x2 a→−∞, b→∞ 2
∫∞ ( )
2. Der Grenzwert −∞ e−x dx existiert, denn e−x ∈ O 1+x
2 2 1
2 . Man kann zeigen,
dass gilt: ∫ ∞
√
e−x dx = π.
2
−∞
Aufgaben
Wir werden nun erfahren, wie man mit Polynomen von höhrem Grad noch
bessere Approximationen erhalten kann.
Txn0 f hat offenbar den gleichen Wert und die gleichen ersten n Ableitungen in
x0 wie f .
192 15 Taylorpolynom und Taylorreihe
an und erhalten:
∫ n
(x − t)n (x − x0 )n+1
Rn+1 (x) = f (n+1)
(ξ) · dt = f (n+1) (ξ) .
x0 n! (n + 1)!
⊓
⊔
x3 x5 x2n+1
(T02n+1 sin)(x) = x − + − · · · + (−1)n ,
3! 5! (2n + 1)!
da
0, k gerade,
sin(k) (0) =
(−1) 2 , k ungerade.
k−1
∑
n+1 ∫ n+1
(n + 1) ln R ≤ ln ε + ln k ≤ ln ε + ln x dx.
k=1 1
Es folgt:
n+1
(n + 1) ln R ≤ ln ε + (x ln x − x) 1
ln ε 1
⇐⇒ ln R ≤ + ln(n + 1) − 1 +
n+1 n+1
1 n+1
⇐⇒ R ≤ (eε) n+1 · .
e
Abbildung 15.2 zeigt die Taylorpolynome des Sinus vom Grad 1, 3, 5, 7.
Beispiel 15.5. Wir betrachten die Funktion f (x) = (1 + x)α , etwa α = 12 . Es gilt:
Daher folgt:
194 15 Taylorpolynom und Taylorreihe
y
+2.5
+0.5
−5 -1 +1 +5 x
-0.5
-2.5
n ( )
∑ α
T0n f (x) = xk ,
k
k=1
Definition 15.6. Sei f : I → R eine ∞–oft diffbare Funktion und x0 ∈ I. Dann heißt
∑
∞
f (k) (x0 )
Tx0 f (x) = (x − x0 )k
k!
k=0
die Taylorreihe von f mit Entwicklungspunkt x0 . Die Taylorreihe Tx0 f ist eine
Potenzreihe in (x − x0 ).
Beispiel 15.7.
∑∞ xk
1. (T0 exp)(x) = k=0 k! ist die definierende Potenzreihe von exp.
2. Die Funktion f (x) = (1 + x)α hat die Taylorreihe
∞ ( )
∑ α
xk .
k
k=0
Antwort.
Wir zeigen: f ist ∞–oft diffbar und f (n) (0) = 0 ∀n. Insbesondere ist die Taylor-
reihe = 0 und konvergiert nicht gegen f .
Wir beweisen dazu mit Induktion nach n, dass
−1
pn ( 1x ) · e x2 , falls x , 0,
f (x) =
(n)
0, falls x = 0,
wobei pn ein Polynom ist. Der Induktionsanfang ist klar. Zunächst betrachten
wir den Fall x , 0:
( (1) 1 )′ ( ( 1 ))′ (1) 2
· e− x2 = pn · e− x2 + pn · 3 · e− x2 .
1 1
pn
x x x x
( ( 1 ) −1 (1) 2 )
· e− x2 .
1
= p′n · + pn ·
x x2 x x3
Dann ist
pn+1 (t) = −p′n (t) · t2 − 2pn (t) · t3 .
An der Stelle x = 0 gilt dann:
(1 (1) 1 )
f (n+1) (0) = lim pn · e− x2 = 0,
x→0 x x
da exp schneller wächst als jedes Polynom, wie wir in Beispiel 12.6 gesehen
haben.
Die folgende Aussage ist wegen Frage und Antwort 15.8 weniger trivial, als
es erscheinen könnte:
Beweis. Der Konvergenzradius der Reihe ist R = 1. Wir möchten das Quoti-
entenkriterium anwenden:
( α ) k+1
k+1 · x α−k
(α) k = · |x| −→ |x|.
k · x k+1 k→∞
Mit der Bemerkung 6.17 zum Quotientenkriterium zeigt dies, dass die Reihe
konvergiert, wenn |x| < 1 und diviergiert, wenn |x| > 1 ist.
196 15 Taylorpolynom und Taylorreihe
Wir zeigen:
∫ x ( )∫ x
1 α
Rn+1 (x) = (x − t)n f (n+1) (t) dt = (n + 1) (x − t)n (1 + t)α−n−1 dt
n! 0 n+1 0
konvergiert für |x| < 1 gegen 0. Nach dem Vorzeichen von x unterscheiden
wir zwei Fälle.
Erster Fall 0 ≤ x < 1: Sei C = max(1, (1 + x)α ). Dann gilt für 0 ≤ t ≤ x
0 ≤ (1 + t)α−n+1 ≤ (1 + t)α ≤ C.
Also
) ∫ |x|(
α
|Rn+1 (x)| = (n + 1) · | | |(x + t)n (1 − t)α−n−1 |dt
n+1 0
( ) ∫ x ( )
α α
≤ (n + 1) · | |·C (x − t) dt = C · |
n
|xn+1 .
n+1 0 n+1
∑∞ (α) ( α ) n+1
Da n=0 n xn konvergiert, bekommen wir | n+1 |x −→ 0 für n → ∞.
Der zweite Fall, −1 < x < 0, ist schwieriger, weil die Funktion (1 + x)α oder
eine ihrer Ableitungen eine Polstelle bei x = −1 haben kann.
( )∫ x
α
|Rn+1 (x)| = (n + 1) · | | |(x − t)n (1 − t)α−n−1 |dt
n+1 0
( ) ∫ |x|
α ( |x| − t )n
≤ (n + 1) · | | (1 − t)α−1 dt.
n+1 0 1−t
|x|−t
Die Funktion t 7→ 1−t ist monoton fallend in [0, |x|], da die Ableitung negative
ist
(1 − t)(−1) − (−1)(|x| − t) |x| − 1
= < 0.
(1 − t)2 (1 − t)2
Also gilt
( |x| − t )n
≤ |x|n für 0 ≤ t ≤ |x|.
1−t
∫ |x|
Mit C = |α| 0
(1 − t)α−1 dt erhalten wir
( ) ∫ |x| ( )
α−1 α−1
|Rn+1 (x)| ≤ |α | · |x|n (1 − t)α−1 dt ≤ C · | | · |x|n ,
n 0 n
Aufgaben
im Entwicklungspunkt x0 = 0.
Zeigen Sie mit Hilfe von Partialbruchzerlegung, dass die Taylorreihe auf dem
offenen Intervall (−1, 1) gegen f konvergiert.
1. f (x) = tan x
√
2. f (x) = 1 + x
und plotten Sie jeweils die Graphen von f und der Taylorpolynome.
16
Vorlesung vom:
Sei
∑
∞ 11. Februar 2008
f (x) = an xn Qualitätsstand:
n=0 erste Version
eine Potenzreihe mit Konvergenzradius R > 0. Wir wollen zeigen, dass f in
] − R, R[ ∞–mal diffbar ist und dass die Potenzreihe mit der Taylorreihe von
f in x0 = 0 übereinstimmt. Allein die Stetigkeit ist hierbei nicht offensichtlich.
Definition 16.1. Sei fn : I → R eine Folge von Funktionen auf einem Intervall. Die
Folge ( fn ) heißt konvergent (genauer: punktweise konvergent), wenn für jedes x
die Folge ( fn (x)) konvergiert und dann ist die Grenzfunktion
Frage 16.2. Wenn alle fn stetig sind, ist dann auch lim fn stetig?
Antwort. Nein, nicht unbedingt. Dazu betrachten wir das Beispiel fn : [0, 1] →
R, fn (x) = xn . Dann existiert f = lim fn , aber
0, x ∈ [0, 1[,
f (x) =
1, x = 1.
Definition 16.3. Sei ( fn : I → R)n∈N eine Folge von Funktionen auf einem Intervall
I. ( fn ) konvergiert gleichmäßig gegen eine Grenzfunktion f : I → R, wenn:
∀ε > 0 ∃ n0 : | fn (x) − f (x)| < ε ∀n ≥ n0 ∀ x ∈ I.
weise). Aber:
∫ 1 ∫ 1
lim fn (x) dx = 1 , 0 = lim fn (x) dx.
n→∞ 0 0 n→∞
16.1 Gleichmäßige Konvergenz 201
Satz 16.6. Sei fn : [a, b] → R eine Folge stetiger Funktionen auf einem abgeschlos-
senen Intervall, die gleichmäßig gegen f : [a, b] → R konvergiert. Dann gilt:
∫ b ∫ b
f (x) dx = lim fn (x) dx.
a n→∞ a
Beweis. Zunächst einmal ist f ebenfalls stetig und deshalb integrierbar. Fer-
ner: ∫ b ∫ b ∫ b
f (x) dx − fn (x) dx ≤ f (x) − fn (x) dx ≤ ε(b − a),
a a a
falls n so groß ist, dass | f (x) − fn (x)| < ε ∀x ∈ [a, b]. Die Behauptung folgt. ⊔
⊓
Korollar 16.8. Sei fn : [a, b] → R eine Folge von stetig diffbaren Funktionen, die
punktweise gegen f : [a, b] → R konvergiert. Konvergiert die Folge der Ableitungen
( fn′ ) gleichmäßig, dann ist f diffbar und es gilt:
f ′ = lim fn′ .
n→∞
∗
Beweis. Sei f = lim fn′ . Nach dem Satz 16.4 ist f ∗ auf [a, b] stetig. Ferner gilt:
∫ x
fn (x) = fn (a) + fn′ (t) dt
a
für x ∈ [a, b]. Mit Satz 16.6 folgt:
∫ x
f (x) = f (a) + f ∗ (t) dt.
a
Der Hauptsatz der Differential– und Integralrechnung liefert nun, dass f
diffbar ist und dass f ′ = f ∗ . ⊓
⊔
202 16 Konvergenz von Funktionenfolgen
die wir durch gliedweise Differentiation bzw. Integration erhalten, den gleichen
Konvergenzradius und konvergieren auf ] − R, R[ gegen
1. f ′ (x),
∫x
2. 0 f (x) dx.
n→∞ n→∞
also:
1
R= √ .
|an |
n
lim supn→∞
Da √ 1 ln n
n = lim n n = lim e n = e0 = 1,
n
lim
n→∞ n→∞ n→∞
∑ ∑
haben ∞ n=1 nan x
n−1
und ∞ xn+1
n=0 an n+1 den gleichen Radius. Die Folge der Par-
tialsummen von f und f ′ konvergieren auf jedem echten Teilintervall [−r, r]
für r < R gleichmäßig. Die Behauptung folgt daher auf [−r, r] aus Satz 16.6
und Korollar 16.8. ⊓ ⊔
Beispiel 16.10.
1 ∑ ∞
f (x) = = (−1)n xn .
1+x
k=0
1 ∑ ∞
= f (x) = (−1)n x2n .
1 + x2 n=0
3. Es gilt:
∑
∞ ∑
∞
nxn = x· nxn−1 .
n=0 n=1
Es folgt:
∑
∞ ( 1 )′ x
nxn = x· = für |x| < 1,
n=0
1−x (1 − x)2
also zum Beispiel:
∑∞ ( 1 )n 1
2
n = = 2.
n=1
2 (1 − 1 2
2)
In den Beispielen 1. und 2. konvergiert die Reihe auch für x = 1. Dies legt die
Vorlesung vom:
Formeln
13. Februar 2008
∑
∞
1 Qualitätsstand:
(−1)n = ln(1 + 1) = ln 2, erste Version
n=0
n+1
∑
∞
1 π
(−1)n = arctan(1) =
n=0
2n + 1 4
(da tan π4 = 1) zumindest nahe. Dass dies wirklich der Fall ist, zeigt das
folgende Resultat:
∑
Satz 16.11 (Abelscher Grenzwertsatz). ∑ Sei ∞ n=0 an eine konvergent Reihe reeller
∞
Zahlen. Dann hat die Potenzreihe f (x) = n=0 an xn den Konvergenzradius R ≥ 1
und für die Grenzfunktion f : ] − 1, 1[→ R gilt:
∑
∞
lim f (x) = an .
x→1
n=0
∑
∞
(−1)n−1 1 1 1
ln(2) = =1− + − + ··· .
n 2 3 4
n=1
∑
2. Wir betrachten ∞ n x2n+1
n=0 (−1) · 2n+1 = arctan x für x ∈ ] − 1, 1[. Für x = 1 liegt
ebenfalls Konvergenz vor, also:
∑
∞
1 π
(−1)n · = arctan 1 = .
n=0
2n + 1 4
Aufgaben
Aufgabe 16.1 (. . . ). . . .
Problem:
Aufgaben zur Kon-
vergenz von Fkt.-
Folgen fehlen noch!
Teil III
Lineare Algebra
207
Einführung
In der linearen Algebra werden Probleme und Phänomene untersucht, die mit
Hilfe linearer Gleichungssysteme ausdrückbar sind. Insbesondere werden
dabei auch Verfahren studiert, um explizit Lösungen für solche Probleme
auszurechnen. Oft sind sowohl die Probleme und Lösungen als auch die
Phänomene sehr anschaulich zu verstehen, wenn man deren geometrische
Seite betont. Wir werden versuchen, dies in dieser Vorlesung möglichst oft
zu realisiseren.
Anwendungen der linearen Algebra finden sich neben der Geometrie in
vielen Bereichen der Mathematik und Informatik, aber auch des alltäglichen
Lebens. Wir werden solche Anwendungen so oft wie möglich ansprechen,
insbesondere, wenn sie die Informatik betreffen.
Um den Anschauungs– und Anwendungsbezug möglichst naheliegend zu
halten, beginnen wir mit der linearen Algebra über den reellen Zahlen und
deren Geometrie. Es wird sich im Verlauf der Vorlesung allerdings heraus-
stellen, dass es oft sinnvoll ist, davon abzuweichen und lineare Algebra auch
über anderen Zahlensystemen zu betreiben. Beispielsweise wäre das ganze
Gebiet der Kodierungstheorie kaum denkbar ohne die lineare Algebra über
endlichen Körpern. Andererseits wäre die Darstellung der Theorie viel zu
kompliziert, ohne die Ausweitung der Zahlen auf die sogenannten komple-
xen Zahlen zu betrachten.
17
Vorlesung vom:
Die zum Teil aus der Schule bekannte Geometrie im Anschauungsraum R3 18. April 2012
stellen wir vor und erfahren dabei, dass die Erweiterung auf den Rn in den Qualitätsstand:
meisten Fällen abstrakt gesehen gar keine Änderung benötigt. zweite Version
17.1 Punkte im Rn
a2
a1
a3
und einer Zahl λ ∈ R (genannt Skalar) setzen wir (siehe Abb. 17.2):
x1 + y1 λx1
..
x + y := .
,
λ·x := ... .
xn + yn λxn
Abbildung 17.2. Summe zweier Vektoren (a, b), (c, d) ∈ R2 sowie Multiplikation eines
Vektors (a, b) ∈ R2 mit dem Skalar 2 ∈ R.
17.2 Skalarprodukt, Euklidische Norm 211
Mit Hilfe des sogenannten Skalarprodukts werden wir nun Abstände und
Winkel einführen und erste Eigenschaften der neuen Begriffe herleiten.
d(x, y) := ∥x − y∥
(5)
Zu 6. ∥x + y∥2 + ∥x − y∥2 = ∥x∥2 + 2⟨x, y⟩ + ∥y∥2 + ∥x∥2 + 2⟨x, −y⟩ + ∥ − y∥2
(2&3)
= ∥x∥2 + 2⟨x, y⟩ + ∥y∥2 + ∥x∥2 − 2⟨x, y⟩ + ∥y∥2 , wie behauptet.
⊓
⊔
Nun kommen wir zu einer weiteren, sehr häufig verwendeten, aber nicht
ganz so leicht nachzuweisenden Eigenschaft:
Ferner gilt für x , 0 die Gleichheit |⟨x, y⟩| = ∥x∥ · ∥y∥ genau dann, wenn y = λx für
ein λ ∈ R.
Da µ > 0, folgt:
Die folgenden Eigenschaften der oben eingeführten Norm sind wieder leicht
einzusehen:
∥x + y∥2 = ⟨x + y, x + y⟩
= ∥x∥2 + 2⟨x, y⟩ + ∥y∥2 .
Die Behauptung folgt mit der Monotonie der Quadratwurzel (Bem. 5.30). ⊓
⊔
Vorlesung vom:
Wir kommen nun zu der geometrischen Bedeutung des Skalarprodukts: 25. April 2012
Qualitätsstand:
Definition 17.6. Zwei Vektoren x, y ∈ Rn heißen senkrecht (auch orthogonal) zweite Version
zueinander (in Zeichen x ⊥ y), wenn ⟨x, y⟩ = 0.
Bemerkung 17.7.
zusammen mit dem geometrischen Satz des Pythagoras a2 +b2 = c2 für die
Seitenlängen a, b, c in einem rechtwinkligen Dreieck, wobei c die längste
ist.
Für die Seitenlängen der beiden in Abb. 17.3 erkennbaren rechtwinkligen
Dreiecke gilt dann nämlich:
d y
a x
x+y
Abbildung 17.3. Anwendung des geometrischen Satzes des Pythagoras auf zwei
rechtwinklige Dreiecke.
214 17 Der R3 und der Rn
b
a a2
c
=
b2
Abbildung 17.4. Dies zeigt: c2 = a2 + b2 , da die vier Dreiecke gleich groß sind.
auf der Tatsache, dass in einem Dreieck die Winkelsumme 180◦ ist, was
wiederum aus dem Parallelenaxiom folgt (siehe Abb. 17.5). Dieses besagt:
In einer Ebene α gibt es zu jeder Geraden g und jedem Punkt S außerhalb
von g genau eine Gerade, die zu g parallel ist und durch den Punkt S
geht. Ob das Parallelenaxiom in der Wirklichkeit gilt (nicht im R3 ), ist
offen und Gegenstand der Astronomie. An dieser Stelle möchten wir auf
zwei Bücher von Roger Penrose hinweisen: [Pena] und [Penb].
180◦
α′ γ β′
α β
Definition 17.8. Für zwei Vektoren x, y ∈ Rn definieren wir den Winkel θ zwi-
schen x und y durch die Formel:
⟨x, y⟩
cos θ = .
∥x∥ · ∥y∥
festgelegt, wenn man sich auf ein geeignetes Intervall für θ beschränkt, hier
etwa auf das Intervall [0, 2π[. 2π ist die Länge des Vollkreises mit Radius 1;
viele Eigenschaften von Cosinus und Sinus sowie Zusammenhänge zwischen
diesen können recht leicht am Einheitskreis erklärt werden (s. Abb. 17.6).
1
sin θ
θ
−1 | {z }
1
cos θ=cos(−θ)
2π − θ sin(−θ)
−1
L = {p + λv | λ ∈ R} =: p + R · v,
wobei p ∈ L ein beliebiger Aufpunkt und v ∈ Rn \ {0} ein Richtungsvektor ist (s.
Abb. 17.7).
Eine Hyperebene H ⊆ Rn ist eine Teilmenge der Gestalt
H = {x ∈ Rn | a1 x1 + · · · + an xn = b} = {x ∈ Rn | ⟨a, x⟩ = b},
p v
17.3.2 Schnittpunkte
Proposition 17.10. 2. oder 3. liegt genau dann vor, wenn der Richtungsvektor von
L senkrecht zum Normalenvektor a von H ist.
b − ⟨a, p⟩ b − ⟨a, p⟩
λ= , also L ∩ H ∋ q = p + v.
⟨a, v⟩ ⟨a, v⟩
Ist ⟨a, v⟩ = 0, also a ⊥ v, dann hat (*) nur dann eine Lösung, wenn b − ⟨a, p⟩ =
0 ⇔ p ∈ H ⇒ L ⊆ H, da dann λ ∈ R beliebig gewählt werden kann. Dies
entspricht dem 3. Fall.
Ist ⟨a, v⟩ = 0 und b , ⟨a, p⟩ dann L ∩ H = ∅, 2. Fall. ⊓
⊔
Definition 17.11. In den Fällen 2. und 3., d.h. wenn a ⊥ v, so sagen wir: L ist eine
zu H parallele Gerade.
17.3.3 Abstände
p v
uq
L
⟨q − p, v⟩
λ= ,
⟨v, v⟩
da ∥v∥2 , 0. Also:
⟨q − p, v⟩ ⟨ v ⟩ v
uq = p + · v = p + q − p, · .
⟨v, v⟩ ∥v∥ ∥v∥
Jeder andere Punkt u ∈ L hat einen größeren Abstand (s. Abb. 17.10), da
Pythagoras
∥u − q∥2 = ∥uq − q∥2 + ∥u − uq ∥2 ≥ ∥uq − q∥2 , also:
⊓
⊔
u
uq
L
Abbildung 17.10. Der Abstand des Punktes q von der Geraden L ist d(L, q) = ∥uq − q∥.
Das Minimum d(H, q) wird in genau einem Punkt uq ∈ H angenommen. uq ist durch
die Bedingung, dass die Differenz uq − q ein skalares Vielfaches des Normalenvektors
a ist, eindeutig bestimmt. Die Abbildung
Rn → H, q → uq
uq
a
Abbildung 17.11. Die Orthogonale Projektion des Punktes q auf die Hyperebene H.
b − ⟨a, q⟩
uq = q + · a.
⟨a, a⟩
Der Abstand ist somit:
b − ⟨a, q⟩ |b − ⟨a, q⟩| b ⟨ a ⟩
d(H, q) = ·a = · ∥a∥ = − ,q .
⟨a, a⟩ ⟨a, a⟩ ∥a∥ ∥a∥
Wählen wir den Normalenvektor normiert, d.h. von der Länge 1, dann gilt:
In diesem Fall lässt sich |b| als Abstand d(H, 0) von H zum Nullpunkt inter-
pretieren. Auch das Vorzeichen von b hat eine Interpretation:
⊓
⊔
L1
L2
x̃
ỹ
Beweis. (x̃, ỹ) erfülle die Bedingung. Für jedes andere Paar (x, y) ∈ L1 × L2 gilt:
∥x − y∥2 = ∥x̃ + λ1 v1 − ỹ − λ2 v2 ∥2
= ∥x̃ − ỹ + λ1 v1 − λ2 v2 ∥2
= ∥x̃ − ỹ∥2 + ∥λ1 v1 − λ2 v2 ∥2
Insgesamt folgt: ∥x − y∥2 ≥ ∥x̃ − ỹ∥2 (also auch d(x, y) ≥ d(x̃, ỹ)) und Gleichheit
gilt genau dann, wenn
λ1 v1 − λ2 v2 = 0 ⇔ λ1 = λ2 = 0,
also:
⟨p1 − p2 + λ1 v1 − λ2 v2 , v1 ⟩ = 0, ⟨p1 − p2 + λ1 v1 − λ2 v2 , v2 ⟩ = 0.
Dies liefert ein lineares Gleichungssystem (d.h. eine Menge von Bedingun-
gen an λ1 , λ2 , die jeweils ein Polynom vom Grad 1 in den λi darstellen) für
λ1 und λ2 :
λ1 ·∥v1 ∥2 − λ2 ⟨v2 , v1 ⟩ = ⟨p2 − p1 , v1 ⟩, λ1 ·⟨v1 , v2 ⟩ − λ2 ∥v2 ∥2 = ⟨p2 − p1 , v2 ⟩.
Wir könnten dies nun explizit lösen. Wir machen das hier aber nicht, weil
wir in Kürze eine Maschinerie zur Lösung solcher Probleme kennen lernen
werden, mit Hilfe der sogenannten Matrixschreibweise:
( )( ) ( )
∥v1 ∥2 −⟨v2 , v1 ⟩ λ1 ⟨p2 − p1 , v1 ⟩
= .
⟨v1 , v2 ⟩ −∥v2 ∥2 λ2 ⟨p2 − p1 , v2 ⟩
Wir werden sehen, dass diese Gleichung genau dann eine eindeutig bestimm-
te Lösung (λ1 , λ2 )t ∈ R2 hat, wenn
( )
∥v1 ∥2 −⟨v2 , v1 ⟩
0 , det := −∥v1 ∥2 · ∥v2 ∥2 + ⟨v1 , v2 ⟩2 ≤ 0,
⟨v1 , v2 ⟩ −∥v2 ∥2
wobei det() die sogenannte Determinante beschreibt, die wir gleich allgemein
einführen werden. Nach der Cauchy–Schwarz’schen Ungleichung ist aber
|⟨v1 , v2 ⟩| ≤ ∥v1 ∥ · ||v2 ∥ und es gilt <, da v1 und v2 nicht skalare Vielfache
voneinander sind. ⊓ ⊔
Aufgaben
S
P
A
D
R
18
Abstrakte Vektorräume
18.1 Definitionen
Definition 18.1. Ein Körper ist ein Tupel (K, +, ·) aus einer Menge K und zwei
Abbildungen
+ : K × K → K, (a, b) → a + b
· : K × K → K, (a, b) → a · b,
(a + b) + c = a + (b + c) ∀ a, b, c ∈ K.
∃ 0 ∈ K, so dass 0 + a = a ∀ a ∈ K.
224 18 Abstrakte Vektorräume
Definition 18.3. Lassen wir in der Definition des Körpers das Axiom K2.3 weg, so
erhalten wir die Axiome eines kommutativen Rings mit 1.
Beispiel/Definition 18.4. Für a ∈ Z bezeichnen wir mit a den Rest bei der
Division durch p ∈ Z. Sei p eine Primzahl. Dann ist
Fp := {0, 1, . . . , p − 1}
= die Menge der Reste bei der Division durch p in Z
ein Körper (mit p Elementen) vermöge der folgenden Verknüpfungen:
a + b := a + b, a · b := a · b.
Häufig läßt man ¯ weg und schreibt die Elemente als 0, 1, . . . . Für Details s.
Kapitel 3.
18.1 Definitionen 225
+ 0̄ 1̄ · 0̄ 1̄
0̄ 0̄ 1̄ 0̄ 0̄ 0̄
1̄ 1̄ 0̄ 1 0̄ 1
+ 0̄ 1̄ 2̄ · 0̄ 1̄ 2̄
0̄ 0̄ 1̄ 2̄ 0̄ 0̄ 0̄ 0̄
1̄ 1̄ 2̄ 0̄ 1̄ 0̄ 1̄ 2̄
2̄ 2̄ 0̄ 1̄ 2̄ 0̄ 2̄ 1̄
Bemerkung 18.6. Ist n eine zusammengesetzte Zahl, etwa eine echte Prim-
zahlpotenz, dann ist Z/n := {0, 1, . . . , n − 1} kein Körper, sondern lediglich ein
kommutativer Ring mit 1.
Beispielsweise hat 2 in Z/6 kein Inverses bzgl. der Multiplikation: Es gibt
kein x ∈ F6 , so dass x · 2 ≡ 1 mod 6, da:
Definition 18.8. Sei K (genauer (K, +, ·)) ein Körper. Ein K-Vektorraum (kurz K–
VR) ist ein Tupel (V, +, ·), wobei V eine Menge ist, zusammen mit zwei Abbildungen
+ : V × V → V, (v, w) → v + w
· : K × V → V, (λ, v) → λ · v,
(λ + µ) · v = λ · v + µ · v ∀ λ, µ ∈ K, ∀ v ∈ V,
λ · (v + w) = λ · v + λ · w ∀ λ ∈ K ∀ v, w ∈ V.
Bemerkung/Definition 18.9. Verlangen wir nicht mehr, dass K ein Körper ist,
sondern nur, dass R = K ein (kommutativer) Ring mit 1 ist, so erhalten die
Definition eines (Links-)Moduls über R.
Die Theorie der Module ist deutlich verschieden von der Theorie der Vektor-
räume.
1
Achtung: Mit 0 bezeichnen wir sowohl die Zahl 0 ∈ K, also auch den Null-Vektor
0 = (0, . . . , 0)t , als auch den Nullvektorraum {(0, . . . , 0)t }. Es wird immer aus dem
Kontext verständlich sein, welche 0 gemeint ist.
18.2 Beispiele von Vektorräumen 227
p + q = x3 + 5x2 − 2x − 1 ∈ R[x],
1 5 3
· p = x2 − x ∈ R[x].
2 2 2
Außerdem ist beispielsweise (x − 1)2 + 2(x + 1) ∈ R[x].
3. Die Mengen (siehe für die Definitionen Kapitel 9)
KM := { f : M → K}
ein K-Vektorraum.
5. In der Kodierungstheorie verwendet man häufig Vektorräume über end-
lichen Körpern, etwa K = F2 :
x
..
1
V = F2 =
n
.
x ∈ {0, 1}
,
i
xn
die Menge der n–Tupel von Elementen aus F2 . Allgemein definiert man
für einen endlichen Körper K = Fp und zwei Vektoren
x1 y1
.
x = .. , y = ... ∈ Fnp
xn yn
die Hammingdistanz:
Beispielsweise ist
( 0 0 )
d 1 , 0 = 2.
0 1
228 18 Abstrakte Vektorräume
In der Kodierungstheorie ist ein Code eine Teilmenge C ⊆ Fnp . Ein Element
x ∈ C heißt ein Codewort. Die Minimaldistanz von C ist
Rauscht der Kanal so wenig, dass man weniger D2 Fehler erwarten darf,
dann können wir das Wort x aus dem übertragenen Wort y zurückbe-
kommen, indem wir
18.3 Untervektorräume
Definition 18.10. Sei V ein K-Vektorraum. Eine nicht leere Teilmenge U ⊆ V heißt
Untervektorraum (kurz UVR), wenn
1. u1 , u2 ∈ U ⇒ u1 + u2 ∈ U,
2. u ∈ U, λ ∈ K ⇒ λ · u ∈ U.
1. + : U × U → V, (u1 , u2 ) 7→ u1 + u2 ∈ U,
2. · : k × U → V, (k, u) 7→ k · u ∈ U.
Frage 18.13. Welche der folgenden Teilmengen des R2 sind Untervektorräume (s.
Abb. 18.1 und 18.2)?
18.3 Untervektorräume 229
{( ) }
x1
U1 = ∈ R2 x1 + 2x2 = 0 ,
x2
{( ) }
x1
U2 = x2 ≥ 0 ,
x2
{( ) }
x1
U3 = x1 + x2 ≤ 1 ,
x2
{( ) }
x1
U4 = x1 + x2 = 1 .
x2
U4 ist kein Untervektorraum, weil z.B. ( 21 , 12 )t ∈ U4 , aber 2·( 12 , 12 )t = (1, 1)t < U4
und weil 0 < U4 . ⊓⊔
⊔
⊓
v = λ1 v1 + λ2 v2 + · · · + λn vn ∈ V,
wobei λ1 , . . . , λn ∈ K. Mit
18.4 Lineare Unabhängigkeit und Basen 231
0 = λ1 v 1 + λ2 v 2 + · · · + λn v n ⇒ λ1 = · · · = λn = 0.
λ1 + λ1 − λ1 = λ1 = 0 ⇒ λ2 = 0 ⇒ λ3 = 0.
Abbildung 18.3. Ist die Summe dreier Vektoren der Nullvektor, so bedeutet dies, dass
sie aneinander gehängt einen geschlossenen Vektorzug ergeben.
b1 1 1 1 λ1 + λ2 + λ3
b 1 0 1 λ + λ
2 = λ1 + λ2 + λ3 = 1 3
b3 0 1 1 λ2 + λ3
liefert nämlich ein Gleichungssystem,
(I) b1 = λ1 + λ2 + λ3
(II) b2 = λ1 + λ3
(III) b3 = λ2 + λ3 ,
welches eine Lösung hat:
I - II - III ergibt: b1 − b2 − b3 = −λ3 ⇒ λ3 = b2 + b3 − b1 .
Dies in II eingesetzt liefert: b2 = λ1 + b2 + b3 − b1 ⇒ λ1 = b1 − b3 .
Dies wiederum in III eingesetzt: b3 = λ2 + b2 + b3 − b1 ⇒ λ2 = b1 − b2 .
Also:
λ1 b1 − b3
λ b − b
2 = 1 2 .
λ3 −b1 + b2 + b3
Probe: 3
p1 = x2 + 1, p2 = x2 − 1, p3 = x3 + 1, p4 = x3 − 1 ∈ R[x]≤3
⟨x2 + 1, x2 − 1, x3 + 1, x3 − 1⟩ ⊆ {p = a3 x3 + a2 x2 + a1 x + a0 | a1 = 0}.
mit nur einer 1 an der i-ten Position und sonst 0-en, bilden eine Basis des
Rn , die sogenannte Standardbasis.
2. R[x]≤3 hat die Basis a, x, x2 , x3 , a , 0. Es gibt aber auch andere Basen. Bei-
spielsweise ist 1, x − a, (x − a)2 , (x − a)3 mit a , 0 auch eine Basis von R[x]≤3 .
Dies ist die Basis, welche für das dritte Taylorpolynom Ta3 f verwendet
wird (siehe Kapitel 15).
234 18 Abstrakte Vektorräume
Bemerkung 18.21. Ist {v1 , . . . , vn } ⊆ V eine Basis, dann hat jeder Vektor w ∈ V
eine eindeutig bestimme Darstellung
w = λ1 v1 + · · · + λn vn mit λi ∈ K
als Linearkombination.
Beweis. Existenz ist die erste Bedingung, Eindeutigkeit die zweite: die Dif-
ferenz zweier Darstellungen ist nämlich eine Relation, die nach der zweiten
Bedingung trivial ist.
Ausführlicher: Sei w ∈ V. Da eine Basis ein Erzeugendensystem ist, gibt es
λi ∈ K, so dass
w = λ1 v1 + · · · + λn vn .
′ ′
Ist w = λ1 v1 + · · · + λn vn eine weitere Darstellung, so gilt für die Differenz:
′ ′
0 = (λ1 − λ1 )v1 + · · · + (λn − λn )vn .
′ ′
Wegen der Definition einer Basis, folgt: λ1 − λ1 = 0, . . . , λn − λn = 0. Damit
′ ′
gilt aber schon: λ1 = λ1 , . . . , λn = λn . Dies zeigt die Eindeutigkeit. ⊓
⊔
Vorlesung vom:
4. Mai 2012
Satz 18.22. Sei V ein K–VR und seien v1 , . . . , vn ∈ V Vektoren. Äquivalent sind:
Qualitätsstand:
zweite Version
1. {v1 , . . . , vn } ist eine Basis von V.
2. {v1 , . . . , vn } bilden ein unverlängerbares System von linear unabhängigen Vek-
toren.
3. {v1 , . . . , vn } bilden ein unverkürzbares Erzeugendensystem von V.
4. Jeder Vektor w ∈ V hat genau eine Darstellung w = λ1 v1 + · · · + λn vn mit
λi ∈ K als Linearkombination von v1 , . . . , vn .
∃ λ1 , . . . , λn , λn+1 ∈ K : λ1 v1 + · · · + λn vn + λn+1 w = 0,
λ1 −λn
w = (− )v1 + · · · + (− ) · vn .
λn+1 λn+1
Dies gilt für beliebige w ∈ V, d.h. v1 , . . . , vn erzeugen V. v1 , . . . , vn ist unver-
kürzbar, das heißt nach Weglassen eines der Vektoren haben wir kein Erzeu-
gendensystem mehr. Wenn wir zum Beispiel vn weglassen und v1 , . . . , vn−1
noch ein Erzeugendensystem wäre, gäbe es eine Darstellung
vn = µ1 v1 + . . . mun+1 vn+1 ,
λ1 v1 + . . . λn vn = 0
Beispiel 18.23. Das Erzeugendensystem v1 = (1, 0), v2 = (0, 1), v3 = (1, 1) von
Vektoren des R2 ist verkürzbar. Wir können sogar jeden beliebigen der drei
Vektoren weglassen und erhalten immer noch ein System, das ganz R2 er-
zeugt: ⟨v1 , v2 ⟩ = ⟨v1 , v3 ⟩ = ⟨v2 , v3 ⟩ = R2 .
Bei w1 = (1, 0), w2 = (0, 1), w3 = (0, 2) können wir allerdings w1 nicht weglas-
sen, da w2 und w3 nur die y-Achse erzeugen:
⟨w2 , w3 ⟩ = {(a, b) ∈ R2 | a = 0} ⊊ R2 .
18.5 Dimension
Da wir nun wissen, was eine Basis eines K–Vektorraumes ist, können wir nun
endlich dessen Dimension definieren:
Definition 18.24. Sei V ein K-Vektorraum. Dann definieren wir die Dimension
von V durch
{
n, falls V eine Basis v1 , . . . , vn aus n Vektoren hat ,
dim V := dimk V =
∞, sonst.
236 18 Abstrakte Vektorräume
Der zweite Fall dim V = ∞ tritt genau dann ein, wenn V kein endliches
Erzeugendensystem hat.
Bemerkung 18.26. Es ist nicht klar, dass die obige Definition der Dimension
eine vernünftige ist. Unklar ist bislang, ob je zwei Basen von V gleich viele
Elemente haben. Also müssen wir zeigen, dass die Dimension wohldefiniert
ist, d.h. unabhängig von der Wahl der Basis. Dies zu zeigen ist unser nächstes
Ziel.
w = λ1 v 1 + · · · + λn v n
1 ( −λ2 ) ( −λn )
v1 = w+ v2 + · · · + vn ,
λ1 λ1 λ1
da 1
λ1 ∈ K existiert.
Sei u ∈ V ein beliebiger Vektor. Dann existieren µ1 , . . . , µn ∈ k, so dass
u = µ1 v1 + · · · + µn vn ,
0 = µ1 w + µ2 v2 + · · · + µn vn , µi ∈ K.
µ1 λ1 = 0, µ2 + µ1 λ2 = 0, ..., µn + µ1 λn = 0 ∈ K.
1
λ1 ≤ 0 ⇒ µ1 = µ1 λ1 = 0.
λ1
Einsetzen liefert: µ2 = · · · = µn = 0. ⊓
⊔
w1 , . . . , wn−1 , vn , . . . , vr
eine Basis ist, denn auch die Familie w1 , . . . , wn−1 ist linear unabhängig. wn
hat eine Darstellung
Beweis. Nach dem vorigen Korollar ist n ≤ r. Ist n < r, so gibt es, ebenfalls
wegen des Korollars, einen Vektor w ∈ V \ ⟨v1 , . . . , vn ⟩. Induktiv können wir
dies fortführen, bis wir schließlich eine Basis erhalten. ⊓ ⊔
Aufgaben
1. V1 := R5 , U1 := {p ∈ R5 | ||p|| = 1}.
2. V2 := R4 , U2 := {(x, y, z, w) ∈ R4 | x + y + z + w = 0, w = 0}.
{ }
3. V3 := R3 , U3 := p ∈ R3 | ⟨p, (1, 2, 3)t ⟩ = 0 .
4. V4 := R4 , U4 := {(x, y, z, w) ∈ R4 | (x + y) · (x − y) = 0}.
5. V5 := R[x]≤3 = {ax3 + bx2 + cx + d | a, b, c, d ∈ R}, U5 := {p ∈ R[x]≤3 | b + d =
0, a + c = 0}.
Parity Check Ist ein Daten-Wort w = (w1 , w2 , . . . , w19 ) ∈ (F2 )19 gegeben, so
setzen wir:
(v1 , v2 , . . . , v19 , v20 ) := (w1 , w2 , . . . , w19 , p) ∈ (F2 )20 , wobei p die Parität des
Wortes w ist, d.h.:
{
0, falls w1 + w2 + · · · + w19 ≡ 0 mod 2,
p=
1, falls w1 + w2 + · · · + w19 ≡ 1 mod 2.
Wir nehmen an, dass bei der Übermittlung eines Wortes v ∈ (F2 )20 höchs-
tens ein Buchstabe fehlerhaft beim Empfänger ankommt. Zeigen Sie, dass
240 18 Abstrakte Vektorräume
V := ⟨v1 , v2 , v3 ⟩ ⊂ R4 .
x1 + 2x2 − 5x3 = 1
2x1 + 3x2 − 7x3 = 3
3x1 + 4x2 − 8x3 = 13
(systematisch) lösen.
Idee: Da der Koeffizient von x1 in der ersten Gleichung , 0, können wir
diese Gleichung verwenden, um x1 aus den beiden anderen Gleichungen zu
entfernen.
x1 + 2x2 − 5x3 = 1
−x2 + 3x3 = 1
−2x2 + 7x3 = 10
x1 + 2x2 − 5x3 = 1,
−x2 + 3x3 = 1,
x3 = 8,
x1 + 2 · 23 − 5 · 8 = 1 ⇒ x1 = −5.
Definition 19.3. 1. Sei K ein Körper. Eine m × n Matrix mit Einträgen in K ist
eine Tabelle
a11 a12 . . . a1n
a a . . . a
21 22 2n
A = . . . ∈ Km×n
.. .. . . ...
am1 am2 . . . amn
von Körperelementen aij ∈ K. m ist die Anzahl der Zeilen und n die Anzahl der
Spalten von A. Wir schreiben auch
C = A · B = (cik ) ∈ Km×r
∑
n
durch die Formel cik = ai j b jk erklärt.
j=1
( ) ( )
1 1
235 −1 2 4 23
Beispiel 19.4. A = , B = . Also, A · B = ∈ R2×2 (1 · 1 + 2 ·
146 3 27
13
4 + 3 · 6 = 27). In diesem speziellen Fall ist auch das Produkt B · A erklärt, da
(zufälligerweise) m = 2 = r:
1 1 ( 2 3 5 ) 3 7 11
−1 2 0 5 7
B · A = = ∈ R3×3 .
146
13 5 15 23
Insbesondere ist A · B , B · A.
19.2 Der Gaußalgorithmus zum Lösen linearer Gleichungssysteme 243
Spaltenvektoren wie
x1
x = ... ∈ Kn×1
xn
können wir mit n × 1 Matrizen identifizieren.
Das allgemeine Gleichungsystem
III) Addieren des λ-fachen (λ ∈ K∗ ) der i-ten Zeile zur j-ten Zeile:
... ..
.
ai ai
A = ... 7→ ..
. =: AIII .
a λa + a
j i j
. ..
.
. .
Bemerkung 19.6. Die Operation vom Typ III und VI kann man auch durch
wiederholtes Anwenden von I und II erhalten.
Beweis. III)
... ... ..
. ..
.
ai λai λai ai
I II I
A = ... 7→ ... 7→ ..
.
→
7
..
. .
a a λa + a λa + a
j j i j
i j
. . .. ..
. .
. . . .
19.2 Der Gaußalgorithmus zum Lösen linearer Gleichungssysteme 245
IV)
... ... ... ... ...
ai ai a j a j
III II III I a j
.. .. .. ..
A = . 7→ . 7→ . 7→ . 7→ ... .
a a − a a − a −a a
j j i j
i
i
i
.
.. .. .. .. .
. . . . .
⊓
⊔
Definition 19.7. Eine Matrix A = (ai j ) ∈ Km×n hat Zeilenstufenform, wenn sie
folgende Form hat1 :
a1j1 ∗ ∗
a2j2 ∗
a3j3 ∗
, aiji , 0.
..
.
ar jr ∗
0
Satz 19.8 (Gaußalgorithmus). Sei A ∈ Km×n . Dann lässt sich A durch eine Folge
e die in Zeilenstufenform ist,
von elementaren Zeilenumformungen in eine Matrix A,
umformen.
Beweis. Induktion nach m. Für m = 1 ist die Aussage trivial richtig. Sei also
m ≥ 2. Wir betrachten die erste Spalte von A:
a11
.
a1 = .. .
am1
Hierbei steht ∗ für Einträge, die nicht genauer spezifiziert sind (sie dürfen auch
1
0 oder gar nicht vorhanden sein). Die 0 in der linken unteren Ecke repräsentiert die
Tatsache, dass alle Einträge, die links oder unterhalb der Linien sind, 0 sind. Solche
Notationen werden oft bei Matrizen verwendet.
246 19 Matrizen und Lineare Gleichungssysteme
1. Fall: Ist a11 , 0, dann setzen wir j1 = 1 und addieren jeweils das (− aa11i1 )-
fache der ersten Zeile zur i-ten Zeile. Anschließend hat A die Gestalt:
a11 a12 ∗ a11
∗
0 a′ · · · a′
22 2n =
. . .
.. .. .. 0 A′
0 a′m2 · · · a′m2
und wir fahren induktiv mit der Matrix A′ fort, die nämlich weniger
Spalten als A hat.
2. Fall: a11 = 0, aber a1 , 0. Ist etwa ai1 , 0, so vertauschen wir die i-te und
die 1-te Zeile
a11 a12 · · · ai1 ai2 · · ·
.. ..
. .
. .
. . . .
a a · · · 7→ a a · · ·
i1 i2 11 12
. . . .
. . . .
. . . .
und fahren wie im 1. Fall fort.
3. Fall: a1 = 0. In diesem Fall ist j1 > 1 und wir fahren mit der Teilmatrix
0
.
. ′ A′ ∈ Km×(n−1)
. A ,
0
genauso fort, bis die erste Spalte keine Nullspalte ist. Dann trifft auf die
neue Matrix Fall 1 oder 2 zu.
⊓
⊔
Vorlesung vom:
11. Mai 2012 Beispiel 19.9.
Qualitätsstand:
zweite Version 1 3 4 1 3 4 1 3 4 1 3 4 1 3 4
0 0 2 IIIs 0
0 2 IV
1 1 III
III 0 1 1 e
0 0 1 1
A = 7→ 7→ 7→ 7→
0 0 5 = A.
2 0 7 0 −6 −1 0 −6 −1 0 0 5
1 4 5 0 1 1 0 0 2 0 0 2 0 0 0
19.2 Der Gaußalgorithmus zum Lösen linearer Gleichungssysteme 247
4 2 7 5
3 0 6 4
B =
1 0 2 4
4 2 7 5 4 2 7 5
−3/2 6 − 21/4 4 − 15/4 = 0 −3/2 3/4 1/4
IVs
7→ 0
0 −1/2 2 − 7/4 1 − 5/4 0 −1/2 1/4 −1/4
4 2 7 5 4 2 7 5
(3)7→(3)−1/3·(2)
7→ 0 −3/2 3/4 1/4 = 0 −3/2 3/4 1/4
0 0 0 −1/4 − 1/12 0 0 0 −1/3
= e
B.
Es leuchtet unmittelbar ein, dass man, wenn man solche Rechnungen per
Hand durchführen möchte, sinnvollerweise versuchen wird, Brüche und zu
kleine Zahlen zu vermeiden. Dies ist manchmal möglich, indem man Zeilen–
oder Spaltenvertauschungen vornimmt. Im nächsten Semester werden wir
auf die damit zusammenhängende Thematik (genannt Pivotierung oder Pi-
votwahl) noch genauer eingehen, denn auch wenn man auf einem Computer
mit Fließkommazahlen arbeitet, möchte man nummerische Fehler möglichst
klein halten und beispielsweise vom Betrag her sehr kleine Zahlen vermei-
den. Auch dies ist mit geeigneten Vertauschungen oft möglich.
Ax = b
.
Beweis. Wir bringen die erweiterte Matrix (A .. b) in Zeilenstufenform durch
elemetare Zeilenumformungen:
∗ ∗e b1
∗
∗
..
e e
(A . b) =
.. .. ,
. .
∗e br
0
mit r Stufen. Ist die letzte Stufe bei Spalte n+1, dann hat das Gleichungssystem
keine Lösung, da
248 19 Matrizen und Lineare Gleichungssysteme
0x1 + · · · + 0xn = 0 , e
br .
Andernfalls ist die Gestalt
e a ∗ ∗
1j1
e
a2j2 ∗
e
a3 j3 ∗
..
.
e
ar jr ∗ ∗
0 0 0
e
arjr x jr + e arn xn = e
arjr +1 x jr +1 + · · · + e br
.. .
. = ..
∑ n
a1j x j = e
e bk
j= jk
.. .
. = ..
∑
n
a1j x j = e
e b1
j= j1
bestimmen:
∑
n
1 e
x jr = br − ar j x j
e
e
ar jr
j= jr +1
..
.
∑
n
1 e
x jk = bk − ak j x j
e
e
ak jk
j= jk +1
..
.
⊓
⊔
Wir können x3 = t ∈ R beliebig wählen. Dann ist −x2 −2t = −3, also x2 = 3−2t.
Eingesetzt in die erste Zeile liefert das: x1 + 2 · (3 − 2t) + 3t = 4, also x1 = −2 + t.
Wir finden also die Lösungsmenge:
{ t − 2 }
L = 3 − 2t t ∈ R ⊂ R3 .
t
∑
n ∑
n
n3
k(k − 1) ≈ k2 ≈ ∈ O(n3 )
3
k=1 k=1
Bemerkung 19.12. Es ist offen, was asymptotisch optimal ist. Arbeiten von
Strassen zeigen: Es kommt auf den Aufwand A · B aus A, B ∈ Kn×n an. Die
naive Betrachtungsweise anhand der Definition liefert: O(n3 ), nämlich n3
Multiplikationen und n2 (n − 1) Additionen.
Satz 19.13 (1969, Strassen). Seien A, B ∈ Kn×n . Dann kann man A·B mit O(nlog2 7 )
(man bemerke: O(nlog2 8 ) = O(n3 )) Operationen ausrechnen.
Aufgaben
Berechnen Sie AB und BA. Können Sie AB , BA auch ohne Rechnen einsehen?
Lineare Abbildungen
f : V → W,
Beispiel 20.2.
ist K-linear.
3. Die Translation eines Vektors b ∈ Rn , b , 0,
Rn 7→ Rn , x 7→ x + b
Abbildung 20.1. Die Funktionen f (x) = 3x + 1 und g(x) = 7x. Dabei ist f keine lineare
Abbildung, z.B. weil f (0) , 0 ist, g aber schon.
ist eine Abbildung injektiv, wenn jedes Element der Bildmenge höchstens
ein Urbild hat, surjektiv, wenn jedes solche mindestens ein Urbild hat, und
bijektiv, wenn jedes solche genau ein Urbild hat.
(auch manchmal im( f ) geschrieben, von engl. image) ein Untervektorraum von W.
Ker f = 0 = {0} ⊆ V.
256 20 Lineare Abbildungen
Satz 20.7. Sei V ein K-Vektorraum endlicher Dimension und B = {v1 , . . . , vn } eine
Basis.
ein Isomorphismus.
2. Ist W ein weiterer K-Vektorraum und A = {w1 , . . . , wn } eine beliebige Familie
von Vektoren aus W, dann ist die Abbildung
∑
n ∑
n
φB
A: V → W, v = λi vi 7→ λ i wi
i=1 i=1
linear.
Beweis. Surjektivität ist klar nach Definition einer Basis. Wegen der Eindeu-
tigkeit der Darstellung in einer Basis ist (0, . . . , 0)t der einzige Vektor, der
auf 0 ∈ V abgebildet wird. Die Linearität beider Abbildungen ist einfach
nachzuweisen und wird daher hier nicht vorgeführt. ⊓ ⊔
Bemerkung 20.9.
φB = φεB .
2. Vorgabe der Bilder einer Basis: Die zweite Aussage von Satz 20.7 besagt,
dass die Bilder einer Basis unter einer linearen Abbildung beliebig vor-
geschrieben werden können, etwa vi 7→ wi , i = 1, . . . , n, und dass damit
die lineare Abbildung festgelegt ist. Denn jeder Vektor v ∈ V entsteht als
Linearkombination der vi .
3. Isomorphie gleich-dimensionaler Vektorräume: Es gilt nach der ersten Aussa-
ge des Satzes 20.7:
dimK V = n ⇒ V Kn ,
da V eine Basis besitzt. Alle n-dimensionalen K-Vektorräume sind also
isomorph.
∑
m
f (v j ) = a1 j w1 + a2 j w2 + · · · + amj wm = ai j wi ∈ W.
i=1
(Dies basiert auf der Eindeutigkeit der Darstellung eines Vektors als Linearkombi-
nation einer Basis.) Dann heißt die Matrix
A = (ai j ) = MA
B
( f ) ∈ Km×n
ist R-linear, weil (p + q)(ai ) = p(ai ) + q(ai ) und (λp)(ai ) = λp(ai ). Um die Dar-
stellung von φ bezüglich der Basen A = {1, t, . . . , td } und der Standardbasis
ε = {e1 , . . . , ed+1 } ⊆ Rd+1 zu berechnen, betrachten wir für i = 0, 1, 2, . . . , d die
Bilder der Basisvektoren aus A und stellen diese als Linearkombination der
Basis ε des Zielvektorraumes dar:
i 1 0 0
α0
0
1 0
.
φ(ti ) = .. = αi0 · 0. + αi1 · 0. + · · · + αid · 0. .
i . . .
αd . . .
0 0 1
Merkregel 20.12. A ∈ Km×n mit Spalten A = (a1 , . . . , an ). Dann ist die j-te Spalte
a1j
.
a j = .. ∈ Km
amj
Also:
0 1 0 ··· 0
0 0 2 ··· 0
MA = .. .. .. .. ∈ R .
d×(d+1)
B (φ)
. . . ..
. .
000 ··· d
20.4 Matrixdarstellungen einer linearen Abbildung 259
1. Das Diagramm
f
VO /W
O
φA φB
Kn
A / Km
kommutiert, das heißt
x1
.
f (φA (x)) = φB (Ax) ∀x = .. ∈ Kn .
xn
2. Jede Matrix A ∈ Km×n liefert eine Abbildung f , so dass das Diagramm kommu-
tiert.
Betrachten wir nun den anderen Weg: Der linke Pfeil ist
x1
φA ∑ n
x = ... 7→ x jv j.
j=1
xn
f linear
∑
n
= x j f (v j )
j=1
Schauen wir uns nun die Ergebnisse, die wir auf den beiden Wegen in der
rechten oberen Ecke erhalten haben, an, so sehen wir:
∑ n
a1 j xi
j=1
! ∑ m ∑
n
.
=
φB .. ai j x j wi ,
∑ i=1 j=1
n
amj x j
j=1
f ◦g
UO /V /) W
g O f O
φC φA φB
Kr
B / Kn A /5 K m
C
20.5 Invertierbare Matrizen 261
kommutiert; insbesondere heißt dies, dass das Matrixprodukt der Komposition von
linearen Abbildungen entspricht.
Also:
∑
n
C = (cik ) ∈ Km×r mit cik = ai j b jk
j=1
B·C
&
Ks
C / Kr B / Kn A /5 K m .
:
A·B
(A·B)·C
⊓
⊔
B · A = E = (δkl ).
{
1, falls k = l
Hierbei bezeichnet δkl := das Kroneckersymbol; E ist also die
0, sonst.
Einheitsmatrix:
1 0 0 ... 0
0 1 0 ... 0
E = 0. 0 1 ...
.. .. . .
0 ∈ Kn×n .
..
.
. . . . .
0 0 0 ... 1
Wir definieren die Inverse:
A−1 := B.
(GL steht für general linear). Vermöge des Matrizenproduktes ist GL(n, k) eine
Gruppe.
Definition 20.20. Eine Gruppe (G, ·) ist eine Menge G, zusammen mit einer Ver-
knüpfung · , das heißt einer Abbildung
G × G → G, (A, B) 7→ A · B,
G1) Assoziativgesetz:
(A · B) · C = A · (B · C) ∀A, B, C ∈ G.
∃ E ∈ G mit A · E = A ∀A ∈ G.
20.6 Berechnung der Inversen mit dem Gaußalgorithmus 263
Eine Gruppe heißt abelsch (nach N.H. Abel (1802-1829), oder kommutativ), falls
für alle g, h ∈ G gilt: gh = hg.
Beweis (von Satz 20.19). Ist klar mit den vorigen Sätzen. ⊓
⊔
Beispiel 20.21.
Bemerkung 20.22.
Analog für die zweite und dritte Spalte bi = (b1i , b2i , b3i )t . Dies sieht man
besonders gut, wenn man das Matrizenprodukt A · B = E folgendermaßen
notiert:
b11 b12 b13
b21 b22 b23
b31 b32 b33
a11 a12 a13 1 0 0
a21 a22 a23 0 1 0 .
a31 a32 a33 0 0 1
4. Wir räumen die Einträge oberhalb der Diagonalen des linken Blocks von
unten nach oben aus. Zuerst 2. Zeile - 3. Zeile und 1. Zeile - 3 × 3. Zeile,
1 2 0 4 −6 3
⇝ 0 1 0 3 −3 1 ,
0 0 1 −1 2 −1
20.7 Der Gaußalgorithmus zur Berechnung der Inversen 265
Sei A ∈ Kn×n .
Die Notwendigkeit ist klar, weil sonst die letzte Zeile eine Nullzeile ist.
Die zugehörige lineare Abbildung ist nicht surjektiv, da dann nämlich
à · x = (x1 , . . . , xn−1 , 0)t ∀x ∈ Kn . Die andere Richtung der Behauptung
zeigt der folgende Algorithmus.
2. Ist A invertierbar, so erhält man die inverse Matrix wie folgt:
a) Wir bilden die um E erweiterte Matrix
a11 · · · · · · a1n 1 0 ··· 0
... a .. .. ..
. 0 1 . .
(A | E) = . 22
. . .. . . ..
.. . . .. . . . 0
an1 · · · · · · ann 0 ··· 0 1
und bringen diese auf Zeilenstufenform (mit Zeilenoperationen)