数学与应用数学毕业论文设计计算机科学中的重要数学思想—迭代

第三章 二分法

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 -