Extrema

Extrema
Extrema
Extrema
Inhoud
3-0
3.1 Extrema
x 7→ f (~x)
Zij f : U ⊂ Rn → R : ~
• f bereikt in p~ ∈ U een absoluut maximum als
1. Extrema
• Maximum en minimum / Kritieke punten
• Tweede afgeleide test
∀~x ∈ U : f (~x) ≤ f (~p)
• f bereikt in p~ ∈ U een absoluut minimum als
∀~x ∈ U : f (~x) ≥ f (~p)
• Extrema van functies van 2 veranderlijken
2. Optimalisatieproblemen met nevenvoorwaarden
• Ook wel globaal maximum of minimum.
• Substitutiemethode
Volgens de hoofdstelling voor continue functies bereikt
• Lagrange techniek
een continue functie op een gesloten en begrensd deel
3. Kleinste kwadraten benadering
van Rn haar absolute minimum en maximum.
Extrema
Extrema
3-2
Lokale extrema
Maximum en minimum
• f bereikt in p~ een lokaal of relatief maximum als er
een δ > 0 bestaat met
∀~x ∈ B(~p, δ) ∩ domf : f (~x) ≤ f (~p)
2
1.9
1.8
z1.7
• f bereikt in p~ een lokaal of relatief minimum als er
een δ > 0 bestaat met
1.6
–1
1.5
–1
–0.5
–0.6
–0.2 0
y
0.4
0
x
0
x
0.5
0.8
1
1
∀~x ∈ B(~p, δ) ∩ domf : f (~x) ≥ f (~p)
• Het (lokale) maximum of minimum kan bereikt worden
in een randpunt van het domein van f of in een
inwendig punt.
1.4
1.2
1
0.8
0.6
0.4
0.2
0
–1
z
–1
–0.5
–0.6
–0.2 0
y
0.4
0.5
0.8
1
1
Extrema
Extrema
Kritieke punten
3-4
• Om de notatie eenvoudig te houden, geven we het
bewijs voor n = 2.
• Als f afleidbaar is en ∇f (~p) = ~0 dan is p~ een
kritiek punt van f .
• Neem aan dat f (x, y) een lokaal extremum bereikt
~ = (x0, y0).
in p
• Ook wel: stationair punt.
• Dan geldt voor de e´ en-dimensionale
´
beperking
g1(x) = f (x, y0)
dat ze een lokaal extremum heeft in x = x0.
STELLING: Als f afleidbaar is en een lokaal extremum
bereikt in een inwendig punt p
~ van het domein van f ,
~ een kritiek punt van f .
dan is p
• Omdat p~ een inwendig punt is van het domein van f ,
is x0 ook een inwendig punt van het domein van g1.
• Uit de theorie van functies van 1 veranderlijke weten
we dat dan g 0 (x0) = 0.
∂f
0
• Omdat ∂f
∂x (x0, y0) = g1(x0) is dus ∂x (x0, y0) = 0
• Op analoge wijze volgt ∂f
∂y (x0, y0) = 0
• Dus is de gradient
¨ van f in p
~ gelijk aan nul, en dus
is p
~ een kritiek punt van f .
Extrema
Kandidaten voor extrema van functie f
Extrema
: U → R zijn
• Inwendig punten van U die kritieke punten zijn.
• Inwendige punten waar f niet afleidbaar is.
• Alle randpunten van U.
3-6
Zadelpunten
• In een kritiek punt wordt niet noodzakelijk een lokaal
extreem bereikt.
• Het kan ook een zadelpunt zijn.
• Dit is een kritiek punt met de eigenschap dat de
beperking van f tot een bepaalde richting een maximum bereikt in dat punt, terwijl de beperking tot een
andere richting in dat punt een minimum bereikt.
Extrema
Extrema
3-8
Tweede afgeleide test
Voor functie f van e´ en
´ veranderlijke:
1.7
1.6
1.5
1.4
1.3
1.2
1.1
1
–1
• Neem aan dat x0 een kritiek punt is van f (d.w.z.
f 0(x0) = 0) en dat de tweede afgeleide f 00(x0)
z
bestaat.
–1
–0.5
–0.6
0
–0.2 0
y
0.4
• Als f 00(x0) < 0 dan bereikt f in x0 een lokaal
x
0.5
0.8
1
maximum.
1
• Als f 00(x0) > 0 dan bereikt f in x0 een lokaal
•
minimum.
Als f 00 (x0)
= 0 dan is er geen uitspraak.
Wat vervangt in hogere dimensies de tweede afgeleide?
Extrema
Extrema
Hessiaan
,
j, k = 1, . . . , n.
• We nemen aan dat de eerste en tweede orde partiele
¨
afgeleiden van f bestaan en continu zijn.
• Dan is de Hessiaan H symmetrisch, omwille van
• Deze kunnen we ordenen in een n × n matrix
∂ 2f
∂ 2f
∂ 2f
·
·
·
2
∂x1∂xn 
 ∂x1 ∂x1∂x2
 ∂ 2f

