【数值分析】非线性方程求根

本篇作为数值分析的入门，介绍一下非线性方程求根的常用算法。

概述

非线性方程组是指包含一个或多个非线性项的方程组成的系统，这些非线性项可以是多项式中的二次项或更高次项，也可以是指数函数、对数函数等。

求解非线性方程组比线性方程组复杂得多，需要借助数值方法。常用的数值方法包括二分法、不动点迭代法、牛顿法等。

这些方法在工程、物理、经济学等多个领域中都有广泛的应用。

本文将对常用的非线性方程求根算法进行介绍。

二分法

二分法（Bisection Method）是一种在数值分析中用于求解非线性方程近似解的方法。

由连续函数介值定理，在区间 $[a, b]$, 若$f(a) \cdot f(b) < 0$ ，存在 $a<x<b$ 使得 $f(x) = 0$

二分法的基本思想是将函数的根所在的区间逐渐缩小，直到找到满足一定精度要求的根的近似值。

不过要保证迭代过程中左右端点处函数值始终异号，因此只能求出单根。

二分法的基本步骤：

计算中点：
- 计算区间 $[a, b]$ 的中点 $c = \frac{a + b}{2}$。
判断中点函数值的符号：
- 计算 $f(c)$ 的值。
- 如果 $f(c) = 0$，则 $c$ 就是方程的根。
- 如果 $f(c) \cdot f(a) < 0$，则根位于区间 $[a, c]$ 内。
- 如果 $f(c) \cdot f(b) < 0$，则根位于区间 $[c, b]$ 内。
迭代：
- 根据中点函数值的符号，选择新的区间 $[a, c]$ 或 $[c, b]$ 作为下一步的搜索区间。
- 重复步骤1和步骤2，直到区间的长度小于预先设定的容忍度 $\epsilon$，或者函数值接近于0。
- 对于 x 误差为 $\frac {b-a} {2^n} $, n为迭代次数

二分法的特点：

二分法适用于那些函数连续且在区间上改变符号的非线性方程。它不要求函数是单调的，也不要求函数的导数信息，因此在很多实际问题中非常有用。

收敛性：只要初始区间选择正确，算法总是能够收敛到一个根。
收敛速度：收敛速度较慢，特别是当根靠近区间端点时。
多根问题：对于多根问题，二分法只能找到一个根，且可能是任意一个根。

def bisection(f, a, b, max_iter=100):
    for _ in range(max_iter):
        c = (a + b) / 2 
        if f(a) * f(c) < 0: 
            b = c
        else:
            a = c
    return c

# 示例：求解方程 x**2 - 2 = 0 的根
def func(x):
    return x**2 - 2

# 调用二分法函数
root = bisection(func, 1, 2)
print(f"方程 x**2 - 2 = 0 的根的近似值为：{root}")

不动点迭代

不动点迭代法是一种求解非线性方程近似解的数值方法。

它基于这样的思想：如果有一个方程 $ f(x) = 0 $ 难以直接求解，我们可以将其转换为 $ x_{n+1} = g(x_n) $ 的形式，然后通过迭代的方式来逼近方程的解。

不动点迭代通常需要根据函数特点因地制宜的设计迭代方程，没有普适性，因此这里只是简单介绍。

不动点迭代的基本步骤：

选择初始值：
- 选择一个初始近似值 $ x_0 $。
迭代过程：
- 通过递归关系 $ x_{n+1} = g(x_n) $ 计算下一个近似值，其中 $ n $ 表示迭代的步数。
判断收敛：
- 检查连续两次迭代的结果是否足够接近，即 $ \lvert x_{n+1} - x_n \rvert < \epsilon $，其中 $ \epsilon $ 是预先设定的容忍度。
- 如果满足收敛条件，则认为 $ x_n $ 是方程的一个近似解。

不动点迭代的特点：

初值选择：不同初始值 $ x_0 $ 的选择对迭代的收敛性和收敛速度影响很大。
收敛性：不是所有的 $ g(x) $ 都能保证迭代过程会收敛到方程的解。收敛性的讨论比较复杂，这里不展开了。
多根问题：收敛到的根不确定，主要取决于初值和迭代方程。

牛顿法

牛顿法（Newton’s Method），也称为牛顿-拉弗森方法（Newton-Raphson Method），是一种求解非线性方程根的迭代算法。

它利用函数的一阶泰勒级数展开来近似求解方程 $ f(x) = 0 $ 的根。

