非线性方程求根市公开课获奖课件

1、第2章 非线性方程求根根隔离根搜索对分法简朴迭代法埃特金加速法牛顿迭代法弦截法 1第1页第1页代数方程：若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)=0m重根，或称x*为f(x)m

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

3、到办法有： 试验法 图解法 分析法 分析法相关定理有： 若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个根）。 超越方程有时有无穷多个根。3第3页第3页2.2 根隔离例2.1：用分析法将2x55x21=0根进行隔离。解：令f(x)=2x55x21。 显然，f(x)在定义域(,)内连续、可导。 f(x)=10 x410 x=10 x(x31)=10 x(x1)(x2x1)。x2x10函数f(x)共有2个

4、极值点：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)。4第4页第4页2.3 根搜索一、 逐步搜索法 逐步搜索法能够用来搜索某一范围内根。它主要依据是： f(x)=0根不好求，但若给出

5、x值，则相应函数值f(x)好求。 若某一区间左右两边界处函数值异号，则此区间内有根。 执行过程是：以搜索范围一侧边界为起点，以h为步长，一步步向另一侧迈进。以每一步起点和终点为边界，一步迈过区域为一个小子区间。每迈过一个小子区间，就检查这个小子区间左右两边界处函数值是异号、同号还是为0。假如异号，则这个小子区间内有根。假如同号，则继续检查下一个小子区间。假如某边界处函数值为0，则此边界为根。 当用逐步搜索法来搜索根时，若步长h设置过大，一步迈过偶数个根，则找不到这些根。若步长h过小，则耗时太长。假如搜索区间无限大，能够设定当超出某一时间限制时候，停止搜索。假如已经知道搜索区间内有单根，能够通过

6、合理设置h，用逐步搜索法来求根。 逐步搜索法要求函数连续。 搜索效率不高，根在有根区间内等概率分布时，平均搜索步数 5第5页第5页2.3 根搜索逐步搜索法算法输入x精度要求，搜索区间左右边界a、b。令步长h=2。 f(b) = = 0Y Nx=b; for(begin=a,end=a+h;beginb Y N end=b; f(begin) = = 0 Y N x=begin; break; f(begin)*f(end)0 Y N x=(begin+end)/2; break;输出方程f(x)=0根x。6第6页第6页2.3 根搜索逐步搜索法相应程序#include double f(doub

7、le x);void main(void)double a,b,epsilon,x,h,begin,end;printf(n请输入x精度要求：);scanf(%lf,&epsilon);printf(n请输入搜索区间边界a,b：);scanf(%lf,%lf,&a,&b);h=2*epsilon;if(f(b)=0) x=b;else for(begin=a,end=a+h;beginb)end=b;if(f(begin)=0)x=begin;break;if(f(begin)*f(end)0)x=(begin+end)/2;break;printf(n方程f(x)=0根x=%lf。,x);d

8、ouble f(double x)return(); /*计算并返回函数值f(x)*/7第7页第7页2.3 根搜索二、变步长逐步搜索法用逐步搜索法求根，当h远小于(ba)时，往往需要诸多步搜索。变步长逐步搜索法是对这一缺点改进。 主要环节为： 取较大步长，以较少步数搜索整个有根区间。若一步迈过子区间边界处为根，则算法结束；若根在某一步迈过子区间内，则把这个更小子区间作为新有根区间。 若环节得到有根区间足够小，则取此区间中点为近似根，算法结束；不然，缩小步长，以上一步得到新更小有根区间作为搜索对象，重复执行环节。同样，变步长逐步搜索法要求函数连续。 8第8页第8页2.3 根搜索变步长逐步搜索法算

9、法输入x精度要求，有根区间左右边界a、b，每一轮搜索步数hnumber令步长h=(ba)/hnumber。 f(b) = = 0Y Nx=b; for(begin=a,end=a+h;begin=end,end+=h) f(begin) = = 0 Y N x=begin; break; f(begin)*f(end)0 Y N (endbegin)/2= Y N x=(begin+end)/2; h/=hnumber; break; end=begin;输出方程f(x)=0根x。9第9页第9页2.3 根搜索变步长逐步搜索法相应程序#include double f(double x);voi

