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

数值分析(一):误差与非线性方程的数值解法

对应数值分析(一)(二):绝对误差、相对误差与有效数字,误差传播与数值稳定性;不动点迭代的收敛性与收敛阶,牛顿迭代法的公式、收敛速度与重根时的处理。

本节考点:误差和有效数字不动点迭代迭代法的收敛阶牛顿迭代法

本节导读

这一节对应数值分析大纲的「(一)误差和有效数字」与「(二)非线性方程的数值解法」。后者分两条:「迭代法的一般理论」,下设「不动点迭代」「迭代法的收敛性和收敛阶」;「牛顿迭代法」。数值分析的说明要求「重点掌握各种算法的基本原理和有关理论」,所以这一节既要会算,也要会说明为什么收敛、收敛得多快。

学完要做到:数出一个近似值有几位有效数字,估计函数值的误差限;判断一个迭代格式收不收敛、是几阶收敛;会用牛顿法算几步,知道它在单根和重根附近的收敛速度。

本节记号:准确值记 xxx,近似值记 x~\tilde xx~;方程的根记 x∗x^*x∗,第 kkk 步迭代值记 xkx_kxk​,误差 ek=xk−x∗e_k=x_k-x^*ek​=xk​−x∗;ppp 是收敛阶,LLL 是压缩映像的常数,rrr 是根的重数。

误差和有效数字

误差从哪里来

用计算机求解实际问题,误差有四个来源:模型误差(数学模型与实际的差别)、观测误差(输入数据的误差)、截断误差(用有限步代替无限过程,如把泰勒级数截成多项式)、舍入误差(计算机字长有限)。数值分析主要研究后两种。

绝对误差、相对误差与误差限

  • 绝对误差 e=x~−xe=\tilde x-xe=x~−x;它的绝对值的一个上界 ε\varepsilonε 叫绝对误差限,即 ∣x~−x∣≤ε\lvert \tilde x-x\rvert\le\varepsilon∣x~−x∣≤ε。
  • 相对误差 er=x~−xxe_r=\dfrac{\tilde x-x}{x}er​=xx~−x​,实际计算常用 x~−xx~\dfrac{\tilde x-x}{\tilde x}x~x~−x​;上界 εr=ε∣x~∣\varepsilon_r=\dfrac{\varepsilon}{\lvert\tilde x\rvert}εr​=∣x~∣ε​ 叫相对误差限。

绝对误差有量纲,比较不同大小的量时看相对误差:测 1 米差 1 毫米,与测 1 千米差 1 毫米,绝对误差相同,精度却差了一千倍。

有效数字

把近似值写成规格化形式

x~=±0.a1a2⋯an×10m,a1≠0\tilde x=\pm 0.a_1a_2\cdots a_n\times 10^{m},\quad a_1\neq 0x~=±0.a1​a2​⋯an​×10m,a1​=0

若 ∣x~−x∣≤12×10m−n\lvert\tilde x-x\rvert\le\tfrac12\times 10^{m-n}∣x~−x∣≤21​×10m−n,就说 x~\tilde xx~ 有 nnn 位有效数字。直白地说:误差不超过某一位的半个单位,从第一个非零数字数到这一位,就是有效数字的位数。按四舍五入得到的数,每一位都是有效数字。

有效数字与相对误差限的关系:有 nnn 位有效数字时,εr≤12a1×10−(n−1)\varepsilon_r\le\dfrac{1}{2a_1}\times 10^{-(n-1)}εr​≤2a1​1​×10−(n−1)。有效数字越多,相对误差越小。

误差传播与数值稳定性

函数值的误差用一阶泰勒展开估计:

ε(f(x~))≈∣f′(x~)∣ ε(x~)\varepsilon\big(f(\tilde x)\big)\approx\lvert f'(\tilde x)\rvert\,\varepsilon(\tilde x)ε(f(x~))≈∣f′(x~)∣ε(x~)

两个数做运算时:和差的误差限不超过两者误差限之和;积的误差限约为 ∣x~2∣ε1+∣x~1∣ε2\lvert\tilde x_2\rvert\varepsilon_1+\lvert\tilde x_1\rvert\varepsilon_2∣x~2​∣ε1​+∣x~1​∣ε2​;商的误差还要除以分母的平方,分母很小时误差被放大。

