第2章 非线性方程求根.ppt

1、1,第2章 非线性方程求根,根的隔离 根的搜索 对分法 简单迭代法 埃特金加速法 牛顿迭代法 弦截法,2,代数方程：若f(x)为n次多项式，即f(x)=anxnan-1xn-1a0，（an0）， 则f(x)=0为n次代数方程。,2.1 引言,超越方程：若f(x)为超越函数，则f(x)=0为超越方程。,线形方程：1次代数方程为线形方程。,非线性方程：高于1次的代数方程和超越方程为非线性方程。,零点：若f(x*)=0，则x*为f(x)=0的根，或称x*为f(x)的零点。,m重零点： 定义 若f(x*)=f(x*)=f”(x*)=f(m-1)(x*)=0，f(m)(x*)0，则x*为f(x)=0的m

2、重根，或称x*为f(x)的m重零点。 定义 若f(x)为多项式，且下式成立：f(x)=(xx*)mg(x)，其中m为0或正整数，g(x)的分子和分母都不含因子(xx*)，则x*为f(x)=0的m重根，或称x*为f(x)的m重零点。,对于4次及以上代数方程和一般的超越方程，不存在通用的根的解析表达式。有时可以用手工来严谨地求解方程，但难以保证效率。常常用计算机求出误差足够小的数值解，以满足实际问题的需要。,3,在用计算机求解非线性方程之前，经常用手工进行根的隔离，来简化程序设计。,2.2 根的隔离,根的隔离的主要任务有： 判定在考察的范围内方程是否有根。 判定根的个数。 给出用具体数值表示的有根

3、区间。,对非线性方程f(x)=0，手工进行根的隔离，可能用到的方法有： 试验法 图解法 分析法,分析法相关的定理有： 若f(x)在a,b上连续，且f(a)f(b)0，则f(x)=0在(a,b)上一定有实根。 若f(x)=0在(a,b)上有根，f(x)在(a,b)中不变号且不为0，则f(x)=0在(a,b)上根唯一。 n次代数方程在复数域上有n个根（r重根算r个根）。 超越方程有时有无穷多个根。,4,2.2 根的隔离,例2.1：用分析法将2x55x21=0的根进行隔离。 解：令f(x)=2x55x21。 显然，f(x)在定义域(,)内连续、可导。 f(x)=10 x410 x=10 x(x31)

4、=10 x(x1)(x2x1)。 x2x10函数f(x)共有2个极值点：x=0，1。 在区间(,1)内，f(x)0，f(x)严格单调增。 x时，f(x)。x=1时，f(x)=2。 此区间有单根。 在区间(1,0)内，f(x)0，f(x)严格单调减。 x=0时，f(x)=1。此区间有单根。 在区间(0,)内，f(x)0，f(x)严格单调增。 x时，f(x)。此区间有单根。 f(x)=0共有3个实根，对应的有根区间分别为(,1)、(1,0)和(0,)。 f(2)=45，f(1)=6， 3个有根区间缩小为(2,1)、(1,0)和(0,1)。,5,2.3 根的搜索,一、 逐步搜索法,逐步搜索法可以用来

5、搜索某一范围内的根。它的主要依据是： f(x)=0的根不好求，但若给出x的值，则对应的函数值f(x)好求。 若某一区间左右两边界处的函数值异号，则此区间内有根。,执行过程是：以搜索范围一侧的边界为起点，以h为步长，一步步向另一侧迈进。以每一步的起点和终点为边界，一步迈过的区域为一个小子区间。每迈过一个小子区间，就检查这个小子区间左右两边界处的函数值是异号、同号还是为0。如果异号，则这个小子区间内有根。如果同号，则继续检查下一个小子区间。如果某边界处函数值为0，则此边界为根。,当用逐步搜索法来搜索根时，若步长h设置过大，一步迈过偶数个根，则找不到这些根。若步长h过小，则耗时太长。如果搜索的区间无

