《计算方法2非线性方程求根》由会员分享，可在线阅读，更多相关《计算方法2非线性方程求根（34页珍藏版）》请在金锄头文库上搜索。
1、第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
2、=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 步产生的
3、 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(x
4、k), 若 收敛，即存在 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上存在不动点？,令,有根, 不动点唯一？
5、,反证：若不然，设还有 ，则,而, 当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
6、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,原理：将非线性方程线性化 Taylo
7、r 展开,取 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 (
8、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 是否仍收敛
9、？,设 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 代入效果不好时，将 减
10、半计算。, /* 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: 如何实际确定收敛阶和渐进误差常数？,证明：,
