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

2023年2月1日1第7章非线性方程与方程组的数值解法7.1方程求根与二分法7.1.1引言方程求根的一般形式：其中，如果实数满足，

则称是方程的根，或称是函数的零点。2023年2月1日2若可分解为：其中为正整数，且则称为方程的重根，或为的重零点。时为单根。若为的重零点，且充分光滑，则2023年2月1日3方程性质不同，求解方法也有很大差异。如果函数是多项式：其中，为实数，则称方程为次代数方程。

次代数方程在复数域有且只有个根（含重根）。当时不能用公式表示方程的根，只能数值求解。2023年2月1日4有根区间：设函数在上连续，则方程在区间内一定有实根，称为方程的有根区间。对于超越方程，例如：在整个轴上有无穷多个解，取值范围不同，解也不同。超远方程只能通过数值求解。2023年2月1日5逐次搜索法：设连续函数存在有根区间①将等分，步长；②端点；③检查节点函数值④若，则可确定有根区间。2023年2月1日6P213例1求方程的有根区间。解：，在区间内至少有一个实根。取步长，进行搜索计算：方程的有根区间为，，2023年2月1日77.1.2二分法计算方法：②计算区间中点函数值

③若，则根为，

①计算区间端点函数值、否则：时，；

时，；

2023年2月1日8④反复计算，直到，（——预定的精度）最终取值：。误差：取有根区间的中点（——二分次数）作为近似根，则：特点：算法简单，可保证收敛，但收敛太慢。用于求近似解。2023年2月1日9P214例2求方程在区间内的一个实根，要求准确到小数点后的第二位。解：注：，即，2023年2月1日107.2不动点迭代法及其收敛性7.2.1不动点与不动点迭代法将方程改写成等价形式：若要求满足，则；反之亦然。——称为函数的一个不动点。因此，求的零点就等价于求的不动点。2023年2月1日11①选择一个初始近似值，代入迭代函数：②将新值作为近似值，再次代入迭代函数：③反复迭代，迭代方程：，④迭代存在极限：不动点迭代法：则称迭代方程收敛，且为的不动点。2023年2月1日12实质：将隐式方程，通过迭代逐步显式化——逐次逼近法。几何意义：直线与曲线其交点横坐标就是方程的根。逐次逼近：（迭代收敛）2023年2月1日13P215例3求方程在附近的根。解：迭代公式，注意：如果迭代公式为，则迭代发散。2023年2月1日147.2.2不动点的存在性与迭代法的收敛性定理1设函数满足以下两个条件：（1）

对于任意，有（2）

存在正常数，使对任意都有（迭代函数在上）（迭代函数的增量小于自变量的增量）则在上存在唯一的不动点。2023年2月1日15证明：先证不动点存在性。若，或：则在上存在不动点。（不动点特点）因，以下设及，定义：显然，且满足，由连续函数性质可知：存在使即，为的不动点。2023年2月1日16再证唯一性。设及都是的不动点，则：引出矛盾。故的不动点只能是唯一的。在的不动点唯一的情况下，可得到迭代法收敛的充分条件。收敛到的不动点，并有误差估计2023年2月1日17定理2设函数满足以下两个条件：（1）

对于任意，有（2）

存在正常数，使对任意都有则对任意：由得到的迭代序列2023年2月1日18证明：设是在上的唯一不动点。由定理条件（1）可知：由定理条件（2）可得：反复应用上述结论：因：故当时，序列收敛到。2023年2月1日19再由定理条件（2）得：如此反复递推得：于是对于任意正整数有：在上式令，注意到：2023年2月1日20讨论一：因正常数未知，上述误差估计无法使用。对于任意正整数有：令可得：即：只要相邻两次计算结果的偏差足够小，

就能保证近似值具有足够的精度。2023年2月1日21讨论二：在某些情形下可求得。如果且对任意有则，由中值定理可得：对有因此，可将上述定理

