本页目录

数值 III · 方程求根、插值与逼近

两个古老而常用的主题。求根是"迭代思想"的教学样板（二分的稳、Newton 的快、不动点的统一视角）；插值与逼近回答"怎么用简单函数替身复杂函数"——以及那个著名的反例：对特定函数使用等距节点做全局高次插值时，加点也可能更糟的 Runge 现象。

学习层：快的步骤，什么时候仍然有证书？

1. 先预测，再打开两本账

求根时先不要看轨迹：对当前函数预设，判断二分法是否拥有连续性与变号证书；再判断一个很小的 \(|f(x)|\) 是否已经足以保证很小的 \(|x-r|\)。插值时先判断：在 Runge 函数的均匀误差上，等距节点还是端部加密的 Chebyshev 节点更可靠，以及这个判断需要哪些函数与误差范数条件。

实验有一个预测门：选择预设、回答当前模式的两个判断，再点击“核对预测”才会显示曲线、数值和逐步账本。改变函数、步数或节点数后，预测会重新锁定；这样“先写下条件，再看结果”不会被图形的第一眼替代。

2. 最小模型：三种求根步骤各自保证什么？

设 \(f\) 在 \([a,b]\) 上连续，且 \(f(a)f(b)\leq0\)。二分法令 \(m=(a+b)/2\)，保留仍然变号的一半区间。它的证书是

\[ r\in[a_k,b_k],\qquad |m_k-r|\leq\frac{b_k-a_k}{2}; \]

证书来自中间值定理，不来自“当前残差看起来很小”。Newton 步

\[ x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)} \]

