Metodi numerici

3ω. 3.2.5 Metodi numerici

Normalmente, i problemi agli autovalori tipici della chimica quantistica sono caratterizzati da matrici di dimensioni che vanno da poche decine a molti milioni. I metodi di risoluzione numerica implementati direttamente in molti applicativi, sia proprietari che open source, fanno uso di algoritmi complessi, che si basano su alcune tecniche generali volte alla riduzione della matrice analizzata in forme più maneggevoli (per esempio, tipicamente, in forma tridiagonale), per il calcolo diretto analitico o seminalitico degli autovalori e degli autovettori, o di osservabili dipendenti dagli autovalori ed autovettori. Per applicazioni avanzate, l’uso di librerie di calcolo specifiche all’interno di codici sviluppati ad hoc è di prammatica. Ricordiamo tra tutte EISPACK (in Fortran), e LAPACK (in C++, Fortran90) disponibili presso www.netlib.org, le librerie proprietarie IMSL, NAG etc.

In pratica, la selezione della routine di soluzione per il problema di interesse dipende dal problema in esame, cioè in ultima analisi dalla natura della matrice che deve essere diagonalizzata: dal caso più semplice di una matrice reale simmetrica definita sino al caso più complicato di una matrice complessa non hermitiana. Anche il tipo di esito può essere diverso da problema a problema: esistono algoritmi, per esempio, per il calcolo di soli autovalori, ed anche di soli autovalori estremi (minimi o massimi). Per esempio, possiamo essere interessati alle sole proprietà di stato fondamentale di una molecola, nel qual caso il calcolo dell’autovalore minimo è sufficiente. Come per la soluzione dei sistemi di equazioni lineari (ma ciò non è sorprendente, perchè i due problemi sono in fondo intimamente collegati), il caso delle matrici sparse dovrebbe poi essere sempre trattato in modo diverso dal caso delle matrici dense, per trarre vanatggio dalla loro struttura particolare e poter trattare problemi di dimensioni molto grandi.

Nel caso di matrici reali simmetriche gli algoritmi a disposizioni sono numerosi, stabili e molto efficienti. Per matrici aventi dimensioni dell’ordine di qualche decina al massimo, può essere utile l’algoritmo di Jacobi, un approccio iterativo che trasforma la matrice originaria in una matrice diagonale mediante una serie di trasformazioni di similitudine

D_k= GkD_k−1G^T_k (3.79)

la matrice (ortogonale) G_k ha la forma di una matrice di Givens

G(i, j, θ) =           1 . . . 0 . . . 0 . . . 0 . . . 0 . . . cos θ . . . sin θ . . . 0 . . . 0 . . . − sin θ . . . cos θ . . . 0 . . . 0 . . . 0 . . . 0 . . . 1           (3.80)

dove il coseno ed il seno di un angolo θ compaiono all’intersezione dell’i-esima riga e della j-esima colonna (in breve, nel seguito, posizione ij). Una matrice di Givens applicata ad un generico vettore x lo ruota di un angolo θ nel piano (i, j). Applicata alla matrice simmetrica D_k−1 la trasforamzione produce una nuova matrice simmetrica D_k con l’elemento nella posizione ij dato dall’espressione

(D_k)_ij = (D_k−1)_ijcos 2θ + ¹

se si sceglie tan 2θ = ^2(Dk−1)ij

(D_k−1)_ii− (D_k−1)_jj^{, l’elemento (Dk)ij va a zero. L’algoritmo quindi procede nel} modo seguente

1. ad ogni nuova iterazione, si cerca l’elemento più grande in valore assoluto della matrice (D_k−1)_ij, detto (come in precedenza) pivot

2. si applica la trasformazione di similitudine per ottenere la nuova matrice D_k con (D_k)ij azzerato Per k → ∞ la matrice D_k tende ad una matrice diagonale, cioè alla matrice degli autovalori (la matrice dei prodotti delle trasformazioni tende alla matrice degli autovettori) della matrice originaria.

