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

数值分析(三):解线性代数方程组的迭代法

对应数值分析(四):Jacobi 迭代与 Gauss-Seidel 迭代的分量形式与矩阵形式,迭代法收敛的充要条件与充分条件,对角占优和对称正定时的结论,收敛速度与所需迭代步数。

本节考点:Jacobi 迭代法Gauss-Seidel 迭代法迭代法敛散性的判定收敛速度

本节导读

这一节对应数值分析大纲「(四)解线性代数方程组的迭代法」的两条:「Jacobi 迭代法,Gauss-Seidel 迭代法」与「迭代法敛散性的判定定理和收敛速度」。迭代法从一个初始向量出发,按固定格式逐步逼近解,适合阶数高、零元素多的大型稀疏方程组:每一步只做矩阵与向量的乘法,不改变矩阵的稀疏结构,存储量小。

学完要做到:写出两种迭代的分量形式并会算一两步;会用谱半径、范数、对角占优、对称正定判断收敛;会由谱半径估计要迭代多少步。

本节记号:把系数矩阵分裂成 A=D−L−UA=D-L-UA=D−L−U,DDD 是 AAA 的对角部分,−L-L−L、−U-U−U 分别是 AAA 的严格下三角、严格上三角部分(这里的 LLL、UUU 与第 3 节的三角分解因子不是一回事);迭代矩阵记 BBB,ρ(B)\rho(B)ρ(B) 是它的谱半径;x(k)\boldsymbol x^{(k)}x(k) 是第 kkk 步的迭代向量。

Jacobi 迭代法与 Gauss-Seidel 迭代法

Jacobi 迭代

从第 iii 个方程解出 xix_ixi​(要求 aii≠0a_{ii}\neq 0aii​=0),右端全部用上一步的值:

xi(k+1)=1aii(bi−∑j≠iaijxj(k))i=1,2,⋯ ,n\begin{aligned} x_i^{(k+1)}&=\frac{1}{a_{ii}}\Big(b_i-\sum_{j\neq i}a_{ij}x_j^{(k)}\Big) \\ i&=1,2,\cdots,n \end{aligned}xi(k+1)​i​=aii​1​(bi​−j=i∑​aij​xj(k)​)=1,2,⋯,n​

矩阵形式 x(k+1)=BJx(k)+D−1b\boldsymbol x^{(k+1)}=B_J\boldsymbol x^{(k)}+D^{-1}\boldsymbol bx(k+1)=BJ​x(k)+D−1b,迭代矩阵 BJ=D−1(L+U)=I−D−1AB_J=D^{-1}(L+U)=I-D^{-1}ABJ​=D−1(L+U)=I−D−1A。BJB_JBJ​ 的对角元为 0,第 iii 行其余元素是 −aij/aii-a_{ij}/a_{ii}−aij​/aii​。

Gauss-Seidel 迭代

计算 xi(k+1)x_i^{(k+1)}xi(k+1)​ 时,前面已经算出的 x1(k+1),⋯ ,xi−1(k+1)x_1^{(k+1)},\cdots,x_{i-1}^{(k+1)}x1(k+1)​,⋯,xi−1(k+1)​ 立即用上:

xi(k+1)=1aii(bi−∑j<iaijxj(k+1)−∑j>iaijxj(k))\begin{aligned} &x_i^{(k+1)}= \\ &\frac{1}{a_{ii}}\Big(b_i-\sum_{j\lt i}a_{ij}x_j^{(k+1)}-\sum_{j\gt i}a_{ij}x_j^{(k)}\Big) \end{aligned}​xi(k+1)​=aii​1​(bi​−j<i∑​aij​xj(k+1)​−j>i∑​aij​xj(k)​)​

矩阵形式 x(k+1)=BGx(k)+(D−L)−1b\boldsymbol x^{(k+1)}=B_G\boldsymbol x^{(k)}+(D-L)^{-1}\boldsymbol bx(k+1)=BG​x(k)+(D−L)−1b,迭代矩阵 BG=(D−L)−1UB_G=(D-L)^{-1}UBG​=(D−L)−1U。编程时只需一套存储单元,新值算出来就覆盖旧值。

