分块矩阵的Sherman-Morrison公式在线性方程组多重右端项求解中的应用

字数 6101 2025-12-06 00:54:05

分块矩阵的Sherman-Morrison公式在线性方程组多重右端项求解中的应用

题目描述
考虑线性方程组 \(A x^{(k)} = b^{(k)}\)，其中 \(A\) 是一个 \(n \times n\) 可逆矩阵，我们需要求解 \(m\) 个右端项 \(b^{(1)}, b^{(2)}, \dots, b^{(m)}\) 对应的解 \(x^{(1)}, x^{(2)}, \dots, x^{(m)}\)。如果直接对每个右端项调用高斯消元法或LU分解，计算复杂度为 \(O(n^3 + m n^2)\)，当 \(m\) 较大时，\(O(m n^2)\) 项可能成为瓶颈。现在，假设我们已对 \(A\) 完成LU分解，并已求解第一个右端项 \(b^{(1)}\) 得到 \(x^{(1)}\)。随后，我们发现后续右端项 \(b^{(k)}\) (\(k \ge 2\)) 可表示为 \(b^{(k)} = b^{(1)} + u^{(k)}\)，其中 \(u^{(k)}\) 是一个已知向量，且满足 \(u^{(k)} = v^{(k)} \cdot w^{(k)T} b^{(1)}\) 的形式（即每个 \(u^{(k)}\) 是 \(b^{(1)}\) 的低秩修正）。在这种情况下，如何利用 Sherman-Morrison 公式，高效地重用已有的LU分解结果，避免对每个右端项重新求解完整的线性方程组，从而将计算复杂度从 \(O(m n^2)\) 降低到接近 \(O(n^2 + m n)\)？请详细描述算法步骤、推导过程，并分析计算复杂度和数值稳定性。

解题过程循序渐进讲解

步骤1：回顾Sherman-Morrison公式及其基本思想
Sherman-Morrison 公式处理的是矩阵 \(A\) 受到一个外积（即秩1矩阵）修正后的逆矩阵。具体公式如下：
如果 \(A\) 是可逆方阵，\(u, v\) 是列向量，且 \(1 + v^T A^{-1} u \neq 0\)，则

\[(A + u v^T)^{-1} = A^{-1} - \frac{A^{-1} u v^T A^{-1}}{1 + v^T A^{-1} u}. \]

这个公式的意义在于，当我们已经计算好 \(A^{-1}\)（或者更实际地，已经计算了 \(A\) 的LU分解并能快速求解 \(A y = d\) 这类方程），可以通过少量额外计算（主要涉及矩阵与向量的乘积和向量内积）得到 \((A + uv^T)^{-1}\) 作用于某个向量的结果，而无需显式构造或分解修正后的矩阵。

在本题中，右端项的变化并不是直接修正矩阵 \(A\)，而是表现为 \(b^{(k)} = b^{(1)} + u^{(k)}\)。但我们可以巧妙地将问题转化为类似 Sherman-Morrison 的形式，通过构造一个辅助线性方程组，使得右端项的修正等价于系数矩阵的秩1修正。下面我们详细推导这个过程。

步骤2：将右端项修正转化为系数矩阵的秩1修正
已知第一个右端项 \(b^{(1)}\) 对应解 \(x^{(1)}\)，满足 \(A x^{(1)} = b^{(1)}\)。
对于后续右端项 \(b^{(k)} = b^{(1)} + u^{(k)}\)，我们希望解 \(A x^{(k)} = b^{(k)}\)。

这里，题目给出 \(u^{(k)} = v^{(k)} \cdot w^{(k)T} b^{(1)}\)，其中 \(v^{(k)}\) 是已知的 \(n \times 1\) 向量，\(w^{(k)}\) 也是已知的 \(n \times 1\) 向量，\(w^{(k)T} b^{(1)}\) 是一个标量。因此，\(u^{(k)}\) 是 \(v^{(k)}\) 乘以一个标量，这本质上是秩1更新，但作用于右端项而非矩阵。

将 \(u^{(k)}\) 表达式代入：

\[A x^{(k)} = b^{(1)} + v^{(k)} (w^{(k)T} b^{(1)}). \]

记标量 \(\alpha^{(k)} = w^{(k)T} b^{(1)}\)（这是已知的，因为 \(b^{(1)}\) 已知）。则：

\[A x^{(k)} = b^{(1)} + \alpha^{(k)} v^{(k)}. \]