2f
∂


.
·
·
·

∂x2∂x1 ∂x2
H=
2
 .

.
.
 .

.
.
 2

2
2
∂ f
∂ f
∂ f
·
·
·
∂xn∂x1 ∂xn∂x2
∂x2n

Hessiaan is symmetrisch
• Er zijn n2 partiele
¨ afgeleiden van de tweede orde
∂ 2f
∂xj ∂xk
3-10

• De matrix H is de Hessiaan, of de matrix van Hesse
de stelling van Schwarz en Young, die zegt dat
∂ 2f
∂ 2f
∂xj ∂xk
=
∂xk ∂xj
• Omdat H symmetrisch is, zijn alle eigenwaarden
¨
van H reeel.
• Bovendien is er een orthonormale basis van Rn
bestaande uit eigenvectoren van H .
Extrema
Extrema
3-12
Beperking langs rechte
Gedrag rond minimum
• Als f een lokaal minimum bereikt in p~, dan bereikt
• Beschouw rechte door p~:
F (t) = f (~p + t~a)
L : ~x = p~ + t~a.
een lokaal minimum in t
• De beperking van f tot L is
= 0.
• Er volgt dan dat F 0(0) = 0 en F 00(0) ≥ 0.
F (t) = f (~p + t~a).
• Dus
• Volgens de kettingregel is
~a · H~a ≥ 0
waarin H de Hessiaan is in p
~.
F 0(t) = ~a · ∇f (~p + t~a).
• Men kan laten zien dat
• Dit moet gelden voor elke richtvector ~a.
F 00(t) = ~a · H(~p + t~a)~a.
waarin H(~
p + t~a) de Hessiaan is in het punt p~ + t~a.
Extrema
Kijk in richting van eigenvector
• Neem voor ~a een eigenvector ~u met eigenwaarde λ.
• Dus H~u = λ~u.
• Dan ~u · H~u = ~u · (λ~u) = λk~uk2.
• Als f in p~ een lokaal minimum bereikt, dan moet dit
≥ 0 zijn.
• Dus dan moet λ ≥ 0 en dit zou moeten gelden voor
elke eigenwaarde van H .
Extrema
3-14
Conclusie
• Als f in p~ een lokaal minimum bereikt dan zijn alle
eigenwaarden van de Hessiaan ≥ 0.
• Evenzo: Als f in p~ een lokaal maximum bereikt dan
zijn alle eigenwaarden van de Hessiaan ≤ 0.
Extrema
Extrema
3-16
Omgekeerd geldt ook
Functies van 2 veranderlijken
~ een kritiek punt, en H de Hessiaan in p~.
Zij p
• Als f : U → R een kritiek punt p~ = (a, b) heeft,
• Als alle eigenwaarden van H positief zijn (d.w.z > 0),
dan bereikt f in p
~ een lokaal minimum.
dan berekenen we de Hessiaan

∂ 2f
 2 (a, b)
H =  ∂x2
∂ f
∂y∂x (a, b)
• Als alle eigenwaarden van H negatief zijn (dus < 0),
~ een lokaal maximum.
dan bereikt f in p