对比项Jacobi 迭代Gauss-Seidel 迭代
用到的值全部用上一步的值本步已算出的分量立即使用
迭代矩阵BJ=D−1(L+U)B_J=D^{-1}(L+U)BJ​=D−1(L+U)BG=(D−L)−1UB_G=(D-L)^{-1}UBG​=(D−L)−1U
存储新旧两套向量一套向量,新值覆盖旧值
并行性各分量可以同时算分量要依次算

迭代法敛散性的判定定理和收敛速度

判定定理

对一般的迭代格式 x(k+1)=Bx(k)+f\boldsymbol x^{(k+1)}=B\boldsymbol x^{(k)}+\boldsymbol fx(k+1)=Bx(k)+f:

  1. 充要条件:对任意初始向量都收敛 ⟺ρ(B)<1\Longleftrightarrow\rho(B)\lt 1⟺ρ(B)<1。
  2. 充分条件:若某种矩阵范数 ∥B∥=q<1\lVert B\rVert=q\lt 1∥B∥=q<1,则迭代收敛,且
∥x∗−x(k)∥≤qk1−q∥x(1)−x(0)∥\lVert\boldsymbol x^*-\boldsymbol x^{(k)}\rVert\le\frac{q^{k}}{1-q}\lVert\boldsymbol x^{(1)}-\boldsymbol x^{(0)}\rVert∥x∗−x(k)∥≤1−qqk​∥x(1)−x(0)∥

范数条件好算但只是充分的:∥B∥≥1\lVert B\rVert\ge 1∥B∥≥1 时迭代仍可能收敛,最后要看谱半径。

由系数矩阵直接判断

不算迭代矩阵,也有几条常用的判断:

系数矩阵 AAA 的性质结论
严格对角占优(每行对角元的绝对值大于同行其余元素绝对值之和)Jacobi 与 Gauss-Seidel 迭代都收敛
不可约弱对角占优(每行对角元的绝对值不小于同行其余元素绝对值之和、至少一行严格大于,且矩阵不可约,例如非对角元全不为零)Jacobi 与 Gauss-Seidel 迭代都收敛
对称正定Gauss-Seidel 迭代收敛
对称正定,且 2D−A2D-A2D−A 也正定Jacobi 迭代收敛

两种迭代谁更快没有一般结论:多数常见问题里 Gauss-Seidel 更快,但也有 Jacobi 收敛而 Gauss-Seidel 发散的例子。对二阶方程组可以直接算出 ρ(BG)=ρ(BJ)2\rho(B_G)=\rho(B_J)^2ρ(BG​)=ρ(BJ​)2。

收敛速度

误差 e(k)=Bke(0)\boldsymbol e^{(k)}=B^k\boldsymbol e^{(0)}e(k)=Bke(0),大致每迭代一步误差缩小到原来的 ρ(B)\rho(B)ρ(B) 倍。定义渐近收敛速度

R(B)=−ln⁡ρ(B)R(B)=-\ln\rho(B)R(B)=−lnρ(B)

要把误差缩小到初始误差的 10−s10^{-s}10−s,大约需要

k≥sln⁡10R(B)k\ge\frac{s\ln 10}{R(B)}k≥R(B)sln10​

步。谱半径越小,收敛越快;ρ(B)\rho(B)ρ(B) 接近 1 时,收敛会非常慢。

易错提醒

  • ❌ 阶数不高的稠密方程组,也优先用迭代法。
    ✅ 迭代法的长处在大型稀疏方程组;阶数不高的稠密方程组,用第 3 节的直接法更省事。

  • ❌ 初始向量必须取得很接近解,迭代才会收敛。
    ✅ 对线性方程组,收不收敛只取决于迭代矩阵,与初始向量无关;初值好只是少迭代几步。

  • ❌ 谱半径越大,迭代收敛得越快。
    ✅ 谱半径越小收敛越快,它越接近 1,收敛越慢。

  • ❌ 迭代法和直接法一样,有限步内就能得到精确解。
    ✅ 迭代法一般只能无限逼近,按误差估计或相邻两步之差决定何时停止。

