一维搜索之割线法（函数逼近法）

算法目的

  得到近似的极小点。

算法步骤

1. 给定初始点$x^{(0)}$x(0)，允许误差$\epsilon >0$ϵ>0，置$k=0$k=0；
2. 若$|f'(x^{(k)})| < \epsilon$∣f′(x(k))∣<ϵ，则停止迭代，得到点$x^{(k)}$x(k)；
3. 计算点$x^{(k+1)}$x(k+1)，$x^{(k+1)}=x^{(k)}-\frac{x^{(k)}-x^{(k-1})}{f'(x^{(k)})-f'(x^{(k-1)})}f'(x^{(k)})，$x(k+1)=x(k)−f′(x(k))−f′(x(k−1))x(k)−x(k−1)​f′(x(k))，置$k:=k+1$k:=k+1，转到步骤2）。

例题

  求解：$\min 3x^4-4x^3-12x^2，$min3x4−4x3−12x2，
取初始点$x^{(1)}=-1.2,\ x^{(2)}=-0.8$x(1)=−1.2, x(2)=−0.8。

import numpy as np
import time
from prettytable import PrettyTable


# 割线法
def default_func_secant1(x):
    return 12 * ((x ** 3) - (x ** 2) - 2 * x)


def secant(func1=default_func_secant1, x1=np.array([-1.2]), x2=np.array([-0.8]), max_iteration=7):
    start = time.perf_counter()
    table = PrettyTable(['k', 'xk', "f'(xk)"])
    table.add_row([1, x1, func1(x1)])
    table.add_row([2, x2, func1(x2)])
    x_km1, x_k, k = x1, x2, 0
    while k <= max_iteration:
        k += 1
        f_km1, f_k = func1(x_km1), func1(x_k)
        if f_km1 == f_k:
            print('在第', k, "次迭代中出现f'[x(k)]=f'[x(k-1)]的情况,程序停止迭代")
            return
        x_kp1 = x_k - (x_k - x_km1) * f_k / (f_k - f_km1)
        table.add_row([k + 2, x_kp1, func1(x_kp1)])
        x_km1, x_k = x_k, x_kp1
    end = time.perf_counter()
    print(table)
    print('Elapsed time', end - start, 's')


secant()

  结果：

+----+---------------+-------------------+
| k  |       xk      |       f'(xk)      |
+----+---------------+-------------------+
| 1  |     [-1.2]    |      [-9.216]     |
| 2  |     [-0.8]    |      [5.376]      |
| 3  | [-0.94736842] |    [1.76352238]   |
| 4  | [-1.01931005] |   [-0.71314618]   |
| 5  | [-0.99859476] |    [0.05049386]   |
| 6  | [-0.99996451] |    [0.00127761]   |
| 7  | [-1.00000007] | [-2.39765441e-06] |
| 8  |     [-1.]     |  [1.13463905e-10] |
| 9  |     [-1.]     |        [0.]       |
| 10 |     [-1.]     |        [0.]       |
+----+---------------+-------------------+
Elapsed time 0.00031288800000006667 s