和定理中的条件（2）改为：2023年2月1日22P215例3求方程在附近的根。例如：（1）当时，在区间有：由定理2可得：迭代法是收敛的。（2）当时，在区间有：不满足定理的条件，无法保证迭代收敛。2023年2月1日237.2.3局部收敛性与收敛阶对于区间上的任意，所产生的迭代序列都收敛，——称为全局收敛。实际应用时，通常只在不动点邻居考察其收敛性，——称为局部收敛。定义1设有不动点，如果存在的某个领域：对任意，迭代产生序列，且收敛到，则称迭代法局部收敛。且，则迭代法局部收敛。定理3设为的不动点，在的某个领域连续，2023年2月1日24证明：由连续函数的性质，存在的某个领域：使对于任意有下式成立：此外，对于任意，总有，这是因为：依据定理2：迭代过程对于任意均收敛。2023年2月1日25P218题4用不同方法求方程的根。解：这里，可改写成不同的等价形式，其不动点为（1），，（2），，2023年2月1日26（3），，（4），，取，对上述4种迭代法，计算三步的结果如下表。2023年2月1日27说明：①精确值，迭代法（1）和（2）不收敛，迭代法（3）和（4）收敛；②迭代法（4）中比迭代法（3）小，迭代法（4）比迭代法（3）收敛速度快。2023年2月1日28定义2设迭代过程收敛于方程的根，如果当时迭代误差满足渐进关系式，常数则称该迭代过程是阶收敛的。特别地，时称为线性收敛，时为超线性收敛，时为平方收敛。2023年2月1日29定理4对于迭代过程及正整数，如果在所求根的邻近连续，且则该迭代过程在点邻近是阶收敛的。证明：由于，根据定理3可得：迭代过程具有局部收敛性。再将在根处泰勒展开，利用定理条件：2023年2月1日30，在与之间注意到，：因此对迭代误差，当时有：这表明迭代过程确实为阶收敛。迭代过程的收敛速度依赖于迭代函数的选取。2023年2月1日31说明①定理表明：②如果时：则该迭代过程只可能是线性收敛的。③在例4中：迭代法（3）的，故它只能是线性收敛；迭代法（4）的，，迭代为二阶收敛。2023年2月1日327.3迭代收敛的加速方法7.3.1埃特金加速收敛方法设是根的某个近似值，用迭代公式迭代一次：由微分中值定理：（在与之间）假定变化不大：，2023年2月1日33将校正值再迭代一次：因而有：消去：可推得：注意：①上式是对两次迭代值加权平均后的结果，可加速迭代；②适用任何求根序列，不只局限于不动点迭代序列。已知求根序列，其三个相邻值为2023年2月1日34埃特金加速法（加速法）：加速计算，得到新值，，——点的一阶差分；——点的二阶差分；可以证明：新序列的收敛速度比的收敛速度快2023年2月1日357.3.2斯特芬森迭代法把埃特金加速法与不动点迭代结合，就可得到斯特芬森迭代法：斯特芬森迭代法是将两步迭代合成一步得到的：2023年2月1日36斯特芬森迭代法思路：为求解的根，令：已知的近似值及，其误差分别为：把误差“外推到零”：即过及两点做线性插值函数，它与轴交点就是。2023年2月1日37即求解方程：其解为：即：2023年2月1日38定理5对于斯特芬森迭代法若为迭代函数的不动点，则也为的不动点。反之，若为的不动点，设存在，则也是的不动点，且斯特芬森迭代法是二阶收敛的。2023年2月1日39P221例5

用斯特芬森法求解方程。解：用迭代公式求解方程是发散的。改进上述迭代公式，斯特芬森迭代法：，因，，2023年2月1日40P222例6

