实验室/上册/第3章 微分中值定理与导数的应用
CPP LAB · CHAPTER 03

中值定理与求根

零点存在定理撑起二分法,切线思想撑起牛顿法,闭区间最值存在性撑起三分法——第 3 章的三大定理各自「孵化」一个经典算法。理论对照主站 第3章。

CASE 3.1 二分法 vs 牛顿法:收敛对决
数学:零点定理 / 切线C++:迭代 + SVG

方程 x³ − x − 1 = 0(唯一实根 r ≈ 1.324718)。二分法从 [1,2] 出发每次对折区间;牛顿法从 x₀=1.5 出发,每步用切线截距更新:xn+1 = xn − f(xn)/f′(xn)。两份迭代表 + 一幅程序生成的半对数误差图,胜负立判。

code/ch03a_roots.cpp(生成 SVG 需要 svgplot.hpp)下载源码 ↓
// ch03a_roots.cpp —— 实验 3.1:二分法与牛顿法求根(含 SVG 收敛曲线)
// 数学:零点存在定理(二分法的依据)+ 牛顿迭代 x_{n+1} = x_n − f(x_n)/f'(x_n)
// 方程:x³ − x − 1 = 0,唯一实根 r ≈ 1.324717957244746
#include "svgplot.hpp"
#include <cstdio>
#include <cmath>
#include <vector>

double f(double x)  { return x * x * x - x - 1.0; }
double fp(double x) { return 3.0 * x * x - 1.0; }

int main() {
    const double ROOT = 1.324717957244746;      // 参考真值
    printf("== 实验 3.1 二分法 vs 牛顿法:x^3 − x − 1 = 0 ==\n\n");

    // ---- 二分法:[1, 2],零点存在定理保证区间内有根 ----
    printf("[二分法] 区间 [1,2],12 次对折:\n");
    printf("%4s %20s %14s\n", "n", "区间中点 c_n", "|c_n − r|");
    printf("------------------------------------------\n");
    std::vector<std::pair<double, double>> errBis;
    double a = 1.0, b = 2.0;
    for (int n = 1; n <= 12; ++n) {
        double c = 0.5 * (a + b);
        double e = std::fabs(c - ROOT);
        printf("%4d %20.15f %14.3e\n", n, c, e);
        errBis.push_back({(double)n, std::log10(e)});
        if (f(a) * f(c) <= 0) b = c; else a = c;
    }

    // ---- 牛顿法:x0 = 1.5,切线与 x 轴交点作为下一步 ----
    printf("\n[牛顿法] 初值 x0 = 1.5:\n");
    printf("%4s %20s %14s\n", "n", "迭代点 x_n", "|x_n − r|");
    printf("------------------------------------------\n");
    std::vector<std::pair<double, double>> errNew;
    double x = 1.5;
    for (int n = 0; n <= 6; ++n) {
        double e = std::fabs(x - ROOT);
        printf("%4d %20.15f %14.3e\n", n, x, e);
        if (e > 0) errNew.push_back({(double)n, std::log10(e)});
        x = x - f(x) / fp(x);
    }

    printf("\n结论:二分法误差每次减半(线性收敛),12 次仅到 1e-4;\n");
    printf("      牛顿法误差平方级下降(二次收敛),5 次即达机器精度。\n");

    // ---- SVG:误差的常用对数曲线 ----
    SvgPlot pl(0.0, 12.0, -16.5, 0.5, 680, 400);
    pl.open("ch03a_roots.svg");
    pl.axes("迭代次数 n", "log10 |误差|");
    pl.plot(errBis, "#003b5c", 1.8, "", "二分法(线性收敛)");
    pl.plot(errNew, "#b23a2e", 2.2, "", "牛顿法(二次收敛)");
    pl.legend();
    pl.close();
    printf("已生成 ch03a_roots.svg(误差半对数收敛曲线)\n");
    return 0;
}
▶ 编译运行输出
== 实验 3.1 二分法 vs 牛顿法:x^3 − x − 1 = 0 ==

[二分法] 区间 [1,2],12 次对折:
   n     区间中点 c_n    |c_n − r|
------------------------------------------
   1    1.500000000000000      1.753e-01
   2    1.250000000000000      7.472e-02
   3    1.375000000000000      5.028e-02
   4    1.312500000000000      1.222e-02
   5    1.343750000000000      1.903e-02
   6    1.328125000000000      3.407e-03
   7    1.320312500000000      4.405e-03
   8    1.324218750000000      4.992e-04
   9    1.326171875000000      1.454e-03
  10    1.325195312500000      4.774e-04
  11    1.324707031250000      1.093e-05
  12    1.324951171875000      2.332e-04

