算法原理和步骤详解-实用计算方法原理及算法实现

设非线性方程f(x) = 0 在区间[a, b]上连续，如果 f ( a ) f (b ) ＜ 0，则f(x)在[a, b]内至少有一个零点。将区间[a, b]二等分，计算其中点c = (a+b)/2 的函数值f(c)，如果f(c) = 0，则c 为方程的根；如果 f ( a ) f ( c ) ＜ 0，则区间[a, c]包含方程的根；否则，方程的根在区间[c, b]内。将包含方程根的区间仍记为[a, b]，再将其二等分，并计算其中点c = (a+b)/2 的函数值f(c)，重复前面的判断。该过程每进行一次，解区间就缩小为原来的一半，重复此过程，直到区间长度缩小到指定的精度。二分法求解非线性方程根的过程如图1.1 所示。

图1.1　二分法求解过程

二分法是一种逐步搜索算法，其全局收敛，但收敛速度较慢。

用二分法求解非线性方程f(x)的算法步骤如下：

步骤1：输入有根区间端点a 和b、解精度E1 和方程精度E2、最大迭代次数M。

步骤2：计算f(x)在区间[a, b]端点处的函数值f(a)和f(b)。(https://www.xing528.com)

步骤3：若| f ( a)|＜ E2或| f (b )|＜ E2，则输出a 或b，计算结束；否则，往下进行。

对于K = 1, 2, …, M，执行步骤4 至步骤6。

步骤4：计算f(x)在区间中点c = (a+b)/2 处的值f(c)。

步骤5：若|f(c)|＜E2，则输出c，计算结束；若f(c)f(a)＜0，则方程的根在区间[a, c]内，令b = c，f(b) = f(c)；否则，方程的根在区间[c, b]内，令a = c，f(a) = f(c)。

步骤6：若区间长度|b-a|＜E1，输出(a+b)/2，计算结束。

步骤7：输出“二分法已迭代M 次，没有得到符合要求的解”，停止计算。