《数值分析》PPT课件.ppt

1,第7章 非线性方程与方程组的数值解法,7.1 方程求根与二分法 7.2 不动点迭代法及其收敛性 7.3 迭代收敛的加速方法 7.4 牛顿法 7.5 弦截法与抛物线法 7.6 求根问题的敏感性与多项式的零点7.7 非线性方程组的数值解法,2,7.1 方程求根与二分法,引言,（1.1）,本章主要讨论求解单变量非线性方程,其中 也可以是无穷区间.,如果实数 满足，则称 是方程(1.1)的根，或称 是 的零点.,3,若 可分解为,其中 为正整数，且 则称 为方程(1.1)的 重根，或 为 的 重零点，时为单根.,若 是 的 重零点，且 充分光滑，则,如果函数 是多项式函数，即,（1.2）,其中 为实数，则称方程(1.1)为 次代数方程.,4,它在整个 轴上有无穷多个解，若 取值范围不同，解也不同，因此讨论非线性方程(1.1)的求解必须强调 的定义域，即 的求解区间,时的求根公式是熟知的，时的求根公式可在数学手册中查到，但比较复杂不适合数值计算，当 时就不能用公式表示方程的根，所以 时求根仍用一般的数值方法,根据代数基本定理可知,次方程在复数域有且只有 个根（含重根，重根为 个根）.,另一类是超越方程，例如,5,迭代法要求先给出根 的一个近似，若 且，根据连续函数性质可知 在 内至少有一个实根，这时称 为方程(1.1)的有根区间.,非线性问题一般不存在直接的求解公式，故没有直接方法求解，都要使用迭代法.,通常可通过逐次搜索法求得方程 的有根区间.,6,例1 求方程 的有根区间.,解 根据有根区间定义，对 的根进行搜索计算，结果如下：,由此可知方程的有根区间为,7,检查 与 是否同号，如果同号，说明所求的根 在 的右侧,这时令否则 必在 的左侧，这时令见图7-1.,考察有根区间，取中点 将它分为两半，,二分法,假设中点 不是 的零点，然后进行根的搜索.,图7-1,不管出现哪一种情况，新的有根区间 的长度仅为 的一半.,8,对压缩了的有根区间 又可施行同样的手续，即用中点 将区间 再分为两半，然后通过根的搜索判定所求的根在 的哪一侧，从而又确定一个新的有根区间，其长度是 的一半.,如此反复二分下去，即可得出一系列有根区间,其中每个区间都是前一个区间的一半，因此 的长度,当 时趋于零.,9,就是说，如果二分过程无限地继续下去，这些区间最终必收缩于一点，该点显然就是所求的根.,作为根的近似，则在二分过程中可以获得一个近似根的序列,该序列必以根 为极限.,每次二分后，设取有根区间 的中点,10,由于,只要二分足够多次（即 充分大），便有,这里 为预定的精度.,（1.3）,11,例2 求方程,在区间 内的一个实根，要求准确到小数点后第2位.,解 这里，而,取 的中点，将区间二等分，由于，即 与 同号，故所求的根 必在 右侧，这时应令，而得到新的有根区间,如此反复二分下去,按误差估计（1.3）式,欲使,只需，即只要二分6次，便能达到预定的精度.,12,计算结果如表7-2.,13,二分法是计算机上的一种常用算法，计算步骤为：,步骤1 准备 计算 在有根区间 端点处的值,步骤2 二分 计算 在区间中点 处的值,步骤3 判断 若，则 即是根，计算过程结束，否则检验.,若，则以 代替，否则以,代替.,14,此时中点 即为所求近似根.,15,7.2 不动点迭代法及其收敛性,不动点与不动点迭代法,将方程（1.1）改写成等价的形式,（2.1）,若 满足，则；反之亦然，称为函数 的一个不动点.,求 的零点就等价于求 的不动点.,选择一个初始近似值，将它代入(2.1)右端，即可求得,16,如此反复迭代计算,（2.2）,称为迭代函数.,如果对任何，由（2.2）得到的序列 有极限,则称迭代方程(2.2)收敛，且 为 的不动点，故称（2.2）为不动点迭代法.,17,方程 的求根问题在 平面上就是要确定曲线 与直线 的交点,对于 的某个近似值，在曲线 上可确定一点，它以 为横坐标，而纵坐标则等于,就是说，迭代过程实质上是一个逐步显示化的过程.,过 引平行 轴的直线，设此直线交直线 于点，,然后过 再作平行于 轴的直线，,与曲线 的交点,上述迭代法是一种逐次逼近法，其基本思想是将隐式方程 归结为一组显式的计算公式.,18,则点 的横坐标为，,图7-2,记作，,纵坐标则等于,按图7-2中箭头所示的路径继续做下去.,在曲线 上得到点列，,其横坐标分别为,19,例3 求方程,（2.3）,在 附近的根,解 设将方程（2.3）改写成下列形式,依公式 求得的迭代值,如果点列 趋向于点，则相应的迭代值 收敛到所求的根,据此建立迭代公式,20,各步迭代的结果见表7-3.,这时可以认为 实际上已满足方程(2.3)，即为所求的根.,如果仅取6位数字，那么结果 与 完全相同，,21,但若采用方程（2.3）的另一种等价形式,建立迭代公式,仍取迭代初值，则有,结果会越来越大，不可能趋于某个极限.,这种不收敛的迭代过程称作是发散的.如图7-3.,一个发散的迭代过程，纵使进行了千百次迭代，其结果也是毫无价值的.,图7-3,22,不动点的存在性与迭代法的收敛性,首先考察 在 上不动点的存在唯一性.,定理1 设 满足以下两个条件：,1.对任意 有,2.存在正常数，使对任意 都有,（2.4）,则 在 上存在唯一的不动点,23,因，,以下设 及，,若 或，则不动点为 或，,存在性得证.,定义函数,显然，,由连续函数性质可知存在,且满足,使,即,即为 的不动点.,证明 先证不动点存在性.,24,再证唯一性.,设 都是 的不动点，,引出矛盾.故 的不动点只能是唯一的.,则由(2.4)得,25,（2.5）,定理2 设 满足定理1中的两个条件，则对任意，由（2.2）得到的迭代序列 收敛到 的不动点，并有误差估计,证明 设 是 在 上的唯一不动点，由条件，可知，再由（2.4）得,因，故当 时序列 收敛到.,26,再证明估计式（2.5），,由（2.4）有,（2.6）,反复递推得,于是对任意正整数 有,27,在上式令，注意到 即得式（2.5）.,迭代过程是个极限过程.,在用迭代法实际计算时，必须按精度要求控制迭代次数.,原则上可以用误差估计式（2.5）确定迭代次数，但由于它含有信息 而不便于实际应用.,根据式（2.6），对任意正整数 有,在上式中令 知,28,对定理1和定理2中的条件2，如果且对任意 有,（2.7）,则由中值定理可知对 有,表明定理中的条件2可用（2.7）代替.,29,例3中，当 时，,在区间 中，故（2.7）成立.,又因，故定理1中条件1也成立.所以迭代法是收敛的.,而当 时，在区间 中 不满足定理条件.,30,局部收敛性与收敛阶,上面给出了迭代序列 在区间 上的收敛性，,定理的条件有时不易检验，实际应用时通常只在不动点 的邻近考察其收敛性，即局部收敛性.,定义1 设 有不动点，如果存在 的某个邻域 对任意，迭代（2.2）产生的序列 且收敛到，则称迭代法（2.2）局部收敛.,通常称为全局收敛性.,31,证明 由连续函数的性质，存在 的某个邻域 使对于任意 成立,定理3 设 为 的不动点，在 的某个邻域连续，且，则迭代法（2.2）局部收敛.,此外，,对于任意，,总有，,于是依据定理2可以断定迭代过程 对于任意初值 均收敛.,这是因为,32,讨论迭代序列的收敛速度.,例4 用不同方法求方程 的根,解 这里，可改写为各种不同的等价形式 其不动点为 由此构造不同的迭代法：,33,取，对上述4种迭代法，计算三步所得的结果如下表.,34,从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件.,注意.,迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中.,35,定义2 设迭代过程 收敛于方程的根，如果迭代误差 当 时成立下列渐近关系式,则称该迭代过程是 阶收敛的.,特别地,时称线性收敛，,时称超线性收敛，,时称平方收敛.,36,定理4 对于迭代过程，如果 在所求根 的邻近连续，并且,则该迭代过程在点 邻近是 阶收敛的.,（2.8）,证明 由于，据定理3立即可以断定迭代过程 具有局部收敛性.,再将 在根 处做泰勒展开，利用条件（2.8），,则有,37,注意到，,因此对迭代误差，,当 时有,（2.9）,这表明迭代过程 确实为 阶收敛.,由上式得,上述定理说明，迭代过程的收敛速度依赖于迭代函数 的选取.,如果当 时，则该迭代过程只可能是线性收敛.,38,在例4中，迭代法（3）的，故它只是线性收敛.,而迭代法（4）的，而 由定理4知，该迭代过程为2阶收敛.,39,7.3 迭代收敛的加速方法,埃特金加速收敛方法,设 是根 的某个近似值，用迭代公式迭代一次得,由微分中值定理，有,其中 介于 与 之间.,假定 改变不大，近似地取某个近似值，,（3.1）,则有,40,由于,将它与（3.1）式联立，消去未知的，,由此推知,在计算了 及 之后，可用上式右端作为 的新近似，记作.,若将校正值 再迭代一次，又得,有,41,一般情形是由 计算，,(3.2)称为埃特金（Aitken）加速方法.,可以证明,它表明序列 的收敛速度比 的收敛速度快.,（3.2）,记,42,斯蒂芬森迭代法,埃特金方法不管原序列 是怎样产生的，对 进行加速计算，得到序列.,如果把埃特金加速技巧与不动点迭代结合，则可得到如下的迭代法：,称为斯蒂芬森(Steffensen)迭代法.,（3.3）,43,它的理解为，要求 的根，,已知 的近似值 及，其误差分别为,过 及 两点做线性插值函数.,它与 轴交点就是（3.3）中的，即方程,的解,令,44,实际上（3.3）是将不动点迭代法（2.2）计算两步合并成一步得到的，可将它写成另一种不动点迭代,（3.4）,其中,（3.5）,45,定理5 若 为（3.5）定义的迭代函数 的不动点，则 为 的不动点.反之，若 为 的不动点，设 存在，则 是 的不动点，且斯蒂芬森迭代法（3.3）是2阶收敛的.,解 例3中已指出,下列迭代,是发散的，现用(3.3)计算，取.,例5 用斯蒂芬森迭代法求解方程,计算结果如下表.,46,至于原来已收敛的迭代法（2.2），由定理5可知它可达到2阶收敛.,计算表明它是收敛的，这说明即使迭代法（2.2）不收敛，用斯蒂芬森迭代法（3.3）仍可能收敛.,47,例6 求方程 在 中的解.,解 由方程得等价形式，取对数得,由此构造迭代法,且当 时，,由于,根据定理2此迭代法是收敛的.,48,若取 迭代16次得，有六位有效数字.,若用（3.3）进行加速，计算结果如下：,这里计算2步（相当于（2.2）迭代4步）结果与 相同，,说明用迭代法（3.3）的收敛速度比迭代法（2.2）快得多.,49,7.4 牛顿法,牛顿法及其收敛性,设已知方程 有近似根（假定)，,将函数 在点 展开，有,于是方程 可近似地表示为,（4.1）,牛顿法是一种线性化方法，其基本思想是将非线性方程 逐步归结为某种线性方程来求解.,50,这是个线性方程，记其根为，,则 的计算公式为,（4.2）,这就是牛顿(Newton)法.,牛顿法的几何解释.,方程 的根 可解释为,曲线 与 轴的交点的横坐标,图7-4,（图7-4).,51,设 是根 的某个近似值，过曲线 上横坐标为 的点 引切线，并将该切线与 轴的交点的横坐标 作为 的新的近似值.,注意到切线方程为,这样求得的值 必满足（4.1），从而就是牛顿公式（4.2）的计算结果.,由于这种几何背景，牛顿法亦称切线法.,由定理4，可以直接得到牛顿法的收敛性，,52,由于,假定 是 的一个单根，即，则由上式知 于是依据定理4可以断定，牛顿法在根 的邻近是平方收敛的.,(4.2)的迭代函数为,又因,53,故由（2.9）可得,（4.3）,例7 用牛顿法解方程,（4.4）,解 这里牛顿公式为,取迭代初值，迭代结果列于表7-6中.,所给方程（4.4）实际上是方程 的等价形式.,54,牛顿法的计算步骤：,步骤1 准备 选定初始近似值，计算,步骤2 迭代 按公式,迭代一次，,得新的近似值，,若用不动点迭代到同一精度,可见牛顿法的收敛速度是很快的.,要迭代17次.,计算,55,此处 是允许误差，而,其中 是取绝对误差或相对误差的控制常数，,步骤4 修改 如果迭代次数达到预先指定的次数，,步骤3 控制 如果 满足 或，则终止迭代，以 作为所求的根；否则转步骤4.,一般可取,56,或者，则方法失败；,否则以 代替 转步骤2继续迭代.,57,牛顿法应用举例,对于给定的正数，应用牛顿法解二次方程,可导出求开方值 的计算程序,（4.5）,这种迭代公式对于任意初值 都是收敛的.,事实上，对（4.5）式施行配方手续，易知,58,以上两式相除得,据此反复递推有,（4.6）,记,59,解 取初值，对 按(4.5)式迭代3次便得到精度为 的结果（见表7-8).,对任意，总有，故由上式推知，当时，即迭代过程恒收敛.,例8 求.,整理（4.6）式，得,60,由于公式（4.5）对任意初值 均收敛，并且收敛的速度很快，因此可取确定的初值如 编成通用程序.,61,简化牛顿法与牛顿下山法,牛顿法的优点是收敛快，缺点一是每步迭代要计算 及，计算量较大且有时 计算较困难，,为克服这两个缺点，通常可用下述方法.,（1）简化牛顿法，也称平行弦法.其迭代公式为,（4.7）,迭代函数,62,若在根 附近成立，即取,则迭代法（4.7）局部收敛.,在（4.7）中取，则称为简化牛顿法，,这类方法计算量省，但只有线性收敛，,其几何意义是用平行弦与 轴交点作为 的近似.,如图7-5所示.,图7-5,即,63,（2）牛顿下山法.,牛顿法收敛性依赖初值 的选取.,如果 偏离所求根 较远，则牛顿法可能发散.,例如，用牛顿法求方程,（4.8）,在 附近的一个根.,设取迭代初值，用牛顿法公式,（4.9）,计算得,64,迭代3次得到的结果 有6位有效数字.,但如果改用 作为迭代初值，则依牛顿法公式（4.9）迭代一次得,这个结果反而比 更偏离了所求的根.,为了防止迭代发散，对迭代过程再附加一项要求，即具有单调性：,（4.10）,满足这项要求的算法称下山法.,65,将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度.,将牛顿法的计算结果,与前一步的近似值 适当加权平均作为新的改进值,（4.11）,其中 称为下山因子，,（4.12）,(4.12)称为牛顿下山法.,（4.11）即为,66,选择下山因子时从 开始，逐次将 减半进行试算，,若用此法解方程（4.8），当 时由（4.9）求得,直到能使下降条件（4.10）成立为止.,，它不满足条件（4.10）.,通过 逐次取半进行试算，当 时可求得,此时有，,显然.,而,由 计算 时,均能使条件（4.10）成立.计算结果如下：,67,即为 的近似.一般情况只要能使条件（4.10）成立，则可得到，从而使 收敛.,68,重根情形,设，整数，则 为方程 的 重根，此时有,只要 仍可用牛顿法（4.2）计算，此时迭代函数,的导数为,且，所以牛顿法求重根只是线性收敛.,69,则.,（4.13）,求 重根，则具有2阶收敛，但要知道 的重数.,构造求重根的迭代法，还可令，,若 是 的 重根，则,若取,用迭代法,70,从而可构造迭代法,（4.14）,它是二阶收敛的.,故 是 的单根.,对它用牛顿法，其迭代函数为,71,例9 方程 的根 是二重根，用上述三种方法求根.,解,（1）牛顿法,先求出三种方法的迭代公式：,（2）用（4.13）式,（3）用（4.14）式,取初值，计算结果如表7-9.,72,从结果看出，经过三步计算，方法（2）及（3）均达到10位有效数字，而由于牛顿法只有线性收敛，所以要达到同样精度需迭代30次.,73,7.5 弦截法与抛物线法,当函数 比较复杂时，计算 往往较困难，,74,弦截法,（5.1）,由于,因此有,（5.2）,75,（5.2）可以看做将牛顿公式,中的导数 用差商 取代的结果.,接着讨论几何意义.,曲线 上横坐标为 的点分别记为，,则弦线 的斜率等于差商值,（5.2）,76,按（5.2)式求得的 实际上是弦线 与 轴交点的横坐标.,表7-6,这种算法因此而称为弦截法.,其方程为,77,而弦截法（5.2），在求 时要用到前面两步的结果，,弦截法与切线法（牛顿法）都是线性化方法，但两者有本质的区别.,切线法在计算 时只用到前一步的值.,因此使用这种方法必须先给出两个开始值.,例10 用弦截法解方程,解 设取 作为开始值，用弦截法求得的结果见表7-10，,78,实际上，弦截法具有超线性的收敛性.,比较例7牛顿法的计算结果可以看出，弦截法的收敛速度也是相当快的.,定理6 假设 在根 的邻域 内具有二阶连续导数，且对任意 有，又初值 那么当邻域充分小时，弦截法（5.2）将按 阶收敛到根.,这里 是方程 的正根.,79,抛物线法,设已知方程 的三个近似根，,几何上，这种方法的基本思想是用抛物线与 轴的交点 作为所求根 的近似位置（图7-7).,图7-7,这样确定的迭代过程称为抛物线法，亦称密勒（Mller）法.,80,插值多项式,有两个零点：,（5.3）,式中,问题是该如何确定.,假定在 三个近似根中，更接近所求的根.,81,为了保证精度，选（5.3）中较接近 的一个值作为新的近似根.,为此，只要取根式前的符号与 的符号相同.,例11 用抛物线法求解方程,解 设用表7-10的前三个值,作为开始值，计算得,82,故,代入（5.3）式求得,以上计算表明，抛物线法比弦截法收敛得更快.,在一定条件下可以证明，对于抛物线法，迭代误差有下列渐近关系式,83,可见抛物线法也是超线性收敛的，其收敛的阶,从（5.3）看到，即使 均为实数，也可以是复数，所以抛物线法适用于求多项式的实根和复根.,收敛速度比弦截法更接近于牛顿法.,84,7.6 求根问题的敏感性与多项式的零点,85,求根问题的敏感性与病态代数方程,方程求根的敏感性与函数求值是相反的，若，则由 求 的病态性与由 求 的病态性相反，光滑函数 在根 附近函数绝对误差与自变量误差之比若，则求根为反问题，即输入 满足若找到一个 使,则解的误差 与 之比为，即 误差将达到，如果 非常小，这个值就非常大，直观的可用图7-8表示.,86,图7-8,87,对多项式方程,若系数有微小扰动其根变化很大，这种根对系数变化的敏感性成为病态的代数方程.,若多项式 的系数有微小变化，可表示为,其中 是一个多项式，次数不大于 的零点表示为，令 为 的零点，即，将（6.2）对 求导，可得,（6.1）,（6.2）,88,于是当 时有,当 充分小时，利用 在 处的泰勒展开得,它表明系数有微小变化 时引起根变化的情况.,当 很大时代数方程（6.1）就是病态的.,（6.3）,（6.4）,89,例12 多项式,解 取 的根,由（6.4）可得,实际上，方程 的根 分别为,这说明方程是严重病态的.,90,多项式的零点,很多问题要求多项式的全部零点，即方程（6.1）的全部根，它等价于求,的全部根.,前面讨论的任一种方法都可用于求出一个根，但通常使用牛顿法最好，可利用秦九韶算法计算 及 的值.,（6.5）,91,再求 的一个根，,如此反复直到求出全部 个根.,由牛顿法 计算到，则得到.,由于，即，将 的次数降低一阶.,一般地，这里 为二次多项式，在此过程中当 增加时不精确性也增加，为了解决此困难可通过原方程 的牛顿法改进 的结果.,92,由于 可能是复根，因此使用抛物线法对求复根更有利.,若 为复根，记，则 也是一个根，于是 是 的一个二次因子，于是 是 阶多项式，可降低二阶.,即使不是复根，也可通过抛物线法求出两个实根，它比牛顿法更优越.,93,例13 求 的全部零点.,解 先用抛物线法求方程的根，取 计算到 为止.结果见表7-11.,94,求得根为，从而可得,再由 可求得另外两根为,可对原方程，以此两根为初值，用牛顿法迭代一次可得到更精确的根,95,令一种求多项式零点的方法是将其转化为求矩阵的特征值问题.,由于方程（6.5）是矩阵,的特征多项式，利用计算矩阵特征值方法求矩阵 的全部特征值，则可得到方程（6.5)的全部根，MATLAB中的roots函数使用的就是这种方法.,此外还有专门针对求多项式全部零点的专门方法.,96,7.7 非线性方程组的数值解法,97,考虑方程组,（7.1）,其中 均为 的多元函数.,用向量记号记,（7.2）,(7.1）就可写成,非线性方程组,98,例14 求 平面上两条抛物线 及的交点，这就是方程组（7.1)中 的情形.,解 当 时无解.当 时有唯一解,当 时有两个解.及 当 时有4个解,99,求方程组（7.1）的根可直接将单个方程 的求根方法加以推广，实际上只要把单变量函数 看成向量函数，将方程(7.1）改写为方程组(7.2)，就可将前面讨论的求根方法用于求方程组（7.2）的根.,为此设向量函数 定义在区域 若，则称 在 连续，这意味着对任意实数，存在实数，使得对满足 的，有,如果 在 上每点都连续，则称 在域 上连续.,100,向量函数 的导数 称为 的雅可比矩阵，它表示为,（7.3）,101,多变量方程的不动点迭代法,为了求解方程组（7.2），可将它改写为便于迭代的形式,（7.4）,其中向量函数，且在定义域 上连续，如果，满足，称 为函数 的不动点，也就是方程组（7.2）的一个解.,根据（7.4）构造的迭代法,称为不动点迭代法，称为迭代函数.,（7.5）,102,如果由它产生的向量序列 满足，对（7.5）取极限，由 的连续性可得，故 是 的不动点，也就是方程组（7.2）的一个解.,103,类似于 时单个方程有下面的定理.,定理7 函数 定义在区域，假设：,（1）存在闭集 及实数，使,（2）对任意，有.,则 在 有唯一不动点，且对任意，由迭代法（7.5）生成的序列 收敛到，并有误差估计,定理的条件（1）称为 的压缩条件.,（7.6）,（7.7）,104,若 是压缩的，则它也是连续的.条件（2）表明 把区域 映入自身，此定理也称压缩映射原理.它是迭代法在域 的全局收敛性定理.,类似于单个方程还有以下局部收敛定理.,定理8 设 在定义域内有不动点 的分量函数有连续偏导数且,则存在 的一个邻域，对任意，迭代法（7.5）产生的序列 收敛于,（7.8）中的 是指函数 的雅可比矩阵的谱半径.,（7.8）,105,类似于一元方程迭代法也有向量序列 收敛阶的定义，设 收敛于，若存在常数 及，使,则称 为 阶收敛.,（7.9）,106,设，不难验证，故有 时.,例15 用不动点迭代法求解方程组,解 将方程组化为（7.4）的形式，其中,107,又对一切，,于是有，即 满足条件（7.6）.根据定理7，在域 中存在唯一不动点 内任意点出发的迭代法收敛于.,今取，用迭代法（7.5）可求得,108,由于,对一切 都有，故，从而有，满足定理7的条件.,此外还可看到故，即满足定理8条件.,109,非线性方程组的牛顿迭代法,将单个方程的牛顿法直接用于方程组（7.2）则可得到解非线性方程组的牛顿迭代法,这里 是（7.3）给出的雅可比矩阵的逆矩阵.,求出向量，再令.每步包括了计算向量函数 及矩阵,（7.10）,具体计算时记，先解方程组,110,定理9 设 的定义域为 满足 在 的开邻域 上 存在且连续，非奇异，则牛顿法生成的序列 在闭域 上超线性收敛于，若还存在常数，使,则 至少平方收敛.,牛顿法有以下收敛性定理.,111,例16 用牛顿法解例15的方程组,解,选，解线性方程组，即,112,解得，按牛顿迭代法（7.10）计算结果如表7-12.,