高等数学 / 系统课时

用LU分解重复求解方程

用LU分解重复求解方程

当系数矩阵不变、右端项不断变化时,每次都从头做高斯消元会重复大量相同计算。LU 分解把第一次消元记录为两个三角矩阵,之后每组右端项只需做前代和回代,就能明显降低重复求解的成本。

学习目标

  • 理解 A=LUA=LU 与高斯消元之间的对应关系
  • 能用前代、回代完成同一系数矩阵下的多组方程求解
  • 判断什么时候应复用 LU 分解,以及主元交换为什么重要

LU分解记录了什么

考虑线性方程组 Ax=bAx=b。普通高斯消元不断用一行的倍数消去下方元素,最终把 AA 变成上三角矩阵。关键是:这些消元倍数并没有必要丢掉,它们可以被保存到一个下三角矩阵 LL 中,而消元后的结果就是上三角矩阵 UU。

于是原矩阵可以写成 A=LUA=LU。其中 LL 的对角线通常为 1,对角线下方保存各步消元使用的倍数;UU 则保存高斯消元结束后的上三角结构。LU 分解本质上不是一种与消元无关的新算法,而是把消元过程整理成可复用的数据。

例如取 A=[[2,1],[6,4]]A=[[2,1],[6,4]]。消去第二行第一列时,需要用第二行减去第一行的 3 倍,因此消元倍数为 3。得到 U=[[2,1],[0,1]]U=[[2,1],[0,1]],同时把这个倍数记录为 L=[[1,0],[3,1]]L=[[1,0],[3,1]]。直接相乘可以验证 LU=ALU=A。

一次分解如何服务多组右端项

若已经得到 A=LUA=LU,原方程可以写成 LUx=bLUx=b。引入中间变量 yy 后,求解被拆成两个更简单的问题:先解下三角方程 Ly=bLy=b,再解上三角方程 Ux=yUx=y。前者从第一行向下计算,称为前代;后者从最后一行向上计算,称为回代。

LU分解重复求解的数据流

继续使用上面的 LL 和 UU。若第一组右端项为 b=[5,16]b=[5,16],先解 Ly=bLy=b:第一式给出 y1=5y_1=5,第二式为 3y1+y2=163y_1+y_2=16,因此 y2=1y_2=1。再解 Ux=yUx=y:由第二式得到 x2=1x_2=1,代回第一式得到 x1=2x_1=2,所以解为 x=[2,1]x=[2,1]。

如果换成第二组右端项 b=[1,2]b=[1,2],LL 和 UU 完全不需要重新计算。前代得到 y=[1,−1]y=[1,-1],回代得到 x=[1,−1]x=[1,-1]。这正是 LU 分解适合重复求解的原因:变化的是 bb,而最昂贵的矩阵消元结果可以保留。

为什么重复求解会更快

对一个 n×nn\times n 稠密矩阵,从头做一次消元的工作量是 O(n3)O(n^3) 量级;而已经有 LL、UU 后,一次前代和一次回代都只需 O(n2)O(n^2) 量级。因此有很多右端项时,先分解一次再复用通常更划算。

工作 执行次数 主要成本量级
LU 分解 1 次 O(n3)O(n^3)
对每个 bb 做前代 每组 1 次 O(n2)O(n^2)
对每个 bb 做回代 每组 1 次 O(n2)O(n^2)

如果有 kk 组右端项,重复从头消元大致会产生 kk 次立方级工作,而 LU 方法把主要成本变成一次 O(n3)O(n^3) 分解加上 kk 次 O(n2)O(n^2) 求解。矩阵规模越大、右端项越多,复用价值越明显。

什么时候不能直接复用

LU 分解能复用的前提是系数矩阵保持不变。只要 AA 中的元素发生变化,原来的 LL、UU 一般就不再对应新问题,必须重新分解;仅仅改变 bb 则不会影响已有分解。

还要注意主元问题。如果消元过程中遇到零主元,或者主元绝对值极小,直接执行不换行的 LU 分解可能失败或产生严重数值误差。因此数值库通常实际保存的是 PP、LL、UU,并按 Ly=PbLy=Pb、Ux=yUx=y 的顺序求解。若矩阵本身奇异,则即使加入行交换,也不能得到用于唯一求解的普通 LU 过程。

因此,面对“同一个模型、不同输入”的一批线性方程组时,应把矩阵分解视为一次性预处理,把每个新的右端项视为廉价的三角方程求解。这正是 LU 分解相对于重复高斯消元的核心价值。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用LU分解重复求解方程

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通