发布时间 : 星期二 文章数学与应用数学毕业论文设计计算机科学中的重要数学思想—迭代更新完毕开始阅读051576c09e3143323968939e
第三章 二分法
3.1 波尔查诺二分法 先介绍连续函数的零点
定义3.1 设f(x)是连续函数。满足f(r)?0的任意
r成为方程f(x)?0的
一个根。也称r为函数f(x)的零点
二分法是将连续函数的区间进行对分取舍,从而逐步逼近到零点,直到一个任意小
的包含零点的间隔 定理3.1 设f(x)?C(a,b),且存在实数r?[a,b]满足f(r)?0。如果f(a)与
f(b)的符号相反,且?cn?n?0表示二分法生成的中点序列,则
?b?ar?cn?n?1 其中n=0,1?
2cn?r 这样,序列?cn?n?0收敛到零点x?r即可表示为limn?? 证明:由于零点r和中点cn都位于区间?an,bn?内,cn与r之间的距离不
会比这个区间的一半宽度范围大。这样,对于所有的n,
r?cn?bn?an2?,观察连续的区间宽度范围,可得到
b1-a1=(b0-a0)/2 b2-a2=(b0-a0)/4,使用数学归纳法很容易得证
b0?a0bn?an?2n 综上可得证
,结合上面的式子,我们有r?cn?bn?an2n?1
?cn?n?0收敛到r,定理得证。
f(x)?xsinx?1的零点,区间为[0,2].
? 例题:利用二分法寻找函数
解:起始值a0=0,b0=2.计算f(0)=-1 f(2)=0.818595 所以f(x)的一个根位于[0,2]内在中点C0=1,可发现f(1)
=-0.158529,因此区间改变为[C0,b0]=[1,2], 接下来从左边压缩,使得a1=c0 b1=b0. 中点为c1=1.5??????
- 8 -
按照这种方法,可得到序列?ck?,他收敛于r?1.11415714
3.2 试值法的收敛性
下面探讨试值法又叫试位法。试值法是对二分法的改造,使收敛速度变快。
与上述条件一样,假设f(a)和f(b)符号相反,如果找到经过点(a,f(a))和,则可得到一个更好的近似值。为了(b,f(b))的割线L与x轴的交点(c,0)
寻找值x,定义了线L的斜率m的的两种表示方法,一种为:m?另一种方法为:m?于是我们有
0?f(b) c?bf(b)?f(a)
b?af(b)(b?a)f(b)?f(a)0?f(b)= 所以c?b?,这样
f(b)?f(a)b?ac?b如果f(a)和f(c)符号相反,则在[a,c]内有一个零点 如果f(b)和f(c)符号相反,则在[c,b]内有一个零点 如果f(c)=0 ,则c是零点
结合上述过程可构造{[an,bn]}区间序列,其中每个序列包涵零点。在每一
步中,零点r的近似值为
f(bn)b(n?an)cn?bn?f(bn)?fa(n,)
而且可以证明序列?cn?将收敛到r
下面我们来用试值法求解xsinx?1?0,在区间[0,2]中,并观察它是否比二分法收敛得快
解:根据初始值a0?0和b0?2,可得到f(0)=-1 f(2)=0.81859485,因此在区间中有一个根。利用试值法,可得到:c0?2?f(c0)??0.0200。19 210.81859485(2?0)?1.09975017
0.81859485?(?1)- 9 -
函数在区间?c0,b0??[1.09975017,2]内改变符号,因此从左边压缩,设
a1?c0,b1?b0,根据上面结论可得到下一个近似值c1=1.12124074和f(c1)?0.00983461,
下一个判定从右边压缩,设a2?a1,b2?c1??
我们可以得到通过4次运算,就能算出r?1.11415714 通过计算我们可以看到试值法比二分法收敛速度快.
- 10 -
第四章 牛顿-拉夫森法与割线法
4.1 求根的斜率法
如果f(x),f?(x),f??(x)在根p附近连续,则可将它作为f(x)的特性,用于开发产生收敛到根p的序列{pk}的算法。而且这种算法比二分法和试值法产生的序列的速度快,牛顿—拉夫森法是这类方法中最好的方法之一
设初始值p0在根P附近。则函数y=f(x)的图形与x轴相交于点(p,0),而且点?p0,f(p0)?位于靠近点(p,0)的曲线上,将p1定义为曲线在点?p0,f(p0)?的切线与x轴的交点,通过下图的显示可以看出p1比p0更靠近于p,写出切线L的两种表达式,则可得到p0与p1的相关方程,如下所示:
m?0?f(p0)f(p0)?f?(p0) 解出p1?p0?。重复上述过程可得到序列{pk}收敛
f?(p0)p1?p0到p
y
p p1 p0 x p2 O (p1,f(p1)) ?p0,f(p0)?
定理 4.1 设f?C2[a,b],且存在数p?[a,b],满足f(p)?0。如果f?(p)?0,则存在一个数??0。对任意初始近似值p0?[p??,p??],使得由如下迭代定义
?{p}的序列kk?0收敛到p:
- 11 -