Precedente Indice Successivo


Chol

Scopo: fattorizzazione di Cholesky di una matrice A simmetrica definita positiva
Specifiche: subroutine chol(a, l, n, ifail)
integer n,ifail
real a(n * (n+1)/2), l(n* (n+1)/2)
Descrizione: Backgroud del problema

Il problema riguarda la fattorizzazione di una matrice quadrata. Nel caso in cui la matrice sia simmetrica 'definita positiva', il procedimento risulta semplificato per due ragioni: non è necessario pivoting ed è possibile operare solo sul triangolo inferiore della matrice, essendo quello superiore il trasposto dell'inferiore. Pertanto, la fattorizzazione della matrice consisterà nel prodotto di due matrici L e Lt, la prima triangolare inferiore, la seconda trasposta della prima. La determinazione degli elementi della matrice L={lij} avviene nel seguente modo:

La matrice in ingresso deve essere 'definita positiva' , perché in caso contrario, nella (3.1) si calcolerebbero radici complesse e nella (3.2) si eseguirebbero divisioni per zero, rendendo in entrambi i casi impossibile l'applicazione dell'algoritmo.

Descrizione dell'algoritmo

Caratteristica fondamentale dell'algoritmo è quella di operare non su di una matrice n*n, ma su di un vettore di lunghezza n*(n+1)/2 (array in formato packed) ottenendo così una diminuzione notevole della complessità sia di tempo che di spazio.

Raccomandazioni sull'uso

Se si desidera fattorizzare una matrice AÎ Mnxn(R)è necessario che questa sia simmetrica e definita positiva; bisogna fornire in ingresso un vettore di lunghezza n*(n+1)/2 contenente solo gli elementi del triangolo inferiore della matrice da fattorizzare, compresi quelli della diagonale, ordinati per righe. In uscita la subroutine fornirà un vettore contenente gli elementi della matrice L, triangolare inferiore, tale che A=L*Lt.

Bibliografia: [1], [2]
Parametri di I/O: input
a - vettore di reali, elementi del triangolo inferiore di A
n - intero, ordine della matrice

output
l - vettore di reali, elementi del triangolo inferiore di L
ifail - intero, indicatore d'errore

Indicatori d'errore: Errori gestiti dalla subroutine: ifail = 0 nessun errore
ifail = 3 la dimensione inserita non è valida
ifail = 5 la matrice inserita non è positiva definita
Routines ausiliarie: nessuna
Tempo d'esecuzione: La complessità asintotica O(n3/6)
Memoria richiesta: sono dichiarati due array di dimensione n*(n+1)/2
Accuratezza fornita: metodo esatto a meno del condizionamento della matrice e degli errori di round-off
Esempio di programma chiamante: 
      Program chold
c     Programma dimostrativo della subroutine chol

      external chol

      integer dim
      parameter (dim=100)

      real a(dim*(dim+1)/2),l(dim*(dim+1)/2)
      integer n,ifail
      character*12 fin,fout

      print*
      print*,'*** PROGRAMMA DIMOSTRATIVO DELLA SUBROUTINE CHOL ***'
      print*
      write(*,10)'Ordine della matrice (max ',dim,') = '
      read(*,*)n

      print*,'Nome del file di input = '
      read(*,'(A)')fin
      open(11,FILE=fin,STATUS='OLD')
      do 1 i=1,n*(n+1)/2
      read(11,*)a(i)
      1 continue
      close(11)

      call chol(a,l,n,ifail)

      if (ifail .eq. 3) stop 'Errore! dimensioni non valide'
      if (ifail .eq. 5) stop 'Errore! matrice non definita positiva'

      print*,'Nome del file di output = '
      read(*,'(A)')fout
      open(12,FILE=fout)
      write(12,20)(l(i),i=1,n*(n+1)/2)
      close(12)

      print*,'Matrice fattorizzata = '
      write(*,20)(l(i),i=1,n*(n+1)/2)

   10 format (1X,A,I3,A)
   20 format (1X,E14.7)
     
      End




Precedente Indice Successivo