1 问题简介¶

1.1 根与重根¶

1.2 根的存在性¶

这一定理是二分法的基础：只要区间两端异号，就可以不断缩小含根区间。

2 二分法¶

2.1 方法思想¶

设 \(f(x)\) 在 \([a,b]\) 上连续，且 \(f(a)f(b)<0\)。令

若 \(f(p)=0\)，则 \(p\) 就是根；否则根据符号选择新的含根区间：

• 若 \(f(a)f(p)<0\)，根在 \([a,p]\)；
• 若 \(f(p)f(b)<0\)，根在 \([p,b]\)。

重复这个过程，直到区间长度小于指定阈值。

2.2 算法¶

算法 2.1（二分法）¶

2.3 收敛性与稳定性¶

经过 \(k\) 次二分后，区间长度为

因此若希望误差不超过 \(\varepsilon\)，只需

二分法稳定、可靠，但收敛速度只有线性，且要求初始区间两端异号。

3 不动点迭代法¶

3.1 不动点¶

将方程 \(f(x)=0\) 改写成等价形式

即可构造迭代格式

若 \(x_k\to x^*\)，则 \(x^*\) 是不动点，也对应原方程的根。

3.2 算法¶

算法 3.1（不动点迭代法）¶

3.3 收敛定理¶

4 收敛阶与误差分析¶

4.1 收敛阶¶

设迭代序列 \(x_k\to x^*\)，误差 \(e_k=x_k-x^*\)。若存在 \(p\geq1\) 和 \(C>0\)，使得

则称该迭代具有 \(p\) 阶收敛。

• \(p=1\)：线性收敛；
• \(p=2\)：二阶收敛；
• \(p>1\)：超线性收敛。

4.2 不动点迭代的局部误差¶

由 Taylor 展开

若 \(\phi'(x^*)\neq0\) 且 \(|\phi'(x^*)|<1\)，则通常为线性收敛：

