数值分析第三版答案知识地图：误差、收敛与算法实现复盘

简介《数值分析》第三版Timothy Sauer教师版习题解答手册面向学习数值计算、计算方法课程的高校学生与授课教师用于核对课后习题思路、验证算法推导与复习章节要点。全包仅1个PDF文件压缩包约6.75MB内容按教材章节编排覆盖多项式求值、浮点与误差、二分法、固定点迭代、Newton法、线性方程组高斯消元与LU分解、插值与Chebyshev/三次样条/Bézier曲线、最小二乘与QR/GMRES、数值微分积分、常微分方程初值问题及边值问题等。解答可帮助读者定位每道题的算法选择和误差分析理解迭代收敛、稳定性与实现细节适合课程作业对照、考前梳理和教师备课参考。已有3384人学习下载。1. 知识地图数值分析第三版到底在练什么数值分析第三版的答案手册最值钱的地方不是核对数字而是把每类算法的「输入—收敛条件—误差量级」三件事并排放。翻一遍目录就能看出来全书只有一条主线把连续的数学问题换成有限步、能复现的离散计算再回答两个问题——算得动吗复杂度、算得准吗误差与稳定性。前四章打地基浮点与有效数字、解方程、线性方程组、插值中间三个工具箱最小二乘、数值微积分、微分方程后半本是出口随机模拟、傅里叶与压缩、特征值、优化。它适合两类人正在跟课、需要对照中间步骤的人和复习阶段想把零散公式串成一张网的人。这张地图先记住后面每一章都是往格子里填东西。2. 误差地基二进制、浮点表示与有效数字丢失数值分析里绝大多数「玄学 bug」都能追到这一章。教材把它放在第 0 章不是热身而是因为后面所有算法的误差分析都要拿这里的三个量做尺子机器精度、舍入规则、条件数。2.1 进制转换与双精度的五个参数整数部分用「除 2 取余、倒序读」小数部分用「乘 2 取整、顺序读」这两条在答案里出现频率极高。典型结果要能背出来几个(79)₁₀ (1001111)₂(227)₁₀ (11100011)₂(1/8)₁₀ (0.001)₂而 1/3、5/7、0.1 这类会进入循环(0.1)₁₀ (0.00011001100…)₂这就是「0.10.2 不等于 0.3」的根不是语言的问题是表示的问题。双精度浮点的结构必须张口就来参数双精度取值复习时要能说清的点符号位1 位0 为正1 为负指数位11 位偏置 1023规格化指数范围 -1022 ~ 1023尾数位52 位另有隐含的 1有效精度 53 位二进制机器精度 ε2⁻⁵² ≈ 2.22×10⁻¹⁶满足 1ε ≠ 1 的最小 ε最大可表示数约 1.8×10³⁰⁸再乘就溢出成 inf答案里反复考的「舍入到最近」规则只有一句话看第 53 位是 0 就舍、是 1 就入恰好卡在中点时取偶。练习里 fl(1/3)、fl(2/3)、fl(0.9)、fl(9.6)、fl(100.2) 这一串就是让你把 53 位截断点找出来别小看判卷时错一位整题就没了。2.2 有效数字丢失减法才是真正的元凶「损失有效数字」loss of significance这一节的核心结论很反直觉乘法除法都还好真正吃掉精度的是两个相近数相减。答案里有一组经典题1 (2⁻⁵¹ 2⁻⁵³) 存进双精度再减 1结果是 2⁻⁵¹而不是精确值 2⁻⁵¹ 2⁻⁵³换成 1 (2⁻⁵¹ 2⁻⁵² 2⁻⁵³)舍入后减回来变成 2⁻⁵⁰误差直接翻倍。小量加到 1 上时低位被尾数长度挤掉了。工程上的对策是恒等变形把「大数减小数」改写成「小数除以大数」二次求根公式 x (−b ± √(b²−4ac)) / (2a)当 b² ≫ 4ac 时与 −b 同号的那个根发生相消改用 x₁ (−b − sign(b)√(b²−4ac)) / (2a)、x₂ c / (a·x₁) 求另一个根。(1 − cos x)/x² 在 x→0 时改成 2sin²(x/2)/x²。√(x1) − √x 改成 1 / (√(x1) √x)。提示这类题在答案里通常只给最终值复习时要自己补一步「为什么这么变形」否则考场上认不出来。配套的概念是条件数。函数求值问题的误差放大因子是 |x·f′(x)/f(x)|值接近 1 说明问题本身良态值很大说明问题病态——这时候算法再好也救不回来只能换公式或者提高精度。2.3 嵌套乘法Horner 的代价账多项式求值是全书第一个真正的算法。朴素写法要算 x²、x³…n 次多项式大约 n(n1)/2 次乘法嵌套写法把它压到 n 次乘法加 n 次加法而且中间量更少、舍入误差更小。def horner(coeffs, x): # coeffs 按最高次到常数项排列[a_n, ..., a_1, a_0] acc 0.0 for c in coeffs: acc acc * x c # 每一步只做一次乘、一次加 return acc # 6x^4 x^3 5x^2 x 1 在 x 1/3 处答案给的是 2 print(horner([6, 1, 5, 1, 1], 1/3))这段代码对应教材 0.1 节的两种嵌套形式。参数 coeffs 的顺序千万别写反倒过来就是另一个多项式x 为浮点时累加顺序固定结果可复现。答案里还有一类变体P(x) a₀ x⁵(a₅ x⁵(a₁₀ x⁵a₁₅))先算 x²、x⁴、x⁵再做 3 次嵌套乘加总共 6 次乘法 3 次加法——这类「按幂次跳着嵌套」的题考的是数乘法的次数不是算具体值一定要写清楚「几次乘法、几次加法」答案里给的就是这个计数。3. 方程与线性系统收敛判据和误差放大因子这一章是全书分值最重的一块。解方程和解线性方程组看起来是两件事其实共用一套语言迭代、收敛速度、条件数。复习时把「收敛条件」和「收敛阶」做成一张表比背十个例题有用。3.1 解方程的四种打法与收敛阶方法迭代式收敛条件收敛阶每步代价二分法取区间中点保留异号半边连续 端点异号线性误差每步减半1 次函数求值不动点迭代x_{k1} g(x_k)根附近 |g′(r)| 1线性速率 |g′(r)|1 次 g 求值牛顿法x − f(x)/f′(x)f′(r) ≠ 0初值足够近二次f 与 f′ 各一次割线法用差商替代导数初值足够近1.618超线性每步 1 次新求值二分法的迭代次数可以直接算k ≥ log₂((b−a)/tol)区间长度 1、要求 10⁻¹⁰ 时大约 34 步这是「稳但慢」的量化版本。牛顿法的误差关系是 e_{k1} ≈ (f″(r) / 2f′(r))·e_k²有效数字大约每步翻倍这也是它一旦收敛就快得离谱的原因。def newton(f, df, x0, tol1e-12, maxit50): x x0 for k in range(maxit): fx, dfx f(x), df(x) if dfx 0: raise ZeroDivisionError(导数为零牛顿法失效) step fx / dfx x - step if abs(step) tol: # 用步长判停而不是用 |f(x)| return x, k 1 return x, maxit停止条件用 |Δx| 而不是 |f(x)|是很多人踩过的坑函数在根附近很平坦时|f(x)| 早就小于 tol 了x 却还差得远。tol 也别一律用绝对值量级大的根要换成相对判据 |Δx|/|x| tol。还有一个必须记住的结论来自「精度极限」那一节如果 f 的计算本身带有相对误差 ε那么单根最多算到约 ε 的精度m 重根只能算到约 ε^(1/m)。这解释了为什么有些题无论怎么迭代误差都卡在 10⁻⁸ 不降——不是代码写错了是问题本身到顶了。3.2 高斯消元、LU 分解与 PALU 的必要性消元的代价是 2n³/3 次乘除回代再加 n² 量级这是后面所有矩阵算法的比较基准。LU 分解把消元过程存下来同一系数矩阵换右端项时只做前代回代代价降到 n²。为什么必须选主元因为主元很小时乘子 f a_ik / a_kk 会被放大误差在消元过程中被成倍搬运。部分主元列主元把 |L| 的元素控制在 1 以内代价只是多一次比较所以工程实现里基本没有不加主元的。def gauss_solve(A, b): n len(A) M [row[:] [bi] for row, bi in zip(A, b)] # 增广矩阵 for k in range(n): p max(range(k, n), keylambda i: abs(M[i][k])) # 选取列主元所在行 if abs(M[p][k]) 1e-14: raise ValueError(主元接近零矩阵可能奇异) M[k], M[p] M[p], M[k] # 交换行对应置换矩阵 P for i in range(k 1, n): f M[i][k] / M[k][k] for j in range(k, n 1): M[i][j] - f * M[k][j] x [0.0] * n for i in reversed(range(n)): # 回代 s sum(M[i][j] * x[j] for j in range(i 1, n)) x[i] (M[i][n] - s) / M[i][i] return x这段是带部分主元的消元等价于先做 PA LU 再解。参数上要能说清三件事p 是列主元行号f 是乘子它的绝对值不会超过 1回代从最后一行往上。误差分析那一节的关键词是误差放大因子条件数‖A‖·‖A⁻¹‖。它衡量的是「右端项扰动一点解会变多少」是矩阵本身的属性。答案里有些题让你比较不同矩阵在同样扰动下的解的变化本质就是算条件数看清这一点题目就变简单了。3.3 迭代法与特殊矩阵Jacobi、Gauss-Seidel 与 Cholesky大规模稀疏矩阵不能直接消元得用迭代。判断收敛的统一标准是迭代矩阵的谱半径小于 1实操中常用的充分条件是严格对角占优也就是每行对角元的绝对值大于该行其余元素绝对值之和——这条判定在选择题里几乎必考写起来快还不容易错。方法更新方式收敛的常用充分条件说明Jacobi全部用上一轮的旧值严格对角占优可并行收敛最慢Gauss-Seidel用本轮已更新的新值严格对角占优或 SPD一般比 Jacobi 快约一倍SOR在 GS 基础上加松弛因子 ω0 ω 2最优 ω 依赖谱半径ω 取错会比 GS 还慢共轭梯度只需矩阵-向量乘A 对称正定稀疏 SPD 的首选对称正定矩阵还有一条捷径Cholesky 分解 A RᵀR代价约是 LU 的一半还不用选主元因为正定性保证主元不会为零。这条性质在最小二乘的正规方程里会再次出现两处一起记效果最好。非线性方程组则把牛顿法搬到多维x_{k1} x_k − J(x_k)⁻¹F(x_k)其中 J 是雅可比矩阵实际实现里不求逆而是每步解一个线性方程组。这里最容易丢分的是「雅可比矩阵的每一行对应哪个方程」写反一行结果全错。4. 逼近与求解插值、最小二乘、数值积分与微分方程从这一章开始题目从「求一个数」变成「求一个函数或一条曲线」。四个模块的共同问题是同一个用有限个信息去近似无穷维的对象误差从哪里来、能压到多小。4.1 插值与样条误差公式和节点选择n1 个互异节点上的插值多项式存在且唯一但「唯一」不等于「好用」。用范德蒙矩阵直接解系数在数值上是灾难条件数随 n 指数增长正确姿势是牛顿差商表O(n²) 时间、增量式加节点。插值误差公式是这一节的命门f(x) − p(x) f⁽ⁿ⁺¹⁾(ξ) / (n1)! · ∏(x − x_i)它告诉你两件事误差和节点乘积有关所以节点位置能优化也和 (n1) 阶导数有关所以函数越「抖」误差越大。等距节点在区间两端会出现龙格现象把节点换成 Chebyshev 点就能压住x_k cos((2k1)π / (2n2))k 0, 1, …, n这些点在区间两端更密正好抵消端点处 (x − x_i) 乘积变大的趋势。答案里涉及「为什么换节点误差就小」的题答到「最小化节点多项式乘积的最大值」就到位了。三次样条换了个思路不追求一个高次多项式而是分段三次、整体光滑。n 段曲线有 4n 个系数插值条件 2n 个、内节点处 S、S′、S″ 连续各 n−1 个还差 2 个靠边界条件补自然样条令两端二阶导为零夹持样条给定两端斜率。这个「数条件」的方法要会考试常直接问「还缺几个条件」。Bézier 曲线是给几何造型用的用 Bernstein 基表示控制点构成凸包曲线必在凸包内。de Casteljau 算法用反复线性插值求点数值上比直接展开 Bernstein 多项式稳定得多。4.2 最小二乘正规方程与 QR 的分水岭超定方程组没有精确解就退而求其次最小化 ‖Ax − b‖₂。教科书第一个给出的是正规方程 AᵀA x Aᵀb形式简单代价是条件数平方cond(AᵀA) cond(A)²。A 的条件数是 10⁸ 时正规方程的条件数就是 10¹⁶双精度下有效数字直接归零这就是「公式对、结果错」的典型来源。方法适用场景代价数值稳定性正规方程小规模、条件数小 10³n³/3 量级差条件数平方QR 分解中小规模通用约 2mn² − 2n³/3好正交变换不放大误差GMRES大规模稀疏每次迭代一次矩阵-向量乘依赖预条件迭代次数不确定QR 的做法是先分解 A QRQ 正交、R 上三角再解 Rx Qᵀb。因为正交矩阵的 2-范数为 1不会放大误差实现上用 Householder 反射比古典 Gram-Schmidt 稳修正 Gram-Schmidt 是折中方案。判分时写「用 QR 而不是正规方程」并能说出理由比写出结果更重要。非线性最小二乘则是把高斯-牛顿法搬过来每步用雅可比矩阵做线性化解一个线性最小二乘当雅可比接近奇异或者残差很大时加阻尼变成 Levenberg-Marquardt本质是在高斯-牛顿和梯度下降之间插值。4.3 数值微分与积分步长不是越小越好数值微分的截断误差和舍入误差方向相反步长 h 越小截断误差降但 f(xh) − f(x) 的相消误差被 h 除掉后放大。总误差大致是 C·h^p ε/h中心差商的最优步长约 ε^(1/3) ≈ 6×10⁻⁶前向差商约 ε^(1/2) ≈ 1.5×10⁻⁸。做实验时画一张 log(误差)–log(h) 的曲线最优点一目了然这比背结论印象深。数值积分这边Newton-Cotes 系列的阶要分清复合梯形误差 −(b−a)h²/12·f″二阶复合 Simpson 误差 −(b−a)h⁴/180·f⁽⁴⁾四阶m 翻倍误差降 16 倍。def simpson(f, a, b, m): # m 必须是偶数区间被分成 m 个等长小区间 h (b - a) / m s f(a) f(b) for i in range(1, m): s (4 if i % 2 else 2) * f(a i * h) # 奇数点权 4偶数点权 2 return s * h / 3参数 m 直接决定精度m 从 10 变成 20误差理论上降到 1/16。要求给定时可以用误差公式反解 m这也是常见考题。Romberg 积分把这套「阶」玩成了加速器用梯形公式在 h、h/2、h/4 上算一串值再做 Richardson 外推把 O(h²) 逐级抬到 O(h⁴)、O(h⁶)。手算时画那张三角形表第一列是梯形值后面每列是前一列的加权外推权重是 4、16、64 这样的幂次。高斯求积是另一种思路节点和权重一起选n 个节点就能精确积分 2n−1 次多项式比 Newton-Cotes 的 n−1 次高出一倍。节点是 Legendre 多项式的根权重由积分公式给出实际使用查表就行。自适应求积则是工程上的解法比较 S(a,m) S(m,b) 与 S(a,b) 的差超过容差就把区间二分哪里难算往哪里加密。4.4 微分方程稳定性、刚性与网格比初值问题的基本盘是 Euler 法局部截断误差 O(h²)全局误差 O(h)一阶方法。改进的 Taylor 法和 Runge-Kutta 一层层往上抬经典 RK4 每步 4 次函数求值全局四阶。def rk4(f, t0, y0, h, n): t, y t0, y0 for _ in range(n): k1 f(t, y) k2 f(t h/2, y h*k1/2) k3 f(t h/2, y h*k2/2) k4 f(t h, y h*k3) y h * (k1 2*k2 2*k3 k4) / 6 # 四点加权平均 t h return t, y四个 k 分别是在起点、两个中点、终点处的斜率估计权重 1:2:2:1 来自 Simpson 公式的系数这不是巧合RK4 的推导正是用求积公式匹配 Taylor 展开。刚性方程是这一章的分水岭显式方法为了稳定步长被最快的衰减模态锁死明明解很平滑h 却小得离谱。这时要换隐式方法后退 Euler、梯形法它们绝对稳定代价是每步要解一个方程非线性时还得内层迭代。多步法Adams-Bashforth 显式、Adams-Moulton 隐式、BDF用历史点换效率启动需要单步法提供前几个点。边值问题有三条路打靶法把边值问题变成初值问题反复试有限差分法把导数换成差商得到三对角线性系统用追赶法 O(n) 求解配点法和有限元法用基函数展开弱形式降低了对解的光滑性要求。偏微分方程按类型分抛物型热传导显式格式要满足网格比约束双曲型波动有类似的稳定性条件椭圆型Laplace是边值问题离散后解大型稀疏线性系统。4.5 变换与特征值FFT、压缩与 SVD三角插值用复指数或正余弦基代替多项式基DFT 的计算量本来是 O(n²)FFT 用分治把偶数项和奇数项拆开降到 O(n log n)n 2²⁰ 时差三个数量级这就是它值得单独一章的原因。压缩那一章的三件套要能对上号DCT 把图像能量集中到低频二维 DCT 后量化高频系数人眼几乎看不出来Huffman 编码对量化后的符号做变长编码出现频率高的用短码MDCT 用重叠窗消除音频的块边界效应是音频压缩的核心变换。特征值部分幂迭代求主特征值收敛速度由 |λ₂/λ₁| 决定比值接近 1 时慢得让人怀疑人生这时要上位移或反幂迭代。QR 算法把矩阵迭代成上三角配合位移加速收敛。SVD 是收尾的万能工具条件数等于 σ₁/σₙ最小二乘、降维、去噪都能用它解释秩亏缺的判断也看奇异值有没有掉到机器精度以下。优化这一章相对轻无导数方法黄金分割、逐次抛物插值只依赖函数值适合导数难求的场景有导数方法里牛顿法二阶收敛但要海森矩阵梯度下降稳但慢共轭梯度是两者之间实用的折中。5. 易错点复盘五个最容易翻车的地方答案对不上八成不是算错而是前提条件漏了。下面五条是按「错误率×隐蔽程度」排出来的每条都给出补法。5.1 把收敛阶当成快慢的唯一指标本文还有配套的精品资源点击获取