10、d main(void)double a,b,epsilon,x,h,begin,end;long hnumber;printf(n请输入x精度要求：);scanf(%lf,&epsilon);printf(n请输入有根区间边界a,b：);scanf(%lf,%lf,&a,&b);printf(n请输入每一轮搜索步数：); scanf(%ld,&hnumber);h=(b-a)/hnumber;if(f(b)=0)x=b;else for(begin=a,end=a+h;begin=end,end+=h) if(f(begin)=0)x=begin;break;if(f(begin)*f(en

11、d)0) if(end-begin)/2) middle=(a+b)/2; f(middle) = = 0 Y N break; f(a)*f(middle)0 Y N a=middle; b=middle; x=(a+b)/2;输出方程f(x)=0根x。12第12页第12页2.4 对分法对分法相应程序#include double f(double x);void main(void)double a,b,epsilon,x,middle;printf(n请输入x精度要求：);scanf(%lf,&epsilon);printf(n请输入有根区间边界a,b：);scanf(%lf,%lf,&

12、a,&b);if(f(a)=0)x=a;else if(f(b)=0)x=b;elsewhile(b-a)/2epsilon)middle=(a+b)/2;if(f(middle)=0)break;else if(f(a)*f(middle)0)a=middle;elseb=middle;x=(a+b)/2;printf(n方程f(x)=0根x=%lf。,x);double f(double x)return(); /*计算并返回函数值f(x)*/13第13页第13页2.4 对分法对分法特点定理2.1 若用对分法求f(x)=0在a,b上单根，要求误差限，最多需要迭代n次，则n满足例2.2：若用

13、对分法求f(x)=0在0,1上单根，要求准确到小数点后3位，问最多需要迭代多少次？解：设最多需要迭代n次。要求准确到小数点后3位，误差限 10-3，由定理2.1得：n= = = =10，即最多需要迭代10次。用对分法求f(x)=0在某区间单根，最多迭代次数与函数f(x)曲线形状无关。普通情况下，对分法最多迭代次数比其它变步长逐步搜索法要少，因此对分法是用得最多变步长逐步搜索法。 14第14页第14页2.5 简朴迭代法一、简朴迭代法主要思想简朴迭代法又称为Picard迭代法、逐次迫近法、不动点迭代法，是求方程在某区间内单根近似值主要办法。用简朴迭代法求f(x)=0单根x*主要环节为： 把方程f(

14、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)变形不唯一。迭代公式不同，或迭代初值不同，使迭代过程有收敛，有不收敛。15第15页第15页2.5 简朴迭代法简朴迭代法几何含义 以 (x)(0,1)时为例，y= (x)函数曲线斜率在直线y=x和x轴之间，直线y=x和曲线y= (x)交点R*相应于x= (x)根，点R*横坐标x*是方程f(x)=0根。 第1轮迭代，按迭代公式x1=