求方程在中的解。解：由方程得，并取对数可构造迭代法且时，，由定理2此迭代法是收敛的。若取迭代16次得，有六位有效数字。若用斯特芬森迭代法加速：2023年2月1日417.4牛顿法7.4.1牛顿法及其收敛性牛顿法基本思想：将非线性方程转化线性方程求解。设已知方程有近似根，将函数在点展开于是方程可近似表示为这是个线性方程，其根为（牛顿法）2023年2月1日42牛顿法的几何解释：方程的根为曲线与轴交点的横坐标。设是根的某个近似值，过曲线上点引切线，切线与轴交点的横坐标作为新解切线方程：（点斜式方程）其根为牛顿法的近似解——切线法。2023年2月1日43讨论：牛顿法的收敛性。，假定是的一个单根：，代入上式，可得：，因此：牛顿法在根邻近是平方收敛的。2023年2月1日44P223例7

用牛顿法解方程。解：牛顿公式为取迭代初值2023年2月1日45牛顿法计算步骤：第一步准备：选定初值，计算，第二步迭代：迭代一次，计算，第三步控制：计算迭代误差，（控制常数），当时，当时2023年2月1日46否则以代替，或者，则方法失败；第四步修改：如果迭代次数达到预先指定的次数，如果满足：或（、允许误差）则迭代收敛，以作为所求的根，否则转第四步。转第二步继续迭代。2023年2月1日477.4.2牛顿法应用举例对于给定正数，开方计算转变为应用牛顿法解方程。，可以证明：对于任意初值迭代都收敛。2023年2月1日48证明：由迭代公式：两式相除：反复递推：2023年2月1日49假设：解出：因此：对于任意，总有，当时，，即迭代过程恒收敛。迭代函数为，要求2023年2月1日507.4.3简化牛顿法与牛顿下山法牛顿法缺点：①每次迭代都要计算及，有时计算困难。②初始值在根附近才能保证收敛，取值不合适可能不收敛。（1）简化牛顿法（平行弦法）迭代公式为其中常量，并保证迭代收敛，即若上式在根附近成立，则该迭代法局部收敛。2023年2月1日51若取为处之值，则有简化牛顿法特点：节省了计算量，但只有线性收敛。几何意义：用斜率为的平行弦与轴的交点作为的近似。2023年2月1日52（2）牛顿下山法问题：牛顿法的收敛性依赖于初值。例如：用牛顿法求解方程公式：如果：取迭代初值，，如果：取迭代初值，，结果偏离了根2023年2月1日53为防止迭代发散，要求迭代过程具有单调性——下山法牛顿下山法：下山法保证函数值稳定下降，牛顿法加速收敛先用牛顿法初步迭代在将近似值与加权平均其中下山因子：2023年2月1日54下山因子选择：从开始，逐次减半试算，直到满足下山法要求例如：求解方程，牛顿下山法公式为当，时，求得，且结果不满足下山法要求，无法继续迭代，需改进值。2023年2月1日55逐次对减半试算：当时，求得以为初值，取，迭代收敛注意：下山因子减半试算，只为确定使迭代收敛的初值。2023年2月1日567.4.4重根情形设，整数，则为方程的重根，此时有：方法1：只要仍可用牛顿法此时迭代函数为，其导数为，且所以牛顿法求重根只是线性收敛。2023年2月1日57改进迭代函数此时有因此，用改进的迭代公式求重根具有二阶收敛性。改进的迭代公式为缺点：需要知道的重根数。2023年2月1日58方法2：重新构造求重根的迭代法令，若是的重根故是的单根。由此应用牛顿法，迭代函数为从而可构造二阶收敛的迭代法特点：无需知道值，但要计算。2023年2月1日59P227例9

方程的根是二重根。

用上述三种方法求根。解：三种方法的迭代公式为（1）牛顿法（2）改进法（3）重构法2023年2月1日60取初值，计算结果如下:注意：方法（2）和（3)均达到10位有效数字，而牛顿法达到同样精度需迭代30次。2023年2月1日617.5弦截法与抛物线法7.5.1弦截法牛顿法问题：每步需计算，当函数复杂时较困难。设、是的近似根由、构造