Metodi numerici, tecniche di discesa
Sto studiando le tecniche di discesa del gradiente e del gradiente coniugato applicate alla risoluzione di un sistema di equazioni lineari del tipo $hatA*vecx=vecb$, supponiamo $hatA$ matrice SPD.
Si vede che lo studio di tale problema è equivalente a studiare il funzionale $F(vecx)=(hatA*vecx,vecx) -2(vecb,vecx)$ ossia a trovare i minimi di tale funzionale. [0] un funzionale è, in breve, una funzione di funzioni...Ma in questo caso non riesco a "vederlo".
Imponendo il gradiente del funzionale $F$ uguale a zero si ottiene che i minimi del funzionale sono le soluzioni del problema $hatA*vecx=vecb$. Fin qui è chiaro, poi ho qualche dubbio.
[1] Non mi è chiaro cosa si intende nel passaggio successivo:
abbiamo una forma quadratica, il procedimento che ci permatte di passare da una forma quadratica a una forma quadratica nell'intorno del punto di minimo del funzionale si chiama "risoluzione in forma normale della forma qudratica" (???)
Usiamo poi una tecnica per arrivare al minimo del funzionale (tecnica di discesa).
Lo studio del funzionale F è equivalente a studiare il seguente funzionale $E=(A*(x-x_0),(x-x_0))$ [2] Ma questo $x_0$ è il minimo?? Come viene fuori, come è introdotto?
si applica quindi una tecnica iterativa a questo funzionale per calcolare il minimo.
Sul significato geometrico ho qualche altro dubbio
Immaginiamo di essere in 2 dimensioni, le linee dove il funzionale assume sempre lo stesso valore $E(vecx)=k$, nell'intorno di un punto di min o di max sono ellissi. [3]percé sono ellissi, da dove lo vedo, qual è l'equazione? [4] non ho capito la scelta di questo $E(vecx)=k$.
[5] La cosa meno chiara è questa: il gradiente del funzionale ci da la direzione di massima variazione. Perché? Me lo mostrereste analiticamente...
Si vede inoltre (so dimostrarlo) che in prima approssimazione il gradiente è ortogonale a alla tangente ad una curva di livello, pertanto le direzioni di discesa vanno scelte ortogonali alla tangente. Bene.
[6] Ma poi mi si dice: vediamo i criteri per scegliere le direzioni di discesa... Ma non lo abbiamo già stabilito???
I criterio: nello spazio è definita una base $e_1, e_2,..., e_n$ e possiamo scegliere $p_1=e_1$, $p_2=e_2$...
II criterio si sceglie come direzione $p_k$ al passo k dell'iterazione $p_k=(gradE)/(||gradE||)$
III criterio $p_k=r_k+beta p_(k-1)$
Si vede che lo studio di tale problema è equivalente a studiare il funzionale $F(vecx)=(hatA*vecx,vecx) -2(vecb,vecx)$ ossia a trovare i minimi di tale funzionale. [0] un funzionale è, in breve, una funzione di funzioni...Ma in questo caso non riesco a "vederlo".
Imponendo il gradiente del funzionale $F$ uguale a zero si ottiene che i minimi del funzionale sono le soluzioni del problema $hatA*vecx=vecb$. Fin qui è chiaro, poi ho qualche dubbio.
[1] Non mi è chiaro cosa si intende nel passaggio successivo:
abbiamo una forma quadratica, il procedimento che ci permatte di passare da una forma quadratica a una forma quadratica nell'intorno del punto di minimo del funzionale si chiama "risoluzione in forma normale della forma qudratica" (???)
Usiamo poi una tecnica per arrivare al minimo del funzionale (tecnica di discesa).
Lo studio del funzionale F è equivalente a studiare il seguente funzionale $E=(A*(x-x_0),(x-x_0))$ [2] Ma questo $x_0$ è il minimo?? Come viene fuori, come è introdotto?
si applica quindi una tecnica iterativa a questo funzionale per calcolare il minimo.
Sul significato geometrico ho qualche altro dubbio
Immaginiamo di essere in 2 dimensioni, le linee dove il funzionale assume sempre lo stesso valore $E(vecx)=k$, nell'intorno di un punto di min o di max sono ellissi. [3]percé sono ellissi, da dove lo vedo, qual è l'equazione? [4] non ho capito la scelta di questo $E(vecx)=k$.
[5] La cosa meno chiara è questa: il gradiente del funzionale ci da la direzione di massima variazione. Perché? Me lo mostrereste analiticamente...
Si vede inoltre (so dimostrarlo) che in prima approssimazione il gradiente è ortogonale a alla tangente ad una curva di livello, pertanto le direzioni di discesa vanno scelte ortogonali alla tangente. Bene.
[6] Ma poi mi si dice: vediamo i criteri per scegliere le direzioni di discesa... Ma non lo abbiamo già stabilito???
I criterio: nello spazio è definita una base $e_1, e_2,..., e_n$ e possiamo scegliere $p_1=e_1$, $p_2=e_2$...
II criterio si sceglie come direzione $p_k$ al passo k dell'iterazione $p_k=(gradE)/(||gradE||)$
III criterio $p_k=r_k+beta p_(k-1)$
Risposte
[1] è nomenclatura...
[2] credo di sì, con $x_0$ dovrebbe intendere il min
[3] hai una forma quadratica, che in 2 dimensioni ha delle linee equilivello ellittiche, basta pensare all'espressione cartesiana delle ellissi
[4] è il funzionale E che assume valore costante
[5] Principalmente si dimostra con quello che dici dopo:
[6] No, finora hai costruito il funzionale, ma non l'algoritmo che ti permette di spostarti per inseguire il minimo (hill climbing tipicamente)
[2] credo di sì, con $x_0$ dovrebbe intendere il min
[3] hai una forma quadratica, che in 2 dimensioni ha delle linee equilivello ellittiche, basta pensare all'espressione cartesiana delle ellissi
[4] è il funzionale E che assume valore costante
[5] Principalmente si dimostra con quello che dici dopo:
Si vede inoltre (so dimostrarlo) che in prima approssimazione il gradiente è ortogonale a alla tangente ad una curva di livello, pertanto le direzioni di discesa vanno scelte ortogonali alla tangente. Bene.
[6] No, finora hai costruito il funzionale, ma non l'algoritmo che ti permette di spostarti per inseguire il minimo (hill climbing tipicamente)
Grazie per le risposte 
E la domanda [0]?
Riguardo alla [1] ok per la nomenclatura, ma io mi riferivo a cosa si intende con: "passare da una forma quadratica a una forma quadratica nell'intorno del punto di minimo del funzionale"
Riguardo alla [6]: poco prima ho scritto: "pertanto le direzioni di discesa vanno scelte ortogonali alla tangente." Se, quindi opto per il primo criterio per la scelta delle direzioni di discesa sono sicuro che i vettori di base siano ortogonali alla tangente? O l'affermazone tra " è imprecisa?
Riguardo alla [1] ok per la nomenclatura, ma io mi riferivo a cosa si intende con: "passare da una forma quadratica a una forma quadratica nell'intorno del punto di minimo del funzionale"
Riguardo alla [6]: poco prima ho scritto: "pertanto le direzioni di discesa vanno scelte ortogonali alla tangente." Se, quindi opto per il primo criterio per la scelta delle direzioni di discesa sono sicuro che i vettori di base siano ortogonali alla tangente? O l'affermazone tra " è imprecisa?
Lo studio del gradiente coniugato è terribile, penso che però è un po' più facile (cioè divengono più che altro conti) usando i sottospazi di Krylov
"zorn":
Lo studio del gradiente coniugato è terribile, penso che però è un po' più facile (cioè divengono più che altro conti) usando i sottospazi di Krylov
Si si devo fare anche quello e già gli ho dato un'occhiata, ma prima volevo capire bene il discorso generale e il metodo del gradiente in ogni punto
Ecco, il gradiente coniugato a ogni passo minimizza, nella norma indotta dalla matrice A, il residuo Ax_k-b
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo