牛顿迭代、割线法、二分法算法实验报告(4)

MATLAB实现的用二分法,割线法,牛顿迭代法求解方程的根的实验报告

4.1 割线法算法思想和简要描述

割线法思路总体上与牛顿法一致，但是为了避免牛顿法中求函数导数所带来的困难，用差商来近似的代替导数得到了割线法近似值的递推式： xn xn 1xn+1=xn nn 1因为xn+1的计算需要xn和xn 1，所以开始时需要两个初始点。

4.2 MATLAB运行割线法程序

割线法求解f=x^3-9的根

参数设置：a,b设置为函数f零点的两个近似值。

n设置为牛顿法for语句迭代次数。

alpha设置为最后结果f(x)的精度。

delta设置为最后结果x的精度。

（若alpha，delta都符合设置的计算精度时，结束迭代并得

出计算结果，否则一直迭代到n次）

设置初始值：设置参数a,b分别为为3,4；迭代次数n为50次；alpha

和delta都设置为0.001。

列出计算结果：

>> gexian(f,3,4,50,0.001,0.001)

n x0 delta alpha

1 3 1 37

2.0000 2.5135 0.4865 11.1202

3.0000 2.2125 0.3010 5.0486

4.0000 2.1034 0.1092 1.5254

5.0000 2.0815 0.0219 0.2874

6.0000 2.0801 0.0014 0.0181

Elapsed time is 0.080747 seconds.

五、收敛性和时间复杂度分析

5.1 三种算法的收敛性分析

从理论上来看，二分法每次估计的范围都是前一次迭代时（a,b）区间的1/2，所以要达到千分位的精度至少应该进行10次左右的迭代；而牛顿法的收敛速度是最快的；割线法把牛顿算法中的导函数用插商代替造成了一定的误差，故收敛速度稍慢于牛顿迭代。

从实验结果来看，结果也与理论上的判断相符，在实验精度取0.001的情况下，二分法迭代次数最多，进行了14次迭代；牛顿迭代算法的次数最少，只进行了3次迭代就到达了0.001位的精度要求；割线迭代法相对于牛顿算法的迭代次数要稍多一点，进行了6次迭代。

5.2 三种算法的时间复杂度分析

我们用迭代次数n来反映算法的要解决问题的规模并作为自变量，用tic toc函数记录每次迭代所花费的时间，记录随着n的不断增大，各算法所耗费时间的变化趋势，得到如下函数图像：

二分法的渐进时间复杂度函数图像