CE7453 Numerical Algorithms 期末高分超详细攻略（第一章：Root Finding）

本章内容：方程求根（Root Finding）
适用对象：零基础/考前冲刺/快速查漏补缺
内容特色：详细原理、公式推导、算法流程、例题全解、英文关键词

1.1 基本概念与背景

什么是方程求根？
给定一个连续函数 $f (x)$ ，我们想找到 $x = r$ 使得 $f (r) = 0$ 。这个 $r$ 就叫做 $f (x)$ 的根（root）。
数学表示：
求解方程 $f (x) = 0$ 的解 $x = r$ 。
实际应用：
- 物理学：平衡点、临界值、交叉点计算
- 工程学：结构稳定性分析、电路设计
- 金融学：期权定价、收益率计算
- 计算机图形学：曲线/曲面求交
- 优化问题：目标函数的极值点（导数为零）
求根方法分类：
- 直接法：代数方程的解析解（如一元二次方程公式）
- 迭代法：通过迭代逼近根（本章重点）
- 混合法：结合多种方法的优点

1.2 主要算法与原理

1.2.1 二分法（Bisection Method）

原理：
如果连续函数 $f (x)$ 在区间 $[a, b]$ 上满足 $f (a)$ 和 $f (b)$ 异号（即 $f (a) f (b) < 0$ ），根据中值定理，区间内必存在至少一个根。
算法流程：
1. 检查 $f (a) f (b) < 0$ ，否则不能用二分法。
2. 计算中点 $c = (a + b) /2$ 。
3. 判断 $f (c)$ 的符号：
  - 如果 $f (c) = 0$ ，找到精确根，返回 $c$ 。
  - 如果 $f (a) f (c) < 0$ ，根在 $[a, c]$ ，令 $b = c$ 。
  - 如果 $f (c) f (b) < 0$ ，根在 $[c, b]$ ，令 $a = c$ 。
4. 重复2-3，直到区间足够小（ $∣ b - a ∣ < ϵ$ ）或迭代次数达到上限。
收敛性分析：
- 每次迭代后，区间长度减半： $∣ b_{n + 1} - a_{n + 1} ∣ = \frac{∣ b _{n} - a _{n} ∣}{2}$
- 经过 $n$ 次迭代后，区间长度： $∣ b_{n} - a_{n} ∣ = \frac{∣ b _{0} - a _{0} ∣}{2 ^{n}}$
- 要达到精度 $ϵ$ ，需要迭代次数： $n \geq lo g_{2} \frac{∣ b _{0} - a _{0} ∣}{ϵ}$
误差估计：
- 若 $c_{n}$ 是第 $n$ 次迭代的中点，则 $∣ c_{n} - r ∣ \leq \frac{∣ b _{0} - a _{0} ∣}{2 ^{n + 1}}$ ，其中 $r$ 是真实根。
- 若要求解精确到小数点后 $d$ 位，需满足 $\frac{∣ b _{0} - a _{0} ∣}{2 ^{n}} < 5 \times 1 0^{- (d + 1)}$
- 精度要求：若要求解精确到小数点后 $p$ 位，即误差小于 $0.5 \times 1 0^{- p}$ ，则需要满足： $\frac{∣ b _{0} - a _{0} ∣}{2 ^{n}} < 0.5 \times 1 0^{- p}$
- 所需迭代次数：解上述不等式可得最小迭代次数 $n$ ： $n > lo g_{2} (\frac{∣ b _{0} - a _{0} ∣}{0.5 \times 1 0 ^{- p}})$ 或更方便计算的形式： $n > \frac{lo g _{10} ( ∣ b _{0} - a _{0} ∣ ) - lo g _{10} ( 0.5 \times 1 0 ^{- p} )}{lo g _{10} ( 2 )}$
优缺点：
- 优点：
  - 一定收敛（全局收敛性，global convergence）
  - 实现简单，稳定可靠
  - 不需要导数信息
- 缺点：
  - 收敛速度慢（线性收敛，收敛阶为1）
  - 每次迭代只减少一位有效数字
  - 只适用于区间端点异号的情况
  - 无法处理重根

伪代码：

function Bisection(f, a, b, tol, max_iter)
    if f(a)*f(b) >= 0 then
        return "Error: 区间端点不异号"
    end if
    
    iter = 0
    while (b-a)/2 > tol and iter < max_iter do
        c = (a+b)/2
        if f(c) == 0 then
            return c  // 找到精确根
        else if f(a)*f(c) < 0 then
            b = c
        else
            a = c
        end if
        iter = iter + 1
    end while
    
    return (a+b)/2  // 返回区间中点作为近似根
end function

公式：
$c_{n} = \frac{a _{n} + b _{n}}{2}$
$∣ b_{n} - a_{n} ∣ = \frac{∣ b _{0} - a _{0} ∣}{2 ^{n}}$
英文关键词：bisection method, bracket, interval halving, binary search, convergence, tolerance, error bound

例题1：二分法求解 $f (x) = x^{3} + x - 1$

问题：用二分法求 $f (x) = x^{3} + x - 1$ 在 $[0, 1]$ 内的根，精度要求为 $1 0^{- 2}$ 。

