LU分解法解线性方程组

题目描述：
给定一个n阶可逆方阵A和一个n维向量b，我们需要求解线性方程组Ax = b。要求使用LU分解法，将矩阵A分解为一个下三角矩阵L和一个上三角矩阵U的乘积，即A = LU。然后通过求解两个三角方程组Ly = b和Ux = y来得到原方程组的解x。

解题过程：

第一步：理解LU分解法的核心思想
LU分解法的基本思路是将一个复杂的矩阵A分解为两个结构简单的三角矩阵L和U的乘积。这样，求解原方程组Ax = b就转化为依次求解两个易于处理的三角方程组：

1. 前向代入：求解下三角方程组 Ly = b，得到中间向量y。
2. 后向代入：求解上三角方程组 Ux = y，得到最终解向量x。

第二步：进行LU分解
这是该方法最关键的一步。我们的目标是为矩阵A找到L和U，使得A = LU。

• L（下三角矩阵）：主对角线上的元素全为1，主对角线以上的元素全为0。
• U（上三角矩阵）：主对角线以下的元素全为0。

我们使用高斯消元法的过程来构造L和U。这个过程是逐步进行的，通过初等行变换将A化为上三角矩阵U，同时记录下所有的行变换乘数，这些乘数就构成了L的元素。

具体步骤（以3x3矩阵为例，假设主元均不为零）：

1. 第一步消元：目标是消除第一列中第2行和第3行的元素。

   • 计算乘数：
     • l21 = A[2,1] / A[1,1] （用于消除第2行第1列的元素）
     • l31 = A[3,1] / A[1,1] （用于消除第3行第1列的元素）
   • 执行行变换：
     • 第2行新值 = 第2行原值 - l21 × 第1行
     • 第3行新值 = 第3行原值 - l31 × 第1行
   • 经过这一步，我们得到了一个中间矩阵A^(1)，其第一列主元以下元素已为零。此时，L矩阵的第一列（主对角线以下部分）就由这些乘数填充：L[2,1] = l21, L[3,1] = l31。

2. 第二步消元：在A^(1)的基础上，消除第二列中第3行的元素。

   • 计算乘数：
     • l32 = A^(1)[3,2] / A^(1)[2,2] （用于消除第3行第2列的元素）
   • 执行行变换：
     • 第3行新值 = 第3行原值 - l32 × 第2行
   • 经过这一步，我们得到了上三角矩阵U。此时，L矩阵的第二列（主对角线以下部分）就由这个乘数填充：L[3,2] = l32。

3. 构造L和U：

   • U 就是最终得到的上三角矩阵。
   • L 是一个主对角线为1的下三角矩阵，其他位置由我们记录下的乘数填充。

     L = [ 1    0    0 ]
         [ l21  1    0 ]
         [ l31  l32  1 ]
     

验证：你可以将L和U相乘，结果应该等于原始矩阵A。

第三步：求解三角方程组
现在我们有A = LU，所以Ax = b 等价于 (LU)x = b，即 L(Ux) = b。我们令 Ux = y，则原方程转化为两个方程组：

1. 求解 Ly = b （前向代入）
   因为L是下三角矩阵，我们可以从第一个方程开始依次求解。

   • 方程1： 1 * y1 = b1 => y1 = b1
   • 方程2： l21 * y1 + 1 * y2 = b2 => y2 = b2 - l21 * y1
   • 方程3： l31 * y1 + l32 * y2 + 1 * y3 = b3 => y3 = b3 - l31 * y1 - l32 * y2
     这个过程是“前向”的，因为求解y_i时只依赖于已经求出的y1, y2, ..., y_{i-1}。

2. 求解 Ux = y （后向代入）
   因为U是上三角矩阵，我们需要从最后一个方程开始反向求解。

   • 方程3： U[3,3] * x3 = y3 => x3 = y3 / U[3,3]
   • 方程2： U[2,2] * x2 + U[2,3] * x3 = y2 => x2 = (y2 - U[2,3] * x3) / U[2,2]
   • 方程1： U[1,1] * x1 + U[1,2] * x2 + U[1,3] * x3 = y1 => x1 = (y1 - U[1,2] * x2 - U[1,3] * x3) / U[1,1]
     这个过程是“后向”的，因为求解x_i时依赖于已经求出的x_{i+1}, x_{i+2}, ..., x_n。

第四步：得到最终解
通过后向代入求出的向量x = [x1, x2, x3]^T 就是线性方程组Ax = b的解。

总结优点：
LU分解法的一个主要优点是，当需要求解一系列具有相同系数矩阵A、但不同常数向量b的方程组时（即Ax = b1, Ax = b2, ...），我们只需要对A做一次LU分解。之后对于每个新的b，我们只需要进行两次相对廉价的前向和后向代入运算即可，这比每次都进行完整的高斯消元要高效得多。