第7章非线性方程与方程组的数值解法《数值分析》VIP

2020/4/30,1,第7章非线性方程与方程组的数值解法,7.1方程求根与二分法,7.1.1引言,方程求根的一般形式：,其中，,如果实数满足，则称是方程的根，,或称是函数的零点。,2020/4/30,2,若可分解为：,其中为正整数，且,则称为方程的重根，或为的重零点。,时为单根。,若为的重零点，且充分光滑，则,2020/4/30,3,方程性质不同，求解方法也有很大差异。,如果函数是多项式：,其中，为实数，则称方程为次代数方程。,次代数方程在复数域有且只有个根（含重根）。,当时不能用公式表示方程的根，只能数值求解。,2020/4/30,4,有根区间：,设函数在上连续，,则方程在区间内一定有实根，,称为方程的有根区间。,对于超越方程，例如：,在整个轴上有无穷多个解，取值范围不同，解也不同。,超远方程只能通过数值求解。,2020/4/30,5,逐次搜索法：,设连续函数存在有根区间,将等分，步长；,端点；,检查节点函数值,若，则可确定有根区间。,2020/4/30,6,P213例1求方程的有根区间。,解：，,在区间内至少有一个实根。,取步长，进行搜索计算：,方程的有根区间为，,2020/4/30,7,7.1.2二分法,计算方法：,计算区间中点函数值,若，则根为，,计算区间端点函数值、,否则：时，；,时，；,2020/4/30,8,反复计算，直到，,（预定的精度）,最终取值：。,误差：取有根区间的中点（二分次数）,作为近似根，则：,特点：算法简单，可保证收敛，但收敛太慢。用于求近似解。,2020/4/30,9,P214例2求方程在区间内的一个实根，要求准确到小数点后的第二位。,解：,注：，即,，,2020/4/30,10,7.2不动点迭代法及其收敛性,7.2.1不动点与不动点迭代法,将方程改写成等价形式：,若要求满足，则；反之亦然。,称为函数的一个不动点。,因此，求的零点就等价于求的不动点。,2020/4/30,11,选择一个初始近似值，代入迭代函数：,将新值作为近似值，再次代入迭代函数：,反复迭代，迭代方程：,，,迭代存在极限：,不动点迭代法：,则称迭代方程收敛，且为的不动点。,2020/4/30,12,实质：将隐式方程，通过迭代逐步显式化逐次逼近法。,几何意义：,直线与曲线,其交点横坐标就是方程的根。,逐次逼近：,（迭代收敛）,2020/4/30,13,P215例3求方程在附近的根。,解：迭代公式,，,注意：如果迭代公式为，则迭代发散。,2020/4/30,14,7.2.2不动点的存在性与迭代法的收敛性,定理1设函数满足以下两个条件：,（1）对于任意，有,（2）存在正常数，使对任意都有,（迭代函数在上）,（迭代函数的增量小于自变量的增量）,则在上存在唯一的不动点。,2020/4/30,15,证明：先证不动点存在性。,若，或：,则在上存在不动点。（不动点特点）,因，以下设及，定义：,显然，且满足,，,由连续函数性质可知：存在使,即，为的不动点。,2020/4/30,16,再证唯一性。,设及都是的不动点，则：,引出矛盾。故的不动点只能是唯一的。,在的不动点唯一的情况下，可得到迭代法收敛的充分条件。,2020/4/30,17,收敛到的不动点，并有误差估计,定理2设函数满足以下两个条件：,（1）对于任意，有,（2）存在正常数，使对任意都有,则对任意：,由得到的迭代序列,2020/4/30,18,证明：设是在上的唯一不动点。,由定理条件（1）可知：,由定理条件（2）可得：,反复应用上述结论：,因：故当时,，序列收敛到。,2020/4/30,19,再由定理条件（2）得：,如此反复递推得：,于是对于任意正整数有：,在上式令，注意到：,2020/4/30,20,讨论一：因正常数未知，上述误差估计无法使用。,对于任意正整数有：,令可得：,即：只要相邻两次计算结果的偏差足够小，就能保证近似值具有足够的精度。,2020/4/30,21,讨论二：在某些情形下可求得。,如果且对任意有,则，由中值定理可得：对有,因此，可将上述定理和定理中的条件（2）改为：,2020/4/30,22,P215例3求方程在附近的根。,例如：,（1）当时，在区间有：,由定理2可得：迭代法是收敛的。,（2）当时，在区间有：,不满足定理的条件，无法保证迭代收敛。,2020/4/30,23,7.2.3局部收敛性与收敛阶,对于区间上的任意，所产生的迭代序列都收敛，,称为全局收敛。,实际应用时，通常只在不动点邻居考察其收敛性，,称为局部收敛。,定义1设有不动点，如果存在的某个领域：,对任意，迭代产生序列，且收敛到，,则称迭代法局部收敛。,2020/4/30,24,且，则迭代法局部收敛。,定理3设为的不动点，在的某个领域连续，,证明：由连续函数的性质，存在的某个领域：,使对于任意有下式成立：,此外，对于任意，总有，这是因为：,依据定理2：迭代过程对于任意均收敛。,2020/4/30,25,P218题4用不同方法求方程的根。,解：这里，,可改写成不同的等价形式，其不动点为,（1）,，,，,（2）,，,，,2020/4/30,26,（3）,，,，,（4）,，,，,取，对上述4种迭代法，计算三步的结果如下表。,2020/4/30,27,说明：精确值，,迭代法（1）和（2）不收敛，迭代法（3）和（4）收敛；,迭代法（4）中比迭代法（3）小，,迭代法（4）比迭代法（3）收敛速度快。,2020/4/30,28,定义2设迭代过程收敛于方程的根，,如果当时迭代误差满足渐进关系式,，常数,则称该迭代过程是阶收敛的。,特别地，时称为线性收敛，,时为超线性收敛，时为平方收敛。,2020/4/30,29,定理4对于迭代过程及正整数，,如果在所求根的邻近连续，且,则该迭代过程在点邻近是阶收敛的。,证明：由于，根据定理3可得：,迭代过程具有局部收敛性。,2020/4/30,30,再将在根处泰勒展开，利用定理条件：,，在与之间,注意到，：,因此对迭代误差，当时有：,这表明迭代过程确实为阶收敛。,2020/4/30,31,迭代过程的收敛速度依赖于迭代函数的选取。,说明,定理表明：,如果时：,则该迭代过程只可能是线性收敛的。,在例4中：,迭代法（3）的，故它只能是线性收敛；,迭代法（4）的，迭代为二阶收敛。,2020/4/30,32,7.3迭代收敛的加速方法,7.3.1埃特金加速收敛方法,设是根的某个近似值，用迭代公式迭代一次：,由微分中值定理：,（在与之间）,假定变化不大：,，,2020/4/30,33,将校正值再迭代一次：,因而有：,消去：,可推得：,注意：上式是对两次迭代值加权平均后的结果，可加速迭代；,适用任何求根序列，不只局限于不动点迭代序列。,2020/4/30,34,已知求根序列，其三个相邻值为,埃特金加速法（加速法）：,加速计算，得到新值,，,，,点的一阶差分；,点的二阶差分；,可以证明：新序列的收敛速度比的收敛速度快,2020/4/30,35,7.3.2斯特芬森迭代法,把埃特金加速法与不动点迭代结合，就可得到斯特芬森迭代法：,斯特芬森迭代法是将两步迭代合成一步得到的：,2020/4/30,36,斯特芬森迭代法思路：,为求解的根，令：,已知的近似值及，其误差分别为：,把误差“外推到零”：,即过及两点做线性插值函数，,它与轴交点就是。,2020/4/30,37,即求解方程：,其解为：,即：,2020/4/30,38,定理5对于斯特芬森迭代法,若为迭代函数的不动点，则也为的不动点。,反之，若为的不动点，设存在，,则也是的不动点，且斯特芬森迭代法是二阶收敛的。,2020/4/30,39,P221例5用斯特芬森法求解方程。,解：用迭代公式求解方程是发散的。,改进上述迭代公式，斯特芬森迭代法：,，,2020/4/30,40,因，,P222例6求方程在中的解。,解：由方程得，并取对数,可构造迭代法,且时，由定理2此迭代法是收敛的。,若取迭代16次得，有六位有效数字。,若用斯特芬森迭代法加速：,2020/4/30,41,7.4牛顿法,7.4.1牛顿法及其收敛性,牛顿法基本思想：将非线性方程转化线性方程求解。,设已知方程有近似根，,将函数在点展开,于是方程可近似表示为,这是个线性方程，其根为（牛顿法）,2020/4/30,42,牛顿法的几何解释：,方程的根为,曲线与轴交点的横坐标。,设是根的某个近似值，,过曲线上点引切线，,切线与轴交点的横坐标作为新解,切线方程：（点斜式方程）,其根为牛顿法的近似解切线法。,2020/4/30,43,讨论：牛顿法的收敛性。,，,假定是的一个单根：,，,代入上式，可得：,，,因此：牛顿法在根邻近是平方收敛的。,2020/4/30,44,P223例7用牛顿法解方程。,解：牛顿公式为,取迭代初值,2020/4/30,45,牛顿法计算步骤：,第一步准备：选定初值，,计算，,第二步迭代：迭代一次，,计算，,第三步控制：计算迭代误差，（控制常数）,，当时,，当时,2020/4/30,46,否则以代替，,或者，则方法失败；,第四步修改：如果迭代次数达到预先指定的次数，,如果满足：,或（、允许误差）,则迭代收敛，以作为所求的根，否则转第四步。,转第二步继续迭代。,2020/4/30,47,7.4.2牛顿法应用举例,对于给定正数，开方计算,转变为应用牛顿法解方程。,，,可以证明：对于任意初值迭代都收敛。,2020/4/30,48,证明：由迭代公式：,两式相除：,反复递推：,2020/4/30,49,假设：,解出：,因此：,对于任意，总有，,当时，即迭代过程恒收敛。,2020/4/30,50,迭代函数为，要求,7.4.3简化牛顿法与牛顿下山法,牛顿法缺点：每次迭代都要计算及，有时计算困难。,初始值在根附近才能保证收敛，取值不合适可能不收敛。,（1）简化牛顿法（平行弦法）,迭代公式为,其中常量，并保证迭代收敛,，即,若上式在根附近成立，则该迭代法局部收敛。,2020/4/30,51,若取为处之值，则有简化牛顿法,特点：节省了计算量，但只有线性收敛。,几何意义：,用斜率为的平行弦,与轴的交点作为的近似。,2020/4/30,52,（2）牛顿下山法,问题：牛顿法的收敛性依赖于初值。,例如：用牛顿法求解方程,公式：,如果：取迭代初值,，,，,如果：取迭代初值,，,，结果偏离了根,2020/4/30,53,为防止迭代发散，要求迭代过程具有单调性,下山法,牛顿下山法：下山法保证函数值稳定下降，牛顿法加速收敛,先用牛顿法初步迭代,在将近似值与加权平均,其中下山因子：,2020/4/30,54,下山因子选择：从开始，逐次减半试算，,直到满足下山法要求,例如：求解方程，牛顿下山法公式为,当，时，求得，且,结果不满足下山法要求，无法继续迭代，需改进值。,2020/4/30,55,逐次对减半试算：当时，求得,以为初值，取，迭代收敛,注意：下山因子减半试算，只为确定使迭代收敛的初值。,2020/4/30,56,7.4.4重根情形,设，整数，,则为方程的重根，此时有：,方法1：只要仍可用牛顿法,此时迭代函数为，其导数为,，且,所以牛顿法求重根只是线性收敛。,2020/4/30,57,改进迭代函数,此时有,因此，用改进的迭代公式求重根具有二阶收敛性。,改进的迭代公式为,缺点：需要知道的重根数。,2020/4/30,58,方法2：重新构造求重根的迭代法,令，若是的重根,故是的单根。,由此应用牛顿法，迭代函数为,从而可构造二阶收敛的迭代法,特点：无需知道值，但要计算。,2020/4/30,59,P227例9方程的根是二重根。用上述三种方法求根。,解：三种方法的迭代公式为,（1）牛顿法,（2）改进法,（3）重构法,2020/4/30,60,取初值，计算结果如下:,注意：方法（2）和（3)均达到10位有效数字，,而牛顿法达到同样精度需迭代30次。,2020/4/30,61,7.5弦截法与抛物线法,7.5.1弦截法,牛顿法问题：每步需计算，当函数复杂时较困难。,设、是的近似根,由、构造一次插值多项式,用的根作为的新的近似根,2020/4/30,62,代入牛顿公式，即得弦截法结果：,用差商取代导数：,弦截法几何意义：,过曲线上横坐标为的两点,作弦线，其方程为,弦线与轴交点的横坐标即为,2020/4/30,63,P229例10用弦截法解方程。,解：迭代公式为,选取开始值为,注意：弦截法比牛顿法收敛速度快；,计算时要用到前两步的结果。,2020/4/30,64,弦截法具有超线性的收敛性,定理6假设在根的邻域：内,具有二阶连续导数，且对任意有,又初值，那么当邻域充分小时，,弦截法将按阶收敛到。,这里是方程的正根。,2020/4/30,65,7.5.2抛物线法,设已知方程的三个近似根、,以这三点为节点构造二次插值多项式,适当选取的一个零点作为新的近似根,抛物线法（密勒法