《数值分析课件：ch04非线性方程组的求解》由会员分享，可在线阅读，更多相关《数值分析课件：ch04非线性方程组的求解（66页珍藏版）》请在金锄头文库上搜索。
1、1第七章 非线性方程求根Root-finding problem of nonlinear equations引言引言q 很多工程和科学计算问题常常归结为求解方程：很多工程和科学计算问题常常归结为求解方程：q 例如：非线性有限元问题、非线性断裂问题、及其它例如：非线性有限元问题、非线性断裂问题、及其它非线性力学问题、电路问题、电力系统计算、医学、非线性力学问题、电路问题、电力系统计算、医学、生命学、天气预报、非线性规划、经济问题等生命学、天气预报、非线性规划、经济问题等。引言引言引言引言方程的根与函数的零点方程的根与函数的零点q 满足函数方程满足函数方程 f(x)=0 f(x)=0 的的x x
2、称为方程称为方程(1)(1)的的根根，或称为函数，或称为函数f(x)f(x)的的零点零点。如果函数。如果函数 ( (x)x)可分解为可分解为 ( (x)=(xx)=(x s)s)m mg(x)g(x)且且g(g(s s ) ) 0,0,则称则称s s是是 ( (x)x)的的m m重零点重零点或或 ( (x)=0x)=0的的m m重根。当重根。当m=1m=1时，称时，称s s是是 ( (x)x)的的单根或单零点单根或单零点。q 定理定理 假设函数假设函数y=f(x)y=f(x)在在x=sx=s的某一邻域内充分可微，则的某一邻域内充分可微，则s s是方程是方程f(x )=0f(x )=0的的m m
3、重根的充分必要条件是重根的充分必要条件是求解非线性方程的根的问题可分为下面几个方面求解非线性方程的根的问题可分为下面几个方面：q l 根的存在性。根的存在性。 判断方程有没有根？有几个根？判断方程有没有根？有几个根？l 根的隔离根的隔离 确定根的分布以及有根区间，实际上也是确定根的分布以及有根区间，实际上也是 获得各个根的初始近似值。获得各个根的初始近似值。l 根的精确化根的精确化 将根的初始近似值逐步精确化，直到满足将根的初始近似值逐步精确化，直到满足 精度为止精度为止 根的存在性定理根的存在性定理q 非线性方程根的存在性非常复杂。非线性方程根的存在性非常复杂。l 对于代数方程即多项式方程，
4、其根的对于代数方程即多项式方程，其根的个数与代数方程个数与代数方程的次数相同的次数相同。而且理论上已证明，对于次数。而且理论上已证明，对于次数n=4n=4的多项的多项式方程式方程, ,它的根可以用公式表示它的根可以用公式表示, ,而而次数大于次数大于5 5的多项式方的多项式方程程, ,它的根一般不能用解析表达式表达。它的根一般不能用解析表达式表达。示示. .l 对于超越方程或其他非线性方程，可能没有零点，也对于超越方程或其他非线性方程，可能没有零点，也可能有一个或若干个零点，甚至无穷多个零点。可能有一个或若干个零点，甚至无穷多个零点。根的隔离根的隔离求根的隔离区间的两种方法求根的隔离区间的两种
5、方法q 画图法画图法023yx画图法画图法逐步搜索逐步搜索法法n用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长h hn 要选择适当要选择适当h h ，使之既能把根隔离开来，工作量又不太大。使之既能把根隔离开来，工作量又不太大。q 逐步搜索法逐步搜索法二分法二分法 Bisectionq 在方程求根的方法中，最直观、最简单的方法就在方程求根的方法中，最直观、最简单的方法就 是二分法。是二分法。q 给定方程给定方程f(x)=0,f(x)=0,设设f(x)f(x)在区间在区间 a,ba,b连续连续, ,且且f(a)f(b)0,f(a)f(b)= 1.0e 6 ) &(
6、 n=1000 ) x = x1 ; x1=g(x); n = n+1 ;endx1nmatlab program 收敛阶(描述收敛速度) 收敛速度（收敛速度的阶）收敛速度（收敛速度的阶）收敛速度（收敛速度的阶）收敛速度（收敛速度的阶）q 设迭代过程设迭代过程 收敛于方程收敛于方程 的根的根 ，如果迭代误差如果迭代误差 当当 时成立下列时成立下列渐近关系式渐近关系式则称则称则称则称 xnxnxnxn 是是是是p p p p阶收敛阶收敛阶收敛阶收敛 若若 p p = 1 = 1 , , 称称 x xk k 为为线性收敛线性收敛, , 这时这时 0 0 1, 1, 称称 x xk k 为为超线性收
7、敛超线性收敛; ; p p=2, =2, 称其为称其为平方收敛平方收敛. .收敛阶定理 q 数数p p的大小反映了迭代法的收敛速度的快慢，的大小反映了迭代法的收敛速度的快慢，P P越大，收越大，收 敛越快敛越快，所以说收敛阶是对迭代法收敛速度的一种度量。，所以说收敛阶是对迭代法收敛速度的一种度量。 q （收敛阶定理）（收敛阶定理） 对于迭代过程对于迭代过程 ，如果，如果 在所求根在所求根 的邻近连续，并且的邻近连续，并且: : 则该迭代过程在点则该迭代过程在点 邻近是邻近是P P阶收敛的阶收敛的。上述定理说明，迭代过程的收敛速度依赖于迭代函数上述定理说明，迭代过程的收敛速度依赖于迭代函数. .
8、 的选取的选取. . Newton迭代法q NewtonNewton法的基本思想法的基本思想 将非线性方程线性化，以线性方程的解逐步逼近将非线性方程线性化，以线性方程的解逐步逼近将非线性方程线性化，以线性方程的解逐步逼近将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解非线性方程的解非线性方程的解非线性方程的解 q 具体而言： 设设x xk k是非线性方程是非线性方程 f f( (x x)=0)=0的一个近似根，把的一个近似根，把 f f( (x x) )在在x xk k处作处作一阶泰勒展开，即用前两项近似代替一阶泰勒展开，即用前两项近似代替则近似方程转化为则近似方程转化为 设 ，上式解
9、为Newton迭代法 于是方程于是方程 f f( (x x)=0)=0的新的近似根的新的近似根x xk k+1+1，可得，可得牛顿迭牛顿迭代公式代公式q q 牛顿迭代公式为特殊的不动点迭代。牛顿迭代公式为特殊的不动点迭代。 其迭代函数为其迭代函数为 Newton迭代法几何解释 设设 是根是根 的某个近似值，过曲线的某个近似值，过曲线 上横上横坐标为坐标为 的点的点 引切线，并将该切线与引切线，并将该切线与 轴的交点的横轴的交点的横坐标坐标 作为作为 的新的近似值的新的近似值. . 注意到切线方程为注意到切线方程为 牛顿法的收敛性及收敛阶 q 牛顿法应用举例可导出求开方值可导出求开方值 的计算程
10、序的计算程序 ：开方公式对于任意给定的正初值均为平方收敛开方公式对于任意给定的正初值均为平方收敛。q 求无理数的近似值求无理数的近似值 可导出求开方值可导出求开方值 的计算程序的计算程序 q 求求 . 取初值取初值 ，对，对 按公式迭代按公式迭代3 3次次便得到精度为便得到精度为 的结果的结果计算重根的牛顿迭代法计算重根的牛顿迭代法q NewtonNewtonNewtonNewton法在重根情形下的收敛阶为线性阶法在重根情形下的收敛阶为线性阶法在重根情形下的收敛阶为线性阶法在重根情形下的收敛阶为线性阶 若若 是方程是方程 的的 重根，重根，即即此时有此时有牛顿迭代法的优缺点q 优点优点 在单根
11、附近在单根附近, , 牛顿迭代法具有平方收敛的速度，所牛顿迭代法具有平方收敛的速度，所 以在迭代过程中只要迭代几次就会得到很精确的解。以在迭代过程中只要迭代几次就会得到很精确的解。 而且能而且能计算复根。计算复根。q 缺点缺点 l 重根情形下为局部线性收敛重根情形下为局部线性收敛; ; l牛顿迭代法计算量比较大牛顿迭代法计算量比较大: : 因每次迭代除计算函数值外因每次迭代除计算函数值外 还要计算导数值还要计算导数值; ;l选定的初值要接近方程的解，否则有可能得不到收敛的结果选定的初值要接近方程的解，否则有可能得不到收敛的结果; ;牛顿迭代法的改进牛顿迭代法的改进l 重根情形下为局部线性收敛重
12、根情形下为局部线性收敛- 改进公式或加速改进公式或加速l 每步都要计算导数值每步都要计算导数值-简化简化NewtonNewton迭代法或弦截法迭代法或弦截法l 初值近似问题初值近似问题-二分法求初值或二分法求初值或”下山算法下山算法”q 重根情形的加速重根情形的加速提速方案提速方案1:1: 迭代函数使用重数迭代函数使用重数. .将迭代函数改为将迭代函数改为则迭代法为则迭代法为可以证明它是求可以证明它是求m m重根重根x x* *的具平方收敛的迭代格式的具平方收敛的迭代格式。 牛顿迭代法的改进牛顿迭代法的改进l 问题是问题是 一般情况下并未知重数一般情况下并未知重数m. 如何确定如何确定m? 令
13、令则则因此可用下式估计m 提速方案提速方案2 2: 将求将求f f的的重根重根转化为求另一函数的转化为求另一函数的单根单根。 构造函数构造函数牛顿迭代法的改进牛顿迭代法的改进对它用牛顿法，其迭代函数为对它用牛顿法，其迭代函数为q 避免导数值的计算避免导数值的计算牛顿迭代法的改进牛顿迭代法的改进l 简化简化NewtonNewton迭代法迭代法l 弦截法弦截法牛顿迭代法的改进牛顿迭代法的改进 导数导数 用差商用差商 取代，取代， 则：则：导数 用差商 取代， 则1 1 弦截法与牛顿法都是线性化方法，弦截法与牛顿法都是线性化方法，但两者有本质的区别但两者有本质的区别. . 2 2 弦截法具有超线性的
14、收敛性弦截法具有超线性的收敛性. q 牛顿下山法牛顿下山法牛顿迭代法的改进牛顿迭代法的改进 如果如果 偏离所求根偏离所求根 较远，则牛顿法可能发散较远，则牛顿法可能发散. 为了防止迭代发散，对迭代过程再附加一项要求，即为了防止迭代发散，对迭代过程再附加一项要求，即 具有单调性：具有单调性： 满足这项要求的算法称下山法满足这项要求的算法称下山法. . 将牛顿法与下山法结合起来使用，即在下山法保证函将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度数值稳定下降的前提下，用牛顿法加快收敛速度. . l l 牛顿迭代法的改进牛顿迭代法的改进牛顿下山法采用以下迭代公
15、式：其中其中 称为下山因子称为下山因子， 选择下山因子时从选择下山因子时从 开始，逐次将开始，逐次将 减半进行试算，减半进行试算，直到能使下降条件成立为止直到能使下降条件成立为止. . l 牛顿下山法只有线性收敛牛顿下山法只有线性收敛迭代过程的加速迭代过程的加速q 对于收敛的迭代过程，从理论上说，只要迭代足够多次，对于收敛的迭代过程，从理论上说，只要迭代足够多次，总可得到满意的精度，但有时迭代过程总可得到满意的精度，但有时迭代过程过于缓慢，计算量极过于缓慢，计算量极大大，实际上得不到满意的结果。因此，实际上得不到满意的结果。因此，迭代过程的加速迭代过程的加速便成便成了一个重要的研究课题了一个重
16、要的研究课题. .l 加速方案一加速方案一 当迭代函数当迭代函数 ( (x x) ) 在不动点在不动点 x* x* 处导数不为零处导数不为零, , 迭代迭代 x xk k+1+1 = = ( (x xk k) )仅是仅是线性收敛线性收敛. . 设由迭代公式计算出设由迭代公式计算出 迭代值迭代值 ，若，若x x在在x*附附近变化近变化, , ( (x x) )连续连续, ,则则 ( (x x) )变化不大变化不大, ,近似地记为常数近似地记为常数L L，则用微分中值定理，可以得到，则用微分中值定理，可以得到 迭代过程的加速迭代过程的加速解出解出x*： 具体算法如下：具体算法如下：把它作为把它作为
17、xk的一种补的一种补偿偿l 加速方案二加速方案二 ：Atiken加速法加速法迭代过程的加速迭代过程的加速 设由基本迭代公式计算出设由基本迭代公式计算出3 3个迭代值个迭代值x xk k , ,x xk+k+1 1, ,x xk+k+2 2 , , 则则把它作为把它作为x xk k的一种补的一种补偿偿迭代过程的加速迭代过程的加速q 定理定理 设序列设序列 线性收敛于线性收敛于x*, x*, 则则 的的AitkenAitken序列序列 存在存在, ,且且 即即 比比 更快收敛于更快收敛于x*.x*.q AtikenAtiken加速法与基本迭代公式结合，即为加速法与基本迭代公式结合，即为Steffe
18、nsen Steffensen 迭代法迭代法迭代过程的加速迭代过程的加速q SteffensenSteffensen迭代法迭代法具体算法如下具体算法如下：或写成不动点迭代形式或写成不动点迭代形式几何解释几何解释xyy = xy = g(x)sx0P(x0, x1)x1x2P(x1, x2)比 x2 更接近 s !例例 求方程x3 -x -1=0在区间(1, 2)内的根 s.发散发散kykzkxk01.512.3750012.39651.4162921.840925.238881.3556531.491402.317281.3289541.347101.444351.3248051.325181
19、.327141.32472计算结果计算结果q SteffensenSteffensen迭代法将原不收敛的迭代法变成收敛迭代法将原不收敛的迭代法变成收敛解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法 q 考虑方程组考虑方程组 其中其中 均为均为 的多元函数的多元函数. . 令令解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法 方程组可以表示为向量形式方程组可以表示为向量形式 F(x) = 0. 只要把前面介绍的单变量函数只要把前面介绍的单变量函数 看成向量函数看成向量函数 则可将单变量方程求根方法推广到方程组则可将单变量方程求根方法推广到方程组. . l l 将函数将函数 的分量的分量
20、 在在 用多元函数用多元函数泰勒展开，并取其线性部分，则可表示为泰勒展开，并取其线性部分，则可表示为 解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法 令上式右端为零，得到线性方程组令上式右端为零，得到线性方程组 其中 l 求解线性方程组，并记解为求解线性方程组，并记解为 ，则得，则得 这就是解非线性方程组的这就是解非线性方程组的牛顿迭代法牛顿迭代法. . 解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法 q 定理 （牛顿法的局部收敛性）（牛顿法的局部收敛性）设设D D R Rn n, ,x x* *是是D D的内点的内点, ,开区域开区域S S D D, ,函数函数F F: :D D
21、 R Rn n在在S S内连续可内连续可微微 且且 F F ( (x x*)*)非奇异非奇异，则则存在闭半球存在闭半球 D D0 0= = x x | | | | x x x x*|*| , , 0 0 S S, ,使对使对 x x0 0 D D0 0，由牛顿迭代公式产生的序列由牛顿迭代公式产生的序列 x x( (k k) ) D D0 0，且此序列，且此序列超线性超线性收敛于收敛于x x* *；进一步，进一步，若若F F( (x x) )在在S S内内2 2次连续可微，则次连续可微，则序列序列 x x( (k k) ) 至少是至少是平方收敛平方收敛的的. .求方程组求方程组F F( (x x
22、)=0)=0的解的解x x*,*,可使用下迭代公式可使用下迭代公式: : F F ( (x x( (k k) )()(x x x x( (k k) )= )= F F( (x x( (k k) ) ) (1) 在在 x x* * 附近选取附近选取 x x(0)(0) D D0 0, , 给定精度给定精度 00. . (2) (2) 反复做以下步骤反复做以下步骤, , 直到达到精度直到达到精度, ,计算计算 F F( (x x( (k k) ) ) 和和 F F ( (x x( (k k) ), ), x x( (k k) ) = ( = (x x( (k k) ) x x( (k -k -1)
23、1) ) , ,求解关于求解关于 x x( (k k) )的方程组的方程组, , 计算计算 x x( (k+k+1) 1) = = x x( (k k) ) + + x x( (k k) ) . .解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法 q 算法 例例解解 牛顿法迭代公式为选选 x =(1,1)T, 当当 k = 4 时时Matlab非线性方程求根的命令非线性方程求根的命令1. 代数方程组的求根代数方程组的求根roots r=roots(P)2. 2. 求零点求零点fzero x=fzero(F,x0,option)3 3 求方程组数值解的命令求方程组数值解的命令fsolve x=fsolve(fun,x0,options)