例题精讲

例题 1(计算:两种迭代各算一步)

方程组 5x1+x2−x3=55x_1+x_2-x_3=55x1​+x2​−x3​=5,x1+4x2+x3=6x_1+4x_2+x_3=6x1​+4x2​+x3​=6,−x1+2x2+6x3=7-x_1+2x_2+6x_3=7−x1​+2x2​+6x3​=7(精确解为 (1,1,1)T(1,1,1)^{\mathrm T}(1,1,1)T),取 x(0)=0\boldsymbol x^{(0)}=\boldsymbol 0x(0)=0,分别用 Jacobi 和 Gauss-Seidel 迭代算一步。

解:Jacobi:x1(1)=5/5=1x_1^{(1)}=5/5=1x1(1)​=5/5=1,x2(1)=6/4=1.5x_2^{(1)}=6/4=1.5x2(1)​=6/4=1.5,x3(1)=7/6≈1.1667x_3^{(1)}=7/6\approx 1.1667x3(1)​=7/6≈1.1667。

Gauss-Seidel:x1(1)=1x_1^{(1)}=1x1(1)​=1;x2(1)=(6−1)/4=1.25x_2^{(1)}=(6-1)/4=1.25x2(1)​=(6−1)/4=1.25;x3(1)=(7+1−2×1.25)/6≈0.9167x_3^{(1)}=(7+1-2\times 1.25)/6\approx 0.9167x3(1)​=(7+1−2×1.25)/6≈0.9167。

点评:系数矩阵严格对角占优,两种迭代都收敛;Gauss-Seidel 第一步就用上了新算出的 x1x_1x1​、x2x_2x2​。

例题 2(计算:谱半径判收敛)

A=(2132)A=\begin{pmatrix}2&1\\3&2\end{pmatrix}A=(23​12​) 不是对角占优的。判断 Jacobi 与 Gauss-Seidel 迭代是否收敛,哪个快。

解:BJ=(0−1/2−3/20)B_J=\begin{pmatrix}0&-1/2\\-3/2&0\end{pmatrix}BJ​=(0−3/2​−1/20​),特征值满足 λ2=34\lambda^2=\dfrac34λ2=43​,ρ(BJ)=32≈0.866<1\rho(B_J)=\dfrac{\sqrt3}{2}\approx 0.866\lt 1ρ(BJ​)=23​​≈0.866<1,收敛。二阶时 ρ(BG)=ρ(BJ)2=0.75<1\rho(B_G)=\rho(B_J)^2=0.75\lt 1ρ(BG​)=ρ(BJ​)2=0.75<1,也收敛,且 Gauss-Seidel 更快。

点评:不对角占优不等于不收敛,充分条件不满足时回到谱半径去判断。

本节小结

  • Jacobi:右端全用旧值,BJ=D−1(L+U)B_J=D^{-1}(L+U)BJ​=D−1(L+U);Gauss-Seidel:新值立即使用,BG=(D−L)−1UB_G=(D-L)^{-1}UBG​=(D−L)−1U。
  • 收敛的充要条件是 ρ(B)<1\rho(B)\lt 1ρ(B)<1;某种范数小于 1 是充分条件,并给出误差估计。
  • 严格对角占优:两种迭代都收敛;对称正定:Gauss-Seidel 收敛。
  • 收敛速度 R(B)=−ln⁡ρ(B)R(B)=-\ln\rho(B)R(B)=−lnρ(B),误差缩小到 10−s10^{-s}10−s 约需 sln⁡10/R(B)s\ln10/R(B)sln10/R(B) 步。

学完练一练

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

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

我要提问免费报名咨询