Cholesky分解法解对称正定线性方程组
题目描述
给定一个n×n的对称正定矩阵A和一个n维向量b，求解线性方程组Ax = b。要求使用Cholesky分解法，将矩阵A分解为下三角矩阵L和其转置L^T的乘积（A = LL^T），然后通过前代和回代法求解x。
解题过程
-
对称正定矩阵的判断
- 对称性：矩阵A必须满足A^T = A，即矩阵元素关于主对角线对称（a_ij = a_ji）。
- 正定性：对于任意非零向量x，都有x^TAx > 0。在实际计算中，我们通过Cholesky分解过程本身来验证：如果分解过程中所有对角元素l_kk的平方根计算都涉及正数，则矩阵正定。
-
Cholesky分解（A = LL^T）
我们的目标是将矩阵A分解成一个下三角矩阵L和其转置L^T的乘积。分解按列（或行）依次进行。-
步骤1：计算L的第一列
L矩阵的第一列只有一个非零元素l_11，它由A的第一个对角元素决定：
l_11 = √(a_11)
然后，L的第一列其他元素（从第二行开始）均为0。 -
步骤2：计算L的第二列
对于第二列，我们需要计算两个元素：
l_21 = a_21 / l_11 （利用A的第二行第一列元素和已知的l_11）
l_22 = √(a_22 - l_21²) （计算第二列第二个元素，需要减去已计算部分的影响） -
步骤3：通用公式（计算第j列）
对于任意第j列（j从1到n）：- 对于当前列j中的每个元素l_ij（其中i从j到n，且i >= j），我们分两种情况：
- 当i = j时（即对角元素）：
l_jj = √( a_jj - Σ_{k=1}^{j-1} l_jk² )
这里，Σ_{k=1}^{j-1} l_jk² 表示对第j行中，从第1列到第j-1列的所有已求出的l_jk进行平方和求和。这确保了分解的准确性。 - 当i > j时（即对角线下方的非对角元素）：
l_ij = ( a_ij - Σ_{k=1}^{j-1} l_ik l_jk ) / l_jj
这里，Σ_{k=1}^{j-1} l_ik l_jk 表示对第i行和第j行中，从第1列到第j-1列的对应元素乘积求和。
- 当i = j时（即对角元素）：
通过这个递推过程，我们可以逐步填充下三角矩阵L的所有非零元素。
- 对于当前列j中的每个元素l_ij（其中i从j到n，且i >= j），我们分两种情况：
-
-
求解线性方程组 Ly = b（前代法）
将原方程Ax = b转化为(LL^T)x = b。
首先，令y = L^T x，则原方程变为Ly = b。
由于L是下三角矩阵，我们可以通过前代法（Forward Substitution）轻松求解y。- 通用公式：
对于i从1到n：
y_i = ( b_i - Σ_{k=1}^{i-1} l_ik y_k ) / l_ii
这里，Σ_{k=1}^{i-1} l_ik y_k 是对于第i行，将已经求出的y_1到y_{i-1}与对应的系数l_i1到l_{i,i-1}相乘并求和。
- 通用公式：
-
求解线性方程组 L^T x = y（回代法）
得到y之后，我们求解L^T x = y。
由于L^T是上三角矩阵，我们可以通过回代法（Back Substitution）求解x。- 通用公式：
对于i从n到1（逆序）：
x_i = ( y_i - Σ_{k=i+1}^{n} l_ki x_k ) / l_ii
注意：这里的l_ki来自L^T，实际上就是原始下三角矩阵L中的l_ik。所以公式通常写作：
x_i = ( y_i - Σ_{k=i+1}^{n} l_ik x_k ) / l_ii
这里，Σ_{k=i+1}^{n} l_ik x_k 是对于第i个方程，将已经求出的x_{i+1}到x_n与对应的系数（在L^T中，即L中的l_i,i+1到l_in）相乘并求和。
- 通用公式：
总结
Cholesky分解法通过利用对称正定矩阵的特殊结构，将一个复杂的矩阵求逆问题转化为两次简单的三角矩阵求解过程（前代和回代）。这种方法比普通的LU分解计算量更小（大约节省一半的计算量），数值稳定性也更好。关键在于成功完成A = LL^T的分解。