是局部线性化：单根 \(f'(r)\neq0\)、初值落在合适邻域且导数不太小时，才有局部二次收敛的保证；它本身不维护区间，候选点可能越界。保守/阻尼 Newton 保留一个有效变号区间，只有当 Newton 候选点在区间内且残差下降时才接受，否则缩短步长或回退到中点。它的区间证书与二分同源，但速度不必每步二次。

还有一条容易漏掉的区别：对任意区间内点 \(x_k\)，仅由 \(r\in[a_k,b_k]\) 能保证的是

\[ |x_k-r|\le\max(x_k-a_k,b_k-x_k). \]

只有 \(x_k\) 恰为中点才可使用半宽。实验的保守 Newton 证书已按当前点计算，并且所有候选都对当前收缩区间检查。固定预设用 \(|f(x_k)|\le10^{-14}\) 或区间宽度 \(\le10^{-12}\max(1,|x_k|)\) 停止，避免机器精度下无法“继续严格下降”而把好解推远。残差停止只是数值规则；平根仍可能有较大根误差。浮点函数求值的符号也不是严格区间算术证书。

三种量必须分列记录：

\[ \text{残差 }|f(x_k)|,\qquad \text{根误差 }|x_k-r|,\qquad \text{区间证书 }r\in[a_k,b_k]. \]

若 \(f'(r)\) 很小，局部反推还会把残差放大成根误差：由 \(f(x)\approx f'(r)(x-r)\) 可见，小残差不普遍等于小根误差。实验将“导数过小”“候选越界”“没有有效变号区间”单独列为状态，不把它们埋进一个收敛数字。

3. 插值的稳定计算：节点、公式、误差范数

对节点 \(x_i\) 和数据 \(y_i=f(x_i)\)，用重心公式

\[ P_N(x)=\frac{\displaystyle\sum_{i=0}^{N-1}\frac{w_i y_i}{x-x_i}} {\displaystyle\sum_{i=0}^{N-1}\frac{w_i}{x-x_i}},\qquad w_i=\frac1{\displaystyle\prod_{j\ne i}(x_i-x_j)}. \]

脚本对权重乘积做对数缩放来构造 \(w_i\)，并在 \(x=x_i\) 时直接返回 \(y_i\)；实际求值使用上面的稳定重心式，避免先展开幂基或把巨大乘积带入计算。比较的是

\[ E_N=\max_{x\in[-1,1]}|f(x)-P_N(x)|, \qquad \Lambda_N=\max_{x\in[-1,1]} \frac{\sum_i\left|\frac{w_i}{x-x_i}\right|} {\left|\sum_i\frac{w_i}{x-x_i}\right|}, \]

其中 \(\Lambda_N(x)\) 是 Lebesgue 函数，\(\Lambda_N\) 是它的最大值。Chebyshev 节点的优势是对区间上的光滑函数、均匀范数和 Runge 型端部振荡提供更好的稳定/逼近尺度；它不是对任意噪声数据、任意权重范数或奇异函数的无条件定理。

无 JavaScript 时的静态读法：本实验固定函数，不允许把交互中的“示例”误读成所有函数的定理。求根预设及其条件如下；“区间证书”只有在函数在区间上连续并且端点变号（或端点已经是根）时才有意义。

预设 \(f(x)\) \([a,b]\) 已知根 \(r\) 要留意的边界
余弦交点 \(\cos x-x\) \([0,1]\) \(0.7390851332\ldots\) 连续、单根，Newton 可作局部比较
三次方程 \(x^3-x-1\) \([1,2]\) \(1.3247179572\ldots\) 连续、单根；初值离开邻域时仍可能越界
平根提示 \((x-1)^3\) \([0,2]\) \(1\) 有变号但 \(f'(r)=0\)，不适用单根二次收敛保证
无变号 \((x-1)^2\) \([0,2]\) \(1\) 连续但端点同号，二分无区间证书

二分、Newton 与保守 Newton 的静态账本读法是：

方法 每步 残差栏 根误差栏 区间证书栏 状态栏
二分 \(m=(a+b)/2\)，保留变号半区间 \(\lvert f(m)\rvert\) \(\lvert m-r\rvert\) \(r\in[a,b]\)，所以 \(\lvert m-r\rvert\le(b-a)/2\) 连续/变号不满足时停止
Newton \(x-f(x)/f'(x)\) \(\lvert f(x)\rvert\) \(\lvert x-r\rvert\) 无（除非另行护栏） \(\lvert f'(x)\rvert\) 过小或候选越界
保守/阻尼 Newton 接受区间内的降残差步，否则减半或取中点 \(\lvert f(x)\rvert\) \(\lvert x-r\rvert\) 当前点到区间两端距离的较大者 接受 Newton、阻尼、区间回退

因此，若某一行的 \(|f(x)|\) 很小而 \(|x-r|\) 仍不小，不能据此否定二分证书；应检查 \(f'(r)\)、单根假设和区间是否仍然有效。脚本可用时，表中每一行都会同时显示这四个数值/状态，并把 raw Newton 的越界与保守 Newton 的回退分开。

插值部分固定 Runge 函数

\[ f(x)=\frac1{1+25x^2},\qquad -1\le x\le1, \]

并比较同样数量 \(N\) 个节点：

\[ x_i^{\rm eq}=-1+\frac{2i}{N-1},\qquad x_i^{\rm ch}=\cos\frac{i\pi}{N-1}\quad(0\le i<N), \]

（实现按从左到右排序）。静态判断表为：

节点 端部分布 Runge 均匀最大误差 Lebesgue 读法 条件
等距 端部稀疏 次数升高时端部振荡可能放大 \(\Lambda_N(x)\) 在端部形成高峰 特定 Runge 例子、全局高次插值
Chebyshev-Lobatto 端部加密 通常显著压低该例的 \(E_N\) \(\Lambda_N\) 更均衡，\(\Lambda_N\) 较小 光滑函数与均匀范数等条件下的比较

改变 \(N\) 后应同时看 \(E_N^{\rm eq},E_N^{\rm ch}\) 与 \(\Lambda_N^{\rm eq}(x),\Lambda_N^{\rm ch}(x)\)；交互数值是在均匀采样网格上近似最大值，不能把有限网格读成解析极值。只看插值曲线经过节点，也不能判断区间内部误差。Lebesgue 常数只是从节点数据误差到插值误差的放大因子，不是“Chebyshev 对所有任务永远最优”的口号。

4. 误区与迁移

  • “二分总能收敛”是错的。 需要函数在区间上连续且端点变号；同号端点可能包着偶重根，也可能根本没有根。
  • “Newton 比二分快，所以应替代二分”是错的。 Newton 是局部方法；导数过小、初值不在单根邻域或候选越界时，保守护栏才是可解释的退路。
  • “小残差就是小根误差”是错的。 还要看导数尺度、根的重数、输入/输出条件数；实验把两者分账正是为了阻止这个偷换。
  • “Runge 现象证明高次插值总是坏”是错的。 它是一个特定函数、区间、等距节点和均匀误差范数下的反例；节点策略、函数正则性与误差范数都要写清楚。
  • “Chebyshev 节点无条件最好”也是错的。 这里的优势对应光滑函数的全局插值和区间均匀误差；噪声、非均匀权重、奇异点或分段方法会改变选择。

5. 迁移题：证书究竟约束哪个点？

  1. 已知 \(r\in[0,1]\)，当前点为 \(x=0.9\)，能保证误差不超过 \(0.5\) 吗？
  2. 对 \(f(x)=(x-1)^3\)，残差 \(10^{-12}\) 对应的根误差是多少？
  3. 已知 \(|f'|\ge m>0\) 于包含 \(x,r\) 的区间，如何从残差推出误差界？这比仅知道“单根”多了什么？
展开核对：半宽、残差与导数下界
  1. 不能；根可能在 \(0\)，误差可达 \(0.9\)。中点 \(0.5\) 才享有半宽 \(0.5\) 的界。
  2. \(|x-1|=10^{-4}\)。小残差不能不经缩放就被称作同样小的坐标误差。
  3. 中值定理给 \(|f(x)-f(r)|=|f'(\xi)||x-r|\ge m|x-r|\)，故误差不超过 \(|f(x)|/m\)。需要整个相关区间上的可验证下界，不能只用未知根处“导数非零”替代。

先修回链：中值定理、浮点误差。实现中可参考 SciPy brentq 的连续性、变号与坐标停止容差说明；本实验的保守 Newton 并非 Brent 算法。

1. 非线性方程求根 \(f(x) = 0\)

Newton 法切线求根

图 3.1Newton 法：在当前点作切线，切线与横轴的交点是下一个猜测——在足够光滑的单根附近局部二次收敛。

二分法：连续函数变号区间反复对半（零点定理，数分 I 的算法化）。在连续与变号假设成立、函数求值符号可靠时，每步区间减半——线性收敛、区间证书稳健；要把绝对误差压到 \(\varepsilon\)，步数约为 \(\log_2\frac{b-a}{\varepsilon}\)。打底用。

不动点迭代（统一视角）：改写 \(f(x) = 0 \iff x = g(x)\)，迭代 \(x_{k+1} = g(x_k)\)。

定理（局部收敛） \(g\) 连续可微，\(|g'(x^*)| < 1\) ⇒ 附近迭代收敛（误差 \(e_{k+1} \approx g'(x^*)e_k\)，线性收敛率 \(|g'|\)）；\(|g'(x^*)| > 1\) 则推开。 （压缩映像原理的局部版——ODE 页 Picard 迭代、本页 Newton 法、值迭代（优化 IV）全是这一个定理的分身。同一方程的不同改写 \(g\) 收敛性天差地别——改写是技术活，例 1 演示。）

Newton 法：切线代曲线（数分 II 线性化的算法化）：

\[ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} \]

二次收敛（\(e_{k+1} \approx \frac{|f''|}{2|f'|}e_k^2\)——有效数字每步翻倍；视角二：它是 \(g = x - f/f'\) 的不动点迭代且 \(g'(x^*) = 0\)，"收敛率为零"即超线性）。代价与风险：要导数、单根附近才保证、初值差会飞（实务：二分圈定 + Newton 收尾）。割线法：差商代导数，收敛阶 \(\approx 1.618\)（黄金比！），免导数——不会求导时的 Newton。🔗 优化 II 的 Newton/拟 Newton 正是本节在 \(\nabla f = 0\) 上的多维版；torch 里 rsqrt 类硬件指令的内部实现也是 Newton 迭代。

2. 多项式插值

问题：过 \(n+1\) 个点 \((x_i, y_i)\) 求次数 \(\leq n\) 的多项式（存在唯一——Vandermonde 行列式非零，高代 II）。两种写法同一多项式：

Lagrange 形式（理论顺手）：\(P_n(x) = \sum_i y_i\, \ell_i(x)\)，基函数 \(\ell_i(x) = \prod_{j \neq i}\frac{x - x_j}{x_i - x_j}\)（在 \(x_i\) 取 1、其余节点取 0）。

Newton 形式（计算顺手）：\(P_n(x) = f[x_0] + f[x_0,x_1](x - x_0) + f[x_0,x_1,x_2](x-x_0)(x-x_1) + \cdots\)，系数是差商（差商表递推 \(f[x_i..x_j] = \frac{f[x_{i+1}..x_j] - f[x_i..x_{j-1}]}{x_j - x_i}\)）——加一个新点只需添一项，增量友好。

误差余项（Taylor 余项的插值版，结构完全平行——数分 II）：

\[ f(x) - P_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^{n}(x - x_i) \]

3. Runge 现象与两条出路

Runge 现象高次插值边缘振荡

图 3.2Runge 现象：对该 Runge 函数使用等距节点做全局高次插值，端部误差会随所取次数序列显著放大；“加点”不自动等于“更准”。

反例（Runge, 1901）：\(f(x) = \frac{1}{1 + 25x^2}\) 在 \([-1,1]\) 上取越来越密的等距节点做全局插值时，插值多项式不在整个区间上一致收敛，端部会出现不断放大的振荡。根源可从节点多项式、Lebesgue 放大与函数复奇点共同理解，不能只把责任归给某一个余项因子。"多项式次数"可能成为过拟合旋钮——这与 ai 课 01 讲的偏差—方差问题相通；对带噪数据强制穿过每点通常会放大噪声，但是否“必然变差”仍取决于噪声模型、节点、度量与正则化。

出路一（换节点）：取 Chebyshev 根 \(x_i = \cos\frac{(2i+1)\pi}{2n+2}\)（端部加密），其首一节点多项式在 \([-1,1]\) 上达到 minimax 尺度；上方实验使用的是同时包含两个端点的 Chebyshev–Lobatto 节点 \(x_i=\cos\frac{i\pi}{n}\)。两族公式不同，但都把节点向端部聚集，并显著改善本页 Runge 例子的均匀误差与 Lebesgue 放大；不能把其中一条公式悄悄换成另一条（谱方法的地基，知其所以然即可）。

出路二（降次分段）——三次样条：每段三次多项式，节点处 \(C^2\) 拼接（函数、一二阶导全连续）+ 两个边界条件 ⇒ 系数由三对角方程组唯一定（追赶法 \(O(n)\) 解，上一页的特例）。样条以分段低次控制全局高次振荡，并提供平滑连接；普通三次样条仍可能过冲，保单调或保形需要额外设计。样条广泛用于 CAD、字体与动画曲线；是否选分段方法仍要看数据和误差需求。

4. 最小二乘拟合（数据带噪时的正确姿势）

放弃"穿过每点"，改求 \(\min_c \sum_i \big(y_i - \sum_k c_k \varphi_k(x_i)\big)^2\)——正规方程 \(A^\top A c = A^\top y\)（高代最小二乘/统计 V OLS 的同一公式第三次出场）。数值要点回收上一页：正规方程条件数是 \(\kappa(A)^2\)（平方级恶化！），认真做用 QR 分解直接解最小二乘——"同一数学、不同算法、精度两个档次"的又一标本。

插值 vs 拟合的选择判据：数据精确（函数表、几何造型）→ 插值/样条；数据带噪（实验、统计）→ 低维拟合 + 残差诊断（统计 V）。

5. 典型例题

例 1（改写的艺术） 解 \(x^3 - x - 1 = 0\)（根 \(\approx 1.325\)）。改写 A：\(x = x^3 - 1\)，\(g' = 3x^2 \approx 5.3 > 1\) 发散；改写 B：\(x = \sqrt[3]{x + 1}\)，\(g' = \frac13(x+1)^{-2/3} \approx 0.19 < 1\) 收敛（每步误差乘 0.19）。同一方程，生死两重天。

例 2（Newton 手算） \(\sqrt 2\)：解 \(x^2 - 2 = 0\)，\(x_{k+1} = \frac12(x_k + \frac{2}{x_k})\)。从 \(x_0 = 1\)：\(1.5,\ 1.41\overline{6},\ 1.414216,\ 1.41421356\dots\)——四步 8 位有效，二次收敛的体感（这也是巴比伦开方法，人类最古老的算法之一）。

例 3（差商表） 过 \((0,1), (1,2), (2,5)\)：差商 \(f[x_0]=1,\ f[x_0,x_1]=1,\ f[x_0,x_1,x_2]=\frac{3-1}{2}=1\) ⇒ \(P_2 = 1 + x + x(x-1) = x^2 + 1\)。验证三点全过 ✓。\(\blacksquare\)

最后一页：积分算不出原函数怎么办、微分方程解不出解析解怎么办——数值积分与 ODE 数值解，扩散模型采样器的老家。