杭州紫金港培训学校(紫金港专升本)杭州紫金港培训学校(紫金港专升本)
同等学力申硕电子科学与技术学科综合考前辅导第一类 数值分析第 3 节 / 共 32 节约 30 分钟免费

数值分析(二):解线性代数方程组的直接法

对应数值分析(三):高斯消去法与主元素消去法,Doolittle 分解、追赶法与 Cholesky 平方根法,向量和矩阵范数、条件数及其在误差分析中的应用。

本节考点:高斯消去法主元素消去法直接三角分解法追赶法与平方根法范数与条件数

本节导读

这一节对应数值分析大纲「(三)解线性代数方程组的直接法」的四条:「高斯消去法」「主元素消去法」「直接三角分解法」(下设「Doolittle 分解法」「三对角方程组的追赶法」「对称正定阵的 Cholesky 分解、平方根法」)和「向量和矩阵范数,矩阵的条件数和应用」。直接法是指不计舍入误差时,经过有限步运算就能得到精确解的方法。

学完要做到:会做三阶方程组的消去和三角分解;说清为什么要选主元;记住追赶法、平方根法各适用于什么矩阵;会算常用范数和条件数,并用条件数估计解的相对误差。

本节记号:方程组 Ax=bA\boldsymbol x=\boldsymbol bAx=b,AAA 为 nnn 阶矩阵;LLL 为下三角矩阵(Doolittle 分解中对角元为 1),UUU 为上三角矩阵;lijl_{ij}lij​、uiju_{ij}uij​ 是它们的元素;ρ(A)\rho(A)ρ(A) 是谱半径。

高斯消去法

顺序消去与回代

高斯消去法分两步。消元:第 kkk 步用第 kkk 行把它下面各行第 kkk 列的元素消成零,乘数 lik=aik(k)/akk(k)l_{ik}=a_{ik}^{(k)}/a_{kk}^{(k)}lik​=aik(k)​/akk(k)​,第 iii 行减去第 kkk 行的 likl_{ik}lik​ 倍;做完 n−1n-1n−1 步得到上三角方程组。回代:从最后一个方程起,逐个解出 xn,xn−1,⋯ ,x1x_n,x_{n-1},\cdots,x_1xn​,xn−1​,⋯,x1​。

顺序消去能进行到底的条件是每一步的主元 akk(k)≠0a_{kk}^{(k)}\neq 0akk(k)​=0,等价于 AAA 的各阶顺序主子式都不为零。乘除运算量约为 n33\dfrac{n^3}{3}3n3​,主要花在消元上。

消去法与三角分解的关系

把各步的乘数 likl_{ik}lik​ 填进一个单位下三角矩阵 LLL,消元后得到的上三角矩阵就是 UUU,于是 A=LUA=LUA=LU。所以高斯消去法本质上就是把 AAA 分解成 LULULU,再依次解两个三角方程组。

主元素消去法

顺序消去时,主元的绝对值很小,乘数就很大,舍入误差会被成倍放大,结果可能完全失真。主元素消去法在每一步先选一个绝对值大的元素当主元:

方法第 kkk 步怎么选主元特点
列主元消去法在第 kkk 列的第 kkk 行到第 nnn 行中,选绝对值最大的元素,交换到第 kkk 行只交换行,解的顺序不变,最常用
全主元消去法在右下角整个子矩阵里选绝对值最大的元素,交换行和列更稳定,但比较次数多,交换列后要记下未知量的次序

选列主元后所有乘数的绝对值都不超过 1,这是它数值稳定的原因。只要 AAA 非奇异,列主元消去法就能进行到底。

直接三角分解法

Doolittle 分解法

若 AAA 的各阶顺序主子式都不为零,AAA 可以唯一地分解成 A=LUA=LUA=LU,LLL 为单位下三角矩阵、UUU 为上三角矩阵,这就是 Doolittle 分解。按「先算 UUU 的第 kkk 行,再算 LLL 的第 kkk 列」的次序,对 k=1,2,⋯ ,nk=1,2,\cdots,nk=1,2,⋯,n:

ukj=akj−∑r=1k−1lkrurj(j=k,⋯ ,n)u_{kj}=a_{kj}-\sum_{r=1}^{k-1}l_{kr}u_{rj}\quad(j=k,\cdots,n)ukj​=akj​−r=1∑k−1​lkr​urj​(j=k,⋯,n) lik=1ukk(aik−∑r=1k−1lirurk)(i=k+1,⋯ ,n)\begin{aligned} l_{ik}&=\frac{1}{u_{kk}}\Big(a_{ik}-\sum_{r=1}^{k-1}l_{ir}u_{rk}\Big) \\ &(i=k+1,\cdots,n) \end{aligned}lik​​=ukk​1​(aik​−r=1∑k−1​lir​urk​)(i=k+1,⋯,n)​