现在，我们希望重用 \(x^{(1)}\) 的信息。设解 \(x^{(k)}\) 与 \(x^{(1)}\) 的差为 \(\delta^{(k)} = x^{(k)} - x^{(1)}\)。代入方程：

\[A (x^{(1)} + \delta^{(k)}) = b^{(1)} + \alpha^{(k)} v^{(k)}. \]

由于 \(A x^{(1)} = b^{(1)}\)，化简得：

\[A \delta^{(k)} = \alpha^{(k)} v^{(k)}. \]

因此，

\[\delta^{(k)} = \alpha^{(k)} A^{-1} v^{(k)}. \]

所以，

\[x^{(k)} = x^{(1)} + \alpha^{(k)} A^{-1} v^{(k)}. \]

这里，\(A^{-1} v^{(k)}\) 表示求解线性方程组 \(A y^{(k)} = v^{(k)}\)。如果我们已经对 \(A\) 完成了LU分解，那么每个 \(y^{(k)}\) 可以通过前代和回代快速求解，复杂度为 \(O(n^2)\)。但这样对于 \(m-1\) 个右端项，我们需要求解 \(m-1\) 个这样的方程，总复杂度仍是 \(O(m n^2)\)，并未降低。

然而，题目中右端项修正的形式 \(u^{(k)} = v^{(k)} (w^{(k)T} b^{(1)})\) 实际上暗示了一种更特殊的结构：\(v^{(k)}\) 可能与 \(k\) 无关，或者只有少数几个不同的 \(v^{(k)}\)，但题目并未明确。为了应用 Sherman-Morrison 公式达到降复杂度的目的，我们需要进一步假设：存在一个固定的向量 \(v\) 和一系列标量 \(\beta^{(k)}\)，使得 \(u^{(k)} = v \cdot \beta^{(k)}\)。在本题中，\(\beta^{(k)} = w^{(k)T} b^{(1)}\)，但 \(w^{(k)}\) 可以不同，所以 \(v\) 必须相同才能满足这个假设。题目没有明确说明，但为了展示 Sherman-Morrison 的应用，我们假定 \(v^{(k)} = v\) 对所有的 \(k\) 都相同（即所有右端项修正都沿同一个方向 \(v\)）。这样，\(u^{(k)} = v \cdot \beta^{(k)}\)，其中 \(\beta^{(k)} = w^{(k)T} b^{(1)}\)。

在一般性讨论中，我们考虑一个更通用的技巧：将右端项变化嵌入到系数矩阵的修正中。我们构造一个扩展的线性方程组，其系数矩阵是 \(A\) 加上一个低秩修正，而右端项是固定的。具体如下：

步骤3：通过扩展方程组将多右端项问题转化为单右端项问题
我们定义一个新的未知向量 \(z = [x^{(1)}; x^{(2)}; \dots; x^{(m)}]\)，它是将所有解堆叠成的 \(mn \times 1\) 向量。原始的方程组可以写成一个块对角形式：

\[\begin{bmatrix} A & & & \\ & A & & \\ & & \ddots & \\ & & & A \end{bmatrix} \begin{bmatrix} x^{(1)} \\ x^{(2)} \\ \vdots \\ x^{(m)} \end{bmatrix} = \begin{bmatrix} b^{(1)} \\ b^{(2)} \\ \vdots \\ b^{(m)} \end{bmatrix}. \]

这个块对角矩阵的逆就是每个对角块的逆，因此求解它等价于分别求解每个方程，没有优势。

但注意到 \(b^{(k)} = b^{(1)} + v \beta^{(k)}\)。我们引入一个辅助变量 \(t = A^{-1} v\)，则 \(x^{(k)} = x^{(1)} + \beta^{(k)} t\)。那么，如果我们能先计算出 \(t\)，那么每个 \(x^{(k)}\) 只需要一次向量数乘和加法即可得到，复杂度为 \(O(n)\) 每个解。而计算 \(t\) 只需要求解一次 \(A t = v\)，复杂度 \(O(n^2)\)（在已LU分解的前提下，实际是 \(O(n^2)\) 的前代回代）。这样总复杂度就是 \(O(n^2 + m n)\)，比原始的 \(O(m n^2)\) 显著降低。

然而，这并没有用到 Sherman-Morrison 公式，而是利用了右端项修正方向相同的特殊结构。如果修正方向不同（即 \(v^{(k)}\) 不同），但数量不多（比如有 \(r\) 个不同的 \(v^{(k)}\)），我们仍然可以计算 \(t_j = A^{-1} v_j\) 对每个不同的 \(v_j\)，然后对每个右端项，\(x^{(k)} = x^{(1)} + \beta^{(k)} t_j\)，其中 \(v^{(k)} = v_j\)。这样复杂度是 \(O(r n^2 + m n)\)，当 \(r \ll m\) 时仍然高效。

