非线性方程求根问题

形式陈述 ​

标量求根问题给定函数公理库函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。 $f:D\subseteq \mathbb{R}\to \mathbb{R}$，寻找 $r\in D$ 使

$$f(r)=0.$$

向量问题给定 $F:D\subseteq {\mathbb{R}}^n\to {\mathbb{R}}^n$，寻找 $F(r)=0$。输出规格必须说明是寻找一个根、给定区域内的全部根，还是只判断根是否存在；这三项任务需要的信息和算法并不相同。

若存在邻域使 $r$ 是其中唯一的零点，称 $r$ 为孤立根。标量函数在 $r$ 附近若可写成

$$f(x)=(x-r{)}^{m}g(x),g(r)\ne 0,$$

则 $r$ 是重数为 $m$ 的根；$m=1$ 时为简单根。对充分可微的函数，这等价于 $f(r)=\cdots =f^{(m-1)}(r)=0$ 且 $f^{(m)}(r)\ne 0$。向量问题通常用 Jacobian 是否可逆描述非退化根，而不直接照搬标量重数。

区间 $[a,b]$ 若端点函数值异号，在连续性假设下构成括根区间，保证其中至少有一个实根。隔离区间的要求更强：它包含指定集合中的恰好一个根。异号本身不证明唯一，也无法检测两侧同号的偶重根；“括住一个根”与“隔离出唯一根”必须分开表述。

近似值 $\hat{r}$ 的残差是 $f(\hat{r})$ 或 $F(\hat{r})$，前向误差则是 $\hat{r}-r$。在标量简单根附近，若函数受到小的加性扰动 $\mathrm{\Delta }f$，一阶关系为

$$\mathrm{\Delta }r\approx -\frac{\mathrm{\Delta }f(r)}{f^{\prime }(r)}.$$

因此 $1/|f^{\prime }(r)|$ 给出一种绝对局部敏感性尺度。向量情形由 $J_F(r{)}^{-1}$ 承担同一角色。相对条件数还取决于输入如何参数化、函数如何缩放，以及允许扰动函数值、系数还是其他数据，不能只给一个无上下文数字。

直觉 ​

求根先是一项关于对象的任务，算法随后才决定怎样搜索。存在性回答“有没有交点”，隔离回答“这段区域内有几个”，条件性回答“曲线稍微移动后交点会走多远”。二分、Newton 和割线法分别利用不同信息，不能用某个方法的更新公式代替这些问题规格。

曲线陡直穿过横轴时，小的竖直扰动通常只让交点水平移动一点；曲线贴着横轴相切时，同样的竖直扰动可能让根分裂、消失或移动很远。导数是否远离零因而既影响局部敏感性，也会影响许多迭代法的收敛行为。

例子与边界 ​

令

$$f(x)=\cos x-x.$$

在 $[0,1]$ 上有 $f(0)=1>0$、$f(1)=\cos 1-1<0$，由介值定理公理库介值定理Intermediate value theorem连续实函数在区间上取得端点函数值之间的每个值。至少存在一根。又因

$$f^{\prime }(x)=-\sin x-1<0$$

在该区间成立，函数严格递减，所以根唯一；其数值约为 $0.7390851332$。存在性来自连续与异号，唯一性来自单调性，这两个论证不能合并成“二分找到了唯一根”。

函数 $(x-1{)}^2$ 在 $x=1$ 有二重根，根两侧函数值同号，符号变化法无法发现它。扰动为

$$f_{\epsilon }(x)=(x-1{)}^2-\epsilon$$

时，$\epsilon >0$ 产生两个根 $1\pm \sqrt{\epsilon }$；若改成加上正的 $\epsilon$，实根则消失。根的位移按 $\sqrt{\epsilon }$ 而不是 $\epsilon$ 缩放，显示重根附近的病态性。

小残差也不能脱离尺度解释。对 $f(x)=\alpha (x-1)$，近似值 $\hat{r}=0$ 的根误差恒为 $1$，残差却是 $-\alpha$，可通过缩小 $\alpha$ 变得任意小。只有结合导数下界、逆 Jacobian 范数或其他条件性信息，残差才能转换成根误差界。

多项式求根只是求根问题的一类。寻找一个已括住的实根可以依靠实区间与符号；寻找多项式的全部复根则要处理复共轭结构、聚集根和系数扰动，不能把同一括区间算法机械推广过去。连续函数还可能有一整段零点，此时“输出一个根”和“描述解集”也完全不同。

推论与应用 ​

二分求根法公理库二分求根法Bisection method以端点异号区间为不变量，给出可验证误差界、对数成本和有限精度停止条件。只使用连续性和端点符号来维护全局括区间；Newton 法利用导数或 Jacobian 获得局部速度；割线法用两次函数值近似斜率。混合方法通常保留括区间作为安全外壳，再在条件允许时采用更快的局部步。

残差与误差估计公理库残差、误差估计与停止准则Residual and error estimation · Stopping criterion区分可计算残差与未知真误差，并说明把缺陷转成误差界和停止证书所需的条件。提供停止证书的共同语言，问题条件性公理库问题条件性与条件数Conditioning of a problem · Condition number度量问题真解对输入微扰的局部敏感性，并把这种固有敏感性与算法误差分开。解释为何同样大小的残差在简单根和重根附近代表不同误差。任何求根结果都应同时报告搜索区域、残差定义、停止条件和失败状态，而不是只给若干小数位。

参考资料

• NIST Digital Library of Mathematical Functions, §3.8: Nonlinear Equations.
• Richard L. Burden, J. Douglas Faires, and Annette M. Burden, Numerical Analysis, 10th ed., Cengage, 2016, Ch. 2.
• Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002, Ch. 1.