无主元LU分解变体算法实现问询：行建L与列建U代码补全

云原生阿岚

2026-6-17

无主元LU分解变体算法补全

要实现无主元LU分解的变体，对n×n矩阵A进行原地覆盖存储——严格下三角部分（不含主对角线）存储L（单位下三角矩阵，对角线元素为1），上三角部分存储U。

经典实现参考

# classical implementation (originated in gaussian-elimination)
for i = 1, ..., n-1 do 
    for j = i + 1, …, n do
        A_j,i = A_j,i / A_i,i;              # update L
        for k = i + 1, …, n do
            A_j,k = A_j,k - A_j,i * A_i,k;  # update U
        end for
    end for
end for

变体算法补全

你提到的变体采用行式构建L、列式构建U，且每个非平凡元素仅修改一次。结合LU分解的数学定义，补全后的算法如下：

L元素更新逻辑

对于严格下三角位置(i,j)（i>j），根据矩阵乘法等式A = L*U推导可得：需要先减去已计算的L元素与对应U元素的乘积和，再除以U的主元A_j,j，代码实现如下：

temp = A_i,j
for k = 1, …, j - 1 do
    temp -= A_i,k * A_k,j
end for
A_i,j = temp / A_j,j;

U元素更新逻辑

你猜测的U更新代码是正确的：对于上三角位置(j+1,i)（j+1 < i），通过消去L的贡献得到U的最终值：

A_j+1,i = A_j+1,i - A_j+1,k * A_k,i;

完整变体代码

# variant
for i = 2, ..., n do 
    for j = 1, …, i - 1 do
        # 更新L的元素A[i][j]
        temp = A_i,j
        for k = 1, …, j - 1 do
            temp -= A_i,k * A_k,j
        end for
        A_i,j = temp / A_j,j;
        
        # 更新U的元素A[j+1][i]
        for k = 1, …, j do
            A_j+1,i = A_j+1,i - A_j+1,k * A_k,i;
        end for
    end for
end for