非线性系统

非线性系统的核心问题是求解方程的根。一般形式为：

f(x⃗∗)=0⃗,f:Rm→Rmf(\vec{x}^*)=\vec{0},\qquad f:\mathbb{R}^m\to\mathbb{R}^m

一维情形写作 f(x∗)=0f(x^*)=0。算法通常只能输出近似解 xestx_{\mathrm{est}}，并用残差 ∣f(xest)∣|f(x_{\mathrm{est}})| 作为可计算的成功标准。

非线性方程可能没有显式解析解。例如：

f(x)=x5−3x4+25f(x)=x^5-3x^4+25

或：

f(x)=ex+e−x−5−xf(x)=e^x+e^{-x}-5-x

因此需要数值方法。

正则性假设

根查找问题本身太一般，若不加假设，很难设计可靠算法。常用假设包括连续、Lipschitz、可微和高阶光滑。

连续与 Lipschitz

连续性表示当 x⃗→y⃗\vec{x}\to\vec{y} 时，f(x⃗)→f(y⃗)f(\vec{x})\to f(\vec{y})。

Lipschitz 条件要求存在常数 cc，使得：

∥f(x⃗)−f(y⃗)∥2≤c∥x⃗−y⃗∥2\|f(\vec{x})-f(\vec{y})\|_2\le c\|\vec{x}-\vec{y}\|_2

Lipschitz 条件比连续性更强，它控制函数值变化不会超过输入变化的常数倍。

可微与光滑

一维函数可微表示 f′(x)f'(x) 存在。若 ff 有 kk 阶连续导数，则称 f∈Ckf\in C^k；若所有阶导数都存在且连续，则称 f∈C∞f\in C^\infty。

典型例子：

  • f(x)=cos⁡xf(x)=\cos x 是 C∞C^\infty，并且在 R\mathbb{R} 上 Lipschitz。
  • g(x)=x2g(x)=x^2 是 C∞C^\infty，但在 R\mathbb{R} 上不是 Lipschitz。
  • h(x)=∣x∣h(x)=|x| 连续且 Lipschitz，但在 x=0x=0 处不可微。

二分法

二分法依赖连续性和介值定理。若 ff 在 [l,r][l,r] 上连续，并且：

f(l)f(r)<0f(l)f(r)<0

则区间内部至少存在一个根。

算法流程

二分法每步取中点：

c=l+r2c=\frac{l+r}{2}

然后根据符号变化保留仍含根的一半区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Bisection(f, l, r, epsilon):
    # 要求 f 连续，并且 f(l) * f(r) < 0。
    while |r - l| >= epsilon:
        c <- (l + r) / 2

        if f(c) == 0:
            return c

        # 根仍在 [l, c] 中。
        if f(l) * f(c) < 0:
            r <- c
        else:
            l <- c

    return (l + r) / 2

二分法的优点是只要初始区间满足符号变化条件，就一定收敛；缺点是速度较慢。

收敛速度

令 EkE_k 表示第 kk 步后的区间长度，则：

Ek+1≤12EkE_{k+1}\le \frac{1}{2}E_k

因此：

Ek≤2−kE0E_k\le 2^{-k}E_0

二分法是线性收敛。若要使误差小于 ε\varepsilon，迭代次数大约满足 2−kE0<ε2^{-k}E_0<\varepsilon。

固定点迭代

固定点问题写作：

g(x∗)=x∗g(x^*)=x^*

它可以转化为根查找问题 g(x)−x=0g(x)-x=0。反过来，根查找问题 f(x)=0f(x)=0 也可以改写为固定点问题。

固定点迭代的基本形式为：

xk+1=g(xk)x_{k+1}=g(x_k)

几何上，它不断用当前点的函数值生成下一个点。

收敛条件

若 gg 在根附近 Lipschitz，且 Lipschitz 常数 c<1c<1，则固定点迭代在足够好的初值附近收敛。

令：

Ek=∣xk−x∗∣E_k=|x_k-x^*|

因为 g(x∗)=x∗g(x^*)=x^*，有：

Ek=∣g(xk−1)−g(x∗)∣≤c∣xk−1−x∗∣=cEk−1E_k=|g(x_{k-1})-g(x^*)|\le c|x_{k-1}-x^*|=cE_{k-1}

因此：

