Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen, 2-0
Continu¨ıteit en Limieten
Functies, Rijen, Continu¨ıteit
en Limieten
Inhoud
2.1.1 Functies: Definities en kenmerken
f van de verzameling A naar de
verzameling B is een voorschrift dat aan elk element
x van ; A juist e´ en
´ element y van B toevoegt. We
noteren y = f (x) en
Een functie
1. Functies
f : A → B : x 7→ f (x).
• Definitie en kenmerken / bewerkingen op functies
• Reele
¨ functies van e´ en
´ reele
¨ veranderlijke
• A is het domein of definitiegebied van f : A = domf .
2. Rijen
• Bij elke x ∈ domf hoort precies e´ en
´ element y =
f (x) ∈ B.
• Definitie en voorbeelden / kenmerken van rijen
• Rekenregels voor limieten
• Deelrijen en het O-symbool
• f (x) is het beeld van x onder f , of ook wel de
waarde van f in x.
3. Continu¨ıteit
• De verzameling van alle beelden
4. Limieten
bldf
= f (A) = {y ∈ B | ∃x ∈ A : y = f (x)}
is het bereik of beeld van f .
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen, 2-2
Continu¨ıteit en Limieten
• Notatie:
f : A → B : x 7→ f (x)
x ∈ A is onafhankelijke veranderlijke of ar-
gument
-
f
A
output
-
f (x)
Opm.: We maken geen onderscheid tussen functie en
afbeelding!
Een functie
f : A → B is een surjectie als
Dat wil zeggen f (A)
• metafoor: ‘input-output machine’
x
∀y ∈ B : ∃x ∈ A : y = f (x).
y = f (x) ∈ B is afhankelijke veranderlijke
input
Surjectie
= B.
B
x1
x2
x3
x4
x5
x6
Pijlendiagram van een surjectie
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen, 2-4
Continu¨ıteit en Limieten
Injectie
Bijectie
f : A → B is een injectie als elk element
´ element van A:
van B het beeld is van hooguit e´ en
Een functie
Een functie
zowel surjectief als injectief is.
A
als y = f (x1) en y = f (x2) dan x1 = x2.
verschillende output
A
f
x1
(‘1–1 duidig’)
B
y6
y7
bld f
x2
x3
x4
x5
B
y1
x1
Bij een injectieve functie geeft verschillende input een
als x1 6= x2 dan f (x1) 6= f (x2).
f : A → B is een bijectie wanneer ze
y1
y2
y3
y4
y5
x2
x3
y2
x4
y4
y3
Pijlendiagram van een bijectie f en de inverse functie f −1
Pijlendiagram van een injectie
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen, 2-6
Continu¨ıteit en Limieten
Inverse functie
Het invers beeld van y
−1
f
2.1.2 Bewerkingen op functies
∈ B is de verzameling
(y) = {x ∈ A | f (x) = y}.
∈ bldf = f (A) dan is f −1(y) niet leeg.
Een functie f : A → B is inverteerbaar als voor iedere
y ∈ f (A) de verzameling f −1(y) uit precies e´ en
´ eleAls y
ment bestaat. In dat geval noteren we dat element ook
met f −1(y) en is
f −1 : f (A) → A : y 7→ x = f −1(y)
de inverse functie.
• Er geldt x = f −1(y) als en slechts als y = f (x).
• f is inverteerbaar als en slechts als f injectief is.
• als f een bijectie is dan is f −1 een bijectie van B
naar A.
f een functie is van A naar B en g een
functie van B naar C dan wordt de samengestelde
functie g ◦ f gedefinieerd als
Als
g ◦ f : A → C : x 7→ g ◦ f (x) = g(f (x)).
A
B
g f
bld f
f
C
g
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen, 2-8
Continu¨ıteit en Limieten
Als ‘input-output machine’:
Som, verschil, product en quotient
¨
output- f (x) input-
x input- f
g
output- g (f (x))
• Het samenstellen van functies is niet commutatief
vb.: stel
⇒
⇒
f (x) = x + 3 en
g(x) = x3
f ◦ g (x) = x3 + 3
g ◦ f (x) = (x + 3)3
B een verzameling is waarop som, verschil, product, quotient
¨ gedefinieerd zijn (bv. B = R).
Stel f en g zijn twee functies van A naar B. De
som f + g , het verschil f − g , het product f g en
f
¨
het quotient
g worden gedefinieerd als
f +g :
A→ B:
x 7→ f (x) + g(x)
f −g :
A→B:
x 7→ f (x) − g(x)
fg :
A→ B:
x 7→ f (x)g(x)
f
f (x)
: {x ∈ A | g(x) 6= 0} → B : x 7→
g
g(x)
• Let op: we mogen niet door nul delen.
Neem aan dat
f (x)
• g(x) is niet gedefinieerd als g(x) = 0.
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen,2-10
Continu¨ıteit en Limieten
Reele
¨ functies van e´ en
´ reele
¨ veranderlijke
¨ als bldf ⊂ R. Als bovendien
Een functie heet reeel
¨ functie van e´ en
´ reele
¨
⊂ R dan is f een reele
domf
Grafiek van een injectie
y
graf f
veranderlijke.
• De grafiek van de functie f is
2
graff = {(x, y) ∈ R | x ∈ domf en y = f (x)}
f(a)
P
• de grafiek bevat alle informatie over het verloop van
f (stijgen/dalen, min/max, limieten, enz.)
a
y
x
Grafiek van een injectie
f(xo)
P
xo
x
• De functie is injectief als en slechts als elke horizontale rechte de grafiek hooguit een
´ keer doorsnijdt.
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen,2-12
Continu¨ıteit en Limieten
Grafiek van de inverse functie
Elementaire reele
¨ functies
• Polynomen of veeltermen: als a0, a1, . . . , an
gegeven reele
¨ getallen zijn met an 6= 0, dan is de
functie P : R → R :
n
X
x 7→ P (x) = a0+a1x+· · ·+anxn =
ak x k
y
graf f
f(a)
P
graf f -1
k=0
een veelterm van de n-de graad in x met coeffici
¨
enten
¨
-1
f (b)
Q
a0 , a 1 , . . . , a n
a
b
x
• Rationale functies: indien P en Q veeltermen
zijn, dan is
Grafiek van een injectie f en van f −1
R=
• De grafiek van de inverse functie krijgen we door
een rationale functie. Het domein van R is
de grafiek van de functie te spiegelen in de rechte
y = x.
domR
Functies, Rijen, Continu¨ıteit en Limieten
• Machtfuncties: Voor elke n ∈ N0 is de machtsfunctie x 7→ xn een veelterm van graad n. Voor
negatieve gehele getallen geldt
1
x−n = n .
x
n ∈ N0 is de beperking van x 7→ xn tot R+
injectief en het bereik is R+. De inverse noteren we
Voor
met
√
R+ → R+ : x 7→ x1/n = n x
en heet de nde machtswortel.
Voor q = m
n ∈ Q (met m ∈ Z, n ∈ N0) geldt
tenslotte
m
xq = x1/n
met domein R+.
P
Q
= {x ∈ R | Q(x) 6= 0}.
Functies, Rijen,2-14
Continu¨ıteit en Limieten
Begrippen rond ordening: stijgen en dalen
Stel f
: domf ⊂ R → R is een reele
¨ functie van e´ en
´
reele
¨ veranderlijke. Zij A ⊂ domf .
• f is stijgend op A indien
∀x1, x2 ∈ A : x1 < x2 =⇒ f (x1) ≤ f (x2).
• f is strikt stijgend op A indien
∀x1, x2 ∈ A : x1 < x2 =⇒ f (x1) < f (x2).
• f is dalend op A indien
∀x1, x2 ∈ A : x1 < x2 =⇒ f (x1) ≥ f (x2).
• f is strikt dalend op A indien
∀x1, x2 ∈ A : x1 < x2 =⇒ f (x1) > f (x2).
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen,2-16
Continu¨ıteit en Limieten
Begrippen rond ordening: begrensd
Stel f
: domf ⊂ R → R is een reele
¨ functie van e´ en
´
reele
¨ veranderlijke. Zij A ⊂ domf .
• f is naar boven begrensd op A indien
Supremum en maximum
Stel f
: domf ⊂ R → R is een reele
¨ functie van e´ en
´
reele
¨ veranderlijke. Zij A ⊂ domf .
• Als f naar boven begrensd is op A, dan is f (A) naar
boven begrensd en heeft bijgevolg een supremum.
∃M ∈ R : ∀x ∈ A : f (x) ≤ M.
Dit is het supremum van f op A
• f is naar onder begrensd op A indien
∃m ∈ R : ∀x ∈ A : f (x) ≥ m.
• f is begrensd op A indien f zowel naar onder als
naar boven begrensd is op A.
• Als f (A) een grootste element heeft, dan is dit het
maximum van f op A. Dit maximum wordt bereikt
in c als c ∈ A en
∀x ∈ A : f (x) ≤ f (c).
• M is een bovengrens van f op A.
• Net zo worden het infimum en het minimum van f
op A gedefinieerd.
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen,2-18
Continu¨ıteit en Limieten
• m is een ondergrens van f op A.
Complexe functies
2.2.1 Rijen: Definitie en voorbeelden
• Als bldf ⊂ C dan is f een complexe functie.
• Als domf ⊂ C en bldf ⊂ C dan is f een complexe
´ complexe veranderlijke.
functie van e´ en
• Veeltermen:
P (z) = a0 + a1z + · · · + anz n =
zijn natuurlijk gedefinieerd voor elke z
De coeffici
¨
enten
¨
getallen zijn.
n
X
de elementen van de rij.
• Andere notatie voor rij: (an) of (an)∞
n=0.
ak z k
k=0
∈ C.
a : N → R is een rij van reele
¨ getallen.
In plaats van a(n) schrijven we an. De getallen an zijn
Een functie
a0, . . . , an mogen ook complexe
• Opeenvolging van reele
¨ getallen
a0 , a 1 , a 2 , . . .
• soms willen we niet met a0 beginnen, maar met bv.
a1. Ook
a1 , a 2 , a 3 , . . .
zullen we een rij noemen.
• Belangrijk is de opeenvolging van getallen en de
richting die in de rij zit:
eerst a0, dan a1, dan a2, enzovoorts.
Functies, Rijen, Continu¨ıteit en Limieten
Complexe rijen
Functies, Rijen, 2-1
Continu¨ıteit en Limieten
Voorbeelden
• Een functie a : N → C is een rij van complexe
• an = n is de rij van natuurlijke getallen
• Notatie (an) of (an)∞
n=0.
√
• an = n
getallen.
0, 1, 2, . . . ,
• an = (−1)n is een alternerende rij
1, −1, 1, −1, 1, −1, 1, . . .
• rij van priemgetallen
2, 3, 5, 7, 11, 13, . . .
• Fibonacci getallen fn
1, 1, 2, 3, 5, 8, 13, 21, . . .
zijn recursief gedefinieerd door f0
= f1 = 1 en
fn = fn−1 + fn−2 voor n ≥ 2.
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen, 2-3
Continu¨ıteit en Limieten
Convergentie van rijen
Rijen worden vaak gebruikt in benaderingsprocessen.
• Bepaal een eerste benadering van de te bepalen
grootheid.
• Vind een manier om een betere benadering te verkrijgen.
• Genereer een rij van steeds betere benaderingen.
• De gewenste grootheid is de limiet van de rij.
Convergentie
(an) is convergent met limiet L ∈ R indien
ε > 0 een natuurlijk getal n0 gevonden kan
worden, zodanig dat |an − L| < ε geldt voor elke
n ≥ n0 .
• In formulevorm
∀ε > 0 : ∃n0 ∈ N : ∀n ≥ n0 : |an − L| < ε
De rij
bij elke
• We kunnen ε beschouwen als een gewenste nauwkeurigheid waarmee we L wensen te benaderen.
Als de rij convergeert naar L, dan kunnen we L
met elke gewenste nauwkeurigheid benaderen door
an ver genoeg in de rij te nemen, namelijk
n ≥ n0 .
maar
• Als ε kleiner wordt genomen, dan zal n0 in het algemeen groter gekozen moeten worden.
Functies, Rijen, Continu¨ıteit en Limieten
R
Functies, Rijen, 2-5
Continu¨ıteit en Limieten
6
•
L+
•
L
•
L−
Voorbeeld 1
•
•
•
•
•
•
•
•
• Notatie voor limiet
• Ook wel
•
•
•
•
•
•
•
•
•
•
• •
•
Rij an
•
•
•
= 10sin(n) tot aan n = 100. Geen convergen-
tie!
•
-
n0
N
10
L = lim an
n→∞
5
0
20
40
60
80
100
–5
–10
an → L
als n → ∞.
Maple code:
with(plots):
f := n -> 10*sin(n):
plot([[ n, f(n)] $n=0..100], x=0..100, style=point,symbol=circle,symbolsize=18,scaling=constrained);
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen, 2-7
Continu¨ıteit en Limieten
Voorbeeld 2
Voorbeeld 2
(n!)1/n
Rij an =
n tot aan n = 50.
(n!)1/n
Rij an =
lijkt te convergeren naar een limiet
n
rond 0.4.
• Laten we uitvergroten rond y = 0.4.
1
0.8
0.6
y
0.4
0.2
0
20
60
40
80
n
Maple code:
with(plots):
g := n -> (n!)^(1/n)/n:
plot([[ n, g(n)] $n=0..50], n=0..100, y=0..1, style=point,symbol=circle,symbolsize=18,scaling=unconstrained);
100
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen, 2-7
Continu¨ıteit en Limieten
Voorbeeld 2
Voorbeeld 2
(n!)1/n
Rij an =
n tot aan n = 100.
(n!)1/n
Rij an =
n . Limiet lijkt zich te bevinden rond 0.38.
Uitvergroting rond 0.38: interval [0.37, 0.39].
0.44
0.39
0.388
0.42
0.386
0.384
y
0.4
0.382
y
0.38
0.38
0.378
0.36
0.374
0.376
0
20
60
40
80
0.372
100
n
0.37 0
20
60
40
Maple code:
80
100
n
with(plots): Digits := 20:
g := n -> (n!)^(1/n)/n:
plot([[ n, g(n)] $n=0..100], n=0..100, y=0.35..0.45, style=point,symbol=circle,symbolsize=18,scaling=unconstrained);
Maple code:
with(plots): Digits := 20: g := n -> (n!)^(1/n)/n: plot([[ n, g(n)] $n=0..100], n=0..100, y=0.37..0.39, style=point,symbol=circle,symbolsize=18,scaling=unconstrained);
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen, 2-7
Continu¨ıteit en Limieten
Voorbeeld 2
Voorbeeld 2
Limiet lijkt zich te bevinden rond
0.38. Ter bevestiging
n = 200 is niet groot genoeg. Neem n = 1000.
nemen we n tot 200.
0.39
0.39
0.388
0.388
0.386
0.386
0.384
0.384
0.382
y
0.382
y
0.38
0.38
0.378
0.378
0.376
0.376
0.374
0.374
0.372
0.372
0.37 0
0.37 0
200
600
400
800
1000
n
20
40
60
80
100
120
140
160
180
200
n
Maple code:
with(plots): Digits := 20: g := n -> (n!)^(1/n)/n: plot([[ n, g(n)] $n=1..200], n=0..200, y=0.37..0.39, style=point,symbol=circle,symbolsize=18,scaling=unconstrained);
Oei! De punten lopen uit het interval [0.37, 0.39].
Maple code:
with(plots): Digits := 40: g := n -> (n!)^(1/n)/n: plot([[ n, g(n)] $n=1..1000], n=0..1000, y=0.37..0.39, style=point,symbol=circle,symbolsize=18,scaling=unconstrained);
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen, 2-7
Continu¨ıteit en Limieten
Voorbeeld 2
Voorbeeld 2
Vergroot het interval tot [0.35, 0.39].
Men kan laten zien dat de limiet van de rij (an) bestaat
en gelijk is aan 0.3679 · · ·
0.39
0.39
0.38
0.38
y
0.37
y
0.37
0.36
0.36
0.35 0
200
600
400
800
1000
n
0.35 0
200
Maple code:
600
400
800
1000
n
with(plots): Digits := 40: g := n -> (n!)^(1/n)/n: plot([[ n, g(n)] $n=1..1000], n=0..1000, y=0.35..0.39, style=point,symbol=circle,symbolsize=18,scaling=unconstrained);
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen, 2-8
Continu¨ıteit en Limieten
Divergentie
Stijgende rijen, begrensde rijen
• Een rij (an) die niet convergent is, is divergent.
• Indien er voor elk reeel
¨ getal M een natuurlijk getal
n0 bestaat zodat
∀n ≥ n0 : an > M
dan is de rij (an) divergent naar
+∞ en we schrij-
ven
lim an = +∞.
n→+∞
• Analoog is divergentie naar −∞ gedefinieerd en
lim an = −∞.
n→∞
Een rij is een speciaal type reele
¨ functie van een reele
¨
veranderlijke. De begrippen rond ordening die we
kennen voor reele
¨ funcies van reele
¨ veranderlijken
zijn dan ook toepasbaar op rijen. Dus kunnen we
spreken van
• stijgende en dalende rijen,
• strikt stijgende en strikt dalende rijen,
• naar boven begrensde en naar onder begrensde
rijen,
• begrensde rijen,
• supremum en infimum van een rij,
• maximum en minimum van een rij.
Functies, Rijen, Continu¨ıteit en Limieten
STELLING 2.3:
Een dalende, naar onder begrensde rij is convergent.
Een stijgende, naar boven begrensde rij is convergent.
We bewijzen dat een stijgende, naar boven begrensde
Vervolg van bewijs
• Neem ε > 0 willekeurig.
• Omdat L het supremum van A is, is L − ε geen
bovengrens van A.
• Er is een element van de rij, zeg an0 met an0 > L−ε
rij, convergent is.
• Neem een stijgende, naar boven begrensde rij (an).
• Dan is A = {an | n ∈ N} een naar boven begrensde verzameling.
• Volgens de derde definierende
¨
eigenschap van R
bezit A een supremum, zeg
L = sup A
Functies, Rijen,2-10
Continu¨ıteit en Limieten
en
L ∈ R.
• We hebben nu L, we willen laten zien dat L de limiet
van de rij is.
• Aangezien de rij stijgend is, geldt voor elke n ≥ n0
dat an ≥ an0 en dus ook an > L − ε.
• Voor elke n ≥ n0 geldt ook an ≤ L, omdat L een
bovengrens van A is.
• Dus L − ε < an ≤ L als n ≥ n0.
• Dus ∀n ≥ n0 : |an − L| < ε.
• Omdat ε > 0 willekeurig gekozen kan worden, volgt
uit de definitie dat de rij convergent is en dat L de
limiet is.
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen,2-12
Continu¨ıteit en Limieten
• Het bewijs voor een dalende rij, die naar onder be-
grensd is, is analoog. Probeer zelf!
• Probeer zelf ook te bewijzen dat een naar boven
begrensde rij (an) met de eigenschap
∀n ≥ 1000 : an ≤ an+1
convergent is.
Voorbeeld
Recursieve rij:
a1 = 4 en
1
2
an+1 =
an +
.
2
an
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen,2-14
Continu¨ıteit en Limieten
Convergentie van complexe rijen
Een complexe rij (zn) is convergent met limiet L
• In formulevorm
Rekenregels
∈C
ε > 0 een natuurlijk getal n0 gevonden
kan worden, zodanig dat |zn − L| < ε geldt voor elke
n ≥ n0 .
indien bij elke
∃L ∈ C : ∀ε > 0 : ∃n0 ∈ N : ∀n ≥ n0 : |zn−L| < ε
Neem aan dat (an) en (bn) convergente rijen zijn met
limieten
L = lim an
n→∞
• Voorbeeld: de rij (z n)
⇒ convergeert naar 0 als |z| < 1,
⇒ is divergent als |z| > 1.
M = lim bn
n→∞
Dan zijn de rijen (an + bn), (an − bn) en (anbn) ook
convergent, met limieten
lim (an + bn) = L + M
n→∞
• L is de limiet van de rij
L = lim zn.
n→∞
en
lim (an − bn) = L − M
n→∞
lim anbn = LM
n→∞
Als tevens geldt dat M =
6 0, dan is de rij (an/bn)
convergent en
an
L
lim
= .
n→∞ bn
M
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen,2-16
Continu¨ıteit en Limieten
Voorbeeld
an =
Limiet en ongelijkheden
n2 + 3n − 2
.
4n2 + 2n − 1
STELLING 2.5: Neem aan dat
(an) en (bn) conver-
gente rijen zijn met limieten
L = lim an
n→∞
en
M = lim bn
n→∞
Veronderstel dat
∃N ∈ N : ∀n ≥ N : an ≤ bn
Dan geldt
L ≤ M.
Bewijs:
• We voeren het bewijs uit het ongerijmde. Neem aan
dat L > M .
• Dan is er een ε > 0 met L > M + 2ε.
(We zouden bv. ε = (L − M )/3 kunnen nemen.)
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen,2-18
Continu¨ıteit en Limieten
• Uit de definitie van convergentie volgt dat er een
n1 ∈ N is met ∀n ≥ n1 : |L − an| < ε.
Insluitstelling voor rijen
• Tevens is er een n2 ∈ N met ∀n ≥ n2 : |M −
b n | < ε.
STELLING 2.6: Neem aan dat
(an) en (cn) conver-
gente rijen zijn met limieten
L = lim an
n→∞
• Neem n ≥ max(n1, n2, N ). Dan geldt
|L − an| < ε, |M − bn| < ε
en an ≤ bn (uit aanname van de stelling)
en
L = lim cn.
n→∞
Als (bn) een rij is waarvoor geldt
∃N ∈ N : ∀n ≥ N : an ≤ bn ≤ cn
dan is de rij (bn) ook convergent en er geldt
• Uit |L − an| < ε volgt nu L − ε < an en uit
|M − bn| < ε volgt bn < M + ε. Dus
L = lim bn.
n→∞
L − ε < an ≤ bn < M + ε.
• Dit betekent L < M + 2ε, hetgeen in tegenspraak
is met het feit dat L > M + 2ε.
• Deze tegenspraak bewijst dat onze aanname dat
L > M geldt, onjuist is. Bijgevolg is L ≤ M .
Functies, Rijen, Continu¨ıteit en Limieten
Voorbeeld
an =
• Neem bn = an − 1 =
√
n
n = n1/n
Functies, Rijen,2-20
Continu¨ıteit en Limieten
lim an = 1
n→∞
√
n
n − 1.
• Het is duidelijk dat an ≥ 1 is, dus bn ≥ 0.
• Omdat (1+bn)n = ann = n, geldt vanwege het binomium van Newton
n 2
n 2
n = (1 + bn)n = 1 + nbn +
bn + · · · ≥ 1 +
b
2
2 n
• Dan is
• Omdat
b2n
n−1
≤ n
2
n
2
=
n(n−1)
2
Deelrijen
• Een deelrij van een rij wordt bekomen door een aan-
tal elementen van de rij weg te laten, zonder iets aan
de volgorde van de overblijvende elemten te veranderen.
(bn) is een deelrij van (an) als er een strikt
stijgende functie ϕ : N → N is zodat
Een rij
∀n ∈ N : bn = aϕ(n).
b2n ≤ (n − 1)
2
2
= .
n(n − 1) n
0 ≤ bn ≤
r
• Uit de insluitstelling volgt lim bn = 0.
n→∞
n→∞
volgt
• Bijgevolg is
• Dus lim an = 1.
2
.
n
• Voorbeeld
a1 , a 3 , a 5 , a 7 , . . .
is een deelrij van (an).
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen,2-22
Continu¨ıteit en Limieten
• Een deelrij van een convergente rij is convergent en
heeft dezelfde limiet.
Stelling van Bolzano-Weierstrass
STELLING: Elke begrensde rij heeft een convergente
deelrij.
• Het bewijs hiervan is gebaseerd op de volledigheid
van R.
• We zullen het bewijs overslaan.
Limsup en liminf
Zij (an) een begrensde rij van reele
¨ getallen
• De limes superior of limsup van de rij (an) is
lim sup an = lim sup{ak | k ≥ n}
n→∞
n→∞
Het is de grootst mogelijke limiet van een convergente deelrij.
• De limes inferior of liminf van de rij (an) is
lim inf an = lim inf{ak | k ≥ n}
n→∞
n→∞
Het is de kleinst mogelijke limiet van een convergente
deelrij.
Functies, Rijen, Continu¨ıteit en Limieten
Functies, Rijen,2-24
Continu¨ıteit en Limieten
• (an) groeit polynomiaal als er een p ∈ N is met
O-symbool • Soms is het limietgedrag van de rij niet belangrijk,
maar hoe een rij zich gedraagt ten opzichte van een
andere, meestal beter gekende rij.
an = O(np)
als n → ∞.
• O-symbool (en verwante symbolen) zijn belangrijk in
het onderzoek naar complexiteit van algoritmen. Als
n staat voor de lengte van de invoer, en an is het
Neem aan dat (an ) en (bn) twee rijen zijn. Dan zeggen
aantal bewerkingen dat gedaan moet worden met
we dat
deze invoer, dan geeft een uitspraak als
an = O(n3)
an = O(bn)
als n → ∞
indien er een constante M > 0 en een n0 ∈ N zijn
met
∀n ≥ n0 : |an| ≤ M |bn|.
We spreken uit:
an is "grote-O"van bn
• (an) is begrensd als en slechts als
an = O(1)
als n → ∞.
aan hoe snel het aantal bewerkingen kan stijgen als
n groot wordt.
• Een algoritme met
an = O(n2)
is dan beter (wat tijdscomplexiteit betreft) dan een
algoritme met
an = O(n4).
© Copyright 2024 ExpyDoc
