方程求根的迭代法

§4.1引言绪论中讲到方程求根得二分法，但二分法收敛速度慢，有必要掌握新的方法。§4.迭代法是一种逐次逼近法，使用某个固定公式〔迭代公式〕反复校正，逐步精确，直到满足精度。迭代法求根分两步：猜想初值2〕迭代如求解初值问题用梯形公式〔1〕看作关于的函数方程，按欧拉公式提供猜想值，代入〔1〕得假设仍不满足要求，那么将它代入〔1〕式，继续得到校正值，写成迭代公式〔2〕一般地，为了求一元非线性方程的根，可以先将其转换为如下的等价形式〔3〕式〔3〕中连续函数称为迭代函数，其右端含未知数，不能直接求解。先用根的某个猜想值代入〔3〕，构造迭代公式：。如果迭代值有极限，那么称迭代收敛，极限值就是方程〔3〕的根。几何意义P127图4-1为使迭代法有效，必须保证它的收敛行，满足什么条件，才能保证收敛？以最简单的线性迭代，可以看出收敛的充分必要条件。几何意义P127图4-2,3,4,5。§4.设是方程的根，那么由微分中值定理，如果存在，使得有，那么迭代误差，由于，故，即迭代收敛。需注意，上述过程中需保证一切迭代值全落在，为此要求对任意，总有。综上，压缩映像原理：定理1设在上具有连续的一阶导数，满足条件：〔1〕对任意，总有。映内性〔2〕存在，使得对于任意成立。压缩性那么迭代过程对于任意初值均收敛于方程的根，且有以下误差估计式：证明：由有从而有，〔7〕式得证，结合〔7〕式得由〔7〕式知只要的偏差足够小，就能保证迭代值足够准确，可用来控制迭代过程是否结束。流程图见P128图4－6。例1P130P142题3，5，6，7注意迭代函数的选择，同一方程，可以采用不同的迭代函数，但迭代函数可能不收敛，或收敛缓慢，迭代函数的选择非常重要。§4.在方程求根的迭代法中，迭代函数确实定，至关重要，它直接影响着迭代法的收敛性。但在实际应用中，同一个方程可以等价导出不同的迭代函数，而且要严格地利用定理1的条件判断迭代公式在整个区间内收敛〔全局收敛〕也非常困难，因此常常判断迭代公式的局部收敛性。通常在根的邻近考察。如果存在邻域，使得迭代过程对于任意初值均收敛，这种收敛性称为局部收敛性。定理2设在的根邻近有一阶导数，且成立，那么迭代过程在邻近具有局部收敛性。证：存在充分小邻域，使，L为某个定数，根据微分中值定理：，注意到，又当时，故有，即由定理1知对于任意均收敛。例2P131§4.迭代误差，当时，称迭代过程为P阶收敛的，P＝1称线性收敛，P＝2称为平方收敛。对于在根邻近收敛的迭代公式，由于，式中介于和之间，故有，假设，那么为线性收敛。假设，将在处进行泰勒展开有：，又，，由上式知，说明当，时平方收敛。故有下述论断：定理3设在在根的邻近有连续的二阶导数，且，那么时线性收敛；当，时平方收敛。例P146题3§4.2迭代过程的加速§4.迭代过程收敛缓慢，计算量将很大，需要进行加速。设是根的某个近似值，用迭代公式校正一次得，假设在所考察得范围内变化不大，其估计值为L，那么有：有迭代公式，是比更好的近似根。这样加工后的计算过程为：迭代改良合并的例3P133§4.上述加速方法含有导数，不便于计算。设将迭代值再迭代一次，又得，由于又，消去L得计算过程如下：迭代迭代改良§4.3牛顿法§4.对于方程，设它的近似根，函数在处可用一阶泰勒展开来近似，取的根作为的新的近似根，记作，那么：，这就是牛顿公式，相应的迭代函数是牛顿法是一种逐步线性化方法，将非线性方程的求根问题归结为计算一系列的根。牛顿法几何意义是：(牛顿法亦称切线法，直线经过、)，流程图P136图4－9例5：P137牛顿法收敛很快。其迭代公式假定是的单根，即，，那么由上式知。故牛顿法至少平方收敛定理4牛顿法在的单根附近为平方收敛。(局部收敛)证：1〕由知，故其局部收敛。2〕代入得由上式得，故单根时平方收敛。但当是的重根时，牛顿法线性收敛。因，其中有二阶导数，且故，当m>1时，且有，故线性收敛。§4.3.给定正数c，用牛顿法解二次方程的计算公式，设是近似根，那么也是近似根，它们的算术平均将是更好的近似值。定理5开方公式对于任意给定初值均为平方收敛。证明：〔15〕两式相除得令，那么由上式得对任意，总有，故有，收敛性得证。由〔15〕，迭代误差，有，迭代过程为平方收敛。§4.例7P138为防止迭代发散，通常对迭代过程附加一项要求，即保证函数单调下降：，称为下山法。将牛顿法与下山法结合，在下山法保证函数值稳定下降得前提下，用牛顿法加快收敛速度。由牛顿法有，与前一步的近似值适当加权平均作为新值：其中，称为下山因子，选取适当的下山因子使单调条件成立。下山因子的选择，可从开始反复折半，一旦单调性条件成立，称下山成功。如果单调性条件始终不成立，那么下山失败，需要重新选择初值进行计算。牛顿法的收敛性强烈依赖于初值的选择，实际计算中，可先采用二分法，求得足够精确的近似值，再用牛顿法。§4.4弦截法牛顿法的收敛速度快，但需要提供导数值，如果比拟复杂，导数的计算困难，为防止求导数，改用差商替换牛