Accelerazione di Anderson

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

L'accelerazione di Anderson (nota anche in inglese come Anderson mixing) è un metodo per l'accelerazione della convergenza delle iterazioni di punto fisso. Introdotto da Donald G. Anderson[1], tale metodo può essere utilizzato per trovare la soluzione di equazioni di punto fisso che emergono spesso nel campo della scienza computazionale.

Definizione[modifica | modifica wikitesto]

Data una funzione , si consideri il problema di trovare un punto fisso di , ovvero una soluzione all'equazione . Un approccio classico al problema è quello di impiegare uno schema di iterazione di punto fisso[2], ovvero data una prima ipotesi per la soluzione, calcolare la sequenza fino a quando non viene soddisfatto un criterio di convergenza. Tuttavia, la convergenza dello schema non è garantita in generale. Inoltre, la convergenza è in generale lineare, e può quindi risultare troppo lenta, soprattutto se la valutazione della funzione è costosa[2]. L'accelerazione di Anderson è un metodo per accelerare la convergenza delle iterazioni di punto fisso[2].

Si definisca , e . Data un'iterata iniziale e un parametro intero , il metodo può essere formulato come segue[3][nota 1]:

Per terminare le iterazioni del metodo possono essere usati i criteri di arresto tipici dei metodi iterativi. Ad esempio, le iterazioni possono essere interrotte quando è al di sotto di una tolleranza prescritta o quando il residuo è al di sotto di una tolleranza prescritta.

Rispetto alla semplice iterazione di punto fisso, è stato riscontrato che il metodo di accelerazione di Anderson converge più velocemente, più robusto e, in alcuni casi, evita la divergenza della sequenza di punto fisso[3][4].

Soluzione del problema di minimizzazione[modifica | modifica wikitesto]

Ad ogni iterazione dell'algoritmo, il problema di ottimizzazione vincolata , soggetto a deve essere risolto. Il problema può essere espresso in alcune formulazioni equivalenti[3], cui corrispondono diversi metodi di soluzione che possono risultare in un'implementazione più efficiente:

  • definendo le matrici e , risolvere e porre [3][4];
  • risolvere , quindi porre [1].

Per entrambe le scelte precedenti, il problema di ottimizzazione si presenta sotto forma di un problema ai minimi quadrati lineare non vincolato, che può essere risolto con metodi standard tra cui decomposizione QR[3] e decomposizione ai valori singolari[4], possibilmente includendo tecniche di regolarizzazione per affrontare problemi legati al rango e al condizionamento del problema di ottimizzazione. Risolvere il problema dei minimi quadrati risolvendo le equazioni normali non è generalmente consigliabile a causa di potenziali instabilità numeriche e costi di calcolo generalmente elevati.

La stagnazione del metodo (ovvero il calcolo di iterazioni successive con lo stesso valore, ) ne causa il breakdown per via della singolarità del problema dei minimi quadrati. Allo stesso modo, la quasi-stagnazione () provoca il mal condizionamento del problema ai minimi quadrati[3]. Inoltre, la scelta del parametro potrebbe essere rilevante nel determinare il condizionamento del problema dei minimi quadrati, come illustrato più avanti.

Rilassamento[modifica | modifica wikitesto]

L'algoritmo può essere modificato introducendo un parametro di rilassamento variabile (o parametro di mixing) [1][3][4]. Ad ogni passaggio, la nuova iterata va calcolata come La scelta del valore di è cruciale per determinare le proprietà di convergenza del metodo; in linea di principio, potrebbe variare ad ogni iterazione, sebbene sia spesso scelto costante[4].

Scelta di m[modifica | modifica wikitesto]

Il parametro determina quante informazioni dalle iterazioni precedenti vengono utilizzate per calcolare la nuova iterazione . Da un lato, se viene scelto troppo piccolo, vengono utilizzate poche informazioni e la convergenza può essere lenta. D'altra parte, se è troppo grande, le informazioni delle vecchie iterazioni possono essere conservate per troppe iterazioni successive, anche in questo caso rallentando la convergenza[3]. Inoltre, la scelta di influisce sulla dimensione del problema di ottimizzazione. Un valore troppo grande di può peggiorare il condizionamento del problema dei minimi quadrati e il costo della sua soluzione. In generale, quale sia una buona scelta di dipende dal particolare problema da risolvere[3].

