Precedente Indice Successivo



Schol


Scopo: risoluzione di un sistema lineare A*x=b, con A matrice simmetrica definita positiva.
Specifiche: Subroutine schol(l, b, n, ifail)
integer n, ifail
real l(n*(n+1)/2), b(n)
Descrizione: Backgroud del problema

Il problema è relativo alla risoluzione di un sistema lineare A*x=b, con A matrice simmetrica definita positiva. Viste le caratteristiche di simmetria della matrice A, si effettua la fattorizzazione di Cholesky di A in modo da ottenere una matrice L, triangolare inferiore tale che A=L*Lt. In questo modo la risoluzione del sistema A*x=b è ricondotto alla risoluzione di (L*Lt)*x=b, al quale sono applicabili gli algoritmi di forward e backward substitution.

Descrizione dell'algoritmo

Caratteristica 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), contenente una matrice triangolare inferiore ottenuta dalla fattorizzazione di Cholesky della matrice A, ottenendo così una diminuzione notevole della complessità sia di tempo che di spazio. Per risolvere il sistema (L*Lt)*x=b l'algoritmo esegue prima una forward substitution per risolvere il sistema L*y=b e poi una backward substitution per il sistema Lt*x=y. La forward e la backward substitution sono implementate nella versione colonna. Per effettuare la backward substitution occorrerebbe calcolare Lt, trasposta di L, ma in realtà si opera sempre sulla matrice L.

Raccomandazioni sull'uso

Il vettore l deve contenere la fattorizzazione di A eseguita dalla subroutine Chol e non deve essere singolare. In uscita il vettore b conterrà la soluzione del sistema, quindi è opportuno salvare b se è necessario per ulteriori elaborazioni.

Bibliografia: [1], [2]
Parametri di I/O: input

l- matrice di reali, matrice dei coefficienti
b - vettore di reali, vettore dei termini noti
n - intero, ordine del sistema

output

b - vettore di reali, soluzione del sistema
ifail - intero, indicatore d'errore
Indicatori d'errore: Errori gestiti dalla subroutine:
ifail = 0 nessun errore
ifail = 3 la dimensione inserita è non positiva o è superiore a ldlu
ifail = 5 la matrice inserita non è definita positiva
Routines ausiliarie: nessuna
Tempo d'esecuzione: complessità asintotica O(n2)
Memoria richiesta: sono allocati un vettore n*(n-1)/2 , e un vettore di dimensione n.
Accuratezza fornita: metodo esatto a meno del condizionamento della matrice e degli errori di round-off
Esempio di programma chiamante: 
      Program schold

c     Programma dimostrativo della subroutine schol

      external schol
      
      integer dim
      parameter (dim=100)
       
      real l(dim*(dim+1)/2), b(dim)
      integer n,ifail
      character*12 fin,fout
                                               
      print*
      print*,'*** PROGRAMMA DIMOSTRATIVO DELLA SUBROUTINE SCHOL ***'
      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,*)l(i)             
    1 continue

      do i=1, n
          read(11,*)b(i)                
      end do
      close(11)            

      call schol(l,b,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)(b(i),i=1,n)
      close(12)                            
                  
      print*,'Soluzione del sistema = '
      write(*,20)(b(i),i=1,n)
        
   10 format (1X,A,I3,A)
   20 format (1X,E14.7)


Precedente Indice Successivo