非线性方程的数值解法ppt课件.ppt

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

1、第二章非线性方程的数值解法/*NumericalSolutionsofNonlinearEquations*/本章主要内容：1、二分法2、不动点迭代的构造及其收敛性判定（重点）3、Newton和Steffensen迭代（重点）4、割线法5、非线性方程组的迭代解法历史背景代数方程的求根问题是一个古老的数学问题。理论上，次代数方程在复数域内一定有个根(考虑重数)。早在16世纪就找到了三次、四次方程的求根公式，但直到19世纪才证明大于等于5次的一般代数方程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，

2、也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。求方程几何意义基本定理如果函数在上连续，且则至少有一个数使得，若同时的一阶导数在内存在且保持定号，即(或)则这样的在内唯一。abx*§1二分法/*BisectionMethod*/原理：若fC[a,b]，且f(a)·f(b)<0，则f在(a,b)上至少有一实根。基本思想：逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求出满足给定精度的根的近似值。以此类推终止法则？abx1x2abW

3、hentostop?或不能保证x的精度x*2xx*二分法算法给定区间[a,b]，求f(x)=0在该区间上的根x.输入:a和b;容许误差TOL;最大对分次数Nmax.输出:近似根x.Step1Setk=1,x=(a+b)/2;Step2Computey=f(x);Step3While(kNmax)dosteps4-6Step4if

4、y

5、

6、tthesolutionofequation:x,iterationsk.3、由二分法的过程可知：4、对分次数的计算公式：1、2、令误差分析解：例1：用二分法求方程在区间上的根，误差限为，问至少需对分多少次？①简单;②对f(x)要求不高(只要连续即可).①无法求复根及偶重根②收敛慢注：用二分法求根，最好先给出f(x)草图以确定根的大概位置。或用搜索程序，将[a,b]分为若干小区间，对每一个满足f(ak)·f(bk)<0的区间调用二分法程序，可找出区间[a,b]内的多个根，且不必要求f(a)·f(b)<0。优点缺点§2迭代法的理论

7、/*TheoryofIterationMethod*/f(x)=0x=g(x)（迭代函数）等价变换思路从一个初值x0出发，计算x1=g(x0),x2=g(x1),…,xk+1=g(xk),…若收敛，即存在x*使得，且g连续，则由可知x*=g(x*)，即x*是g的不动点，也就是f的根。看起来很简单，令人有点不相信，那么问题是什么呢？如何判定这种方法是收敛的呢？f(x)的根g(x)的不动点一、不动点迭代/*Fixed-PointIteration*/xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=

8、g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1几何意义例2：已知方程在上有一个根（正根）下面选取5种迭代格式：1、即2、即3、即4、即5、即取计算结果如下：法1法4法3法2法5f(x)=0不动点迭代求方程的近似解，需解决以下问题：Why?!1.如何选取迭代函数g(x)?2.迭代函数g(x)满足什么条件才能保证收敛？3.的收敛性如何？误差估计？4.如何加速收敛？Lipschitz条件成立的充分条件考虑方程x=g(x),若(I)当x[a,b]时，g(x)[a,b]；(II)0L<

9、1使得对x[a,b]成立。则任取x0[a,b]，由xk+1=g(xk)得到的序列收敛于g(x)在[a,b]上的唯一不动点。并且有误差估计式：(k=1,2,…)且存在极限连续时证明：①g(x)在[a,b]上存在不动点？令有根②不动点唯一？反证：若不然，设还有，则在和之间。而③当k时，xk收敛到x*？L越收敛越快可用来控制收敛精度④⑤⑥小注：条件(II)可改为在[a,b]满足Lipschitz条件,定理结论仍然成立(定理2.1)。算法:不动点迭代给定初始近似值x0，求x=g(x)的解.输入:初始近似值x0;

10、容许误差TOL;最大迭代次数Nmax.输出:近似解x或失败信息.Step1i=1;x=g(x0);Step2whileabs(xx0)