分析： $f (0) = - 1$ , $f (1) = 1$ 。 $f (0) f (1) < 0$ ，符合二分法使用条件。初始区间 $[a_{0}, b_{0}] = [0, 1]$ ，区间长度为 1。要求精度 $ϵ = 1 0^{- 2} = 0.01$ 。需要满足 $\frac{∣ b _{0} - a _{0} ∣}{2 ^{n}} < ϵ$ ，即 $\frac{1}{2 ^{n}} < 0.01$ 。 $2^{n} > 100$ 。因为 $2^{6} = 64$ , $2^{7} = 128$ ，所以至少需要 $n = 7$ 次迭代。

迭代过程：

n	$a_{n}$	$b_{n}$	$c_{n} = (a_{n} + b_{n}) /2$	$f (c_{n})$	区间	长度
0	0	1	0.5	-0.375	[0.5, 1]	0.5
1	0.5	1	0.75	0.171875	[0.5, 0.75]	0.25
2	0.5	0.75	0.625	-0.130859	[0.625, 0.75]	0.125
3	0.625	0.75	0.6875	0.012451	[0.625, 0.6875]	0.0625
4	0.625	0.6875	0.65625	-0.061012	[0.65625, 0.6875]	0.03125
5	0.65625	0.6875	0.671875	-0.024755	[0.671875, 0.6875]	0.015625
6	0.671875	0.6875	0.6796875	-0.006270	[0.6796875, 0.6875]	0.0078125

结果：经过7次迭代，得到近似根 $x \approx c_{6} = 0.6796875$ 。此时区间长度为 $0.0078125 < 0.01$ ，满足精度要求。

Python代码示例：

def is_close(a, b, rtol=1e-5, atol=1e-8):
    """
    检查两个数值是否足够接近，考虑浮点数精度问题
    """
    return np.abs(a - b) <= (atol + rtol * np.abs(b))

def test_example1_bisection():
    """
    验证例题1：用二分法求 f(x)=x^3+x-1 在 [0,1] 内的根，精度 10^-2
    文档中的答案：x ≈ 0.6796875
    """
    f = lambda x: x**3 + x - 1
    
    # 二分法实现
    def bisection_method(f, a, b, tol=1e-10, max_iter=100):
        if f(a) * f(b) >= 0:
            raise ValueError("区间端点函数值必须异号")
        
        iter_count = 0
        while (b - a) / 2 > tol and iter_count < max_iter:
            c = (a + b) / 2
            if f(c) == 0:
                return c
            elif f(a) * f(c) < 0:
                b = c
            else:
                a = c
            iter_count += 1
        
        return (a + b) / 2
    
    # 用自己实现的二分法计算
    root_bisection = bisection_method(f, 0, 1, tol=1e-2)
    # 用scipy的方法计算精确值
    root_exact = optimize.root_scalar(f, bracket=[0, 1], method='brentq').root
    
    # 文档中给出的答案
    root_document = 0.6796875
    
    # 验证自己实现的方法是否与文档答案一致
    # 这里我们只展示计算过程，验证部分在test文件中执行
    print(f"二分法计算结果: {root_bisection}")
    print(f"文档答案: {root_document}")
    print(f"Scipy精确解: {root_exact}")
    print(f"函数在文档答案处的值: {f(root_document)}")

# 运行示例 (需要 import numpy as np 和 from scipy import optimize)
# test_example1_bisection()

1.2.2 牛顿法（Newton's Method）

