数值分析(二):解线性代数方程组的直接法
对应数值分析(三):高斯消去法与主元素消去法,Doolittle 分解、追赶法与 Cholesky 平方根法,向量和矩阵范数、条件数及其在误差分析中的应用。
本节导读
这一节对应数值分析大纲「(三)解线性代数方程组的直接法」的四条:「高斯消去法」「主元素消去法」「直接三角分解法」(下设「Doolittle 分解法」「三对角方程组的追赶法」「对称正定阵的 Cholesky 分解、平方根法」)和「向量和矩阵范数,矩阵的条件数和应用」。直接法是指不计舍入误差时,经过有限步运算就能得到精确解的方法。
学完要做到:会做三阶方程组的消去和三角分解;说清为什么要选主元;记住追赶法、平方根法各适用于什么矩阵;会算常用范数和条件数,并用条件数估计解的相对误差。
本节记号:方程组 Ax=b,A 为 n 阶矩阵;L 为下三角矩阵(Doolittle 分解中对角元为 1),U 为上三角矩阵;lij、uij 是它们的元素;ρ(A) 是谱半径。
高斯消去法
顺序消去与回代
高斯消去法分两步。消元:第 k 步用第 k 行把它下面各行第 k 列的元素消成零,乘数 lik=aik(k)/akk(k),第 i 行减去第 k 行的 lik 倍;做完 n−1 步得到上三角方程组。回代:从最后一个方程起,逐个解出 xn,xn−1,⋯,x1。
顺序消去能进行到底的条件是每一步的主元 akk(k)=0,等价于 A 的各阶顺序主子式都不为零。乘除运算量约为 3n3,主要花在消元上。
消去法与三角分解的关系
把各步的乘数 lik 填进一个单位下三角矩阵 L,消元后得到的上三角矩阵就是 U,于是 A=LU。所以高斯消去法本质上就是把 A 分解成 LU,再依次解两个三角方程组。
主元素消去法
顺序消去时,主元的绝对值很小,乘数就很大,舍入误差会被成倍放大,结果可能完全失真。主元素消去法在每一步先选一个绝对值大的元素当主元:
| 方法 | 第 k 步怎么选主元 | 特点 |
|---|---|---|
| 列主元消去法 | 在第 k 列的第 k 行到第 n 行中,选绝对值最大的元素,交换到第 k 行 | 只交换行,解的顺序不变,最常用 |
| 全主元消去法 | 在右下角整个子矩阵里选绝对值最大的元素,交换行和列 | 更稳定,但比较次数多,交换列后要记下未知量的次序 |
选列主元后所有乘数的绝对值都不超过 1,这是它数值稳定的原因。只要 A 非奇异,列主元消去法就能进行到底。
直接三角分解法
Doolittle 分解法
若 A 的各阶顺序主子式都不为零,A 可以唯一地分解成 A=LU,L 为单位下三角矩阵、U 为上三角矩阵,这就是 Doolittle 分解。按「先算 U 的第 k 行,再算 L 的第 k 列」的次序,对 k=1,2,⋯,n:
ukj=akj−r=1∑k−1lkrurj(j=k,⋯,n) lik=ukk1(aik−r=1∑k−1lirurk)(i=k+1,⋯,n)分解完后,先由 Ly=b 向前求 y,再由 Ux=y 回代求 x。系数矩阵相同、右端项不同的几组方程,只需分解一次。
三对角方程组的追赶法
三对角方程组只在主对角线和它上下相邻两条线上有非零元素,常见于样条插值和微分方程边值问题的差分离散。对它做 LU 分解,L 和 U 都只有两条对角线,求解分「追」(从上到下算分解系数和中间量)和「赶」(从下到上回代)两步,乘除运算量只与 n 成正比。当矩阵对角占优(主对角元的绝对值大于同行其余两个元素绝对值之和)时,追赶法能进行到底且数值稳定。
对称正定阵的 Cholesky 分解、平方根法
A 对称正定时,存在唯一的对角元为正的下三角矩阵 L,使 A=LLT,这就是 Cholesky 分解;用它解方程组叫平方根法。公式(j=1,2,⋯,n):
ljjlij=(ajj−k=1∑j−1ljk2)1/2=ljj1(aij−k=1∑j−1likljk) (i>j)平方根法不用选主元也是数值稳定的,运算量约为高斯消去的一半。为了避免开方,可以改写成 A=LDLT(L 为单位下三角、D 为对角阵),叫改进平方根法。
向量和矩阵范数,矩阵的条件数和应用
范数
常用的向量范数:∥x∥1=∑∣xi∣,∥x∥2=(∑xi2)1/2,∥x∥∞=max∣xi∣。由它们导出的矩阵范数:
| 范数 | 算法 |
|---|---|
| ∥A∥1 | 各列元素绝对值之和的最大值(列和范数) |
| ∥A∥∞ | 各行元素绝对值之和的最大值(行和范数) |
| ∥A∥2 | λmax(ATA)(谱范数) |
谱半径 ρ(A) 是 A 的特征值绝对值的最大值,对任何一种由向量范数导出的矩阵范数都有 ρ(A)≤∥A∥。
条件数及其应用
矩阵的条件数 cond(A)=∥A∥∥A−1∥。右端项有扰动 δb 时,解的相对误差满足
∥x∥∥δx∥≤cond(A)∥b∥∥δb∥条件数越大,数据的小误差可能引起解的大误差,叫病态方程组;条件数接近 1 叫良态。病态是方程组本身的性质,换算法消除不了,只能提高计算精度或改变模型。行列式小不等于病态(把矩阵乘以 0.1,行列式变小,条件数不变),要看条件数。
易错提醒
-
❌ 全主元消去法交换了列,解出来的未知量顺序不用管。
✅ 交换列就是交换了未知量的次序,要记下每次交换,最后把解按原来的次序排回去。 -
❌ 只要方程组有唯一解,Cholesky 分解就能用。
✅ Cholesky 分解要求矩阵对称正定;一般的非奇异矩阵用列主元消去或 LU 分解。 -
❌ 行列式的绝对值很小,方程组就一定病态。
✅ 病态看条件数,不看行列式:整体缩放会改变行列式,却不改变条件数。 -
❌ 方程组病态,换一种消去法就能算准。
✅ 病态是问题本身对数据敏感,算法只能做到不额外放大误差。
例题精讲
例题 1(计算:Doolittle 分解)
用 Doolittle 分解解方程组,系数矩阵与右端项为
A=24−2131134,b=375解:第 1 步:u11=2,u12=1,u13=1;l21=4/2=2,l31=−2/2=−1。第 2 步:u22=3−2×1=1,u23=3−2×1=1;l32=(1−(−1)×1)/1=2。第 3 步:u33=4−((−1)×1+2×1)=3。
解 Ly=b:y1=3,y2=7−2×3=1,y3=5+3−2×1=6。解 Ux=y:x3=6/3=2,x2=1−2=−1,x1=(3+1−2)/2=1。所以 x=(1,−1,2)T。
点评:求和项里每一项都是「L 的行」乘「U 的列」,漏一项是最常见的错。
例题 2(计算:条件数与误差估计)
A=(32.922)。求 cond∞(A);若右端项的相对误差为 0.1%,解的相对误差最多可能放大到多少?
解:detA=6−5.8=0.2,A−1=(10−14.5−1015)。∥A∥∞=max(5,4.9)=5,∥A−1∥∞=max(20,29.5)=29.5,cond∞(A)=147.5。解的相对误差上界 =147.5×0.1%=14.75%。
点评:两行几乎成比例时条件数大,数据千分之一的误差,解可能错到一成以上。
本节小结
- 高斯消去 = 消元 + 回代,运算量约 n3/3;顺序消去要求各阶顺序主子式非零,等价于 A=LU。
- 主元太小会放大舍入误差;列主元消去法每步在当前列选绝对值最大的元素,乘数都不超过 1。
- Doolittle 分解先行后列逐步算;追赶法用于对角占优的三对角方程组,运算量与 n 成正比;平方根法用于对称正定矩阵。
- 范数:列和、行和、谱范数;ρ(A)≤∥A∥;条件数 ∥A∥∥A−1∥ 衡量病态程度,用它估计解的相对误差上界。
学完练一练
按本节考点从本课的课后练习里抽题(每次 10 道以内),做完看解析、错题自动进错题本。
本节内容由 AI 辅助编写,配图由 AI 生成,仅供备考参考;考试要求以《全国各类成人高等学校招生考试大纲(2024 年版)》及浙江省教育考试院当年公布为准。