一个算法在运算中舍入误差不增长,叫数值稳定。设计算法时的几条原则:避免两个相近的数相减(例如 1001−1000\sqrt{1001}-\sqrt{1000}1001​−1000​ 改写成 11001+1000\dfrac{1}{\sqrt{1001}+\sqrt{1000}}1001​+1000​1​);避免除数绝对值远小于被除数;防止大数「吃掉」小数(很多小数先相加再加到大数上);尽量减少运算次数(多项式求值用秦九韶算法)。

迭代法的一般理论

不动点迭代

把方程 f(x)=0f(x)=0f(x)=0 改写成等价形式 x=φ(x)x=\varphi(x)x=φ(x),取初值 x0x_0x0​,按 xk+1=φ(xk)x_{k+1}=\varphi(x_k)xk+1​=φ(xk​) 迭代。若 xk→x∗x_k\to x^*xk​→x∗ 且 φ\varphiφ 连续,则 x∗=φ(x∗)x^*=\varphi(x^*)x∗=φ(x∗),x∗x^*x∗ 叫 φ\varphiφ 的不动点,也就是原方程的根。同一个方程可以改写成很多种 φ\varphiφ,有的收敛、有的发散,关键看 φ\varphiφ 的导数。

全局收敛定理(压缩映像):设 φ\varphiφ 在 [a,b][a,b][a,b] 上满足:① 对任意 x∈[a,b]x\in[a,b]x∈[a,b],φ(x)∈[a,b]\varphi(x)\in[a,b]φ(x)∈[a,b];② 存在常数 0<L<10\lt L\lt 10<L<1,使 ∣φ′(x)∣≤L\lvert\varphi'(x)\rvert\le L∣φ′(x)∣≤L。则 φ\varphiφ 在 [a,b][a,b][a,b] 上有唯一不动点 x∗x^*x∗,任取 x0∈[a,b]x_0\in[a,b]x0​∈[a,b] 迭代都收敛,且有误差估计:

∣x∗−xk∣≤Lk1−L∣x1−x0∣∣x∗−xk∣≤L1−L∣xk−xk−1∣\begin{aligned} \lvert x^*-x_k\rvert&\le\frac{L^{k}}{1-L}\lvert x_1-x_0\rvert \\ \lvert x^*-x_k\rvert&\le\frac{L}{1-L}\lvert x_k-x_{k-1}\rvert \end{aligned}∣x∗−xk​∣∣x∗−xk​∣​≤1−LLk​∣x1​−x0​∣≤1−LL​∣xk​−xk−1​∣​

前一个式子用来事先估计要迭代多少步,后一个用来在计算中判断何时停止:LLL 不太接近 1 时,相邻两次迭代值足够接近就可以停。

局部收敛:若 φ′\varphi'φ′ 在 x∗x^*x∗ 附近连续且 ∣φ′(x∗)∣<1\lvert\varphi'(x^*)\rvert\lt 1∣φ′(x∗)∣<1,则初值取在 x∗x^*x∗ 足够小的邻域内时迭代收敛;∣φ′(x∗)∣>1\lvert\varphi'(x^*)\rvert\gt 1∣φ′(x∗)∣>1 时不收敛。

迭代法的收敛性和收敛阶

设迭代收敛于 x∗x^*x∗,若

lim⁡k→∞ek+1ek p=C≠0\lim_{k\to\infty}\frac{e_{k+1}}{e_k^{\,p}}=C\neq 0k→∞lim​ekp​ek+1​​=C=0

就说迭代是 ppp 阶收敛的。p=1p=1p=1 且 0<∣C∣<10\lt\lvert C\rvert\lt 10<∣C∣<1 叫线性收敛,p>1p\gt 1p>1 叫超线性收敛,p=2p=2p=2 叫平方收敛。阶越高,每步有效数字增加得越快:平方收敛大致每步把有效数字位数翻倍。

判定收敛阶的常用定理:若 φ(p)\varphi^{(p)}φ(p) 在 x∗x^*x∗ 附近连续,且

φ′(x∗)=φ′′(x∗)=⋯=φ(p−1)(x∗)=0φ(p)(x∗)≠0\begin{aligned} \varphi'(x^*)&=\varphi''(x^*)=\cdots=\varphi^{(p-1)}(x^*)=0 \\ &\varphi^{(p)}(x^*)\neq 0 \end{aligned}φ′(x∗)​=φ′′(x∗)=⋯=φ(p−1)(x∗)=0φ(p)(x∗)=0​