∂ 2f
∂x∂y (a, b)
.
∂ 2f
(a,
b)
∂y 2
• Als H zowel positieve als negatieve eigenwaarden
~ een zadelpunt.
heeft, dan is p
¨ eigen• Dit is een symmetrische matrix met twee reele
waarden λ1 en λ2.
• Als 0 een eigenwaarde van H is, en alle andere
• Om te onderzoeken of het kritieke punten een (lokaal)
eigenwaarden hebben hetzelfde teken, dan is er geen
maximum of minimum is, is de preciese waarde van
uitspraak.
λ1 en λ2 niet van belang, maar alleen het teken.
Extrema
Extrema
3-18
Negatieve eigenwaarden
Positieve eigenwaarden
0
2
–0.5
1.5
z –1
z1
–1
–1.5
–2
–1
–0.5
–0.6
0
–0.2 0
y
0.4
0
–1
x
0.5
0.8
1
1
–1
0.5
–0.5
–0.6
0
–0.2 0
y
1
0.4
0.5
0.8
1
x
1
1
0.8
0.8
y 0.6
y 0.6
0.4
0.4
0.2
0.2
–1 –0.8 –0.6 –0.4 –0.2
–0.2
–1 –0.8 –0.6 –0.4 –0.2
–0.2
0.2 0.4 0.6 0.8
x
1
–0.4
–0.4
–0.6
–0.6
–0.8
–0.8
–1
–1
0.2 0.4 0.6 0.8
x
1
Extrema
Extrema
Positieve en negatieve eigenwaarde
Karakteristieke veelterm
• De eigenwaarden zijn nulpunten van
2
∂ f −λ
∂2f
∂x2
∂x∂y
det(H − λI) = 2
2
∂ f
∂ f
∂y∂x ∂y2 − λ 2
2
2 2
∂ f
∂ f
∂ f
=
−
λ
−
λ
−
∂x2
∂x2
∂x∂y
2 2!
2
∂ 2f ∂ 2f
∂ f
∂ f ∂ 2f
+
λ
+
·
−
= λ2 −
∂x2 ∂y 2
∂x2 ∂x2
∂x∂y
1
0.5
z0
–1
–0.5
–1
–1
–0.5
–0.6
0
–0.2 0
y
0.4
x
0.5
0.8
1
1
1
3-20
0.8
y 0.6
= λ2 − sp (H)λ + det(H).
0.4
0.2
–1 –0.8 –0.6 –0.4 –0.2
–0.2
0.2 0.4 0.6 0.8
x
1
• Spoor van H is de som van de diagonaalelementen:
–0.4
–0.6
sp (H)
–0.8
–1
Extrema
Extrema
=
∂ 2f ∂ 2f
+
.
∂x2 ∂y 2
3-22
Spoor en determinant
• Omdat λ2 −sp (H)λ+det(H) = (λ−λ1)(λ−λ2)
geldt
sp (H)
= λ1 + λ2 en det(H) = λ1 · λ2.
• Als det H < 0 dan hebben λ1 en λ2 verschillend
teken. Het kritieke punt is dan een zadelpunt.
• Als det H > 0, dan hebben λ1 en λ2 hetzelfde
teken. Er is dan een extremum.
• Als sp H > 0, dan zijn λ1, λ2 > 0 en er is een
lokaal minimum.
• Als sp H < 0, dan zijn λ1, λ2 < 0 en er is een
lokaal maximum.
3.2 Optimalisatie met nevenvoorwaarden
• Stel er is een bedrag b te besteden voor het kopen
van twee producten.
• Het eerste product kost 2 Euro/stuk en het tweede
product kost 1 Euro/stuk.
• We kopen x stuks van product 1 en y stuks van
product 2.
• De ‘nut’ van het het pakket (x, y) wordt uitgedrukt
door een nutsfunctie, bv:
n(x, y) = xy + 2x
Wat is het ‘nuttigste’ pakket binnen ons budget b ?

 Maximaliseer
xy + 2x
 onder de nevenvoorwaarde 2x + y = b.
Extrema
Extrema
3.2.1 Substitutiemethode
3-61
3.2.2 Lagrange-techniek
• Los e´ en
´ variabele op uit de nevenvoorwaarde en substitueer deze in de doelfunctie.
• Functie van twee veranderlijken f (x, y).
• Maximaliseer (of minimaliseer) f (x, y) onder de nevenvoorwaarde h(x, y) = c.
• In het voorbeeld is
• De nevenvoorwaarde h(x, y) = c bepaalt een kromme
K in het xy -vlak. Dit is een niveaukromme van h.
y = b − 2x
• Vul in in n(x, y) = xy + 2x
n(x, b−2x) = x(b−2x)+2x = −2x2+(2+b)x.
• Dit resulteert in optimalisatieprobleem zonder nevenvoorwaarde met e´ en
´ variabele minder voor functie
N (x) = −2x2 + (2 + b)x.
Extrema
Extrema
Grafisch
3-63
Meer niveaulijnen van f
p
• Maximaliseer f (x, y) = x2 + y 2 onder nevenvoorwaarde h(x, y) = x2 + y 2 + 2x − 2y + 1 = 0
2
y
3
1
2
–2
y
–1
0
1
2
x
1
–1
–3
–2
–1
2
1
3
–2
x
–1
Maple commando’s
–2
–3
Maple commando’s
>
>
>
>
with(plots): f:= (x^2+y^2)^(1/2): h := x^2+y^2+2*x-2*y+1:
plotf := contourplot(f, x=-3..3, y=-3..3, contours=[1/2,1,3/2,2,5/2,3],grid=[50,50],color=black):
plotq := contourplot(q, x=-3..3, y=-3..3, contours=[0], color=black,thickness=3,grid=[50,50]):
display(plotq,plotf,scaling=constrained);
>
>
>
>
with(plots): f:= (x^2+y^2)^(1/2): h := x^2+y^2+2*x-2*y+1:
plotf := contourplot(f, x=-3..3, y=-3..3, contours=[2.1,2.2,2.3,2.4,2.5,2.6,2.7],grid=[50,50],color=black):
plotq := contourplot(q, x=-3..3, y=-3..3, contours=[0], color=black,thickness=3,grid=[50,50]):
display(plotq,plotf,scaling=constrained);
Extrema
Extrema
3-65
Voorwaarde voor extremum
FEIT: In een extremum onder nevenvoorwaarde raakt
K aan de niveaukromme van f .
• ∇h is de normaal op K.
• ∇f is de normaal op de niveaukromme van f .
Lagrange multiplicator
• We krijgen drie vergelijkingen
∇f − λ∇h = ~0
h(x, y) = c
• Ook drie onbekenden x, y en λ.
• Nodige voorwaarde voor extremum is dat deze twee
normalen in dezelfde richting staan.
• Ze moeten dus lineair afhankelijk zijn:
∇f = λ∇h
voor zekere λ
∈ R.
• λ heet de Lagrange multiplicator (of Lagrange vermenigvuldiger).
Extrema
Extrema
Voorbeeld
3-67
Het probleem
Probleem Vind optimale afmetingen van een conservenblik met inhoud L liter.
• Optimaal betekent hier dat de totale oppervlakte
van de zijkanten minimaal is.
• Het conservenblik is cilindervormig. De straal van de
cilinder is r en de hoogte is x.
• De inhoud is dan πr 2x.
• De oppervlakte van de ronde zijde is 2πrx.
• De oppervlakte van de boven- en onderkant is πr 2.
• Totale oppervlakte is 2πrx + 2πr 2.
f (r, x) = 2πrx + 2πr 2
onder de nevenvoorwaarde h(r, x) = πr 2x = L.
Minimaliseer
• Lagrange-techniek: Bepaal ∇f en ∇h.
∂f ∂f
∇f =
,
= (2πx + 4πr, 2πr).
∂r ∂x
∂h ∂h
∇h =
,
= (2πrx, πr 2).
∂r ∂x
• Dit leidt tot stelsel

 2πx + 4πr = λ2πrx