Scelta di [modifica | modifica wikitesto]

Rispetto all'algoritmo sopra descritto, la scelta di ad ogni iterazione può essere modificata. Una possibilità è scegliere per ogni iterazione (questa scelta è a volte indicata come accelerazione di Anderson senza troncamento)[3]. In questo modo, ogni nuova iterazione viene calcolata utilizzando tutte le iterazioni precedenti. Una tecnica più sofisticata si basa sullo scegliere in modo da mantenere un condizionamento abbastanza piccolo per il problema ai minimi quadrati[3].

Confronto con altre classi di metodi[modifica | modifica wikitesto]

Il metodo di Newton può essere applicato alla soluzione di per calcolare un punto fisso di con convergenza quadratica. Tuttavia, tale metodo richiede la valutazione della derivata esatta di , cosa può essere molto costosa[4]. L'approssimazione della derivata mediante differenze finite è una possibile alternativa, ma richiede valutazioni multiple di ad ogni iterazione, che di nuovo può essere molto costoso. L'accelerazione di Anderson richiede solo una valutazione della funzione per iterazione e nessuna valutazione della sua derivata. D'altra parte, la convergenza di una sequenza di punto fisso con accelerazione di Anderson è ancora lineare in generale[5].

Diversi autori hanno messo in evidenza somiglianze tra lo schema di accelerazione di Anderson e altri metodi per la soluzione di equazioni non lineari. In particolare:

  • Eyert[6] e Fang e Saad[4] hanno interpretato l'algoritmo all'interno della classe dei metodi quasi-Newton e multisecante, che generalizzano il noto metodo delle secanti, per la soluzione dell'equazione non lineare ; hanno anche mostrato come lo schema può essere visto come un metodo nella di Broyden[7];
  • Walker e Ni[3] hanno dimostrato che lo schema di accelerazione di Anderson è equivalente al metodo GMRES in caso di problemi lineari (ovvero il problema di trovare una soluzione a per una matrice quadrata e può quindi essere visto come una generalizzazione di GMRES nel caso non lineare; un risultato simile è stato trovato da Washio e Oosterlee[8].

Inoltre, altri metodi equivalenti o quasi equivalenti sono stati sviluppati in modo indipendente da altri autori[8][9][10][11][12], sebbene il più delle volte nel contesto di un'applicazione specifica di interesse piuttosto che come metodo generale per equazioni di punto fisso.

Esempio di implementazione in MATLAB[modifica | modifica wikitesto]

Di seguito è riportato un esempio di implementazione in linguaggio MATLAB dello schema di accelerazione di Anderson per trovare il punto fisso della funzione . Si noti che:

  • il problema di ottimizzazione è stato risolto nella forma usando la decomposizione QR;
  • il calcolo della decomposizione QR non è ottimale: infatti, ad ogni iterazione viene aggiunta una singola colonna alla matrice ed eventualmente una singola colonna viene rimossa: questo può essere sfruttato per aggiornare in modo efficiente la decomposizione QR con minori costi computazionali[13];
  • l'algoritmo può essere reso più efficiente in termini di memoria salvando solo le ultime iterazioni e residui, se l'intero vettore di iterazioni non è necessario;
  • il codice è facilmente generalizzabile al caso di una a valori vettoriali.
f = @(x) sin(x) + atan(x); % Funzione di cui calcolare il punto fisso.
x0 = 1; % Iterata iniziale.

k_max = 100; % Numero massimo di iterazioni.
tol_res = 1e-6; % Tolleranza sul residuo.
m = 3; % Parametro m.

x = [x0, f(x0)]; % Vettore di tutte le iterazioni.
g = f(x) - x; % Vettore di tutti i residui.

G_k = g(2) - g(1); % Matrice degli incrementi dei residui.
X_k = x(2) - x(1); % Matrice degli incrementi nelle iterazioni.

k = 2;
while k < k_max && abs(g(k)) > tol_res
  m_k = min(k, m);
  
  % Soluzione del problema ai minimi quadrati con fattorizzazione QR.
  [Q, R] = qr(G_k);
  gamma_k = R \ (Q' * g(k));
  
  % Calcolo della nuova iterata e del residuo corrispondente.
  x(k+1) = x(k) + g(k) - (X_k + G_k) * gamma_k;
  g(k+1) = f(x(k+1)) - x(k+1);
  
  % Aggiornamento delle matrici degli incrementi.
  X_k = [X_k, x(k+1) - x(k)];
  G_k = [G_k, g(k+1) - g(k)];
  
  n = size(X_k, 2);
  if n > m_k
    X_k = X_k(:,n-m_k+1:end);
    G_k = G_k(:,n-m_k+1:end);
  end
  
  k = k + 1;
end

% Stampa il risultato: Trovato punto fisso 2.013444 dopo 9 iterazioni
fprintf ("Trovato punto fisso %f dopo %d iterazioni\n", x(end), k);

Voci correlate[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

  1. ^ La formulazione che segue non corrisponde esattamente a quella fornita dall'autore originale[1], ma è una formulazione equivalente data da Walker e Ni[3].

Bibliografia[modifica | modifica wikitesto]

  1. ^ a b c d Donald G. Anderson, Iterative Procedures for Nonlinear Integral Equations, in Journal of the ACM (JACM), vol. 12, n. 4, ottobre 1965, pp. 547–560, DOI:10.1145/321296.321305.
  2. ^ a b c Alfio Quarteroni, Riccardo Sacco e Fausto Saleri, Numerical mathematics, 2ª ed., Springer, ISBN 978-3-540-49809-4.
  3. ^ a b c d e f g h i j k l m Homer F. Walker e Peng Ni, Anderson Acceleration for Fixed-Point Iterations, in SIAM Journal on Numerical Analysis, vol. 49, n. 4, gennaio 2011, pp. 1715–1735, DOI:10.1137/10078356X.
  4. ^ a b c d e f g Haw-ren Fang e Yousef Saad, Two classes of multisecant methods for nonlinear acceleration, in Numerical Linear Algebra with Applications, vol. 16, n. 3, marzo 2009, pp. 197–221, DOI:10.1002/nla.617.
  5. ^ Claire Evans, Sara Pollock e Leo G. Rebholz, A Proof That Anderson Acceleration Improves the Convergence Rate in Linearly Converging Fixed-Point Methods (But Not in Those Converging Quadratically), in SIAM Journal on Numerical Analysis, vol. 58, n. 1, 20 febbraio 2020, pp. 788–810, DOI:10.1137/19M1245384.
  6. ^ V. Eyert, A Comparative Study on Methods for Convergence Acceleration of Iterative Vector Sequences, in Journal of Computational Physics, vol. 124, n. 2, marzo 1996, pp. 271–285, DOI:10.1006/jcph.1996.0059.
  7. ^ C. G. Broyden, A class of methods for solving nonlinear simultaneous equations, in Mathematics of Computation, vol. 19, n. 92, 1965, pp. 577–577, DOI:10.1090/S0025-5718-1965-0198670-6.
  8. ^ a b C. W. Oosterlee e T. Washio, Krylov Subspace Acceleration of Nonlinear Multigrid with Application to Recirculating Flows, in SIAM Journal on Scientific Computing, vol. 21, n. 5, gennaio 2000, pp. 1670–1690, DOI:10.1137/S1064827598338093.
  9. ^ Péter Pulay, Convergence acceleration of iterative sequences. the case of scf iteration, in Chemical Physics Letters, vol. 73, n. 2, luglio 1980, pp. 393–398, DOI:10.1016/0009-2614(80)80396-4.
  10. ^ P. Pulay, ImprovedSCF convergence acceleration, in Journal of Computational Chemistry, vol. 3, n. 4, 1982, pp. 556–560, DOI:10.1002/jcc.540030413.
  11. ^ Neil N. Carlson e Keith Miller, Design and Application of a Gradient-Weighted Moving Finite Element Code I: in One Dimension, in SIAM Journal on Scientific Computing, vol. 19, n. 3, maggio 1998, pp. 728–765, DOI:10.1137/S106482759426955X.
  12. ^ Keith Miller, Nonlinear Krylov and moving nodes in the method of lines, in Journal of Computational and Applied Mathematics, vol. 183, n. 2, novembre 2005, pp. 275–287, DOI:10.1016/j.cam.2004.12.032.
  13. ^ J. W. Daniel, W. B. Gragg e L. Kaufman, Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization, in Mathematics of Computation, vol. 30, n. 136, ottobre 1976, pp. 772–772, DOI:10.1090/S0025-5718-1976-0431641-8.