// 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;
}
