不完全 Cholesky 分解算法

计算科学 线性代数 矩阵分解
2021-12-25 06:20:53

我想实现不完整的 Cholesky 分解来进行前置条件,我从不完整的 Cholesky 分解中引用的算法,

function a = ichol(a)
    n = size(a,1);

    for k=1:n
        a(k,k) = sqrt(a(k,k));
        for i=(k+1):n
            if (a(i,k)!=0)
                a(i,k) = a(i,k)/a(k,k);            
            endif
        endfor
        for j=(k+1):n
            for i=j:n
                if (a(i,j)!=0)
                    a(i,j) = a(i,j)-a(i,k)*a(j,k);  
                endif
            endfor
        endfor
    endfor

    for i=1:n
        for j=i+1:n
            a(i,j) = 0;
        endfor
    endfor            
endfunction

但这似乎不对。

问题是算法不能保证它a[k,k]是一个正整数。a[k,k]不是正整数时,算法会产生错误。

我想询问正确版本的 Cholesky 分解和一些相关参考资料。

1个回答

Cholesky 分解适用于正定矩阵(对于正半定,分解存在,但不是唯一的)。正定性是确保它a[k,k]是一个正数并且sqrt是可以的(例如,参见关于那个的 Wiki 解释)。

不完整的 Cholesky 分解也发生了类似的情况,因为它的适用性也仅限于正定矩阵。

您遇到问题的事实是由于您尝试分解的矩阵不具备 Cholesky 分解族所需的属性(很可能)或矩阵在数值过程中失去其正定性(非常不可能) .

因此,上面用于不完全 Cholesky 分解的代码是正确的。

在您的情况下,我建议研究不完整的 LU 分解,它有点重,但对它所应用的矩阵的期望较少。它是一种常见的因式分解,可用于许多类型的预条件子,其中涉及非正定矩阵。

或者,如果您可以对正在分解的矩阵进行更改(例如,您正在处理一个先决条件),这将强制其正定性,它可能是一个更好的选择。