楚水08《算法初步》算法案例3.ppt

楚水实验学校高二数学备课组算法案例算法案例3 3知识回顾：知识回顾：用二分法求方程用二分法求方程 f f( (x x)=0)=0（或（或g g( (x x)=)=h h( (x x) )）近似解的基本步骤）近似解的基本步骤: :1 1、寻找解所在区间、寻找解所在区间（（1））图象法图象法先画出先画出y= f(x)图象，观察图象与图象，观察图象与x轴的交点横坐标所处的范围；轴的交点横坐标所处的范围；或画出或画出y=g(x)和和y=h(x)的图象，观察两图象的交点横坐标的的图象，观察两图象的交点横坐标的范围2））函数法函数法把方程均转换为把方程均转换为 f(x)=0的形式，再利用函数的形式，再利用函数y=f(x)的有关性质的有关性质（如单调性）来判断解所在的区间及解的个数如单调性）来判断解所在的区间及解的个数2 2、不断二分解所在的区间、不断二分解所在的区间若若（（3）若）若 ，，对对(1)、、(2)两种情形再继续二分解所在的两种情形再继续二分解所在的区间区间.（（1）若）若 ，，（（2）若　）若　 ，，由　　　　，由　　　　，则则由　　　　，由　　　　， 则则则则3 3、根据精确度得出近似解、根据精确度得出近似解当当 ，且，且m, n根据精确度得到的近似值均为同根据精确度得到的近似值均为同一个值一个值P时，则时，则x1≈P ，即求得近似解。

即求得近似解 例例1 用二分法求方程用二分法求方程x2－－2x－－1＝＝0的近似解（精确到的近似解（精确到0.1）．）． 首先画出函数首先画出函数f(x)＝＝x2－－2x－－1的图象，从图象上可以发现：的图象，从图象上可以发现： 方程方程x2－－2x－－1＝＝0的一个根的一个根x1在区间在区间(－－1，，0)内，另一个根内，另一个根x2在区间在区间(2，，3)内．内．据函数图象，我们发现：据函数图象，我们发现： f(2)＝－＝－1<0，，f(3)＝＝2>0，即，即f(2)·f(3)<0，，由二次函数的单调性表明图象在区间由二次函数的单调性表明图象在区间(2，，3)内仅内仅穿越穿越x轴一次，即方程在区间轴一次，即方程在区间(2，，3)内有惟一解．内有惟一解．可以将区间一分为二，使包含根的区间长度缩小可以将区间一分为二，使包含根的区间长度缩小下面计算下面计算2，，3的平均值的平均值(以下称之为区间的中点以下称之为区间的中点)2.5所对应的函数值所对应的函数值f(2.5)，并进一步缩小根所在，并进一步缩小根所在的区间．的区间． f(2.5)＝＝0.25>0，即，即f(2)·f(2.5)<0，，故近似解在区间故近似解在区间(2，，2.5)内．内．算法应用案例：算法应用案例： 通过依次取区间中点的方法，将根所在的区间逐步通过依次取区间中点的方法，将根所在的区间逐步缩小，并列出表格：缩小，并列出表格：区区 间间区间中点的值区间中点的值中点对应的函数值中点对应的函数值(2，，3)2.50.25(2，，2.5)2.25－－0.4375(2.25，，2.5)2.375－－0.10938(2.375，，2.5)2.43750.066406(2.375，，2.4375) 直到区间两个端点值精确到直到区间两个端点值精确到0.1时的近似值都是时的近似值都是2.4，，所以方程的一个近似解为所以方程的一个近似解为2.4．．注：由于确定近似值的方法不太方便，因此用计注：由于确定近似值的方法不太方便，因此用计算机实现二分法时，常常不是给出精度，而是给算机实现二分法时，常常不是给出精度，而是给出误差范围！出误差范围！问题：如果方程问题：如果方程f(x)＝＝0在某区间在某区间[a，，b]内有一个根，如何利用二分内有一个根，如何利用二分法搜索符合误差限制法搜索符合误差限制c的近似解？的近似解？ S1 取取[a，，b]的中点的中点 x0＝＝ ，将区间一分为二；，将区间一分为二；S2 若若f(x0)＝＝0，则，则x0就是方程的根，转就是方程的根，转S4, 否则当否则当f(a)·f(x0)<0，则，则x∈∈(a, x0)，用，用x0代替代替b, 否则用否则用x0代替代替a；；S3 若若|a－－b|不小于不小于c，转，转S1；； S4 输出输出x0 . 问题：写出用区间二分法求方程问题：写出用区间二分法求方程x3－－x－－1＝＝0在区间在区间[1,1.5]内的一个近似解（误差不超过内的一个近似解（误差不超过0.001）的一个算法．）的一个算法． a1 b1.5 c0.001 Do x0( (a＋＋b)/)/2 f( (a) )a3－－a－－1 f( (x0) )x03－－x0－－1 If f( (x0) )＝＝0 Then End Do If f( (a) )f( (x0) ) ＜＜0 Then bx0 Else ax0 End If Until | Until |a－－b| |＜＜c End Do P Print x0 若是若是,则则m为所求为所求; 探究探究:画出用二分法求方程画出用二分法求方程x2-2=0的近似根的近似根(精确精确度为度为0.005)的程序框图的程序框图.算法分析算法分析:第一步第一步:令令f(x)=x2-2.因为因为f(1)<0,f(2)>0,所以设所以设a=1,b=2.第二步第二步:令令判断判断f(m)是否为是否为0.若否若否,则继续判断则继续判断f(a) (m)大于大于0还是小于还是小于0.第三步第三步:若若f(a) (m)>0,则令则令a=m;否则否则,令令b=m. 第四步第四步:判断判断|a-b|<ε是否成立是否成立?若是若是,则则a或或b为满为满足条件的近似根足条件的近似根;若否若否,则返回第二步则返回第二步. 否否是是是是否否f(a) f(m)>0?程序框图程序框图开始开始f(x)←x2-2输入精确度输入精确度ε和初值和初值a,bf(m)=0?a m否否b m|a-b|<ε?122输出输出a和和b结束结束输出输出m313是是例例2 编写一个求编写一个求 的近似值的算法，要求精确度不超过的近似值的算法，要求精确度不超过0.0001，写出其伪代码，写出其伪代码.分析：转化为求方程的近似解问题分析：转化为求方程的近似解问题.。