电子科大数值分析非线性方程求根省公共课一等奖全国赛课获奖课件.pptx

第二章第二章 非线性方程求根方法非线性方程求根方法第1页第二章第二章 非线性方程求根方法非线性方程求根方法n n引言引言n n方程求根二分法方程求根二分法n n迭代法及其收敛性迭代法及其收敛性n nNewton迭代法迭代法第2页n n方程是在科学研究中不可缺乏工具；方程是在科学研究中不可缺乏工具；方程是在科学研究中不可缺乏工具；方程是在科学研究中不可缺乏工具；n n方程求解是科学计算中一个主要研究对象；方程求解是科学计算中一个主要研究对象；方程求解是科学计算中一个主要研究对象；方程求解是科学计算中一个主要研究对象；n n几百年前就已经找到了代数方程中二次至五次方程几百年前就已经找到了代数方程中二次至五次方程几百年前就已经找到了代数方程中二次至五次方程几百年前就已经找到了代数方程中二次至五次方程求解公式；求解公式；求解公式；求解公式；n n不过，对于更高次数代数方程当前仍无有效准确解不过，对于更高次数代数方程当前仍无有效准确解不过，对于更高次数代数方程当前仍无有效准确解不过，对于更高次数代数方程当前仍无有效准确解法；法；法；法；n n对于无规律非代数方程求解也无准确解法；对于无规律非代数方程求解也无准确解法；对于无规律非代数方程求解也无准确解法；对于无规律非代数方程求解也无准确解法；n n所以，研究非线性方程数值解法成为必定。所以，研究非线性方程数值解法成为必定。所以，研究非线性方程数值解法成为必定。所以，研究非线性方程数值解法成为必定。2.1 引言引言第3页非线性方程普通形式：非线性方程普通形式：非线性方程普通形式：非线性方程普通形式：f f(x x)=0 0代数方程：代数方程：代数方程：代数方程：f f(x x)=a=a0 0+a+a1 1x+ax+an nx xn n （a an n 0 0）超越方程超越方程：f f(x x)中含三角函数、指数函数、或其中含三角函数、指数函数、或其它超越函数。它超越函数。用数值方法求解非线性方程步骤：用数值方法求解非线性方程步骤：（1）找出隔根区间；（只含一个实根区间称隔根区）找出隔根区间；（只含一个实根区间称隔根区间）间）（2）近似根准确化。从隔根区间内一个或多个点出）近似根准确化。从隔根区间内一个或多个点出发，逐次迫近，寻求满足精度根近似值。发，逐次迫近，寻求满足精度根近似值。第4页2.2 方程求根二分法方程求根二分法n n定理定理定理定理1 1（介值定理）设函数（介值定理）设函数（介值定理）设函数（介值定理）设函数f f(x x)在区间在区间在区间在区间 a a,b b 连续，连续，连续，连续，且且且且f f(a a)f f(b b)0)0)0，则则则则x x*在在在在x x0 0右侧，令右侧，令右侧，令右侧，令a a1 1=x x0 0，b b1 1=b b;（2 2）若）若）若）若f f(x x0 0)f f(a a)0)0，则则则则x x*在在在在x x0 0左侧，令左侧，令左侧，令左侧，令a a1 1=a a，b b1 1=x x0 0。第5页以以以以 a a1 1,b b1 1 为新隔根区间，且仅为为新隔根区间，且仅为为新隔根区间，且仅为为新隔根区间，且仅为 a a,b b 二分之一，对二分之一，对二分之一，对二分之一，对 a a1 1,b b1 1 重复前过程，得新隔根区间重复前过程，得新隔根区间重复前过程，得新隔根区间重复前过程，得新隔根区间 a a2 2,b b2 2，如此二分下去，得一系列隔根区间：如此二分下去，得一系列隔根区间：如此二分下去，得一系列隔根区间：如此二分下去，得一系列隔根区间：a a,b b a a1 1,b b1 1 a a2 2,b b2 2 a ak k,b bk k 其中每个区间都是前一区间二分之一，故其中每个区间都是前一区间二分之一，故其中每个区间都是前一区间二分之一，故其中每个区间都是前一区间二分之一，故 a ak k,b bk k 长度：长度：长度：长度：当当当当k k趋于无穷时趋于趋于无穷时趋于趋于无穷时趋于趋于无穷时趋于0 0。即若二分过程无限继续下去，这些区间最终必收敛于即若二分过程无限继续下去，这些区间最终必收敛于即若二分过程无限继续下去，这些区间最终必收敛于即若二分过程无限继续下去，这些区间最终必收敛于一点一点一点一点x x*，即方程根。即方程根。即方程根。即方程根。第6页n n二分法性质：二分法性质：uuf(an)f(bn)0;uubn an=(b a)/2n实际计算中，若给定充分小正数实际计算中，若给定充分小正数实际计算中，若给定充分小正数实际计算中，若给定充分小正数 0 0和允许误差限和允许误差限和允许误差限和允许误差限 1 1，当，当，当，当|f f(x xn n)|)|0 0或或或或b bn n-a an n 1 1时，均可取时，均可取时，均可取时，均可取x x*x xn n。每次二分后，取有根区间中点每次二分后，取有根区间中点每次二分后，取有根区间中点每次二分后，取有根区间中点x xk k=(a ak k+b bk k)/2)/2作为作为作为作为根近似值，则可得一近似根序列：根近似值，则可得一近似根序列：根近似值，则可得一近似根序列：根近似值，则可得一近似根序列：x x0 0,x x1 1,x x2 2,该序该序该序该序列必以根列必以根列必以根列必以根x x*为极限。为极限。为极限。为极限。第7页n n定理定理2 设设设设x x*为方程为方程为方程为方程f f(x x)=0)=0在在在在 a a,b b 内唯一根，且内唯一根，且内唯一根，且内唯一根，且f f(x x)满满满满足足足足f f(a)(a)f f(b b)0)0，则由二分法产生第，则由二分法产生第，则由二分法产生第，则由二分法产生第n n个区间个区间个区间个区间 a an n,b bn n 中点中点中点中点x xn n满足不等式满足不等式满足不等式满足不等式证实：证实：第8页n n计算过程简单，收敛性可确保；计算过程简单，收敛性可确保；n n对函数性质要求低，只要连续即可。对函数性质要求低，只要连续即可。n n收敛速度慢；收敛速度慢；n n不能求复根和重根；不能求复根和重根；n n调用一次求解一个调用一次求解一个a,b间多个根无法求间多个根无法求得。得。二分法求解非线性方程优缺点：二分法求解非线性方程优缺点：第9页n n不动点迭代法不动点迭代法n n不动点存在性与迭代法收敛性不动点存在性与迭代法收敛性n n迭代收敛加速方法迭代收敛加速方法2.3 迭代法及其收敛性迭代法及其收敛性第10页迭代法基本思想：迭代法基本思想：迭代法是一个逐次迫近方法，用某个固定公式重迭代法是一个逐次迫近方法，用某个固定公式重迭代法是一个逐次迫近方法，用某个固定公式重迭代法是一个逐次迫近方法，用某个固定公式重复校正根近似值，使之逐步准确化，最终得到满足复校正根近似值，使之逐步准确化，最终得到满足复校正根近似值，使之逐步准确化，最终得到满足复校正根近似值，使之逐步准确化，最终得到满足精度要求结果。精度要求结果。精度要求结果。精度要求结果。例：求方程例：求方程例：求方程例：求方程 x x3 3-x x-1=0-1=0 在在在在 x x=1.5=1.5 附近一个根。附近一个根。附近一个根。附近一个根。解：将所给方程改写成解：将所给方程改写成解：将所给方程改写成解：将所给方程改写成假设初值假设初值假设初值假设初值x x0 0=1.5=1.5是其根，代入得是其根，代入得是其根，代入得是其根，代入得第11页x x1 1 x x0 0，再将，再将，再将，再将x x1 1代入得代入得代入得代入得x x2 2 x x1 1，再将，再将，再将，再将x x2 2代入得代入得代入得代入得如此下去，这种逐步校正过程称为如此下去，这种逐步校正过程称为如此下去，这种逐步校正过程称为如此下去，这种逐步校正过程称为迭代过程迭代过程迭代过程迭代过程。这里用公式称为这里用公式称为这里用公式称为这里用公式称为迭代公式迭代公式迭代公式迭代公式，即，即，即，即k k=0,1,2,=0,1,2,第12页迭代结果见下表：迭代结果见下表：迭代结果见下表：迭代结果见下表：k k x xk k k k x xk k0 01 12 23 34 41.51.51.357211.357211.330861.330861.325881.325881.324941.324945 56 67 78 81.324761.324761.324731.324731.324721.324721.324721.32472仅取六位数字，仅取六位数字，仅取六位数字，仅取六位数字，x x7 7与与与与x x8 8相同，即认为相同，即认为相同，即认为相同，即认为x x8 8是是是是方程根。方程根。方程根。方程根。x x*x x8 8=1.32472=1.32472第13页2.3.1 不动点迭代法不动点迭代法n n将连续函数方程将连续函数方程将连续函数方程将连续函数方程f f(x x)0 0改写为等价形式：改写为等价形式：改写为等价形式：改写为等价形式：x=x=(x x)其中其中其中其中 (x x)也是连续函数，称为迭代函数。也是连续函数，称为迭代函数。也是连续函数，称为迭代函数。也是连续函数，称为迭代函数。不动点不动点不动点不动点：若：若：若：若x x*满足满足满足满足f f(x*x*)=0 0，则则则则x*=x*=(x*x*)；反之，若反之，若反之，若反之，若x*=x*=(x*x*)，则，则，则，则f f(x*x*)=0 0 ，称，称，称，称x x*为为为为 (x x)一个不动点。一个不动点。一个不动点。一个不动点。不动点迭代不动点迭代不动点迭代不动点迭代：(k k=0,1,)=0,1,)若对任意若对任意若对任意若对任意 x x0 0 a a,b b，由上述迭代得序列由上述迭代得序列由上述迭代得序列由上述迭代得序列 x xk k，有极限，有极限，有极限，有极限则称迭代过程则称迭代过程则称迭代过程则称迭代过程收敛收敛收敛收敛，且，且，且，且x x*=*=(x x*)*)为为为为 (x x)不动点。不动点。不动点。不动点。第14页x2 x1 x0y=x几何意义：几何意义：第15页n n但迭代法并不总令人满意，如将前述方程但迭代法并不总令人满意，如将前述方程但迭代法并不总令人满意，如将前述方程但迭代法并不总令人满意，如将前述方程x x3 3-x x-1=0-1=0改写为另一等价形式：改写为另一等价形式：改写为另一等价形式：改写为另一等价形式：此时称迭代过程此时称迭代过程发散发散。则有则有x1=2.375，x2=12.396，x3=1904,结果越来越大。结果越来越大。仍取初值仍取初值x0=1.5，建迭代公式：建迭代公式：第16页收敛收敛 发散发散 第17页n n定理定理3（存在性）（存在性）设设(x)Ca,b且满足以下且满足以下两个条件：两个条件：uu（1）对于任意）对于任意x a,b，有，有a(x)b；uu（2 2）若）若(x)在在a,b一阶连续，且一阶连续，且存在常数存在常数0 0L1，使得对任意，使得对任意x a,b，成立成立|(x)|L则则(x)在在a,b上存在唯一不动点上存在唯一不动点x*。2.3.2 不动点存在性与迭代法收敛性不动点存在性与迭代法收敛性第18页不动点存在性证实：不动点存在性证实：证：证：若若或或显然显然 (x)有不动点；有不动点；不然，设不然，设则有则有（因（因a(x)b）记记则有则有故存在故存在x*使得使得即即x*即为不动点。即为不动点。第19页不动点存在唯一性证实：不动点存在唯一性证实：设有设有 x1*x2*,使得使得则则其中，其中，介于介于 x1*和和 x2*之间。之间。由定理条件由定理条件可得可得矛盾！矛盾！故故 x1*=x2*，不动点唯一存在。，不动点唯一存在。第20页定理定理4（全局收敛性）（全局收敛性）设设(x x)C a a,b b 且满足以下两个条件：且满足以下两个条件：则对任意则对任意x0 a a,b b，由由xn+1=(xn)得到迭代序列得到迭代序列xn 收敛到收敛到(x x)不动点不动点x x*，并有误差预计：并有误差预计：（2）若若(x)在在a,b一阶连续，且存在常数一阶连续，且存在常数0L1，使得对任意使得对任意x a,b，成立，成立|(x)|L（1）对于任意）对于任意x a,b，有有a(x)b；第21页(0L1)故迭代格式收敛。故迭代格式收敛。所以所以证实：证实：第22页重复递推，可得误差预计式重复递推，可得误差预计式第23页n n定义定义 设设(x)有不动点有不动点x*，若存在，若存在x*某邻域某邻域R：|x-x*|，对任意，对任意x0 R，迭代过程，迭代过程xk+1=(xk)产生序列产生序列xk R且收敛到且收敛到x*，则称不动，则称不动点迭代法点迭代法xk+1=(xk)局部收敛局部收敛。定理定理定理定理4 4给出收敛性称全局收敛性，实际应用时给出收敛性称全局收敛性，实际应用时给出收敛性称全局收敛性，实际应用时给出收敛性称全局收敛性，实际应用时通常只在不动点通常只在不动点通常只在不动点通常只在不动点x x*邻近考查其收敛性，称局部收敛邻近考查其收敛性，称局部收敛邻近考查其收敛性，称局部收敛邻近考查其收敛性，称局部收敛性。性。性。性。第24页n n证实证实证实证实：依据连续函数性质，因：依据连续函数性质，因：依据连续函数性质，因：依据连续函数性质，因 (x x)连续，存在连续，存在连续，存在连续，存在x x*某邻某邻某邻某邻域域域域R R：|x-x*|x-x*|，对任意，对任意，对任意，对任意x x R R，|(x)|(x)|L L11，且，且，且，且|(x x)-x*|=|-x*|=|(x x)-(x*x*)|=|=|()|x-x*|x-x*|L|x-x*|L|x-x*|x-x*|x-x*|即对任意即对任意即对任意即对任意x x R R，总有总有总有总有 (x x)R R。由全局收敛性定义知，迭代过程由全局收敛性定义知，迭代过程由全局收敛性定义知，迭代过程由全局收敛性定义知，迭代过程 x xk k+1+1=(x xk k )对于任意初对于任意初对于任意初对于任意初值值值值x x0 0 R R均收敛。均收敛。均收敛。均收敛。n n定理定理5（局部收敛性）（局部收敛性）设设x*为为(x)不动点，不动点，(x)在在x*某邻域连续，且某邻域连续，且|(x*)|11时称时称时称时称超线性收敛超线性收敛超线性收敛超线性收敛。且且且且r r 越大，收敛越快。越大，收敛越快。越大，收敛越快。越大，收敛越快。第28页n n定理定理定理定理：设：设：设：设x x*为为为为x x=(x x )不动点，若不动点，若不动点，若不动点，若 (x x )满足：满足：满足：满足：uu（1 1）(x x )在在在在x x*附近是附近是附近是附近是p p次连续可微次连续可微次连续可微次连续可微(p p1)1)；uu（2 2）则迭代过程则迭代过程则迭代过程则迭代过程x xn n+1+1=(x xn n)在点在点在点在点x x*邻近是邻近是邻近是邻近是p p阶收敛。阶收敛。阶收敛。阶收敛。得得得得所以所以所以所以故故故故迭代过程迭代过程迭代过程迭代过程x xn n+1+1=(x xn n )p p阶收敛。阶收敛。阶收敛。阶收敛。n n证：证：证：证：由由Taylor公式公式第29页假定假定假定假定 (x x )改变不大，近似取某个近似值改变不大，近似取某个近似值改变不大，近似取某个近似值改变不大，近似取某个近似值L L，则有，则有，则有，则有2.3.3 迭代收敛加速方法迭代收敛加速方法一、一、Aitken加速收敛方法：加速收敛方法：由微分中值定理，有由微分中值定理，有由微分中值定理，有由微分中值定理，有同理同理同理同理两式相比，得两式相比，得两式相比，得两式相比，得第30页类推可得类推可得类推可得类推可得故故故故上式即为上式即为上式即为上式即为AitkenAitken加速收敛方法迭代格式。加速收敛方法迭代格式。加速收敛方法迭代格式。加速收敛方法迭代格式。第31页将将将将AitkenAitken加速技巧与不动点结合可得加速技巧与不动点结合可得加速技巧与不动点结合可得加速技巧与不动点结合可得或将其写为或将其写为二、二、Steffensen迭代法：迭代法：第32页解解解解：由前知，迭代格式：由前知，迭代格式：由前知，迭代格式：由前知，迭代格式 x xk k+1+1=x xk k3 3-1-1 是发散。现用是发散。现用是发散。现用是发散。现用steffensensteffensen迭代法计算。取迭代法计算。取迭代法计算。取迭代法计算。取 (x x )=)=x x3 3-1-1，结果以下：，结果以下：，结果以下：，结果以下：k k x xk k y yk k z zk k0 01 12 23 34 45 51.51.51.416291.416291.355651.355651.328951.328951.324801.324801.324721.324722.375002.375001.840921.840921.491401.491401.347101.347101.325181.3251812.396512.39655.238885.238882.317282.317281.444351.444351.327141.32714表明即使不动点迭代法不收敛，用表明即使不动点迭代法不收敛，用steffensen迭迭代法仍可能收敛。代法仍可能收敛。例例例例：用：用：用：用steffensensteffensen迭代法求解方程迭代法求解方程迭代法求解方程迭代法求解方程 x x3 3-x x-1=0-1=0。第33页求方程求方程求方程求方程在在在在3,43,4中解。中解。中解。中解。例例解解由由由由取对数取对数取对数取对数结构迭代格式结构迭代格式结构迭代格式结构迭代格式故故故故当当当当x x 3,43,4时，时，时，时，(x)3,43,4，且，且，且，且故迭代格式收敛。故迭代格式收敛。故迭代格式收敛。故迭代格式收敛。第34页取取取取x x0 0=3.5=3.5，经计算可得迭代，经计算可得迭代，经计算可得迭代，经计算可得迭代1616次后次后次后次后x x1616=3.73307=3.73307，有有有有6 6位有效数字。位有效数字。位有效数字。位有效数字。若用若用若用若用steffensensteffensen迭代法加速，结果以下：迭代法加速，结果以下：迭代法加速，结果以下：迭代法加速，结果以下：k k xk k yk k zk k0 03.53.53.604143.604143.662023.662021 13.734443.734443.733813.733813.733473.733472 23.733073.73307说明说明steffensen迭代法收敛速度比不动点迭代迭代法收敛速度比不动点迭代快得多。快得多。第35页1.不动点存在性与迭代法收敛性不动点存在性与迭代法收敛性前一次课内容回顾前一次课内容回顾2.收敛阶判定收敛阶判定3.迭代收敛加速方法迭代收敛加速方法4.Steffensen迭代法迭代法第36页n nNewton迭代法及其收敛性迭代法及其收敛性n n简化简化Newton迭代法（平行弦法）迭代法（平行弦法）n n弦截法弦截法n nNewton下山法下山法n n重根情形重根情形2.4 Newton迭代法迭代法第37页uu设方程设方程设方程设方程f f(x x)=0)=0有近似根有近似根有近似根有近似根x xk k（f f(x xk k)0 0），将），将），将），将f f(x x)在在在在x xk k展开：展开：展开：展开：（在在在在x x和和和和x xk k之间）之间）之间）之间）2.4.1 Newton迭代法及其收敛性迭代法及其收敛性n n基本思想：基本思想：将非线性方程逐步归结为某种线将非线性方程逐步归结为某种线性方程求解。性方程求解。可设可设可设可设第38页记该线性方程根为记该线性方程根为记该线性方程根为记该线性方程根为x xk k+1+1，则，则，则，则故故故故f f(x x)=0)=0可近似表示为可近似表示为可近似表示为可近似表示为即为即为即为即为NewtonNewton法迭代格式法迭代格式法迭代格式法迭代格式。（k=0,1,）第39页n nNewton迭代法几何意义迭代法几何意义：（亦称（亦称切线法切线法）xyx*xk+1xkPky=f(x)切线方程切线方程切线方程切线方程故故故故第40页n nNewtonNewton迭代法收敛性：迭代法收敛性：迭代法收敛性：迭代法收敛性：uu迭代函数：迭代函数：迭代函数：迭代函数：定理定理定理定理：假设：假设：假设：假设f f(x x)在在在在x x*某邻域内含有连续二阶导数，且设某邻域内含有连续二阶导数，且设某邻域内含有连续二阶导数，且设某邻域内含有连续二阶导数，且设f f(x x*)=0*)=0，f f(x x*)*)0 0，则对充分靠近则对充分靠近则对充分靠近则对充分靠近x x*初始值初始值初始值初始值x x0 0，NewtonNewton迭代法产生序列迭代法产生序列迭代法产生序列迭代法产生序列 x xn n 最少平方收敛于最少平方收敛于最少平方收敛于最少平方收敛于x x*。设设设设f f(x x*)=0*)=0，f f(x x*)*)0 0，则则则则 (x x*)=0*)=0，故故故故NewtonNewton迭代法迭代法迭代法迭代法在在在在x x*附近最少平方收敛。附近最少平方收敛。附近最少平方收敛。附近最少平方收敛。第41页解解解解：f f(x x)=)=e ex x+xexex x，故，故，故，故NewtonNewton迭代公式为迭代公式为迭代公式为迭代公式为k xk 00.51 0.5710220.5671630.56714迭代迭代3次即可得到精度为次即可得到精度为10-5近似解近似解0.56714。若用。若用不动点迭代，到达同一精不动点迭代，到达同一精度需度需17次。次。例例：用：用Newton迭代法解方程迭代法解方程 xex-1=0。即即即即取迭代初值取迭代初值取迭代初值取迭代初值x x0 0=0.5=0.5，结果以下：，结果以下：，结果以下：，结果以下：第42页Newton迭代法缺点：迭代法缺点：1.被零除错误被零除错误2.程序死循环程序死循环y=arctan x方程方程方程方程:f f(x x)=)=x x3 3 3 3x x+2=0+2=0在重根在重根在重根在重根x x*=1*=1附近，附近，附近，附近，f f(x x)近似近似近似近似为零。为零。为零。为零。对对 f(x)=arctan x存在存在 x0，Newton迭代迭代法陷入死循环。法陷入死循环。第43页uu若若若若|(x x)|=|1-)|=|1-cfcf(x x)|1)|1，即取，即取，即取，即取00cfcf(x x)2)2在在在在x x*附近成附近成附近成附近成立，则收敛。立，则收敛。立，则收敛。立，则收敛。uu若取若取若取若取c c=1/=1/f f(x x0 0)，则称，则称，则称，则称简化简化简化简化NewtonNewton法法法法。2.4.2 简化简化Newton法（平行弦法）法（平行弦法）迭代公式：迭代公式：迭代公式：迭代公式：（c 0,k=0,1,）迭代函数：迭代函数：迭代函数：迭代函数：第44页在在在在NewtonNewton迭代格式中，用差商近似导数，迭代格式中，用差商近似导数，迭代格式中，用差商近似导数，迭代格式中，用差商近似导数，2.4.3 弦截法（割线法）弦截法（割线法）称称称称弦截法弦截法弦截法弦截法。得得得得第45页弦截法几何意义：弦截法几何意义：xyx*xk+1xk-1Pk-1y=f(x)xkPk弦线弦线弦线弦线P Pk kP Pk k-1-1方程：方程：方程：方程：当当当当y y0 0时，时，时，时，第46页n n例例例例 用简化用简化用简化用简化NewtonNewton迭代法和弦截法计算方程迭代法和弦截法计算方程迭代法和弦截法计算方程迭代法和弦截法计算方程x x3 3-3 3x x+1=0+1=0根。根。根。根。n n解：解：解：解：设设设设f f(x x)=)=x x3 3-3-3x x+1+1，则，则，则，则f f(x x)=3)=3x x2 2-3-3由简化由简化由简化由简化NewtonNewton法，得法，得法，得法，得由弦截法，得由弦截法，得由弦截法，得由弦截法，得第47页x x0 0=0.5=0.5x x1 1=0.3333333333=0.3333333333x x2 2=0.3497942387=0.3497942387x x3 3=0.3468683325=0.3468683325x x4 4=0.3473702799=0.3473702799x x5 5=0.3472836048=0.3472836048x x6 6=0.3472985550=0.3472985550 x x7 7=0.3472959759=0.3472959759x x8 8=0.3472964208=0.3472964208x x9 9=0.3472963440=0.3472963440 x x1010=0.3472963572=0.3472963572x x1111=0.3472963553=0.3472963553x x0 0=0.5;=0.5;x x1 1=0.4;=0.4;x x2 2=0.3430962343=0.3430962343x x3 3=0.3473897274=0.3473897274x x4 4=0.3472965093=0.3472965093x x5 5=0.3472963553=0.3472963553x x6 6=0.3472963553=0.3472963553简化简化简化简化NewtonNewton法法法法弦截法弦截法弦截法弦截法要到达精度要到达精度要到达精度要到达精度1010-8-8，简化，简化，简化，简化NewtonNewton法迭代法迭代法迭代法迭代1111次，弦截次，弦截次，弦截次，弦截法迭代法迭代法迭代法迭代5 5次，次，次，次，NewtonNewton迭代迭代迭代迭代法迭代法迭代法迭代法迭代4 4次次次次。第48页不论前面哪种迭代法：不论前面哪种迭代法：不论前面哪种迭代法：不论前面哪种迭代法：（NewtonNewton迭代法、迭代法、迭代法、迭代法、简化简化简化简化NewtonNewton法、法、法、法、弦截法）弦截法）弦截法）弦截法）NewtonNewton迭代法迭代法迭代法迭代法x x0 0=2=2x x1 1=-3.54=-3.54x x2 2=13.95=13.95x x3 3=-279.34=-279.34x x4 4=12=12是否收敛均与初值位置相关。是否收敛均与初值位置相关。是否收敛均与初值位置相关。是否收敛均与初值位置相关。如如如如x x0 0=1=1x x1 1=-0.5708=-0.5708x x2 2=0.1169=0.1169x x3 3=-0.0011=-0.0011x x4 4=7.9631e-010=7.9631e-010 x x5 5=0=0收敛发散第49页n n为预防为预防为预防为预防NewtonNewton法发散，可增加一个条件法发散，可增加一个条件法发散，可增加一个条件法发散，可增加一个条件：|f f(x xk k+1+1)|)|f f(x xk k)|)|，满足该条件算法称，满足该条件算法称，满足该条件算法称，满足该条件算法称下山法下山法下山法下山法。n n可用下山法确保收敛，可用下山法确保收敛，可用下山法确保收敛，可用下山法确保收敛，NewtonNewton法加紧速度。法加紧速度。法加紧速度。法加紧速度。2.4.4 Newton下山法下山法称称Newton下山法下山法。（0 1,下山下山因子）因子）记记记记即即即即第50页从从从从 =1=1开始，逐次减半计算。开始，逐次减半计算。开始，逐次减半计算。开始，逐次减半计算。次序，直到使下降条件次序，直到使下降条件次序，直到使下降条件次序，直到使下降条件|f f(x xk k+1+1)|)|f f(x xk k)|)|成立为止。成立为止。成立为止。成立为止。选取：选取：即按即按第51页n n例例例例：求解方程：求解方程：求解方程：求解方程要求到达精度要求到达精度要求到达精度要求到达精度|x xn n-x xn n-1-1|1010-5-5，取，取，取，取x x0 0=-0.99=-0.99。解解解解：先用：先用：先用：先用NewtonNewton迭代法：迭代法：迭代法：迭代法：f f(x x)=)=x x2 2-1-1x x2 2=21.69118=21.69118 x x3 3=15.15689 =15.15689 x x4 4=9.70724 =9.70724 x x5 5=6.54091 =6.54091 x x6 6=4.46497 =4.46497 x x7 7=3.13384=3.13384x x8 8=2.32607 =2.32607 x x9 9=1.90230 =1.90230 x x1010=1.75248 =1.75248 x x1111=1.73240 =1.73240 x x1212=1.73205 =1.73205 x x1313=1.73205=1.73205需迭代需迭代需迭代需迭代1313次才次才次才次才到达精度要求到达精度要求到达精度要求到达精度要求第52页n n用用用用NewtonNewton下山法，结果以下：下山法，结果以下：下山法，结果以下：下山法，结果以下：k k=0 =0 x x0 0=-0.99 =-0.99 f f(x x0 0)=0.666567)=0.666567k k=1 =1 x x1 1=32.505829 =32.505829 f f(x x)=11416.4)=11416.4 =0.5 =0.5 x x1 1=15.757915 =15.757915 f f(x x)=1288.5)=1288.5 =0.25 =0.25 x x1 1=7.383958 =7.383958 f f(x x)=126.8)=126.8 =0.125 =0.125 x x1 1=3.196979 =3.196979 f f(x x)=7.69)=7.69 =0.0625 =0.0625 x x1 1=1.103489 =1.103489 f f(x x)=-0.655)=-0.655k k=2 =2 x x2 2=4.115071 =4.115071 f f(x x)=19.1)=19.1 =0.5 =0.5 x x2 2=2.60928 =2.60928 f f(x x)=3.31)=3.31 =0.25 =0.25 x x2 2=1.85638 =1.85638 f f(x x)=0.27)=0.27k k=3 =3 x x3 3=1.74352 =1.74352 f f(x x)=0.023)=0.023k k=4 =4 x x4 4=1.73216 =1.73216 f f(x x)=0.00024)=0.00024k k=5 =5 x x5 5=1.73205 =1.73205 f f(x x)=0.00000)=0.00000k k=6 =6 x x6 6=1.73205 =1.73205 f f(x x)=0.000000)=0.000000k k 下山因子下山因子下山因子下山因子x xk k f f(x xk k)第53页n n设设设设f f(x x)=()=(x x-x x*)*)mm g g(x x),),mm 2 2，mm为整数，为整数，为整数，为整数，g g(x x*)*)0,0,则则则则x x*为为为为方程方程方程方程f f(x x)=0)=0mm重根。此时有重根。此时有重根。此时有重根。此时有 f f(x x*)=*)=f f(x x*)=*)=f f(mm-1)-1)(x x*)=0,*)=0,f f(mm)(x x*)*)0 02.4.5 重根情形重根情形方法一方法一只要只要f(xk)0，仍可用仍可用Newton法计算，此法计算，此时时为线性收敛。为线性收敛。为线性收敛。为线性收敛。方法二方法二方法二方法二若取若取若取若取则则则则 (x x*)=0*)=0，用迭代法用迭代法用迭代法用迭代法求求求求mm重根，则具重根，则具重根，则具重根，则具2 2阶阶阶阶收敛，但要知道收敛，但要知道收敛，但要知道收敛，但要知道mm。第54页n n方法三方法三方法三方法三还可令还可令还可令还可令 则则则则故故故故x x*是是是是(x x)=0)=0单根，对单根，对单根，对单根，对(x x)用用用用NewtonNewton法，可得法，可得法，可得法，可得它是二阶收敛。它是二阶收敛。它是二阶收敛。它是二阶收敛。第55页n nP43-44习题二：习题二：2，4，6，8，9，10。本章作业第56页