Kapitel 2
Folgen und Grenzwerte
Die Grundlage der Analysis ist der Begriff des Grenzwertes. Er ist aus der Schule bekannt (bzw. sollte bekannt sein) und wird hier rekapituliert. Da es kaum einen Unterschied macht, Folgen und Grenzwerte in R oder in C zu betrachten, formulieren wir die folgenden Definitionen und Satze in C, was R als Spezialfall dieresis
dieresis
umschließt. In den Beispielen und Ubungen werden hauptsachlich reelle Folgen dieresis
betrachtet.
2.1 Definitionen, Beispiele, einige Satze
dieresis
Notation: N = {1, 2, . . .}, N = {0, 1, 2, . . .}.
0
Definition 2.1: (Folgen)
Eine Folge (z ) = (z , z , z . . .), manchmal auch (z ) = (z , z , z , . . .),
n 1 2 3 n 0 1 2
ist eine Zuordnung (Funktion)
Index n element N (bzw. N ) minus arrowright Wert z element C.
0 n
Beispiel 2.2:
n
a) x = (minus 1) ; n element N. Die Folge (x ) ist (minus 1, 1, minus 1, 1, . . .).
n n
1 1 1 1
b) x = ; n element N. Die Folge (x ) ist (1, , , , . . .).
n n
n 2 3 4
1 3 8 15 24
c) x = 1 minus ; n element N. Die Folge (x ) ist (0, , , , , . . .).
n 2 n
n 4 9 16 25
1 n
d) x = (1 + ) ; n element N. Die Folge (x ) ist
n n
n
parenleftBig parenrightBig
9 64 625 7776
2, , , , , . . . approxequal (2.0, 2.25, 2.3703..., 2.4414..., 2.4883..., . . .).
4 27 256 3125
16 KAPITEL 2. FOLGEN UND GRENZWERTE Beispiel 2.3: Einige simple Berechnungen mit MuPAD. Folgen konnen z.B. als Funk-
dieresis
tionen definiert werden:
>> x := n -> (1 + 1/n)^n
n -> (1 + 1/n)^n
Der Folgengenerator" $ dient zur Erzeugung von Folgen:
quotedblright
>> x(n) $ n = 1..5
2, 9/4, 64/27, 625/256, 7776/3125
Gleitpunktnaherungen werden durch float erzeugt:
dieresis
>> float(x(n)) $ n = 1..5
2.0, 2.25, 2.37037037, 2.44140625, 2.48832
Manchmal sind Monotonieeigenschaften von Folgen interessant. Da hierzu Folgenglieder verglichen werden mussen, kann Monotonie nur im Reellen betrachtet dieresis
werden (auf C gibt es keine sinnvolle Begriff sbildung der Art z < z ).
1 2
Bezeichnung 2.4:
Eine reelle Folge (x ) heißt monoton wachsend" bzw. monoton
n quotedblright quotedblright
fallend", wenn x lessequal x bzw. x greaterequal x gilt fur alle Indexpaare n, m mit
dieresis
n m n m
n < m. Bei x < x bzw. x > x spricht man von streng monoton
n m n m quotedblright
wachsend" bzw. streng monoton fallend".
quotedblright
Zunachst die formale Definition von Konvergenz" und Grenzwert", die etwas dieresis quotedblright quotedblright
abschreckend sein mag, aber (keine Angst!) spater nur in (den hier nicht wirkdieresis lich interessierenden) technischen Beweisen zum Einsatz kommt. Oft reicht es, einfache Vererbungsreglen wie z.B. aus Satz 2.13 zu benutzen, um Grenzwerte
mittels Arithmetikregeln zu ermitteln.
Definition 2.5: (Grenzwerte von Folgen)
asteriskmath
Eine Folge (z ) in C heißt konvergent", wenn eine Zahl z element C exi-
n quotedblright asteriskmath
stiert, so dass sich (intuitiv) alle Zahlen z fur großes n dem Wert z
dieresis
n
quotedblright
beliebig genau annahern".
dieresis
Formal: zu jedem noch so kleinen epsilon1 > 0 laßt sich eine reelle Zahl N(epsilon1 )
dieresis
asteriskmath
angeben, so dass |z minus z | lessequal epsilon1 gilt fur alle Indizes n greaterequal N(epsilon1 ).
dieresis
n
Anschaulich: alle Werte z weichen fur n greaterequal N(epsilon1 ) maximal um den Wert
dieresis
n
epsilon1 vom Grenzwert ab.
asteriskmath
Der Wert z heißt dann Grenzwert" ( Limes") der Folge (z ).
n
quotedblright quotedblright
Schreibweisen:
asteriskmath asteriskmath
z = lim z oder auch z arrowright z fur n arrowright infinity .
dieresis
n n
narrowright infinity
dieresis
2.1. DEFINITIONEN, BEISPIELE, EINIGE SATZE 17
Eine nicht konvergierende Folge heißt divergent". Konvergente Folgen
quotedblright
mit dem Grenzwert 0 heißen auch Nullfolgen.
Bemerkung 2.6: Die Aussage fur alle n greaterequal N(epsilon1 )" impliziert, dass nur hinreidieresis
quotedblright quotedblright
chend große Indizes n" betrachtet zu werden brauchen. Merke: fur Konvergenz dieresis ist das Verhalten der Folge fur kleine Indexwerte vollig irrelevant. Genauer: dieresis dieresis
man kann immer endlich viele Folgenelemente abandern, ohne dass sich etwas dieresis an der Konvergenz andert: man kann o.B.d.A. (= ohne Beschrankung der dieresis dieresis
Allgmeinheit) immer N(epsilon1 ) großer wahlen als der großte Index der geanderten dieresis dieresis dieresis dieresis
Folgenglieder.
Eine intuitive Interpretation der epsilon1 -Definition der Konvergenz lautet:
Fur jedes (noch so kleine) epsilon1 > 0 haben hochstens endlich viele
dieresis dieresis
Folgenglieder einen Abstand zum Grenzwert, der großer ist als epsilon1 .
dieresis
Satz 2.7: (Eindeutigkeit von Grenzwerten)
asteriskmath
Grenzwerte sind eindeutig, d.h., zu (z ) gibt es hochstens ein z mit der
dieresis
n
obigen Eigenschaft.
asteriskmath asteriskmath asteriskmath
Beweis: Seien z und z zwei Grenzwerte. Zu jedem epsilon1 > 0 gilt fur hinreichend dieresis
große Indizes n: asteriskmath asteriskmath asteriskmath
|z minus z | lessequal epsilon1 , |z minus z | lessequal epsilon1
n n
asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath
arrowdblright |z minus z | = |z minus z + z minus z | lessequal |z minus z | + |z minus z | lessequal 2 periodcentered epsilon1 .
n n n n
Da epsilon1 > 0 beliebig klein gewahlt werden kann und damit auch 2 periodcentered epsilon1 beliebig klein dieresis
asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath
sein kann, folgt |z minus z | = 0, also z = z .
Q.E.D.
Einige einfache Beispiele mit formalem Beweis:
Beispiel 2.8: Die konstante Folge (z ) = (c, c, c, . . .) ist konvergent mit dem Grenzwert
n
asteriskmath z = lim z = c, denn fur alle n gilt
dieresis
n
narrowright infinity
asteriskmath
|z minus z | = |c minus c| = 0 lessequal epsilon1 ,
n
wie auch immer epsilon1 > 0 vorgegeben wird. Formal: zu epsilon1 > 0 wahle N(epsilon1 ) = 1.
dieresis
Nun ja, im obigen Beispiel war sogar das formale N(epsilon1 )endash Kriterium sehr einfach
zu handhaben. Im nachsten Beispiel wird es ein klein wenig komplizierter:
dieresis
18 KAPITEL 2. FOLGEN UND GRENZWERTE
asteriskmath
1
Beispiel 2.9: Die Folge x = ist konvergent mit dem Grenzwert x = lim x = 0.
n n
n narrowright infinity
1
Formaler Beweis: zu beliebigem epsilon1 > 0 wahle N(epsilon1 ) = . Dann folgt fur alle n greaterequal N(epsilon1 ):
dieresis dieresis
epsilon1
vextendsingle vextendsingle
vextendsingle vextendsingle 1 1 1 1
asteriskmath vextendsingle vextendsingle
|x minus x | = |x minus 0| = |x | = = lessequal = = epsilon1 .
n n n 1
vextendsingle vextendsingle n n N (epsilon1 ) epsilon1
Und noch ein Beispiel mit formalem Beweis:
n
Beispiel 2.10: Fur c element C gelte |c| < 1. Dann ist die Folge z = c eine Nullfolge.
dieresis n
1 1
Beweis: Fur c = 0 ist alles klar. Sei nun c negationslash = 0. Definiere h = minus 1 > 0, d.h., |c| = .
dieresis |c| 1+h
Es gilt
parenleftbigg parenrightbigg
1 1 n
n 2
= = (1 + h) = 1 + n periodcentered h + periodcentered h + periodcentered periodcentered periodcentered greaterequal 1 + n periodcentered h > n periodcentered h.
n n
|c | |c| 2
1 1
n
Es folgt |c | < lessequal epsilon1 fur alle Indizes n greaterequal =: N(epsilon1 ).
dieresis
nperiodcentered h hperiodcentered epsilon1 Q.E.D.
Beispiele:
n
c = 0.5 : (c ) = (0.5, 0.25, 0.125, 0.0625, 0.03125 . . .).
Fur |c| greaterequal 1 gilt diese Aussage nicht! Z.B.:
dieresis
n
c = 1 : (c ) = (1, 1, 1, 1, . . .) (konvergiert gegen 1),
n
c = i : (c ) = (i, minus 1, minus i, 1, i, minus 1, . . .) (konvergiert nicht),
n
c = 2 : (c ) = (2, 4, 8, 16, . . .) (divergiert, bzw. konvergiert gegen infinity ").
quotedblright
2.5.02arrowdown Beispiel 2.11: Einige Berechnungen mit MuPAD:
>> x := n -> c^n
n -> c^n
>> x(n) $ n = 1..10
2 3 4 5 6 7 8 9 10
c, c , c , c , c , c , c , c , c , c
Grenzwerte werden mit limit berechnet. Die Hilfeseite dazu wird mittels ?limit an-
gefordert:
>> ?limit
Ohne Weiteres kann der Grenzwert nicht bestimmt werden, da er ja von den Eigen-
schaften von c abhangt:
dieresis
dieresis
2.1. DEFINITIONEN, BEISPIELE, EINIGE SATZE 19
>> limit(x(n), n = infinity)
Warning: cannot determine sign of ln(c) [stdlib::limit::limitMRV]
n
limit(c , n = infinity)
Nehmen wir an, c sei reell und 0 < c < 1:
>> assume(0 < c < 1):
>> limit(x(n), n = infinity)
0
Nehmen wir an, c > 1:
>> assume(c > 1):
>> limit(x(n), n = infinity)
infinity
Ein Beispiel einer nicht konvergierenden Folge:
n
Beispiel 2.12: Die Folge x = (minus 1) , also (x ) = (minus 1, 1, minus 1, 1, . . .) ist nicht konvergent n n
(hat keinen Grenzwert). Hier ein formaler Beweis (damit in dieser Vorlesung wenigstens
1
einmal ein sauberer Nichtexistenzbeweis vorkommt): zu epsilon1 = laßt sich kein N(epsilon1 ) finden. dieresis
2
asteriskmath
Angenommen, ein Grenzwert x existiert. Dann mußte N(epsilon1 ) existieren mit
dieresis
asteriskmath asteriskmath
|x minus x | lessequal epsilon1 , |x minus x | lessequal epsilon1
n n+1
fur alle n greaterequal N(epsilon1 ). Es wurde folgen:
dieresis dieresis
1 1
asteriskmath asteriskmath asteriskmath asteriskmath
|x minus x | = |x minus x + x minus x | lessequal |x minus x | + |x minus x | lessequal epsilon1 + epsilon1 = + = 1.
n n+1 n n+1 n n+1
bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright 2 2
=0
Fur die betrachtete Folge gilt aber |x minus x | = 2 fur jedes n. Widerspruch! Damit dieresis dieresis
n n+1
asteriskmath
muß die Annahme es existiert x " falsch gewesen sein.
quotedblright
Die formale Definition mit epsilon1 und N(epsilon1 ) ist unangenehm und man mochte diese dieresis recht technischen Betrachtungen und Abschatzungen liebend gern vermeiden. dieresis Wie geht man beim praktischen Rechnen vor? Es gibt Rechenregeln! Damit laßt dieresis
sich epsilon1 und N(epsilon1 ) praktisch immer verbannen:
Satz 2.13: (Rechenregeln fur Grenzwerte)
dieresis
Seien (x ), (y ) konvergente Folgen in C, sei c element C eine Konstante. Dann
n n
gilt:
a) lim (c periodcentered x ) = c periodcentered lim x ,
n n
narrowright infinity narrowright infinity
20 KAPITEL 2. FOLGEN UND GRENZWERTE
b) lim (x plusminus y ) = lim x plusminus lim y ,
n n n n
narrowright infinity narrowright infinity narrowright infinity
c) lim (x periodcentered y ) = lim x periodcentered lim y ,
n n n n
narrowright infinity narrowright infinity narrowright infinity
parenleftBig parenrightBig lim xn
xn narrowright infinity
d) lim = , falls lim y negationslash = 0 gilt (!),
n
narrowright infinity narrowright infinity
y lim y
n n
narrowright infinity
radicalBig
radical
e) lim x = lim x .
n n
narrowright infinity narrowright infinity
Eine Beweisandeutung (nur fur technisch Interessierte):
dieresis
asteriskmath asteriskmath
Beweisskizze: Seien x bzw. y die Grenzwerte von (x ) bzw. (y ).
n n
a) Fur c = 0 ist die Behauptung sicherlich richtig. Sei nun c negationslash = 0. Zu epsilon1 > 0 gibt dieresis
es ein N , so dass epsilon1
asteriskmath
|x minus x | lessequal
n |c|
gilt fur alle n greaterequal N . Fur diese Indizes folgt
dieresis dieresis
epsilon1
asteriskmath asteriskmath
|c periodcentered x minus c periodcentered x | = |c| periodcentered |x minus x | lessequal |c| periodcentered = epsilon1 .
n n |c|
b) Wahle ein beliebiges epsilon1 > 0. Da (x ) und (y ) als konvergent vorausgesetzt dieresis n n
sind, gibt es Werte N bzw. N mit
x y
epsilon1 epsilon1
asteriskmath asteriskmath
|x minus x | lessequal bzw. |y minus y | lessequal
n n
2 2
fur alle n greaterequal N bzw. n greaterequal N . Fur alle n greaterequal N(epsilon1 ) := max(N , N ) folgt
dieresis dieresis
x y x y
asteriskmath asteriskmath asteriskmath asteriskmath
|x plusminus y minus (x plusminus y )| = |x minus x plusminus (y minus y )|
n n n n
epsilon1 epsilon1
asteriskmath asteriskmath
lessequal |x minus x | + | plusminus (y minus y )| lessequal + = epsilon1 .
n n 2 2
Die Aussagen c) endash e) lassen sich mit ahnlichen (etwas aufwendigeren) dieresis
Abschatzungen beweisen.
dieresis
Q.E.D. Beispiel 2.14: Wir wissen bereits, dass konstante Folgen x = c gegen c konvergieren,
n
1
und dass x = eine Nullfolge ist. Durch Einsatz der Rechenregeln folgt unmittelbar: n n
1 1 1 1 1
lim = lim periodcentered = lim periodcentered lim = 0 periodcentered 0 = 0,
2
narrowright infinity narrowright infinity narrowright infinity narrowright infinity
n n n n n
1 1 1 1 1
lim = lim periodcentered = lim periodcentered lim = 0 periodcentered 0 = 0,
3 2 2
narrowright infinity narrowright infinity narrowright infinity narrowright infinity
n n n n n
usw. Durch Induktion nach k ergibt sich:
1
Alle Folgen der Form x = mit positiven Potenzen k sind Nullfolgen.
n kn
dieresis
2.1. DEFINITIONEN, BEISPIELE, EINIGE SATZE 21 Manchmal muß man etwas manipulieren und umschreiben. Bei rationalen Ausdrucken in n (also Polynom(n)/Polynom(n)) gilt das allgemeine Rezept: ziehe dieresis in Zahler und Nenner die fuhrende Potenz von n raus und kurze. Typischerweise dieresis dieresis dieresis
verbleiben dann nur noch Nullfolgen im Ausdruck, die zu 0 werden, wenn man
uber die obigen Rechenregeln den Grenzwert in den Ausdruck 'reinzieht":
dieresis quotedblright
Beispiel 2.15:
1
1 1
2 2+ lim
2 n periodcentered (2 + ) 2 + 2
2 periodcentered n + 1 2+ 0
2 2 narrowright infinity n
n n
lim = lim = lim = = = 2 .
1 1
2 2 1
narrowright infinity narrowright infinity narrowright infinity
n minus n 1minus 0
n periodcentered (1 minus ) 1 minus
n n 1 minus lim
narrowright infinity n
Hierbei wurde benutzt, dass wir in den Beispielen 2.9 und 2.14 bereits 1/n und
2
1/n als Nullfolgen identifiziert haben. Man sieht, mit etwas Geschick eingesetzt,
machen die Rechenregeln die Berechnung von Grenzwerten oft sehr einfach.
Manchmal muß man allerdings tricksen":
quotedblright
Beispiel 2.16:
radical radical radical
radical radical radical
2 2
radical radical ( n + 1 minus n) periodcentered ( n + 1 + n) n + 1 minus n
radical radical
lim ( n + 1 minus n) = lim = lim
radical radical
narrowright infinity narrowright infinity narrowright infinity
n + 1 + n n + 1 + n
(n + 1) minus n 1 1
radical radical radicalBig
= lim = lim = lim
radical radical radical
narrowright infinity narrowright infinity narrowright infinity 1
n + 1 + n n + 1 + n n periodcentered (1 + ) + n
n
1 1
radicalBig radicalBig
= lim = lim parenleftBig parenrightBig
radical radical radical
narrowright infinity narrowright infinity
1 1
n periodcentered 1 + + n n periodcentered 1 + + 1
n n
radicalbigg
1 1 1 1
radical radicalBig radicalbigg
= lim periodcentered lim = lim periodcentered parenleftBig parenrightBig
narrowright infinity narrowright infinity narrowright infinity
n n
1 1
1 + + 1
n lim 1 + + 1
narrowright infinity n
radicalbigg 1 1 1
radicalbigg radical
= lim periodcentered = 0 periodcentered = 0.
narrowright infinity n 1+ 0+ 1
1
1 + lim + 1
narrowright infinity n
Manchmal helfen alle Rechenregeln nichts, und man muß technisch abschatzen. dieresis Eine hilfreiche Aussage liefert der folgende Satz, der nur fur reelle Folgen gilt. dieresis Liegen die Folgenglieder x in Intervallen [a , b ] und konvergieren die Inter-
n n n
vallenden gegen den selben Wert, so bleibt der Folge nichts anderes ubrig, als dieresis ebenfalls gegen diesen Wert zu konvergieren (die Intervalllange b minus a konverdieresis n n
giert gegen 0):
22 KAPITEL 2. FOLGEN UND GRENZWERTE
Satz 2.17: (Intervallschachtelung)
Seien (a ), (b ), (x ) reelle Folgen. Die Folgen (a ) und (b ) mogen ge-
dieresis
n n n n n
gen den selben Grenzwert konvergieren. Gilt fur alle hinreichend großen
dieresis
Indizes a lessequal x lessequal b , so konvergiert auch (x ) gegen
n n n n
lim x = lim a = lim b .
n n n
narrowright infinity narrowright infinity narrowright infinity
asteriskmath
Beweis: Sei x der Grenzwert von (a ) und (b ). Die Folge (b minus a ) ist positiv n n n n
und eine Nullfolge. Zu epsilon1 > 0 gibt es Werte N bzw. N mit
1 2
epsilon1 epsilon1
asteriskmath
b minus a = |b minus a | lessequal , |a minus x | lessequal
n n n n n
2 2
fur alle n greaterequal N bzw. n greaterequal N . Fur alle n greaterequal N := max(N , N ) folgt
dieresis dieresis
1 2 1 2
asteriskmath asteriskmath asteriskmath
|x minus x | = |x minus a + a minus x | lessequal |x minus a | + |a minus x |
n n n n n n n
epsilon1 epsilon1
asteriskmath asteriskmath
= x minus a + |a minus x | lessequal b minus a + |a minus x | lessequal + = epsilon1 .
n n n n n n 2 2 Q.E.D.
n
Beispiel 2.18: Sei x = . Off ensichtlich gilt
n 2n +1
n n 1
0 lessequal x = lessequal = .
n 2 2
bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright n + 1 n n
bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright
an bn
1
Die Intervallgrenzen a = 0 und b = sind beides Nullfolgen, also ist auch x eine
n n n
n
Nullfolge.
1/n
Beispiel 2.19: Fur positive reelle Zahlen c definieren wir z = c als die positive dieresis n
n
reelle Losung von z = c.
dieresis
Fall 1: Sei c greaterequal 1. Sicherlich gilt z greaterequal 1 . Setze z = 1 + h mit h greaterequal 0. Es folgt
n n n n
parenleftbigg parenrightbigg
n cminus 1
n 2
c = (1 + h ) = 1 + n periodcentered h + periodcentered h + periodcentered periodcentered periodcentered greaterequal 1 + n periodcentered h arrowdblright 0 lessequal h lessequal .
n n n n
n
2 n
Damit ist h eine Nullfolge, also z = 1 + h arrowright 1 fur n arrowright infinity .
dieresis
n n n
Fall 2: Sei 0 < c lessequal 1. Sicherlich gilt 0 < z lessequal 1. Setze z = 1/(1 + h ) mit h greaterequal 0.
n n n n
Analog zu Fall 1 folgt
parenleftbigg parenrightbigg 1 minus 1
1 n
n 2 c
= (1 + h ) = 1 + n periodcentered h + periodcentered h + periodcentered periodcentered periodcentered greaterequal 1 + n periodcentered h arrowdblright 0 lessequal h lessequal .
n n n n
n
c 2 n
Damit ist h eine Nullfolge, also z = 1/(1 + h ) arrowright 1 fur n arrowright infinity .
dieresis
n n n
Merke:
1/n
lim c = 1 fur jedes reelle c > 0.
dieresis
narrowright infinity
dieresis
2.1. DEFINITIONEN, BEISPIELE, EINIGE SATZE 23
Satz und Definition 2.20:
z n
Sei z eine beliebige komplexe Zahl. Die Folge x = (1 + ) konver- arrowdown 3.5.02
n n
asteriskmath z
giert gegen einen von z abhangenden Grenzwert x (z), der auch als e
dieresis z
oder auch als exp(z) bezeichnet wird. Die Funktion exp : z mapsto arrowright e heißt
1
Exponential-Funktion". Der spezielle Grenzwert e = e fur z = 1
dieresis
quotedblright heißt Eulersche Zahl":
quotedblright parenleftBig parenrightBig n
1
e = lim 1 + approxequal 2.71828... .
narrowright infinity n
Der Beweis ist sehr technisch und bringt keine wirklichen Erkenntnisse. Nur
der Vollstandigkeit halber wird eine Teilskizze angegeben:
dieresis
Beweisskizze: Wir betrachten nur den Fall z = 1. Man zeigt jeweils per In-
parenleftBig parenrightBig n
1
duktion, dass die reelle Folge x = 1 + streng monoton wachsend in n ist n n
und dass
parenleftBig parenrightBig parenleftBig parenrightBig parenleftBig parenrightBig parenleftBig parenrightBig
n nminus 1
1 1 1 1
y = 1 + = 1 + periodcentered 1 + = x periodcentered 1 +
n nminus 1
n minus 1 n minus 1 n minus 1 n minus 1
streng monoton fallend in n ist. Da off ensichtlich x < y < y = 4 gilt, ist x
n n 2 n
monoton wachsend und nach oben beschrankt. Dies reicht, um die Konvergenz
dieresis
von (x ) zu folgern (Satz 2.28). Zusatz: y ist monoton fallend und nach unten
n n
durch y > x > x = 2 beschrankt, konvergiert also ebenfalls. Es gilt
dieresis
n nminus 1 1
parenleftBig parenrightBig parenleftBig parenrightBig
1 1
lim y = lim x periodcentered 1 + = lim x periodcentered lim 1 +
n nminus 1 nminus 1
narrowright infinity narrowright infinity narrowright infinity narrowright infinity
n minus 1 nminus 1
= lim x = lim x .
nminus 1 n
narrowright infinity narrowright infinity
Damit liefert jedes x eine untere und y eine obere Schranke fur die Eulersche dieresis
n n
Zahl, wobei das Intervall [x , y ], in dem sie zu finden ist, auf die Lange 0 dieresis
n n
zusammenschrumpft.
Q.E.D.
Eine technische Voruberlegung fur den Beweis des kommenden Satzes 2.22:
dieresis dieresis
Technischer Hilfssatz 2.21:
2
Sei (z ) eine komplexe Nullfolge mit der Eigenschaft, dass (n periodcentered z ) be-
n n
schrankt ist (d.h., es gibt eine Konstante c > 0, so dass fur alle Indizes n
dieresis dieresis
c
|z | lessequal gilt). Dann gilt
n 2n
n
lim (1 + z ) = 1.
n
narrowright infinity
24 KAPITEL 2. FOLGEN UND GRENZWERTE Der Beweis ist sehr technisch und bringt keine wirklichen Erkenntnisse. Er ist
nur der Vollstandigkeit halber angegeben:
dieresis
Beweis: Es gilt (Aufgabe 8) fur jedes z element C:
dieresis
parenleftBig parenrightBig
n nminus 1
z minus 1 = (z minus 1) periodcentered 1 + z + periodcentered periodcentered periodcentered + z .
Fur z = 1 + z folgt
dieresis n
parenleftBig parenrightBig
n nminus 1
(1 + z ) minus 1 = z periodcentered 1 + (1 + z ) + periodcentered periodcentered periodcentered + (1 + z ) .
n n n n
Die Dreiecksungleichung liefert
vextendsingle vextendsingle parenleftBig parenrightBig
vextendsingle vextendsingle
n nminus 1
(1 + z ) minus 1 lessequal |z | periodcentered 1 + |1 + z | + periodcentered periodcentered periodcentered + |1 + z |
vextendsingle vextendsingle
n n n n
parenleftBig parenrightBig
nminus 1
lessequal |z | periodcentered 1 + (1 + |z |) + periodcentered periodcentered periodcentered + (1 + |z |) .
n n n
k n
Mit (1 + |z |) lessequal (1 + |z |) fur alle k = 0, 1, . . . , n minus 1 folgt
dieresis
n n
vextendsingle vextendsingle parenleftBig parenrightBig
vextendsingle vextendsingle
n n n n
(1 + z ) minus 1 lessequal |z | periodcentered (1 + |z |) + (1 + |z |) + periodcentered periodcentered periodcentered + (1 + |z |)
vextendsingle vextendsingle
n n n n n
n
= n periodcentered |z | periodcentered (1 + |z |) .
n n
2
Wegen |z | lessequal c/n gilt auch |z | lessequal c/n:
n n
vextendsingle vextendsingle parenleftBig parenrightBig n
c
vextendsingle vextendsingle
n c
(1 + z ) minus 1 lessequal n periodcentered |z | periodcentered 1 + lessequal n periodcentered |z | periodcentered e .
vextendsingle vextendsingle
n n n
n
2
Wegen |z | lessequal c/n gilt |n periodcentered z | lessequal c/n:
n n
vextendsingle vextendsingle c
c periodcentered e
vextendsingle vextendsingle
n
(1 + z ) minus 1 lessequal .
vextendsingle vextendsingle
n n
parenleftBig parenrightBig
n n
Damit gilt lim (1 + z ) minus 1 = 0, und es folgt lim (1 + z ) = 1.
n n
narrowright infinity narrowright infinity Q.E.D.
Der folgende Satz ist fundamental und sehr wichtig:
Satz 2.22: (Funktionalgleichungen der Exponentialfunktion)
Fur alle z, z , z element C, n element Z gilt:
dieresis 1 2
1
0 minus z z +z z z z n nperiodcentered z
1 2 1 2
e = 1, e = , e = e periodcentered e , (e ) = e .
ze
dieresis
2.1. DEFINITIONEN, BEISPIELE, EINIGE SATZE 25 Trotz aller Wichtigkeit des Satzes: der Beweis bringt keine wirklichen Erkenntnisse und ist nur der Vollstandigkeit halber fur technisch Interessierte dieresis dieresis
angegeben:
Beweis: Es gilt
parenleftBig parenrightBig parenleftBig parenrightBig parenleftBig parenrightBig
n n n
z + z z z
1 2 1 2
1 + periodcentered 1 minus periodcentered 1 minus
n n n
parenleftBig parenleftBig parenrightBig parenleftBig parenrightBig parenleftBig parenrightBig parenrightBig n
z + z z z
1 2 1 2
= 1 + periodcentered 1 minus periodcentered 1 minus
n n n
parenleftBig parenrightBig
2 2 n
z + z periodcentered z + z z periodcentered z periodcentered (z + z )
1 2 1 2 1 2
1 2
= 1 minus + .
2 3
n n
Die Folge 2 2
z + z periodcentered z + z z periodcentered z periodcentered (z + z )
1 2 1 2 1 2
1 2
x = minus +
n 2 3
n n
parenleftBig parenrightBig
1 z periodcentered z periodcentered (z + z )
1 2 1 2
2 2
= periodcentered z + z periodcentered z + z +
1 2
1 2
2n n 2
erfullt die im Hilfssatz 2.21 geforderte Bedingung |x | lessequal c/n mit
dieresis n
vextendsingle vextendsingle
z periodcentered z periodcentered (z + z ) |z periodcentered z periodcentered (z + z )|
vextendsingle vextendsingle
1 2 1 2 1 2 1 2
2 2 2 2
z + z periodcentered z + z + lessequal |z + z periodcentered z + z | +
vextendsingle vextendsingle
1 2 1 2
1 2 1 2
n n
2 2
lessequal |z + z periodcentered z + z | + |z periodcentered z periodcentered (z + z )| =: c.
1 2 1 2 1 2
1 2
Hilfssatz 2.21 liefert damit
parenleftBig parenrightBig parenleftBig parenrightBig parenleftBig parenrightBig
n n n
z + z z z
1 2 1 2 n
lim 1 + periodcentered 1 minus periodcentered 1 minus = lim (1 + x ) = 1
n
narrowright infinity narrowright infinity
n n n
und folglich gilt:
parenleftBig parenrightBig parenleftBig parenrightBig parenleftBig parenrightBig
n n n
z + z z z
1 2 1 2
1 = lim 1 + periodcentered lim 1 minus periodcentered lim 1 minus
narrowright infinity narrowright infinity narrowright infinity
n n n
z +z minus z minus z
1 2 1 2
= e periodcentered e periodcentered e .
parenleftBig parenrightBig n
0
0 n
Mit e = lim 1 + = lim 1 = 1 folgt fur z = z, z = minus z:
dieresis 1 2
narrowright infinity narrowright infinity
n
1 0 minus z z minus z z minus z
1 = e periodcentered e periodcentered e = e periodcentered e arrowdblright e = .ze
Fur allgemeine z , z folgt dann:
dieresis 1 2
z +z minus z minus z z +z z z
1 2 1 2 1 2 1 2
1 = e periodcentered e periodcentered e arrowdblright e = e periodcentered e .
Hiermit folgt fur n element N:
dieresis
z n z z z z+z+...+z nperiodcentered z
(e ) = e periodcentered e periodcentered . . . periodcentered e = e = e .
minus z z
Mit e = 1/e folgt die selbe Eigenschaft auch fur negative ganzzahlige Potendieresis
zen n.
Q.E.D.
26 KAPITEL 2. FOLGEN UND GRENZWERTE
Beispiel 2.23: Einige Rechnungen mit MuPAD. Die Exponentialfunktion heißt exp:
>> limit((1 + 1/n)^n, n = infinity)
exp(1)
Mit \% wird auf den letzten Wert zugegriff en:
>> float(\%)
2.718281829
>> exp(20) = float(exp(20))
exp(20) = 485165195.4
>> exp(3 + I/2) = float(exp(3 + I/2))
exp(3 + 1/2 I) = 17.62671695 + 9.629519358 I
Fur reelle Argumente kann die Exponentialfunktion mittels plotfunc2d gezeichnet
dieresis
werden. Falls x vorher einen Wert zugewiesen bekommen hatte, muß dieser zunachst
dieresis
mittels delete geloscht werden:
dieresis
>> delete x:
>> plotfunc2d(exp(x), x = -2..3)
2.2 Weitere Konvergenzsatze
dieresis
In diesem Abschnitt werden einige allgemeine Satze formuliert, die hilfreich dieresis sind, die Konvergenz von Folgen zu prufen. Als Vorbereitung wird zunachst das dieresis dieresis
Supremumsaxiom vorgestellt. Es garantiert, dass R vollstandig" genug ist, um dieresis
quotedblright
die Existenz diverser Grenzwerte zu sichern.
2.2.1 Das Supremumsaxiom fur R
dieresis
Welcher Unterschied besteht zwischen der Menge R der reellen Zahlen und der Menge Q der rationalen Zahlen? In beiden Mengen ist die Arithmetik (Addition, Subtraktion, Multiplikation, Division) definiert und verlaßt die Menge nicht. dieresis Mathematisch gesprochen: beide Mengen sind Korper". Die Einfuhrung der
dieresis dieresis
quotedblright
reellen Zahlen als Verallgemeinerung der rationalen Zahlen ist dadurch moti-
radical
2
viert, Gleichungen wie z.B. x = 2 losen zu konnen ( 2 ist eine irrationale dieresis dieresis
Zahl, also in R, aber nicht in Q). In diesem Sinne ist R vollstandiger" als Q. dieresis
quotedblright
Worauf lauft dies mathematisch hinaus?
dieresis
dieresis
2.2. WEITERE KONVERGENZSATZE 27
Definition 2.24: (Beschranktheit)
dieresis
Eine Teilmenge A von R heißt nach oben bzw. nach unten be-
quotedblright
schrankt", wenn es Zahlen M element R bzw. m element R gibt, so dass a lessequal M
dieresis
bzw. m lessequal a fur alle a element A gilt. Die Zahl M bzw. m heißt obere bzw.
dieresis quotedblright
untere Schranke" fur A. Eine sowohl nach oben als auch nach unten
dieresis
beschrankte Menge heißt beschrankt". Es gilt |a| lessequal max(|m|, |M |) fur
dieresis dieresis dieresis
quotedblright
alle a element A.
Das Supremumsaxiom 2.25:
Jede nach oben beschrankte nichtleere Teilmenge A von R besitzt eine
dieresis
kleinste obere Schranke ( das Supremum" von A):
quotedblright
sup A = min{M element R; a lessequal M für alle a element A}.
Jede nach unten beschrankte nichtleere Teilmenge A von R besitzt eine
dieresis
großte untere Schranke ( das Infimum" von A):
dieresis quotedblright
inf A = max{m element R; m lessequal a für alle a element A}.
Hierbei braucht man als Axiom eigentlich nur die Existenz eine Supremums zu fordern. Das Infimum von A ergibt sich dann automatisch als das negative
Supremum der Menge der negativen Werte in A:
inf A = minus sup {minus a; a element A}.
Die Existenz des Minimums/Maximums aller oberen/unteren Schranken, welche das Supremum/Infimum definieren, ist die gewunschte Vollstandigkeit der dieresis dieresis
reellen Zahlen, die R z.B. von Q unterscheidet.
Bemerkung 2.26: Existiert in A propersubset R ein maximales Element, so ist dieses
Maximum auch das Supremum:
sup A = max A.
Aber nicht jede beschrankte Menge hat ein maximales Element. Z.B. hat A = dieresis
[0, 1) kein Maximum, denn das Supremum sup A = 1 (der einzige Kandidat furdieresis
das Maximum) liegt nicht in A.
Beispiel 2.27: Beispielsweise garantiert das Supremumsaxiom, dass es eine positive
radical 2
reelle Zahl 2 gibt, deren Quadrat 2 ist. Betrachte dazu A = {a element R; a lessequal 2}. Die
2
beiden Losungen von x = 2 ergeben sich als
dieresis
radical radical
2 = sup A, minus 2 = inf A.
28 KAPITEL 2. FOLGEN UND GRENZWERTE Das ist intuitiv plausibel, kann aber auch ganz formal bewiesen werden. Wir betrach-
2
ten hier nur das Supremum und fuhren den Beweis von (sup A) = 2 fur technisch dieresis dieresis
Interessierte formal durch:
Off ensichtlich ist die Menge A beschrankt (sicherlich gilt z.B. A propersubset [minus 3/2, 3/2]). Es ist
dieresis 2
zu zeigen, dass das Supremum (nennen wir es s) in der Tat s = 2 erfullt:
dieresis
Sicherlich gilt s > 0, also speziell 2 + s > 0.
2
Angenommen, es gilt s < 2. Dann kann s keine obere Schranke von A sein, denn
z.B. die Zahl 2 2 2
2 minus s 2 periodcentered s + s + 2 minus s 2 + 2 periodcentered s
a = s + = =
2 + s 2 + s 2 + s
bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright
>0
ware echt großer als s und liegt in A, denn es gilt
dieresis dieresis
2 2 2
4 + 8 periodcentered s + 4 periodcentered s (8 + 8 periodcentered s + 2 periodcentered s ) minus 2 periodcentered (2 minus s )
2a = =
2 2
(2 + s) (2 + s)
2 2 2
2 periodcentered (2 + s) minus 2 periodcentered (2 minus s ) 2 minus s
= = 2minus 2 periodcentered < 2.
2 2
(2 + s) (2 + s)
bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright
>0
Widerspruch! 2
Angenommen, es gilt s > 2. Dann kann s nicht die kleinste obere Schranke von A
sein, denn z. B. die Zahl
2 2 2
2 minus s 2 periodcentered s + s + 2 minus s 2 + 2 periodcentered s
M = s + = =
2 + s 2 + s 2 + s
bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright
<0
ist kleiner als s und ist obere Schranke von A, denn wegen
2 2 2
4 + 8 periodcentered s + 4 periodcentered s (8 + 8 periodcentered s + 2 periodcentered s ) + 2 periodcentered (s minus 2)
2
M = =
2 2
(2 + s) (2 + s)
2 2 2
2 periodcentered (2 + s) + 2 periodcentered (s minus 2) s minus 2
= = 2+ 2 periodcentered > 2
2 2
(2 + s) (2 + s)
bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright
>0
gilt: 2 2 2
a element A arrowdblboth a lessequal 2 arrowdblright a < M arrowdblright a < M.
(Im letzten Schritt wird ausgenutzt, dass wir bereits wissen, dass M = (2+2periodcentered s)/(2+s) >
0 gilt, da sicherlich s > 0 gilt.) Widerspruch!
2
Also muss s = 2 gelten.
Q.E.D.
dieresis
2.2. WEITERE KONVERGENZSATZE 29
2.2.2 Konvergenz monotoner reeller Folgen
Die folgende Aussage ist außerst hilfreich, denn sie gerantiert Konvergenz, ohdieresis ne dass der konkrete Grenzwert bekannt zu sein braucht. Die Aussage beruht auf Monotonie und ist daher nur auf reelle Folgen anwendbar. Die Konvergenz
basiert auf dem Supremumsaxiom 2.25 fur R.
dieresis
Satz 2.28: (Konvergenz monotoner Folgen)
Sei (x ) eine monoton steigende bzw. fallende reelle Folge. Ist die Folge
n
nach oben bzw. unten beschrankt, also x lessequal M bzw. m lessequal x fur alle
dieresis dieresis
n n
Indizes n, so ist (x ) konvergent. Es gilt
n
lim x = sup {x ; n element N} lessequal M bzw. m lessequal lim x = inf {x ; n element N}.
n n n n
narrowright infinity narrowright infinity
Beweis: Betrachte eine monoton steigende und durch M nach oben beschrankte dieresis
asteriskmath
Folge (x ). Setze A = {x ; n element N}. Der gesuchte Grenzwert ist x = sup A. n n asteriskmath asteriskmath
Zum Beweis der Konvergenz gegen x sei epsilon1 > 0 beliebig vorgegeben. Da x
asteriskmath
die kleinste obere Schranke von A ist, ist x minus epsilon1 keine obere Schranke, d.h., es
asteriskmath
existiert ein Index N(epsilon1 ) mit x > x minus epsilon1 . Wegen der Monotonie gilt fur alle dieresis
N(epsilon1 )
Indizes n greaterequal N(epsilon1 ):
asteriskmath asteriskmath asteriskmath asteriskmath
x greaterequal x greaterequal x greaterequal x minus epsilon1 arrowdblright 0 lessequal x minus x lessequal epsilon1 arrowdblright |x minus x | lessequal epsilon1 .
n n n
N(epsilon1 )
asteriskmath
Da x die kleinste obere Schranke von A ist, gilt fur die obere Schranke M die dieresis
asteriskmath
Ungleichung x lessequal M .
Die Konvergenz monoton fallender, nach unten beschrankter Folgen ist analog dieresis
zu beweisen.
Q.E.D.
Beispiel 2.29: Betrachte
nsummationdisplay 1 1 1 1
x = = 1 + + + periodcentered periodcentered periodcentered + .
n k! 1! 2! n!
k=0
Off ensichtlich ist (x ) monoton steigend und nach oben beschrankt:
dieresis
n
nminus 1 1
summationdisplay 1 minus
1 1 1 1 1 n2
x = 1 + + + + periodcentered periodcentered periodcentered + lessequal 1 + = 1 + lessequal 3.
n 1
k
1! 2! 3! n! 2 1 minus 2
bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright k=0
1 1 1 1
= = < <
0 1 2 nminus 1
2 2 2 2
Die Folge konvergiert gegen einen Grenzwert lessequal 3 (es ist die Eulersche Zahl 2.71828...).
30 KAPITEL 2. FOLGEN UND GRENZWERTE
2.2.3 Cauchyendash Folgen und der Banachsche Fixpunktsatz
Wir betrachten einige Aussagen, die sowohl in R als auch allgemeiner in C gelten. Zunachst wird der Zusammenhang zwischen reeller und komplexer Kondieresis
vergenz von Folgen durch den folgenden Satz aufgedeckt:
Satz 2.30: (Komplexe und reelle Konvergenz)
Sei z = x + i periodcentered y element C mit x , y element R. Die Folge (z ) konvergiert dann
n n n n n n
asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath
und genau dann gegen z = x + i periodcentered y (x , y element R), wenn Real- und
asteriskmath asteriskmath
Imaginarteil einzeln konvergieren: lim x = x , lim y = y .
dieresis n n
narrowright infinity narrowright infinity
asteriskmath 2 asteriskmath 2 asteriskmath 2
Beweis: Es gilt |z minus z | = (x minus x ) + (y minus y ) .
n n n
asteriskmath asteriskmath asteriskmath 2
Gilt (x ) arrowright x und gleichzeitig (y ) arrowright y , so ist |z minus z | eine Nullfolge, also n n n
asteriskmath asteriskmath
auch |z minus z |. Dies ist per Definition die Konvergenz (z ) arrowright z .
n n
asteriskmath
Umgekehrt, es gelte (z ) arrowright z . Mit
n
asteriskmath asteriskmath asteriskmath asteriskmath
0 lessequal |x minus x | lessequal |z minus z |, 0 lessequal |y minus y | lessequal |z minus z |
n n n n
asteriskmath asteriskmath
folgt mit Satz 2.17 unmittelbar, dass |x minus x | und |y minus y | Nullfolgen sein n nasteriskmath asteriskmath
mussen. Dies ist per Definition die Konvergenz (x ) arrowright x , (y ) arrowright y .
dieresis n n
Q.E.D.
10.5.02arrowdown
Die Definition der Konvergenz 2.5 benotigt die Kenntnis des Grenzwerts. Der dieresis folgende Satz 2.31 ist eine Existenzaussage, mit der auch ohne Kenntnis des konkreten Grenzwerts die Konvergenz abgelesen werden kann. Zunachst die entdieresis
scheidende Begriff sbildung:
Definition 2.31: (Cauchyendash Folgen)
Eine Folge (z ) in C heißt Cauchyendash Folge", wenn zu jedem epsilon1 > 0 eine
n quotedblright
reelle Zahl N(epsilon1 ) existiert, so dass fur alle n, m greaterequal N(epsilon1 ) gilt: |z minus z | lessequal epsilon1 .
dieresis n m
Satz 2.32: (Die konvergenten Folgen sind die Cauchyendash Folgen)
Eine Folge in C konvergiert dann und genau dann, wenn sie eine Cauchyendash
Folge ist.
Der Beweis ist technisch und bringt keine wirklichen Erkenntnisse. Er ist nur
der Vollstandigkeit halber angegeben:
dieresis
Beweis: Wir betrachten zunachst Folgen (x ) in R.
dieresis n asteriskmath
Konvergenz arrowdblright Cauchyendash Folge: Ist (x ) konvergent mit Grenzwert x , so gibt
n
es zu epsilon1 > 0 ein N(epsilon1 ), so dass
asteriskmath asteriskmath
|x minus x | lessequal epsilon1 , |x minus x | lessequal epsilon1
n m
dieresis
2.2. WEITERE KONVERGENZSATZE 31
gilt fur alle n, m greaterequal N(epsilon1 ). Fur alle n, m greaterequal N(epsilon1 /2) folgt
dieresis dieresis
epsilon1 epsilon1
asteriskmath asteriskmath asteriskmath asteriskmath
|x minus x | = |x minus x + x minus x | lessequal |x minus x | + |x minus x | lessequal + = epsilon1 ,
n m n m n m 2 2
d.h., (x ) ist eine Cauchyendash Folge.
n
Cauchyendash Folge arrowdblright Konvergenz: Sei (x ) eine Cauchyendash Folge mit |x minus x | lessequal epsilon1
n n m
fur alle n, m greaterequal N (epsilon1 ). Hieraus folgt, dass die Menge A = {x ; m greaterequal n} fur jedes dieresis dieresis
x n m
n beschrankt ist:
dieresis
braceleftBigg lessequal |x | + |x minus x |,
n m n
|x | = |x minus x + x |
m m n n greaterequal |x | minus |x minus x |,
n m n
wobei z.B. |x minus x | lessequal 1 fur m, n greaterequal N (1) gilt. Man kann also definieren:
dieresis
m n x
a := inf {x ; m greaterequal n}, b := sup {x ; m greaterequal n}.
n m n m
Off ensichtlich gilt a lessequal x lessequal b . Die Folge b ist monoton fallend, da die
n n n n
Suprema immer kleinerer Mengen betrachtet werden. Analog ist die Folge an monoton wachsend. Nach Satz 2.28 konvergieren damit (a ) und (b ) gegen
n n
asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath
gewisse Grenzwerte a und b mit a lessequal b . Wir zeigen, dass a = b gilt.
asteriskmath asteriskmath asteriskmath asteriskmath
Angenommen, es gilt a < b . Betrachte epsilon1 = (b minus a )/4 > 0. Wahle ein n greaterequal dieresis N (epsilon1 ). Da a als Infimum die großte untere Schranke von A ist, ist a +epsilon1 keine dieresis
x n n n
untere Schranke von A mehr: es gibt ein m greaterequal n, so dass x < a + epsilon1 . Anlog
n 1 m n
1
gibt es ein m greaterequal n, so dass x > b minus epsilon1 . Wegen der Monotonie von (a ) und
2 m n n
2
asteriskmath asteriskmath
(b ) gilt a lessequal a und b greaterequal b , also:
n n n
asteriskmath asteriskmath
b minus a greaterequal b minus a = 4 periodcentered epsilon1 .
n n
Damit folgt
x minus x = x minus b + b minus a + a minus x greaterequal minus epsilon1 + 4 periodcentered epsilon1 minus epsilon1 > epsilon1 .
m m m n n n n m
2 1 2 1
bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright
bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright
greaterequal 4periodcentered epsilon1
>minus epsilon1 >minus epsilon1
Hierbei gilt m , m greaterequal n greaterequal N (epsilon1 ). Mit der Cauchyendash Eigenschaft von (x ) mußte dieresis
1 2 x n
fur solche Indizes aber |x minus x | lessequal epsilon1 gelten. Widerspruch!
dieresis m m
2 1
Damit ist gezeigt, dass reelle Folgen (x ) genau dann konvergieren, wenn sie
n
Cauchyendash Folgen sind. Analog zu Satz 2.30 ist leicht gezeigt, dass eine komplexe Folge genau dann eine Cauchyendash Folge ist, wenn die Folgen der Real- und Imaginarteile beide Cauchyendash Folgen sind. Zusammen mit Satz 2.30 ergibt sich damit, dieresis dass auch komplexe Folgen genau dann konvergieren, wenn sie Cauchyendash Folgen
sind.
Q.E.D.
32 KAPITEL 2. FOLGEN UND GRENZWERTE Auch wenn der Begriff Cauchyendash Folgen" sehr technisch ist, ist er fur Anwendieresis
quotedblright dungen sehr interessant. Er taucht (wenngleich nur im Beweis versteckt) beim fur die Praxis sehr wichtigen Banachschen Fixpunktsatz fur kontrahierende Abdieresis dieresis
bildungen auf. Zunachst einige relevante Begriff e:
dieresis
Definition 2.33: (Haufungspunkte von Mengen)
dieresis
asteriskmath
Ein Punkt z element C heißt Haufungspunkt" einer Menge A propersubset C, wenn
dieresis
quotedblright asteriskmath
fur jedes epsilon1 > 0 die sogenannte epsilon1 -Umgebung" von z
dieresis quotedblright
asteriskmath asteriskmath
macron U (z ) = {z element C; |z minus z | lessequal epsilon1 }
epsilon1
asteriskmath
macron
mindestens einen Punkt in A enthalt: U (z ) intersection A negationslash = emptyset .
dieresis epsilon1
asteriskmath
Geometrisch ist die epsilon1 -Umgebung eines Punktes z ein Kreisgebiet mit Mittel-
asteriskmath
punkt z und Radius epsilon1 , wobei in der obigen Definition der Kreisrand
asteriskmath
{z element C; |z minus z | = epsilon1 }
mit zur Umgebung gerechnet wird.
Beispiel 2.34: Off ensichtlich ist jeder Punkt in A ein Haufungspunkt von A (denn
dieresis
dieser Punkt liegt in jeder epsilon1 -Umgebung von sich selbst). Es kann aber auch Punkte außerhalb von A geben, die Haufungspunkte von A sind. In R sind z.B. die Endpunkte
dieresis
von Intervallen stets Haufungspunkte, selbst wenn das Intervall A = (a, b) propersubset R off en
dieresis
ist. Z.B.: off ensichtlich liegt fur epsilon1 > 0 der Punkt x = min((a + b)/2, a + epsilon1 ) sowohl in
dieresis
A = (a, b) als auch in der epsilon1 Umgebung von a. Also ist a ein Haufungspunkt von A.
dieresis
Fur den Banachschen Fixpunktsatz brauchen wir weiterhin die Begriff sbildung dieresis
abgeschlossene Menge". Wir definieren den Begriff off ene Menge" gleich mit
quotedblright quotedblright
(brauchen ihn momentan aber nicht).
Definition 2.35: (abgeschlossene Mengen)
Eine Menge A element C heißt abgeschlossen", wenn jeder ihrer Haufungs-
dieresis
quotedblright
punkte in A liegt. Die Menge heißt off en", wenn ihr Komplement
quotedblright
C \ A = {z element C; z negationslash element A} abgeschlossen ist.
Beispiel 2.36: Abgeschlossene Intervalle [a, b] in R sind abgeschlossene Mengen. Die
hier definierten epsilon1 -Umgebungen
asteriskmath asteriskmath
macron U (z ) = {z element C; |z minus z | lessequal epsilon1 }
epsilon1
sind abgeschlossene Mengen in C .
Achtung: in der Literatur werden als epsilon1 -Umgebungen oft die Mengen
asteriskmath asteriskmath
U (z ) = {z element C; |z minus z | < epsilon1 }
epsilon1
asteriskmath
betrachtet, die den Kreisrand {z element C; |z minus z | = epsilon1 } nicht enthalten. Diese Mengen sind
nicht abgeschlossen, denn die Punkte des Kreisrands sind Haufungspunkte. Die U
dieresis epsilon1
sind off ene Mengen.
dieresis
2.2. WEITERE KONVERGENZSATZE 33
Wir definieren den Begriff einer kontrahierenden Abbildung:
arrowdown entfallt dieresis
Definition 2.37:
Eine Abbildung Phi : A propersubset C arrowright C heißt Kontraktion in A", wenn eine
quotedblright
Kontraktionskonstante" k element [0, 1) existiert, so dass fur alle x, y element A
dieresis
quotedblright gilt:
|Phi (x) minus Phi (y)| lessequal k periodcentered |x minus y|.
Zur Namensgebung: der Abstand zweier Bildpunkte |Phi (x) minus Phi (y)| einer Kon-
traktion ist stets kleiner als der Abstand der Urbildpunkte |x minus y|.
Bemerkung 2.38: Kontraktionen sind automatisch das, was wir spater als arrowdown entfallt dieresis dieresis
stetige Funktionen" einfuhren werden. Fur jede konvergierende Folge (z ) kon-
dieresis dieresis n
quotedblright vergiert Phi (z ), und es gilt
n
parenleftBig parenrightBig
lim Phi (z ) = Phi lim z .
n n
narrowright infinity narrowright infinity
asteriskmath
Dies ist leicht einzusehen. Sei z der Grenzwert von (z ). Die Kontraktionsei-
n
genschaft liefert asteriskmath asteriskmath
0 lessequal |Phi (z ) minus Phi (z )| < |z minus z |.
n n
asteriskmath
Wegen der Konvergenz z arrowright z ist die rechte Seite eine reelle Nullfolge. Mit
n asteriskmath
Satz 2.17 folgt, dass |Phi (z ) minus Phi (z )| eine Nullfolge ist, was die Konvergenz
n
asteriskmath
Phi (z ) arrowright Phi (z ) bedeutet.
n arrowdown entfallt
dieresis
Der folgende wichtige Fixpunktsatz fur kontrahierende Abbildungen geht auf
dieresis
Stefan Banach (polnischer Mathematiker, 1892 endash 1945) zuruck. Er setzt neben
dieresis
der Kontraktionseigenschaft als wichtige Annahme voraus, dass die Kontraktion
ihren Definitionsbereich in sich selbst abbildet:
Satz 2.39: ( BFS": der Banachsche Fixpunktsatz) arrowdown entfallt
dieresis
quotedblright
Sei Phi : A arrowright A eine Kontraktion in einer abgeschlossenen Menge A propersubset C
mit einer Kontraktionskonstanten k < 1 . Dann
asteriskmath asteriskmath
a) existiert ein eindeutig bestimmter Fixpunkt z = Phi (z ) element A,
b) konvergiert jede Folge z = Phi (z ) mit beliebigem Startwert z element A
n+1 n 0
asteriskmath
gegen z ,
c) gelten fur jede solche Folge die Abschatzungen
dieresis dieresis
n
k k
asteriskmath
|z minus z | lessequal periodcentered |z minus z | lessequal periodcentered |z minus z |.
n n nminus 1 1 0
1 minus k 1 minus k
bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright
"a posterioriquotedblright "a prioriquotedblright
34 KAPITEL 2. FOLGEN UND GRENZWERTE Vom (wiederum sehr technischen) Beweis braucht man eigentlich nur zu wissen, dass man zeigen kann, dass die per z = Phi (z ) konstruierten Folgen Cauchyendash
n+1 n
Folgen sind. Der Fixpunkt ergibt sich dann uber den Grenzwert der Folgen, dieresis dessen Existenz mittels Satz 2.32 gesichert ist. Aus der Kontraktionseigenschaft folgt die Eindeutigkeit (alle Folgen konvergieren gegen denselben Grenzwert). Fur technisch Interessierte ist der Beweis der Vollstandigkeit halber angegeben: dieresis dieresis
entfalltarrowdown Beweis: Zeige: (z ) ist Cauchy-Folge.
dieresis n
|z minus z | = |z minus z + z minusplus periodcentered periodcentered periodcentered minus z + z minus z |
n+m n n+m n+mminus 1 n+mminus 1 n+1 n+1 n
lessequal |z minus z | + |z minus z | + periodcentered periodcentered periodcentered + |z minus z |
n+m n+mminus 1 n+mminus 1 n+mminus 2 n+1 n
fur jedes n, m greaterequal 0. Aus |z minus z | = |Phi (z )minus Phi (z )| lessequal k periodcentered |z minus z |, d.h., dieresis j jminus 1 jminus 1 jminus 2 jminus 1 jminus 2
2
|z minus z | lessequal k periodcentered |z minus z | lessequal k periodcentered |z minus z | lessequal . . .
j jminus 1 jminus 1 jminus 2 jminus 2 jminus 3
folgt
mminus 1 mminus 2
|z minus z | lessequal k periodcentered |z minus z | + k periodcentered |z minus z | + periodcentered periodcentered periodcentered + |z minus z |
n+m n n+1 n n+1 n n+1 n
m
1 minus k
2 mminus 1
= (1 + k + k + periodcentered periodcentered periodcentered + k ) periodcentered |z minus z | = periodcentered |z minus z |
n+1 n n+1 n
1 minus k
2 n
(#) (##)
|z minus z | k |z minus z | k |z minus z | k |z minus z |
n+1 n n nminus 1 nminus 1 nminus 2 1 0
lessequal lessequal lessequal lessequal . . . lessequal .
1 minus k 1 minus k 1 minus k 1 minus k
n asteriskmath
Mit k arrowright 0 folgt die Cauchy-Eigenschaft. Es existiert somit ein Grenzwert z .
asteriskmath
Mit z element A und Phi : A arrowright A folgt z element A arrowdblright z ist Haufungspunkt von A arrowdblright dieresis
0 n
asteriskmath z element A (abgeschlossen). Da Phi im Sinne von Bemerkung 2.38 stetig ist:
asteriskmath asteriskmath
z = lim z = lim Phi (z ) = Phi ( lim z ) = Phi (z ) .
n+1 n n
narrowright infinity narrowright infinity
iarrowright infinity
asteriskmath asteriskmath asteriskmath
Eindeutigkeit: fur einen weiteren Fixpunkt z negationslash = z folgt der Widerspruch
dieresis
asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath
|z minus z | = |Phi (z ) minus Phi (z )| lessequal k periodcentered |z minus z | < |z minus z | .
Die Abschatzungen c) ergeben sich aus (#) und (##):
dieresis
n
(#) (##)
k k
asteriskmath
lim |z minus z | = |z minus z | lessequal |z minus z | lessequal |z minus z | .
n+m n n n nminus 1 1 0
marrowright infinity 1minus k 1minus k
Q.E.D.
dieresis
2.2. WEITERE KONVERGENZSATZE 35
Interpretation und Anwendung 2.40:
entfalltarrowdown
dieresis
Eine Gleichung f(z) = 0 sei zu losen. Der BFS gibt ein Rezept, wie man
dieresis
Naherungen fur die Losung konstruieren kann:
dieresis dieresis dieresis
1) Formuliere die Gleichung f(z) = 0 in ein aquivalentes Fixpunktpro-
dieresis
blem z = Phi (z) um.
2) Ist Phi kontrahierend auf einer Umgebung A der Losung und bildet
dieresis
Phi diese Menge A auf sich selbst ab, so laßt sich der BFS anwenden:
dieresis
wahle einen beliebigen Punkt z element A und iteriere z = Phi (z ).
dieresis 0 n+1 n
Diese Folge konvergiert gegen eine Losung des Fixpunktproblems und
dieresis
damit gegen eine Losung des Ausgangsproblems f(z) = 0.
dieresis
3) Hat man durch Abschatzungen eine Kontraktionskonstante k fur die
dieresis dieresis
Menge A gefunden, kann man mit den a-priori- bzw. a-posteriori-
Abschatzungen bestimmen, wie weit man noch von der Losung ent-
dieresis dieresis
fernt ist und abbrechen, sobald eine vorgegebene Zielgenauigkeit er-
reicht ist.
Mit der a-priori-Abschatzung kann man aus dem Startpunkt z und dem
dieresis 0
nachsten Punkt z sofort ermitteln, wie oft man iterieren muß, um die Ziel-
dieresis 1
genauigkeit zu erreichen (die Iterationswerte werden dafur nicht benotigt).
dieresis dieresis
Nachdem die Iteration durchgefuhrt worden ist und Zahlenwerte fur z
dieresis dieresis n
vorliegen, kann man a-posteriori abschatzen, welche Approximationsge-
dieresis
nauigkeit nun wirklich erreicht ist (die a-posteriori-Abschatzung ist prin-
dieresis
zipiell genauer als die a-priori-Abschatzung).
dieresis
Bemerkung 2.41: Es gibt viele Wege, eine gegebene Gleichung f(x) = 0 in arrowdown entfallt
dieresis
eine Fixpunktgleichung x = Phi (x) umzuformen, z.B.
Phi (x) = x minus g(x) periodcentered f(x)
mit einer (praktisch beliebig wahlbaren) Funktion g(x). Ist f(x) diff erenzierbar dieresis und ist die Losung im Sinne von Definition 1.10 eine einfache Nullstelle, so ist dieresis
prime
g(x) = 1/f (x) eine ausgezeichnete Wahl. Die Iteration lautet dann
f(x )n
x = Phi (x ) = x minus (das Newton-Verfahren").
n+1 n n prime quotedblright
f (x )n
Man kann zeigen, dass es immer eine (eventuell kleine) Umgebung A einer Nullstelle von f gibt, auf der Phi eine Kontraktion ist und fur die Phi (A) propersubset A gilt. dieresis Damit gilt der BFS auf einer (leider oft nicht konkret bekannten) Umgebung
einer Losung, und es gilt:
dieresis
asteriskmath
Fur hinreichend genaue Startwerte x dicht bei einer Losung x von
dieresis dieresis
0 prime
f(x) = 0 konvergiert die Newton-Folge x = x minus f(x )/f (x )
n+1 n n n
asteriskmath
gegen x .
36 KAPITEL 2. FOLGEN UND GRENZWERTE Bei einfachen Nullstellen ist die Konvergenz beim Newton-Verfahren sehr schnell, da die Kontraktionskonstanten auf kleinen Umgebungen der Losung dieresis
prinzipiell sehr klein sind.
entfalltarrowdown Beispiel 2.42: In einer Softwareumgebung gebe es die Grundarithmetik, aber keine dieresis 2
Wurzelfunktion. Um diese zu implementieren, soll die Gleichung y = b fur gegebenes
dieresis
positives b element R nach y gelost werden. Mittels Division durch eine geeignete 4er-Potenz
dieresis
kann b auf das Interval [1, 4] transformiert werden (in Binardarstellung kostet dies
dieresis
n 2 n
nichts). Sei nun a = b/4 element [1, 4]. Ist x element [1, 2] eine Losung von x = a, so ist y = 2 periodcentered x dieresis
2
die gesuchte Losung des Ausgangsproblems y = b.
dieresis
Das verbleibende Problem ist also, ein x element [1, 2] zu finden, das das Nullstellenproblem
2
f(x) = x minus a = 0 mit a element [1, 4] erfullt. Hierzu soll das Newtonendash Verfahren benutzt dieresis
werden. Betrachte also
parenleftBig parenrightBig
2 2
f(x) x minus a x + a 1 a
Phi (x) = x minus = x minus = = periodcentered x + .
prime f (x) 2 periodcentered x 2 periodcentered x 2 x
Die entsprechende Iteration lautet also
parenleftBig parenrightBig
1 a
x = periodcentered x + .
n+1 n
2 xn
radical
asteriskmath
Das Verfahren konvergiert sehr schnell gegen x = a. Beispiel: a = 2, x = 1.5:
0
x = 1.5, x = 1.416666666..., x = 1.414215686...,
0 1 2
x = 1.414213562..., x = 1.414213562..., . . .
3 4
Die folgende Analyse ist wiederum sehr technisch und an technisch Interessierte
addressiert:
radical radical
1+a
Analyse: betrachte das Intervall A = [ a, ], das die Losung a enthalt. (Dieses dieresis dieresis
2
Intervall fallt hier vom Himmel.) Die folgenden Rechnungen zeigen, dass dieses Intervall
dieresis
in der Tat so ist, dass der BFS angewendet werden kann.
Es ist zunachst zu zeigen, dass Phi (A) propersubset A gilt. In Erinnerung an die Schule berechnen
dieresis
wir dazu parenleftBig parenrightBig 2
1 a x minus a
prime Phi (x) = periodcentered 1 minus = greaterequal 0
2 2
2 x 2 periodcentered x
radical 1+a
fur x element [ a, ]. Die Funktion ist also in diesem Bereich monoton steigend, und damit
dieresis 2
gilt parenleftBig parenrightBig
radical radical 1 + a 1 + a a 1 + a
Phi ( a) = a lessequal Phi (x) lessequal Phi = + lessequal
2 4 1 + a 2
radical 1+a
fur alle x element [ a, ]. Als Kontraktionskonstante auf A schatzt man ab:
dieresis dieresis
2
vextendsingle vextendsingle vextendsingle vextendsingle
1 a a 1 a periodcentered (x minus y)
vextendsingle vextendsingle vextendsingle vextendsingle
|Phi (x) minus Phi (y)| = periodcentered x + minus y minus = periodcentered x minus y minus
vextendsingle vextendsingle vextendsingle vextendsingle
2 x y 2 x periodcentered y
dieresis
2.2. WEITERE KONVERGENZSATZE 37
vextendsingle vextendsingle parenleftBig parenrightBig parenleftBig parenrightBig
|x minus y| a |x minus y| a |x minus y| a
vextendsingle vextendsingle
= periodcentered 1 minus = periodcentered 1 minus lessequal periodcentered 1 minus
vextendsingle vextendsingle a+1 2
2 x periodcentered y 2 x periodcentered y 2 ( )
2
parenleftBig parenrightBig 2
1 a minus 1
= |x minus y| periodcentered periodcentered .
2 a + 1
Also, in Abhangigkeit von a ist
dieresis
parenleftBig parenrightBig 2
1 a minus 1
k = periodcentered
2 a + 1
eine Kontraktionskonstante fur Phi uber A. Fur alle a element [1, 4] gilt k lessequal 0.18, d.h., Phi ist
dieresis dieresis dieresis
auf A in der Tat eine Kontraktion.
Speziell, fur a = 2 ist k = 1/18 approxequal 0.0555 . . . . Starten wir mit x = 3/2, so ergibt sich
dieresis 0
x = 17/12 und die a-priori-Abschatzung liefert
dieresis
1
n
radical k 3
|x minus 2| lessequal periodcentered |x minus x | = .
n 0 1 n
1 minus k 34 periodcentered 18
Nach n = 5 Schritten ergibt sich beispielsweise
radical minus 8
|x minus 2| lessequal 4.7 periodcentered 10 ,
5
radical
d.h., x beschreibt garantiert die ersten 7 bis 8 Dezimalstellen von 2 korrekt. (In
5
Wirklichkeit ist x schon wesentlich genauer, aber mehr gibt die a-priori-Abschatzung
dieresis
5
nicht her.)
Bemerkung 2.43: Das letzte Beispiel hat gezeigt, dass das Abschatzen von arrowdown entfallt
dieresis dieresis
Kontraktionskonstanten muhselig ist. Es geht aber auch einfacher! Fur stetig
dieresis dieresis
diff erenzierbares Phi gilt, dass
prime
k = sup {|Phi (x)|; x element A}
die bestmogliche (weil kleinste) Kontraktionskonstante uber einem Intervall
dieresis dieresis
A propersubset R ist. Um dies einzusehen, brauchen wir aber den Mittelwertsatz der
Diff erentialrechnung, der erst spater bereitgestellt wird.
dieresis
2.2.4 Teilfolgen und Haufungspunkte
dieresis arrowdown ab hier
Neben der Konvergenz gibt es den (schwacheren) Begriff von Teilkonvergenz",
dieresis quotedblright arrowdown wieder
der sich in sogenannten Haufungspunkten von Folgen" (im Unterschied zum
dieresis
quotedblright
schon eingefuhrten Begriff Haufungspunkte von Mengen") manifestiert.
dieresis dieresis arrowdown behandelt
quotedblright
Definition 2.44: (Haufungspunkte von Folgen)
dieresis
asteriskmath
Ein Punkt z element C heißt Haufungspunkt" der Folge (z ), wenn in jeder
dieresis n
quotedblright
asteriskmath
epsilon1 -Umgebung von z unendlich viele Folgenglieder liegen, also: zu jedem
asteriskmath
epsilon1 > 0 existieren unendlich viele Folgenglieder z mit |z minus z | lessequal epsilon1 .
n n
38 KAPITEL 2. FOLGEN UND GRENZWERTE
n
Beispiel 2.45: Die Folge x = (minus 1) , also (x ) = (minus 1, 1, minus 1, 1, . . .) hat die beiden n n
asteriskmath asteriskmath
Haufungspunkte x = 1 und x = minus 1.
dieresis 1 2
asteriskmath
Der Punkt x = 1 ist Haufungspunkt, denn fur alle Folgenglieder mit geradem Index n dieresis dieresis
1 asteriskmath
(dies sind unendlich viele) gilt |x minus x | = 0 lessequal epsilon1 fur jedes epsilon1 > 0.
dieresis
n 1
asteriskmath
Der Punkt x = minus 1 ist Haufungspunkt, denn fur alle Folgenglieder mit ungeradem dieresis dieresis
2 asteriskmath
Index n (dies sind unendlich viele) gilt |x minus x | = 0 lessequal epsilon1 fur jedes epsilon1 > 0.
dieresis
n 2
Bemerkung 2.46: Sei n < n < . . . eine streng monoton steigende Folge von
1 2
Indizes in N. Die Folge (z ) = (z , z , . . .) heißt Teilfolge" der Folge (z ).
n n n n
1 2
i quotedblright
asteriskmath z ist genau dann Haufungspunkt der Folge (z ), wenn
dieresis n
asteriskmath
es eine gegen z konvergierende Teilfolge von (z ) gibt.
n
asteriskmath
Zu einem gegebenen Haufungspunkt z folgt eine explizite Konstruktion einer dieresis konvergenten Teilfolge. Zu epsilon1 = 1/k gibt es unendlich viele Folgenglieder z mit
n
asteriskmath
|z minus z | lessequal 1/k. Wahle n als den ersten Folgenindex, fur den der Abstand dieresis dieresis
n i
zwischen z und dem Haufungspunkt den Wert 1/k unterschreitet:
dieresis
n
braceleftbigg bracerightbigg
1
asteriskmath
n := min n;n > n ; |z minus z | lessequal (n := 0).
n 0
k kminus 1 k
1
asteriskmath
Nach Konstruktion gilt |z minus z | lessequal fur alle k = 1, 2, . . . und damit auch dieresis
nk k
1 1
asteriskmath asteriskmath
|z minus z | lessequal lessequal fur alle n greaterequal n . Damit konvergiert (z ) gegen z .
dieresis
n j n
k
j k
j k
asteriskmath
Umgekehrt, gibt es eine gegen z konvergente Teilfolge von (z ), so liegen in n
asteriskmath
jeder epsilon1 -Umgebung von z alle bis auf endliche viele Glieder der Teilfolge. Also
asteriskmath
ist z ein Haufungspunkt von (z ).
dieresis n
Beispiel 2.47: Fur die Folge (x ) = (minus 1, 1, minus 1, 1, . . .) aus Beispiel 2.45 konvergiert
dieresis n
die Teilfolge (x , x , . . .) = (1, 1, 1, . . .) gegeben den Haufungspunkt 1 und die Teilfolge dieresis
2 4
(x , x , . . .) = (minus 1, minus 1, minus 1, . . .) gegeben den Haufungspunkt minus 1.
dieresis
1 3
Satz 2.48:
Eine konvergente Folge besitzt genau einen Haufungspunkt: den Grenz-
dieresis
wert.
asteriskmath
Beweis: Fur den Grenzwert z einer konvergierenden Folge (z ) gibt es fur dieresis dieresis
n
jedes epsilon1 > 0 ein N(epsilon1 ), so dass alle Folgenglieder mit Indizes greaterequal N(epsilon1 ) in der epsilon1 -
asteriskmath
Umgebung von z liegen. Damit ist der Grenzwert ein Haufungspunkt. Gabe dieresis dieresis
asteriskmath asteriskmath
es einen weiteren davon verschiedenen Haufungspunkt z , gabe es fur epsilon1 = dieresis dieresis dieresis
asteriskmath asteriskmath asteriskmath
|z minus z |/3 > 0 mindestens einen Folgenpunkt z mit Index n greaterequal N(epsilon1 ) in dieser n
2.3. UNENDLICHES, UNEIGENTLICHE KONVERGENZ 39
asteriskmath asteriskmath
epsilon1 -Umgebung von z , und es wurde folgen:
dieresis
asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath asteriskmath
3 periodcentered epsilon1 = |z minus z | = |z minus z + z minus z | lessequal |z minus z | + |z minus z | lessequal 2 periodcentered epsilon1 .
n n n n
Widerspruch!
Q.E.D.
Satz 2.49: (Bolzano (1781endash 1848) und Weierstrass (1815endash 1897))
Eine Folge heißt beschrankt, wenn die Menge aller Folgenpunkte be-
dieresis
schrankt ist. Es gilt: Jede beschrankte Folge besitzt mindestens einen
dieresis dieresis
Haufungspunkt.
dieresis
Wir verzichten auf die strenge technische Durchfuhrung des Beweises und
dieresis
geben nur die Idee an:
Beweisidee: Die Folge liege innerhalb eines Quadrates in der komplexen Ebene. Zerlege dieses Quadrat in 4 gleichgrosse Teilquadrate der halben Seitenlange. dieresis Mindestens eines der Teilquadrate enthalt unendliche viele der Folgenglieder. dieresis Wahle eines dieser Teilquadrate aus und zerlege es wiederum in 4 Teilquadradieresis te usw. Die so konstruierte Folge von Quadraten schrumpft auf einen Punkt zusammen (dies ist der Haufungspunkt), in dessen Nahe nach Konstruktion undieresis dieresis
endlich viele der Folgenpunkte existieren.
Q.E.D.
Bemerkung 2.50: Nach Bemerkung 2.46 heißt dies:
Jede beschrankte Folge besitzt eine konvergente Teilfolge.
dieresis
2.3 Unendliches, uneigentliche Konvergenz
In diesem Abschnitt geht es um eine oft nutzliche Schreibweise, die in der hier dieresis vorgestellten Form nur bei reellen Folgen sinnvoll ist. Die unendlichen Werte"
quotedblright plusminus infinity sind keine reellen Zahlen, sondern dienen nur als nutzliche Abkurzungen, dieresis dieresis
um gewisse Situationen zu beschreiben. Wir lassen plusminus infinity als ( uneigentliche")
quotedblright
Grenzwerte reeller Folgen zu:
Definition 2.51: (plusminus infinity als Grenzwert)
* Eine reelle Folge (x ) konvergiert (uneigentlich) gegen infinity ",
n quotedblright
wenn die Folgenglieder jede beliebig vorgegebene Schranke c > 0
uberschreiten: zu jedem reellen c existiert eine reelle Zahl N(c), so
dieresis
dass x greaterequal c gilt fur alle Indizes n greaterequal N(c). Schreibweise:
dieresis
n
lim x = infinity .
n
narrowright infinity
40 KAPITEL 2. FOLGEN UND GRENZWERTE
* Eine reelle Folge (x ) konvergiert (uneigentlich) gegen minus infinity ",
n quotedblright
wenn die Folgenglieder jede beliebig vorgegebene Schranke c < 0 unterschreiten: zu jedem reellen c existiert eine reelle Zahl N(c), so
dass x lessequal c gilt fur alle Indizes n greaterequal N(c). Schreibweise:
dieresis
n
lim x = minus infinity .
n
narrowright infinity
radical
2 n
Beispiel 2.52: Die Folgen x = n, x = n , x = n, x = 2 konvergieren gegen infinity .
n n n n
radical
2 n
Die Folgen x = minus n, x = minus n , x = minus n, x = minus (2 ) konvergieren gegen minus infinity .
n n n n
n
Beispiel 2.53: Achtung: die Folgen x = (minus 1) periodcentered n (also (minus 1, 2, minus 3, 4, minus 5, . . .)) oder
n
n
auch x = (minus 2) (also (minus 2, 4, minus 8, 16, minus 32, . . .)) konvergieren nicht gegen infinity oder minus infinity ,
n
sie divergieren!
Man darf getrost mit infinity und minus infinity rechnen, wobei folgende Rechenregeln gelten:
Rechenregeln fur plusminus infinity 2.54:
dieresis
entfalltarrowdown
dieresis
Sei c eine reelle Zahl.
* c plusminus infinity = plusminus infinity ,
* c periodcentered (plusminus infinity ) = plusminus sign(c) periodcentered infinity fur c negationslash = 0. Hierbei ist sign(c) das Vorzeichen
dieresis
von c.
1
* = 0,
plusminus infinity
* infinity + infinity = infinity , minus infinity minus infinity = minus infinity ,
* infinity periodcentered infinity = (minus infinity ) periodcentered (minus infinity ) = infinity , infinity periodcentered (minus infinity ) = (minus infinity ) periodcentered infinity = minus infinity ,
infinity minus infinity
* infinity = infinity , infinity = 0,
infinity infinity
* c = infinity fur c > 1, c = 0 fur 0 < c < 1,
dieresis dieresis
minus infinity minus infinity
* c = 0 fur c > 1, c = infinity fur 0 < c < 1.
dieresis dieresis
3
entfalltarrowdown Beispiel 2.55: Die Folge x = n + n konvergiert gegen infinity :
dieresis n
3 3
lim (n + n) = lim n + lim n = infinity + infinity = infinity .
narrowright infinity narrowright infinity narrowright infinity
Aus dem obigen Ergebnis folgt sofort das nachste Ergebnis:
dieresis
1
entfalltarrowdown Beispiel 2.56: Die Folge x = konvergiert gegen 0:
dieresis n 3n +n
1 1 1
lim = = = 0.
3
3
narrowright infinity n + n infinity
lim (n + n)
narrowright infinity
2.4. WACHSTUM VON FOLGEN, LANDAU-SYMBOLE 41 Beim Rechnen mit plusminus infinity muß man aber etwas Vorsicht walten lassen. Wenn man auf eine der folgenden Situationen stoßt, darf man nicht weiterrechnen, sondern dieresis
muß die betrachteten Grenzwerte anders ermitteln:
Undefinierte Ergebnisse beim Rechnen mit plusminus infinity 2.57: arrowdown entfallt
dieresis
* 0 periodcentered (plusminus infinity ) = undefiniert",
quotedblright
* infinity minus infinity = undefiniert", minus infinity + infinity = undefiniert",
quotedblright quotedblright
infinity
* c = undefiniert" fur c lessequal 0 und c = 1,
dieresis
quotedblright
minus infinity
* c = undefiniert" fur c lessequal 0 und c = 1,
dieresis
quotedblright
1
* = undefiniert".
0 quotedblright
3
Beispiel 2.58: Betrachte die Folge x = n minus n: arrowdown entfallt
dieresis
n
(??) (??) (??)
3 3
lim (n minus n) = lim n minus lim n = infinity minus infinity = undefiniert".
quotedblright
narrowright infinity narrowright infinity narrowright infinity
Dies heißt nicht, dass kein Grenzwert existiert, sondern nur, dass wir den Grenzwert uber die Rechenregeln mit plusminus infinity nicht berechnen konnen. Man muß in einem solchen
dieresis dieresis
Fall genauer untersuchen. Z.B funktioniert folgendes Argument:
parenleftBig parenrightBig parenleftBig parenrightBig
1 1
3 3 3
lim (n minus n) = lim n periodcentered 1 minus = lim n periodcentered lim 1 minus
2 2
narrowright infinity narrowright infinity narrowright infinity narrowright infinity
n n
parenleftBig parenrightBig parenleftBig parenrightBig
1 1
= infinity periodcentered 1 minus = infinity periodcentered 1 minus = infinity periodcentered (1 minus 0) = infinity .
2 infinity
lim n
narrowright infinity
Ein weiteres solches Beispiel:
3
2periodcentered n +n
Beispiel 2.59: Betrachte die Folge x = : arrowdown entfallt
dieresis
n 4n +1
3
lim (2 periodcentered n + n)
3
2 periodcentered n + n infinity
(??) (??) (??)
narrowright infinity
lim = = = undefiniert".
4
4 quotedblright
narrowright infinity n + 1 infinity
lim (n + 1)
narrowright infinity
Dies sagt wiederum gar nichts daruber aus, ob ein Grenzwert existiert oder nicht. In
dieresis
diesem Fall fuhrt wieder ein wenig Manipulation zum Erfolg:
dieresis
parenleftBig parenrightBig
1
3 1
3 n periodcentered 2 + 2 2 +
n
2 periodcentered n + n 2n
parenleftBig parenrightBig parenleftBig parenrightBig
lim = lim = lim
4
narrowright infinity narrowright infinity narrowright infinity
1 1
n + 1 4n periodcentered 1 + n periodcentered 1 +
4 4
n n
1
2 + 2
infinity
parenleftBig parenrightBig
= = = 0.
1 infinity
infinity periodcentered 1 + infinity
42 KAPITEL 2. FOLGEN UND GRENZWERTE
2.4 Wachstum von Folgen, Landau-Symbole
arrowdown 16.5.02 Algorithmen werden typischerweise auf Problemklassen angewendet, die einen arrowdown ab hier
Großenparameter" n haben: Invertierung von n multiply n Matrizen, Sortieren ei-
dieresis
quotedblright ner Liste mit n Elementen, Untersuchungen auf Graphen mit n Knoten usw. arrowdown wieder
Die Laufzeit des Algorithmus wachst mit der durch n gegebenen Große des
dieresis dieresis
arrowdown behandelt
Problems, und man mochte oft eine einfach zu lesende Kostenabschatzung in
dieresis dieresis
Abhangigkeit von n angeben. Hierzu dienen die sogenannten Landau-Symbole"
dieresis quotedblright
O ( Big-Oh"), o ( Small-Oh") etc.:
quotedblright quotedblright
Notation 2.60:
Seien (f ), (g ) Folgen komplexer Zahlen.
n n
* f = O(g ) heißt, dass die Folge |f |/|g | nach oben beschrankt ist.
dieresis
n n n n
* f = o(g ) heißt, dass die Folge f /g eine Nullfolge ist.
n n n n
* f = Omega (g ) heißt, dass die Folge |g |/|f | nach oben beschrankt ist.
dieresis
n n n n
* f = omega (g ) heißt, dass die Folge g /f eine Nullfolge ist.
n n n n
* f = Theta (g ) heißt, dass die Folgen |f /g | und |g /f | nach oben
n n n n n n
beschrankt sind: es existieren positive Konstanten c und C, so dass
dieresis
c periodcentered |g | lessequal |f | lessequal C periodcentered |g | gilt fur alle hinreichend großen n.
dieresis
n n n
Hierbei nimmt man implizit an, dass man sich fur große Werte von n interessiert.
dieresis
Eigentlich sollte man genauer sagen: f = O(g ) im Limes n arrowright infinity " etc.
n n quotedblright
2 2 2 3 2 4 2 n
Beispiel 2.61: n + 1 = O(n ), n + 1 = O(n ), n + 1 = O(n ), n + 1 = O(2 ),
parenleftBig parenrightBig parenleftBig parenrightBig parenleftBig parenrightBig
1 1 1 1 1 1
2 3 2 n
radical radical
= O , = O , n = o(n ), n = o(2 ), = o ,
n + 1 n n + 1 n n+ 1 n
3 n 3
n 2 n
2 3 2 3
2periodcentered n+1 = Omega (n), 2periodcentered n +1 = omega (n), = Omega (n ), = omega (n ), 2periodcentered n+1 = Theta (n), = Theta (n ).
2 7 2
Beispiel 2.62: Man kann n lineare Gleichungen fur n Unbekannte numerisch stets mit
dieresis
3
hochstens etwa n /3 Multiplikationen losen. Also:
dieresis dieresis
3
Die Kosten der Losung eines linearen n multiply n Systems ist O(n )."
dieresis
quotedblright
Ist die Koeffi zientenmatrix eine obere oder untere Dreiecksmatrix, kommt man mit
2 2
hochstens n /2 Multiplikationen aus. Die Kosten sind in diesem Fall O(n ).
dieresis
Die Kosten, alle Eigenwerte und -vektoren einer nmultiply n-Matrix numerisch zu bestimmen,
3
sind O(n ).
Das Sortieren einer Liste mit n Elementen kostet O(n periodcentered log (n)) Vergleichsoperationen.
2
(Genauer: es existieren Sortieralgorithmen, die mit diesem Aufwand auskommen).