LU分解在多重线性方程组求解中的高效应用

题目描述
考虑需要求解一系列具有相同系数矩阵A但不同右端项b的线性方程组：Ax₁=b₁, Ax₂=b₂, ..., Axₖ=bₖ。当矩阵A固定而右端项变化时，直接对每个方程组重复使用高斯消元法效率低下。LU分解通过将矩阵A分解为下三角矩阵L和上三角矩阵U的乘积，可以显著提高这类问题的计算效率。

解题过程

第一步：理解LU分解的基本原理
LU分解的核心思想是将系数矩阵A分解为：
A = LU
其中L是单位下三角矩阵（主对角线元素全为1），U是上三角矩阵。这个分解只需对A完成一次，即可用于求解所有具有相同系数矩阵的线性方程组。

第二步：进行LU分解（以3×3矩阵为例）
设矩阵A为：

A = [2,  1,  1]
    [4,  3,  3]
    [8,  7,  9]

通过高斯消元法进行分解：

1. 第一列消元：用第一行消去第二行和第三行的第一个元素

   • 乘数：l₂₁ = 4/2 = 2, l₃₁ = 8/2 = 4
   • 更新矩阵：

     [2,   1,   1]
     [0,   1,   1]  (3-2×1=1, 3-2×1=1)
     [0,   3,   5]  (7-4×1=3, 9-4×1=5)
     

2. 第二列消元：用第二行消去第三行的第二个元素

   • 乘数：l₃₂ = 3/1 = 3
   • 更新矩阵：

     [2,   1,   1]
     [0,   1,   1]
     [0,   0,   2]  (5-3×1=2)
     

得到：
L = [1, 0, 0] U = [2, 1, 1]
[2, 1, 0] [0, 1, 1]
[4, 3, 1] [0, 0, 2]

第三步：前代法求解Ly=b
对于每个右端项b，先解下三角方程组Ly=b。

例如b₁ = [1, 2, 3]ᵀ：

1. y₁ = b₁₁ = 1
2. 2y₁ + y₂ = 2 ⇒ y₂ = 2 - 2×1 = 0
3. 4y₁ + 3y₂ + y₃ = 3 ⇒ y₃ = 3 - 4×1 - 3×0 = -1

解得y = [1, 0, -1]ᵀ

第四步：回代法求解Ux=y
接着解上三角方程组Ux=y：

1. 2x₃ = -1 ⇒ x₃ = -0.5
2. x₂ + x₃ = 0 ⇒ x₂ = 0 - (-0.5) = 0.5
3. 2x₁ + x₂ + x₃ = 1 ⇒ 2x₁ = 1 - 0.5 - (-0.5) = 1 ⇒ x₁ = 0.5

第五步：效率分析

• 分解阶段：O(n³)复杂度（只需一次）
• 求解每个方程组：前代O(n²) + 回代O(n²) = O(n²)
• 总复杂度：O(n³) + k×O(n²)，当k很大时远优于k×O(n³)

这种方法的优势在于，一旦完成LU分解，后续每个新方程组的求解成本大大降低，特别适用于需要反复求解相同系数矩阵的问题。