Ek≤ckE0E_k\le c^kE_0

当 c<1c<1 时，误差趋于 0。若 ∣g′(x∗)∣<1|g'(x^*)|<1，通常可以在根附近得到这样的局部收敛性。

收敛阶

若 g′(x∗)≠0g'(x^*)\ne 0 且 ∣g′(x∗)∣<1|g'(x^*)|<1，固定点迭代通常线性收敛。

若 g′(x∗)=0g'(x^*)=0，对 gg 在 x∗x^* 处作 Taylor 展开：

g(xk)=g(x∗)+12g′′(x∗)(xk−x∗)2+O((xk−x∗)3)g(x_k)=g(x^*)+\frac{1}{2}g''(x^*)(x_k-x^*)^2+O((x_k-x^*)^3)

因此误差满足：

Ek+1≈12∣g′′(x∗)∣Ek2E_{k+1}\approx \frac{1}{2}|g''(x^*)|E_k^2

此时可能出现二次收敛。

Newton 方法

Newton 方法适用于可微函数。它用当前点处的切线近似函数，并取切线与 xx 轴的交点作为下一次迭代。

一阶近似为：

f(x)≈f(xk)+f′(xk)(x−xk)f(x)\approx f(x_k)+f'(x_k)(x-x_k)

令右侧等于 0，得到 Newton 迭代：

xk+1=xk−f(xk)f′(xk)x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}

也可以看作固定点迭代：

g(x)=x−f(x)f′(x)g(x)=x-\frac{f(x)}{f'(x)}

收敛性

若 x∗x^* 是简单根，即：

f(x∗)=0,f′(x∗)≠0f(x^*)=0,\qquad f'(x^*)\ne 0

则 Newton 方法在足够接近根的初值附近通常二次收敛。

对 g(x)=x−f(x)f′(x)g(x)=x-\frac{f(x)}{f'(x)} 求导：

g′(x)=f(x)f′′(x)(f′(x))2g'(x)=\frac{f(x)f''(x)}{(f'(x))^2}

在简单根处 f(x∗)=0f(x^*)=0，所以 g′(x∗)=0g'(x^*)=0，这解释了 Newton 方法的二次收敛。

Newton 方法并非全局可靠。若初值不好、导数接近 0、函数形状复杂，迭代可能发散、震荡，或收敛到其他根。

算法流程

1
2
3
4
5
6
7
8
Newton(f, f_prime, x0, epsilon):
    x <- x0

    while |f(x)| >= epsilon:
        # f_prime(x) 过小时不能直接除。
        x <- x - f(x) / f_prime(x)

    return x

实际实现中通常还需要设置最大迭代次数，并检查 ∣f′(x)∣|f'(x)| 是否过小。

割线法

Newton 方法需要计算导数。若导数难以获得，可以用有限差分近似：

f′(xk)≈f(xk)−f(xk−1)xk−xk−1f'(x_k)\approx \frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}

代入 Newton 公式，得到割线法：

xk+1=xk−f(xk)(xk−xk−1)f(xk)−f(xk−1)x_{k+1}=x_k-\frac{f(x_k)(x_k-x_{k-1})}{f(x_k)-f(x_{k-1})}

割线法需要两个初始点 x0,x1x_0,x_1。它通常比二分法快，不需要显式导数，但没有二分法那样的无条件收敛保证。

算法流程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Secant(f, x0, x1, epsilon):
    prev <- x0
    curr <- x1

    while |f(curr)| >= epsilon:
        denom <- f(curr) - f(prev)

        # denom 过小时，割线斜率不可靠。
        next <- curr - f(curr) * (curr - prev) / denom

        prev <- curr
        curr <- next

    return curr

割线法可以看作“用最近两点的割线代替 Newton 切线”。它省去了导数计算，但稳定性更依赖初始点和函数形状。

方法对比

四种方法的主要差异：

  • 二分法：只要求连续和初始区间异号，收敛可靠，但速度较慢。
  • 固定点迭代：形式简单，收敛依赖 gg 在根附近是否为压缩映射。
  • Newton 方法：局部收敛很快，简单根附近通常二次收敛，但需要导数且可能失败。
  • 割线法：不需要显式导数，通常比二分法快，但稳定性不如二分法。

选择方法时，应同时考虑可用信息、初始值质量、函数正则性和失败处理策略。