计算方法2非线性方程求根.ppt
第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.08008x2=2.09235x3=2.094217x4=2.094494x5=2.094543x6=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:如何实际确定收敛阶和渐进误差常数？,证明：,