则迭代在 x∗x^*x∗ 附近 ppp 阶收敛,并且 lim⁡k→∞ek+1ek p=φ(p)(x∗)p!\lim\limits_{k\to\infty}\dfrac{e_{k+1}}{e_k^{\,p}}=\dfrac{\varphi^{(p)}(x^*)}{p!}k→∞lim​ekp​ek+1​​=p!φ(p)(x∗)​。若 φ′(x∗)≠0\varphi'(x^*)\neq 0φ′(x∗)=0 但绝对值小于 1,就只是线性收敛。

牛顿迭代法

公式和几何意义

把 f(x)f(x)f(x) 在 xkx_kxk​ 处做一阶泰勒展开,令线性部分为零,得

xk+1=xk−f(xk)f′(xk),f′(xk)≠0x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)},\quad f'(x_k)\neq 0xk+1​=xk​−f′(xk​)f(xk​)​,f′(xk​)=0

几何上就是用曲线在 (xk,f(xk))(x_k,f(x_k))(xk​,f(xk​)) 处的切线与 xxx 轴的交点作为下一个近似,所以牛顿法又叫切线法。

收敛速度

牛顿法的迭代函数是 φ(x)=x−f(x)f′(x)\varphi(x)=x-\dfrac{f(x)}{f'(x)}φ(x)=x−f′(x)f(x)​。若 x∗x^*x∗ 是单根(f′(x∗)≠0f'(x^*)\neq 0f′(x∗)=0),可以算出 φ′(x∗)=0\varphi'(x^*)=0φ′(x∗)=0,所以在单根附近至少平方收敛,且

