数值分析第7章非线性方程与方程组的数值解法课件.ppt

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