数值分析(三):解线性代数方程组的迭代法
对应数值分析(四):Jacobi 迭代与 Gauss-Seidel 迭代的分量形式与矩阵形式,迭代法收敛的充要条件与充分条件,对角占优和对称正定时的结论,收敛速度与所需迭代步数。
本节导读
这一节对应数值分析大纲「(四)解线性代数方程组的迭代法」的两条:「Jacobi 迭代法,Gauss-Seidel 迭代法」与「迭代法敛散性的判定定理和收敛速度」。迭代法从一个初始向量出发,按固定格式逐步逼近解,适合阶数高、零元素多的大型稀疏方程组:每一步只做矩阵与向量的乘法,不改变矩阵的稀疏结构,存储量小。
学完要做到:写出两种迭代的分量形式并会算一两步;会用谱半径、范数、对角占优、对称正定判断收敛;会由谱半径估计要迭代多少步。
本节记号:把系数矩阵分裂成 A=D−L−U,D 是 A 的对角部分,−L、−U 分别是 A 的严格下三角、严格上三角部分(这里的 L、U 与第 3 节的三角分解因子不是一回事);迭代矩阵记 B,ρ(B) 是它的谱半径;x(k) 是第 k 步的迭代向量。
Jacobi 迭代法与 Gauss-Seidel 迭代法
Jacobi 迭代
从第 i 个方程解出 xi(要求 aii=0),右端全部用上一步的值:
xi(k+1)i=aii1(bi−j=i∑aijxj(k))=1,2,⋯,n矩阵形式 x(k+1)=BJx(k)+D−1b,迭代矩阵 BJ=D−1(L+U)=I−D−1A。BJ 的对角元为 0,第 i 行其余元素是 −aij/aii。
Gauss-Seidel 迭代
计算 xi(k+1) 时,前面已经算出的 x1(k+1),⋯,xi−1(k+1) 立即用上:
xi(k+1)=aii1(bi−j<i∑aijxj(k+1)−j>i∑aijxj(k))矩阵形式 x(k+1)=BGx(k)+(D−L)−1b,迭代矩阵 BG=(D−L)−1U。编程时只需一套存储单元,新值算出来就覆盖旧值。
| 对比项 | Jacobi 迭代 | Gauss-Seidel 迭代 |
|---|---|---|
| 用到的值 | 全部用上一步的值 | 本步已算出的分量立即使用 |
| 迭代矩阵 | BJ=D−1(L+U) | BG=(D−L)−1U |
| 存储 | 新旧两套向量 | 一套向量,新值覆盖旧值 |
| 并行性 | 各分量可以同时算 | 分量要依次算 |
迭代法敛散性的判定定理和收敛速度
判定定理
对一般的迭代格式 x(k+1)=Bx(k)+f:
- 充要条件:对任意初始向量都收敛 ⟺ρ(B)<1。
- 充分条件:若某种矩阵范数 ∥B∥=q<1,则迭代收敛,且
范数条件好算但只是充分的:∥B∥≥1 时迭代仍可能收敛,最后要看谱半径。
由系数矩阵直接判断
不算迭代矩阵,也有几条常用的判断:
| 系数矩阵 A 的性质 | 结论 |
|---|---|
| 严格对角占优(每行对角元的绝对值大于同行其余元素绝对值之和) | Jacobi 与 Gauss-Seidel 迭代都收敛 |
| 不可约弱对角占优(每行对角元的绝对值不小于同行其余元素绝对值之和、至少一行严格大于,且矩阵不可约,例如非对角元全不为零) | Jacobi 与 Gauss-Seidel 迭代都收敛 |
| 对称正定 | Gauss-Seidel 迭代收敛 |
| 对称正定,且 2D−A 也正定 | Jacobi 迭代收敛 |
两种迭代谁更快没有一般结论:多数常见问题里 Gauss-Seidel 更快,但也有 Jacobi 收敛而 Gauss-Seidel 发散的例子。对二阶方程组可以直接算出 ρ(BG)=ρ(BJ)2。
收敛速度
误差 e(k)=Bke(0),大致每迭代一步误差缩小到原来的 ρ(B) 倍。定义渐近收敛速度
R(B)=−lnρ(B)要把误差缩小到初始误差的 10−s,大约需要
k≥R(B)sln10步。谱半径越小,收敛越快;ρ(B) 接近 1 时,收敛会非常慢。
易错提醒
-
❌ 阶数不高的稠密方程组,也优先用迭代法。
✅ 迭代法的长处在大型稀疏方程组;阶数不高的稠密方程组,用第 3 节的直接法更省事。 -
❌ 初始向量必须取得很接近解,迭代才会收敛。
✅ 对线性方程组,收不收敛只取决于迭代矩阵,与初始向量无关;初值好只是少迭代几步。 -
❌ 谱半径越大,迭代收敛得越快。
✅ 谱半径越小收敛越快,它越接近 1,收敛越慢。 -
❌ 迭代法和直接法一样,有限步内就能得到精确解。
✅ 迭代法一般只能无限逼近,按误差估计或相邻两步之差决定何时停止。
例题精讲
例题 1(计算:两种迭代各算一步)
方程组 5x1+x2−x3=5,x1+4x2+x3=6,−x1+2x2+6x3=7(精确解为 (1,1,1)T),取 x(0)=0,分别用 Jacobi 和 Gauss-Seidel 迭代算一步。
解:Jacobi:x1(1)=5/5=1,x2(1)=6/4=1.5,x3(1)=7/6≈1.1667。
Gauss-Seidel:x1(1)=1;x2(1)=(6−1)/4=1.25;x3(1)=(7+1−2×1.25)/6≈0.9167。
点评:系数矩阵严格对角占优,两种迭代都收敛;Gauss-Seidel 第一步就用上了新算出的 x1、x2。
例题 2(计算:谱半径判收敛)
A=(2312) 不是对角占优的。判断 Jacobi 与 Gauss-Seidel 迭代是否收敛,哪个快。
解:BJ=(0−3/2−1/20),特征值满足 λ2=43,ρ(BJ)=23≈0.866<1,收敛。二阶时 ρ(BG)=ρ(BJ)2=0.75<1,也收敛,且 Gauss-Seidel 更快。
点评:不对角占优不等于不收敛,充分条件不满足时回到谱半径去判断。
本节小结
- Jacobi:右端全用旧值,BJ=D−1(L+U);Gauss-Seidel:新值立即使用,BG=(D−L)−1U。
- 收敛的充要条件是 ρ(B)<1;某种范数小于 1 是充分条件,并给出误差估计。
- 严格对角占优:两种迭代都收敛;对称正定:Gauss-Seidel 收敛。
- 收敛速度 R(B)=−lnρ(B),误差缩小到 10−s 约需 sln10/R(B) 步。
学完练一练
按本节考点从本课的课后练习里抽题(每次 10 道以内),做完看解析、错题自动进错题本。
本节内容由 AI 辅助编写,配图由 AI 生成,仅供备考参考;考试要求以《全国各类成人高等学校招生考试大纲(2024 年版)》及浙江省教育考试院当年公布为准。