数值分析第一次实验

学生学号实验课成绩武汉理工大学学生实验报告书实验课程名称：数值分析开课名称：计算机科学与技术学院指导老师姓名：熊盛武学生姓名：学生专业班级：2009——2010学年第一学期一、实习目的：（1）、通过编程计算实践，体会和理解二分法、简单迭代法、Newton迭代法和弦截法的算法思想。（2）、通过编程计算实践，熟练各种算法的计算流程。（3）、通过各种方法对同一问题的求解，体会各种方法的精度差异。（4）、通过编程计算实践，深入领会和掌握迭代算法的改进思路，提高对算法改进技巧的本质的认识以及算法流程的实际控制技术。二、实习步骤和内容：（1）、分别画出二分法，简单迭代法，牛顿迭代法和弦截法的算法流程图。（2）、分别画出二分法和简单迭代法通过编程计算x*x*x-x-1=0在[1,2]内的近似根，要求精度达到0.0001和0.00001，并给出二分法和迭代的次数，分析和比较算法的效率差异，和精度差异，最后与理论估计的二分和迭代次数作比较。（3）、用Aitken算法通过编程计算x*x*x-x-1=0在[1,2]内的近似根，要求精度达到0.0001，并分析算法精度与二分法的结果进行比较。（4）、分别用牛顿迭代法和弦截法通过编程计算x*x*x-x-1=0在[1,2]内的近似根，要求精度达到0.00001，并分析算法及不同方法的计算量。然后将程序应用于以下方程求根（1）.x=(2-e^x+x*x)/3（2）3*x*x-e^x=0。分析和比较算法的效率差异：收敛速度和总计算量等之间的关系。三、算法流程图：（1）、二分法计算流程图：b-aeb=xa=xf(a)f(x)0i++x=(a+b)/2t=(a+b)/2输出近似根t，循环次数i结束方程x*x*x-x-1=0开始b-ae求根区间[a,b]循环次数i,i=0否是是否是否（2）、简单迭代法算法流程图：开始定义函数s(t)=t+1方程x*x*x-x-1=0输入迭代初始值x0,控制精度e.迭代次数i，i=0x1=pow(s(x0),1.0/3.0);fabs(x1-x0)ei++;x1=pow(s(x0),1.0/3.0);x0=x1;x1=pow(s(x0),1.0/3.0);fabs(x1-x0)eex=(x1+x0)/2输出近似根x,迭代次数i结束否是是否（3）、Aitken算法程序流程图：开始定义函数s(t)=t*t*t-1输入迭代初始值x0,控制精度e,循环次数I,i=0fabs(x0*x0*x0-x0-1)ei++;x1=s(x0);x2=s(x1);x0=x2-(x2-x1)*(x2-x1)/(x2-2*x1+pow((x1+1),1.0/3.0));x=x0;输出近似根x迭代次数e结束fabs(x0*x0*x0-x0-1)e否是是否（4）、牛顿迭代法流程图：开始定义函数s(t)=t-(t*t*t-t-1)/(3*t*t-1)迭代初始值x0,控制精度e，迭代次数i,i=0x1=x0fabs(s(x1)-x1)ei++;x2=s(x1);x1=x2;输出近似根x,迭代次数ix=(x1+x2)/2;结束fabs(s(x1)-x1)e否是是否二分法算法描述：（1）、程序开始（2）、输入求根区间[a,b]和精度控制量e,方程x*x*x-x-1=0。循环变量i=0（3）、判断b-ae是否成立，若成立执行下面的操作，若不成立，程序结束。（4）、计算中值点x=(a+b)/2及f(x)的值,i++当f(a)*f(x)0时：b=x,得到新的求根区间[a,b]当f(a)*f(x)0时：a=x，得到新的求根区间[a,b]（5）、判断b-ae是否成立，若成立返回步骤4，若不成立，往下执行。（6）、t=(a+b)/2（7）、输出近似根t,循环次数i（8）、程序结束二分法程序源代码：#includeiostream#includecmath#definef(x)(x*x*x-x-1)usingnamespacestd;intmain(){inti;floatx,t,a,b,e;cout请输入求根区间a,b控制变量eendl;cinabe;i=0;while((b-a)e){i++;x=(a+b)/2;if(f(a)*f(x)0)b=x;if(f(a)*f(x)0)a=x;}t=(a+b)/2;cout在求根区间a,b间近似根t=tendl;cout所需二分法次数i=iendl;return0;}调试过程，实验结果及分析：计算x*x*x-x-1=0在[1,2]内的近似根。精度达到0.0001时，程序运行结果如下图：当精度达到0.00001时，程序运行如下图：调试过程中如果把while((b-a)e)改为while((b-a)e),算然会出现程序运行之后的界面，但是输出的近似根是1.5，迭代次数i=0,也就是说程序的循环体没有执行，这是因为求根呢区间远远大于精度。从而跳过循环体直接输出前面输入的数据。由运行结果看出：精度达到0.0001时，二分法次数为14。精度达到0.00001时，二分法次数为17。精度要求越高，二分法次数越多。二分法缺点：逼近速度较慢。二分法对有根区间逐步逼近得到更精确的近似根，二分法不采用等步长扫描，而是在有根区间[a,b]中，取中点，然后计算中点值，判断中点对应函数值和端点函数值乘积的正负来确定新的端点，当有根区间长度小于精确度时得到近似根。如果没有区间长度和精度大小的判断，程序是一个死程序，得不到近似根。简单迭代法算法描述：（1）、定义函数s=(t+1)（2）、输入迭代初始值x0.控制变量e（3）、判断fabs(x1-x0)e（4）、当判别式成立时，执行下面程序，当判别式不成立时，程序结束。（5）、i++;x1=pow(s(x0),1.0/3.0);x0=x1;x1=pow(s(x0),1.0/3.0);（6）、判断fabs(x1-x0)e（7）、当判别式成立时，返回到步骤5，当判别式不成立时，往下执行。（8）、输出近似根x迭代次数i（9）、程序结束。简单迭代法程序源代码：#includeiostream#includecmathdoubles(doublet){return(t+1);}usingnamespacestd;intmain(){inti;doublex,x0,x1,e;cout请输入迭代初始值x0,和控制精度eendl;cinx0e;i=0;while(fabs(x1-x0)e){i++;x1=pow(s(x0),1.0/3.0);x0=x1;x1=pow(s(x0),1.0/3.0);}x=(x1+x0)/2;cout近似根x=xendl;cout所需迭代次数i=iendl;return0;}调试过程，实验结果及分析：计算x*x*x-x-1=0在[1,2]内的近似根。精度达到0.0001时，程序运行结果如下图：当精度达到0.00001时，程序运行如下图：当循环体程序代码如下：x1=pow(s(x0),1/3);x0=x1;x1=pow(s(x0),1/3);时会出现程序运行结果的界面，但是输出的近似根是1，迭代次数是1，这是因为x1=pow(s(x0),1/3)与三次求根函数式的数据类型不符。导致x1=pow(s(x0),1/3)不再是三次求根的函数式由运行结果看出：精度达到0.0001时，简单迭代法迭代次数为5.精度达到0.00001时，简单迭代法迭代次数为6。精度要求越高，简单迭代法迭代次数越多。简单迭代法归结于找直线和曲线的交点的横坐标，其中迭代法的效果并不是总能令人满意的。例如：该程序中简单迭代法另一种等价形式x=x*x*x-1对此建立迭代公式：x(k+1)=x(k)*x(k)*x(k)-1迭代初始值x0=1.5，则有x1=2.375,x2=12.39.继续迭代下去已经没有必要了，为结果显然会越来越大，不可能区域某个极限。这种不收敛的迭代过程是发散的，一个发散的迭代过程，显然其结果是毫无价值的。二分法和简单迭代法比较：当精度都是0.0001，所求结果为：1.32474时，简单迭代法迭代次数比二分法少9次，当精度都是0.00001，所求结果都为：1.32472时，简单迭代法迭代次数比二分法少11次。简单迭代法逼近速度比二分法好，计算的效率比二分法提高了很多精度要求越高，简单迭代法的优势也越明显。二分法不能用于求偶数重根和复根，多用于为其他求根方法提供初始近似值。简单迭代法的迭代过程可能是收敛的也可能是发散的，简单迭代法对迭代公式有要求，迭代公式必须是收敛的，即结果逐渐趋近于某个极限。Aitken算法程序算法描述：1.程序开始2.定义函数s(t)=t*t*t-13.输入迭代初始值x0,控制精度e判断fabs(x0*x0*x0-x0-1)e判别式，若成立，执行下面操作，若不成立，程序结束4.i++;x1=s(x0);x2=s(x1);x0=x2-(x2-x1)*(x2-x1)/(x2-2*x1+pow((x1+1),1.0/3.0));5判断fabs(x0*x0*x0-x0-1)e判别式，若成立，返回步骤4，若不成立，往下执行。6.x=x0;7输出近似根x迭代次数i8程序结束Aitken算法程序源代码：#includeiostream#includecmathdoubles(doublet){return(t*t*t-1);}usingnamespacestd;intmain(){inti;doublex,x0,x1,x2,e;cout请输入迭代初始值x0,和控制精度eendl;cinx0e;i=0;while(fabs(x0*x0*x0-x0-1)e){i++;x1=s(x0);x2=s(x1);x0=x2-(x2-x1)*(x2-x1)/(x2-2*x1+pow((x1+1),1.0/3.0));}x=x0;cout近似根x=xendl;cout所需迭代次数i=iendl;return0;}调试过程，实验结果及分析：计算x*x*x-x-1=0在[1,2]内的近似根。精度达到0.0001时，程序运行结果如下图：当将x=x0;改成x=x1，输出结果近似根为1.32517，迭代次数为5，这与要求得到的试验结果1.32472有一些差距，这是有循环语句i++;x1=s(x0);x2=s(x1);x0=x2-(x2-x1)*(x2-x1)/(x2-2*x1+pow((x1+1),1.0/3.0));执行顺序决定的近似根式子应该是x=x0;由运行结果看出：精度达到0.0001时，Aitken迭代法迭代次数为5.Aitken迭代法是将迭代值在迭代一次，此时对于发散的x(k+1)=x(k)*x(k)*x(k)-1迭代公式，经过Aitken迭代法处理后却获得了相当好的收敛性。Aitken迭代法和二分法的比较：当精度都是0.0001时，Aitken迭代法迭代次数为5.，比二分法少9次，而且Aitken迭代法所求出的近似根为：1，32472，更接近理想值，Aitken迭代法是将迭代值在迭代一次从迭代次数和所求根的差异上可以看出Aitken迭代法是一种加速迭代法。牛顿迭代法程序算法描述：（1）、程序开始（2）、定义函数s(t)=t-(t*t*t-t-1)/(3*t*t-1)（3）、输入迭代初始值x0,控制进度e（4）、x=(x1+x2)/2;（5）、判断判别式fabs(s(x1)-x1)e是否成立，若成立，执行下面操作，若不成立，程序结束。（6）、.i++;x2=s(x1);x1=x2;（7）、判断判别式fabs(s(x1)-x1)e.是否成立，若成立，返回操作5，若不成立，往下执行。（8）、x=(x1+x2)/2;（9）、输出近似根x,迭代次数i（10）、程序结束牛顿迭代法程序源代码：#includeiostream#includecmathdoubles(doub