非线性方程求解公开课一等奖优质课大赛微课获奖课件.pptx

第二章非线性非线性方程求解方程求解 第1页第1页第二章第二章非线性方程求解非线性方程求解返回前进第二章第二章 非线性方程求解目录非线性方程求解目录 1对分法对分法2迭代法迭代法2.1迭代法基本思想迭代法基本思想2.2迭代法收敛条件迭代法收敛条件2.3 Steffensen办办 法法 简简 朴朴 迭迭 代代法加速法加速3Newton法与弦截法法与弦截法3.1Newton法法3.2弦截法弦截法第2页第2页第二章第二章非线性方程求解非线性方程求解返回前进第二章 非线性方程求解概述 诸多科学计算问题经常诸多科学计算问题经常诸多科学计算问题经常诸多科学计算问题经常归结为求解方程：归结为求解方程：归结为求解方程：归结为求解方程：第3页第3页第二章第二章非线性方程求解非线性方程求解返回前进比如，从曲线比如，从曲线比如，从曲线比如，从曲线y y=x x和和和和y y=lg xlg x简朴草图可看出方程简朴草图可看出方程简朴草图可看出方程简朴草图可看出方程lglg x x+x x=0=0有唯一正根有唯一正根有唯一正根有唯一正根x x*，但是没有求，但是没有求，但是没有求，但是没有求x x*准确值已知办法，准确值已知办法，准确值已知办法，准确值已知办法，即使是对代数方程，要求其准确解也是困难。对于二次方即使是对代数方程，要求其准确解也是困难。对于二次方即使是对代数方程，要求其准确解也是困难。对于二次方即使是对代数方程，要求其准确解也是困难。对于二次方程程程程axax2 2+bx+cbx+c=0=0，我们能够用熟悉求根公式，我们能够用熟悉求根公式，我们能够用熟悉求根公式，我们能够用熟悉求根公式：对于三、四次代数方程，尽管存在求解公式，但并对于三、四次代数方程，尽管存在求解公式，但并对于三、四次代数方程，尽管存在求解公式，但并对于三、四次代数方程，尽管存在求解公式，但并不实用。而对于不小于等于五次代数方程，它根不能用不实用。而对于不小于等于五次代数方程，它根不能用不实用。而对于不小于等于五次代数方程，它根不能用不实用。而对于不小于等于五次代数方程，它根不能用方程系数解析式表示，至于普通超越方程，更没有求根方程系数解析式表示，至于普通超越方程，更没有求根方程系数解析式表示，至于普通超越方程，更没有求根方程系数解析式表示，至于普通超越方程，更没有求根公式。因此，为求解一个非线性方程，我们必须依托某公式。因此，为求解一个非线性方程，我们必须依托某公式。因此，为求解一个非线性方程，我们必须依托某公式。因此，为求解一个非线性方程，我们必须依托某种数值办法来求其近似解。种数值办法来求其近似解。种数值办法来求其近似解。种数值办法来求其近似解。对于方程（对于方程（对于方程（对于方程（2-12-1）要求得其准确解普通来说是不也许。）要求得其准确解普通来说是不也许。）要求得其准确解普通来说是不也许。）要求得其准确解普通来说是不也许。第4页第4页第二章第二章非线性方程求解非线性方程求解返回前进求方程根近似解，普通有下列几种问题：求方程根近似解，普通有下列几种问题：求方程根近似解，普通有下列几种问题：求方程根近似解，普通有下列几种问题：3.3.3.3.根准确化：根准确化：根准确化：根准确化：已知一个根粗略近似值后，建立计算办法已知一个根粗略近似值后，建立计算办法已知一个根粗略近似值后，建立计算办法已知一个根粗略近似值后，建立计算办法快要似解逐步准确化，直到满足给定精度为止。快要似解逐步准确化，直到满足给定精度为止。快要似解逐步准确化，直到满足给定精度为止。快要似解逐步准确化，直到满足给定精度为止。设函数设函数设函数设函数f f(x x)在区间在区间在区间在区间 a a,b b 上连续，严格单调，且上连续，严格单调，且上连续，严格单调，且上连续，严格单调，且f f(a a)f f(b b)0)0，则在，则在，则在，则在 a a,b b 内方程内方程内方程内方程f f(x x)=0)=0有且仅有一个实根。有且仅有一个实根。有且仅有一个实根。有且仅有一个实根。依据此结论，我们能够采用下列两种办法求出根隔离依据此结论，我们能够采用下列两种办法求出根隔离依据此结论，我们能够采用下列两种办法求出根隔离依据此结论，我们能够采用下列两种办法求出根隔离区间。区间。区间。区间。1.1.根存在性：根存在性：根存在性：根存在性：方程是否有根？假如有根，有几种根？方程是否有根？假如有根，有几种根？方程是否有根？假如有根，有几种根？方程是否有根？假如有根，有几种根？2.2.2.2.根隔离：根隔离：根隔离：根隔离：拟定根所在区间，使方程在这个小区间内有拟定根所在区间，使方程在这个小区间内有拟定根所在区间，使方程在这个小区间内有拟定根所在区间，使方程在这个小区间内有且仅有一个根，这一过程称为根隔离，完毕根隔离，就可且仅有一个根，这一过程称为根隔离，完毕根隔离，就可且仅有一个根，这一过程称为根隔离，完毕根隔离，就可且仅有一个根，这一过程称为根隔离，完毕根隔离，就可得到方程各个根近似值。得到方程各个根近似值。得到方程各个根近似值。得到方程各个根近似值。关于根存在性是纯数学问题，不详细简介，可查阅有关于根存在性是纯数学问题，不详细简介，可查阅有关于根存在性是纯数学问题，不详细简介，可查阅有关于根存在性是纯数学问题，不详细简介，可查阅有关代数学内容。关代数学内容。关代数学内容。关代数学内容。根隔离主要依据下列结论：根隔离主要依据下列结论：根隔离主要依据下列结论：根隔离主要依据下列结论：第5页第5页第二章第二章非线性方程求解非线性方程求解返回前进求根隔离区间两种办法1.1.描图法：描图法：描图法：描图法：画出画出画出画出y=y=f f(x x)草图，由草图，由草图，由草图，由f f(x x)与与与与x x轴交点大约位置轴交点大约位置轴交点大约位置轴交点大约位置来拟定有根区间。也可利用导函数来拟定有根区间。也可利用导函数来拟定有根区间。也可利用导函数来拟定有根区间。也可利用导函数f f (x x)正、负与函数正、负与函数正、负与函数正、负与函数f f(x x)单调性关系来拟定根大约位置。单调性关系来拟定根大约位置。单调性关系来拟定根大约位置。单调性关系来拟定根大约位置。例例例例1 1 求求求求f f(x x)=3)=3x x 1 1 coscosx x=0=0有根区间有根区间有根区间有根区间解：将方程变形为解：将方程变形为解：将方程变形为解：将方程变形为3 3x x 1=cos1=cosx x绘出曲线绘出曲线绘出曲线绘出曲线 y y=3=3x x 1 1及及及及 y y=cos=cosx x，由图由图由图由图8-18-1可知，方程只有一个可知，方程只有一个可知，方程只有一个可知，方程只有一个实根：实根：实根：实根：yxx x*图图图图8-18-1例例例例2 2紧接下屏紧接下屏紧接下屏紧接下屏第6页第6页第二章第二章非线性方程求解非线性方程求解返回前进2.2.逐步搜索法：逐步搜索法：逐步搜索法：逐步搜索法：从区间从区间从区间从区间 a a,b b 左端点左端点左端点左端点a a出发，按选定步长出发，按选定步长出发，按选定步长出发，按选定步长h h一步步向右搜索，一步步向右搜索，一步步向右搜索，一步步向右搜索，若若若若:则区间则区间则区间则区间 a a+jhjh,a a+(+(j j+1)+1)h h 内必有根。搜索过程也能够内必有根。搜索过程也能够内必有根。搜索过程也能够内必有根。搜索过程也能够从从从从 b b开始，这时应取步长开始，这时应取步长开始，这时应取步长开始，这时应取步长h h00,)0,f f(0)=10,(0)=10,f f(3)=(3)=260,260)0因此仅有二个实根，因此仅有二个实根，因此仅有二个实根，因此仅有二个实根，分别位于分别位于分别位于分别位于(0,3),(3,(0,3),(3,)内。又因内。又因内。又因内。又因f f(4)=10,(4)=10,因此，二个因此，二个因此，二个因此，二个隔根区间拟定为隔根区间拟定为隔根区间拟定为隔根区间拟定为(0,3),(3,4)(0,3),(3,4)。第7页第7页第二章第二章非线性方程求解非线性方程求解返回前进1对分法设设设设f f(x x)在区间在区间在区间在区间 a a,b b 上连续，严格单调，且上连续，严格单调，且上连续，严格单调，且上连续，严格单调，且f f(a a)f f(b b)0)0，不妨设，不妨设，不妨设，不妨设f f(a a)0,)0)0，则方程，则方程，则方程，则方程f f(x x)=0)=0在在在在 a a,b b 内存在唯一实根，对分法基本思想是：用对分区间办法，内存在唯一实根，对分法基本思想是：用对分区间办法，内存在唯一实根，对分法基本思想是：用对分区间办法，内存在唯一实根，对分法基本思想是：用对分区间办法，通过判别函数通过判别函数通过判别函数通过判别函数f f(x x)在每个对分区间中点符号，逐步将有根在每个对分区间中点符号，逐步将有根在每个对分区间中点符号，逐步将有根在每个对分区间中点符号，逐步将有根区间缩小，最后求得一个含有相称准确程度近似根。详细区间缩小，最后求得一个含有相称准确程度近似根。详细区间缩小，最后求得一个含有相称准确程度近似根。详细区间缩小，最后求得一个含有相称准确程度近似根。详细环节为环节为环节为环节为:第8页第8页第二章第二章非线性方程求解非线性方程求解返回前进若每次对分区间时所取区间中点都不是根，则若每次对分区间时所取区间中点都不是根，则上述过程将无限地进行下去，当上述过程将无限地进行下去，当n时，区间将时，区间将最后收缩为一点最后收缩为一点x*，显然，显然x*就是所求方程根就是所求方程根。第9页第9页第二章第二章非线性方程求解非线性方程求解返回前进对分法误差预计作为作为作为作为x x*近似值，则误差为：近似值，则误差为：近似值，则误差为：近似值，则误差为：只要只要只要只要n n足够大（即区间对分次数足够多），足够大（即区间对分次数足够多），足够大（即区间对分次数足够多），足够大（即区间对分次数足够多），x xn n误差就可误差就可误差就可误差就可足够小，且只要足够小，且只要足够小，且只要足够小，且只要f f(x x)连续，对分区间总是收敛。连续，对分区间总是收敛。连续，对分区间总是收敛。连续，对分区间总是收敛。式（式（式（式（8-28-2）不但能够预计对分区间法误差，并且能够给）不但能够预计对分区间法误差，并且能够给）不但能够预计对分区间法误差，并且能够给）不但能够预计对分区间法误差，并且能够给定误差限定误差限定误差限定误差限 预计出对分区间次数，由于由式（预计出对分区间次数，由于由式（预计出对分区间次数，由于由式（预计出对分区间次数，由于由式（2-22-2）有：）有：）有：）有：若取区间若取区间若取区间若取区间 a an n,b bn n 中点：中点：中点：中点：第10页第10页第二章第二章非线性方程求解非线性方程求解返回前进例例3解：解：解：解：由于由于由于由于f f(x x)连续且连续且连续且连续且f f (x x)=3)=3x x2 2+100(+100(x x (,)，故故故故f f(x x)在在在在(,)上单调增长上单调增长上单调增长上单调增长而而而而f f(1)=(1)=90,90(2)=80因此因此因此因此原方程在（原方程在（原方程在（原方程在（1 1，2 2）内有唯一实根。）内有唯一实根。）内有唯一实根。）内有唯一实根。第11页第11页第二章第二章非线性方程求解非线性方程求解返回前进N Na an nb bn nx xn nf f(x xn n)0 01 12 21.51.5-1.625-1.6251 11.51.52 21.751.752.8593752.8593752 21.51.51.751.751.6251.6250.541015630.541015633 31.51.51.6251.6251.56251.5625-0.56030273-0.560302734 41.56251.56251.6251.6251.593751.59375-0.01431274-0.014312745 51.593751.593751.6251.6251.6093751.6093750.262172700.262172706 61.593751.593751.60937501.60937501.60156251.60156250.123636720.123636727 71.593751.593751.60156251.60156251.59765621.59765620.054588850.054588858 81.593751.593751.59765621.59765621.59570311.59570310.09790.09799 91.593751.593751.59570311.59570311.59472661.59472660.002898960.0028989610101.593751.593751.59472661.59472661.59423831.5942383-0.00570803-0.0057080311111.59423831.59423831.59472661.59472661.59448241.5944824-0.00140482-0.0014048212121.59448241.59448241.59472661.59472661.59460451.59460450.000747000.0007470013131.59448241.59448241.59460451.59460451.59454351.5945435-0.00032893-0.0003289314141.59454361.59454361.59460461.59460461.59457411.5945741 第12页第12页第二章第二章非线性方程求解非线性方程求解返回前进n f=x3+10*x-20nf=nx3+10*x-20n double(solve(f)nans=n 1.5946 n -0.7973+3.4506in -0.7973-3.4506i第13页第13页第二章第二章非线性方程求解非线性方程求解返回前进对分法优缺点对分法长处是计算简朴，对分法长处是计算简朴，办法可靠，容易预计误差。办法可靠，容易预计误差。但它收敛较慢，不能求偶次但它收敛较慢，不能求偶次重根，也不能求复根。重根，也不能求复根。因此，普通在求方程近似根因此，普通在求方程近似根时，很少单独使用，惯用于为其时，很少单独使用，惯用于为其他高速收敛算法（如牛顿法）提他高速收敛算法（如牛顿法）提供初值。供初值。第14页第14页第二章第二章非线性方程求解非线性方程求解返回前进2 简朴迭代法 迭代法迭代法是求解方程是求解方程f(x)=0根一个主要办法。它是利根一个主要办法。它是利用同一个迭代公式，逐次迫近用同一个迭代公式，逐次迫近方程根，使其得到满足预先方程根，使其得到满足预先给定精度要求近似值。给定精度要求近似值。第15页第15页第二章第二章非线性方程求解非线性方程求解返回前进2.1迭代法基本思想迭代法是一个主要逐次迫近法，迭代法是一个主要逐次迫近法，迭代法是一个主要逐次迫近法，迭代法是一个主要逐次迫近法，其基本思想是其基本思想是其基本思想是其基本思想是：设方程设方程设方程设方程f f(x x)=0)=0在区间在区间在区间在区间 a a,b b 内有一根内有一根内有一根内有一根x x*，将方程化为等，将方程化为等，将方程化为等，将方程化为等价方程价方程价方程价方程x x=(x x)，并在，并在，并在，并在 a a,b b 内任取一点内任取一点内任取一点内任取一点x x0 0作为初始近似作为初始近似作为初始近似作为初始近似值，然后按迭代公式计第二章值，然后按迭代公式计第二章值，然后按迭代公式计第二章值，然后按迭代公式计第二章 非线性方程求解算：非线性方程求解算：非线性方程求解算：非线性方程求解算：产生迭代序列产生迭代序列产生迭代序列产生迭代序列x x0 0,x x1 1,x xn n,显然，若显然，若显然，若显然，若 x xn n 收敛于收敛于收敛于收敛于x x*，(x x)在在在在x x*处连续，就有处连续，就有处连续，就有处连续，就有:这种求根办法称为这种求根办法称为这种求根办法称为这种求根办法称为迭代法迭代法迭代法迭代法，式（，式（，式（，式（2-32-3）称为）称为）称为）称为迭代格式迭代格式迭代格式迭代格式，(x x)称为称为称为称为迭代函数迭代函数迭代函数迭代函数，x x0 0称为称为称为称为迭代初值迭代初值迭代初值迭代初值，x xn n 称为称为称为称为迭代序列迭代序列迭代序列迭代序列假如迭代序列收敛，则称迭代格式（假如迭代序列收敛，则称迭代格式（假如迭代序列收敛，则称迭代格式（假如迭代序列收敛，则称迭代格式（2-32-3）收敛，不）收敛，不）收敛，不）收敛，不然称为发散。然称为发散。然称为发散。然称为发散。即：即：即：即：x x*是方程是方程是方程是方程f f(x x)=0)=0解。解。解。解。故：当故：当故：当故：当n n充足大时，可取充足大时，可取充足大时，可取充足大时，可取x xn n作为方程近似解。作为方程近似解。作为方程近似解。作为方程近似解。满足x=(x)点点x也称为不动点也称为不动点第16页第16页第二章第二章非线性方程求解非线性方程求解返回前进例例4解：容易验证，解：容易验证，解：容易验证，解：容易验证，方程在方程在方程在方程在1,21,2内内内内有根，取有根，取有根，取有根，取x x0 0=1.5=1.5第17页第17页第二章第二章非线性方程求解非线性方程求解返回前进n nx xn nn nx xn n0 01.51.58 81.59449341.59449341 11.63265311.63265319 91.59459001.59459002 21.57908581.579085810101.59455081.59455083 31.60083091.600830911111.59456671.59456674 41.5961.59612121.59456031.59456035 51.59559281.595592813131.59456291.59456296 61.59414421.594144214141.59456181.59456187 71.59473151.594731515151.59456221.5945622第18页第18页第二章第二章非线性方程求解非线性方程求解返回前进迭代法举例续例例例例5 5 解：解：解：解：对方程进行变换，可得下列三种等价形式：对方程进行变换，可得下列三种等价形式：对方程进行变换，可得下列三种等价形式：对方程进行变换，可得下列三种等价形式：分别按以上三种分别按以上三种分别按以上三种分别按以上三种形式建立迭代格式，形式建立迭代格式，形式建立迭代格式，形式建立迭代格式，并取并取并取并取x x00=1=1进行迭代进行迭代进行迭代进行迭代计算，结果下列：计算，结果下列：计算，结果下列：计算，结果下列：例5计算结果表明：将一方程化为等价方程方法很多，由此可结构许多不同迭代函数，得到各种迭代格式。而它们所产生迭代序列则可能收敛，也可能发散，可能收敛很快，也可能收敛很慢。迭代法收敛性取决于迭代函数在方程根邻近性态。第19页第19页第二章第二章非线性方程求解非线性方程求解返回前进迭代法几何含义从几何上看，迭代法是将求曲线从几何上看，迭代法是将求曲线从几何上看，迭代法是将求曲线从几何上看，迭代法是将求曲线y y=f f(x x)零点问题化为零点问题化为零点问题化为零点问题化为求曲线求曲线求曲线求曲线y y=(x x)与直线与直线与直线与直线y y=x x交点，迭代过程如图交点，迭代过程如图交点，迭代过程如图交点，迭代过程如图2-22-2所表所表所表所表示，从初始点示，从初始点示，从初始点示，从初始点x x0 0出发，沿直线出发，沿直线出发，沿直线出发，沿直线x x=x x0 0走到曲线走到曲线走到曲线走到曲线y y=(x x)，得，得，得，得点点点点(x x0 0,(x x0 0)，再沿直线，再沿直线，再沿直线，再沿直线y y=(x x0 0)走到直线走到直线走到直线走到直线y y=x x，交点，交点，交点，交点为为为为(x x1 1,(x(x1)1)，如此继续下去，越来越靠近点，如此继续下去，越来越靠近点，如此继续下去，越来越靠近点，如此继续下去，越来越靠近点(x x*,*,x x*)*)。y=xy=(x)xx0 x2x*x1xyy y=x xy y=(x x)x x2 2x x0 0 x*x x1 1图图图图8-28-2第20页第20页第二章第二章非线性方程求解非线性方程求解返回前进当然，迭代过程也也许出现图当然，迭代过程也也许出现图当然，迭代过程也也许出现图当然，迭代过程也也许出现图8-38-3所表示情况，此时点所表示情况，此时点所表示情况，此时点所表示情况，此时点(x xn n,x xn n)越来越远离交点越来越远离交点越来越远离交点越来越远离交点(x x*,*,x x*)*)，迭代序列发散，迭代序列发散，迭代序列发散，迭代序列发散。yy=xy=(x)xx2x0 x*x3x1y=xy=(x)xx2x0 x*x1图图图图8-38-3由此可见，使用迭代法必须处理两个问题：一是迭代由此可见，使用迭代法必须处理两个问题：一是迭代由此可见，使用迭代法必须处理两个问题：一是迭代由此可见，使用迭代法必须处理两个问题：一是迭代格式满足什么条件才干确保收敛；二是如何判别迭代收敛格式满足什么条件才干确保收敛；二是如何判别迭代收敛格式满足什么条件才干确保收敛；二是如何判别迭代收敛格式满足什么条件才干确保收敛；二是如何判别迭代收敛速度，建立收敛快迭代格式。速度，建立收敛快迭代格式。速度，建立收敛快迭代格式。速度，建立收敛快迭代格式。迭代法几何含义（续）第21页第21页第二章第二章非线性方程求解非线性方程求解返回前进2.2迭代法收敛条件（三大定理）定理定理2.6（压缩映象原理）（压缩映象原理）（压缩映象原理）（压缩映象原理）设函数设函数设函数设函数 (x x)在区间在区间在区间在区间 a a,b b 上满足条件：上满足条件：上满足条件：上满足条件：则方程则方程则方程则方程x x=(x x)在在在在 a a,b b 内有唯一内有唯一内有唯一内有唯一根根根根x x*，且对任意，且对任意，且对任意，且对任意初值初值初值初值x x00 a a,b b，迭代序列：迭代序列：迭代序列：迭代序列：证实见下屏：证实见下屏：证实见下屏：证实见下屏：第23页第23页第二章第二章非线性方程求解非线性方程求解返回前进压缩映象原理证实由条件（由条件（由条件（由条件（2 2）易得）易得）易得）易得 (x x)在在在在 a a,b b 上连续。上连续。上连续。上连续。令令令令 (x x)=)=x x (x x)，则，则，则，则 (x x)也在也在也在也在 a a,b b 上连续，且：上连续，且：上连续，且：上连续，且：由连续函数介值定理，存在由连续函数介值定理，存在由连续函数介值定理，存在由连续函数介值定理，存在 a a,b b，使得，使得，使得，使得 ()=0)=0，即即即即 =()因此方程因此方程因此方程因此方程x=x=(x x)在在在在 a a,b b 内有根。内有根。内有根。内有根。假设方程假设方程假设方程假设方程x=x=(x x)在在在在 a a,b b 内有两个根内有两个根内有两个根内有两个根x x1 1*x x2 2*，由，由，由，由条件（条件（条件（条件（2 2）有：）有：）有：）有：导出矛盾，唯一性得证。导出矛盾，唯一性得证。导出矛盾，唯一性得证。导出矛盾，唯一性得证。（存在性）（存在性）（唯一性）（唯一性）第24页第24页第二章第二章非线性方程求解非线性方程求解返回前进对任意对任意x0 a,b，由迭代公式有：，由迭代公式有：即对任意初值即对任意初值x0 a,b，迭代序列迭代序列xn均收敛到方程均收敛到方程根根x*。压缩映象原理证实（续1）（收敛性）（收敛性）第25页第25页第二章第二章非线性方程求解非线性方程求解返回前进类似地，对任意正整数类似地，对任意正整数类似地，对任意正整数类似地，对任意正整数K K，有，有，有，有：定理定理定理定理2.62.6证实中两个误差预计式证实中两个误差预计式证实中两个误差预计式证实中两个误差预计式（2-52-5）,（2-62-6）是很故意义。）是很故意义。）是很故意义。）是很故意义。（误差预计公式）（误差预计公式）利用利用利用利用第27页第27页第二章第二章非线性方程求解非线性方程求解返回前进两个主要误差公式阐明1.式（式（式（式（2-52-5）阐明，在正常情况下，即）阐明，在正常情况下，即）阐明，在正常情况下，即）阐明，在正常情况下，即L L不太靠近于不太靠近于不太靠近于不太靠近于1 1（若（若（若（若L L靠近于靠近于靠近于靠近于1 1，则收敛速度很慢），可用相邻两次迭代值，则收敛速度很慢），可用相邻两次迭代值，则收敛速度很慢），可用相邻两次迭代值，则收敛速度很慢），可用相邻两次迭代值之差绝对值来预计误差，控制迭代次数。之差绝对值来预计误差，控制迭代次数。之差绝对值来预计误差，控制迭代次数。之差绝对值来预计误差，控制迭代次数。就停止计算，取就停止计算，取就停止计算，取就停止计算，取x xn n作为方程近似根。这种用相邻两次计算作为方程近似根。这种用相邻两次计算作为方程近似根。这种用相邻两次计算作为方程近似根。这种用相邻两次计算结果来预计误差办法，称为结果来预计误差办法，称为结果来预计误差办法，称为结果来预计误差办法，称为事后预计法事后预计法。即当给定精度即当给定精度即当给定精度即当给定精度时，假如有：时，假如有：时，假如有：时，假如有：第28页第28页第二章第二章非线性方程求解非线性方程求解返回前进2.而式（而式（而式（而式（2-62-6）误差预计，称为）误差预计，称为）误差预计，称为）误差预计，称为事前预计法事前预计法，由于用它，由于用它，由于用它，由于用它能够预计出要达到给定精度能够预计出要达到给定精度能够预计出要达到给定精度能够预计出要达到给定精度 所需次数所需次数所需次数所需次数n事实上，由事实上，由事实上，由事实上，由 注意：注意：定理定理定理定理2.62.6给出了判别迭代收敛给出了判别迭代收敛给出了判别迭代收敛给出了判别迭代收敛 充足条件。在实际计算时，由于充足条件。在实际计算时，由于充足条件。在实际计算时，由于充足条件。在实际计算时，由于L L比较难求，而我们所讨比较难求，而我们所讨比较难求，而我们所讨比较难求，而我们所讨 论函数通常是可导函数，因此，实用收敛条件是用论函数通常是可导函数，因此，实用收敛条件是用论函数通常是可导函数，因此，实用收敛条件是用论函数通常是可导函数，因此，实用收敛条件是用 导数界得到。见下屏：导数界得到。见下屏：导数界得到。见下屏：导数界得到。见下屏：第29页第29页第二章第二章非线性方程求解非线性方程求解返回前进迭代法收敛条件之二推论推论推论推论1 1（1 1）对任意）对任意）对任意）对任意x x a a,b b，有，有，有，有 (x x)a a,b b；（2 2）存在常数）存在常数）存在常数）存在常数00L L 11，使得对任意，使得对任意，使得对任意，使得对任意x x a a,b b，都有：，都有：，都有：，都有：则方程则方程则方程则方程x x=(x x)在在在在 a a,b b 上有唯一根上有唯一根上有唯一根上有唯一根x x*，且对任意初值，且对任意初值，且对任意初值，且对任意初值x x0 0 a a,b b，迭代序列，迭代序列，迭代序列，迭代序列：均收敛于均收敛于均收敛于均收敛于x x*，并有：，并有：，并有：，并有：证实见下屏：证实见下屏：证实见下屏：证实见下屏：设函数设函数设函数设函数 (x x)在区间在区间在区间在区间 a a,b b 上满足条件：上满足条件：上满足条件：上满足条件：第30页第30页第二章第二章非线性方程求解非线性方程求解返回前进证实设设x,y为为a,b上任意两点，由微分中值定理，在上任意两点，由微分中值定理，在 x,y之间至少存在一点之间至少存在一点，使得，使得:于是：于是：即即(x)满足定理满足定理2.6条件（条件（2），故结论成立。），故结论成立。第31页第31页第二章第二章非线性方程求解非线性方程求解返回前进推论1应用举例采用三种迭代格式，采用三种迭代格式，采用三种迭代格式，采用三种迭代格式，在隔根区间（在隔根区间（在隔根区间（在隔根区间（1,1.21,1.2）内有：）内有：）内有：）内有：用推论用推论1判别简朴迭代法收敛性比定理判别简朴迭代法收敛性比定理2.6以便以便如对例题如对例题5：第32页第32页第二章第二章非线性方程求解非线性方程求解返回前进第一个迭代格式发散，第二、三种迭代格式收敛且第第一个迭代格式发散，第二、三种迭代格式收敛且第第一个迭代格式发散，第二、三种迭代格式收敛且第第一个迭代格式发散，第二、三种迭代格式收敛且第三种迭代格式比第二种迭代格式中三种迭代格式比第二种迭代格式中三种迭代格式比第二种迭代格式中三种迭代格式比第二种迭代格式中L L要小，因而收敛要快要小，因而收敛要快要小，因而收敛要快要小，因而收敛要快得多，这与实际迭代结果完全吻合。得多，这与实际迭代结果完全吻合。得多，这与实际迭代结果完全吻合。得多，这与实际迭代结果完全吻合。故可取故可取故可取故可取n n=7=7，只需迭代，只需迭代，只需迭代，只需迭代7 7次就可达到所要求精度。次就可达到所要求精度。次就可达到所要求精度。次就可达到所要求精度。依据推论依据推论1可知，可知，对第三种迭代格式，为使与方程近似根误差不超出对第三种迭代格式，为使与方程近似根误差不超出对第三种迭代格式，为使与方程近似根误差不超出对第三种迭代格式，为使与方程近似根误差不超出1010-6-6，可预计迭代次数：，可预计迭代次数：，可预计迭代次数：，可预计迭代次数：第33页第33页第二章第二章非线性方程求解非线性方程求解返回前进应用举例LeonardoLeonardo于于于于12251225年研究了方程年研究了方程年研究了方程年研究了方程曾经轰动一时，由于没有些人知道他用是什么办法。曾经轰动一时，由于没有些人知道他用是什么办法。曾经轰动一时，由于没有些人知道他用是什么办法。曾经轰动一时，由于没有些人知道他用是什么办法。我们现在可用迭代法求解：我们现在可用迭代法求解：我们现在可用迭代法求解：我们现在可用迭代法求解：还可用还可用还可用还可用NewtonNewton法，法，法，法，弦截法求解弦截法求解弦截法求解弦截法求解第34页第34页第二章第二章非线性方程求解非线性方程求解返回前进迭代法收敛条件之三定理定理2.7 第35页第35页第二章第二章非线性方程求解非线性方程求解返回前进定理定理定理定理2.32.3强调迭代初值强调迭代初值强调迭代初值强调迭代初值x x0 0应取在根应取在根应取在根应取在根x x*邻域中。假如对任邻域中。假如对任邻域中。假如对任邻域中。假如对任意给定意给定意给定意给定x x0 0，迭代格式均收敛，则称此格式含有，迭代格式均收敛，则称此格式含有，迭代格式均收敛，则称此格式含有，迭代格式均收敛，则称此格式含有全局收敛性全局收敛性全局收敛性全局收敛性，但这样格式是极其稀少。假如对根但这样格式是极其稀少。假如对根但这样格式是极其稀少。假如对根但这样格式是极其稀少。假如对根x x*某邻域内任一点某邻域内任一点某邻域内任一点某邻域内任一点x x0 0，迭代格式均收敛，则此格式含有迭代格式均收敛，则此格式含有迭代格式均收敛，则此格式含有迭代格式均收敛，则此格式含有局部收敛性局部收敛性局部收敛性局部收敛性。即可确保对其中任取一点即可确保对其中任取一点即可确保对其中任取一点即可确保对其中任取一点x x0 0迭代收敛。事实上，在用迭代迭代收敛。事实上，在用迭代迭代收敛。事实上，在用迭代迭代收敛。事实上，在用迭代法求解方程（法求解方程（法求解方程（法求解方程（2-12-1）时，经常先用对分区间求得较好初值，）时，经常先用对分区间求得较好初值，）时，经常先用对分区间求得较好初值，）时，经常先用对分区间求得较好初值，然后再进行迭代。然后再进行迭代。然后再进行迭代。然后再进行迭代。本定理给出就是局部收敛性条件本定理给出就是局部收敛性条件本定理给出就是局部收敛性条件本定理给出就是局部收敛性条件。详细解题时，即使无。详细解题时，即使无。详细解题时，即使无。详细解题时，即使无法判别隔根区间是否为以法判别隔根区间是否为以法判别隔根区间是否为以法判别隔根区间是否为以x x*为中心邻域，但只要它足够小，为中心邻域，但只要它足够小，为中心邻域，但只要它足够小，为中心邻域，但只要它足够小，且在邻域中满足：且在邻域中满足：且在邻域中满足：且在邻域中满足：第36页第36页第二章第二章非线性方程求解非线性方程求解返回前进2.3Steffensen方程简朴迭代法加速收敛速度（收敛速度阶）：收敛速度（收敛速度阶）：成立，则称成立，则称xn是是r 阶收敛，或称阶收敛，或称xn收敛阶为收敛阶为r，收敛阶收敛阶r 大小刻划了序列大小刻划了序列xn收敛速度：收敛速度：r 越大，收敛越快越大，收敛越快:r=1线性收敛线性收敛r 1超线性收敛超线性收敛r=2平方收敛平方收敛设序列设序列xn收敛于收敛于x*，若存在正数，若存在正数r和和a使得：使得：第37页第37页第二章第二章非线性方程求解非线性方程求解返回前进xnr 阶收敛定理定理定理2.8设迭代函数设迭代函数(x)在在x*邻近有邻近有r阶连续导数，阶连续导数，且且x*=(x*)，并且有，并且有证实：证实：1）(x)满足收敛定理条件满足收敛定理条件xnx*；紧接下屏紧接下屏紧接下屏紧接下屏第38页第38页第二章第二章非线性方程求解非线性方程求解返回前进2 2）利用）利用）利用）利用TaylorTaylor公式将公式将公式将公式将 (x x)在在在在x x*附近展开：附近展开：附近展开：附近展开：这表明：这表明：这表明：这表明：x xn n 是是是是r r阶收敛。阶收敛。阶收敛。阶收敛。一阶收敛即为线性收敛，收敛速度较慢，下面想法加速：一阶收敛即为线性收敛，收敛速度较慢，下面想法加速：一阶收敛即为线性收敛，收敛速度较慢，下面想法加速：一阶收敛即为线性收敛，收敛速度较慢，下面想法加速：第39页第39页第二章第二章非线性方程求解非线性方程求解返回前进第40页第40页第二章第二章非线性方程求解非线性方程求解返回前进第41页第41页第二章第二章非线性方程求解非线性方程求解返回前进1、Aitken加速法若序列若序列xn线性收敛于线性收敛于x*，可按式：，可按式：当当当当n n充足大时，有：充足大时，有：充足大时，有：充足大时，有：紧接下屏紧接下屏紧接下屏紧接下屏第42页第42页第二章第二章非线性方程求解非线性方程求解返回前进Aitken加速法（续）由此式可推导出：由此式可推导出：由此式可推导出：由此式可推导出：由此可得比值：由此可得比值：由此可得比值：由此可得比值：第43页第43页第二章第二章非线性方程求解非线性方程求解返回前进第44页第44页第二章第二章非线性方程求解非线性方程求解返回前进3Newton法与弦截法3.13.1Newton法法法法 将非线性方程线性化，以线性方程解逐步迫近非线性将非线性方程线性化，以线性方程解逐步迫近非线性将非线性方程线性化，以线性方程解逐步迫近非线性将非线性方程线性化，以线性方程解逐步迫近非线性方程解，这就是方程解，这就是方程解，这就是方程解，这就是NewtonNewton法基本思想法基本思想法基本思想法基本思想。设已知方程设已知方程设已知方程设已知方程f f(x x)=0)=0近似根近似根近似根近似根