分解完后,先由 Ly=bL\boldsymbol y=\boldsymbol bLy=b 向前求 y\boldsymbol yy,再由 Ux=yU\boldsymbol x=\boldsymbol yUx=y 回代求 x\boldsymbol xx。系数矩阵相同、右端项不同的几组方程,只需分解一次。

三对角方程组的追赶法

三对角方程组只在主对角线和它上下相邻两条线上有非零元素,常见于样条插值和微分方程边值问题的差分离散。对它做 LU 分解,LLL 和 UUU 都只有两条对角线,求解分「追」(从上到下算分解系数和中间量)和「赶」(从下到上回代)两步,乘除运算量只与 nnn 成正比。当矩阵对角占优(主对角元的绝对值大于同行其余两个元素绝对值之和)时,追赶法能进行到底且数值稳定。

对称正定阵的 Cholesky 分解、平方根法

AAA 对称正定时,存在唯一的对角元为正的下三角矩阵 LLL,使 A=LLTA=LL^{\mathrm T}A=LLT,这就是 Cholesky 分解;用它解方程组叫平方根法。公式(j=1,2,⋯ ,nj=1,2,\cdots,nj=1,2,⋯,n):

ljj=(ajj−∑k=1j−1ljk2)1/2lij=1ljj(aij−∑k=1j−1likljk) (i>j)\begin{aligned} l_{jj}&=\Big(a_{jj}-\sum_{k=1}^{j-1}l_{jk}^2\Big)^{1/2} \\ l_{ij}&=\frac{1}{l_{jj}}\Big(a_{ij}-\sum_{k=1}^{j-1}l_{ik}l_{jk}\Big)\ (i\gt j) \end{aligned}ljj​lij​​=(ajj​−k=1∑j−1​ljk2​)1/2=ljj​1​(aij​−k=1∑j−1​lik​ljk​) (i>j)​

平方根法不用选主元也是数值稳定的,运算量约为高斯消去的一半。为了避免开方,可以改写成 A=LDLTA=LDL^{\mathrm T}A=LDLT(LLL 为单位下三角、DDD 为对角阵),叫改进平方根法。

向量和矩阵范数,矩阵的条件数和应用

范数

常用的向量范数:∥x∥1=∑∣xi∣\lVert\boldsymbol x\rVert_1=\sum\lvert x_i\rvert∥x∥1​=∑∣xi​∣,∥x∥2=(∑xi2)1/2\lVert\boldsymbol x\rVert_2=\big(\sum x_i^2\big)^{1/2}∥x∥2​=(∑xi2​)1/2,∥x∥∞=max⁡∣xi∣\lVert\boldsymbol x\rVert_\infty=\max\lvert x_i\rvert∥x∥∞​=max∣xi​∣。由它们导出的矩阵范数:

范数算法
∥A∥1\lVert A\rVert_1∥A∥1​各列元素绝对值之和的最大值(列和范数)
∥A∥∞\lVert A\rVert_\infty∥A∥∞​各行元素绝对值之和的最大值(行和范数)
∥A∥2\lVert A\rVert_2∥A∥2​λmax⁡(ATA)\sqrt{\lambda_{\max}(A^{\mathrm T}A)}λmax​(ATA)​(谱范数)

谱半径 ρ(A)\rho(A)ρ(A) 是 AAA 的特征值绝对值的最大值,对任何一种由向量范数导出的矩阵范数都有 ρ(A)≤∥A∥\rho(A)\le\lVert A\rVertρ(A)≤∥A∥。

条件数及其应用

矩阵的条件数 cond(A)=∥A∥ ∥A−1∥\mathrm{cond}(A)=\lVert A\rVert\,\lVert A^{-1}\rVertcond(A)=∥A∥∥A−1∥。右端项有扰动 δb\delta\boldsymbol bδb 时,解的相对误差满足

∥δx∥∥x∥≤cond(A) ∥δb∥∥b∥\frac{\lVert\delta\boldsymbol x\rVert}{\lVert\boldsymbol x\rVert}\le\mathrm{cond}(A)\,\frac{\lVert\delta\boldsymbol b\rVert}{\lVert\boldsymbol b\rVert}∥x∥∥δx∥​≤cond(A)∥b∥∥δb∥​

条件数越大,数据的小误差可能引起解的大误差,叫病态方程组;条件数接近 1 叫良态。病态是方程组本身的性质,换算法消除不了,只能提高计算精度或改变模型。行列式小不等于病态(把矩阵乘以 0.1,行列式变小,条件数不变),要看条件数。

易错提醒

  • ❌ 全主元消去法交换了列,解出来的未知量顺序不用管。
    ✅ 交换列就是交换了未知量的次序,要记下每次交换,最后把解按原来的次序排回去。

  • ❌ 只要方程组有唯一解,Cholesky 分解就能用。
    ✅ Cholesky 分解要求矩阵对称正定;一般的非奇异矩阵用列主元消去或 LU 分解。

  • ❌ 行列式的绝对值很小,方程组就一定病态。
    ✅ 病态看条件数,不看行列式:整体缩放会改变行列式,却不改变条件数。

  • ❌ 方程组病态,换一种消去法就能算准。
    ✅ 病态是问题本身对数据敏感,算法只能做到不额外放大误差。

