计算方法讲解课件.ppt

1、第二章第二章 一元非线性方程的解法一元非线性方程的解法 设非线性方程为 f(x)=0 (2-1)方程（2-1）的解 x*称为方程的根或函数 f(x)的零点。若f(x)可表示为 f(x)=(x-x*)m g(x)其中m为大于1的整数,且g(x)0,称x*为方程(2-1)的m重根,或函数 f(x)的m重零点.若 f(x)为n次多项式,则称 f(x)=0为n次代数方程;若 f(x)为超越函数,则称f(x)=0为超越方程。若 f(x)在a,b内连续,且 f(a)?f(b)0,f(0)=10,f(3)=-260 可见 f(x)仅有两个实根,分别位于(0,3),(3,+),又 f(4)=10,所以第二根的

2、隔根区间可缩小为 (3,4)。以上分析可用下表表示 x(-,0)0(0,3)3(3,4)4(4,+)f?(x)f(x)-0+-0-+隔根区间(0,3)(3,4)2.逐步搜索法 从区间a,b的左端点 a 出发,按选定的步长h 一步步向右搜索，若 f(a+jh)f(a+(j+1)h)0 (j=0,1,2,)则区间 a+jh,a+(j+1)h 内必有根。搜索过程也可从 b开始，这时应取步长 h 0。二、二分法 设f(x)在区间a,b 上连续,f(a)f(b)0,则a,b 内有方程的根。取 a,b 的中点 将区间一分为二。若 f(x0)=0,则 x0 就是方程的根,否则判别根 x*在 x0 的左侧还是

