数值分析(一):误差与非线性方程的数值解法
对应数值分析(一)(二):绝对误差、相对误差与有效数字,误差传播与数值稳定性;不动点迭代的收敛性与收敛阶,牛顿迭代法的公式、收敛速度与重根时的处理。
本节导读
这一节对应数值分析大纲的「(一)误差和有效数字」与「(二)非线性方程的数值解法」。后者分两条:「迭代法的一般理论」,下设「不动点迭代」「迭代法的收敛性和收敛阶」;「牛顿迭代法」。数值分析的说明要求「重点掌握各种算法的基本原理和有关理论」,所以这一节既要会算,也要会说明为什么收敛、收敛得多快。
学完要做到:数出一个近似值有几位有效数字,估计函数值的误差限;判断一个迭代格式收不收敛、是几阶收敛;会用牛顿法算几步,知道它在单根和重根附近的收敛速度。
本节记号:准确值记 x,近似值记 x~;方程的根记 x∗,第 k 步迭代值记 xk,误差 ek=xk−x∗;p 是收敛阶,L 是压缩映像的常数,r 是根的重数。
误差和有效数字
误差从哪里来
用计算机求解实际问题,误差有四个来源:模型误差(数学模型与实际的差别)、观测误差(输入数据的误差)、截断误差(用有限步代替无限过程,如把泰勒级数截成多项式)、舍入误差(计算机字长有限)。数值分析主要研究后两种。
绝对误差、相对误差与误差限
- 绝对误差 e=x~−x;它的绝对值的一个上界 ε 叫绝对误差限,即 ∣x~−x∣≤ε。
- 相对误差 er=xx~−x,实际计算常用 x~x~−x;上界 εr=∣x~∣ε 叫相对误差限。
绝对误差有量纲,比较不同大小的量时看相对误差:测 1 米差 1 毫米,与测 1 千米差 1 毫米,绝对误差相同,精度却差了一千倍。
有效数字
把近似值写成规格化形式
x~=±0.a1a2⋯an×10m,a1=0若 ∣x~−x∣≤21×10m−n,就说 x~ 有 n 位有效数字。直白地说:误差不超过某一位的半个单位,从第一个非零数字数到这一位,就是有效数字的位数。按四舍五入得到的数,每一位都是有效数字。
有效数字与相对误差限的关系:有 n 位有效数字时,εr≤2a11×10−(n−1)。有效数字越多,相对误差越小。
误差传播与数值稳定性
函数值的误差用一阶泰勒展开估计:
ε(f(x~))≈∣f′(x~)∣ε(x~)两个数做运算时:和差的误差限不超过两者误差限之和;积的误差限约为 ∣x~2∣ε1+∣x~1∣ε2;商的误差还要除以分母的平方,分母很小时误差被放大。
一个算法在运算中舍入误差不增长,叫数值稳定。设计算法时的几条原则:避免两个相近的数相减(例如 1001−1000 改写成 1001+10001);避免除数绝对值远小于被除数;防止大数「吃掉」小数(很多小数先相加再加到大数上);尽量减少运算次数(多项式求值用秦九韶算法)。
迭代法的一般理论
不动点迭代
把方程 f(x)=0 改写成等价形式 x=φ(x),取初值 x0,按 xk+1=φ(xk) 迭代。若 xk→x∗ 且 φ 连续,则 x∗=φ(x∗),x∗ 叫 φ 的不动点,也就是原方程的根。同一个方程可以改写成很多种 φ,有的收敛、有的发散,关键看 φ 的导数。
全局收敛定理(压缩映像):设 φ 在 [a,b] 上满足:① 对任意 x∈[a,b],φ(x)∈[a,b];② 存在常数 0<L<1,使 ∣φ′(x)∣≤L。则 φ 在 [a,b] 上有唯一不动点 x∗,任取 x0∈[a,b] 迭代都收敛,且有误差估计:
∣x∗−xk∣∣x∗−xk∣≤1−LLk∣x1−x0∣≤1−LL∣xk−xk−1∣前一个式子用来事先估计要迭代多少步,后一个用来在计算中判断何时停止:L 不太接近 1 时,相邻两次迭代值足够接近就可以停。
局部收敛:若 φ′ 在 x∗ 附近连续且 ∣φ′(x∗)∣<1,则初值取在 x∗ 足够小的邻域内时迭代收敛;∣φ′(x∗)∣>1 时不收敛。
迭代法的收敛性和收敛阶
设迭代收敛于 x∗,若
k→∞limekpek+1=C=0就说迭代是 p 阶收敛的。p=1 且 0<∣C∣<1 叫线性收敛,p>1 叫超线性收敛,p=2 叫平方收敛。阶越高,每步有效数字增加得越快:平方收敛大致每步把有效数字位数翻倍。
判定收敛阶的常用定理:若 φ(p) 在 x∗ 附近连续,且
φ′(x∗)=φ′′(x∗)=⋯=φ(p−1)(x∗)=0φ(p)(x∗)=0则迭代在 x∗ 附近 p 阶收敛,并且 k→∞limekpek+1=p!φ(p)(x∗)。若 φ′(x∗)=0 但绝对值小于 1,就只是线性收敛。
牛顿迭代法
公式和几何意义
把 f(x) 在 xk 处做一阶泰勒展开,令线性部分为零,得
xk+1=xk−f′(xk)f(xk),f′(xk)=0几何上就是用曲线在 (xk,f(xk)) 处的切线与 x 轴的交点作为下一个近似,所以牛顿法又叫切线法。
收敛速度
牛顿法的迭代函数是 φ(x)=x−f′(x)f(x)。若 x∗ 是单根(f′(x∗)=0),可以算出 φ′(x∗)=0,所以在单根附近至少平方收敛,且
k→∞limek2ek+1=2f′(x∗)f′′(x∗)牛顿法是局部收敛的,初值要取得离根足够近。一个常用的充分条件:f 在 [a,b] 上二阶连续可导,f(a)f(b)<0,f′ 和 f′′ 在区间上都不变号,初值 x0 满足 f(x0)f′′(x0)>0,则牛顿迭代单调收敛于根。
重根时怎么办
若 x∗ 是 f 的 r 重根(r≥2),牛顿法的 φ′(x∗)=1−r1=0,收敛速度会降下来。改进办法有两种:已知重数时用 xk+1=xk−rf′(xk)f(xk);重数未知时,对 μ(x)=f′(x)f(x) 用牛顿法,因为 x∗ 是 μ(x) 的单根。两种改进在 x∗ 附近都恢复平方收敛。
| 方法 | 每步要算 | 单根附近的收敛阶 |
|---|---|---|
| 一般不动点迭代 | φ(xk) | 一般为 1(φ′(x∗)=0 时更高) |
| 牛顿迭代法 | f(xk) 与 f′(xk) | 至少 2 |
| 已知重数的改进牛顿法 | f(xk) 与 f′(xk) | 2(用于重根) |
易错提醒
-
❌ 两个相近的数相减,只要每个数都有 6 位有效数字,差也有 6 位。
✅ 相近数相减会损失有效数字,差的相对误差可能很大,要改写算式避开。 -
❌ 一个迭代格式只要收敛,从任何初值出发都收敛。
✅ 多数收敛定理只保证局部收敛,初值要取在根附近;牛顿法对初值尤其敏感。 -
❌ 误差在一步步减小,就说明迭代是线性收敛的。
✅ 收敛阶看极限 ek+1/ekp 是不是非零常数,不能只看误差在减小。 -
❌ 牛顿法每一步只要算一次函数值。
✅ 每步要同时算 f(xk) 和 f′(xk),导数难算时代价不小。
例题精讲
例题 1(计算:有效数字)
3=1.7320508⋯,取近似值 x~=1.732,它有几位有效数字?
解:∣1.732−3∣≈5.08×10−5。规格化写成 x~=0.1732×101,m=1。误差不超过 21×10−3=21×101−4,所以至少 n=4;又因为 5.08×10−5 比 21×10−4=5×10−5 略大,n=5 不成立。所以 1.732 有 4 位有效数字。
点评:先求出误差,再找它不超过哪一位的半个单位;这一步要和规格化形式里的 m 一起用,才不会数错位置。
例题 2(计算:迭代格式与牛顿法)
方程 x3+x−3=0 在 [1,2] 内有唯一根 x∗≈1.2134。(1)判断 x=33−x 与 x=3−x3 两种迭代格式在根附近是否收敛;(2)取 x0=1,用牛顿法算两步。
解:(1)φ1(x)=(3−x)1/3,φ1′(x)=−3(3−x)2/31,在 x∗ 处约为 −0.23,绝对值小于 1,局部收敛;φ2(x)=3−x3,φ2′(x∗)=−3(x∗)2≈−4.42,发散。
(2)f′(x)=3x2+1。x1=1−4−1=1.25;f(1.25)=0.203125,f′(1.25)=5.6875,x2=1.25−0.0357≈1.2143,与根已相差不到 10−3。
点评:同一个方程改写成不同的 φ,收敛性可以完全不同;牛顿法两步就接近根,体现了平方收敛。
本节小结
- 有效数字看误差不超过末位的半个单位,从第一个非零数字数起;有效数字越多,相对误差越小。
- 函数值误差约等于导数绝对值乘自变量误差;避免相近数相减、小除数、大数吃小数。
- 不动点迭代:压缩映像条件保证全局收敛,∣φ′(x∗)∣<1 保证局部收敛;高阶导数在不动点处为零的个数决定收敛阶。
- 牛顿法 xk+1=xk−f(xk)/f′(xk),单根附近至少平方收敛;重根时用改进格式恢复平方收敛。
学完练一练
按本节考点从本课的课后练习里抽题(每次 10 道以内),做完看解析、错题自动进错题本。
本节内容由 AI 辅助编写,配图由 AI 生成,仅供备考参考;考试要求以《全国各类成人高等学校招生考试大纲(2024 年版)》及浙江省教育考试院当年公布为准。