现在数值分析课件科大 现代数值分析15 非线性方程求解.ppt

《现在数值分析课件科大 现代数值分析15 非线性方程求解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章非线性方程求根/*SolutionsofNonlinearEquations*/§1二分法/*BisectionMethod*/求f(x)=0的根原理：若fC[a,b]，且f(a)·f(b)<0，则f在(a,b)上必有一根。§2BisectionMethodabx1x2abWhentostop?或不能保证x的精度x*2xx*§2BisectionMethod误差分析：第1步产生的有误差第k步产生的xk有误差对于给定的精度,可估计二分法所需的步数k：①简单;②对f(x)要求不高(只要连续即可).①无法求复根及偶重根②收敛慢注：用二分

2、法求根，最好先给出f(x)草图以确定根的大概位置。或用搜索程序，将[a,b]分为若干小区间，对每一个满足f(ak)·f(bk)<0的区间调用二分法程序，可找出区间[a,b]内的多个根，且不必要求f(a)·f(b)<0。§2迭代法/*Fixed-PointIteration*/f(x)=0x=g(x)等价变换f(x)的根g(x)的不动点思路从一个初值x0出发，计算x1=g(x0),x2=g(x1),…,xk+1=g(xk),…若收敛，即存在x*使得，且g连续，则由可知x*=g(x*)，即x*是g的不动点，也就是f的根。Sobasicallywe

3、aredone!Ican’tbelieveit’ssosimple!What’stheproblem?Ohyeah?Whotellsyouthatthemethodisconvergent?§2Fixed-PointIterationxyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1§2Fixed-PointIteration定理考虑方程x=g(x),g(x)C[a,b],若(I)当x[a,b]时，g(x)[a,

4、b]；(II)0L<1使得

5、g’(x)

6、L<1对x[a,b]成立。则任取x0[a,b]，由xk+1=g(xk)得到的序列收敛于g(x)在[a,b]上的唯一不动点。并且有误差估计式：(k=1,2,…)且存在极限k§2Fixed-PointIteration证明：①g(x)在[a,b]上存在不动点？令有根②不动点唯一？反证：若不然，设还有，则在和之间。而③当k时，xk收敛到x*？§2Fixed-PointIteration④⑤⑥可用来控制收敛精度L越收敛越快小注：定理条件非必要条件，可将[a,b]缩小，

7、定义局部收敛性：若在x*的某领域B={x

8、

9、xx*

10、}有gC1[a,b]且

11、g’(x*)

12、<1，则由x0B开始的迭代收敛。即调整初值可得到收敛的结果。§3Fixed-PointIterationAlgorithm:Fixed-PointIterationFindasolutiontox=g(x)givenaninitialapproximationx0.Input:initialapproximationx0;toleranceTOL;maximumnumberofiterationsNmax.Output:approxim

13、atesolutionxormessageoffailure.Step1Seti=1;Step2While(iNmax)dosteps3-6Step3Setx=g(x0);/*computexi*/Step4If

14、xx0

15、

16、法/*acceleratingconvergence*/待定参数法：若

17、g’(x)

18、1，则将x=g(x)等价地改造为求K，使得例：求在(1,2)的实根。如果用进行迭代，则在(1,2)中有现令希望，即在(1,2)上可取任意，例如K=0.5，则对应即产生收敛序列。Aitken加速（两点组合）§3加速收敛方法xyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)一般地，有：比收敛得略快。Steffensen加速：