若 \(\phi'(x^*)=0\) 且 \(\phi''(x^*)\neq0\)，则通常为二阶收敛：

5 松弛法¶

5.1 松弛迭代¶

对方程 \(f(x)=0\)，可构造

其中 \(\omega\) 为松弛因子。它也可看成不动点迭代：

在根 \(x^*\) 附近，

若希望局部收敛，需要

即当 \(f'(x^*)>0\) 时，通常要求

5.2 最优局部选择¶

若能取

则 \(\phi'(x^*)=0\)，局部收敛阶可由线性提升到二阶。这正是 Newton 法的思想来源：用当前点的导数近似根处导数。

6 Newton 法¶

6.1 迭代格式¶

对 \(f(x)=0\)，在 \(x_k\) 处作一阶 Taylor 展开：

令右端为 0，得到 Newton 迭代：

6.2 几何意义¶

Newton 法用曲线在当前点的切线与 \(x\) 轴的交点作为下一次近似。因此若初值足够靠近单根且 \(f'(x^*)\neq0\)，通常收敛非常快。

用几何语言描述，第 \(k\) 步迭代时，点 \((x_{k+1}, 0)\) 是曲线 \(y=f(x)\) 在点 \((x_k, f(x_k))\) 处的切线

与 \(x\) 轴的交点，如下图所示。

从图中可以看到，Newton 法迭代迅速逼近真实根 \(x^*=\sqrt{2}\approx1.4142\)。

6.3 收敛性分析¶

6.4 重根情况¶

若 \(f(x)\) 在 \(x=x^*\) 处有 \(m\) 重根 \((m>1)\)，即

其中 \(g(x^*)\neq0\)，并假设 \(g(x)\) 有二阶导数。此时

Newton 法的标准迭代格式在重根处的收敛性会发生变化。从误差入手：

于是

其中 \(\xi_k\) 和 \(\eta_k\) 为介于 \(x_k\) 与 \(x^*\) 之间的两个数。令 \(k\to\infty\) 求极限，得到收敛阶为 \(1-\dfrac{1}{m}\)。于是，在重根的情况下，Newton 法不再是平方收敛。

改善重根收敛性的方法¶

方法一：已知重数 \(m\)

将迭代格式更换成

此时误差比为

恢复了二阶收敛。

方法二：未知重数 \(m\)

令

无论 \(f(x)\) 的根 \(x^*\) 重数是多少，\(x^*\) 都是 \(h(x)\) 的 单根。于是对 \(h(x)=0\) 应用 Newton 法，迭代格式为

这种方法不需要预先知道重数 \(m\)，同样能恢复二阶收敛。

6.5 收敛域的改善¶

Newton 法要求初始值 \(x_0\) 足够接近方程的根 \(x^*\)；否则，Newton 法可能不收敛。

阻尼 Newton 法¶

为了扩大 Newton 法的收敛域，一种常见的改进称为 阻尼 Newton 法。在阻尼 Newton 迭代中，增加参数 \(\alpha_k\)：

其中参数 \(\alpha_k\) 使得不等式

成立。通常 \(\alpha_k\) 可以通过线搜索（line search）来确定，例如从 \(\alpha_k=1\) 开始，若不满足下降条件则不断减半，直到满足条件为止。

7 Aitken 加速¶

7.1 线性收敛序列的加速¶

设序列 \(x_k\to x^*\) 线性收敛，并近似满足

解这个关系可得对极限的加速估计：

这称为 Aitken \(\Delta^2\) 加速法。

7.2 适用条件¶

Aitken 法适合近似线性收敛的序列。如果分母

接近 0，则加速结果可能数值不稳定。

8 Steffensen 方法¶

8.1 从 Aitken 到 Steffensen¶

对不动点迭代 \(x_{k+1}=\phi(x_k)\)，有

将 Aitken 加速直接写成只依赖当前点的迭代函数：

等价地，

于是 Steffensen 迭代为

8.2 特点¶

Steffensen 法不显式使用导数，却常能达到类似 Newton 法的二阶收敛效果。代价是每步通常需要计算两次 \(\phi\)。

9 Ramanujan 迭代法¶

9.1 基本形式¶

Ramanujan 迭代法用于处理形如

的方程。构造级数

比较系数可得递推：

若极限

存在，则 \(c\) 对应方程中模最小的根。

9.2 例子¶

10 弦位法（割线法）¶

弦位法是一系列与 Newton 迭代法类似、但 不用计算函数导数 \(f'(x)\) 的算法。本节介绍两种弦位法：双点弦位法与单点弦位法。

10.1 双点弦位法¶

双点弦位法将函数的导数近似成差商：

代入 Newton 迭代格式，得到双点弦位法的迭代格式：

算法¶

收敛性分析¶

10.2 单点弦位法¶

单点弦位法将 \(f'(x_k)\) 近似成

即始终固定一个端点 \(x_0\)，迭代格式为

11 Müller 法（抛物线法）¶

弦位法采用当前两个近似解进行迭代。将这个思路推广，即采用当前 三个 近似解来确定下一个迭代近似解，这个方法就是 Müller 法，也称为 抛物线法。

11.1 方法思想¶

当前三个插值点记作 \((x_{k-2},f(x_{k-2}))\)、\((x_{k-1},f(x_{k-1}))\) 与 \((x_k,f(x_k))\)。一个简单直接的想法就是将这三个点插值得到 Lagrange 多项式 \(L_k(x)\)，然后求解 \(L_k(x)=0\) 获得 \(x_{k+1}\)。

为了方便计算，将迭代格式记为

同样也就有

于是二次方程 \(L_k(x_{k+1})=0\) 可以整理成关于 \(\lambda_{k+1}\) 的二次方程：

其中

求解 \(L_k(\lambda_{k+1})=0\)，并选取 绝对值较小 的 \(\lambda_{k+1}\)（保证收敛），更新 \(x_{k+1}\)。

12 非线性方程组的 Newton 法¶

解单个非线性方程的方法可以进一步推广至求解非线性方程组

或者简写成向量形式

12.1 从极值问题到方程组¶

从多变量标量函数的极值问题

如果 \(\phi(\boldsymbol{x})\) 满足一定可导性，那么极值问题对应于找到驻点 \(\boldsymbol{x}\) 使得

这正是一个非线性方程组求零点的问题（注意极大值/极小值问题还需要判断 Hessian 的正定/负定性质）。

12.2 Newton 迭代格式¶

非线性方程组同样可以通过 Newton 迭代法求解。对 \(\boldsymbol{f}(\boldsymbol{x})\) 在点 \(\boldsymbol{x}^{(0)}\) 处做 Taylor 展开，并只保留线性部分：

其中 \(\boldsymbol{J}\) 为 Jacobi 矩阵：

令线性近似等于 \(\boldsymbol{0}\)，得到线性方程组：

当 Jacobi 矩阵可逆时，解出 \(\Delta\boldsymbol{x}^{(0)}\)，于是下一个迭代解更新为

一般地，非线性方程组的 Newton 迭代格式为

实际计算中不直接求逆矩阵，而是解线性方程组 \(\boldsymbol{J}(\boldsymbol{x}^{(k)})\Delta\boldsymbol{x}^{(k)}=-\boldsymbol{f}(\boldsymbol{x}^{(k)})\) 得到修正量 \(\Delta\boldsymbol{x}^{(k)}\)。

13 拓展：Halley 迭代法¶

Edmund Halley（1656-1742）不仅以预测哈雷彗星轨道闻名，在数学上也有重要贡献。他在 1684 年提出了两种利用 二阶导数 获得高阶收敛率的迭代法。

13.1 第一种形式¶

令 Taylor 展开保留到二阶：

解这个关于 \(x_{k+1}\) 的二次方程，得到

分母上的 \(\pm\) 选择使分母绝对值更大的符号。

13.2 第二种形式（有理函数逼近）¶

定义有理函数

计算 \(a, b, c\) 使得 \(R(x)\) 与 \(f(x)\) 在 \(x_k\) 处具有相同的函数值和一阶、二阶导数值。利用 \(R(x)=0\) 的根 \(x=a\) 作为下一次近似，得到迭代格式：

14 拓展：快速平方根求解法（Quake III 中的 InvSqrt）¶

14.1 一段传奇代码¶

在 2003 年，论坛 gamedev.net 上出现了一段传奇代码：

float InvSqrt(float x) {
    float xhalf = 0.5f * x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i >> 1);
    x = *(float*)&i;
    x = x * (1.5f - xhalf * x * x);
    return x;
}

这段代码计算的是 \(1/\sqrt{x}\)，据称比标准库 (float)(1.0/sqrt(x))$ 快约 4 倍。代码中神秘的十六进制常数0x5f3759df` 引起了许多人的关注。

14.2 背后的 Newton 迭代¶

对于给定实数 \(x>0\)，定义非线性函数：

于是 \(f(y)=0\) 的根即为 \(1/\sqrt{x}\)（正根）。Newton 迭代格式为

与代码中的

x = x * (1.5f - xhalf * x * x);

完全一致！

14.3 魔法常数的来源¶

这段代码的精髓在于：只进行了一次 Newton 迭代，但初始猜测值 0x5f3759df - (i >> 1) 极其精确。

利用 IEEE 754 单精度浮点数的存储格式：

其中 \(s\) 为符号位，\(E\) 为指数位，\(M\) 为尾数位。对于 \(x>0\)，有 \(s=0\)，即

于是

通过将浮点数 reinterpret 为整数、右移一位、再减去魔法常数，本质上是在对指数和尾数同时做近似，使得初始猜测的相对误差极小。随后一次 Newton 迭代即可将误差降到可接受范围。

15 小结¶

不同求根方法的侧重点不同：