非线性方程求根省公共课一等奖全国赛课获奖课件.pptx

第2章 非线性方程求根v根隔离根隔离v根搜索根搜索v对分法对分法v简单迭代法简单迭代法v埃特金加速法埃特金加速法v牛顿迭代法牛顿迭代法v弦截法弦截法 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重零点。重零点。定定义义 若若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 根隔离根隔离根隔离主要任务有：根隔离主要任务有：判定在考查范围内方程是否有根。判定在考查范围内方程是否有根。判定根个数。判定根个数。给出用详细数值表示有根区间。给出用详细数值表示有根区间。对非线性方程对非线性方程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个根）。个根）。超越方程有时有没有穷多个根。超越方程有时有没有穷多个根。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个极值点：个极值点：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页2.3 根搜索根搜索一、一、逐步搜索法逐步搜索法v 逐步搜索法能够用来搜索某一范围内根。它主要依据是：逐步搜索法能够用来搜索某一范围内根。它主要依据是：f(x)=0根不好求，但若给出根不好求，但若给出x值，则对应函数值值，则对应函数值f(x)好求。好求。若某一区间左右两边界处函数值异号，则此区间内有根。若某一区间左右两边界处函数值异号，则此区间内有根。v 执行过程是：以搜索范围一侧边界为起点，以执行过程是：以搜索范围一侧边界为起点，以h为步长，一步步向另一侧为步长，一步步向另一侧前进。以每一步起点和终点为边界，一步迈过区域为一个小子区间。每迈过前进。以每一步起点和终点为边界，一步迈过区域为一个小子区间。每迈过一个小子区间，就检验这个小子区间左右两边界处函数值是异号、同号还是一个小子区间，就检验这个小子区间左右两边界处函数值是异号、同号还是为为0。假如异号，则这个小子区间内有根。假如同号，则继续检验下一个小。假如异号，则这个小子区间内有根。假如同号，则继续检验下一个小子区间。假如某边界处函数值为子区间。假如某边界处函数值为0，则此边界为根。，则此边界为根。v 当用逐步搜索法来搜索根时，若步长当用逐步搜索法来搜索根时，若步长h设置过大，一步迈过偶数个根，则设置过大，一步迈过偶数个根，则找不到这些根。若步长找不到这些根。若步长h过小，则耗时太长。假如搜索区间无限大，能够设过小，则耗时太长。假如搜索区间无限大，能够设定当超出某一时间限制时候，停顿搜索。假如已经知道搜索区间内有单根，定当超出某一时间限制时候，停顿搜索。假如已经知道搜索区间内有单根，能够经过合理设置能够经过合理设置h，用逐步搜索法来求根。，用逐步搜索法来求根。v 逐步搜索法要求函数连续。逐步搜索法要求函数连续。v 搜索效率不高，根在有根区间内等概率分布时，平均搜索步数搜索效率不高，根在有根区间内等概率分布时，平均搜索步数 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页2.3 根搜索根搜索逐步搜索法对应程序逐步搜索法对应程序#include double f(double 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);double f(double x)return();/*计算并返回函数值计算并返回函数值f(x)*/7第7页2.3 根搜索根搜索二、变步长逐步搜索法二、变步长逐步搜索法v用逐步搜索法求根，当用逐步搜索法求根，当h远小于远小于(ba)时，往往需要很多步搜索。变时，往往需要很多步搜索。变步长逐步搜索法是对这一缺点改进。步长逐步搜索法是对这一缺点改进。v主要步骤为：主要步骤为：取较大步长，以较少步数搜索整个有根区间。若一步迈过子区间边取较大步长，以较少步数搜索整个有根区间。若一步迈过子区间边界处为根，则算法结束；若根在某一步迈过子区间内，则把这个更小界处为根，则算法结束；若根在某一步迈过子区间内，则把这个更小子区间作为新有根区间。子区间作为新有根区间。若步骤若步骤得到有根区间足够小，则取此区间中点为近似根，算法结得到有根区间足够小，则取此区间中点为近似根，算法结束；不然，缩小步长，以上一步得到新更小有根区间作为搜索对象，束；不然，缩小步长，以上一步得到新更小有根区间作为搜索对象，重复执行步骤重复执行步骤。v一样，变步长逐步搜索法要求函数连续。一样，变步长逐步搜索法要求函数连续。8第8页2.3 根搜索根搜索变步长逐步搜索法算法变步长逐步搜索法算法输入输入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页2.3 根搜索根搜索变步长逐步搜索法对应程序变步长逐步搜索法对应程序#include double f(double x);void 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(end)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页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,&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页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)曲线形状无关。曲线形状无关。普通情况下，普通情况下，对对分法最多迭代次数比其它分法最多迭代次数比其它变变步步长长逐步搜索法要少，所以逐步搜索法要少，所以对对分法是用得最多分法是用得最多变变步步长长逐步搜索法。逐步搜索法。14第14页2.5 简单迭代法简单迭代法一、简单迭代法主要思想一、简单迭代法主要思想v简单迭代法又称为简单迭代法又称为Picard迭代法、逐次迫近法、不动点迭代法，是迭代法、逐次迫近法、不动点迭代法，是求方程在某区间内单根近似值主要方法。求方程在某区间内单根近似值主要方法。v用简单迭代法求用简单迭代法求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*。v方程方程f(x)=0到到x=(x)变形不唯一。迭代公式不一样，或迭代初值不变形不唯一。迭代公式不一样，或迭代初值不一样，使迭代过程有收敛，有不收敛。一样，使迭代过程有收敛，有不收敛。15第15页2.5 简单迭代法简单迭代法简单迭代法几何含义简单迭代法几何含义 v以以 (x)(0,1)时为例，时为例，y=(x)函数曲线斜率在直线函数曲线斜率在直线y=x和和x轴之间，轴之间，直线直线y=x和曲线和曲线y=(x)交点交点R*对应于对应于x=(x)根，点根，点R*横坐标横坐标x*是方程是方程f(x)=0根。根。v第第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(x1,0)，完完成成一一轮轮迭迭代。代。v类类似似，第第2轮轮迭迭代代x2=(x1)，对对应应于于点点P2点点Q2点点R2点点P3过过程程。依依次次类推，类推，x0,x1,x2,会逐步迫近会逐步迫近x*。16第16页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为为李李普普希希兹兹（Lipschitz）常数）。）常数）。则：则：x=(x)在在a,b上存在唯一根上存在唯一根x*。迭代序列迭代序列x0,x1,x2,x3,必收敛于必收敛于x*，即，即 =x*。|xnx*|xn+1xn|成立。成立。|xnx*|x1x0|成立。成立。17第17页2.5 简单迭代法简单迭代法简单迭代法局部收敛性简单迭代法局部收敛性 v局部收敛局部收敛：在根在根x*某一个邻域某一个邻域内，内，xn+1=(xn)对任意迭代初值对任意迭代初值x0，迭代，迭代序列都收敛于序列都收敛于x*，则称，则称xn+1=(xn)在在x*邻域邻域内局部收敛。内局部收敛。v定理：定理：若若 (x)在在x=(x)根根x*某邻域内有连续一阶导数，且某邻域内有连续一阶导数，且|(x)|1，则，则xn+1=(xn)局部收敛。局部收敛。简单迭代法收敛阶简单迭代法收敛阶不不一一样样序序列列需需要要有有一一个个参参数数来来区区分分收收敛敛快快慢慢。收收敛敛阶阶是是一一个个抽抽象象、综综合合反应各种序列收敛快慢参数，收敛阶越高，序列收敛得越快。反应各种序列收敛快慢参数，收敛阶越高，序列收敛得越快。定义：设序列定义：设序列 收敛于收敛于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*附近附近p阶收敛。阶收敛。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页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)=epsilon)break;if(imaxi)printf(n方程方程f(x)=0根根x=%lf。,x1);elseprintf(n迭代次数已超出上限。迭代次数已超出上限。);double picard(double x)return();/*计算并返回函数值计算并返回函数值 (x)*/20第20页 将将 转化为转化为 方法有各种多样，方法有各种多样，例：例：在在 上可有以下方法：上可有以下方法：(1)(1)(2)(2)(3)(3)(4)(4)取取 ,有收敛、有发散、有快、有慢。有收敛、有发散、有快、有慢。21第21页xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p122第22页将原方程化为等价方程将原方程化为等价方程迭代法迭代法算例分析算例分析比如比如:用迭代法求解方程用迭代法求解方程解解1:1:取初值取初值显然迭代法发散显然迭代法发散23第23页仍取初值仍取初值x2=0.9644x3=0.9940 x4=0.9990 x5=0.9998x6=1.0000 x7=1.0000依这类推依这类推,得得已经收敛已经收敛,故原方程解为故原方程解为一样方程一样方程不一样迭代格式不一样迭代格式有不一样结果有不一样结果什么形式迭代法什么形式迭代法能够收敛呢能够收敛呢?迭代函数结构相关迭代函数结构相关(2)(2)假如将原方程化为等价方程假如将原方程化为等价方程24第24页解：将方程改写为解：将方程改写为 ，由此建立迭代公式：由此建立迭代公式：计算结果以下表计算结果以下表比如：求方程 在 附近根0123456781.51.35721 1.33086 1.32588 1.32494 1.32476 1.32473 1.32472 1.32472 迭代法迭代法算例分析算例分析2 2这是一个收敛不动点迭代格式这是一个收敛不动点迭代格式.25第25页这是一个收敛例子这是一个收敛例子，也有不收敛迭代公式，如对于一样问题，也有不收敛迭代公式，如对于一样问题，假如将方程改写为令一个迭代公式假如将方程改写为令一个迭代公式 ，仍取初值，仍取初值 ，则迭代发散。，则迭代发散。为此，研究为此，研究 存在性及迭代法收敛性。存在性及迭代法收敛性。解：将方程改写为解：将方程改写为 ，由此建立迭代公式：由此建立迭代公式：计算结果以下表计算结果以下表比如：求方程 在 附近根0123456781.51.35721 1.33086 1.32588 1.32494 1.32476 1.32473 1.32472 1.32472 迭代法迭代法算例分析算例分析2 226第26页因为因为所以所以 为有根区间为有根区间因为因为 则则用迭代法求方程近似解用迭代法求方程近似解,准确到小数点后准确到小数点后6 6位位本题迭代函数有两种结构形式本题迭代函数有两种结构形式所以采取迭代函数所以采取迭代函数比如比如:解解:时时 迭代法迭代法算例分析算例分析3 327第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页2.6 埃特金加速法埃特金加速法埃特金加速法主要思想埃特金加速法主要思想v埃特金（埃特金（Aitken）加速法用来加）加速法用来加紧简单紧简单迭代法收迭代法收敛敛速度。速度。令令yn=(xn)，（埃特金加速法，（埃特金加速法yn即加速前即加速前简单简单迭代法迭代法xn+1。）。）令令zn=(yn)，（埃特金加速法，（埃特金加速法zn即加速前即加速前简单简单迭代法迭代法xn+2。）。）v若用若用简单简单迭代法求迭代法求f(x)=0单单根根x*，迭代公式，迭代公式为为x=(x)，迭代初，迭代初值为值为x0，用埃特金加速法，用埃特金加速法对简单对简单迭代法迭代法x=(x)迭代迭代过过程加速得到迭代序列程加速得到迭代序列记记为为 ，则则由由xn求出求出xn+1步步骤为骤为：xn+1=xn （注：（注：xn+1是用埃特金加速法一次迭代是用埃特金加速法一次迭代结结果。）果。）若迭代序列若迭代序列 收收敛敛，则则必收必收敛敛于于x*。29第29页xxxx*nn+1n+20y=xy=f(x)XYBABABA30第30页 能够证实：能够证实：它表明序列它表明序列 收敛速度比收敛速度比 收敛速度快。收敛速度快。AitkenAitken加速方法加速方法 Aitken 加速有加速有 。称为称为超线性收敛超线性收敛.31第31页解：解：比如：求方程 在 附近根加速迭代方法加速迭代方法AitkenMethodAitkenMethodAitken迭代公式为迭代公式为:32第32页解：解：比如：求方程 在 附近根加速迭代方法加速迭代方法AitkenMethodAitkenMethodAitken程序程序33第33页2.7 牛顿迭代法牛顿迭代法一、牛顿迭代法主要思想一、牛顿迭代法主要思想v牛顿迭代法又称为切线法，是另一个有特色求根方法。牛顿迭代法又称为切线法，是另一个有特色求根方法。以以x*附近某一个附近某一个值值x0为为迭代初迭代初值值，代入迭代公式，重复迭代，得，代入迭代公式，重复迭代，得到序列到序列x0,x1,x2,。v用牛用牛顿顿迭代法求迭代法求f(x)=0单单根根x*主要步主要步骤为骤为：牛顿迭代法迭代公式为牛顿迭代法迭代公式为 ，(n=0,1,2,)。若此序列收若此序列收敛敛，则则必收必收敛敛于准确根于准确根x*，即，即 xn=x*。34第34页xxxx*nn+1n+20XYy=f(x)QQnn+135第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页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,&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(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页例1：利用牛顿迭代法求解 f(x)=ex-1.5-tan-1x 零点。初始点x0=-7.0 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.07018881 -10.6771 -0.02256662 -13.2792 -0.004366023 -14.0537 -0.000239024 -14.1011 -7.99585e-0075 -14.1013 -9.00833e-012NewtonMethod_PPT45NewtonMethod_PPT4539第39页注：注：注：注：Newtons Method 收敛性依赖于收敛性依赖于x0 选取。选取。x*x0 x0 x0算法说明算法说明:40第40页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内根唯一，且牛顿迭代序列收敛于此根。内根唯一，且牛顿迭代序列收敛于此根。牛牛顿顿迭代法是一个特殊迭代法是一个特殊简单简单迭代法。把牛迭代法。把牛顿顿迭代法看作迭代法看作简单简单迭代法迭代法时时，它迭代函数它迭代函数 (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第41页2.7 牛顿迭代法牛顿迭代法牛顿迭代法小结牛顿迭代法小结总之，牛顿迭代法含有以下特点：总之，牛顿迭代法含有以下特点：对对f(x)要求较高。需要对要求较高。需要对f(x)求导数，且求导数，且f(xn)不能为不能为0。收敛速度较快，但重根时收敛较慢。收敛速度较快，但重根时收敛较慢。含含有有局局部部收收敛敛性性，但但在在较较大大范范围围内内迭迭代代时时，有有可可能能不不收收敛敛。能能够够与与一一些些收收敛敛较较慢慢，但但收收敛敛条条件件不不太太苛苛刻刻方方法法联联用用。如如先先用用二二分分法法使使有有根根区区间间足足够够小小，把把二二分分法法得得到到粗粗略略根根作作为为牛牛顿顿迭迭代代法法迭迭代代初初值值，再再用用牛顿迭代法迭代。牛顿迭代法迭代。42第42页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)。43第43页0XYy=f(x)abxx*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.452675 0.456376。f(0.456376)f()0，a=0.456376。=0.452675 0.4559。45第45页2.8 弦截法弦截法二、双点弦截法算法二、双点弦截法算法输入输入x精度要求精度要求，迭代次数，迭代次数i最大值最大值maxi，有根区间边界，有根区间边界a,b。令令fa=f(a)，fb=f(b)。for(i=0;imaxi;i+)把此次迭代初值把此次迭代初值x1暂存入暂存入x0中。中。此次迭代结果此次迭代结果x1=b-fb*(b-a)/(fb-fa)。令令fx1=f(x1)。fx1=0 Y N break;|x1-x0|=Y N break;fx1*fa0 Y N b=x1;fb=fx1;a=x1;fa=fx1;imaxiY N输出方程输出方程f(x)=0根根x1。迭代次数已超出上限，异常退出。迭代次数已超出上限，异常退出。46第46页2.8 弦截法弦截法双点弦截法对应程序双点弦截法对应程序#include#include double f(double x);void main(void)double a,b,epsilon,x0,x1,fa,fb,fx1;long i,maxi;printf(n请输入请输入x精度要求：精度要求：);scanf(%lf,&epsilon);printf(n请输入最大迭代次数：请输入最大迭代次数：);scanf(%ld,&maxi);printf(n请输入有根区间边界请输入有根区间边界a,b：);scanf(%lf,%lf,&a,&b);fa=f(a);fb=f(b);x1=a;for(i=0;imaxi;i+)x0=x1;x1=b-fb*(b-a)/(fb-fa);fx1=f(x1);if(fx1=0)break;if(fabs(x1-x0)=epsilon)break;if(fx1*fa0)b=x1;fb=fx1;else a=x1;fa=fx1;if(imaxi)printf(n方程方程f(x)=0根根x=%lf。,x1);elseprintf(n迭代次数已超出上限。迭代次数已超出上限。);double f(double x)return();/*计算并返回函数值计算并返回函数值f(x)*/47第47页1手工进行根隔离，为迭代求解做准备。手工进行根隔离，为迭代求解做准备。2收敛性有确保求解方法收敛性有确保求解方法 逐步搜索法。能够用于根搜索。普通不用来求根。逐步搜索法。能够用于根搜索。普通不用来求根。二分法。收敛速度较慢，求零点最多迭代次数与函数曲线形状无关。二分法。收敛速度较慢，求零点最多迭代次数与函数曲线形状无关。双双点点弦弦截截法法（单单点点弦弦截截法法）。需需2个个初初值值。收收敛敛稍稍快快，收收敛敛速速度度与与函函数曲线形状相关。数曲线形状相关。3可能不收敛求解方法可能不收敛求解方法 简单迭代法。它是下面迭代法基础，可用埃特金加速法加速。简单迭代法。它是下面迭代法基础，可用埃特金加速法加速。牛顿迭代法。收敛较快，但需要求导。牛顿迭代法。收敛较快，但需要求导。变形双点弦截法。比牛顿迭代法收敛阶稍低，且不需要求导。变形双点弦截法。比牛顿迭代法收敛阶稍低，且不需要求导。第第2章章 非线性方程求根非线性方程求根 小结小结48第48页49第49页