15、(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(x1,0)，完毕一轮迭代。类似，第2轮迭代x2= (x1)，相应于点P2点Q2点R2点P3过程。依次类推，x0,x1,x2,会逐步迫近x*。16第16页第16页2.5 简朴迭代法二、简朴迭代法收敛条件这个定理为简朴迭代法收敛充足条件，并且能够预计满足指定误差所需要迭代

16、次数。 推论： 将此定理中已知条件改为： 对任意xa,b，有| (x)|L1。此定理仍然成立。推论仍为充足条件。推论要求对迭代函数 (x)求1阶导数。定理：若迭代函数 (x)满足： (x)在a,b上连续，且对任意xa,b，有 (x)a,b。 对任意i,ja,b，有| (i) (j)|L|ij|，且0L1（L为李普希兹（Lipschitz）常数）。则： x= (x)在a,b上存在唯一根x*。 迭代序列x0,x1,x2,x3,必收敛于x*，即 =x*。 |xnx*| |xn+1xn|成立。 |xnx*| |x1x0|成立。17第17页第17页2.5 简朴迭代法简朴迭代法局部收敛性 局部收敛：在根x

17、*某一个邻域内，xn+1= (xn)对任意迭代初值x0，迭代序列都收敛于x*，则称xn+1= (xn)在x*邻域内局部收敛。定理：若 (x)在x= (x)根x*某邻域内有连续一阶导数，且| (x)|1，则xn+1= (xn)局部收敛。简朴迭代法收敛阶不同序列需要有一个参数来区分收敛快慢。收敛阶是一个抽象、综合反应各种序列收敛快慢参数，收敛阶越高，序列收敛得越快。 定义：设序列 收敛于x*。若存在常数p和正常数c，使 =c，则序列 是p阶收敛。1阶收敛又称为线性收敛；2阶收敛又称为平方收敛；3阶收敛又称为立方收敛；阶数p1时，称为超线性收敛。 定理：若在x= (x)根x*某邻域内，xn+1= (

18、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*附近p阶收敛。 18第18页第18页2.5 简朴迭代法简朴迭代法算法输入x精度要求，迭代初值x1，迭代次数i最大值maxi。for(i=0;imaxi;i+) 把本次迭代初值x1暂存入x0中。 本次迭代结果x1=(x0)。 |x1x0| Y N break; imaxiY N输出方程f(x)=0根x1。

19、迭代次数已超出上限，异常退出。 19第19页第19页2.5 简朴迭代法简朴迭代法相应程序#include #include double picard(double x);void main(void)double epsilon,x0,x1;long i,maxi;printf(n请输入x精度要求：);scanf(%lf,&epsilon);printf(n请输入迭代初值：);scanf(%lf,&x1);printf(n请输入最大迭代次数：);scanf(%ld,&maxi);for(i=0;imaxi;i+)x0=x1;x1=picard(x0);if(fabs(x1-x0)=epsil

20、on)break;if(imaxi)printf(n方程f(x)=0根x=%lf。,x1);elseprintf(n迭代次数已超出上限。);double picard(double x)return(); /*计算并返回函数值 (x)*/20第20页第20页 将 转化为 办法有各种多样，例： 在 上可有下列办法： (1) (2) (3) (4)取 ,有收敛、有发散、有快、有慢。21第21页第21页xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1x0p0 x1p1x0p0 x1p1x0p0 x1p122第2

21、2页第22页将原方程化为等价方程迭代法算例分析比如: 用迭代法求解方程解1:取初值显然迭代法发散23第23页第23页仍取初值x2 = 0.9644x3 = 0.9940 x4 = 0.9990 x5 = 0.9998x6 = 1.0000 x7 = 1.0000依这类推,得已经收敛,故原方程解为一样方程不同迭代格式有不同结果什么形式迭代法能够收敛呢?迭代函数结构相关(2) 假如将原方程化为等价方程24第24页第24页解：将方程改写为 ， 由此建立迭代公式： 计算结果下列表比如：求方程 在 附近根0123456781.51.357211.330861.325881.324941.324761.3

22、24731.324721.32472 迭代法算例分析2这是一个收敛不动点迭代格式.25第25页第25页这是一个收敛例子，也有不收敛迭代公式，如对于同样问题，假如将方程改写为令一个迭代公式 ，仍取初值 ，则迭代发散。 为此，研究 存在性及迭代法收敛性。解：将方程改写为 ， 由此建立迭代公式： 计算结果下列表比如：求方程 在 附近根0123456781.51.357211.330861.325881.324941.324761.324731.324721.32472 迭代法算例分析226第26页第26页由于因此 为有根区间由于 则用迭代法求方程近似解,准确到小数点后6位本题迭代函数有两种结构形式因

23、此采用迭代函数比如:解:时 迭代法算例分析327第27页第27页取初值 d1 = 0.1000000d2 = -0.0105171d3 = 0.1156e-002d4 = -0.1265e-003d5 = 0.1390e-004d6 = -0.1500e-005d7 = 0.1000e-006由于|d7| =0.1000e-0061e-6因此原方程解为x7 = 0.090525x1 = 0.1000000 x2 = 0.0894829x3 = 0.0906391x4 = 0.0905126x5 = 0.0905265x6 = 0.0905250 x7 = 0.090525128第28页第28页

24、2.6 埃特金加速法埃特金加速法主要思想埃特金（Aitken）加速法用来加快简朴迭代法收敛速度。 令yn=(xn)，（埃特金加速法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*。 29第29页第29页xxxx*nn+1n+20y=xy=f(x)XYBABABA30第30页

25、第30页 能够证实：它表明序列 收敛速度比 收敛速度快。Aitken加速办法 Aitken 加速有 。 称为超线性收敛. 31第31页第31页解：比如：求方程 在 附近根加速迭代办法AitkenMethodAitken迭代公式为:32第32页第32页解：比如：求方程 在 附近根加速迭代办法AitkenMethodAitken程序33第33页第33页2.7 牛顿迭代法一、牛顿迭代法主要思想牛顿迭代法又称为切线法，是另一个有特色求根办法。 以x*附近某一个值x0为迭代初值，代入迭代公式，重复迭代，得到序列x0,x1,x2,。用牛顿迭代法求f(x)=0单根x*主要环节为： 牛顿迭代法迭代公式为 ，(

26、n=0,1,2,)。 若此序列收敛，则必收敛于准确根x*，即 xn=x*。34第34页第34页xxxx*nn+1n+20XYy=f(x)QQnn+135第35页第35页2.7 牛顿迭代法二、牛顿迭代法算法输入x精度要求，迭代初值x1，迭代次数i最大值maxi。for(i=0;imaxi;i+) 把本次迭代初值x1暂存入x0中。 本次迭代结果x1=x0f(x0)f(x0)。 |x1x0| Y N break; imaxiY N输出方程f(x)=0根x1。 迭代次数已超出上限，异常退出。36第36页第36页2.7 牛顿迭代法牛顿迭代法相应程序#include #include double f(d

27、ouble x);double df(double x);void main(void)double epsilon,x0,x1,fx0,dfx0;long i,maxi;printf(n请输入x精度要求：);scanf(%lf,&epsilon);printf(n请输入迭代初值：);scanf(%lf,&x1);printf(n请输入最大迭代次数：);scanf(%ld,&maxi);for(i=0;imaxi;i+)x0=x1;fx0=f(x0);dfx0=df(x0);x1=x0-fx0/dfx0;if(fabs(x1-x0)=epsilon)break;if(imaxi)printf(

28、n方程f(x)=0根x=%lf。,x1);elseprintf(n迭代次数已超出上限。);double f(double x)return(); /*计算并返回函数值f(x)*/double df(double x)return(); /*计算并返回函数值f(x)*/37第37页第37页例1： 利用牛顿迭代法求解 f(x)=ex-1.5-tan-1x 零点。初始点x0=-7.0 38第38页第38页解： f (x0)=-0.70210-1，f (x)=ex-(1+x2)-1 计算迭代格式: 计算结果下列表：(取|f(x) |=10-10)k x f (x) 0 -7.0000 -0.07018