步骤4：当修正方向不同但低秩时，利用Sherman-Morrison公式的另一种视角
实际上，Sherman-Morrison 公式常用于矩阵求逆的低秩更新。在本问题中，我们可以考虑以下策略：
我们希望求解 \(A x^{(k)} = b^{(k)} = b^{(1)} + u^{(k)}\)。设 \(u^{(k)} = \sum_{i=1}^{r} v_i \beta_i^{(k)}\)，其中 \(v_i\) 是固定的 \(r\) 个向量，\(\beta_i^{(k)}\) 是标量系数。这表示每个右端项修正位于由 \(v_1, \dots, v_r\) 张成的子空间中。我们可以将多右端项问题转化为求解 \(A^{-1} v_i\) 的问题，然后线性组合。

具体算法如下：

对 \(A\) 进行LU分解，并求解 \(A x^{(1)} = b^{(1)}\) 得到 \(x^{(1)}\)。
对于每个基向量 \(v_i\) （\(i=1,\dots,r\)），求解 \(A t_i = v_i\) 得到 \(t_i\)。
对于每个 \(k = 2, \dots, m\)，计算 \(x^{(k)} = x^{(1)} + \sum_{i=1}^{r} \beta_i^{(k)} t_i\)，其中 \(\beta_i^{(k)}\) 是 \(u^{(k)}\) 在 \(v_i\) 上的系数。

这个算法复杂度为：步骤1和2需要 \(1 + r\) 次前代回代（每个前代回代 \(O(n^2)\)），所以是 \(O((r+1) n^2)\)，步骤3每个 \(k\) 需要 \(O(r n)\) 操作，总共 \(O(m r n)\)。当 \(r\) 很小（比如 \(r=1\) 或 \(2\)）且 \(m\) 很大时，这比直接求解 \(m\) 个方程（\(O(m n^2)\)）要快得多。

步骤5：数值稳定性与实现细节
在实际计算中，我们应避免显式计算 \(A^{-1}\)，而是使用LU分解求解线性方程组。

对 \(A\) 做LU分解（可能带有选主元以保证稳定性），得到 \(PA = LU\)，其中 \(P\) 是排列矩阵，\(L\) 是单位下三角矩阵，\(U\) 是上三角矩阵。
求解 \(x^{(1)}\)：解 \(L y = P b^{(1)}\)，再解 \(U x^{(1)} = y\)。
对于每个基向量 \(v_i\)，解 \(L y_i = P v_i\)，再解 \(U t_i = y_i\)。
对于后续右端项，计算系数 \(\beta_i^{(k)}\)（根据 \(u^{(k)} = \sum_i v_i \beta_i^{(k)}\) 确定），然后计算 \(x^{(k)} = x^{(1)} + \sum_i \beta_i^{(k)} t_i\)。

当 \(r\) 较大时，计算 \(t_i\) 的开销会增大。但若 \(r\) 与 \(m\) 可比拟，则本方法可能没有优势。因此，本方法适用于右端项修正具有低秩结构的情况，即 \(u^{(k)}\) 可以表示为少数几个固定向量的线性组合。

步骤6：复杂度分析对比

原始方法（每个右端项独立求解）：
LU分解一次 \(O(n^3)\)，之后每个右端项前代回代 \(O(n^2)\)，总复杂度 \(O(n^3 + m n^2)\)。
所提出的低秩修正重用方法：
LU分解一次 \(O(n^3)\)，求解 \(x^{(1)}\) 和 \(r\) 个基向量对应的 \(t_i\) 共 \((r+1)\) 次前代回代 \(O((r+1) n^2)\)，之后每个右端项计算线性组合 \(O(r n)\)，总复杂度 \(O(n^3 + (r+1) n^2 + m r n)\)。
当 \(r \ll n\) 且 \(m \gg r\) 时，\(m r n\) 项远小于 \(m n^2\)，节省了大量计算。

总结
本题通过识别右端项修正的低秩结构，将多右端项线性方程组的求解转化为先求解少量基向量对应的方程组，再通过线性组合快速得到所有解。这本质上是利用了Sherman-Morrison公式的思想——低秩修正可高效处理，但这里将修正应用于右端项而非矩阵。算法在右端项修正具有低维表示时非常高效，显著降低了计算复杂度。