6、限大，可以设定当超过某一时间限制的时候，停止搜索。如果已经知道搜索的区间内有单根，可以通过合理设置h，用逐步搜索法来求根。,逐步搜索法要求函数连续。 搜索效率不高，根在有根区间内等概率分布时，平均搜索步数,6,2.3 根的搜索,逐步搜索法的算法,7,2.3 根的搜索,逐步搜索法对应的程序,#include double f(double x); void main(void) double a,b,epsilon,x,h,begin,end; printf(n请输入x的精度要求：); scanf(%lf, ,double f(double x) return(); /*计算并返回函数值f(x)

7、*/ ,8,2.3 根的搜索,二、变步长逐步搜索法,用逐步搜索法求根，当h远小于(ba)时，往往需要很多步搜索。变步长逐步搜索法是对这一缺陷的改进。,主要步骤为： 取较大步长，以较少步数搜索整个有根区间。若一步迈过的子区间边界处为根，则算法结束；若根在某一步迈过的子区间内，则把这个更小的子区间作为新的有根区间。 若步骤得到的有根区间足够小，则取此区间的中点为近似根，算法结束；否则，缩小步长，以上一步得到的新的更小的有根区间作为搜索对象，重复执行步骤。,同样，变步长逐步搜索法要求函数连续。,9,2.3 根的搜索,变步长逐步搜索法的算法,10,2.3 根的搜索,变步长逐步搜索法对应的程序,#inc

8、lude double f(double x); void main(void) double a,b,epsilon,x,h,begin,end; long hnumber; printf(n请输入x的精度要求：);scanf(%lf, ,double f(double x) return(); /*计算并返回函数值f(x)*/ ,11,2.4 对分法,对分法的主要思想,对分法（二分法，区间分半法）是一种特殊的变步长逐步搜索法。对分法每一轮搜索的步数为2，即每一轮都是2步搜索完整个待搜索的有根区间，使有根区间的大小减为上一轮有根区间大小的一半。,主要步骤为： 计算当前有根区间中点处的函数值。

9、若函数值为0，则此点为函数零点，算法结束；否则，判断中点处函数值与区间哪一侧端点处函数值异号，异号的一侧为新的有根区间。中点成为新的端点，使有根区间缩小一半。 若步骤得到的有根区间足够小，则取此区间的中点为近似根，算法结束；否则，对新的有根区间，重复执行步骤。,对分法要求函数连续。,12,2.4 对分法,对分法的算法,13,2.4 对分法,对分法对应的程序,#include double f(double x); void main(void) double a,b,epsilon,x,middle; printf(n请输入x的精度要求：); scanf(%lf, ,double f(doub

10、le x) return(); /*计算并返回函数值f(x)*/ ,14,2.4 对分法,对分法的特点,定理2.1 若用对分法求f(x)=0在a,b上的单根，要求误差限，最多需要迭代n次，则n满足,例2.2：若用对分法求f(x)=0在0,1上的单根，要求精确到小数点后3位，问最多需要迭代多少次？,解：设最多需要迭代n次。 要求精确到小数点后3位， 误差限 10-3， 由定理2.1得： n= = = = =10，即最多需要迭代10次。,用对分法求f(x)=0在某区间的单根，最多迭代次数与函数f(x)曲线形状无关。一般情况下，对分法的最多迭代次数比其他的变步长逐步搜索法要少，因此对分法是用得最多的

11、变步长逐步搜索法。,15,2.5 简单迭代法,一、简单迭代法的主要思想,简单迭代法又称为Picard迭代法、逐次逼近法、不动点迭代法，是求方程在某区间内单根的近似值的重要方法。,用简单迭代法求f(x)=0的单根x*的主要步骤为： 把方程f(x)=0变形为x= (x)，称 (x)为迭代函数。 以xn+1= (xn) (n=0,1,2,)为迭代公式，以x*附近的某一个值x0为迭代初值，反复迭代，得到迭代序列x0,x1,x2,。 若此序列收敛，则必收敛于精确根x*，即 xn=x*。,方程f(x)=0到x= (x)的变形不唯一。迭代公式不同，或迭代初值不同，使迭代过程有的收敛，有的不收敛。,16,2.

