牛顿迭代、割线法、二分法算法实验报告.docx
6页
数值分析作业[键入文档副标题]20123789 黄佳诚2014/11/25摘要本文分别采用了“二分法” 、 “牛顿法” 、 “割线法” 、3 种方法讨论如何求解方程“ ”，描述了每个算法的算法思想，给出了计算结果与迭代时𝑥3‒9=0间以及每一步迭代结果和解的精度，并且用多项式拟合了不同算法的时间复杂度函数进行收敛性和时间复杂度分析比较了的优劣在最后报告给出了其他可供使用的求根方法例如， “简易牛顿算法” 、Steffensenf 迭代法并对它的思想和计算流程进行了简单的介绍关键词：二分法 牛顿法 割线法 简易牛顿法 Steffensenf 迭代法一、计算机配置操作系统：windows7 旗舰版处理器：Intel(R) Core(TM) i5-3210M CPU@2.50GHz 安装内存（RAM）：4.00GB(2.91GB 可用)系统类型：32 位操作系统二、二分法计算实验2.1 二分法算法思想和简要描述若 f 是区间[a,b] 上的连续函数，且 f(a)f(b)> erfen(f,2,3,50,0.001,0.001)n a b delta alpha 1.0000 2.0000 2.5000 0.5000 19.00002.0000 2.0000 2.2500 0.2500 7.62503.0000 2.0000 2.1250 0.1250 3.3906 4.0000 2.0625 2.1250 0.0625 1.59575.0000 2.0625 2.0938 0.0313 0.82206.0000 2.0781 2.0938 0.0156 0.40497.0000 2.0781 2.0859 0.0078 0.20408.0000 2.0781 2.0820 0.0039 0.10169.0000 2.0801 2.0820 0.0020 0.050710.0000 2.0801 2.0811 0.0010 0.025411.0000 2.0801 2.0806 0.0005 0.012712.0000 2.0801 2.0803 0.0002 0.006313.0000 2.0801 2.0802 0.0001 0.003214.0000 2.0801 2.0801 0.0001 0.0016elapsed time is 0.316426 seconds.三、牛顿法计算实验3.1 牛顿法算法思想和简要描述我们有一个函数 f，其零点由数值计算得出，设 r 是 f 的一个零点，x 是 r 的一个近似。
若 f 的二阶导数存在并且连续，则有泰勒定理，得0=f(r)=f(x+h)=f(x)+hf’(x)+o(h^2)其中 h=r-x若 h 较小（即 x 在 r 附近） ，则有理由略去 o(h^2)项并且在余下方程中求 h即得到 h=-f(x)/f’(x)故 x-f(x)/f’(x)是比 x 更好的一个近似牛顿法从 r 的一个估计 x0 开始，得到更加准确的近似值 xn递推式定义为：𝑥𝑛+1=𝑥𝑛‒𝑓(𝑥𝑛)𝑓'(𝑥𝑛)3.2 MATLAB 运行牛顿法程序牛顿法求解 f=x^3-9 的根参数设置：x0 设置为函数 f 零点的近似n 设置为牛顿法 for 语句迭代次数alpha 设置为最后结果 f(x)的精度delta 设置为最后结果 x 的精度若 alpha，delta 都符合设置的计算精度时，结束迭代并得出计算结果，否则一直迭代到 n 次）设置初始值：设置参数 x0 分别为为 3；迭代次数 n 为 50 次；alpha 和delta 都设置为 0.001列出计算结果：>> newton(f,50,3,0.001,0.001)n x f(x) delta alpha1.0000 2.3333 3.7037 0.6667 3.70372.0000 2.1066 0.3483 0.2268 0.34833.0000 2.0804 0.0043 0.0262 0.0043Elapsed time is 0.166680 seconds.四、割线法计算实验4.1 割线法算法思想和简要描述割线法思路总体上与牛顿法一致，但是为了避免牛顿法中求函数导数所带来的困难，用差商来近似的代替导数得到了割线法近似值的递推式：𝑥𝑛+1=𝑥𝑛‒ 𝑥𝑛‒𝑥𝑛‒1𝑓(𝑥𝑛)‒𝑓(𝑥𝑛‒1)因为 的计算需要 和 ，所以开始时需要两个初始点。
𝑥𝑛+1 𝑥𝑛 𝑥𝑛‒14.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 alpha1 3 1 372.0000 2.5135 0.4865 11.12023.0000 2.2125 0.3010 5.04864.0000 2.1034 0.1092 1.52545.0000 2.0815 0.0219 0.28746.0000 2.0801 0.0014 0.0181Elapsed 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 的不断增大，各算法所耗费时间的变化趋势，得到如下函数图像：二分法的渐进时间复杂度函数图像牛顿法的渐进时间复杂度函数图像割线法的渐进时间复杂度的函数图像从三种算法的渐进时间复杂度函数图像容易看出，随着 n 的不断增大是图像大致呈线性变化，说明了每次迭代所进行的计算量都是大致相当的，可以认为是三种算法都是稳定的图像也反映出二分法的计算时间明显大于另外两种算法，这是由于二分法每一个循环语句内都要进行求 f(a),f(b),f(a)*f(b),(a+b)/2 四次计算计算量大于其他两种算法；牛顿法相较于割线法虽然收敛速得更快，但每次迭代都要重新计算 f(x 和 f’(x)，相比于割线法每次只需计算一个 f(x)，计算量要稍大一些，所以每次迭代耗时更多。
六、其他可供使用的算法6.1 简易牛顿法算法思想简述简易牛顿法即将 1()kkfxx中的 换成一个常数 ,迭代公式为()kfx M1()kkfxx6.2 Steffensenf 迭代法算法思想简述假设我们要解方程 ，这个方法的迭代公式是()xg， ，)kkyx()kzgy， 21(kkk0,123.。
