Ofullständig Cholesky-faktorisering

I numerisk analys är en ofullständig Cholesky-faktorisering av en symmetrisk positiv bestämd matris en sparsam approximation av Cholesky-faktoriseringen . En ofullständig Cholesky-faktorisering används ofta som en förutsättning för algoritmer som den konjugerade gradientmetoden .

Cholesky-faktoriseringen av en positiv bestämd matris A är A = LL * där L är en lägre triangulär matris . En ofullständig Cholesky-faktorisering ges av en gles nedre triangulär matris K som i någon mening är nära L . Motsvarande förkonditionerare är KK *.

Ett populärt sätt att hitta en sådan matris K är att använda algoritmen för att hitta den exakta Cholesky-sönderdelningen där K har samma sparsitetsmönster som A (vilket som helst inmatning av K sätts till noll om motsvarande post i A också är noll). Detta ger en ofullständig Cholesky-faktorisering som är lika gles som matrisen A .

Algoritm

För $i$ från $1$ till $N$ :

$L_{ii}=\left({a_{ii}-\sum \limits _{k=1} ^{i-1}{L_{ik}^{2}}}\right)^{1 \over 2}$

För $j$ från $i+1$ till ${\ displaystyle N}$ :

$L_{ji}={1 \over {L_{ii}}} \left({a_{ji}-\sum \limits _{k=1}^{i-1}{L_{ik}L_{jk}}}\right)$

Genomförande

Implementering av den ofullständiga Cholesky-faktoriseringen i skriptspråket Octave. Faktoriseringen lagras som en nedre triangulär matris, med elementen i den övre triangeln nollställda.

   
	  

	 
		  
		 
		     0
		                      
		    
		
		 
		     
		         0
		                
		        
		    
		
	

     
         
              0
        
                
 funktion  a  =  ichol  (  a  )  n  =  storlek  (  a  ,  1  );  för  k  =  1  :  n  a  (  k  ,  k  )  =  sqrt  (  a  (  k  ,  k  ));  för  i  =(  k  +  1  ):  n  om  (  a  (  i  ,  k  )  !=  )  a  (  i  ,  k  )  =  a  (  i  ,  k  )  /  a  (  k  ,  k  );  endif  endfor  för  j  =(  k  +  1  ):  n  för  i  =  j  :  n  if  (  a  (  i  ,  j  )  !=  )  a  (  i  ,  j  )  =  a  (  i  ,  j  )  -  a  (  i  ,  k  )  *  a  (  j  ,  k  );  endif  endfor  endfor  endfor  för  i  =  1  :  n  för  j  =  i  +  1  :  n  a  (  i  ,  j  )  =  ;  endfor  endfor  endfunction 

• Ofullständig Cholesky-faktorisering på CFD Online-wiki
•   Golub, Gene H .; Van Loan, Charles F. (1996), Matrix Computations (3:e upplagan), Johns Hopkins, ISBN 978-0-8018-5414-9 . Se avsnitt 10.3.2.