1、数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日1第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法7.1 7.1 方程求根与二分法方程求根与二分法7.1.1 7.1.1 引言引言方程求根的一般形式：方程求根的一般形式：0 xf其中其中 ，Rx b,aCxf 如果实数如果实数 满足满足 ，则称则称 是是方程的根方程的根，*x 0*xf*x或称或称 是函数是函数 的的零点零点。*x xf数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日2若若 可分解为：可分解为：xgxxxfm*xf其中其中 为正整数，且为正整数，且m 0*xg则称则称 为方程的为
2、方程的 重根重根，或，或 为为 的的 重零点重零点。*xm*x xfm 时为时为单根单根。1 m若若 为为 的的 重零点，且重零点，且 充分光滑，则充分光滑，则*x xfm xg 001*m*m*xf,xfxfxf数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日3方程性质不同，求解方法也有很大差异。方程性质不同，求解方法也有很大差异。如果函数如果函数 是多项式：是多项式：xf nnnnaxaxaxaxf 1110其中其中 ，为实数，则称方程为为实数，则称方程为 次代数方程次代数方程。00 aian 次代数方程在复数域有且只有次代数方程在复数域有且只有 个根（含重根）。个根（含重根
3、）。nn当当 时不能用公式表示方程的根，只能数值求解。时不能用公式表示方程的根，只能数值求解。5 n数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日4有根区间有根区间：设函数设函数 在在 上连续，上连续，xf b,a 0 bfaf则方程则方程 在区间在区间 内一定有实根，内一定有实根，0 xf b,a称称 为方程为方程 的有根区间。的有根区间。b,a 0 xf xfx2x1xab对于对于超越方程超越方程，例如：，例如：010sin10 xex在整个在整个 轴上有无穷多个解，轴上有无穷多个解，取值范围不同，解也不同。取值范围不同，解也不同。xx超远方程只能通过数值求解。超远方程只能
4、通过数值求解。数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日5逐次搜索法逐次搜索法：设连续函数设连续函数 存在有根区间存在有根区间 xf b,a 将将 等分，步长等分，步长 ；b,aNabh 端点端点 ；khaxk N,k10 检查节点函数值检查节点函数值?kxf 若若 ，则可确定有根区间，则可确定有根区间 。01 kkxfxf kkx,x1 a1 kxkxxN数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日6P213 例例1 求方程求方程 的有根区间。的有根区间。0774183811123 .x.x.xxf解解：，07410 .f 04376 .f 在区间在区间
5、 内至少有一个实根。内至少有一个实根。xf 60,取步长取步长 ，进行搜索计算：，进行搜索计算：1 h方程的有根区间为方程的有根区间为 ，21,43,65,xfx6543210数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日77.1.2 7.1.2 二分法二分法计算方法：计算方法：af?bf 计算区间中点函数值计算区间中点函数值?2 baf 若若 ，则根为，则根为 ，02 baf2bax*计算区间端点函数值计算区间端点函数值 、否则：否则：时时 ，；02 afbafbba 2 时时 ，；02 bfbafaba 2数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日8 反
6、复计算，直到反复计算，直到 ，ab（预定的精度）预定的精度）最终取值：最终取值：。2bax*误差：取有根区间误差：取有根区间 的中点的中点 （二分次数）二分次数）kkb,ak作为近似根，则：作为近似根，则：2kkkbax 122 kkkk*ababxx特点：算法简单，可保证收敛，但收敛太慢。用于求近似解。特点：算法简单，可保证收敛，但收敛太慢。用于求近似解。数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日9P214例例2 求方程求方程 在区间在区间 内的一个实根，内的一个实根，要求准确到小数点后的第二位。要求准确到小数点后的第二位。013 xxxf 5101.,.解解：注：注：，
7、即，即12 kk*abxx0040250166.xx*0101 .f，0875051 .f数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日107.2 7.2 不动点迭代法及其收敛性不动点迭代法及其收敛性7.2.1 7.2.1 不动点与不动点迭代法不动点与不动点迭代法将方程将方程 改写成等价形式：改写成等价形式：0 xf xx 若要求若要求 满足满足 ，则，则 ；反之亦然。；反之亦然。*x 0*xf *xx 称称 为函数为函数 的一个的一个不动点不动点。*x x 因此，求因此，求 的零点就等价于求的零点就等价于求 的不动点。的不动点。xf x 数值分析数值分析 黄龙主讲黄龙主讲 2
8、022年年12月月3日日11 选择一个初始近似值选择一个初始近似值 ，代入，代入迭代函数迭代函数 ：0 x 01xx 将新值将新值 作为近似值，再次代入迭代函数：作为近似值，再次代入迭代函数：1x 12xx 反复迭代，反复迭代，迭代方程迭代方程：kkxx 1,k10，迭代存在极限：迭代存在极限：*kkxx lim不动点迭代法不动点迭代法：x 则称迭代方程则称迭代方程收敛收敛，且，且 为为 的不动点。的不动点。*xx x 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日12实质：将隐式方程实质：将隐式方程 ，通过迭代逐步显式化，通过迭代逐步显式化逐次逼近法逐次逼近法。xx 几何意义
9、：几何意义：直线直线 与曲线与曲线xy xy 其交点横坐标就是方程的根。其交点横坐标就是方程的根。逐次逼近：逐次逼近：0 x 00 xy 10 xy 1x 11xy 21xy kkxx 1*x（迭代收敛）（迭代收敛）数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日13P215例例3 求方程求方程 在在 附近的根附近的根 。013 xxxf510.x *x解解：迭代公式：迭代公式311 kkxx，,k10 注意：如果迭代公式为注意：如果迭代公式为 ，则，则迭代发散迭代发散。131 kkxx数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日147.2.2 7.2.2 不动
10、点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性定理定理1 1 设函数设函数 满足以下两个条件：满足以下两个条件：（1 1）对于任意对于任意 ，有，有 b,aCx b,ax bxa （2 2）存在正常数存在正常数 ，使对任意，使对任意 都有都有 b,ay,x 1 L yxLyx （迭代函数在（迭代函数在 上）上）b,a（迭代函数的增量小于自变量的增量）（迭代函数的增量小于自变量的增量）则则 在在 上存在唯一的不动点上存在唯一的不动点 。x b,a*x数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日15证明证明：先证不动点存在性。：先证不动点存在性。若若 ，或，或 ：aa
11、bb 则则 在在 上存在不动点。（不动点特点上存在不动点。（不动点特点 ）x b,a *xx 因因 ，以下设，以下设 及及 ，定义：，定义：bxa aa bb xxxf 显然显然 ，且满足，且满足 b,aCxf 0 aaaf，0 bbbf 由连续函数性质可知：存在由连续函数性质可知：存在 使使 b,ax*0*xf即即 ，为为 的不动点。的不动点。*xx *x x 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日16再证唯一性。再证唯一性。设设 及及 都是都是 的不动点，则：的不动点，则：*x1 x b,ax*2 *xxxxLxxxx21212121 引出矛盾。故引出矛盾。故 的不
12、动点只能是唯一的。的不动点只能是唯一的。x 在在 的不动点唯一的情况下，可得到迭代法收敛的充分条件。的不动点唯一的情况下，可得到迭代法收敛的充分条件。x 数值分析数值分析 黄龙主讲黄龙主讲 收敛到收敛到 的不动点的不动点 ，并有误差估计，并有误差估计2022年年12月月3日日17定理定理2 2 设函数设函数 满足以下两个条件：满足以下两个条件：（1 1）对于任意对于任意 ，有，有 b,aCx b,ax bxa （2 2）存在正常数存在正常数 ，使对任意，使对任意 都有都有 b,ay,x 1 L yxLyx 则对任意则对任意 ：b,ax 0 x*x由由 得到的迭代序列得到的迭代序列 kkxx 1
13、 kx011xxLLxxk*k 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日18证明证明：设：设 是是 在在 上的唯一不动点。上的唯一不动点。b,ax*x b,a由定理条件（由定理条件（1 1）可知：）可知：b,axk *k*k*kxxLxxxx 11 由定理条件（由定理条件（2 2）可得：）可得：反复应用上述结论：反复应用上述结论：*k*k*k*kxxLxxLxxLxx 0221因因 ：故当：故当 时时10 L k00*kkxx,L，序列，序列 收敛到收敛到 。kx*x数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日19再由定理条件（再由定理条件（2 2）得：
14、）得：111 kkkkkkxxLxxxx 如此反复递推得：如此反复递推得：011xxLxxkkk 于是对于任意正整数于是对于任意正整数 有：有：pkkpkpkpkpkkpkxxxxxxxx 1211 0101211xxLLxxLLLkkpkpk 在上式令在上式令 ，注意到，注意到 ：p*pkpxx lim011xxLLxxk*k 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日20讨论一讨论一：因正常数：因正常数 未知，上述误差估计无法使用。未知，上述误差估计无法使用。L对于任意正整数对于任意正整数 有：有：pkkpkpkpkpkkpkxxxxxxxx 1211 kkkkppxx
15、LxxLL 1121111令令 可得：可得：pkkkxxLxx 1*11即：只要相邻两次计算结果的偏差即：只要相邻两次计算结果的偏差 足够小，足够小，就能保证近似值就能保证近似值 具有足够的精度。具有足够的精度。kkxx 1kx数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日21讨论二讨论二：在某些情形下可求得：在某些情形下可求得 。L如果如果 且对任意且对任意 有有 b,aCx1 b,ax 1 Lx 则，由中值定理可得：对则，由中值定理可得：对 有有 b,ay,x b,a,yxLyxyx 因此，可将上述因此，可将上述定理定理 和和定理定理 中的条件（中的条件（2 2）改为：）改
16、为：12 1 Lx 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日22P215例例3 求方程求方程 在在 附近的根附近的根 。013 xxxf510.x *x例如：例如：（1 1）当）当 时，在区间时，在区间 有：有：31 xx 12311313232 xx 21,232133 x 由定理由定理2 2可得：迭代法是收敛的。可得：迭代法是收敛的。（2 2）当）当 时，在区间时，在区间 有：有：13 xx 21,132 xx 不满足定理的条件，无法保证迭代收敛。不满足定理的条件，无法保证迭代收敛。数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日237.2.3 7.2.
17、3 局部收敛性与收敛阶局部收敛性与收敛阶对于区间对于区间 上的任意上的任意 ，所产生的迭代序列，所产生的迭代序列 都收敛，都收敛，称为称为全局收敛全局收敛。b,a0 x kx实际应用时，通常只在不动点实际应用时，通常只在不动点 邻居考察其收敛性，邻居考察其收敛性，称为称为局部收敛局部收敛。*x定义定义1 1 设设 有不动点有不动点 ，如果存在，如果存在 的某个领域的某个领域 ：x*x*xR *xx对任意对任意 ，迭代产生序列，迭代产生序列 ，且收敛到，且收敛到 ，Rx 0 Rxk*x则称迭代法则称迭代法局部收敛局部收敛。数值分析数值分析 黄龙主讲黄龙主讲 且且 ，则迭代法，则迭代法 局部收敛。
18、局部收敛。定理定理3 3 设设 为为 的不动点，的不动点，在在 的某个领域连续，的某个领域连续，2022年年12月月3日日24 x*x*x x 1*x kkxx 1证明证明：由连续函数的性质，存在：由连续函数的性质，存在 的某个领域的某个领域 ：*xR *xx使对于任意使对于任意 有下式成立：有下式成立：Rx 1 Lx 此外，对于任意此外，对于任意 ，总有，总有 ，这是因为：，这是因为：Rx Rx *xxxxxx *xxxxL依据定理依据定理2 2：迭代过程对于任意：迭代过程对于任意 均收敛。均收敛。Rx 0数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日25P218题题4 用不
19、同方法求方程用不同方法求方程 的根的根 。03-2 x3*x解：这里解：这里 ，可改写成不同的等价形式可改写成不同的等价形式 ，其不动点为，其不动点为 32 xxf xx 3*x（1 1）321 kkkxxx，32 xxx 12 xx，11323 *x（2 2）kkxx31 ，xx3 23xx ，13 *x数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日26（3 3）34121 kkkxxx，3412 xxx xx211 ，11340231 .x*（4 4）kkkxxx3211，xxx321 23121xx，03 *x取取 ，对上述，对上述4 4种迭代法，计算三步的结果如下表。种
20、迭代法，计算三步的结果如下表。20 x数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日27 7320511732361151873732143173475129275175151312222043213210.x.x.xxxkk迭代法迭代法迭代法迭代法迭代法迭代法迭代法迭代法说明：说明：精确值精确值 ，732050813.迭代法（迭代法（1 1）和（）和（2 2）不收敛，迭代法（）不收敛，迭代法（3 3）和（）和（4 4）收敛；）收敛；迭代法（迭代法（4 4）中）中 比迭代法（比迭代法（3 3）小，）小，迭代法（迭代法（4 4）比迭代法（）比迭代法（3 3）收敛速度快。）收敛速度
21、快。0 *x 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日28定义定义2 2 设迭代过程设迭代过程 收敛于方程收敛于方程 的根的根 ，kkxx 1 xx *x如果当如果当 时迭代误差时迭代误差 满足渐进关系式满足渐进关系式 k*kkxxe Ceepkk 1，常数，常数0 C则称该迭代过程是则称该迭代过程是 阶收敛阶收敛的。的。特别地，特别地，时称为时称为线性收敛线性收敛，时为时为超线性收敛超线性收敛，时为时为平方收敛平方收敛。p 11 Cp1 p2 p数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日29定理定理4 4 对于对于迭代过程迭代过程 及正整数及正整数
22、，kkxx 1p如果如果 在所求根在所求根 的邻近连续，且的邻近连续，且 xp*x 01 *p*xxx 0*px 则该迭代过程在点则该迭代过程在点 邻近是邻近是 阶收敛的。阶收敛的。*xp证明：由于证明：由于 ，根据定理，根据定理3 3可得：可得：0 *x 迭代过程迭代过程 具有局部收敛性。具有局部收敛性。kkxx 1数值分析数值分析 黄龙主讲黄龙主讲 再将再将 在根在根 处泰勒展开，利用定理条件：处泰勒展开，利用定理条件：2022年年12月月3日日30 kx*x p*kp*kxxpxx !，在在 与与 之间之间 kx*x注意到注意到 ，：1 kkxx *xx p*kp*kxxpxx !1 因
23、此对迭代误差，当因此对迭代误差，当 时有：时有：k !1pxee*ppkk 这表明迭代过程这表明迭代过程 确实为确实为 阶收敛。阶收敛。kkxx 1p数值分析数值分析 黄龙主讲黄龙主讲 迭代过程的收敛速度依赖于迭代函数迭代过程的收敛速度依赖于迭代函数 的选取。的选取。2022年年12月月3日日31说明说明 定理表明：定理表明：x 如果如果 时时 ：则该迭代过程只可能是线性收敛的。则该迭代过程只可能是线性收敛的。b,ax 0 x 在例在例4 4中：中：迭代法（迭代法（3 3）的）的 ，故它只能是线性收敛；，故它只能是线性收敛；0*x 迭代法（迭代法（4 4）的）的 ，迭代为二阶收敛。，迭代为二阶
24、收敛。0*x 0*x 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日327.3 7.3 迭代收敛的加速方法迭代收敛的加速方法7.3.1 7.3.1 埃特金加速收敛方法埃特金加速收敛方法设设 是根是根 的某个近似值，用迭代公式迭代一次：的某个近似值，用迭代公式迭代一次：0 x*x 01xx 由微分中值定理：由微分中值定理：*xxxxxx 001 （在在 与与 之间之间 ）0 x*x假定假定 变化不大：变化不大：x Lx *xxLxx 01，数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日33将校正值将校正值 再迭代一次：再迭代一次：01xx 12xx 因而有：因而有
25、：*xxLxx 01 *xxLxx 12消去消去 ：L*xxxxxxxx 1021可推得：可推得：0122010012212022xxxxxxxxxxxxx*注意：注意：上式是对两次迭代值加权平均后的结果，可加速迭代；上式是对两次迭代值加权平均后的结果，可加速迭代；适用任何求根序列适用任何求根序列 ，不只局限于不动点迭代序列。，不只局限于不动点迭代序列。kx数值分析数值分析 黄龙主讲黄龙主讲 已知求根序列已知求根序列 ，其三个相邻值为，其三个相邻值为2022年年12月月3日日34埃特金加速法埃特金加速法（加速法加速法）：）：kx1 kx2 kx加速计算，得到新值加速计算，得到新值 ,k,xxx
26、xxxxxxxkkkkkkkkkk1022212211 kx，kkkxxx 1点点 的一阶差分；的一阶差分；kx kkkkkxxxxx 1122点点 的二阶差分；的二阶差分；kx2 可以证明：新序列可以证明：新序列 的收敛速度比的收敛速度比 的收敛速度快的收敛速度快 kx kx0lim1 *k*kkxxxx数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日357.3.2 7.3.2 斯特芬森迭代法斯特芬森迭代法把埃特金加速法与不动点迭代结合，就可得到把埃特金加速法与不动点迭代结合，就可得到斯特芬森迭代法斯特芬森迭代法：kkkkyz,xy ,kxyzxyxxkkkkkkk10221
27、，斯特芬森迭代法是将两步迭代合成一步得到的：斯特芬森迭代法是将两步迭代合成一步得到的：,k,xxkk101 xxxxxxx 22数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日36斯特芬森迭代法思路：斯特芬森迭代法思路：为求解为求解 的根的根 ，令，令 ：xx *x xxx 0 *xxx 已知已知 的近似值的近似值 及及 ，其误差分别为：，其误差分别为：*xkxky kkkkkxyxxx kkkkkyzyyy 把误差把误差 “外推到零外推到零”：即过即过 及及 两点做线性插值函数，两点做线性插值函数，kkx,x kky,y 它与它与 轴交点就是轴交点就是 。x x1 kx数值分析
28、数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日37即求解方程：即求解方程：0 kkkkkkxxxyxyx 其解为：其解为：kkkkkkkkkkkkxyzxyxxyxyxxx 22 即：即：kkkkkkkxyzxyxx 221数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日38定理定理5 5 对于斯特芬森迭代法对于斯特芬森迭代法 ,k,xxkk101 xxxxxxx 22若若 为迭代函数为迭代函数 的不动点，则的不动点，则 也为也为 的不动点。的不动点。*x x*x x 反之，若反之，若 为为 的不动点，设的不动点，设 存在，存在，*x x x 1 *x 则则 也是也是 的
29、不动点，且斯特芬森迭代法是二阶收敛的。的不动点，且斯特芬森迭代法是二阶收敛的。*x x 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日39P221例例5 5 用斯特芬森法求解方程用斯特芬森法求解方程 。013 xxxf解解：用迭代公式：用迭代公式 求解方程是发散的。求解方程是发散的。131 kkxx改进上述迭代公式，斯特芬森迭代法：改进上述迭代公式，斯特芬森迭代法：13 kkxy13 kkyz，kkkkkkkxyzxyxx 221324721532714132518132480144443513471013289513317282491401355651223888584092
30、14162911396512375002510.zyxkkkk数值分析数值分析 黄龙主讲黄龙主讲 因因 ，2022年年12月月3日日40P222例例6 6 求方程求方程 在在 中的解中的解 。033 xex 43,解解：由方程得：由方程得 ，并取对数，并取对数23xex xxxx 3lnln23ln2可构造迭代法可构造迭代法 xx2 132max43 xx 且且 时，时，由定理，由定理2 2此迭代法是收敛的。此迭代法是收敛的。3lnln21 kkxx 43,x 43,x 若取若取 迭代迭代1616次得次得 ，有六位有效数字。，有六位有效数字。530.x 73307316.x 733083273
31、45937359037383531662783604143530.zyxkkkk若用斯特芬森若用斯特芬森迭代法加速：迭代法加速：数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日417.4 7.4 牛顿法牛顿法7.4.1 7.4.1 牛顿法及其收敛性牛顿法及其收敛性牛顿法基本思想：将非线性方程转化线性方程求解。牛顿法基本思想：将非线性方程转化线性方程求解。设已知方程设已知方程 有近似根有近似根 ，0 xfkx 0 kxf将函数将函数 在点在点 展开展开 xfkx kkkxxxfxfxf 于是方程于是方程 可近似表示为可近似表示为 0 xf 0 kkkxxxfxf这是个线性方程，其根
32、为这是个线性方程，其根为 （牛顿法牛顿法）1 kx ,k,xfxfxxkkkk101 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日42牛顿法的几何解释牛顿法的几何解释：方程方程 的根的根 为为 0 xf*x曲线曲线 与与 轴交点的横坐标。轴交点的横坐标。xfy x设设 是根是根 的某个近似值，的某个近似值，kx*x过曲线过曲线 上点上点 引切线，引切线，xfy kky,x切线与切线与 轴交点的横坐标轴交点的横坐标 作为新解作为新解x1 kx切线方程：（切线方程：（点斜式方程）点斜式方程）kkkxxxfxfy 其根为牛顿法的近似解其根为牛顿法的近似解切线法切线法。数值分析数值分
33、析 黄龙主讲黄龙主讲 2022年年12月月3日日43讨论：牛顿法的收敛性。讨论：牛顿法的收敛性。xfxfxx ，2xfxfxfx 42xfxfxfxfx 假定假定 是是 的一个单根：的一个单根：*x xf 0*xf，0 *xf代入上式，可得：代入上式，可得：0 *x，0 *x 因此：牛顿法在根因此：牛顿法在根 邻近是平方收敛的。邻近是平方收敛的。*x数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日44P223例例7 用牛顿法解方程用牛顿法解方程 。01 xxe解解：牛顿公式为：牛顿公式为 1 xxexf xexxf 1 kkkkxfxfxx 1kxkkxexxk 1取迭代初值取迭
34、代初值500.x 567140356716025710201500.xkk数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日45牛顿法计算步骤牛顿法计算步骤：第一步第一步 准备准备：选定初值：选定初值 ，0 x计算计算 ，00 xff 00 xff 第二步第二步 迭代迭代：迭代一次：迭代一次 ，0001ffxx 计算计算 ，11xff 11xff 第三步第三步 控制控制：计算迭代误差：计算迭代误差 ，（，（控制常数控制常数）01xx ，当，当 时时Cx 1101xxx ，当，当 时时Cx 11 C数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日46否则以否则以 代替代
35、替 ，或者或者 ，则方法失败；，则方法失败；第四步第四步 修改修改：如果迭代次数达到预先指定的次数：如果迭代次数达到预先指定的次数 ，111f,f,x 如果如果 满足：满足：N01 f1x1 或或 （、允许误差）允许误差）21 f1 2 则迭代收敛，以则迭代收敛，以 作为所求的根，否则转第四步。作为所求的根，否则转第四步。1x 000f,f,x 转第二步继续迭代。转第二步继续迭代。数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日477.4.2 7.4.2 牛顿牛顿法应用举例法应用举例对于给定正数对于给定正数 ，开方计算，开方计算 C?C转变为应用牛顿法解方程转变为应用牛顿法解方程
36、 。02 Cx Cxxf 2，xxf2 kkkkxfxfxx 1 kkkxCxx211可以证明：对于任意初值可以证明：对于任意初值 迭代都收敛。迭代都收敛。00 x数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日48证明证明：由迭代公式：由迭代公式：212121CxxCxCxCxkkkkk 212121CxxCxCxCxkkkkk 两式相除：两式相除：2211211CxCxCxCxCxCxkkkkkk反复递推：反复递推：kCxCxCxCxkk200 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日49假设：假设：CxCxq 00解出：解出：Cqqxkkk2211 因
37、此：因此：kkqqCCxk2212 对于任意对于任意 ，总有，总有 ，00 x1 q当当 时，时，即迭代过程恒收敛。，即迭代过程恒收敛。kCxk数值分析数值分析 黄龙主讲黄龙主讲 迭代函数为迭代函数为 ，要求，要求2022年年12月月3日日507.4.3 7.4.3 简化牛顿法与牛顿简化牛顿法与牛顿下山法下山法牛顿法缺点：牛顿法缺点：每次迭代都要计算每次迭代都要计算 及及 ，有时计算，有时计算 困难。困难。kxf kxf kxf 初始值初始值 在根在根 附近才能保证收敛，取值不合适可能不收敛。附近才能保证收敛，取值不合适可能不收敛。0 x*x（1 1）简化牛顿法简化牛顿法（平行弦法平行弦法）迭
38、代公式为迭代公式为 ,k,xCfxxkkk101 xCfxx 0 C其中常量其中常量 ，并保证迭代收敛，并保证迭代收敛 11 xfCx，即，即 20 xfC若上式在根若上式在根 附近成立，则该迭代法局部收敛。附近成立，则该迭代法局部收敛。*x数值分析数值分析 黄龙主讲黄龙主讲 0 x1x2022年年12月月3日日51若若 取为取为 处之值处之值 ，则有，则有简化牛顿法简化牛顿法C0 x 01xfC ,k,xfxfxxkkk1001 特点：节省了计算量，但只有线性收敛。特点：节省了计算量，但只有线性收敛。几何意义：几何意义：用斜率为用斜率为 的平行弦的平行弦与与 轴的交点作为轴的交点作为 的近似
39、。的近似。0 xf x*x数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日52（2 2）牛顿下山法牛顿下山法问题：牛顿法的收敛性依赖于初值问题：牛顿法的收敛性依赖于初值 。0 x例如：用牛顿法求解方程例如：用牛顿法求解方程 013 xx公式：公式：131231 kkkkkkkkxxxxxfxfxx如果：取迭代初值如果：取迭代初值510.x 3478311.x 3252012.x *x.x 3247213，如果：取迭代初值如果：取迭代初值600.x 9171.x 2x，结果偏离了根，结果偏离了根324721.x*数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日53为防
40、止迭代发散，要求迭代过程具有单调性为防止迭代发散，要求迭代过程具有单调性 kkxfxf 1下山法下山法牛顿下山法牛顿下山法：下山法保证函数值稳定下降，牛顿法加速收敛：下山法保证函数值稳定下降，牛顿法加速收敛先用牛顿法初步迭代先用牛顿法初步迭代 kkkkxfxfxx 1在将近似值在将近似值 与与 加权平均加权平均kx1 kx kkkkkkxfxfxxxx 111其中其中下山因子下山因子 ：10 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日54下山因子选择下山因子选择：从：从 开始，逐次减半试算，开始，逐次减半试算，1 直到满足下山法要求直到满足下山法要求 kkxfxf 1例如：
41、求解方程例如：求解方程 ，牛顿下山法公式为，牛顿下山法公式为 013 xxxf当当 ，时，求得时，求得 ，且，且131231 kkkkkxxxxx 600.x 1 9171.x 01xfxf 结果不满足下山法要求，无法继续迭代，需改进结果不满足下山法要求，无法继续迭代，需改进 值。值。数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日55逐次对逐次对 减半试算：当减半试算：当 时，求得时，求得 321 1406511.x 01xfxf 以以 为初值，取为初值，取 ，迭代收敛，迭代收敛1406511.x 1 1866036181122.xf,.x 00667032628133.xf,
42、.x 00000860324721144.xf,.x 注意：下山因子减半试算，只为确定使迭代收敛的初值注意：下山因子减半试算，只为确定使迭代收敛的初值 。0 x数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日567.4.4 7.4.4 重根情形重根情形设设 ，整数，整数 ，xgxxxfm*2 m 0*xg则则 为方程为方程 的的 重根，此时有：重根，此时有：*x 0 xfm 001 *m*m*xf,xfxfxf方法方法1 1：只要：只要 仍可用牛顿法仍可用牛顿法 0 kxf此时迭代函数为此时迭代函数为 ，其导数为，其导数为 xfxfxx 011 mx*，且，且 1 *x 所以牛顿
43、法求重根只是线性收敛。所以牛顿法求重根只是线性收敛。数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日57改进迭代函数改进迭代函数 xfxfmxx 此时有此时有 0011 *x,mmx 因此，用改进的迭代公式求重根具有二阶收敛性。因此，用改进的迭代公式求重根具有二阶收敛性。改进的迭代公式为改进的迭代公式为 ,k,xfxfmxxkkkk101 缺点：需要知道缺点：需要知道 的重根数的重根数 。*xm数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日58方法方法2 2：重新构造求重根的迭代法：重新构造求重根的迭代法令令 ，若，若 是是 的的 重根重根 xfxfx *x 0
44、xfm xgxxxmgxgxxx*故故 是是 的单根。的单根。*x 0 x 由此应用牛顿法，迭代函数为由此应用牛顿法，迭代函数为 xfxfxfxfxfxxxxx 2 从而可构造二阶收敛的迭代法从而可构造二阶收敛的迭代法 ,k,xfxfxfxfxfxxkkkkkkk1021 特点：无需知道特点：无需知道 值，但要计算值，但要计算 。m xf 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日59P227例例9 方程方程 的根的根 是二重根是二重根 。用上述三种方法求根。用上述三种方法求根。04424 xx解解：三种方法的迭代公式为：三种方法的迭代公式为2*x（1 1）牛顿法）牛顿法
45、kkkkkkkxxxxfxfxx4221 （2 2）改进法）改进法 kkkkkkkxxxxfxfmxx2221 （3 3）重构法）重构法 22221 kkkkkkkkxxxxxxxx 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日60取初值取初值 ，计算结果如下，计算结果如下:510.x 414213562141421356214254976191341421143814142156861436607143124117647061416666667145833333311321321.x.x.xxkk）方方法法（）方方法法（）方方法法（注意：方法（注意：方法（2 2）和（）和（
46、3)3)均达到均达到1010位有效数字，位有效数字，而牛顿法达到同样精度需迭代而牛顿法达到同样精度需迭代3030次。次。数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日617.5 7.5 弦截法与抛物线法弦截法与抛物线法7.5.1 7.5.1 弦截法弦截法牛顿法问题：每步需计算牛顿法问题：每步需计算 ，当函数复杂时较困难。，当函数复杂时较困难。设设 、是是 的近似根的近似根 kxf kx 0 xf1 kx由由 、构造一次插值多项式构造一次插值多项式 kxf 1 kxf xp1 kkkkkkxxxxxfxfxfxp 111用用 的根作为的根作为 的新的近似根的新的近似根 01 xp
47、 0 xf1 kx 111 kkkkkkkxxxfxfxfxx数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日62代入牛顿公式，即得弦截法结果：代入牛顿公式，即得弦截法结果：111 kkkkkkkkkkxxxfxfxfxxfxfxx用差商取代导数：用差商取代导数：11 kkkkkxxxfxfxf弦截法几何意义：弦截法几何意义：过曲线过曲线 上横坐标为上横坐标为 的两点的两点 xfy 作弦线作弦线 ，其方程为，其方程为1 kkx,x1 kkPP kkkkkkxxxxxfxfxfy 11弦线弦线 与与 轴交点的横坐标即为轴交点的横坐标即为 1 kkPPx1 kx数值分析数值分析 黄龙
48、主讲黄龙主讲 2022年年12月月3日日63P229例例10 用弦截法解方程用弦截法解方程 。01 xxexf解解：迭代公式为：迭代公式为 111 kkkkkkkxxxfxfxfxx567140456709035653202601500.xkk选取开始值为选取开始值为605010.x,.x 注意：注意：弦截法比牛顿法收敛速度快；弦截法比牛顿法收敛速度快；计算时要用到前两步的结果计算时要用到前两步的结果 。1 kkx,x数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日64弦截法具有超线性的收敛性弦截法具有超线性的收敛性定理定理6 6 假设假设 在根在根 的邻域的邻域 ：内内 xf*
49、x *xx具有二阶连续导数，且对任意具有二阶连续导数，且对任意 有有 x 0 xf又初值又初值 ，那么当邻域，那么当邻域 充分小时，充分小时，10 x,x弦截法将按阶弦截法将按阶 收敛到收敛到 。6181251.p *x这里这里 是方程是方程 的正根。的正根。p012 数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日657.5.2 7.5.2 抛物线法抛物线法设已知方程设已知方程 的三个近似根的三个近似根 、kx 0 xf1 kx2 kx以这三点为节点构造二次插值多项式以这三点为节点构造二次插值多项式 xp2适当选取适当选取 的一个零点的一个零点 作为新的近似根作为新的近似根 x
50、p21 kx抛物线法抛物线法（密勒法密勒法）几何意义：几何意义：过节点过节点 、kx1 kx2 kx作抛物线作抛物线 xpy2 抛物线与抛物线与 轴的交点轴的交点x即为根即为根 的近似值的近似值*x1 kx数值分析数值分析 黄龙主讲黄龙主讲 2022年年12月月3日日66二次插值多项式为二次插值多项式为 kkkkxxx,xfxfxp 12 121 kkkkkxxxxx,x,xf有两个零点有两个零点 212142 kkkkkkkx,x,xfxfxfxx xp2 1211 kkkkkkkxxx,x,xfx,xf 在三个近似根在三个近似根 、中，往往中，往往 更接近所求根更接近所求根kx1 kx2
