Neúplná Choleského faktorizace - Incomplete Cholesky factorization - Wikipedia

v numerická analýza, an neúplná Choleského faktorizace symetrické pozitivní určitá matice je řídký aproximace Choleského faktorizace. Neúplná Choleského faktorizace se často používá jako a kondicionér pro algoritmy jako metoda sdruženého gradientu.

Choleského faktorizace kladné určité matice A je A = LL* kde L je dolní trojúhelníková matice. Neúplná Choleského faktorizace je dána řídkou spodní trojúhelníkovou maticí K. to je v jistém smyslu blízké L. Odpovídající předpoklad je KK*.

Jeden populární způsob, jak najít takovou matici K. je použít algoritmus k nalezení přesného Choleského rozkladu, kromě toho, že jakýkoli záznam je nastaven na nulu, pokud je odpovídající záznam v A je také nula. To dává neúplnou Choleského faktorizaci, která je stejně řídká jako matice A.

Algoritmus

Pro ${ displaystyle i}$ z ${ displaystyle 1}$ na ${ displaystyle N}$:

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

Pro ${ displaystyle j}$ z ${ displaystyle i + 1}$ na ${ displaystyle N}$:

${ displaystyle L_ {ji} = {1 nad {L_ {ii}}} vlevo ({a_ {ji} - sum limity _ {k = 1} ^ {i-1} {L_ {ik} L_ {jk}}} vpravo)}$

Implementace

Implementace neúplné Choleského faktorizace ve skriptovacím jazyce Octave. Faktorizace je uložena jako spodní trojúhelníková matice, přičemž prvky v horním trojúhelníku jsou nastaveny na nulu.

funkceA =ichol(A)	n = velikost(A,1);	pro k=1:n		A(k,k) = čtv(A(k,k));		pro i=(k+1):n		    -li (A(i,k)!=0)		        A(i,k) = A(i,k)/A(k,k);            		    endif		konec		pro j=(k+1):n		    pro i=j:n		        -li (A(i,j)!=0)		            A(i,j) = A(i,j)-A(i,k)*A(j,k);  		        endif		    konec		konec	konec    pro i=1:n        pro j=i+1:n            A(i,j) = 0;        konec    konec            koncová funkce

Reference

• Neúplná Choleského faktorizace na CFD Online wiki
• Golub, Gene H.; Van Loan, Charles F. (1996), Maticové výpočty (3. vydání), Johns Hopkins, ISBN  978-0-8018-5414-9. Viz část 10.3.2.

Tento aplikovaná matematika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.