例题精讲

例题 1(计算:Doolittle 分解)

用 Doolittle 分解解方程组,系数矩阵与右端项为

A=(211433−214),b=(375)A=\begin{pmatrix}2&1&1\\4&3&3\\-2&1&4\end{pmatrix},\qquad \boldsymbol b=\begin{pmatrix}3\\7\\5\end{pmatrix}A=​24−2​131​134​​,b=​375​​

解:第 1 步:u11=2u_{11}=2u11​=2,u12=1u_{12}=1u12​=1,u13=1u_{13}=1u13​=1;l21=4/2=2l_{21}=4/2=2l21​=4/2=2,l31=−2/2=−1l_{31}=-2/2=-1l31​=−2/2=−1。第 2 步:u22=3−2×1=1u_{22}=3-2\times 1=1u22​=3−2×1=1,u23=3−2×1=1u_{23}=3-2\times 1=1u23​=3−2×1=1;l32=(1−(−1)×1)/1=2l_{32}=\big(1-(-1)\times 1\big)/1=2l32​=(1−(−1)×1)/1=2。第 3 步:u33=4−((−1)×1+2×1)=3u_{33}=4-\big((-1)\times 1+2\times 1\big)=3u33​=4−((−1)×1+2×1)=3。

解 Ly=bL\boldsymbol y=\boldsymbol bLy=b:y1=3y_1=3y1​=3,y2=7−2×3=1y_2=7-2\times 3=1y2​=7−2×3=1,y3=5+3−2×1=6y_3=5+3-2\times 1=6y3​=5+3−2×1=6。解 Ux=yU\boldsymbol x=\boldsymbol yUx=y:x3=6/3=2x_3=6/3=2x3​=6/3=2,x2=1−2=−1x_2=1-2=-1x2​=1−2=−1,x1=(3+1−2)/2=1x_1=(3+1-2)/2=1x1​=(3+1−2)/2=1。所以 x=(1,−1,2)T\boldsymbol x=(1,-1,2)^{\mathrm T}x=(1,−1,2)T。

点评:求和项里每一项都是「LLL 的行」乘「UUU 的列」,漏一项是最常见的错。

例题 2(计算:条件数与误差估计)

A=(322.92)A=\begin{pmatrix}3&2\\2.9&2\end{pmatrix}A=(32.9​22​)。求 cond∞(A)\mathrm{cond}_\infty(A)cond∞​(A);若右端项的相对误差为 0.1%0.1\%0.1%,解的相对误差最多可能放大到多少?

解:det⁡A=6−5.8=0.2\det A=6-5.8=0.2detA=6−5.8=0.2,A−1=(10−10−14.515)A^{-1}=\begin{pmatrix}10&-10\\-14.5&15\end{pmatrix}A−1=(10−14.5​−1015​)。∥A∥∞=max⁡(5, 4.9)=5\lVert A\rVert_\infty=\max(5,\,4.9)=5∥A∥∞​=max(5,4.9)=5,∥A−1∥∞=max⁡(20, 29.5)=29.5\lVert A^{-1}\rVert_\infty=\max(20,\,29.5)=29.5∥A−1∥∞​=max(20,29.5)=29.5,cond∞(A)=147.5\mathrm{cond}_\infty(A)=147.5cond∞​(A)=147.5。解的相对误差上界 =147.5×0.1%=14.75%=147.5\times 0.1\%=14.75\%=147.5×0.1%=14.75%。

点评:两行几乎成比例时条件数大,数据千分之一的误差,解可能错到一成以上。

本节小结

  • 高斯消去 = 消元 + 回代,运算量约 n3/3n^3/3n3/3;顺序消去要求各阶顺序主子式非零,等价于 A=LUA=LUA=LU。
  • 主元太小会放大舍入误差;列主元消去法每步在当前列选绝对值最大的元素,乘数都不超过 1。
  • Doolittle 分解先行后列逐步算;追赶法用于对角占优的三对角方程组,运算量与 nnn 成正比;平方根法用于对称正定矩阵。
  • 范数:列和、行和、谱范数;ρ(A)≤∥A∥\rho(A)\le\lVert A\rVertρ(A)≤∥A∥;条件数 ∥A∥∥A−1∥\lVert A\rVert\lVert A^{-1}\rVert∥A∥∥A−1∥ 衡量病态程度,用它估计解的相对误差上界。

学完练一练

按本节考点从本课的课后练习里抽题(每次 10 道以内),做完看解析、错题自动进错题本。

本节内容由 AI 辅助编写,配图由 AI 生成,仅供备考参考;考试要求以《全国各类成人高等学校招生考试大纲(2024 年版)》及浙江省教育考试院当年公布为准。

我要提问免费报名咨询