29、881 -10.6771 -0.02256662 -13.2792 -0.004366023 -14.0537 -0.000239024 -14.1011 -7.99585e-0075 -14.1013 -9.00833e-012NewtonMethod_PPT4539第39页第39页注：Newtons Method 收敛性依赖于x0 选取。x*x0 x0 x0算法阐明:40第40页第40页2.7 牛顿迭代法三、牛顿迭代法收敛阶与收敛条件定理 ：若x*是f(x)=0单根，f(x)在x*附近有连续2阶导数，适当地选取迭代初值x0，则牛顿迭代产生迭代序列收敛于x*，且收敛阶不小于2。 定理：若f(

30、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内根唯一，且牛顿迭代序列收敛于此根。牛顿迭代法是一个特殊简朴迭代法。把牛顿迭代法看作简朴迭代法时，它迭代函数 (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内唯一根。41

31、第41页第41页2.7 牛顿迭代法牛顿迭代法小结总之，牛顿迭代法含有下列特点： 对f(x)要求较高。需要对f(x)求导数，且f(xn)不能为0。 收敛速度较快，但重根时收敛较慢。 含有局部收敛性，但在较大范围内迭代时，有也许不收敛。能够与一些收敛较慢，但收敛条件不太苛刻办法联用。如先用二分法使有根区间足够小，把二分法得到粗略根作为牛顿迭代法迭代初值，再用牛顿迭代法迭代。42第42页第42页2.8 弦截法一、双点弦截法主要思想 弦截法又称为割线法、弦位法，它收敛条件不算苛刻，而收敛速度较快。弦截法分为双点弦截法和单点弦截法。 如图所表示，设f(x)在a,b内连续，f(x)=0在a,b内有单根x*

32、。用双点弦截法求f(x)=0在a,b内单根x*迭代过程为： 过点(a,f(a)和(b,f(b)做始终线，与X轴相交，设交点横坐标为 。 各轮循环得到 形成迭代序列，必收敛于根x*。 若f( )=0，则 为准确根，迭代结束；不然，判断根x*在 哪一侧，排除a,b中没有根x*那一侧，以 为新有根区间边界，得到新有根区间，仍记为a,b，转重复循环。 计算 公式为： =bf(b) 。 43第43页第43页0XYy=f(x)abxx*44第44页第44页2.8 弦截法单点迭代法：每次迭代需要一个或一套数据作为初值。 多点迭代法：每次迭代需要多个或多套数据作为初值。 简朴迭代法把上次迭代结果作为本次迭代初值，属于单点迭代法。双点弦截法每次迭代以最后2次迭代结果作为本次迭代初值，属于多点迭代法。 例：用双点弦截法求2x55x21=0在区间(1,0)内单根，迭代3次，结果保留4位有效数字。 解：令f(x)=2x55x21，迭代初值a=1，b=0。第一轮迭代：f(a)=f(1)=2，f(b)=f(0)=1。 =0 = 。第三轮 ：f( )=f(0.456376)0.001799。第二轮：f( )=f( )0.452675，f(1)f( )0，b= 。 = 0.45267