Неполная факторизация Холецкого - Википедия - 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 более 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.

Этот Прикладная математика -связанная статья является заглушка. Вы можете помочь Википедии расширяя это.