原理：
利用函数的局部线性近似（泰勒展开）逐步逼近根。在当前点 $x_{n}$ 处作切线，切线与 $x$ 轴的交点作为下一个近似值 $x_{n + 1}$ 。
数学推导：
在 $x_{n}$ 处展开 $f (x)$ 的一阶泰勒级数： $f (x) \approx f (x_{n}) + f^{'} (x_{n}) (x - x_{n})$

令 $f (x) = 0$ ，解得： $x = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$

这就是牛顿法的迭代公式： $x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$
几何解释：
每次迭代相当于用切线近似函数，切线与 $x$ 轴的交点作为下一个近似值。
几何解释：在点 $(x_{n}, f (x_{n}))$ 处作函数 $f (x)$ 的切线，切线的方程为 $y - f (x_{n}) = f^{'} (x_{n}) (x - x_{n})$ 。令 $y = 0$ ，解出切线与 $x$ 轴的交点横坐标，即为 $x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ 。
算法流程：
1. 选择初始值 $x_{0}$ （初值选择很重要！）
2. 计算 $f (x_{n})$ 和 $f^{'} (x_{n})$
3. 计算 $x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$
4. 检查收敛条件：
  - 若 $∣ x_{n + 1} - x_{n} ∣ < ϵ_{x}$ （解的变化小）或
  - 若 $∣ f (x_{n + 1}) ∣ < ϵ_{f}$ （函数值接近零）或
  - 达到最大迭代次数则停止；否则 $n \leftarrow n + 1$ ，回到步骤2
- 停止准则（Stopping Criteria）：迭代过程需要一个明确的停止条件，以避免无限循环并确保达到所需精度。常用准则包括：
  - 解的绝对误差： $∣ x_{n + 1} - x_{n} ∣ < ϵ_{ab s}$ 。当连续两次迭代的解足够接近时停止。
  - 解的相对误差： $\frac{∣ x _{n + 1} - x _{n} ∣}{∣ x _{n + 1} ∣} < ϵ_{re l}$ (当 $x_{n + 1} \neq = 0$ )。适用于解的数量级未知或变化较大时。
  - 函数值接近零： $∣ f (x_{n + 1}) ∣ < ϵ_{f}$ 。当函数值足够接近零时停止。
  - 达到最大迭代次数：设置一个迭代上限 max_iter，防止算法因不收敛或收敛过慢而无限运行。实际应用中通常组合使用这些准则。
收敛性分析：
- 若初值足够接近根，且 $f^{'} (r) \neq = 0$ （非重根），则牛顿法具有二次收敛性（quadratic convergence）
- 误差关系： $∣ x_{n + 1} - r ∣ \approx C ∣ x_{n} - r ∣^{2}$ ，其中 $C$ 为常数
- 对于重根（ $f^{'} (r) = 0$ ），收敛阶降为线性
优缺点：
- 优点：
  - 收敛速度快（通常为二次收敛）
  - 每次迭代可使有效数字翻倍
  - 适用于高精度计算
- 缺点：
  - 需要计算导数
  - 初值选择敏感，可能不收敛或收敛到非预期根
  - 在导数接近零处可能不稳定
  - 对重根收敛较慢

伪代码：

function Newton(f, f_prime, x0, tol_x, tol_f, max_iter)
    x = x0
    iter = 0
    
    while iter < max_iter do
        fx = f(x)
        if |fx| < tol_f then
            return x  // 函数值足够接近零
        end if
        
        fpx = f_prime(x)
        if fpx == 0 then
            return "Error: 导数为零，无法继续"
        end if
        
        x_new = x - fx/fpx
        if |x_new - x| < tol_x then
            return x_new  // 解的变化足够小
        end if
        
        x = x_new
        iter = iter + 1
    end while
    
    return "Warning: 达到最大迭代次数"
end function

英文关键词：Newton's method, Newton-Raphson method, tangent method, quadratic convergence, initial guess, derivative, root finding

例题2：牛顿法求解 $f (x) = x^{2} - 2$

问题：用牛顿法求 $f (x) = x^{2} - 2$ 的正根，取初值 $x_{0} = 1$ ，精度要求 $1 0^{- 4}$ 。

分析： $f (x) = x^{2} - 2$ $f^{'} (x) = 2 x$ 迭代公式： $x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )} = x_{n} - \frac{x _{n}^{2} - 2}{2 x _{n}} = \frac{2 x _{n}^{2} - ( x _{n}^{2} - 2 )}{2 x _{n}} = \frac{x _{n}^{2} + 2}{2 x _{n}} = 0.5 (x_{n} + \frac{2}{x _{n}})$

迭代过程： $x_{0} = 1$ $x_{1} = 0.5 (1 + 2/1) = 1.5$ $x_{2} = 0.5 (1.5 + 2/1.5) = 0.5 (1.5 + 1.3333) = 0.5 (2.8333) = 1.41665$ $x_{3} = 0.5 (1.41665 + 2/1.41665) = 0.5 (1.41665 + 1.41176) = 0.5 (2.82841) = 1.414205$ $x_{4} = 0.5 (1.414205 + 2/1.414205) = 0.5 (1.414205 + 1.414221) = 0.5 (2.828426) = 1.414213$

结果： $∣ x_{4} - x_{3} ∣ = ∣1.414213 - 1.414205∣ = 0.000008 < 1 0^{- 4}$ ，满足精度要求。近似根 $x \approx 1.4142$ 。（实际根为 $2 \approx 1.41421356$ ）

Python代码示例：

def test_example2_newton():
    """
    验证例题2：用牛顿法求 f(x)=x^2-2 的根，x₀=1，精度 10^-4
    文档中的答案：x ≈ 1.4142
    """
    f = lambda x: x**2 - 2
    df = lambda x: 2*x
    
    # 牛顿法实现
    def newton_method(f, df, x0, tol=1e-10, max_iter=100):
        x = x0
        for i in range(max_iter):
            fx = f(x)
            if abs(fx) < tol:
                return x
            
            dfx = df(x)
            if dfx == 0:
                raise ValueError("导数为零，牛顿法失效")
            
            x_new = x - fx / dfx
            if abs(x_new - x) < tol:
                return x_new
            
            x = x_new
        
        return x
    
    # 用自己实现的牛顿法计算
    root_newton = newton_method(f, df, 1, tol=1e-4)
    # 文档中给出的答案
    root_document = 1.4142
    # 精确值是根号2
    root_exact = np.sqrt(2)
    
    # 验证部分在test文件中执行
    print(f"牛顿法计算结果: {root_newton}")
    print(f"文档答案: {root_document}")
    print(f"精确解: {root_exact}")
    print(f"函数在文档答案处的值: {f(root_document)}")

# 运行示例 (需要 import numpy as np)
# test_example2_newton()

例题3：牛顿法求解 $f (x) = e^{x} - x - 2$

问题：用牛顿法求解 $f (x) = e^{x} - x - 2$ 的根，取初始值 $x_{0} = 1$ 。

分析： $f (x) = e^{x} - x - 2$ $f^{'} (x) = e^{x} - 1$ 迭代公式： $x_{n + 1} = x_{n} - \frac{e ^{x_{n}} - x _{n} - 2}{e ^{x_{n}} - 1}$

迭代过程： $x_{0} = 1$ $f (x_{0}) = e^{1} - 1 - 2 = e - 3 \approx - 0.2817$ $f^{'} (x_{0}) = e^{1} - 1 = e - 1 \approx 1.7183$ $x_{1} = 1 - \frac{- 0.2817}{1.7183} \approx 1 + 0.1640 = 1.1640$

$f (x_{1}) = e^{1.1640} - 1.1640 - 2 \approx 3.2020 - 3.1640 = 0.0380$ $f^{'} (x_{1}) = e^{1.1640} - 1 \approx 3.2020 - 1 = 2.2020$ $x_{2} = 1.1640 - \frac{0.0380}{2.2020} \approx 1.1640 - 0.0173 = 1.1467$

$f (x_{2}) = e^{1.1467} - 1.1467 - 2 \approx 3.1483 - 3.1467 = 0.0016$ $f^{'} (x_{2}) = e^{1.1467} - 1 \approx 3.1483 - 1 = 2.1483$ $x_{3} = 1.1467 - \frac{0.0016}{2.1483} \approx 1.1467 - 0.0007 = 1.1460$

结果：迭代几次后，解趋于稳定。近似根 $x \approx 1.146$ 。

Python代码示例：

def test_example3_newton():
    """
    验证例题3：用牛顿法求解 f(x) = e^x - x - 2 的根，初始值 x₀ = 1
    文档中的答案：x ≈ 1.146
    """
    f = lambda x: np.exp(x) - x - 2
    df = lambda x: np.exp(x) - 1
    
    # 使用上面的牛顿法实现
    root_newton = newton_method(f, df, 1, tol=1e-4)
    # 用scipy的方法计算精确值
    root_exact = optimize.root_scalar(f, x0=1, fprime=df, method='newton').root
    # 文档中给出的答案
    root_document = 1.146
    
    # 验证部分在test文件中执行
    print(f"牛顿法计算结果: {root_newton}") # 实际计算会更精确
    print(f"文档答案: {root_document}")
    print(f"Scipy精确解: {root_exact}")
    print(f"函数在文档答案处的值: {f(root_document)}")

# 运行示例 (需要 import numpy as np 和 from scipy import optimize, 以及上面的 newton_method 函数)
# test_example3_newton()

牛顿法求 $3$ 的例题

问题：使用牛顿法计算 $3$ ，取初值 $x_{0} = 2$ 。

分析：求 $3$ 等价于求 $f (x) = x^{2} - 3 = 0$ 的正根。 $f (x) = x^{2} - 3$ $f^{'} (x) = 2 x$ 迭代公式： $x_{n + 1} = x_{n} - \frac{x _{n}^{2} - 3}{2 x _{n}} = \frac{2 x _{n}^{2} - x _{n}^{2} + 3}{2 x _{n}} = \frac{x _{n}^{2} + 3}{2 x _{n}} = 0.5 (x_{n} + \frac{3}{x _{n}})$

迭代过程： $x_{0} = 2$ $x_{1} = 0.5 (2 + 3/2) = 0.5 (2 + 1.5) = 0.5 (3.5) = 1.75$ $x_{2} = 0.5 (1.75 + 3/1.75) \approx 0.5 (1.75 + 1.714286) = 0.5 (3.464286) = 1.732143$ $x_{3} = 0.5 (1.732143 + 3/1.732143) \approx 0.5 (1.732143 + 1.731959) = 0.5 (3.464102) = 1.732051$

结果：迭代3次后，得到近似根 $x \approx 1.73205$ 。

Python代码示例：

def test_sqrt3_newton():
    """
    验证牛顿法求 sqrt(3) 的例题
    文档中的答案：sqrt(3) ≈ 1.73205
    """
    f = lambda x: x**2 - 3
    df = lambda x: 2*x
    
    # 牛顿法迭代公式的简化版本
    def newton_sqrt3(x0, iterations=3):
        x = x0
        for _ in range(iterations):
            x = 0.5 * (x + 3/x)
        return x
    
    # 用简化的牛顿法计算（文档中的迭代过程）
    root_newton = newton_sqrt3(2, iterations=3)
    # 文档中给出的答案
    root_document = 1.73205
    # 精确值是根号3
    root_exact = np.sqrt(3)
    
    # 验证部分在test文件中执行
    print(f"简化牛顿法计算结果 (3次迭代): {root_newton}")
    print(f"文档答案: {root_document}")
    print(f"精确解: {root_exact}")

# 运行示例 (需要 import numpy as np)
# test_sqrt3_newton()

1.2.3 割线法（Secant Method）

原理：
牛顿法的变种，用差商近似导数，避免显式计算导数。使用前两次迭代点连线的斜率代替导数。
迭代公式：
$x_{n + 1} = x_{n} - f (x_{n}) \frac{x _{n} - x _{n - 1}}{f ( x _{n} ) - f ( x _{n - 1} )}$
数学推导：
用差商近似导数： $f^{'} (x_{n}) \approx \frac{f ( x _{n} ) - f ( x _{n - 1} )}{x _{n} - x _{n - 1}}$

代入牛顿法公式得到割线法公式。
几何解释：割线法用连接点 $(x_{n - 1}, f (x_{n - 1}))$ 和 $(x_{n}, f (x_{n}))$ 的割线来近似函数 $f (x)$ 。割线与 $x$ 轴的交点即为下一个近似值 $x_{n + 1}$ 。
算法流程：
1. 选择两个初始点 $x_{0}$ 和 $x_{1}$
2. 计算 $x_{n + 1} = x_{n} - f (x_{n}) \frac{x _{n} - x _{n - 1}}{f ( x _{n} ) - f ( x _{n - 1} )}$
3. 检查收敛条件，若满足则停止；否则 $n \leftarrow n + 1$ ，回到步骤2
收敛性分析：
- 收敛阶约为 $\frac{1 + 5}{2} \approx 1.618$ （黄金分割比）
- 介于线性收敛和二次收敛之间，称为超线性收敛（superlinear convergence）
优缺点：
- 优点：
  - 不需要计算导数
  - 收敛速度优于二分法
  - 每次迭代只需一次函数评估（牛顿法需要函数和导数）
- 缺点：
  - 收敛速度低于牛顿法
  - 需要两个初始点
  - 可能出现分母接近零的情况（两点函数值接近）
  - 收敛性不如二分法可靠

伪代码：

function Secant(f, x0, x1, tol, max_iter)
    iter = 0
    
    while iter < max_iter do
        f0 = f(x0)
        f1 = f(x1)
        
        if |f1| < tol then
            return x1
        end if
        
        if f1 == f0 then
            return "Error: 分母为零，无法继续"
        end if
        
        x_new = x1 - f1*(x1-x0)/(f1-f0)
        
        if |x_new - x1| < tol then
            return x_new
        end if
        
        x0 = x1
        x1 = x_new
        iter = iter + 1
    end while
    
    return "Warning: 达到最大迭代次数"
end function

英文关键词：secant method, finite difference Newton, superlinear convergence, initial points

例题4：割线法求解 $f (x) = x^{3} + x - 1$

问题：用割线法求 $f (x) = x^{3} + x - 1$ 的根，取初值 $x_{0} = 0, x_{1} = 1$ 。

分析： $f (x) = x^{3} + x - 1$ 迭代公式： $x_{n + 1} = x_{n} - f (x_{n}) \frac{x _{n} - x _{n - 1}}{f ( x _{n} ) - f ( x _{n - 1} )}$

迭代过程： $x_{0} = 0, f (x_{0}) = - 1$ $x_{1} = 1, f (x_{1}) = 1$ $x_{2} = x_{1} - f (x_{1}) \frac{x _{1} - x _{0}}{f ( x _{1} ) - f ( x _{0} )} = 1 - 1 \times \frac{1 - 0}{1 - ( - 1 )} = 1 - \frac{1}{2} = 0.5$ $f (x_{2}) = (0.5)^{3} + 0.5 - 1 = 0.125 + 0.5 - 1 = - 0.375$

$x_{3} = x_{2} - f (x_{2}) \frac{x _{2} - x _{1}}{f ( x _{2} ) - f ( x _{1} )} = 0.5 - (- 0.375) \times \frac{0.5 - 1}{- 0.375 - 1} = 0.5 + 0.375 \times \frac{- 0.5}{- 1.375} = 0.5 + 0.375 \times 0.3636 = 0.5 + 0.13635 = 0.63635$ $f (x_{3}) = (0.63635)^{3} + 0.63635 - 1 \approx 0.2576 + 0.63635 - 1 = - 0.10605$

$x_{4} = x_{3} - f (x_{3}) \frac{x _{3} - x _{2}}{f ( x _{3} ) - f ( x _{2} )} = 0.63635 - (- 0.10605) \times \frac{0.63635 - 0.5}{- 0.10605 - ( - 0.375 )} = 0.63635 + 0.10605 \times \frac{0.13635}{0.26895} = 0.63635 + 0.10605 \times 0.50697 = 0.63635 + 0.05377 = 0.69012$ $f (x_{4}) = (0.69012)^{3} + 0.69012 - 1 \approx 0.3287 + 0.69012 - 1 = 0.01882$

$x_{5} = x_{4} - f (x_{4}) \frac{x _{4} - x _{3}}{f ( x _{4} ) - f ( x _{3} )} = 0.69012 - (0.01882) \times \frac{0.69012 - 0.63635}{0.01882 - ( - 0.10605 )} = 0.69012 - 0.01882 \times \frac{0.05377}{0.12487} = 0.69012 - 0.00810 = 0.68202$ $f (x_{5}) = (0.68202)^{3} + 0.68202 - 1 \approx 0.3173 + 0.68202 - 1 = - 0.00068$

结果：迭代5次后，函数值非常接近零。近似根 $x \approx 0.682$ 。

Python代码示例：

def test_secant_example():
    """
    验证割线法求 f(x)=x^3+x-1 的根的例题
    文档中的答案：x ≈ 0.6822 (文档计算过程有微小差异，取0.682)
    """
    f = lambda x: x**3 + x - 1
    
    # 割线法实现
    def secant_method(f, x0, x1, tol=1e-10, max_iter=100):
        for i in range(max_iter):
            f0, f1 = f(x0), f(x1)
            
            if abs(f1) < tol:
                return x1
            
            if f1 == f0:
                raise ValueError("割线法分母为零")
            
            x_new = x1 - f1 * (x1 - x0) / (f1 - f0)
            
            if abs(x_new - x1) < tol:
                return x_new
            
            x0, x1 = x1, x_new
        
        return x1
    
    # 用自己实现的割线法计算
    root_secant = secant_method(f, 0, 1, tol=1e-4)
    # 用scipy的方法计算精确值
    root_exact = optimize.root_scalar(f, bracket=[0, 1], method='brentq').root
    # 文档中给出的答案 (根据我们的计算是 0.682)
    root_document = 0.682
    
    # 验证部分在test文件中执行
    print(f"割线法计算结果: {root_secant}")
    print(f"文档答案 (按计算过程): {root_document}")
    print(f"Scipy精确解: {root_exact}")
    print(f"函数在文档答案处的值: {f(root_document)}")

# 运行示例 (需要 import numpy as np 和 from scipy import optimize)
# test_secant_example()

例题5：割线法求解 $f (x) = cos (x) - x$

问题：用割线法求 $f (x) = cos (x) - x$ 的根，取初值 $x_{0} = 0.5, x_{1} = 1$ 。

分析： $f (x) = cos (x) - x$

迭代过程： $x_{0} = 0.5, f (x_{0}) = cos (0.5) - 0.5 \approx 0.8776 - 0.5 = 0.3776$ $x_{1} = 1, f (x_{1}) = cos (1) - 1 \approx 0.5403 - 1 = - 0.4597$

$x_{2} = x_{1} - f (x_{1}) \frac{x _{1} - x _{0}}{f ( x _{1} ) - f ( x _{0} )} = 1 - (- 0.4597) \frac{1 - 0.5}{- 0.4597 - 0.3776} = 1 + 0.4597 \frac{0.5}{- 0.8373} = 1 - 0.4597 \times 0.5968 = 1 - 0.2744 = 0.7256$ $f (x_{2}) = cos (0.7256) - 0.7256 \approx 0.7481 - 0.7256 = 0.0225$

$x_{3} = x_{2} - f (x_{2}) \frac{x _{2} - x _{1}}{f ( x _{2} ) - f ( x _{1} )} = 0.7256 - (0.0225) \frac{0.7256 - 1}{0.0225 - ( - 0.4597 )} = 0.7256 - 0.0225 \frac{- 0.2744}{0.4822} = 0.7256 + 0.0225 \times 0.5691 = 0.7256 + 0.0128 = 0.7384$ $f (x_{3}) = cos (0.7384) - 0.7384 \approx 0.7396 - 0.7384 = 0.0012$

$x_{4} = x_{3} - f (x_{3}) \frac{x _{3} - x _{2}}{f ( x _{3} ) - f ( x _{2} )} = 0.7384 - (0.0012) \frac{0.7384 - 0.7256}{0.0012 - 0.0225} = 0.7384 - 0.0012 \frac{0.0128}{- 0.0213} = 0.7384 + 0.0012 \times 0.6009 = 0.7384 + 0.0007 = 0.7391$

结果：迭代几次后，解趋于稳定。近似根 $x \approx 0.739$ 。

Python代码示例：

def test_cos_x_example():
    """
    验证割线法求 f(x) = cos(x) - x 的根的例题
    文档中的答案：x ≈ 0.739
    """
    f = lambda x: np.cos(x) - x
    
    # 使用上面的割线法实现
    root_secant = secant_method(f, 0.5, 1, tol=1e-4)
    # 用scipy的方法计算精确值
    root_exact = optimize.root_scalar(f, bracket=[0, 1], method='brentq').root
    # 文档中给出的答案
    root_document = 0.739
    
    # 验证部分在test文件中执行
    print(f"割线法计算结果: {root_secant}")
    print(f"文档答案: {root_document}")
    print(f"Scipy精确解: {root_exact}")
    print(f"函数在文档答案处的值: {f(root_document)}")

# 运行示例 (需要 import numpy as np 和 from scipy import optimize, 以及上面的 secant_method 函数)
# test_cos_x_example()

1.2.4 Regula Falsi 法（假位法）

原理：
结合二分法的可靠性和割线法的快速收敛性。使用割线法确定下一个迭代点，但保持区间端点异号。
迭代公式：
与割线法相同，但每次迭代后保留使函数值异号的区间。
算法流程：
1. 初始区间 $[a, b]$ 满足 $f (a) f (b) < 0$
2. 计算割线法的下一个点 $c = b - f (b) \frac{b - a}{f ( b ) - f ( a )}$
3. 若 $f (c) f (a) < 0$ ，则 $b = c$ ；否则 $a = c$
4. 重复2-3直到收敛
优缺点：
- 优点：结合了二分法的可靠性和割线法的快速收敛
- 缺点：在某些情况下可能收敛缓慢
英文关键词：regula falsi, false position method, bracketing method, hybrid method

1.2.5 Brent 方法

原理：
结合二分法、割线法和反二次插值（inverse quadratic interpolation）的优点，是实际应用中最常用的求根方法之一。
特点：
- 保证收敛（如二分法）
- 在良好条件下快速收敛（如割线法）
- 使用三点插值进一步加速收敛
- MATLAB 的 fzero 函数和 Python 的 scipy.optimize.brentq 使用此方法
英文关键词：Brent's method, inverse quadratic interpolation, guaranteed convergence, hybrid method

1.3 典型例题与详细解答

例题1：用二分法求 $f (x) = x^{3} + x - 1$ 在 $[0, 1]$ 内的根，精度 $1 0^{- 2}$

解答步骤：

检查端点： $f (0) = 0^{3} + 0 - 1 = - 1$ , $f (1) = 1^{3} + 1 - 1 = 1$ ，满足 $f (0) f (1) < 0$ ，可用二分法。
第一次迭代：
- $c_{1} = (0 + 1) /2 = 0.5$
- $f (0.5) = 0. 5^{3} + 0.5 - 1 = 0.125 + 0.5 - 1 = - 0.375$
- $f (0) f (0.5) = (- 1) (- 0.375) > 0$ ，根在 $[0.5, 1]$
第二次迭代：
- $c_{2} = (0.5 + 1) /2 = 0.75$
- $f (0.75) = 0.7 5^{3} + 0.75 - 1 = 0.422 + 0.75 - 1 = 0.172$
- $f (0.5) f (0.75) = (- 0.375) (0.172) < 0$ ，根在 $[0.5, 0.75]$
第三次迭代：
- $c_{3} = (0.5 + 0.75) /2 = 0.625$
- $f (0.625) = 0.62 5^{3} + 0.625 - 1 = 0.244 + 0.625 - 1 = - 0.131$
- $f (0.5) f (0.625) = (- 0.375) (- 0.131) > 0$ ，根在 $[0.625, 0.75]$
第四次迭代：
- $c_{4} = (0.625 + 0.75) /2 = 0.6875$
- $f (0.6875) = 0.687 5^{3} + 0.6875 - 1 = 0.325 + 0.6875 - 1 = 0.0125$
- $f (0.625) f (0.6875) = (- 0.131) (0.0125) < 0$ ，根在 $[0.625, 0.6875]$
检查精度： $∣0.6875 - 0.625∣ = 0.0625 > 0.01$ ，继续迭代
第五次迭代：
- $c_{5} = (0.625 + 0.6875) /2 = 0.65625$
- $f (0.65625) = 0.6562 5^{3} + 0.65625 - 1 = 0.283 + 0.65625 - 1 = - 0.061$
- $f (0.625) f (0.65625) = (- 0.131) (- 0.061) > 0$ ，根在 $[0.65625, 0.6875]$
检查精度： $∣0.6875 - 0.65625∣ = 0.03125 > 0.01$ ，继续迭代
第六次迭代：
- $c_{6} = (0.65625 + 0.6875) /2 = 0.671875$
- $f (0.671875) = 0.67187 5^{3} + 0.671875 - 1 = 0.303 + 0.671875 - 1 = - 0.025$
- $f (0.65625) f (0.671875) = (- 0.061) (- 0.025) > 0$ ，根在 $[0.671875, 0.6875]$
检查精度： $∣0.6875 - 0.671875∣ = 0.015625 > 0.01$ ，继续迭代
第七次迭代：
- $c_{7} = (0.671875 + 0.6875) /2 = 0.6796875$
- $f (0.6796875) = 0.679687 5^{3} + 0.6796875 - 1 = 0.314 + 0.6796875 - 1 = - 0.006$
- $f (0.671875) f (0.6796875) = (- 0.025) (- 0.006) > 0$ ，根在 $[0.6796875, 0.6875]$
检查精度： $∣0.6875 - 0.6796875∣ = 0.0078125 < 0.01$ ，满足精度要求，停止迭代

答案： $x \approx 0.6796875$ ，精确根约为 $0.6823$ ，误差在允许范围内。

例题2：用牛顿法求 $f (x) = x^{2} - 2$ 的根， $x_{0} = 1$ ，精度 $1 0^{- 4}$

解答步骤：

计算 $f (x) = x^{2} - 2$ , $f^{'} (x) = 2 x$
第一次迭代：
- $f (1) = 1^{2} - 2 = - 1$ , $f^{'} (1) = 2$
- $x_{1} = 1 - \frac{- 1}{2} = 1 - \frac{- 1}{2} = 1.5$
第二次迭代：
- $f (1.5) = 1. 5^{2} - 2 = 2.25 - 2 = 0.25$ , $f^{'} (1.5) = 3$
- $x_{2} = 1.5 - \frac{0.25}{3} = 1.5 - \frac{0.25}{3} = 1.4167$
第三次迭代：
- $f (1.4167) = 1.416 7^{2} - 2 = 2.007 - 2 = 0.007$ , $f^{'} (1.4167) = 2.8334$
- $x_{3} = 1.4167 - \frac{0.007}{2.8334} = 1.4167 - 0.0025 = 1.4142$
第四次迭代：
- $f (1.4142) = 1.414 2^{2} - 2 = 2.0000 - 2 = 0.00004$ , $f^{'} (1.4142) = 2.8284$
- $x_{4} = 1.4142 - \frac{0.00004}{2.8284} = 1.4142 - 0.000014 = 1.414186$
检查精度： $∣ x_{4} - x_{3} ∣ = ∣1.414186 - 1.4142∣ = 0.000014 < 1 0^{- 4}$ ，满足精度要求

答案： $x \approx 1.4142$ ，即 $2$ 的近似值。

收敛性分析：

第一次迭代：误差约 $0.5$
第二次迭代：误差约 $0.0025$ （误差平方级减小）
第三次迭代：误差约 $0.000014$ （继续平方级减小）
体现了牛顿法的二次收敛特性

例题3：用牛顿法求解 $f (x) = e^{x} - x - 2$ 的根，初始值 $x_{0} = 1$

解答步骤：

计算 $f (x) = e^{x} - x - 2$ ， $f^{'} (x) = e^{x} - 1$
第一次迭代：
- $f (1) = e^{1} - 1 - 2 = 2.718 - 1 - 2 = - 0.282$
- $f^{'} (1) = e^{1} - 1 = 2.718 - 1 = 1.718$
- $x_{1} = 1 - \frac{- 0.282}{1.718} = 1 + 0.164 = 1.164$
第二次迭代：
- $f (1.164) = e^{1.164} - 1.164 - 2 = 3.203 - 1.164 - 2 = 0.039$
- $f^{'} (1.164) = e^{1.164} - 1 = 3.203 - 1 = 2.203$
- $x_{2} = 1.164 - \frac{0.039}{2.203} = 1.164 - 0.018 = 1.146$
第三次迭代：
- $f (1.146) = e^{1.146} - 1.146 - 2 = 3.146 - 1.146 - 2 = 0.000$
- 已经足够接近零，可以停止迭代

答案： $x \approx 1.146$

验证： $e^{1.146} \approx 3.146$ ， $1.146 + 2 = 3.146$ ，方程成立。

1.4 常见考点与易错点

初值选择：
- 牛顿法对初值敏感，选择不当可能导致不收敛或收敛到非预期根
- 二分法需要确保区间端点函数值异号
- 割线法需要两个初始点，且不能使函数值相等
收敛判断：
- 解的变化： $∣ x_{n + 1} - x_{n} ∣ < ϵ_{x}$
- 函数值接近零： $∣ f (x_{n + 1}) ∣ < ϵ_{f}$
- 两种判断标准可能导致不同的停止时机
收敛速度比较：
- 二分法：线性收敛（收敛阶为1）
- 牛顿法：二次收敛（收敛阶为2）
- 割线法：超线性收敛（收敛阶约为1.618）
特殊情况处理：
- 重根问题：牛顿法对重根收敛较慢
- 导数为零：牛顿法可能失效
- 函数不连续：需要谨慎选择区间
误差分析：
- 截断误差：由算法本身引入
- 舍入误差：由计算机浮点运算引入
- 两种误差的平衡考虑

中文术语	英文术语
方程求根	Root Finding
二分法	Bisection Method
牛顿法	Newton's Method / Newton-Raphson Method
割线法	Secant Method
假位法	Regula Falsi / False Position Method
收敛性	Convergence
收敛阶	Order of Convergence
线性收敛	Linear Convergence
二次收敛	Quadratic Convergence
超线性收敛	Superlinear Convergence
全局收敛	Global Convergence
局部收敛	Local Convergence
误差估计	Error Estimation
截断误差	Truncation Error
舍入误差	Round-off Error
迭代法	Iterative Method
直接法	Direct Method
混合法	Hybrid Method

CE7453 Numerical Algorithms Notes

CE7453 Numerical Algorithms 期末高分超详细攻略（第一章：Root Finding）

1.1 基本概念与背景

1.2 主要算法与原理

1.2.1 二分法（Bisection Method）

例题1：二分法求解 $f (x) = x^{3} + x - 1$

1.2.2 牛顿法（Newton's Method）

例题2：牛顿法求解 $f (x) = x^{2} - 2$

例题3：牛顿法求解 $f (x) = e^{x} - x - 2$

牛顿法求 $3$ 的例题

1.2.3 割线法（Secant Method）

例题4：割线法求解 $f (x) = x^{3} + x - 1$

例题5：割线法求解 $f (x) = cos (x) - x$

1.2.4 Regula Falsi 法（假位法）

1.2.5 Brent 方法

1.3 典型例题与详细解答

例题1：用二分法求 $f (x) = x^{3} + x - 1$ 在 $[0, 1]$ 内的根，精度 $1 0^{- 2}$

例题2：用牛顿法求 $f (x) = x^{2} - 2$ 的根， $x_{0} = 1$ ，精度 $1 0^{- 4}$

例题3：用牛顿法求解 $f (x) = e^{x} - x - 2$ 的根，初始值 $x_{0} = 1$

1.4 常见考点与易错点

1.5 实际应用案例

1.5.1 计算机图形学中的曲线求交

1.5.2 机器学习中的优化问题

1.5.3 物理模拟中的平衡点

1.6 英文术语对照表