Introduzione Data una funzione f che dipende da una o più variabili, si vogliono trovare i valori...
-
Upload
felisa-pasquali -
Category
Documents
-
view
213 -
download
0
Transcript of Introduzione Data una funzione f che dipende da una o più variabili, si vogliono trovare i valori...
IntroduzioneData una funzione f che dipende da una o più variabili, si
vogliono trovare i valori delle variabili in corrispondenza dei quali f assume valore massimo o minimo, e calcolare tale valore i due problemi sono equivalenti:
il massimo (minimo) di f è il minimo (massimo) di –fClassificazione degli estremi:
estremo globale: è il punto in cui la funzione assume il valore più alto (o più basso) in assoluto
estremo locale: è il punto in cui la funzione assume il valore più alto (o più basso) limitatamente ad un intorno dell’estremo (massimi e minimi relativi)
In genere si vogliono ricercare gli estremi locali di una funzione
Ci sono due tipi di metodi di ricerca di massimi e minimi:metodi che non richiedono il calcolo delle derivatemetodi che richiedono il calcolo delle derivate
nel caso multidimensionale la derivata è un gradiente in genere questi metodi richiedono un numero maggiore di
calcoli, ma sono più efficaci
Intrappolamento (“bracketing”)Un minimo di una funzione f(x) si dice intrappolato se
esistono tre punti a,b,c con a<b<c tali che f(b)<f(a) e f(b)<f(c)in questo caso, se f(x) è continua, il minimo si troverà in
un punto dell’intervallo [a,c]nel caso di un massimo, devono esistere tre punti
a,b,c con a<b<c tali che f(b)>f(a) e f(b)>f(c)
x
y
a b c
f(c)
f(b)
f(a)
Metodo della sezione aurea (1)Si parte da un minimo inizialmente intrappolatoDetti a,b,c i punti che intrappolano il minimo si ha:
Analogamente a quanto viene fatto nel metodo di bisezione, si cerca un nuovo punto x, compreso tra a e b oppure tra b e c, che restringa l’intervallo
Supponiamo di scegliere x tra b e c: se f(x)>f(b) il nuovo tripletto di punti sarà a,b,x se f(x)<f(b) il nuovo tripletto di punti sarà b,x,c
)()()()( cfbfafbf
cba
x
y
a b cx x
y
a b cx
Metodo della sezione aurea (2)Il processo di intrappolamento viene arrestato quando la
distanza c-a è sufficientemente piccolase è la precisione della macchina, si potrebbe pensare di
fermare il processo quando a=b(1- ) e c=b(1+ ) in realtà conviene fermarsi prima per evitare troppi calcoli
Se x=b è la posizione del minimo, in un intorno di x si ha:
Il secondo termine della somma deve essere trascurabile rispetto al primo (di un fattore ):
Poiché il termine sotto radice è in genere dell’ordine dell’unità, è sufficiente che la larghezza frazionaria dell’intervallo |x-b|/b sia dell’ordine di ε1/2
in questo modo si evita di effettuare troppe bisezioni
2)(2
1)()( bxbfbfxf
)(
)(2
)(
)(2)()(
2
12
2
bfb
bfbbx
bf
bfbxbfbxbf
Metodo della sezione aurea (3)Quale è la strategia migliore per scegliere il
nuovo punto x in ogni iterazione?Poniamo:
Supponiamo che il punto x successivo si trovi tra b e c e poniamo:
Se x si trova tra a e b si ragiona analogamente (in questo caso sarà Z<0)
ac
bcW
ac
abW
1
ac
bxZ
a b cx
W(c-a) (1-W)(c-a)
Z(c-a)
Metodo della sezione aurea (4)A seconda del valore di f(x) si sceglierà il nuovo tripletto di
punti:se f(x)>f(b) i nuovi 3 punti da usare sono a,b,x
il nuovo intervallo [a,x] ha lunghezza (W+Z)(c-a)se f(x)<f(b) i nuovi 3 punti da usare sono b,x,c
il nuovo intervallo [b,c] ha lunghezza (1-W)(c-a)Conviene scegliere Z in maniera tale che, qualunque condizione
si verifichi, l’intervallo finale abbia sempre la stessa lunghezza:
Con questa scelta |b-a|=|x-c|:
WZWZW 211
)())(1(
))(1()()()(
)(
acWacWZ
acWacZbcbxcx
acWab
a b cx
W(c-a) (1-W)(c-a)
Z(c-a) W(c-a)
Metodo della sezione aurea (5) Il punto x è il simmetrico di b nell’intervallo [a,c]
il punto x si trova sempre all’interno del più lungo tra i segmenti [a,b] (se Z<0) e [b,c] (se Z>0)
Consideriamo i tripletti di punti a,b,c e b,x,c:
Se gli intervalli vengono divisi sempre allo stesso modo, allora i due rapporti devono essere uguali e quindi deve aversi:
a b cx
W(c-a) (1-W)(c-a)
Z(c-a) W(c-a)
W
Z
acW
acZ
bc
bxW
ac
ab
11
38197.02
5301321
11
22
WWWWWW
WWZWW
Z
Metodo della sezione aurea (6)L’intrappolamento ottimale porta a tripletti di punti in cui
il punto centrale si trova ad una distanza frazionaria W=0,38197 da uno dei due estremi e ad una distanza frazionaria 1-W=0,61803 dall’altro estremo (sezioni auree)
Dato un tripletto di punti a,b,c, il punto successivo x in cui calcolare il valore della funzione si trova alla distanza frazionaria W=0.38197 dal punto di mezzo del tripletto, nel più lungo dei due intervalli [a,b] o [b,c]
Se gli intervalli del tripletto di partenza non rispettano i rapporti aurei non è un problema la procedura iterativa converge rapidamente verso intervalli
ottimaliLa dimensione dell’intervallo ottenuto alla n-esima
iterazione è pari a 0,61803 volte la dimensione dell’intervallo ottenuto alla (n-1)-esima iterazionequesto valore va confrontato con il valore di 0,5 del metodo
di bisezione per la ricerca degli zeri
Interpolazione parabolica (1)Se la funzione f(x) è abbastanza regolare, in un intorno del
minimo si può approssimare il suo grafico con quello di una parabola
Sia x0 l’ascissa del minimo e sviluppiamo f(x) in serie di Taylor in un intorno di x0:
avendo sfruttato il fatto che f’(x0)=0In prossimità del minimo ha dunque senso approssimare il
grafico della funzione con quello di una parabolaUna volta individuati 3 punti a,b,c che intrappolano il
minimo di f(x) consideriamo la parabola per i tre punti [a,f(a)], [b,f(b)] e [c,f(c)] il minimo della parabola (che ne è anche il vertice) sarà
usato come approssimazione del minimo della funzione
2000 2
1xxxfxfxf
Interpolazione parabolica (2)Scriviamo l’equazione della parabola che
passa per i tre punti [a,f(a)], [b,f(b)] e [c,f(c)] nella forma:
e determiniamo i parametri A, B e C:
Restano da risolvere la prima e la terza equazione per trovare i valori di A e B
CbxBbxAy 2
cfCbcBbcA
bfC
afCbaBbaA
2
2
bfcfbcBbcA
bfC
bfafbaBbaA
2
2
Interpolazione parabolica (3)Riscrivendo in maniera opportuna le due
equazioni e sottraendo membro a membro si ha:
bc
bfcfBbcA
ba
bfafBbaA
ab
afbf
bc
bfcf
acA
ba
bfaf
bc
bfcfacA
1
2
2
bc
bfcf
bc
BA
ba
bfaf
ba
BA
ab
afbfbc
bc
bfcfab
acB
ab
afbf
bc
bfcf
abbc
acB
ba
bfaf
bc
bfcf
babcB
1
11
22
22
Interpolazione parabolica (4)Cerchiamo adesso l’ascissa del minimo della
parabola:
Sostituendo i valori di A e B determinati prima si ha:
L’interpolazione parabolica viene usata nel metodo di Brent, in combinazione con la regola aurea
A
BbxBbxA
dx
dy
2020
afbfbcbfcfab
afbfbcbfcfabbx
abafbf
bcbfcf
ac
abafbfbc
bcbfcfab
acb
A
Bbx
22
2
1
2
1
2
Metodo di Nelder e Mead (1) Il metodo di Nelder e Mead, noto come “downhill simplex
method” o “metodo dell’ameba”, permette di ricercare massimi e minimi di funzioni di più variabili
In tale metodo si utilizzano soltanto i valori della funzione, senza calcolarne le derivate
Definizione: si chiama “simplex” in uno spazio a N dimensioni la figura geometrica definita da N+1 vertici e da tutte le linee che connettono tali vertici nello spazio a 2 dimensioni un simplex è un triangolo nello spazio a 3 dimensioni un simplex è un tetraedro
In generale ci interessano i simplex non degeneri, ossia i simplex che racchiudono un volume N-dimensionale nello spazio a 2 dimensioni un triangolo è degenere se i suoi 3
vertici sono collineari in tal caso il triangolo degenera in un segmento e la sua superficie è nulla
nello spazio a 3 dimensioni un tetraedro è degenere se i suoi 4 vertici sono complanari in tal caso il tetraedro degenera in un triangolo ed il suo volume è nullo
in generale, nello spazio a N dimensioni un simplex è degenere se i suoi N+1 vertici sono contenuti in un iperpiano di dimensione N-1
Metodo di Nelder e Mead (2)Si sceglie un simplex di partenza individuato dagli
N+1 punti P0,P1,...,PN
in genere conviene fissare P0 e scegliere gli altri N punti in modo che sia:
dove gli ei sono N vettori unitari linearmente indipendenti e λ è una costante che può rappresentare una costante di scala del problema in esamein principio si possono scegliere N valori di λi diversi
Si procede in maniera iterativa:in ogni iterazione il simplex ottenuto nell’iterazione
precedente viene opportunamente modificato
NiePP ii ...1 0
Metodo di Nelder e Mead (3)Possibili operazioni:
riflessione: il punto in cui f(x) ha il valore più alto viene sostituito con il suo simmetrico rispetto alla faccia opposta del simplex
riflessione con espansione: il punto in cui f(x) ha il valore più alto è sostituito con un punto simmetrico rispetto alla faccia opposta del simplex, a distanza maggiore
contrazione lungo una dimensione: il punto in cui f(x) ha il valore più alto è sostituito con un punto lungo la perpendicolare alla faccia opposta, a distanza minore
contrazione lungo tutte le dimensioni verso il punto in cui f(x) ha il valore più basso: gli altri N punti del simplex dove f(x) ha il valore maggiore vengono spostati lungo la congiungente con il punto in cui f(x) ha il valore più basso in direzione di tale punto
Metodo di Nelder e Mead (4)
A
B
C
A’A
B
CA’
f(A)>f(B)>f(C)
A
B
C
A’
C
A’
A
B’B
riflessione riflessione con
espansione
contrazione in una
dimensione
contrazione lungo
più dimension
i
Metodo di Nelder e Mead (5)
Metodo di Nelder e Mead (6)La procedura iterativa sceglie di volta in volta
quale è l’operazione più opportuna da compiere sul simplex di partenza
La procedura termina quando la distanza percorsa in una iterazione è più piccola di un valore di tolleranza prefissato dall’utentetipicamente si sceglie una tolleranza pari alla
precisione della macchinaA volte la procedura iterativa può essere
terminata erroneamenteè sempre bene far ripartire l’algoritmo dal punto
in cui è stato individuato il minimo se effettivamente il punto di partenza è un minimo,
allora la procedura iterativa restituirà ancora una volta tale punto
EsempioConsideriamo la funzione f(x,y)=(1-x)2+100(y-x2)2+1Tale funzione ha un minimo in (1,1) e f(1,1)=1