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:

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

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

Anschaulich: alle Werte z weichen fur n greaterequal N(epsilon1 ) maximal um den Wert
dieresis

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

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

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

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

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:

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]

limit(c , n = infinity)

Nehmen wir an, c sei reell und 0 < c < 1:

>> assume(0 < c < 1):

>> limit(x(n), n = infinity)

Nehmen wir an, c > 1:

>> assume(c > 1):

>> limit(x(n), n = infinity)

infinity

Ein Beispiel einer nicht konvergierenden Folge:

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

einmal ein sauberer Nichtexistenzbeweis vorkommt): zu epsilon1 = laßt sich kein N(epsilon1 ) finden. dieresis

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

bracehtipupleft bracehtipdownright bracehtipdownleft bracehtipupright 2 2

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,

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,

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:

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
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

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

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.

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

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

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

Exponential-Funktion". Der spezielle Grenzwert e = e fur z = 1
dieresis

quotedblright heißt Eulersche Zahl":

quotedblright parenleftBig parenrightBig n

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

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:

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

|z | lessequal gilt). Dann gilt
n 2n

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 periodcentered |z | periodcentered (1 + |z |) .
n n

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

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 .

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

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 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

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

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-

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

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

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

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

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

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

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

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

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

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

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

k k

asteriskmath

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

folgt

mminus 1 mminus 2

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
(#) (##)

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

Die Abschatzungen c) ergeben sich aus (#) und (##):
dieresis

n
(#) (##)
k k
asteriskmath

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

die gesuchte Losung des Ausgangsproblems y = b.
dieresis

Das verbleibende Problem ist also, ein x element [1, 2] zu finden, das das Nullstellenproblem

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

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

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

= 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

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

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

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

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

braceleftbigg bracerightbigg

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

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

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

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

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

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

Beispiel 2.53: Achtung: die Folgen x = (minus 1) periodcentered n (also (minus 1, 2, minus 3, 4, minus 5, . . .)) oder
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.

* = 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

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

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

* = undefiniert".
0 quotedblright

Beispiel 2.58: Betrachte die Folge x = n minus n: arrowdown entfallt
dieresis

(??) (??) (??)
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:

2periodcentered n +n

Beispiel 2.59: Betrachte die Folge x = : arrowdown entfallt
dieresis

n 4n +1

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

narrowright infinity narrowright infinity narrowright infinity
1 1
n + 1 4n periodcentered 1 + n periodcentered 1 +

4 4
n n

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

hochstens etwa n /3 Multiplikationen losen. Also:
dieresis dieresis

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).