牛顿法收敛速度为二次收敛，要比二分法快得多。

牛顿法基本思想

牛顿法基于这样的思想：对于一个可微函数 $ f(x) $，如果我们知道一个近似根 $ x_n $，那么可以通过切线来找到一个更好的近似根。

具体来说，如果 $ x_n $ 是方程 $ f(x) = 0 $ 的根的近似值，那么在 $ x_n $ 处的切线方程为：

\[y = f(x_n) + f'(x_n)(x - x_n)\]

这条切线与x轴的交点 $ x_{n+1} $ 将是下一个更精确的近似根。因此，我们可以通过解方程：

\[f(x_n) + f'(x_n)(x_{n+1} - x_n) = 0\]

来找到 $ x_{n+1} $。

解上述方程，我们得到牛顿法的迭代公式：

\[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\]

其中，$ x_n $ 是当前迭代值，$ f(x_n) $ 是函数在 $ x_n $ 处的值，$ f’(x_n) $ 是函数在 $ x_n $ 处的导数值。

牛顿法基本步骤

选择初始值 $ x_0 $：选择一个足够接近根的初始近似值 $ x_0 $。
迭代计算：使用迭代公式 $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ 计算下一个近似值 $ x_{n+1} $。
判断收敛：检查 $ \lvert x_{n+1} - x_n \rvert < \epsilon $ 或 $ \lvert f(x_{n+1}) \rvert < \epsilon $，其中 $ \epsilon $ 是预先设定的容忍度。如果满足收敛条件，则认为 $ x_{n+1} $ 是方程的一个近似根。

牛顿法的特点：

初始值的选择：初始值的选择对牛顿法的收敛性和收敛速度至关重要。如果初始值选择不当，可能会导致方法不收敛，甚至发散。
收敛性：牛顿法的收敛速度非常快，通常是二次收敛，但前提是初始值足够接近真实根，且函数在根附近表现良好（即导数不为零）。
导数不能为零：如果在某次迭代中 $ f’(x_n) = 0 $，那么迭代将无法继续，因为分母为零。
多根问题：牛顿法可能会收敛到初值最近的根，主要取决于初始值的位置。

def newton_method(f, df, x0, tol=1e-6, max_iter=100):
    x_n = x0
    for _ in range(max_iter):
        x_next = x_n - f(x_n) / df(x_n)
        if abs(x_next - x_n) < tol:
            return x_next
        x_n = x_next
    return x_n

# 示例：求解方程 x^2 - 2 = 0 的根
def func(x):
    return x**2 - 2

def func_derivative(x):
    return 2*x

# 调用牛顿法函数
root = newton_method(func, func_derivative, 1.0)
print(f"方程 x^2 - 2 = 0 的根的近似值为：{root}")

弦截法

弦截法，也称为割线法，是一种用于求解非线性方程近似根的数值方法。

它可以看作牛顿法在用弦斜率代替导数的特殊情况。

假设我们要找的是函数 $ f(x) $ 与x轴的交点，即 $ f(x) = 0 $ 的解。弦截法通过求解过点 $ A $ 和 $ B $ 的直线与x轴的交点来近似这个根。这条直线的方程可以表示为：

\[y - f(x_1) = \frac{f(x_2) - f(x_1)}{x_2 - x_1}(x - x_1)\]

令 $ y = 0 $（因为我们要找到x轴的交点），我们可以解出 $ x $ 的值，这个 $ x $ 的值就是方程根的一个近似值。

弦截法的迭代公式如下：

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

其中，$ x_k $ 和 $ x_{k-1} $ 是前两次迭代的值，$ f(x_k) $ 和 $ f(x_{k-1}) $ 是对应的函数值。

弦截法的基本步骤

选择两个初始值 $ x_0 $ 和 $ x_1 $，计算对应的函数值 $ f(x_0) $ 和 $ f(x_1) $。
迭代计算：使用迭代公式计算下一个近似值 $ x_2 $。
判断收敛：检查 $ \lvert x_{k+1} - x_k \rvert < \epsilon $，其中 $ \epsilon $ 是预先设定的容忍度。如果满足收敛条件，则认为 $ x_{k+1} $ 是方程的一个近似根。。

弦截法的特点：

弦截法特点和牛顿法类似，不过也有特殊点：

优点是不需要计算函数的导数，因此在处理那些求导比较复杂的函数时非常有用。
弦截法的收敛速度通常比牛顿法慢，为超线性收敛。
弦的斜率不能为0，否则会除0错误。