Un approccio simile consiste nella riduzione, tramite una serie di trasformazioni, della matrice originaria ad una forma tridiagonale. Le matrici tridiagonali (vedi sopra) sono particolarmente ’facili’ da diagonalizzare, con algoritmi ad hoc. Di conseguenza, la strategia numerica di elezione nel caso si debba risolvere un problema agli autovalori con una matrice di dimensioni superiore al centinaio, e come vedremo fra breve soprattutto nel caso di matrici molto grandi sparse, è quella 1) di portare la matrice ad una forma tridiagonale e 2) di risolvere il problema agli autovalori con la nuova matrice tridiaonale. Una delle tecniche più usate per la tridiagonalizzazione è la procedura di Householder, una serie di trasformazioni che sistematicamente annulla la parte di colonna i-esima e di riga i-esima corrispondente alla posizione diagonale ii, lasciando solo come elementi non nulli quelli appartenenti alla diagonale superiore ed inferiore, portando quindi alla fine alla formazione di una matrice tridiagonale.

Una metodologia per la tridiagonalizzazione di matrici sparse particolarmente efficiente è invece dato dalla famiglia di approcci basati sull’algoritmo di Lanczos, che per la sua facilità di implementazione è applicato con frequenza alla soluzione di problemi agli autovalori nell’ambito della chimica quantistica, direttamente o in forme modificate.

Approfondimento 8. Supponiamo di voler trasformare la matrice generica A (reale simmetrica per sem-plicià) in forma tridiagonale. Sia v₁ un vettore che possiamo anche scegliere in modo arbitrario. Generiamo la sequenza di vettori v_k come segue

β_k+1v_k+1 = (A − α_k) v_k− β_kv_k−1

α_k = v^T_kAv_k (3.81)

β_k = v^T_kAv_k−1

I vettori v₁, v₂ etc. sono ortonormali (almeno in precisione infinita, cioè in assenza di errori di arroton-damento) e formano una matrice ortogonale V = (v₁, v2, . . . , vn)^T tale che VAV^T = T, dove T è la matrice tridiagonale (simmetrica)

T =         α₁ β₁ β₁ α₂ β₂ β2 . .. . .. . .. . .. β_n−1 β_n−1 α_n         (3.82)

Supponiamo di volere calcolare la grandezza scalare j(s) = v₁(s + A)⁻¹v₁ (si tratta di un’espressione, detta nel contesto densità spettrale, che si ottiene spesso nell’ambito della spettroscopia computazionale come risultato di elaborazione teoriche volte a calcolare sull’asse delle frequenze generiche s un segnale spettroscopico. In questo caso si ha che j(s) = eT

1(s + A)⁻¹v₁ dove e₁ è la colonna e₁ = (1, 0, . . . , 0)^T. L’espressione si può scrivere direttamente sotto forma di frazione continua

j(s) = ¹ s − α₁− ^β 2 1 s − α₂− ^β 2 2 s − α₃+ . . . (3.83)

I coefficienti della matrice T si ottengono direttamente dalla sequenza di operazioni di moltiplcazione matrice-vettore (3.81): opportunamente ottimizzati nel caso di matrici sparse, questi prodotti sono computa-zionalmente poco costosi. La matrice tridiagonale ottenuta può essere diagonalizzata impiegando algoritmi specifici, anch’essi a basso costo computazionale, come per esempio il metodo di decomposizione QR o QL. Il metodo di decomposizione QR (QL) permette di ridurre una matrice generica alla forma A = QR (A = QL, dove Q è ortogonale e R (L) è triangolare superiore (inferiore). La procedura di decomposizione è accompagnata dalla generazione di una nuova matrice simile alla precedente usando Q come matrice di trasformazione. La sequenza tende a generare la matrice diagonale degli autovalori. In pratica si procede come segue

1. si decompone A₀ = A = QR 2. si genera A₁ = RQ = Q^TA₀Q

3. si continua decomponendo ad ogni iterazione A_k = Q_kR_ke generando A_k+1 = RkQ_k= Q^T_kA_kQ_k Se per una matrice ’normale’ di dimensioni n il costo computazionale cresce come O(n3), nel caso di una matrice tridiagonale il costo è solo O(n) rendendo l’algoritmo molto conveniente.

Integrazione di funzioni

4.1 Definizioni

In questo (breve) capitolo saranno discussi i metodi di integrazione analitici e numerici più comuni, come sempre nel contesto di alcuni problemi di interesse generale per il chimico.