非线性方程与方程组的数值解法优秀PPT.ppt
《非线性方程与方程组的数值解法优秀PPT.ppt》由会员分享,可在线阅读,更多相关《非线性方程与方程组的数值解法优秀PPT.ppt(70页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、非线性方程与方程组的数值解法第一页,本课件共有70页第七章第七章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法/*Numerical Solutions of Nonlinear Equations and Nonlinear Algebraic Systems*/我们知道在实际应用中有许多非线性方程的例子我们知道在实际应用中有许多非线性方程的例子例如例如:(1)在光的衍射理论()在光的衍射理论(the theory of diffraction of light)中中,我们需要我们需要求求 x-tanx=0 的根的根(2)在行星轨道()在行星轨道(planetary orbits
2、)的计算中)的计算中,对任意的对任意的a和和b,我,我们需要求们需要求 x-asinx=b 的根的根(3)在数学中,需要求在数学中,需要求n次多项式的根次多项式的根第二页,本课件共有70页历史背景历史背景 代数方程的求根问题是一个古老的数学问题。理论上,代数方程的求根问题是一个古老的数学问题。理论上,次代数方程在复数域内一定有次代数方程在复数域内一定有 个根个根(考虑重数考虑重数)。早在。早在1616世纪世纪就找到了三次、四次方程的求根公式,但直到就找到了三次、四次方程的求根公式,但直到1919世纪才证明大世纪才证明大于等于于等于5 5次的一般代数方程式不能用代数公式求解,而对于超次的一般代数
3、方程式不能用代数公式求解,而对于超越方程就复杂的多,如果有解,其解可能是一个或几个,也可越方程就复杂的多,如果有解,其解可能是一个或几个,也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。数值方法求得满足一定精度要求的根的近似解。第三页,本课件共有70页求方程求方程 几何意义几何意义基本定理基本定理 如果函数如果函数 在在 上连续,且上连续,且则至少有一个数则至少有一个数 使得使得 ,若同时,若同时 的一阶的一阶导数导数 在在 内存在且保持定号,即内存在且保持定号,即 (或或 )则这样的则这
4、样的 在在 内唯一。内唯一。abx*第四页,本课件共有70页1 1 二分法二分法 /*Bisection Method*/原理:原理:若若 f Ca,b,且,且 f(a)f(b)0,则,则 f 在在(a,b)上至上至少有一实根。少有一实根。基本思想:基本思想:逐步将区间分半,通过判别区间端点函数值的符号,逐步将区间分半,通过判别区间端点函数值的符号,进一步搜索有根区间,将有根区间缩小到充分小,从而求进一步搜索有根区间,将有根区间缩小到充分小,从而求 出满足给定精度的根出满足给定精度的根 的近似值。的近似值。以以此此类类推推第五页,本课件共有70页终止法则?终止法则?abx1x2abWhen t
5、o stop?或或不能保证 x 的精度x*2xx*第六页,本课件共有70页 二分法算法给定区间a,b,求f(x)=0 在该区间上的根x.输入:a和b;容许误差 TOL;最大对分次数 Nmax.输出:近似根 x.Step 1 Set k=1;Step 2 Compute x=(a+b)/2;Step 3 While(k Nmax)do steps 4-6 Step 4 If f(x)=0 or|b-a|TOL,STOP;Output the solution x.Step 5 If x*f(a)0,Set b=x;Else Set a=x;Step 6 Set k=k+1;Compute x=(
6、a+b)/2;Go To Step 3;Step 7 Output the solution of equation:x;STOP.第七页,本课件共有70页3、由二分法的过程可知:由二分法的过程可知:4、对分次数的计算公式:对分次数的计算公式:1、2、令令误差误差 分析分析第八页,本课件共有70页解解:例例1 1:用二分法求方程用二分法求方程 在区间在区间 上的上的根,精确到小数点后第根,精确到小数点后第2 2位,问至少需对分多少次?位,问至少需对分多少次?第九页,本课件共有70页k ak bk xkf(xk)符号0123456 1.0 1.25 1.31251.3203 1.5 1.3751
7、.34381.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242 +第十页,本课件共有70页简单简单;对对f(x)要求不高要求不高(只要连续即可只要连续即可).无法求复根及无法求复根及偶重根偶重根收敛慢收敛慢 注:注:用二分法求根,最好先给出 f(x)草图以确定根的大概位置,或用搜索程序,将a,b分为若干小区间,对每一个满足 f(ak)f(bk)0 的区间调用二分法程序,可找出区间a,b内的多个根,且不必要求 f(a)f(b)0。优点优点缺点缺点第十一页,本课件共有70页2 不动点迭代法及其收敛性不动点迭代法及其收敛性f(x)=0 x=(x)(
8、迭代函数)(迭代函数)等价变换等价变换思思路路从一个初值从一个初值 x0 出发,计算出发,计算 x1=(x0),x2=(x1),xk+1=(xk),若若 收敛,即存在收敛,即存在 x*使得使得 ,且,且 连续,则由连续,则由 可可知知 x*=(x*),即,即x*是是 的不动点,也就是的不动点,也就是f 的根。的根。看起来很简单,令人有点看起来很简单,令人有点不相信,那么问题是什么不相信,那么问题是什么呢?呢?如何判定这种方法是收如何判定这种方法是收敛的呢?敛的呢?f(x)的根(x)的不动点一、不动点迭代一、不动点迭代 /*Fixed-Point Iteration*/第十二页,本课件共有70页
9、xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1几何意义几何意义第十三页,本课件共有70页例例2:已知方程已知方程 在在 上有一个根(正根)上有一个根(正根)下面选取下面选取5 5种迭代格式:种迭代格式:1 1、即即2 2、即即3 3、即即4 4、即即5 5、即即第十四页,本课件共有70页取取计算结果如下:计算结果如下:法法1 1法法4 4法法3 3法法2 2法法5 5 第十五页,本课件共有70页Lipschitz条件成立的充分条件考虑方程考虑方程 x=(x),若若(I)
10、当当 x a,b 时,时,(x)a,b;(II)0 L 1 使得使得 对对 x a,b 成立。成立。则任取则任取 x0 a,b,由,由 xk+1=(xk)得到的序列得到的序列 收敛收敛于于(x)在在a,b上的唯一不动点。并且有误差估计式:上的唯一不动点。并且有误差估计式:(k=1,2,)且存在极限且存在极限连续时连续时第十六页,本课件共有70页证明:证明:(x)在在a,b上存在不动点?上存在不动点?令令有根有根 不动点唯一?不动点唯一?反证:若不然,设还有反证:若不然,设还有 ,则,则在在和和之间。之间。而而 当当k 时,时,xk 收敛到收敛到 x*?第十七页,本课件共有70页L 越 收敛越快
11、可用 来控制收敛精度 小小注:注:条件(II)可改为 在a,b 满足Lipschitz条件,定理结论仍然成立。第十八页,本课件共有70页 算法:不动点迭代给定初始近似值 x0,求x=(x)的解.输入:初始近似值 x0;容许误差 TOL;最大迭代次数 Nmax.输出:近似解 x 或失败信息.Step 1 Set i=1;Step 2 While(i Nmax)do steps 3-6Step 3 Set x=(x0);/*计算 xi*/Step 4 If|x x0|1)(1)阶收敛的方法,阶收敛的方法,改用改用Stefensen迭代方法优点不多。迭代方法优点不多。第三十八页,本课件共有70页第三
12、十九页,本课件共有70页第四十页,本课件共有70页第四十一页,本课件共有70页第四十二页,本课件共有70页第四十三页,本课件共有70页第四十四页,本课件共有70页4 牛顿法牛顿法 /*Newton-Raphson Method*/一、牛顿迭代公式的推导一、牛顿迭代公式的推导1、待定参数法待定参数法不动点迭代的不动点迭代的关键关键是构造满足是构造满足收敛条件收敛条件的的迭代函数迭代函数 一种一种自然的选择自然的选择是令是令为了加速不动点迭代的收敛过程,应尽可能使迭代函数为了加速不动点迭代的收敛过程,应尽可能使迭代函数 在在 处有处有更多阶导数等于零更多阶导数等于零。令令现设现设第四十五页,本课件
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 非线性 方程 方程组 数值 解法 优秀 PPT
限制150内