CASE 3.1
二分法 vs 牛顿法:收敛对决
方程 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 步到机器精度。
要点解析:二分法的可靠性来自零点定理的构造性证明(区间套);牛顿法的速度来自切线近似的二阶精度,代价是需要导数且可能发散(初值选取敏感)。稳健与快速的取舍,是所有迭代算法的共同命题。