[牛顿法] 初值 x0 = 1.5:
   n        迭代点 x_n    |x_n − r|
------------------------------------------
   0    1.500000000000000      1.753e-01
   1    1.347826086956522      2.311e-02
   2    1.325200398950907      4.824e-04
   3    1.324718173999054      2.168e-07
   4    1.324717957244790      4.374e-14
   5    1.324717957244746      0.000e+00
   6    1.324717957244746      0.000e+00

结论:二分法误差每次减半(线性收敛),12 次仅到 1e-4;
      牛顿法误差平方级下降(二次收敛),5 次即达机器精度。
已生成 ch03a_roots.svg(误差半对数收敛曲线)
二分法与牛顿法的误差收敛半对数曲线
FIG 3.1误差收敛曲线(程序生成):二分法每步误差减半(蓝线,线性),牛顿法误差平方级坍缩(红线,二次)——5 步到机器精度。

要点解析:二分法的可靠性来自零点定理的构造性证明(区间套);牛顿法的速度来自切线近似的二阶精度,代价是需要导数且可能发散(初值选取敏感)。稳健与快速的取舍,是所有迭代算法的共同命题。

CASE 3.2 三分法搜索极值
数学:最值存在性C++:区间消去

求 f(x) = x·e−x 的极大点(理论 x*=1)。三分法在区间内取两个三分点,比较函数值后每次砍掉三分之一——全程不需要导数,适合「黑盒」函数。

code/ch03b_extremum.cpp下载源码 ↓
// ch03b_extremum.cpp —— 实验 3.2:三分法搜索极值
// 数学:闭区间连续函数必有最值;极值点处 f' = 0(驻点)
// 三分法:每次保留三分之二区间,逼近极大点(不需求导)
#include <cstdio>
#include <cmath>

double f(double x) { return x * std::exp(-x); }   // 极大点在 x = 1(f'(1)=0)

int main() {
    printf("== 实验 3.2 三分法求 f(x) = x·e^(−x) 的极大点 ==\n\n");
    printf("理论:f'(x) = (1−x)e^(−x),驻点 x = 1,f''(1) < 0,极大值 f(1) = e^(−1)。\n\n");

    double a = 0.2, b = 5.0;
    printf("%4s %22s %22s %14s\n", "n", "区间 [a, b]", "区间长度", "f(区间中点)");
    printf("--------------------------------------------------------------\n");
    int n = 0;
    while (b - a > 1e-10) {
        double m1 = a + (b - a) / 3.0;
        double m2 = b - (b - a) / 3.0;
        if (f(m1) < f(m2)) a = m1;     // 极大点在右侧三分之二
        else               b = m2;
        ++n;
        double mid = 0.5 * (a + b);
        printf("%4d   [%10.7f, %10.7f] %22.3e %14.9f\n",
               n, a, b, b - a, f(mid));
        if (n >= 60) break;
    }

    double xm = 0.5 * (a + b);
    printf("\n结果:极大点 x* ≈ %.12f(理论值 1)\n", xm);
    printf("      极大值 f(x*) ≈ %.12f(理论值 e^(−1) = %.12f)\n",
           f(xm), std::exp(-1.0));
    printf("      误差 %.2e —— 三分法不依赖导数,适合“黑盒”函数。\n",
           std::fabs(xm - 1.0));
    return 0;
}
▶ 编译运行输出
== 实验 3.2 三分法求 f(x) = x·e^(−x) 的极大点 ==

理论:f'(x) = (1−x)e^(−x),驻点 x = 1,f''(1) < 0,极大值 f(1) = e^(−1)。

   n          区间 [a, b]           区间长度 f(区间中点)
