我们先举例说明一下计算逻辑。对于给定的函数f(x),如果知道f(x)=0在区间[a,b]上有解,是否可以不用解公式,只通过函数的数值计算就可以求出这个解?或者能不能找到一个近似的解?答案是肯定的。我们知道这个问题很有意义,因为在实际问题中,往往无法得到求解公式,只能用近似解代替真解。一般情况下,设这个真解为x0,如果我们找到一个近似解为x*,使得|x*-x0|≤10 -n,我们说x*是精确到10 -n的近似解..我们计算一个具体的例子,从中抽象出一种方法来求近似解。
设函数f(x)=x2+x-1,很容易验证f (0) =-1
第一个近似解是x(1)=(1-0)/2=1/2。因为f (1/2) =-1/4
第二个近似解是x(2)=1/2+(1-1/2)÷2=3/4。因为f (3/4) = 5/16 >: 0,所以解在[1/2,3/4]之间;
第三个近似解是x(3)=1/2+(3/4-1/2)÷2=5/8。因为f (5/8) = 1/64 >: 0,所以解在[1/2,5/8]之间;
第四个近似解是x(4)=1/2+(5/8-1/2)÷2=9/16。因为f(9/16)=-31/256,所以解在[9/16,5/8]之间;
第五个近似解是x(5)=9/16+(5/8-9/16)÷2=19/32。因为f(19/32)=-55/1024,所以解在[19/32,5/8]之间;
第六个近似解是x(6)=19/32+(5/8-19/32)÷2=39/64。因为f(39/64)=-79/4096,所以解在[39/64,5/8]之间;
第七个近似解是x(7)= 39/64+(5/8-39/64)÷2 = 79/128。因为f(79/128)=-31/16384,所以解在[79/128,5/8]之间。
这一计算过程的图示说明见图(1)。
图(1) 二分法的图形解释图(1)二分法的图解解释
大家可以看到,每一个解的过程都是逐渐接近真实解的,所以虽然我们不知道真实解是什么,因为
| x(7)-x0 |≤5/8-79/128 & lt;1/128 & lt;10-2
满足精度要求后,我们可以停止计算,作出如下近似解
x*=x(7) =17/128≈0.617
从上面的计算过程中很容易抽象出求近似解的规律:每个近似解都是前一个区间的中点。所以人们把这种解法叫做二分法,看似笨拙,实则有效,因为二分法的解法简单,可以任意逼近真解,计算的近似精度也很简单。但是我们上面描述的求解方法有一个致命的弱点,就是不知道上一步的计算结果就无法进行下一步的运算。这种方法不能用计算机自动计算,因为本质上这种运算方法还没有形成计算逻辑。那么,如何给出一个既符合上述运算规则,又能让计算机自动计算的计算逻辑呢?我们来详细讨论一下这个问题。
不失一般性,假设定义在区间[a,b]上的连续函数f(x)满足:f (a)
输入f(x),a,b,n。
1.计算c=a+1/2(a+b)
2.如果|c-a|≤10 -n,转到说明7。否则
计算f(c)
4.如果f (c)
5.使b=c
6.返回说明1
7.设x * = C .停。
输出x*。
我们不用正式的计算机语言来表达,因为我们表达的是计算逻辑。虽然计算机使用的语言可以不同,但各种计算机语言遵循的计算逻辑是相同的。可以看出,遵循上述计算逻辑就可以达到我们的目的:在固定和有限步指令的帮助下,实现各种精度要求的各种自动化运算。正是因为这个计算程序的通用性,使得这个计算逻辑的实用性毋庸置疑。其次,如果仔细分析上述逻辑的叙述过程,可以发现这种逻辑叙述不仅要注意基本推理,还要注意系统推理,即注意整个推理过程的句子顺序,如:
使用一个可以连续替换的过渡符号C,每次运算后替换区间的端点A或B,解决了反复迭代运算的问题,也解决了自动运算的问题。
第二条指令是停止操作的指令,在正常操作中似乎是在操作之后,但从系统推理的角度来看,把这条指令作为第二条指令,然后用“否则”转到第三条指令是最合适的。
显然,一个算法的好坏与计算次数有关。在精度相同的要求下,计算次数越少越好(本质上是计算时间越少越好)。如果用m来表示计算次数,那么可以在上面的计算逻辑中添加什么地方、什么样的语句,使计算逻辑自动记录计算次数?我们可以这样设计它:
输入f(x),a,b,n。
1.设m=0
2.m=m+l
3.计算c=a+1/2(a+b)
4.如果|c-a|≤10 -n,转到说明9。否则
5.计算,f(°c)
6.如果f (c)
7.使b=c
8.返回说明2
9.x*=c .停下来。
输出x*,m
在原有计算逻辑的基础上,增加替换符号m来表示计算次数。读者可以自己思考,把计算次数m放在指令1和指令2中。
二分法不仅是一种求解方法,也可用于实验设计。例如,当我们开发一种新的零食时,我们需要确定多少糖是合适的。如果口感好,应该如何确定糖的比例?显然,这是一个无法从理论上推理的问题,只能通过实验得出合适的结果。假设我们已经知道最合适的糖比在区间[a,b]内,f(x)代表糖比为x时的口感评价值,如果评价值越大越好,那么我们的问题就可以转化为求f(x)在[a,b]内的最大值。
因为无法给出f(x)的具体表达式,所以只能通过数值计算来求解。一个最简单的方法,可以取这个区间内的任意点,比如xl,…,xn。在这几个点上做实验,通过尝试可以得到f(x1),…,f(xn),然后取这几个值中的最大值作为最大值的近似值,比如这个近似值就是f( xm),这样就可以在xm附近设定最合适的糖比例。可以想象,只要取足够多的点,就能得到很好的近似。但对于这样一类问题,人们不仅要得到一个近似值,还希望实验的次数越少越好,因为安排实验需要花费金钱和人力。一种简单易行的改进方法是分式法,可以看作是二分法的推广。其实这些方法都和黄金分割有关。
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。