12065: 方程求解

binary search, http://cs101.openjudge.cn/practice/12065

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

输入

输出

精确到小数点后9位。

解题思路：对 $f (x)$ 求导，得到 $f^{'} (x) = 3 x^{2} - 10 x + 10$ 。由一元二次方程求根公式可知方程 $f^{'} (x)$ 无解，因此 $f^{'} (x) > 0$ 恒成立，一元三次方程 $f (x)$ 关于 $x$ 是单调递增的，且 $f (0) = - 80 < 0$ 而 $f (10) = 520 > 0$ ，则根必在 $[0, 10]$ 之间，由于 $f (x)$ 在 $[0, 10]$ 内是单调递增的，所以可以用二分查找的办法在区间中寻找根。

由此可以看出二分查找的一个应用：难以求解或者无法直接求解的方程求根问题，首先求其范围，再进一步缩小范围，逼近要求的解。二分查找的好处是每次二分都将查找的范围缩小一半。

2020fall-cs101，苏荣薰。

解题思路：找到一个整数区间[a,b]，使 f(a)f(b)<0，便可由零点存在定理知[a,b]内存在 f(x)=0的一个解。然后不断二分区间套用上述方法，直到所得到的解足够要求的精度。做的时候想不到判断精度够不够的方法，上网找了恍然大悟可以用区间长度来判断，如果比要求精度小就说明已经达到所求精度。

2020fall-cs101，胡新越

python

left = 0
right = 10
eps = 1e-12

func = lambda x:x**3 - 5*(x**2) + 10*x - 80
while right - left > eps:
    mid = (left + right)/2
    if func(mid) > 0:
    	right = mid
    else:
    	left = mid
print(format(right, ".9f"))

终止，逼近0，就是小于一个很小的数。

python

left = 0
right = 10
e = 1e-12

f = lambda x:x**3 - 5*(x**2) + 10*x - 80
while True:
    x = (left + right)/2  
    y = f(x)
    
    if abs(y) < e:
        print('{:.9f}'.format(x))
        break
    
    if y < 0:
        left = x
    elif y>0:
        right = x

2020fall-cs101，施惟明。迭代法

python

def f(x):
    return x*x*x-5*x*x+10*x-80
def ff(x):
    return 3*x*x-10*x+10
x =0
x0 = -10000
while abs(x-x0) > 1e-10:
    x0 = x
    x = x - f(x)/ff(x)

print('%.9f' % x)

2020fall-cs101，李博海

其实我这个不是二分搜索，是“迭代法”，这种解方程方法来源于以前的计算器实用技巧（甚至可以解多元任意方程组），时间复杂度未知，且迭代能否收敛看天。

python

prex, x = 0, 5
while abs(x - prex) > 1e-11:
    prex = x
    x = (5*prex*prex - 10*prex + 80) ** (1/3)

print('{:.9f}'.format(x))

2020fall-cs101，阚立言。

用了大概一个小时多，写了一个使用牛顿法解方程的函数，可以解任意多项式方程，改一下代码用exec()，放进去math库或许还能解超越方程。输入表达式，初值，步长即可求解。受限于方法，一次只能求一个解。但是这个人工求导精度很差，不过通常够用了。

讨论：二分法对于初值是有要求的，如果零点不在区间内会error，但是二分法的好处精度可控，说精确到九位就是九位，而且精度可以做到最好。

牛顿法好在无论多么离谱的初值都能给算出解来，而且速度一般比二分法快，但是因为手动涉及到小量的除法，精度就不好说了（设置收敛半径过小可能出现死循环）。

不过综合各种因素看，还是牛顿法更加普适些。

python

# Newton's method
def solve():
    global a
    #c = input()
    c = "x**3-5*x**2+10*x-80"
    #a = float(input())
    a = 4.0
    
    def f(x):
        return eval(c)
    
    def df(x,dx):
        return (f(x+dx)-f(x))/dx
    
    while abs(f(a)) >1e-10:
        if df(a,1e-10) == 0:
            a -= 1e-10
        else:
            a = a-f(a)/df(a,1e-10)
    return a

ans = solve()
print("{:.9f}".format(ans))

12065: 方程求解 ​

12065: 方程求解