资源预览内容
第1页 / 共34页
第2页 / 共34页
第3页 / 共34页
第4页 / 共34页
第5页 / 共34页
第6页 / 共34页
第7页 / 共34页
第8页 / 共34页
第9页 / 共34页
第10页 / 共34页
亲,该文档总共34页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第2章 非线性方程求根,求 f (x) = 0 的根,非线性方程求解的基本思想,确定非线性方程实根范围的方法 图解法: 计算机比较难实现,对人使用方便。 逐步扫描法: 便于计算机实现。 2. 对方程根进一步精确化的方法 二分法,迭代法,Newton迭代法,依据:若 f Ca, b,且 f (a) f (b) 0,则 f 在 (a, b) 上必有一根。此时a, b称为有根区间。,2.1 二分法,原理,设a, b是方程f(x)=0的一个有根区间,取,是a1, b1的中点。,若f(x1) = 0,则x1是f(x) = 0的一个根,,若f(x1) f(a1) 0,则取a2=x1,b2=b1,否则取a2=a1,b2=x1,得到a2, b2,满足:,以a2, b2取代a1, b1,继续以上过程,得到a3, b3,直到某一xk时, ,使f(xk)=0,则xk是f(x)=0 的根,若不存在这样的xk,能得到一系列闭区间:,表明存在x*, f(x*)=0 , x* ak , bk,因此ak 单调上升,有上界x* , bk 单调下降,有下界x* ,且这二个序列均存在极限:,定 理2-4,若 f Ca, b,且 f (a) f (b) 0,则由二分法产生的序列xk 收敛于f (x) =0的一个根x*,且,x1,x2,a,b,When to stop?,或,不能保证 x 的精度,x*,2,第 k 步产生的 xk 有误差,对于给定的精度 ,可估计二分法所需的步数 k :,简单; 对f (x) 要求不高(只要连续即可) .,无法求复根及偶重根 收敛慢,注:用二分法求根,最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序,将a, b分为若干小区间,对每一个满足 f (ak)f (bk) 0 的区间调用二分法程序,可找出区间a, b内的多个根,且不必要求 f (a)f (b) 0 。,误差 分析:,例,例,f (x) = 0,x = 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 的根。,我不相信如此简单, 问题究竟是什么?,如何保证它的收敛性?,2.2 迭代法,迭代法的几何意义,方程x = g (x)的求根问题,在几何上就是确定xy平面内直线y = x和y = g (x)的交点p*。,p0,p1,p2,如此继续,曲线y = g (x)得到点列p1,p2,其横坐标分别为x1,x2,如果点列pk趋向于p*,则相应的迭代值xk收敛到所求的根x*。,可是这样做一定会收敛吗?,k,定理2-6, g(x) 在a, b上存在不动点?,令,有根, 不动点唯一?,反证:若不然,设还有 ,则,而, 当k 时, xk 收敛到 x* ?,证明:,可用 来控制收敛精度,L 越 收敛越快,小,注:定理条件非必要条件,可将a, b缩小,定义局部收敛性:若在 x* 的某 领域 B = x | | x x* | 有 gC1a, b 且 | g(x*) | 1,则由x0B 开始的迭代收敛。即调整初值可得到收敛的结果。,示例,求代数方程方程x3-2x-5=0,在x0=2附近的实根,方法一:,迭代格式为x3=2x+5,即,构造迭代序列收敛,取x0=2,则:,x1=2.08008 x2=2.09235 x3=2.094217 x4=2.094494 x5=2.094543 x6=2.094550,精确解为x=2.09455148150,2,方法二:,迭代格式为2x=x3-5,即,构造迭代序列不收敛,运算结果:,2.3 收迭代法的加速,P(x0, x1),P(x1, x2),一般地,有:,在xk+1=g(xk)迭代的每一步中,都用Aitken方法加以改进能加速收敛。 而且对某些不收敛的情况,用Aitken方法还有可能收敛。, Aitken 加速:,解:若迭代格式为2x=x3-5,构造迭代序列不收敛。用Atiken方法加以改进。,示例,求代数方程方程x3-2x-5=0,在x0=2附近的实根,精确解为x=2.09455148150,原理:将非线性方程线性化 Taylor 展开,取 x0 x*,将 f (x)在 x0 做一阶Taylor展开:,, 在 x0 和 x 之间。,将 (x* x0)2 看成高阶小量,则有:,线性 /* linear */,只要 f C1,每一步迭代都有f ( xk ) 0, 而且 ,则 x*就是 f 的根。,2.4 牛顿法,(收敛的充分条件)设 f C2a, b,若 f (a) f (b) 0; 则Newtons Method产生的序列 xk 收敛到f (x) 在 a, b 的唯一根。,有根,根唯一,产生的序列单调有界,保证收敛。,定理2-8,(局部收敛性)设 f C2a, b,若 x* 为 f (x) 在a, b上的根,且 f (x*) 0,则存在 x* 的邻域 使得任取初值 ,Newtons Method产生的序列 xk 收敛到x*,且满足,定理2-9,Newtons Method 事实上是一种特殊的不动点迭代 其中 ,则,收敛,由 Taylor 展开:,只要 f (x*) 0,则令 可得结论。,在单根 附近收敛快,证明:,注:Newtons Method 收敛性依赖于x0 的选取。,x*,示例,2.5 Newton迭代法的改进,/* improvement and generalization */, 重根 /* multiple root */ 加速收敛法:,Q1: 若 ,Newtons Method 是否仍收敛?,设 x* 是 f 的 n 重根,则: 且,因为 Newtons Method 事实上是一种特殊的不动点迭代, 其中 ,则,A1: 有局部收敛性,但重数 n 越高,收敛越慢。,Q2: 如何加速重根的收敛?,A2: 将求 f 的重根转化为求另一函数的单根。,令 ,则 f 的重根 = 的单根。, /* Descent Method */ Newtons Method 局部微调:,下山法,原理:若由 xk 得到的 xk+1 不能使 | f | 减小,则在 xk 和 xk+1 之间找一个更好的点 ,使得 。,注: = 1 时就是Newtons Method 公式。 当 = 1 代入效果不好时,将 减半计算。, /* Secant Method */ :,正割法,Newtons Method 一步要计算 f 和 f ,相当于2个函数值,比较费时。现用 f 的值近似求 f ,可少算一个函数值。,切线 /* tangent line */,割线 /* secant line */,切线斜率 割线斜率,需要2个初值 x0 和 x1。,收敛比Newtons Method 慢,且对初值要求同样高。, 一般 Fixed-Point Iteration 有 ,称为线 性收敛 ,这时 p = 1,0 C 1。, Aitken 加速有 。 称为超线性收敛,2.6 迭代法的收敛阶, Newtons Method 有 ,只要 就有 p 2。重根是线性收敛的。,Q: 如何实际确定收敛阶和渐进误差常数?,证明:,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号