《数值方法第二章非线性方程的近似解法幻灯片.ppt》由会员分享，可在线阅读，更多相关《数值方法第二章非线性方程的近似解法幻灯片.ppt（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数值方法第二章非线性方程的近似解法第1页，共65页，编辑于2022年，星期六第二章 非线性方程的近似解法2.0 2.0 简介简介 2.1 2.1 二分法（对分法）二分法（对分法）2.2 2.2 简单迭代法简单迭代法2.3 Newton2.3 Newton迭代法迭代法第2页，共65页，编辑于2022年，星期六2.0 2.0 简介简介求解非线性方程求解非线性方程 f f(x x)=0)=0 一、问题一、问题困难困难：方程的解难以用公式表达。：方程的解难以用公式表达。例如例如:1):1)多项式方程：多项式方程：需要一定精度的近似解！需要一定精度的近似解！2)2)超越方程超越方程:第3页，共65页，编
2、辑于2022年，星期六方程方程 的解的解 称为方程称为方程 的的根根或称为或称为 的的零点零点。二、概念二、概念方程可能有多个实根，我们只能逐个求出来。方程可能有多个实根，我们只能逐个求出来。第4页，共65页，编辑于2022年，星期六二、概念二、概念设在区间设在区间 a a,b b 上方程有一个根，则称该区间为方上方程有一个根，则称该区间为方程的一个程的一个有根区间有根区间。若在区间。若在区间 a a,b b 上方程只有一上方程只有一个根，则称该区间为方程隔根区间个根，则称该区间为方程隔根区间。RemarkRemark：若能把有根区间不断缩小，则可以得出根的近若能把有根区间不断缩小，则可以得出
3、根的近似值。似值。第5页，共65页，编辑于2022年，星期六三、根的隔离三、根的隔离基于函数基于函数f f(x x)的连续性质，常用的根的隔离的方法有：的连续性质，常用的根的隔离的方法有：描图法描图法与与逐步搜索法逐步搜索法。1、描图法描图法：画出画出y y=f f(x x)的简图，从曲线与的简图，从曲线与x x轴交点的位轴交点的位置确定出隔根区间，或者将方程等价变形为置确定出隔根区间，或者将方程等价变形为g g1 1(x x)=)=g g2 2(x x)，画出函数，画出函数y y=g g1 1(x x)和和y y=g g2 2(x x)的简图，从两条曲线交点的简图，从两条曲线交点的横坐标的位
4、置确定隔根区间。的横坐标的位置确定隔根区间。2 2、逐步搜索法、逐步搜索法：先确定方程先确定方程f f(x)=0(x)=0的所有实根所在的所有实根所在区间区间 a a,b b，再按照选定的步长，再按照选定的步长 （n n为正整为正整数），取点数），取点x xk k=a a+khkh(k k=0,1,=0,1,n n)，逐步计算函数值，逐步计算函数值f f(x xk k)，依据函数值异号以及实根的个数确定隔根区间。，依据函数值异号以及实根的个数确定隔根区间。必要时可调整步长必要时可调整步长h h，总可把隔根区间全部找出。，总可把隔根区间全部找出。第6页，共65页，编辑于2022年，星期六三、根的
5、隔离三、根的隔离第7页，共65页，编辑于2022年，星期六三、根的隔离三、根的隔离问题：问题：扫描间距扫描间距？第8页，共65页，编辑于2022年，星期六2.1 2.1 二分法（对分法）二分法（对分法）关于求解算法关于求解算法:算法多样：比如刚才的算法多样：比如刚才的逐步搜索法逐步搜索法考虑因素：考虑因素：1稳定性；稳定性；2收敛性；收敛性；3第9页，共65页，编辑于2022年，星期六2.1 2.1 二分法（对分法）二分法（对分法）一、算法一、算法设设 在在 a,ba,b 上连续，上连续，f f(a a)f f(b)0(b)0且在且在 a a,b b 内内f f(x x)=0 0仅有一个实根仅
6、有一个实根 。二分法的。二分法的基本思想基本思想是：逐步将是：逐步将有根区间分半，通过判别函数值的符号，进一步搜索有有根区间分半，通过判别函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求出满足给定根区间，将有根区间缩小到充分小，从而求出满足给定精度的根精度的根 的近似值。的近似值。执行步骤：执行步骤：1计算计算f(x)在有解区间在有解区间a,b端点处的值端点处的值，f(a)，f(b)。2计算计算f(x)在区间中点处的值在区间中点处的值f(x1)。第10页，共65页，编辑于2022年，星期六3判断若判断若f(x1)=0，则则x1即是根，否则检验即是根，否则检验：（1）若若f(x1
7、)与与f(a)异号异号，则知解位于区间则知解位于区间a,x1，b1=x1,a1=a;（2）若若f(x1)与与f(a)同号同号，则知解位于区间则知解位于区间x1,b，a1=x1,b1=b。4.反复执行步骤反复执行步骤2、3，便可得到一系列有根区间便可得到一系列有根区间：(a,b),(a1,b1),(ak,bk),当当时时则则即为方程的近似根即为方程的近似根第11页，共65页，编辑于2022年，星期六二、误差估计二、误差估计定理定理1 1：给定方程给定方程 f f(x x)=0)=0，设，设 f f(x x)在区间在区间 a a,b b 上上连续，且连续，且f f(a a)f f(b b)0)0f
8、(a)f(b)=0f(a)=0打印打印b,k打印打印a,k结束结束是是是是是是否否否否否否m=(a+b)/2|a-b|0打印打印m,ka=mb=m结束结束k=K+1是是是是否否否否输入输入 k=0算法算法(二分法二分法)第15页，共65页，编辑于2022年，星期六2.2 2.2 迭代法迭代法即序列即序列 的极限的极限 为为 的根。的根。当当 连续时，有连续时，有 或或 。即即 一、迭代法一、迭代法1.1.基本思想：基本思想：令方程令方程 ,将其变成一个等价的方程将其变成一个等价的方程 ,构造构造 ,称为称为迭代数列迭代数列，或或迭代过程迭代过程。称为称为迭代函数迭代函数,称为称为迭代公式迭代公
9、式 因此，我们可以通过求迭代数列的极限的方法来求得方因此，我们可以通过求迭代数列的极限的方法来求得方程程f f(x x)=0)=0的根。的根。第16页，共65页，编辑于2022年，星期六RemarkRemark：可以通过不同的途径将：可以通过不同的途径将f f(x x)=0)=0化为化为x x=(x x)的的形式，从而构造不同的迭代公式，得到不同的迭代序列。形式，从而构造不同的迭代公式，得到不同的迭代序列。在所有这些构造的迭代公式中形成的序列中，有的序列是在所有这些构造的迭代公式中形成的序列中，有的序列是收敛的，而有些是发散的。收敛的，而有些是发散的。问题问题：如何选取合适的迭代函数：如何选取
10、合适的迭代函数(x x)？(x x)应满足什么条件，序列应满足什么条件，序列 x xk k 收敛？收敛？怎样加速序列怎样加速序列 x xk k 的收敛？的收敛？第17页，共65页，编辑于2022年，星期六xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1第18页，共65页，编辑于2022年，星期六2.2.迭代法的收敛定理迭代法的收敛定理（2 2）对任意初值）对任意初值x x0 0 a a,b b 由迭代公式由迭代公式则有则有:定理定理1.1.（全局收敛定理）（全局收敛定理）
11、设方程设方程 ，如果满足，如果满足（3 3）存在常数）存在常数00L L1,1,使对任意使对任意（1 1）迭代函数）迭代函数 在区间在区间 a a,b b 上可导；上可导；（2 2）当当x a,b时，时，；（1 1）方程）方程 在区间在区间 a a,b b 上有唯一的根上有唯一的根 ；（3 3）误差估计）误差估计产生的序列产生的序列 必收敛于方程的根必收敛于方程的根 ；第19页，共65页，编辑于2022年，星期六证明：由于由于 上连续，作辅助函数上连续，作辅助函数 故由连续函数的介值定理知，至少存在故由连续函数的介值定理知，至少存在又设 即即 有唯一的根。有唯一的根。(1)(1)先证方程根的存
12、在性。先证方程根的存在性。，即，即 是方程是方程 的根。的根。故由拉格朗日中值定理知，故由拉格朗日中值定理知，第20页，共65页，编辑于2022年，星期六（2）由拉格朗日中值定理）由拉格朗日中值定理,有有因其中介于 之间，故有第21页，共65页，编辑于2022年，星期六（3）由证毕第22页，共65页，编辑于2022年，星期六则对于任意的初值x0S，迭代公式 产生的序列 必收敛于方程的根 。3.3.迭代法的局部收敛定理迭代法的局部收敛定理迭代法的全局收敛性定理给出的是区间迭代法的全局收敛性定理给出的是区间 a a,b b 上的收敛性，上的收敛性，称之为称之为全局收敛性全局收敛性，一般不易验证，并
13、且在较大的隔根区间上，一般不易验证，并且在较大的隔根区间上此定理的条件不一定成立，而只能在根的一个较小的邻域内成此定理的条件不一定成立，而只能在根的一个较小的邻域内成立。下面给出局部收敛定理：立。下面给出局部收敛定理：定理2.（局部收敛定理）（局部收敛定理）设 是方程 的根，若满足：（1）迭代函数 在 的邻域可导；（2）在 的某个邻域 ，对于任意xS，有：第23页，共65页，编辑于2022年，星期六当xS，即 时，由Lagrange中值定理有将前述将前述定理定理1中的中的a,b取为取为 ，则，则只需证明只需证明 即可。即可。其中在x与x*之间，即S。证明：证明：证毕证毕 故第24页，共65页，
14、编辑于2022年，星期六Remark2Remark2：可以证明，若在根可以证明，若在根 的邻域中的邻域中 ，则，则可以以邻域内任何一点可以以邻域内任何一点 为初始值，用迭代过程产生为初始值，用迭代过程产生的序列就一定不会收敛于的序列就一定不会收敛于 。事实上，。事实上，Remark3Remark3：当当 不取在不取在 的邻域内时可能不收敛。的邻域内时可能不收敛。Remark1Remark1：全局与局部收敛定理中的条件都是全局与局部收敛定理中的条件都是充分充分条件，条件满足则迭代法收敛，不满足则不能判定，条件，条件满足则迭代法收敛，不满足则不能判定，此时可以用试算来判定迭代法的是收敛性。此时可以
15、用试算来判定迭代法的是收敛性。Remark4Remark4：全局收敛定理中的两个误差估计式实际上全局收敛定理中的两个误差估计式实际上给出了迭代收敛的两个准则：事后误差估计与事先误给出了迭代收敛的两个准则：事后误差估计与事先误差估计（利用估计式可以预先求出迭代次数差估计（利用估计式可以预先求出迭代次数k k）。）。第25页，共65页，编辑于2022年，星期六4.4.迭代收敛准则迭代收敛准则方法一、事先误差估计法方法一、事先误差估计法方法二、事后误差估计法方法二、事后误差估计法先计算满足误差要求的迭代次数先计算满足误差要求的迭代次数k k，再进行迭代。，再进行迭代。有有由由由由因此可以用因此可以用
16、 来控制迭代过程。来控制迭代过程。只要使只要使 ，就可使，就可使 ，对于较为复杂的迭代函数，其导数也较为复杂，对于较为复杂的迭代函数，其导数也较为复杂，使得使得L L难以取得，因而实际中不常用此方法。难以取得，因而实际中不常用此方法。第26页，共65页，编辑于2022年，星期六Remark1:Remark1:迭代方法的优点是计算程序简单，并迭代方法的优点是计算程序简单，并且虽然是以求解非线性方程的实根来讨论的，且虽然是以求解非线性方程的实根来讨论的，但类似的结果完全可以推广到求方程的复数根但类似的结果完全可以推广到求方程的复数根的情形。的情形。Remark2Remark2：由全局收敛定理知，若
17、由全局收敛定理知，若L L 1 1，则，则 x xk k 必然收敛较慢；若必然收敛较慢；若L L11，则收敛速度快。，则收敛速度快。第27页，共65页，编辑于2022年，星期六例 求 x3-2x-5=0在1.5，2.5上的根。解 1）2）若将迭代格式写为：第28页，共65页，编辑于2022年，星期六实验题目：用迭代法求方程在实验题目：用迭代法求方程在0,10,1内的根。内的根。为了获得较快的收敛速度你认为应该为了获得较快的收敛速度你认为应该写成怎样的等价方程？写成怎样的等价方程？第29页，共65页，编辑于2022年，星期六第30页，共65页，编辑于2022年，星期六Remark1:Remark
18、1:以特定的图形符号加上说明，表示算以特定的图形符号加上说明，表示算法的图，称为法的图，称为流程图或框图流程图或框图。Remark2Remark2：为便于识别，绘制习惯做法是：为便于识别，绘制习惯做法是：圆角矩形表示圆角矩形表示“开始开始”与与“结束结束”；矩形表示工作环节用矩形表示工作环节用 ；菱形表示问题菱形表示问题判断（审核）环节；判断（审核）环节；平行四边形表示输平行四边形表示输入输出；入输出；箭头代表工作流方向。箭头代表工作流方向。关于流程图关于流程图第31页，共65页，编辑于2022年，星期六时间表控制流程图时间表控制流程图第32页，共65页，编辑于2022年，星期六km是是输出输
19、出k=k+1是是否否输入输入k=0算法算法(迭代法迭代法)定义定义 已到最大迭代次数已到最大迭代次数否否结束结束开始开始第33页，共65页，编辑于2022年，星期六二、二、迭代法的收敛阶迭代法的收敛阶若若00C C1,11称为称为超线性收敛超线性收敛；p p2 2称为称为平方收敛平方收敛（二次收敛二次收敛）。）。p p 越大，收敛速度越快；反之，越大，收敛速度越快；反之，p p越小，收敛速度就越慢。因此，迭代法的收敛阶是对迭越小，收敛速度就越慢。因此，迭代法的收敛阶是对迭代法收敛速度的一种度量。代法收敛速度的一种度量。（C称为渐近误差常数）称为渐近误差常数）定义：定义：设设 收敛于收敛于 ，令
20、迭代误差，令迭代误差 ，如果存在实数，如果存在实数 及非零正常数及非零正常数C使得使得则称该迭代过程以及该迭代式是则称该迭代过程以及该迭代式是p p阶收敛的阶收敛的，也称相应，也称相应的迭代法是的迭代法是p p阶方法。阶方法。第34页，共65页，编辑于2022年，星期六1.1.迭代迭代-加速公式加速公式记记 ，则由微分中值定理有，则由微分中值定理有三、迭代法的加速三、迭代法的加速其中其中 在在xk与与x*之间。之间。假定假定 在根在根x*附近变化不大，可设附近变化不大，可设 ，由，由迭代收敛条件有迭代收敛条件有 ，故上式可写为：，故上式可写为：整理为：整理为：第35页，共65页，编辑于2022
21、年，星期六得到迭代加速公式得到迭代加速公式上上式式说说明明，把把 作作为为根根的的近近似似值值时时，其其绝绝对对误误差差大大致为致为 。如果把该误差值作为对。如果把该误差值作为对 的一种补偿，便可以得到更好的近似值的一种补偿，便可以得到更好的近似值记记第36页，共65页，编辑于2022年，星期六Remark3Remark3：该方法的缺点是需估计：该方法的缺点是需估计 的的近似值。近似值。Remark1Remark1：该迭代法对原迭代式的各近似值在根：该迭代法对原迭代式的各近似值在根x x*的两侧往复地趋于的两侧往复地趋于x x*时较为有效。在这种情时较为有效。在这种情况下，不但能加快新序列的收
22、敛，还能有效地况下，不但能加快新序列的收敛，还能有效地防止死循环的出现。防止死循环的出现。Remark2Remark2：若序列：若序列 x xk k 单调趋于单调趋于x x*时，上式不时，上式不能起到加速收敛的作用。能起到加速收敛的作用。第37页，共65页，编辑于2022年，星期六xyy=xx*y=(x)x0p0 x1p1 第38页，共65页，编辑于2022年，星期六2 2埃特金（埃特金（AitkenAitken）加速方法）加速方法记用平均变化率用平均变化率代替迭代加速公式中的代替迭代加速公式中的 ，于是有，于是有则从上式可以看出，第二项是对从上式可以看出，第二项是对 的一种补偿。的一种补偿。
23、第39页，共65页，编辑于2022年，星期六因此可以得下述因此可以得下述AitkenAitken加速方法：加速方法：RemarkRemark：因为迭代过程：因为迭代过程x xk k+1+1=(x xk k)总是在根总是在根x x*附近附近进行，因此用平均变化率代替迭代加速公式中进行，因此用平均变化率代替迭代加速公式中 的是有意义的。的是有意义的。记记第40页，共65页，编辑于2022年，星期六对于埃特金（对于埃特金（AitkenAitken）加速方法有如下的定理：）加速方法有如下的定理：定理3：如果由迭代公式xk+1=(xk)产生的数列xk 满足：（1 1）收敛于根）收敛于根x x*；（2）则
24、由埃特金（则由埃特金（Aitken）加速公式产生的数列）加速公式产生的数列 比数列比数列xk较快的收敛于根较快的收敛于根x*，即，即第41页，共65页，编辑于2022年，星期六取前两项近似代替取前两项近似代替 得近似得近似 的线性方程的线性方程一、一、NewtonNewton迭代法迭代法1.1.牛顿法的基本思想同牛顿法的基本思想同Newton-RaphsonNewton-Raphson公式公式2.3 Newton2.3 Newton迭代法迭代法设设 是是 的一个近似根，则的一个近似根，则基本思想基本思想：将非线性方程转化为线性方程来求解。：将非线性方程转化为线性方程来求解。第42页，共65页，
25、编辑于2022年，星期六由由 知知 是是 处处 的的切线切线 与与 轴交点的横坐标，轴交点的横坐标，F故故NewtonNewton法法的的几何意义几何意义是逐次用切线代替曲线，是逐次用切线代替曲线，求切线与横坐标轴的交点。求切线与横坐标轴的交点。F NewtonNewton法亦称为切线法法亦称为切线法。（如下图）。（如下图）设设 ,令解为令解为 得得显然是显然是 的同解方程。的同解方程。上式上式称为称为 的的Newton迭代法迭代法，对应的方程，对应的方程第43页，共65页，编辑于2022年，星期六x*x0 x1x2xyf(x)NewtonNewton迭代法逼近过程迭代法逼近过程第44页，共6
26、5页，编辑于2022年，星期六证明：证明：只需证满足迭代法局部收敛定理的两个条件。只需证满足迭代法局部收敛定理的两个条件。2.2.局部收敛性局部收敛性及条件（及条件（1 1）（）（2 2）知，）知，(x x)在在x x*的邻域可导。的邻域可导。定理（定理（Newton迭代法局部收敛性迭代法局部收敛性）：）：设设 为为 的的根，如果：（根，如果：（1 1）函数）函数f(x)f(x)在在 的邻域具有连续的二阶的邻域具有连续的二阶导数；（导数；（2 2）在）在 的邻域的邻域 。则存在则存在 的某个邻域的某个邻域 ，对于任意的初始，对于任意的初始值值x0 S，由，由Newton迭代公式产生的数列收敛于
27、根迭代公式产生的数列收敛于根 。由迭代函数由迭代函数 得得:第45页，共65页，编辑于2022年，星期六根据连续函数的性质，一定存在根据连续函数的性质，一定存在x x*的某个的某个邻域邻域 ，对于任意的，对于任意的x x S S，有，有RemarkRemark：上上述述定定理理对对于于初初值值x x0 0的的要要求求比比较较高高，只只有有当当初初值值选选的的充充分分靠靠近近时时，才才能能保证序列收敛。保证序列收敛。证毕显然又有显然又有第46页，共65页，编辑于2022年，星期六3.3.非局部收敛性非局部收敛性 定理（定理（NewtonNewton迭代法的非局部收敛性）：迭代法的非局部收敛性）：
28、设设x x*是方程是方程f f(x x)=0)=0在隔根区间在隔根区间 a a,b b 内的根，如果满足内的根，如果满足（2）取）取 使使（1）对于）对于x a,b，连续且不变号；连续且不变号；则由Newton迭代公式产生的数列收敛于根x*。Remark：定理的几何解释见下图。满足定理条件的定理的几何解释见下图。满足定理条件的情况只有情况只有4种。种。第47页，共65页，编辑于2022年，星期六yx0aby=f(x)x0(a)x x0 0取靠近取靠近b b一侧一侧yx0aby=f(x)x0(b)x x0 0取靠近取靠近a a一侧一侧yx0aby=f(x)x0(c)x x0 0取靠近取靠近a a
29、一侧一侧yx0aby=f(x)x0(d)x x0 0取靠近取靠近b b一侧一侧第48页，共65页，编辑于2022年，星期六证明：证明：仅就图仅就图(c c)的情况进行证明。此时，有的情况进行证明。此时，有要证要证 ，应证数列，应证数列 x xk k 单调递增上有界。单调递增上有界。（1 1）用数学归纳法证明数列上有界，即证）用数学归纳法证明数列上有界，即证x xk k x x*。k k0 0时，时，x xk k x x*成立。成立。一般的，设一般的，设x xk k x x*成立，再证成立，再证x xk k1 1 x x*成立即可。成立即可。将将f f(x x)在在x xk k处作一阶处作一阶T
30、aylorTaylor展开，展开，其中其中 k k在在x x与与x xk k之间。因为之间。因为x x，x xk k a a,b b,所以所以 k k(a a,b b)。第49页，共65页，编辑于2022年，星期六将将x=xx=x*代入上式，有代入上式，有于是有于是有由已知条件知，上式右端第二项小于零，从而由已知条件知，上式右端第二项小于零，从而有有x xk k1 1 x x*成立。成立。故由数学归纳法知，故由数学归纳法知，x xk k 00，则可以保证，则可以保证NewtonNewton迭代法的收敛性。迭代法的收敛性。第53页，共65页，编辑于2022年，星期六二、二、迭代法的收敛阶迭代法的
31、收敛阶若若00C C1,11称为称为超线性收敛超线性收敛；p p2 2称称为为平方收敛平方收敛（二次收敛二次收敛）。）。p p 越大，收敛速度越快；反之，越大，收敛速度越快；反之，p p越小，收敛速度就越慢。因此，迭代法的收敛阶是对迭代法收越小，收敛速度就越慢。因此，迭代法的收敛阶是对迭代法收敛速度的一种度量。敛速度的一种度量。（C称为渐近误差常数）称为渐近误差常数）定义：定义：设设 收敛于收敛于 ，令迭代误差，令迭代误差 ，如果存在实数，如果存在实数 及非零正常数及非零正常数C使得使得则称该迭代过程以及该迭代式是则称该迭代过程以及该迭代式是p p阶收敛的阶收敛的，也称相，也称相应的迭代法是应
32、的迭代法是p p阶方法。阶方法。第54页，共65页，编辑于2022年，星期六定理：定理：（1）在迭代法的局部收敛定理的条件下，）在迭代法的局部收敛定理的条件下，即即x*是方程是方程 的根，满足的根，满足迭代函数迭代函数 在在x*的邻域内可导，的邻域内可导，且在根且在根x*的某个邻域的某个邻域 内，内，对于任意对于任意x S，有，有 ，则迭代则迭代法是线性收敛的。法是线性收敛的。（2）由由Newton迭代公式迭代公式xk+1=(xk)产生的数列产生的数列xk 若满足若满足Newton迭代法的非局部收敛定理，则迭代法的非局部收敛定理，则Newton迭代法是平方收敛的。迭代法是平方收敛的。证明证明：
33、（：（1 1）因为迭代函数）因为迭代函数(x x)在根在根x x*的邻域内可的邻域内可导，故由导，故由LagrangeLagrange中值定理有中值定理有其中其中 在在x xk k与与x x*之间。之间。第55页，共65页，编辑于2022年，星期六由由 知，迭代法是线性收敛的。知，迭代法是线性收敛的。（2 2）由）由NewtonNewton迭代法的非局部收敛定理证明过程知，迭代法的非局部收敛定理证明过程知，即即因为因为 在邻域内不变号，故在邻域内不变号，故有有 即即NewtonNewton迭代法是平方收敛的。迭代法是平方收敛的。证毕证毕第56页，共65页，编辑于2022年，星期六三、牛顿迭代法
34、的变形三、牛顿迭代法的变形Newton迭代优点：迭代优点：格式构造容易；格式构造容易；迭代收敛速度快；迭代收敛速度快；Newton迭代缺点：迭代缺点：对初值的选取比较敏感，要求初值充对初值的选取比较敏感，要求初值充 分接近真解；分接近真解；对重根收敛速度较慢；对重根收敛速度较慢；当函数复杂时，导数计算工作量大当函数复杂时，导数计算工作量大第57页，共65页，编辑于2022年，星期六1 1牛顿下山法牛顿下山法牛顿迭代法依赖于牛顿迭代法依赖于x x0 0（1 1）敏感度高；）敏感度高；（2 2）对重根收敛慢；）对重根收敛慢；2.2.牛顿下山法牛顿下山法：修正：修正（1 1）选取下山因子；）选取下山
35、因子；第58页，共65页，编辑于2022年，星期六（4 4）计算）计算f f(x xk k+1+1)，并比较，并比较 与与 的大小，分以下二种情况：的大小，分以下二种情况：1 1）若）若 ，则当，则当 时，取时，取x x*x xk k+1+1，计算过程结束，计算过程结束;当当 时，则把时，则把x xk k+1+1作为新作为新的的x xk k值，并重复回到（值，并重复回到（3 3）。）。1 1牛顿下山法牛顿下山法牛顿下山法计算步骤可归纳如下：牛顿下山法计算步骤可归纳如下：（1 1）选取初始近似值）选取初始近似值x x0 0；（2 2）取下山因子）取下山因子 =1=1；（3 3）计算）计算第59页
36、，共65页，编辑于2022年，星期六当当 ；且且 ,则将下山因子缩小一半，则将下山因子缩小一半，取取/2/2代入，并转向（代入，并转向（3 3）重复计算。）重复计算。x xk k+1+1加上一个适当选定的小正数，加上一个适当选定的小正数，2）若若 ，则当，则当 且且 ，取，取x x*x xk k，计算过程结束；计算过程结束；否则若否则若 ，而，而 时，时，则把则把即取即取x xk k+1+1+作为新的作为新的x xk k值，值，并转向（并转向（3 3）重复计算；）重复计算；第60页，共65页，编辑于2022年，星期六例例5 5：求方程：求方程f f(x x)=)=x x3 3 x x 1=0
37、1=0 的根的根k xk010.611/251.14063211.36681311.32628411.32472牛顿下山法的计算结果：牛顿下山法的计算结果：第61页，共65页，编辑于2022年，星期六2 2针对重根情形的加速算法针对重根情形的加速算法设设 是方程的是方程的m m 重根，并且存在函数重根，并且存在函数 ，使得，使得 可见，此时牛顿迭代法仅为线性收敛可见，此时牛顿迭代法仅为线性收敛第62页，共65页，编辑于2022年，星期六法法1：令：令法法2：为加速收敛，可以采取如下两种方法：为加速收敛，可以采取如下两种方法：第63页，共65页，编辑于2022年，星期六3 3、单点弦截法单点弦截法 ：牛顿法一步要计算牛顿法一步要计算 f 和和 f，相当于，相当于2个函数值。现用个函数值。现用 f 的值的值近似近似 f :x0 x1切线切线 割线割线 切线斜率切线斜率 割线斜率割线斜率x2第64页，共65页，编辑于2022年，星期六4 4、双点弦截法双点弦截法 ：切线斜率切线斜率 割线斜率割线斜率需要需要2个初值个初值 x0 和和 x1。x0 x1x2第65页，共65页，编辑于2022年，星期六