Неполная факторизация Холецкого - Incomplete Cholesky factorization

В числовой анализ, неполная факторизация Холецкого симметричной положительно определенная матрица это редкий приближение Факторизация Холецкого. Неполная факторизация Холецкого часто используется как предварительный кондиционер для таких алгоритмов, как метод сопряженных градиентов.

Факторизация Холецкого положительно определенной матрицы А является А = LL* куда L это нижняя треугольная матрица. Неполная факторизация Холецкого задается разреженной нижней треугольной матрицей K это в некотором смысле близко к L. Соответствующий предобуславливатель KK*.

Один из популярных способов найти такую ​​матрицу K заключается в использовании алгоритма нахождения точного разложения Холецкого, за исключением того, что любая запись обнуляется, если соответствующая запись в А также равен нулю. Это дает неполную факторизацию Холецкого, которая столь же разрежена, как и матрица А.

Алгоритм

За ${\displaystyle i}$ из ${\displaystyle 1}$ к ${\displaystyle N}$:

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

За ${\displaystyle j}$ из ${\displaystyle i+1}$ к ${\displaystyle N}$:

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

Выполнение

Реализация неполной факторизации Холецкого в скриптовом языке Octave. Факторизация сохраняется как нижняя треугольная матрица с нулевыми элементами в верхнем треугольнике.

функцияа =ихол(а)	п = размер(а,1);	за k=1:п		а(k,k) = sqrt(а(k,k));		за я=(k+1):п		    если (а(я,k)!=0)		        а(я,k) = а(я,k)/а(k,k);            		    endif		конец		за j=(k+1):п		    за я=j:п		        если (а(я,j)!=0)		            а(я,j) = а(я,j)-а(я,k)*а(j,k);  		        endif		    конец		конец	конец    за я=1:п        за j=я+1:п            а(я,j) = 0;        конец    конец            конечная функция

Рекомендации

• Неполная факторизация Холецкого в CFD Online wiki
• Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996), Матричные вычисления (3-е изд.), Джонс Хопкинс, ISBN  978-0-8018-5414-9. См. Раздел 10.3.2.