第6章-非线性方程的计算方法课件.ppt

1、2 Bisection Methodabx1x2abWhen to stop?11xxkk 2)(xf 或或不能保证不能保证 x 的精的精度度x*2xx*6.1.1 Bisection Method误差误差 分析：分析：第第1步产生的步产生的21bax 有误差有误差21abx*|x 第第 k 步产生的步产生的 xk 有误差有误差kkabx*|x2 对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k：2lnlnln2abkabk 简单简单;对对f(x)要求不高要求不高(只要连续即可只要连续即可).无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 用二分法求根，最好

2、先给出用二分法求根，最好先给出 f(x)草图以确定根的大草图以确定根的大概位置。或用搜索程序，将概位置。或用搜索程序，将a,b分为若干小区间，对每一分为若干小区间，对每一个满足个满足 f(ak)f(bk)0 的区间调用二分法程序，可找出区的区间调用二分法程序，可找出区间间a,b内的多个根，且不必要求内的多个根，且不必要求 f(a)f(b)0。6.1.1 Bisection MethodLab 02.Bisection Method Use the Bisection method to find on m given intervals the m real roots of a given

3、polynomial of degree 5 n m,.InputThere are several sets of inputs.For each set:The 1st line contains an integer n which is the degree of a polynomial.n=1 signals the end of file.The 2nd line contains n+1 real numbers which are the coefficients of the polynomial.The numbers are separated by spaces.Th

4、e 3rd line contains an integer Max and two real numbers eps1 and eps2,where Max is the maximum number of iterations,eps1 is the accuracy bound for x and eps2 is the accuracy bound for p(x).The 4th line contains an integer m(n m 0),followed by m pairs of real numbers a1 b1 am bm which are the end poi

5、nts of the intervals a1,b1 am,bm.0111.)(cxcxcxcxpnnnn 01.cccnOutputEach root is to be printed as in the C fprintf:fprintf(outfile,%12.7f,root);/*hererepresentsaspace*/If there is no root found in an interval,simply print“noroot”.The output of the next set must be printed in a new line.Sample Input(r

6、epresents a space)210 110000.000000010.000000012 2 0.50.523100 110000.000000010.000000012 1002 1Sample Output(represents a space)1.00000001.0000000noroot1.00000006.1.1 Bisection Method6.1.2 迭代法迭代法 /*Fixed-PointIteration*/f(x)=0 x=(x)等价变换等价变换f(x)的根的根(x)的不动点的不动点思思路路从一个初值从一个初值 x0 出发，计算出发，计算 x1=(x0),x2=

7、(x1),xk+1=(xk),若若 收敛，即存在收敛，即存在 x*使得使得 ，且，且 连续，则由连续，则由 可可知知 x*=(x*)，即，即x*是是 的不动点，也就是的不动点，也就是f 的根。的根。0kkx*limxxkk 1limlimkkkkxx So basically we are done!I cant believe its so simple!Whats the problem?Oh yeah?Who tells you that the method is convergent?6.1.2 Fixed-Point Iterationxyy=xxyy=xxyy=xxyy=xx*x

8、*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p16.1.2 Fixed-Point Iteration定理定理考虑方程考虑方程 x=(x),(x)Ca,b,若若(I)当当 x a,b 时，时，(x)a,b；(II)0 L 1 使得使得|(x)|L 1 对对 x a,b 成立。成立。则任取则任取 x0 a,b，由，由 xk+1=(xk)得到的序列得到的序列 收收敛于敛于(x)在在a,b上的唯一不动点。并且有误差估计式：上的唯一不动点。并且有误差估计式：0kkx|11|*|1kkkxxLxx|1|*|01xxLLxxk

9、(k=1,2,)且存在极限且存在极限 1*lim*kkkxxxxx k6.1.2 Fixed-Point Iteration证明：证明：(x)在在a,b上存在不动点？上存在不动点？令令()()f xxx()axb ()()0,f aaa ()()0f bbb )(xf有根有根 不动点唯一？不动点唯一？反证：若不然，设还有反证：若不然，设还有 ，则，则()xx (*)()()(*),xxxx xx*在在和和之间。之间。*xx()(1()0 x*x 而而|()|1*xx 当当k 时，时，xk 收敛到收敛到 x*？|*|kxx111|(*)()|()|*|kkkxxxx 0|*|.|*|01 xxL

10、xxLkk 6.1.2 Fixed-Point Iteration?|11|*|1kkkxxLxx|*|*|*|*|11kkkkkkxxLxxxxxxxx?|1|*|01xxLLxxkk 111110|()()|()()|.|kkkkkkkkkkxxxxxxL xxLxx 1*lim*?*kkkxxxxx 1*()(*)limlim(*)*kkkkkkkxxxxxxxxx 可用可用 来来控制收敛精度控制收敛精度|1kkxx L 越越 收敛越快收敛越快小小定理条件非必要条件，可将定理条件非必要条件，可将a,b缩小，定义缩小，定义局部收局部收敛性敛性：若在：若在 x*的某的某 领域领域 B =x|

11、x x*|有有 C1a,b 且且|(x*)|1，则由则由 x0 B 开始的迭开始的迭代收敛。即代收敛。即调整初值可得到收敛的结果。调整初值可得到收敛的结果。6.1.2 Fixed-Point IterationAlgorithm:Fixed-PointIterationFind a solution to x=(x)given an initial approximation x0.Input:initial approximation x0;tolerance TOL;maximum number of iterations Nmax.Output:approximate solution

12、x or message of failure.Step 1 Set i=1;Step 2 While(i Nmax)do steps 3-6Step 3 Set x=(x0);/*compute xi*/Step 4 If|x x0|TOL then Output(x);/*successful*/STOP;Step 5 Set i+;Step 6 Set x0=x;/*update x0*/Step 7 Output(The method failed after Nmax iterations);/*unsuccessful*/STOP.当当 x 很大时，此处很大时，此处可改为可改为TO

13、Lxxx 06.1.3 牛顿法牛顿法 /*Newton-RaphsonMethod*/原理：原理：将非线性方程线性化将非线性方程线性化 Taylor 展开展开/*Taylorsexpansion*/取取 x0 x*，将将 f(x)在在 x0 做一阶做一阶Taylor展开展开:20000)(!2)()()()(xxfxxxfxfxf ，在在 x0 和和 x 之间。之间。将将(x*x0)2 看成高阶小量，则有：看成高阶小量，则有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 线性线性/*linear*/xyx*x0)()(1kkkkxfxfxx 只要只要 f C1，

14、每一步迭代都有，每一步迭代都有f(xk)0，而且而且 ，则则 x*就是就是 f 的根。的根。*limxxkk 6.1.3 Newton-Raphson Method定理定理 （收敛的充分条件收敛的充分条件）设）设 f C2a,b，若，若(1)f(a)f(b)0；则则Newtons Method产生的序列产生的序列 xk 收敛到收敛到f(x)在在 a,b 的的唯一根。唯一根。有根有根根唯一根唯一产生的序列单调有产生的序列单调有界，保证收敛。界，保证收敛。定理定理 （局部收敛性局部收敛性）设）设 f C2a,b，若，若 x*为为 f(x)在在a,b上的根，且上的根，且 f(x*)0，则存在，则存在

15、 x*的邻域的邻域 使得任取初使得任取初值值 ，Newtons Method产生的序列产生的序列 xk 收敛到收敛到x*，且满足且满足*)(xB*)(0 xBx *)(2*)()*(*lim21xfxfxxxxkkk 6.1.3 Newton-Raphson Method证明：证明：Newtons Method 事实上是一种特殊的不动点迭代事实上是一种特殊的不动点迭代 其中其中 ，则，则()()()f xxxfx 2(*)(*)(*)01(*)fxf xxfx 收敛收敛由由 Taylor 展开：展开：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(!2)()(

16、)(*kkkkkkxxxffxfxfxx 1 kx)(2)()*(*21kkkkxffxxxx 只要只要 f(x*)0，则令，则令 可得结论。可得结论。k在在单根单根/*simpleroot*/附近收敛快附近收敛快 6.1.3 Newton-Raphson MethodNewtons Method 收敛性依赖于收敛性依赖于x0 的选取。的选取。x*x0 x0 x06.1.3 Newton-Raphson Method改进与推广改进与推广/*improvementandgeneralization*/重根重根 /*multipleroot*/加速收敛法：加速收敛法：Q1:若若 ，Newtons

17、Method 是否仍收敛？是否仍收敛？0*)(xf设设 x*是是 f 的的 n 重根，则：重根，则：且且 。)(*)()(xqxxxfn 0*)(xq因为因为 Newtons Method 事实上是一种特殊的不动点迭代，事实上是一种特殊的不动点迭代，其中其中 ，则，则()()()f xxxfx 22(*)(*)(*)|(*)|1(*)fxfxfxxfx 111 nA1:有局部收敛性，但重数有局部收敛性，但重数 n 越高，收敛越慢。越高，收敛越慢。Q2:如何加速重根的收敛？如何加速重根的收敛？A2:将求将求 f 的重根转化为求另一函数的单根。的重根转化为求另一函数的单根。令，则令，则 f 的重根

18、的重根 =的单根。的单根。)()()(xfxfx 6.1.3 Newton-Raphson Method 正割法正割法 /*SecantMethod*/：Newtons Method 一步要计算一步要计算 f 和和 f，相当于，相当于2个函数值，个函数值，比较费时。现用比较费时。现用 f 的值近似的值近似 f，可少算一个函数值。，可少算一个函数值。x0 x1切线切线/*tangentline*/割线割线/*secantline*/切线斜率切线斜率 割线斜率割线斜率11)()()(kkkkkxxxfxfxf)()()(111 kkkkkkkxfxfxxxfxx需要需要2个初值个初值 x0 和和

19、x1。收敛比收敛比Newtons Method 慢，且对初值要求同样高。慢，且对初值要求同样高。6.1.3 Newton-Raphson Method 下山法下山法 /*DescentMethod*/Newtons Method 局部微调：局部微调：原理：原理：若由若由 xk 得到的得到的 xk+1 不能使不能使|f|减小，则在减小，则在 xk 和和 xk+1 之间找一个更好的点之间找一个更好的点 ，使得，使得 。1 kx)()(1kkxfxf xkxk+1,)1(1kkxx 1,0 )()()1()()(1kkkkkkkkxfxfxxxfxfxx =1 时就是时就是Newtons Metho

20、d 公式。公式。当当 =1 代入效果不好时，将代入效果不好时，将 减半计算。减半计算。6.1.3 Newton-Raphson MethodAlgorithm:NewtonsDescentMethodFind a solution to f(x)=0 given an initial approximation x0.Input:initial approximation x0;f(x)and f(x);minimum step size of xmin;tolerance TOL1 for x;tolerance TOL2 for ;maximum number of iterations

21、Nmax.Output:approximate solution x or message of failure.Step 1 Set k=1;Step 2 While(k Nmax)do steps 3-10Step 3 Set =1;Step 4 Set ;/*compute xk*/Step 5 If|x x0|TOL2 then GOTO Step 4;/*compute a better xi*/Step 9 Set x0=x0+xmin;/*move forward anyway to avoid deadlock*/Step 10 Set k+;Step 11 Output(Me

22、thod failed after Nmax iterations);STOP./*unsuccessful*/)()(000 xfxfxx )()(0 xfxf 计算量未见得减小计算量未见得减小精品课件精品课件！精品课件精品课件！6.1.3 Newton-Raphson Method 求复根求复根 /*FindingComplexRoots*/Newton 公式中的自变量可以是复数公式中的自变量可以是复数记记 z=x+i y,z0 为初值，同样有为初值，同样有)()(1kkkkzfzfzz kkkkkkDiCzfBiAzf )(,)(设设代入公式，令实、虚部对应相等代入公式，令实、虚部对应相等，可得，可得;221kkkkkkkkDCDBCAxx .221kkkkkkkkDCCBDAyy