7-18 二分法求多项式单根 (20 分)

这是一个编程类的问题，可以回答。二分法求多项式单根的基本思路是：首先确定一个区间，然后将区间分成两半，判断单根在哪一半，再将该半区间继续分成两半，重复上述步骤，直到找到单根或者区间足够小。具体实现可以参考以下代码： ```lua -- 多项式函数 function f(x) return x^3 - 2*x - 5 end -- 二分法求单根 function bisection(a, b, eps) local fa, fb = f(a), f(b) if fa * fb > 0 then return nil end while b - a > eps do local c = (a + b) / 2 local fc = f(c) if fa * fc < 0 then b, fb = c, fc else a, fa = c, fc end end return (a + b) / 2 end -- 测试 local root = bisection(1, 2, 0.0001) if root then print("单根为：" .. root) else print("未找到单根") end ``` 其中，f(x) 是多项式函数，bisection(a, b, eps) 是二分法求单根的函数，a 和 b 是区间的左右端点，eps 是精度要求。在测试中，我们以 x^3 - 2x - 5 = 0 为例，求解区间为 [1, 2]，精度要求为 0.0001。运行结果为： ``` 单根为：1.7692928314209 ```

### 使用二分法求解多项式单根 #### 方法概述 二分法是一种基于区间分割的数值方法，适用于连续函数在一个闭区间上只有一个实数根的情况。其基本原理是不断缩小区间范围，直到满足精度要求为止。对于多项式 $ f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_0 $ 的单根问题，在已知区间 $[a, b]$ 上如果满足 $f(a) \cdot f(b) < 0$，则该区间内必然存在一个实数根。 以下是具体的算法描述： 1. 定义多项式的系数数组 `coeff` 和目标区间的两个端点 $a$ 和 $b$。 2. 计算多项式在两端点处的值 $f(a)$ 和 $f(b)$。 3. 如果 $f(a) \cdot f(b) > 0$，说明区间内无根或有多重根，则需重新定义区间[^3]。 4. 否则进入循环，计算中间点 $c = (a+b)/2$ 并判断： - 若 $|f(c)|$ 小于设定的误差阈值 $\epsilon$ 或者 $(b-a)/2 < \delta$（其中 $\delta$ 是允许的最大步长），返回 $c$ 作为近似根； - 若 $f(a) \cdot f(c) < 0$，更新右边界 $b=c$； - 否则更新左边界 $a=c$。 #### 示例代码实现 下面是一个 Java 实现的例子，用于求解任意次数多项式的单根： ```java public class PolynomialRootFinder { public static double evaluatePolynomial(double[] coeff, double x) { double result = 0; int n = coeff.length; // Number of coefficients for (int i = 0; i < n; i++) { result += coeff[i] * Math.pow(x, n - 1 - i); // Calculate polynomial value at x } return result; } public static double findSingleRoot(double[] coeff, double a, double b, double epsilon) { if (evaluatePolynomial(coeff, a) * evaluatePolynomial(coeff, b) >= 0) { System.out.println("The interval does not bracket a root."); return Double.NaN; } while ((b - a) / 2 > epsilon) { // Continue until the interval is small enough double c = (a + b) / 2; // Midpoint double fc = evaluatePolynomial(coeff, c); if (fc == 0 || (b - a) / 2 < epsilon) { // Root found or precision reached return c; } else if (evaluatePolynomial(coeff, a) * fc < 0) { b = c; // Narrow to left half } else { a = c; // Narrow to right half } } return (a + b) / 2; // Return midpoint as approximation } public static void main(String[] args) { double[] coeff = {-6, 11, -6, 1}; // Coefficients of x^3 - 6x^2 + 11x - 6 double a = 1.5, b = 2.5, epsilon = 1e-7; double root = findSingleRoot(coeff, a, b, epsilon); if (!Double.isNaN(root)) { System.out.printf("Approximate root: %.7f\n", root); } } } ``` 上述程序实现了以下功能： - **`evaluatePolynomial` 函数**：根据给定的多项式系数和变量值 $x$，计算多项式的值。 - **`findSingleRoot` 函数**：采用二分法查找指定区间内的单根，并控制误差小于预设阈值 $\epsilon$。 - **主函数部分**：设置了一组测试数据来验证算法的有效性。 #### 注意事项 1. 输入的多项式必须在其所选区间上有且仅有一个实数根，否则可能导致错误的结果或者无限循环。 2. 需要合理调整参数 $\epsilon$ 来平衡精确度与运行时间之间的关系。