lim⁡k→∞ek+1ek2=f′′(x∗)2f′(x∗)\lim_{k\to\infty}\frac{e_{k+1}}{e_k^{2}}=\frac{f''(x^*)}{2f'(x^*)}k→∞lim​ek2​ek+1​​=2f′(x∗)f′′(x∗)​

牛顿法是局部收敛的,初值要取得离根足够近。一个常用的充分条件:fff 在 [a,b][a,b][a,b] 上二阶连续可导,f(a)f(b)<0f(a)f(b)\lt 0f(a)f(b)<0,f′f'f′ 和 f′′f''f′′ 在区间上都不变号,初值 x0x_0x0​ 满足 f(x0)f′′(x0)>0f(x_0)f''(x_0)\gt 0f(x0​)f′′(x0​)>0,则牛顿迭代单调收敛于根。

重根时怎么办

若 x∗x^*x∗ 是 fff 的 rrr 重根(r≥2r\ge 2r≥2),牛顿法的 φ′(x∗)=1−1r≠0\varphi'(x^*)=1-\dfrac1r\neq 0φ′(x∗)=1−r1​=0,收敛速度会降下来。改进办法有两种:已知重数时用 xk+1=xk−rf(xk)f′(xk)x_{k+1}=x_k-r\dfrac{f(x_k)}{f'(x_k)}xk+1​=xk​−rf′(xk​)f(xk​)​;重数未知时,对 μ(x)=f(x)f′(x)\mu(x)=\dfrac{f(x)}{f'(x)}μ(x)=f′(x)f(x)​ 用牛顿法,因为 x∗x^*x∗ 是 μ(x)\mu(x)μ(x) 的单根。两种改进在 x∗x^*x∗ 附近都恢复平方收敛。

方法每步要算单根附近的收敛阶
一般不动点迭代φ(xk)\varphi(x_k)φ(xk​)一般为 1(φ′(x∗)=0\varphi'(x^*)=0φ′(x∗)=0 时更高)
牛顿迭代法f(xk)f(x_k)f(xk​) 与 f′(xk)f'(x_k)f′(xk​)至少 2
已知重数的改进牛顿法f(xk)f(x_k)f(xk​) 与 f′(xk)f'(x_k)f′(xk​)2(用于重根)

易错提醒

  • ❌ 两个相近的数相减,只要每个数都有 6 位有效数字,差也有 6 位。
    ✅ 相近数相减会损失有效数字,差的相对误差可能很大,要改写算式避开。

  • ❌ 一个迭代格式只要收敛,从任何初值出发都收敛。
    ✅ 多数收敛定理只保证局部收敛,初值要取在根附近;牛顿法对初值尤其敏感。

  • ❌ 误差在一步步减小,就说明迭代是线性收敛的。
    ✅ 收敛阶看极限 ek+1/ek pe_{k+1}/e_k^{\,p}ek+1​/ekp​ 是不是非零常数,不能只看误差在减小。

  • ❌ 牛顿法每一步只要算一次函数值。
    ✅ 每步要同时算 f(xk)f(x_k)f(xk​) 和 f′(xk)f'(x_k)f′(xk​),导数难算时代价不小。

例题精讲

例题 1(计算:有效数字)

3=1.7320508⋯\sqrt3=1.7320508\cdots3​=1.7320508⋯,取近似值 x~=1.732\tilde x=1.732x~=1.732,它有几位有效数字?

解:∣1.732−3∣≈5.08×10−5\lvert 1.732-\sqrt3\rvert\approx 5.08\times 10^{-5}∣1.732−3​∣≈5.08×10−5。规格化写成 x~=0.1732×101\tilde x=0.1732\times 10^{1}x~=0.1732×101,m=1m=1m=1。误差不超过 12×10−3=12×101−4\tfrac12\times 10^{-3}=\tfrac12\times 10^{1-4}21​×10−3=21​×101−4,所以至少 n=4n=4n=4;又因为 5.08×10−55.08\times 10^{-5}5.08×10−5 比 12×10−4=5×10−5\tfrac12\times 10^{-4}=5\times 10^{-5}21​×10−4=5×10−5 略大,n=5n=5n=5 不成立。所以 1.7321.7321.732 有 4 位有效数字。

点评:先求出误差,再找它不超过哪一位的半个单位;这一步要和规格化形式里的 mmm 一起用,才不会数错位置。

例题 2(计算:迭代格式与牛顿法)

方程 x3+x−3=0x^3+x-3=0x3+x−3=0 在 [1,2][1,2][1,2] 内有唯一根 x∗≈1.2134x^*\approx 1.2134x∗≈1.2134。(1)判断 x=3−x3x=\sqrt[3]{3-x}x=33−x​ 与 x=3−x3x=3-x^3x=3−x3 两种迭代格式在根附近是否收敛;(2)取 x0=1x_0=1x0​=1,用牛顿法算两步。

解:(1)φ1(x)=(3−x)1/3\varphi_1(x)=(3-x)^{1/3}φ1​(x)=(3−x)1/3,φ1′(x)=−13(3−x)2/3\varphi_1'(x)=-\dfrac{1}{3(3-x)^{2/3}}φ1′​(x)=−3(3−x)2/31​,在 x∗x^*x∗ 处约为 −0.23-0.23−0.23,绝对值小于 1,局部收敛;φ2(x)=3−x3\varphi_2(x)=3-x^3φ2​(x)=3−x3,φ2′(x∗)=−3(x∗)2≈−4.42\varphi_2'(x^*)=-3(x^*)^2\approx-4.42φ2′​(x∗)=−3(x∗)2≈−4.42,发散。

(2)f′(x)=3x2+1f'(x)=3x^2+1f′(x)=3x2+1。x1=1−−14=1.25x_1=1-\dfrac{-1}{4}=1.25x1​=1−4−1​=1.25;f(1.25)=0.203125f(1.25)=0.203125f(1.25)=0.203125,f′(1.25)=5.6875f'(1.25)=5.6875f′(1.25)=5.6875,x2=1.25−0.0357≈1.2143x_2=1.25-0.0357\approx 1.2143x2​=1.25−0.0357≈1.2143,与根已相差不到 10−310^{-3}10−3。

点评:同一个方程改写成不同的 φ\varphiφ,收敛性可以完全不同;牛顿法两步就接近根,体现了平方收敛。

本节小结

  • 有效数字看误差不超过末位的半个单位,从第一个非零数字数起;有效数字越多,相对误差越小。
  • 函数值误差约等于导数绝对值乘自变量误差;避免相近数相减、小除数、大数吃小数。
  • 不动点迭代:压缩映像条件保证全局收敛,∣φ′(x∗)∣<1\lvert\varphi'(x^*)\rvert\lt 1∣φ′(x∗)∣<1 保证局部收敛;高阶导数在不动点处为零的个数决定收敛阶。
  • 牛顿法 xk+1=xk−f(xk)/f′(xk)x_{k+1}=x_k-f(x_k)/f'(x_k)xk+1​=xk​−f(xk​)/f′(xk​),单根附近至少平方收敛;重根时用改进格式恢复平方收敛。

学完练一练

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

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

我要提问免费报名咨询