2πr
= λπr 2
 2
πr x
=L
Extrema
Oplossing
Extrema
3-69
Conclusie
• Uit 2πr = λπr 2 en r =
6 0 volgt
λr = 2.
• In een perfect blik is de hoogte twee keer zo groot als
• Uit eerste vergelijking volgt x + 2r = λrx en omdat
λr = 2 betekent dit dat x + 2r = 2x, zodat
x = 2r.
• Controleer dit eens in de GB (of zo)!
de straal.
• Omdat πr 2x = L volgt dan
L = 2πr 3
• Dus
L 1/3
r=
2π
1/3
L
x = 2r = 2
.
2π
en
Extrema
Extrema
3-71
Algemene formulering Lagrange-techniek
Maximaliseer of minimaliseer de functie van
n veran-
derlijken
Vergelijkingen
• Als in een punt ~x een lokaal extremum wordt bereikt
dan
f (x1, x2, . . . , xn)
onder de m nevenvoorwaarden (met m







< n)
h1(x1, x2, . . . , xn) = c1
h2(x1, x2, . . . , xn) = c2
..
..
..
hm(x1, x2, . . . , xn) = cm
• Neem aan dat ∇h1(~x), . . . , ∇hm(~x) lineair onafhankelijke vectoren zijn in Rn.
• Neem m Lagrange multiplicatoren λ1, λ2, . . . , λm
∇f (~x) = λ1∇h1(~x) + · · · + λm∇hm(~x)

 h1(~x) = c1
..
..
hm(~x) = cm
• Dit zijn n+m vergelijkingen voor n+m onbekenden

x 1 , x 2 , . . . , x n , λ1 , . . . , λ m
Extrema
Extrema
Voorbeeld
Bepaal het extremum van de functie
2
2
f (x, y, z) = (x − 1) + (y − 1) + (z − 1)2,
onder nevenvoorwaarden
h1(x, y) = 2x+y−z = 1, h2(x, y) = x−y+z = 2.
• Interpretatie: Elk van de nevenvoorwaarden bepaalt
een vlak een R3. De twee nevenvoorwaarden samen
bepalen een rechte L.
• f (x, y, z) is het kwadraat van de afstand van (x, y, z)
tot het punt (1, 1, 1).
• Het probleem is dus om het punt (x, y, z) op de
rechte L te zoeken dat het dichtst bij (1, 1, 1) ligt.
• Het gezochte extremum is dan de kwadraat van de
minimale afstand.
3-73
Lagrange-techniek
• ∇f = (2(x − 1), 2(y − 1), 2(z − 1))
• ∇h1 = (2, 1, −1) en ∇h2 = (1, −1, 1).
• Vergelijkingen


2(x − 1) = 2λ1 + λ2





 2(y − 1) = λ1 − λ2
2(z − 1) = −λ1 + λ2



2x + y − z = 1



 x−y+z = 2
• Dit zijn 5 lineaire vergelijkingen met 5 veranderlijken.
• Oplossing is
1
3
1
2
x = 1, y = , z = , λ1 = − , λ2 = .
2
2
3
3

Download Report