--------------------------------------------------------------
   1   [ 0.2000000,  3.4000000]              3.200e+00    0.297537999
   2   [ 0.2000000,  2.3333333]              2.133e+00    0.356907766
   3   [ 0.2000000,  1.6222222]              1.422e+00    0.366337026
   4   [ 0.6740741,  1.6222222]              9.481e-01    0.364219777
   5   [ 0.6740741,  1.3061728]              6.321e-01    0.367861380
   6   [ 0.8847737,  1.3061728]              4.214e-01    0.366305795
   7   [ 0.8847737,  1.1657064]              2.809e-01    0.367764214
   8   [ 0.8847737,  1.0720622]              1.873e-01    0.367792522
   9   [ 0.9472032,  1.0720622]              1.249e-01    0.367862483
  10   [ 0.9472032,  1.0304425]              8.324e-02    0.367856290
  11   [ 0.9749496,  1.0304425]              5.549e-02    0.367878107
  12   [ 0.9749496,  1.0119449]              3.700e-02    0.367871508
  13   [ 0.9872814,  1.0119449]              2.466e-02    0.367879414
  14   [ 0.9955025,  1.0119449]              1.644e-02    0.367876897
  15   [ 0.9955025,  1.0064641]              1.096e-02    0.367879263
  16   [ 0.9955025,  1.0028102]              7.308e-03    0.367879310
  17   [ 0.9979384,  1.0028102]              4.872e-03    0.367879415
  18   [ 0.9979384,  1.0011863]              3.248e-03    0.367879406
  19   [ 0.9990211,  1.0011863]              2.165e-03    0.367879439
  20   [ 0.9990211,  1.0004646]              1.443e-03    0.367879429
  21   [ 0.9995022,  1.0004646]              9.623e-04    0.367879441
  22   [ 0.9998230,  1.0004646]              6.416e-04    0.367879437
  23   [ 0.9998230,  1.0002507]              4.277e-04    0.367879441
  24   [ 0.9998230,  1.0001081]              2.851e-04    0.367879441
  25   [ 0.9999181,  1.0001081]              1.901e-04    0.367879441
  26   [ 0.9999181,  1.0000448]              1.267e-04    0.367879441
  27   [ 0.9999603,  1.0000448]              8.448e-05    0.367879441
  28   [ 0.9999603,  1.0000166]              5.632e-05    0.367879441
  29   [ 0.9999791,  1.0000166]              3.755e-05    0.367879441
  30   [ 0.9999916,  1.0000166]              2.503e-05    0.367879441
  31   [ 0.9999916,  1.0000083]              1.669e-05    0.367879441
  32   [ 0.9999972,  1.0000083]              1.113e-05    0.367879441
  33   [ 0.9999972,  1.0000046]              7.417e-06    0.367879441
  34   [ 0.9999972,  1.0000021]              4.945e-06    0.367879441
  35   [ 0.9999988,  1.0000021]              3.296e-06    0.367879441
  36   [ 0.9999988,  1.0000010]              2.198e-06    0.367879441
  37   [ 0.9999995,  1.0000010]              1.465e-06    0.367879441
  38   [ 0.9999995,  1.0000005]              9.767e-07    0.367879441
  39   [ 0.9999995,  1.0000002]              6.512e-07    0.367879441
  40   [ 0.9999997,  1.0000002]              4.341e-07    0.367879441
  41   [ 0.9999999,  1.0000002]              2.894e-07    0.367879441
  42   [ 0.9999999,  1.0000001]              1.929e-07    0.367879441
  43   [ 1.0000000,  1.0000001]              1.286e-07    0.367879441
  44   [ 1.0000000,  1.0000000]              8.575e-08    0.367879441
  45   [ 1.0000000,  1.0000000]              5.717e-08    0.367879441
  46   [ 1.0000000,  1.0000000]              3.811e-08    0.367879441
  47   [ 1.0000000,  1.0000000]              2.541e-08    0.367879441
  48   [ 1.0000000,  1.0000000]              1.694e-08    0.367879441
  49   [ 1.0000000,  1.0000000]              1.129e-08    0.367879441
  50   [ 1.0000000,  1.0000000]              7.528e-09    0.367879441
  51   [ 1.0000000,  1.0000000]              5.019e-09    0.367879441
  52   [ 1.0000000,  1.0000000]              3.346e-09    0.367879441
  53   [ 1.0000000,  1.0000000]              2.231e-09    0.367879441
  54   [ 1.0000000,  1.0000000]              1.487e-09    0.367879441
  55   [ 1.0000000,  1.0000000]              9.913e-10    0.367879441
  56   [ 1.0000000,  1.0000000]              6.609e-10    0.367879441
  57   [ 1.0000000,  1.0000000]              4.406e-10    0.367879441
  58   [ 1.0000000,  1.0000000]              2.937e-10    0.367879441
  59   [ 1.0000000,  1.0000000]              1.958e-10    0.367879441
  60   [ 1.0000000,  1.0000000]              1.305e-10    0.367879441

结果:极大点 x* ≈ 0.999999991052(理论值 1)
      极大值 f(x*) ≈ 0.367879441171(理论值 e^(−1) = 0.367879441171)
      误差 8.95e-09 —— 三分法不依赖导数,适合“黑盒”函数。

要点解析:对照理论:f′(x) = (1−x)e−x,驻点恰在 x=1,f″(1) < 0 确认极大——数值搜索与解析判别殊途同归。三分法与二分法是同一套「区间套」思想的两种用法:一个找零点,一个找极值。