迭代法求解方程的根

求解方程的根，即$f(x)=0$的数值解等问题，对于经典的二次方程等函数我们可以直接进行求解，但是对于超越方程我们不能用常规方法进行求解。因此我们可以通过使用计算机实现某些求解算法进行计算。

选取样例

$f(x) =x^3 - x - 2$

$\frac{dy}{dx} = 3x^2-1$

求解$f(x)$在[1, 2]上的零点

二分法

在高中数学课本我们就接触过二分法求函数零点，根据零点存在性定理，可以保证我们得到符合要求的一个根，但是该方法局限性太大，只能求解区间内的一个根。

大致流程如下

先确定要求解的区间[x, y]，然后不断对区间进行二分，根据精度要求判断根是否合法，再根据中点值与端点值的符号是否相同缩小二分范围。

$if \ f(mid)\times f(l) > 0$

$let \ l = mid$

$or \ r = mid$

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


import numpy as np
import math as m

def f(x):
    return x**3-x-2

def binary(x, y):
    res = 0
    eps = 1e-3
    h = 1e-3
    l = x
    r = y
    while l <= r:
        mid = (l+r)/2
        if abs(f(mid)-0) < eps:
            return mid
        if f(mid)*f(x) > 0:
            l = mid
        else:
            r = mid
    return -1

answer = binary(1.0, 2.0)
print(np.around(answer, 4))

运算结果为1.5215

牛顿迭代法

牛顿迭代法的基本思想为将非线性方程线性化，选取一个初始点，做切线交与x轴一点，然后继续该操作，直到根收敛或者达到精度要求。

基本流程为

取任意的迭代初始值$x_0$
计算 $x_1 = x_0 - \frac{f(x_0)}{f’(x_0)}$
判断收敛性：如果$|x_1 - x_0|< \epsilon \ or |f(x_1)-0| < \epsilon$
令$x_0 = x_1$，保存上一步结果，继续迭代

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


import numpy as np
import math as m

# f(x) = x**3 - x - 2
# df/dx = 3x**2 -1

def df(x):
    return 3*x**2 - 1

def f(x):
    return x**3 - x - 2

def newton(x):
    eps = 1e-7
    x0 = x
    x1 = x0 - f(x0)/df(x0)
    while abs(x1-x0) > eps:
        t = x1
        x1 = t - f(t)/df(t)
        x0 = t
    return x1

answer = newton(1.0)
print(np.around(answer, 4))

运算结果为1.5214

方程求根的迭代法

迭代法求解方程的根

二分法

牛顿迭代法