Precedente Indice Successivo


Lups

Scopo: fattorizzazione di una matrice quadrata in due matrici triangolari, con applicazione del pivoting scalato.
Specifiche: subroutine lups (a, lds, n, ipiv, s, ifail)
integer lda, n, ipiv(n), ifail
real a(lda, n), s(n)
Descrizione:

Backgroud del problema

Il problema è quello dell'eliminazione gaussiana per una matrice quadrata A secondo la formula P*A=L*U con P matrice delle permutazioni, L matrice triangolare inferiore ed U triangolare superiore.

Descrizione dell'algoritmo

L'algoritmo che implementa lups, si differenzia da quello implementante lup per la strategia di pivot, che è di tipo scalato. In pratica al pivot parziale si affianca la determinazione dell'ordine di grandezza di ogni riga per consentire la scalatura del problema di ricerca del pivot. Il pivoting è simulato, cioè, l'applicazione del pivot alla matrice avviene, virtualmente, con un vettore di interi (ipiv) nel quale si memorizza l'ordine effettivo delle righe. L'algoritmo, per una migliore efficienza, lavora sulle colonne della matrice.

Raccomandazioni sull'uso

Si raccomanda che la matrice da fattorizzare non sia singolare, in modo da poter applicare l'eliminazione di Gauss. Per problemi legati all'allocazione in memoria di array bidimensionali in fortran, la dimensione lda deve essere uguale alla dimensione di riga della matrice dichiarata nel programma chiamante. Per ridurre la complessità di spazio la subroutine memorizza nel triangolo superiore della matrice di ingresso la matrice triangolare U, in quello inferiore la matrice triangolare L, la matrice di ingresso è, quindi, persa. Il vettore ipiv è impiegato per permutare le righe della matrice in uscita, in modo da "ricostruire" la matrice fattorizzata. Il vettore s conterrà la norma infinito di ciascuna riga della matrice da fattorizzare.

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

matrice di reali, matrice da fattorizzare
lda - intero, leading dimension
n - intero, ordine della matrice

output

a - matrice di reali, matrice fattorizzata
ipiv - vettore di interi, vettore delle permutazioni
s - vettore di reali, norma infinito delle righe
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 = 4 la matrice inserita è singolare
Routines ausiliarie: nessuna.
Tempo d'esecuzione: la complessità di tempo è somma di due contributi separati, quello del pivoting e quello dell'eliminazione. Il primo è pari a O(n2/2), il secondo è pari a O(n3/3)
Memoria richiesta: si dichiarano una matrice di reali di dimensione lda*n, un array di interi e un array di reali, entrambi di dimensione n.
Accuratezza fornita: metodo esatto a meno del condizionamento della matrice e degli errori di round-off.
Esempio di programma chiamante: 
       Program lupsd 
 c     Programma dimostrativo della subroutine lups 

       external lups 
        
       integer dim 
       parameter (dim=6) 
       real a(dim,dim),s(dim) 
       integer ipiv(dim),n,ifail 
       character*12 fin,fout 
         
       print* 
       print*,'*** PROGRAMMA DIMOSTRATIVO DELLA SUBROUTINE LUPS ***' 
       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 2 i=1,n 
          do 1 j=1,n 
             read(11,*)a(i,j) 
     1    continue 
     2 continue   
       close(11) 
        
       call lups(a,dim,n,ipiv,s,ifail) 
         
       if (ifail .eq. 3) stop 'Errore! dimensione non valida' 
       if (ifail .eq. 4) stop 'Errore! matrice singolare' 
         
       print*,'Nome del file di output= ' 
       read(*,'(A)')fout 
       open(12,FILE=fout) 
       write(12,20)((a(i,j),j=1,n),i=1,n) 
       write(12,*) 
       write(12,30)(ipiv(i),i=1,n) 
       close(12)  
        
       print*,'Matrice fattorizzata= ' 
       write(*,20)((a(ipiv(i),j),j=1,n),i=1,n) 
          
    10 format (1X,A,I2,A) 
    20 format (1X,E14.7)   
    30 format (1X,I3) 

       End




Precedente Indice Successivo