12、5 简单迭代法,简单迭代法的几何含义,以 (x)(0,1)时为例，y= (x)函数曲线的斜率在直线y=x和x轴之间，直线y=x和曲线y= (x)的交点R*对应于x= (x)的根，点R*的横坐标x*是方程f(x)=0的根。,第1轮迭代，按迭代公式x1= (x0)，由x0求出x1的过程，对应于图中按虚线，点P1点Q1点R1点P2的过程。 步骤 由x0求 (x0)相当与从点P1(x0,0)向上走到点Q1(x0, (x0)。 步骤 从点Q1向左走到点R1( (x0), (x0)，把求得的Q1纵坐标 (x0)转换为点R1的横坐标 (x0)。 步骤 把 (x0)赋值给x1，对应于从点R1向下走到点P2(x

13、1,0)，完成一轮迭代。 类似，第2轮迭代x2= (x1)，对应于点P2点Q2点R2点P3的过程。依次类推，x0,x1,x2,会逐渐逼近x*。,17,2.5 简单迭代法,二、简单迭代法的收敛条件,这个定理为简单迭代法收敛的充分条件，并且可以估计满足指定误差所需要的迭代次数。,推论： 将此定理中的已知条件改为： 对任意xa,b，有| (x)|L1。 此定理仍然成立。,推论仍为充分条件。推论要求对迭代函数 (x)求1阶导数。,定理：若迭代函数 (x)满足： (x)在a,b上连续，且对任意xa,b，有 (x)a,b。 对任意i,ja,b，有| (i) (j)|L|ij|，且0L1（L为李普希兹（Li

14、pschitz）常数）。 则： x= (x)在a,b上存在唯一根x*。 迭代序列x0,x1,x2,x3,必收敛于x*，即 =x*。 |xnx*| |xn+1xn|成立。 |xnx*| |x1x0|成立。,18,2.5 简单迭代法,简单迭代法的局部收敛性,局部收敛：在根x*的某一个邻域内，xn+1= (xn)对任意迭代初值x0，迭代序列都收敛于x*，则称xn+1= (xn)在x*的邻域内局部收敛。,定理：若 (x)在x= (x)的根x*某邻域内有连续的一阶导数，且| (x)|1，则xn+1= (xn)局部收敛。,简单迭代法的收敛阶,不同的序列需要有一个参数来区分收敛的快慢。收敛阶是一个抽象的、综

15、合反映各种序列收敛快慢的参数，收敛阶越高，序列收敛得越快。,定义：设序列 收敛于x*。若存在常数p和正常数c，使 =c， 则序列 是p阶收敛的。1阶收敛又称为线性收敛；2阶收敛又称为平方收敛；3阶收敛又称为立方收敛；阶数p1时，称为超线性收敛。,定理：若在x= (x)的根x*某邻域内，xn+1= (xn)局部收敛于x*， (x)连续且一阶可导，0| (x)|1，则xn+1= (xn)线性收敛。,定理：若在x= (x)的根x*某邻域内，xn+1= (xn)局部收敛于x*， (x)有连续的p阶导数，且 (x*)= (x*)= (x*)= (x*)=0，但 (x*)0，则xn+1= (xn)在x*附

16、近p阶收敛。,19,2.5 简单迭代法,简单迭代法的算法,20,2.5 简单迭代法,简单迭代法对应的程序,#include #include double picard(double x); void main(void) double epsilon,x0,x1; long i,maxi; printf(n请输入x的精度要求：); scanf(%lf, ,double picard(double x) return(); /*计算并返回函数值 (x)*/ ,21,2.6 埃特金加速法,埃特金加速法的主要思想,埃特金（Aitken）加速法用来加快简单迭代法的收敛速度。, 令yn=(xn)，（埃

17、特金加速法的yn即加速前简单迭代法的xn+1。）, 令zn=(yn)，（埃特金加速法的zn即加速前简单迭代法的xn+2。）,若用简单迭代法求f(x)=0的单根x*，迭代公式为x=(x)，迭代初值为x0，用埃特金加速法对简单迭代法x=(x)迭代过程加速得到的迭代序列记为 ，则由xn求出xn+1的步骤为：, xn+1=xn （注：xn+1是用埃特金加速法一次迭代的结果。）,若迭代序列 收敛，则必收敛于x*。,22,2.7 牛顿迭代法,一、牛顿迭代法的主要思想,牛顿迭代法又称为切线法，是另一种有特色的求根方法。, 以x*附近的某一个值x0为迭代初值，代入迭代公式，反复迭代，得到序列x0,x1,x2,

18、。,用牛顿迭代法求f(x)=0的单根x*的主要步骤为：, 牛顿迭代法的迭代公式为 ，(n=0,1,2,)。, 若此序列收敛，则必收敛于精确根x*，即 xn=x*。,23,2.7 牛顿迭代法,二、牛顿迭代法的算法,24,2.7 牛顿迭代法,牛顿迭代法对应的程序,#include #include double f(double x); double df(double x); void main(void) double epsilon,x0,x1,fx0,dfx0; long i,maxi; printf(n请输入x的精度要求：);scanf(%lf, ,double f(double x)

19、return(); /*计算并返回函数值f(x)*/ double df(double x) return(); /*计算并返回函数值f(x)*/ ,25,2.7 牛顿迭代法,三、牛顿迭代法的收敛阶与收敛条件,定理 ：若x*是f(x)=0的单根，f(x)在x*附近有连续的2阶导数，适当地选取迭代初值x0，则牛顿迭代产生的迭代序列收敛于x*，且收敛阶不小于2。,定理：若f(x)在a,b上连续，存在2阶导数，且满足下列条件： f(a)f(b)0。 f”(x)不变号且f”(x)0。 选取初值x0，满足f(x0)f”(x)0。 则f(x)=0在a,b内根唯一，且牛顿迭代序列收敛于此根。,牛顿迭代法是一

20、种特殊的简单迭代法。把牛顿迭代法看作简单迭代法时，它的迭代函数 (x)= 。,用简单迭代法的收敛性判定定理，也可以判断牛顿迭代法是否收敛。,定理：若f(x)在a,b上连续，存在2阶导数，且满足下列条件： f(a)f(b)0。 f(x)不变号且f(x)0。 f”(x)不变号且f”(x)0。 b-a，且 b-a。 则对任意初值x0a,b，牛顿迭代序列收敛于f(x)=0在a,b内的唯一根。,26,2.7 牛顿迭代法,牛顿迭代法小结,总之，牛顿迭代法具有以下特点： 对f(x)要求较高。需要对f(x)求导数，且f(xn)不能为0。 收敛速度较快，但重根时收敛较慢。 具有局部收敛性，但在较大范围内迭代时，

21、有可能不收敛。可以与一些收敛较慢，但收敛条件不太苛刻的方法联用。如先用二分法使有根区间足够小，把二分法得到的粗略根作为牛顿迭代法的迭代初值，再用牛顿迭代法迭代。,27,2.8 弦截法,一、双点弦截法的主要思想,弦截法又称为割线法、弦位法，它的收敛条件不算苛刻，而收敛速度较快。弦截法分为双点弦截法和单点弦截法。,如图所示，设f(x)在a,b内连续，f(x)=0在a,b内有单根x*。,用双点弦截法求f(x)=0在a,b内单根x*的迭代过程为：, 过点(a,f(a)和(b,f(b)做一直线，与X轴相交，设交点横坐标为 。, 各轮循环得到的 形成的迭代序列，必收敛于根x*。, 若f( )=0，则 为精确根，迭代结束；否则，判断根x*在 的哪一侧，排除a,b中没有根x*的那一侧，以 为新的有根区间边界，得到新的有根区间，仍记为a,b，转反复循环。,计算 的公式为： =bf(b) 。,28,2.8 弦截法,单点迭代法：每次迭代需要一个或一套数据作为初值。,多点迭代法：每次迭代需要多个或多套数据作为初值。,简单迭代法把上次的迭代结果作为本次迭代的初值，属于单点迭代法。双点弦截法每次迭代以最后2次的迭代结果作为本次迭代的初值，