3、右侧。,)(bax?210若f(a)f(x0)0,则x*(x0,b),令 a1=x0,b1=b.不论出现哪种情况,(a1,b1)均为新的有根区间,它的长度只有原有根区间长度的一半,达到了压缩有根区间的目的。对压缩了的有根区间,又可实行同样的步骤,再压缩。如此反复进行,即可的一系列有根区间套?,11nnbababa由于每一区间都是前一区间的一半，因此区间 an,bn 的长度为)(ababnnn?21若每次二分时所取区间中点都不是根，则上述过程将无限进行下去。当 n 时，区间必将最终收缩为一点x*，显然x*就是所求的根。若 取区间 an,bn 的中点)(nnnbax?21作为x*的 近似值，则有下

4、述误差估计式 )22()(21)(21*1?ababxxnnnn只要 n 足够大,即区间二分次数足够多 ），误差就可足够小。),(,*11?nnnbaxx 由于在偶重根附近曲线 y=f(x)为上凹或下凸，即 f(a)与 f(b)的符号相同，因此不能用二分法求偶重根.例 2 用二分法求例1中（1）方程的实根,要求误差不超过0.005。解 由例1可知x*(1,1.5),要想满足题意，即：|x*-xn|0.005，则要 005.021)15.1(21)(21211?nnnab由此解得,6.512lg2?n取n=6。按二分法计 算过程见下表。x6=1.3242 为所求之近似根。n an bn xn f

5、(xn)0 1 2 3 4 5 6 1.0 1.25 1.25 1.3125 1.3125 1.3125 1.3203 1.5 1.5 1.375 1.375 1.3438 1.3281 1.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242-+-+-(1)f(a)0(2)根据精 度要求，取到小数 点后四位 即可.第二节 迭代法 一、迭代法的基本思想 迭代法是一种重要的逐次逼近法,其基本思想是：将方程 f(x）=0 化为等价方程,)(xx?然后在隔根区间内取一点 x0，按下式计算)32(),2,1,0()(1?kxxkk?计算结果生成数列 x0

6、,x1,xk,(2-4)如果这个数列有极限 ,*limxxkk?当?(x)连续时,显然 x*就是方程 x=?(x)之根.于是可以从此数列中求得满足精度要求的近似根.这种求根方法称为迭代法,式(2-3)称为迭代格式,?(x)称为迭代函数，x0 称为迭代初值，数列（2-4）称为迭代序列。如果迭代序列收敛,则称迭代格式（2-3）收 敛,否则称为发散。例3 用迭代法求方程 x4+2x2-x-3=0 在区间1,1.2内的实根。解 对方程进行如下三种变形：?03224xxx分别按以上三种形式建立迭代格式，并取 x0=1进行迭代计算，结果如下：74331762127261110495307.8,96,)(1

7、24123.1,)(124123.1,)(?xxxxxxxxxxxxkkkkkk?14)(2?xxx?32)(243?xxxx?4121)23()(xxxx?准确根 x*=1.124123029,可见迭代格式不同,收敛情况也不同。第二种格式比第一种格式收敛快得多,而第三种格式不收敛。二、迭代法的收敛条件 定理1 设)(x?在a,b上存在,且满足条件：（1）当xa,b时，;,)(bax?（2）存在正数L1，使对任意的 xa,b,。1)(?Lx?则 （1）方程)(xx?在a,b上有唯一根 x*;（2）对任意迭代初值 x0a,b,迭代序列),2,1,0()(1?kxxkk?收敛于x*。证（1）先证方

8、程)(xx?之解存在且唯一.由于)(x?在a,b上存在，所以)(x?连续。作函数,)()(xxxf?则 f(x)在a,b上连续。由条件(1)f(a)0,f(b)0,故存在x*a,b,使 f(x*)=0,即。)(*xx?设方程)(xx?还有一根,?则由微分中 值定理及条件（2）有?*)()()(xLxxx此式仅当 0*?x才能成立，因此。*x?（2）再证迭代格式)(1kkxx?收敛 任取 x0 a,b，由微分中值定理，有 1*1*1*)()()(?kkkkxxLxxxxxx?反复用此不等式，并注意 0 L 1，因此 x*-xkLkx*-x00 (k)即迭代过程收敛，且 。?xxkklim证毕。此

9、定理在理论上十分重要，但是条件（1）却不容易判别。如果仅在根的邻域中考察迭代格式，则下述定理可避免条件（1）的判别。定理2 若方程)(xx?之根的某邻域?*|xxxR内)(x?存在，且存在正常数 L 1时称为超线性收敛.显然,收敛阶越大,收敛越快.利用微分中值定理及泰勒展式可得下面的定理 3.三、迭代法的收敛速度 若,?xxkk?定理3 设 x*为)(xx?之根,在x*的邻域 R)(x?有连续的 p 阶导 数，则,1)(0)1(?x?若则迭代过程在 x*的邻近 为线性收敛；,0)(,0)()()()2()()1(?xxxxpp?若则迭代过程在 x*的邻近为 p 阶收敛。内)0(?aa的三阶方法

10、。假设 x0 充分靠近 x*,求 31)(limkkkxaxa?解 由泰勒展式可得 aaxaxakkkkkk41)(!31)(lim)(lim3131?例4 证明迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)是求 迭 代 格 式)92(2)()()()1(1)2(12)1(1)2(1)2(11)1(1)2(1)1(1?kkkkkkkkkkkxxxxxxxxxxx称为埃特金(Aitken)外推法，可以证明，若 )(1kkxx?为线性收敛，则埃特金法为平方 四、加速迭代法 收敛；若)(1kkxx?为 p(p 1)阶收敛，)(x?的 p 阶导数连续，则埃特金法为 2p 1 阶收敛。例5

11、求方程 x=e x 在 x=0.5 附近的根.解 取 x0=0.5,迭代格式 x25=x26=0.5671433 若对此格式用埃特金法,则 kxkex?1 得 kkkkkkkxkxkxxxxxxxexexkk?)1(1)2(12)1(1)2(1)2(11)2(2)1(12)()1(1仍取 x0=0.5,得 5671433.05671433.05671433.05671433.05672979.05668708.05676279.05452392.06065307.03)2(3)1(32)2(2)1(21)2(1)1(1?xxxxxxxxx由此可见,埃特金法加速收敛效果是相当显著的.第三节第三节

12、 牛顿切线法牛顿切线法 一、牛顿法的基本思想 设已知方程 f(x)=0 的近似根 x0，且在 x0附近 f(x)可用一阶泰勒多项式近似，表示为 )()()(000 xxxfxfxf?当 f?(x0)0 时，方程 f(x)=0 可用线性方程近似代替，即 f(x0)+f?(x0)(x-x0)=0 解此线性方程得)()(000 xfxfxx?取此 x 作为原方程的新近似根 x1，重复以上步骤，得迭代公式)102(),1,0()()(1?kxfxfxxkkkk此式称为牛顿(Newton)迭代公式。二、牛顿法的几何意义 若过曲线 y=f(x)上的点 P(xk,f(xk)引切线，该切线与 x 轴交点的横坐

13、标即为由牛顿迭代公式 求得的 xk+1,因此牛顿迭代法也称牛顿切线法。例6 用牛顿迭代法求方程 x=e x 在 x=0.5附近 的根。解 将原方程化为 x e x=0，则 牛顿迭代格式为 kkxxkkkeexxx?11取 x0=0.5，迭代得 x1=0.566311,x2=0.5671431,x3=0.5671433 f(x)=x e x，f?(x)=1+e x,三、牛顿迭代法的收敛速度 )()()(xfxfxx?由于 f(x*)=0，所以当 f?(x*)0 时,?，不一定为 0)()()(0)()()()(*xfxfxxfxfxfx?牛顿迭代法的迭代函数为 1、当 x*为单根时，牛顿迭代法在

14、根 x*的附近至少 是二阶收敛的；2、当 x*为重根时，设为m重根，则 f(x)可表为 f(x)=(x-x*)m g(x)其中 g(x*)0，此时用牛顿迭代法求 x*仍然收敛，只是收敛速度将大大减慢。事实上，因为 )()()()()()()(*1kkkkkkkkkkxgxxxgmxgxxxxfxfxx?令 ek=xk x*，则)()()(*11kkkkkkkkxgexmgxgeexxe?可见用牛顿法求方程的重根仅为线性收敛。有两种方法可以提高求重根的收敛速度：)132(011)()()(1limlim1?mxgexmgxgeekkkkkkkk1）将求重根问题化为求单根问题，注意函数 )01)(

15、)()()()()(*?mxQxQxxxfxfxu所以化为求 u(x)=0的单根,是平方收敛的.格式为?)()()()()()()(21kkkkkkkkkkxfxfxfxfxfxxuxuxx?2）采用如下迭代格式 3、计算重根的牛顿迭代法 )142()()(1?kkkkxfxfmxx下面介绍一个求重数的方法，令 211?kkkkkxxxx?则 121121111?kkkkkkkkkkkeeeeeeeeee?由式（2-13）可知 mmmkk111lim?因此可用下式估计 m)152(11?km?例8 用牛顿迭代法求 f(x)=(x-1)sin(x-1)+3x-x3+1=0 在0.95附近之根。解

16、 取 x0=0.95,用牛顿迭代法式(2-10)求得的 xk 见右表 可见 xk 收敛很慢。由重根数 m 为 2 用式（2-14）得 x0=0.95 x1=0.9988559 x2=x3=1 收敛速度大大加快于直接用牛顿迭代公式(2-10).k xk?k m 0 1 2 3 4 5 6 0.95 0.9744279 0.9870583 0.9934878 0.9967328 0.9983576 0.9991901 0.5090 0.5047 0.5007 0.5125 2.0369 2.0190 2.0028 2.0511 1、简化牛顿迭代法 在牛顿迭代公式（2-10）中用一常数 M 代替 f

17、?(xk)，得)112(),1,0()(1?kMxfxxkkk此式称为简化牛顿迭代公式，只要 M选择得当，式（2-11）总是线性收敛的。四、割线法 用常数 M 来代替 f?(xk)虽然简单，但没充分 利用 f(x)本身的特性，因此收敛较慢，若在牛顿 迭代公式中改用差商 11)()(?kkkkxxxfxf代替导数 f?(xk)，得迭代公式)122()()()()(111?kkkkkkkxxxfxfxfxx2、割线（弦截）法 称其为双点割线法。可以证明它的收敛阶为 ,618.1)51(21?p确实比式（2-11）收敛快。将式（2-12）中的 xk-1 改为 x0，即)()()()(0001xxxfxfxfxxkkkk?每步只用一新点，此格式为单点割线法。例7 用牛顿迭代法和割线法求方程 f(x)=x4+2x2 x 3=0 在区间（1,1.5）内之根（误差为 10-9）。解 取x0=1.5,用牛顿法,可得x6=1.12412303030；取x0=1.5,x1=1,用双点割线法,迭代6次得到同样 的结果，而采用单点割线法，则迭代 18次得 x18=1.124123029.