M04140: 方程求解

牛顿迭代法, AI, binary search, http://cs101.openjudge.cn/practice/04140/

求下面方程的根：$ f(x) = x^3 - 5x^2 + 10x - 80 = 0 $。

输入

输出

精确到小数点后9位。

样例输入

样例输出

可以用 牛顿迭代法 或 二分法 来求解方程 $ f(x) = x^3 - 5x^2 + 10x - 80 = 0 $。

方法 1：牛顿迭代法（Newton-Raphson Method）

牛顿法适用于方程可微的情况，需要计算导数：

f^{'} (x) = 3 x^{2} - 10 x + 10

更新公式：

x_{n + 1} = x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})}

Python 实现，输出保留到小数点后 9 位：

python

def f(x):
    return x**3 - 5*x**2 + 10*x - 80

def f_prime(x):
    return 3*x**2 - 10*x + 10

def newton_method(x0, eps=1e-10, max_iter=1000):
    x = x0
    for _ in range(max_iter):
        fx = f(x)
        fpx = f_prime(x)
        if abs(fpx) < 1e-12:
            raise ValueError("Derivative too small, method fails.")
        x_new = x - fx / fpx
        if abs(x_new - x) < eps:
            return x_new
        x = x_new
    raise ValueError("Newton method did not converge.")

# 初始猜测（可以图像估计或经验选择）
initial_guess = 4.0
root = newton_method(initial_guess)

# 输出结果，保留9位小数
print(f"{root:.9f}")

说明：

使用初始猜测 x0 = 4.0，该函数在 x=4 附近有根。
精度设置为 1e-10，确保输出时小数点后 9 位准确。
若牛顿法不收敛，会抛出异常。

这个程序没有输入，因此运行时直接输出结果即可，符合题目要求。

用牛顿迭代法实现。
因为大语言模型的训练过程中涉及到了梯度下降（或其变种，如SGD、Adam等），用于优化模型参数以最小化损失函数。两种方法都是通过迭代的方式逐步接近最优解。每一次迭代都基于当前点的局部信息调整参数，试图找到一个比当前点更优的新点。理解牛顿迭代法有助于深入理解基于梯度的优化算法的工作原理，特别是它们如何利用导数信息进行决策。
牛顿迭代法
目的：主要用于寻找一个函数 $f (x)$ 的根，即找到满足 $f (x) = 0$ 的 $x$ 值。不过，通过适当变换目标函数，它也可以用于寻找函数的极值。
方法基础：利用泰勒级数的一阶和二阶项来近似目标函数，在每次迭代中使用目标函数及其导数的信息来计算下一步的方向和步长。
迭代公式：$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $ 对于求极值问题，这可以转化为$ x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)} $，这里 $f^{'} (x)$ 和 $f^{″} (x)$ 分别是目标函数的一阶导数和二阶导数。
特点：牛顿法通常具有更快的收敛速度（尤其是对于二次可微函数），但是需要计算目标函数的二阶导数（Hessian矩阵在多维情况下），并且对初始点的选择较为敏感。
梯度下降法
目的：直接用于寻找函数的最小值（也可以通过取负寻找最大值），尤其在机器学习领域应用广泛。
方法基础：仅依赖于目标函数的一阶导数信息（即梯度），沿着梯度的反方向移动以达到减少函数值的目的。
迭代公式：$ x_{n+1} = x_n - \alpha \cdot \nabla f(x_n) $ 这里 $α$ 是学习率， $\nabla f (x_{n})$ 表示目标函数在 $x_{n}$ 点的梯度。
特点：梯度下降不需要计算复杂的二阶导数，因此在高维空间中相对容易实现。然而，它的收敛速度通常较慢，特别是当目标函数的等高线呈现出椭圆而非圆形时（即存在条件数大的情况）。
相同与不同
相同点：两者都可用于优化问题，试图找到函数的极小值点；都需要目标函数至少一阶可导。
不同点：
牛顿法使用了更多的局部信息（即二阶导数），因此理论上收敛速度更快，但在实际应用中可能会遇到计算成本高、难以处理大规模数据集等问题。
梯度下降则更为简单，易于实现，特别是在高维空间中，但由于只使用了一阶导数信息，其收敛速度可能较慢，尤其是在接近极值点时。

思路：先算一下迭代的方程$$\phi(x)=x-\frac{x^3-5x^2+10x-80}{3x^2-10x+10}=\frac{2x^3-5x^2+80}{3x^2-10x+10}$$ 与此同时，利用一点点数学，可以发现原方程有且仅有一实根，且在5到6之间。

python

# coding: utf-8
"""
@File        :   newton_04140.py
@Time        :   2025/03/01 16:14:57
@Author      :   Usercyk
@Description :   Using Newton's method to solve the equation f(x) = 0
"""


class Solution:
    """
    The solution
    """

    def phi(self, x: float) -> float:
        """
        The iteration function

        Arguments:
            x -- The nth x value

        Returns:
            The (n+1)th x value
        """
        return (2*x**3-5*x**2+80)/(3*x**2-10*x+10)

    def solve(self, x_init: float = 5.0, eps: float = 1e-15) -> float:
        """
        Solve the equation f(x) = x**3-5*x**2+10*x-80 = 0

        Keyword Arguments:
            x_init -- The initial value of x (default: {5.0})
            eps -- The precision (default: {1e-15})

        Returns:
            The solution of the equation
        """
        x = x_init
        while True:
            x_next = self.phi(x)
            if abs(x_next-x) < eps:
                return x_next
            x = x_next


if __name__ == "__main__":
    print(f"{Solution().solve():.9f}")

方法 2：二分法

二分法适用于单调区间，我们需要先找到根所在的区间，然后不断缩小范围，直到精度满足要求。

python

def f(x):
    return x ** 3 - 5 * x ** 2 + 10 * x - 80


def binary_search(a, b, tol=1e-9):
    """在区间 [a, b] 内使用二分法找到方程 f(x) = 0 的根"""
    if f(a) * f(b) > 0:
        raise ValueError("二分法要求 f(a) 和 f(b) 符号相反，确保根在区间内")

    while abs(b - a) > tol:
        mid = (a + b) / 2
        if f(mid) == 0:
            return mid
        elif f(mid) * f(a) < 0: # 说明区间内有根
            b = mid
        else:
            a = mid

    return (a + b) / 2 # 根就在这个很小的区间里


# 选择合适的区间（先观察 f(x) 在不同区间的符号变化）
root1 = binary_search(3, 10)
print(f"{root1:.9f}")

比较

方法	适用情况	优点	缺点
二分法	确保有根的区间	一定收敛	需要选区间，收敛较慢
牛顿法	初值合理时	收敛快	需要计算导数，初值不好可能不收敛

M04140: 方程求解 ​

M04140: 方程求解