分块矩阵的Sherman-Morrison公式在线性方程组多重右端项求解中的应用题目描述考虑线性方程组 \( A x^{(k)} = b^{(k)} \)，其中 \( A \) 是一个 \( n \times n \) 可逆矩阵，我们需要求解 \( m \) 个右端项 \( b^{(1)}, b^{(2)}, \dots, b^{(m)} \) 对应的解 \( x^{(1)}, x^{(2)}, \dots, x^{(m)} \)。如果直接对每个右端项调用高斯消元法或LU分解，计算复杂度为 \( O(n^3 + m n^2) \)，当 \( m \) 较大时，\( O(m n^2) \) 项可能成为瓶颈。现在，假设我们已对 \( A \) 完成LU分解，并已求解第一个右端项 \( b^{(1)} \) 得到 \( x^{(1)} \)。随后，我们发现后续右端项 \( b^{(k)} \) (\( k \ge 2 \)) 可表示为 \( b^{(k)} = b^{(1)} + u^{(k)} \)，其中 \( u^{(k)} \) 是一个已知向量，且满足 \( u^{(k)} = v^{(k)} \cdot w^{(k)T} b^{(1)} \) 的形式（即每个 \( u^{(k)} \) 是 \( b^{(1)} \) 的低秩修正）。在这种情况下，如何利用 Sherman-Morrison 公式，高效地重用已有的LU分解结果，避免对每个右端项重新求解完整的线性方程组，从而将计算复杂度从 \( O(m n^2) \) 降低到接近 \( O(n^2 + m n) \)？请详细描述算法步骤、推导过程，并分析计算复杂度和数值稳定性。解题过程循序渐进讲解步骤1：回顾Sherman-Morrison公式及其基本思想 Sherman-Morrison 公式处理的是矩阵 \( A \) 受到一个外积（即秩1矩阵）修正后的逆矩阵。具体公式如下：如果 \( A \) 是可逆方阵，\( u, v \) 是列向量，且 \( 1 + v^T A^{-1} u \neq 0 \)，则 \[ (A + u v^T)^{-1} = A^{-1} - \frac{A^{-1} u v^T A^{-1}}{1 + v^T A^{-1} u}. \] 这个公式的意义在于，当我们已经计算好 \( A^{-1} \)（或者更实际地，已经计算了 \( A \) 的LU分解并能快速求解 \( A y = d \) 这类方程），可以通过少量额外计算（主要涉及矩阵与向量的乘积和向量内积）得到 \( (A + uv^T)^{-1} \) 作用于某个向量的结果，而无需显式构造或分解修正后的矩阵。在本题中，右端项的变化并不是直接修正矩阵 \( A \)，而是表现为 \( b^{(k)} = b^{(1)} + u^{(k)} \)。但我们可以巧妙地将问题转化为类似 Sherman-Morrison 的形式，通过构造一个辅助线性方程组，使得右端项的修正等价于系数矩阵的秩1修正。下面我们详细推导这个过程。步骤2：将右端项修正转化为系数矩阵的秩1修正已知第一个右端项 \( b^{(1)} \) 对应解 \( x^{(1)} \)，满足 \( A x^{(1)} = b^{(1)} \)。对于后续右端项 \( b^{(k)} = b^{(1)} + u^{(k)} \)，我们希望解 \( A x^{(k)} = b^{(k)} \)。这里，题目给出 \( u^{(k)} = v^{(k)} \cdot w^{(k)T} b^{(1)} \)，其中 \( v^{(k)} \) 是已知的 \( n \times 1 \) 向量，\( w^{(k)} \) 也是已知的 \( n \times 1 \) 向量，\( w^{(k)T} b^{(1)} \) 是一个标量。因此，\( u^{(k)} \) 是 \( v^{(k)} \) 乘以一个标量，这本质上是秩1更新，但作用于右端项而非矩阵。将 \( u^{(k)} \) 表达式代入： \[ A x^{(k)} = b^{(1)} + v^{(k)} (w^{(k)T} b^{(1)}). \] 记标量 \( \alpha^{(k)} = w^{(k)T} b^{(1)} \)（这是已知的，因为 \( b^{(1)} \) 已知）。则： \[ A x^{(k)} = b^{(1)} + \alpha^{(k)} v^{(k)}. \] 现在，我们希望重用 \( x^{(1)} \) 的信息。设解 \( x^{(k)} \) 与 \( x^{(1)} \) 的差为 \( \delta^{(k)} = x^{(k)} - x^{(1)} \)。代入方程： \[ A (x^{(1)} + \delta^{(k)}) = b^{(1)} + \alpha^{(k)} v^{(k)}. \] 由于 \( A x^{(1)} = b^{(1)} \)，化简得： \[ A \delta^{(k)} = \alpha^{(k)} v^{(k)}. \] 因此， \[ \delta^{(k)} = \alpha^{(k)} A^{-1} v^{(k)}. \] 所以， \[ x^{(k)} = x^{(1)} + \alpha^{(k)} A^{-1} v^{(k)}. \] 这里，\( A^{-1} v^{(k)} \) 表示求解线性方程组 \( A y^{(k)} = v^{(k)} \)。如果我们已经对 \( A \) 完成了LU分解，那么每个 \( y^{(k)} \) 可以通过前代和回代快速求解，复杂度为 \( O(n^2) \)。但这样对于 \( m-1 \) 个右端项，我们需要求解 \( m-1 \) 个这样的方程，总复杂度仍是 \( O(m n^2) \)，并未降低。然而，题目中右端项修正的形式 \( u^{(k)} = v^{(k)} (w^{(k)T} b^{(1)}) \) 实际上暗示了一种更特殊的结构：\( v^{(k)} \) 可能与 \( k \) 无关，或者只有少数几个不同的 \( v^{(k)} \)，但题目并未明确。为了应用 Sherman-Morrison 公式达到降复杂度的目的，我们需要进一步假设：存在一个固定的向量 \( v \) 和一系列标量 \( \beta^{(k)} \)，使得 \( u^{(k)} = v \cdot \beta^{(k)} \)。在本题中，\( \beta^{(k)} = w^{(k)T} b^{(1)} \)，但 \( w^{(k)} \) 可以不同，所以 \( v \) 必须相同才能满足这个假设。题目没有明确说明，但为了展示 Sherman-Morrison 的应用，我们假定 \( v^{(k)} = v \) 对所有的 \( k \) 都相同（即所有右端项修正都沿同一个方向 \( v \)）。这样，\( u^{(k)} = v \cdot \beta^{(k)} \)，其中 \( \beta^{(k)} = w^{(k)T} b^{(1)} \)。在一般性讨论中，我们考虑一个更通用的技巧：将右端项变化嵌入到系数矩阵的修正中。我们构造一个扩展的线性方程组，其系数矩阵是 \( A \) 加上一个低秩修正，而右端项是固定的。具体如下：步骤3：通过扩展方程组将多右端项问题转化为单右端项问题我们定义一个新的未知向量 \( z = [ x^{(1)}; x^{(2)}; \dots; x^{(m)} ] \)，它是将所有解堆叠成的 \( mn \times 1 \) 向量。原始的方程组可以写成一个块对角形式： \[ \begin{bmatrix} A & & & \\ & A & & \\ & & \ddots & \\ & & & A \end{bmatrix} \begin{bmatrix} x^{(1)} \\ x^{(2)} \\ \vdots \\ x^{(m)} \end{bmatrix} \begin{bmatrix} b^{(1)} \\ b^{(2)} \\ \vdots \\ b^{(m)} \end{bmatrix}. \] 这个块对角矩阵的逆就是每个对角块的逆，因此求解它等价于分别求解每个方程，没有优势。但注意到 \( b^{(k)} = b^{(1)} + v \beta^{(k)} \)。我们引入一个辅助变量 \( t = A^{-1} v \)，则 \( x^{(k)} = x^{(1)} + \beta^{(k)} t \)。那么，如果我们能先计算出 \( t \)，那么每个 \( x^{(k)} \) 只需要一次向量数乘和加法即可得到，复杂度为 \( O(n) \) 每个解。而计算 \( t \) 只需要求解一次 \( A t = v \)，复杂度 \( O(n^2) \)（在已LU分解的前提下，实际是 \( O(n^2) \) 的前代回代）。这样总复杂度就是 \( O(n^2 + m n) \)，比原始的 \( O(m n^2) \) 显著降低。然而，这并没有用到 Sherman-Morrison 公式，而是利用了右端项修正方向相同的特殊结构。如果修正方向不同（即 \( v^{(k)} \) 不同），但数量不多（比如有 \( r \) 个不同的 \( v^{(k)} \)），我们仍然可以计算 \( t_ j = A^{-1} v_ j \) 对每个不同的 \( v_ j \)，然后对每个右端项，\( x^{(k)} = x^{(1)} + \beta^{(k)} t_ j \)，其中 \( v^{(k)} = v_ j \)。这样复杂度是 \( O(r n^2 + m n) \)，当 \( r \ll m \) 时仍然高效。步骤4：当修正方向不同但低秩时，利用Sherman-Morrison公式的另一种视角实际上，Sherman-Morrison 公式常用于矩阵求逆的低秩更新。在本问题中，我们可以考虑以下策略：我们希望求解 \( A x^{(k)} = b^{(k)} = b^{(1)} + u^{(k)} \)。设 \( u^{(k)} = \sum_ {i=1}^{r} v_ i \beta_ i^{(k)} \)，其中 \( v_ i \) 是固定的 \( r \) 个向量，\( \beta_ i^{(k)} \) 是标量系数。这表示每个右端项修正位于由 \( v_ 1, \dots, v_ r \) 张成的子空间中。我们可以将多右端项问题转化为求解 \( A^{-1} v_ i \) 的问题，然后线性组合。具体算法如下：对 \( A \) 进行LU分解，并求解 \( A x^{(1)} = b^{(1)} \) 得到 \( x^{(1)} \)。对于每个基向量 \( v_ i \) （\( i=1,\dots,r \)），求解 \( A t_ i = v_ i \) 得到 \( t_ i \)。对于每个 \( k = 2, \dots, m \)，计算 \( x^{(k)} = x^{(1)} + \sum_ {i=1}^{r} \beta_ i^{(k)} t_ i \)，其中 \( \beta_ i^{(k)} \) 是 \( u^{(k)} \) 在 \( v_ i \) 上的系数。这个算法复杂度为：步骤1和2需要 \( 1 + r \) 次前代回代（每个前代回代 \( O(n^2) \)），所以是 \( O((r+1) n^2) \)，步骤3每个 \( k \) 需要 \( O(r n) \) 操作，总共 \( O(m r n) \)。当 \( r \) 很小（比如 \( r=1 \) 或 \( 2 \)）且 \( m \) 很大时，这比直接求解 \( m \) 个方程（\( O(m n^2) \)）要快得多。步骤5：数值稳定性与实现细节在实际计算中，我们应避免显式计算 \( A^{-1} \)，而是使用LU分解求解线性方程组。对 \( A \) 做LU分解（可能带有选主元以保证稳定性），得到 \( PA = LU \)，其中 \( P \) 是排列矩阵，\( L \) 是单位下三角矩阵，\( U \) 是上三角矩阵。求解 \( x^{(1)} \)：解 \( L y = P b^{(1)} \)，再解 \( U x^{(1)} = y \)。对于每个基向量 \( v_ i \)，解 \( L y_ i = P v_ i \)，再解 \( U t_ i = y_ i \)。对于后续右端项，计算系数 \( \beta_ i^{(k)} \)（根据 \( u^{(k)} = \sum_ i v_ i \beta_ i^{(k)} \) 确定），然后计算 \( x^{(k)} = x^{(1)} + \sum_ i \beta_ i^{(k)} t_ i \)。当 \( r \) 较大时，计算 \( t_ i \) 的开销会增大。但若 \( r \) 与 \( m \) 可比拟，则本方法可能没有优势。因此，本方法适用于右端项修正具有低秩结构的情况，即 \( u^{(k)} \) 可以表示为少数几个固定向量的线性组合。步骤6：复杂度分析对比原始方法（每个右端项独立求解）： LU分解一次 \( O(n^3) \)，之后每个右端项前代回代 \( O(n^2) \)，总复杂度 \( O(n^3 + m n^2) \)。所提出的低秩修正重用方法： LU分解一次 \( O(n^3) \)，求解 \( x^{(1)} \) 和 \( r \) 个基向量对应的 \( t_ i \) 共 \( (r+1) \) 次前代回代 \( O((r+1) n^2) \)，之后每个右端项计算线性组合 \( O(r n) \)，总复杂度 \( O(n^3 + (r+1) n^2 + m r n) \)。当 \( r \ll n \) 且 \( m \gg r \) 时，\( m r n \) 项远小于 \( m n^2 \)，节省了大量计算。总结本题通过识别右端项修正的低秩结构，将多右端项线性方程组的求解转化为先求解少量基向量对应的方程组，再通过线性组合快速得到所有解。这本质上是利用了Sherman-Morrison公式的思想——低秩修正可高效处理，但这里将修正应用于右端项而非矩阵。算法在右端项修正具有低维表示时非常高效，显著降低了计算复杂度。