第六章非线性方程数值解(2014-06)

1、江西理工大学江西理工大学第六章第六章 非线性方程与非线性方程组解法非线性方程与非线性方程组解法:,.,次代数方程求例如程组的问题方程或非线性方常常会遇到求解非线性在许多实际问题中n.00111的根axaxaxannnn.0)2sin(的的根根或或求求超超越越方方程程xex.)(,0)(的零点或称为求函数的根这些都可以表示求方程xfxf.10)(, 0)(, 0)()()(.0)(, 0)(, 0)(.,)1()(重根的称为方程则但如果有的单根称为方程则但有如果对于也可以是复数方程的根可以是实数kxfaafafafafxfaafafamkk7.1 7.1 二分法二分法.),(.0)(),(, 0

2、)()(,)(,称为方程的有根区间区间实根至少有一个内则在若满足条件即设性质是闭区间上连续函数的二分法的主要数学原理baxfbabfafbacxf:0)(归结如下的一个实根的算法可以二分法求xf).(),(),(0)() 1 (bfafbaxf并计算出端点的函数值的根的存在区间找出).2()()2(bafxf在区间中点的值计算)2(.),(,2,)()2(,2, 0)2()3(*bafbabbaafbafbaxbaf若内考虑方程的根仍在区间代替则以异号与若为所求的根则停止计算若.),(,2,)(内考虑方程的根仍在区间代替则以异号与baababf.,2.,),3(),2()4(1二分区间的次数为

3、其中且其误差小于的根区间中点即可作为方程此时差范围内直到区间缩小到允许误重复步骤nabn.)(|,0停止计算即可事先给定的精度要求通常用在实际计算中 xx.,:且总收敛算法简单二分法的优点.:收敛速度较慢求重根只能用于求实根且不能二分法的缺点. 1 . 6,.2, 1 , 05)2(, 01) 1 (, 1)(:.05. 02,2, 1 011 . 62323结果如表结果如表用二分法计算用二分法计算内有一实根内有一实根方程在方程在显然显然设设解解差不超过差不超过要求误要求误内的一个实根内的一个实根在区间在区间求方程求方程例例ffxxxfabxxnnnanbnxnf(xn)的符号1121.5+2

4、11.51.25-31.251.51.375-41.3751.51.4375-51.43751.51.46881 . 6表表.4688. 1,05. 02/ )( ,*xabnn停止迭代最后一行中6.2 6.2 简单迭代法简单迭代法写成下面的等价形式若将给定的非线性方程0)(xf6.2.1 6.2.1 简单迭代法的一般形式简单迭代法的一般形式.,),(),(,:10作为方程的近似解利用其中的某一项得到一个迭代序列利用迭代公式代函数构造迭选取合适的初始值是简单迭代法的一般形式nnnnxxxxxx) 1 . 6()(xx.0)(,)(迭代法近似解的算法则可得到另一种求方程为连续函数要求xfx:要思

5、考这里有以下几个问题需?) 1 (0 x如何选取合适的初始值),(,)2(x同的迭代函数一般可以构造出几个不对同一个方程.得到不同的迭代序列01)(3xxxf在求方程例如:,5 . 1*0数就可以得到两个迭代函时附近的根在xx 3233131)(11)(1xxxxxxxx和和. 2 . 6?,迭迭代代结结果果见见表表否否都都令令人人满满意意呢呢得得到到的的两两个个迭迭代代序序列列是是那那么么:.这里的令人满意是指显然答案是否定的则有即是收敛的若迭代序列是收敛的得到的一个迭代序列由迭代函数,lim,.)(nnnnxxxxkk01.51.541.00661061.324811.8751.35725

6、1.021081.324724.71681.330961.061110541.32473100.22331.324971.194810541.3247)(11kkxx)(21kkxx)(21kkxx)(11kkxx2 . 6表表)()(limlim1nnnnxx.0)(),(的根是方程也就是说即xfx?)(?)()3(收敛的是列保证由它得到的迭代序就应满足什么条件才能函数迭代是收敛的得到的迭代序列如何判断由迭代函数nnxxxx6.2.2 6.2.2 简单迭代法的收敛条件简单迭代法的收敛条件:,)(),(0)(21都有和即对任意的条件满足如果改写成把方程xxlipschitzxxxxf证明证明有

7、因为对任意正整数p)2 . 6(定理定理6.16.1| )()(|2121xxLxx:, 1),(,21则迭代若数简称李氏常常数称为无关的正常数和是与其中LLipschitzxxL:,)(1并有误差估计且收敛到准确解收敛nnxx|1|01xxLLxnn|1211nnpnpnpnpnnpnxxxxxxxx| )()(|,01111xxLxxLxxxxkkkkkkkk有对任意整数由迭代公式和李氏条件:因此|1|11| ) 1(|0101012101012011xxLLxxLLLxxLLLxxLxxLxxLxxnnpppnnpnpnnpn:,lim, 0lim,1则设是收敛的收敛准则可知序列由注意到

8、时当nnnnnxxCauchyLL.0)()()(limlim1的根的根的极限就是方程的极限就是方程所以所以xfxxxnnnnn. |1|,lim|1|0101xxLLxxxxLLxxnnpnpnnpn得及由6.2.3 6.2.3 简单迭代法的误差分析和收敛阶简单迭代法的误差分析和收敛阶|1|01xxLLxnn6.2.3.1 6.2.3.1 误差分析与算法误差分析与算法 迭代过程是个极限过程。在用迭代式进行实际计算时，迭代过程是个极限过程。在用迭代式进行实际计算时，必须按精度要求控制迭代次数。误差估计式必须按精度要求控制迭代次数。误差估计式:由对任意正整数由不便于实际应用而但由于它含有李氏常数

9、次数原则上可用于确定迭代pxxLxxLkkkk|,|.,11|11| ) 1(|1121nnnnppnpnxxLxxLLxx|11|,lim1nnnpnpxxLxx知又由.,|,1具有足够精度即可保证近似值足够小的偏差只要相邻两次计算结果由此可见nnnxxx:,计算步骤可以总结简单迭代法的由上面的分析).(),(0)(,) 1 (0 xxxxfx得到迭代函数形式写成的等价将给定的非线性方程选取初始值).()()2(011xxxxnn计算按迭代公式11,),(|:)3(nnnxxx则则停停止止计计算算要要求求的的精精度度如如果果判判别别等比级数).3()2(,;1和步骤重复步骤代替否则用即为所求

10、近似解nnxx.1| )(|,)(,来代替比较方便通常用李氏条件比较困难是否适合验证迭代函数在实际计算时应该指出Lxx.,1:不不能能保保证证迭迭代代过过程程收收敛敛就就若若没没有有这这点点保保证证这这一一点点是是非非常常重重要要的的正正常常数数注注意意L., 1| )(|, 1| )(|,2, 1 ,3)(, 1)(12131发散故相应的迭代满足不存在正常数上在区间例如前面例题中LxLxxxxx., 1)21(31| )(| ,2, 1 ,) 1(31)(, 1)(32322232故故相相应应的的迭迭代代过过程程收收敛敛上上在在区区间间xxxxx6.2.3.2 局部收敛性与收敛阶局部收敛性与

11、收敛阶 上面给出了迭代序列在区间上的收敛性，通常称为全局收上面给出了迭代序列在区间上的收敛性，通常称为全局收敛性。因为有时不易检验定理敛性。因为有时不易检验定理1 1的条件，实际应用时通常只在的条件，实际应用时通常只在方程解的邻近考察其收敛性，即局部收敛性。方程解的邻近考察其收敛性，即局部收敛性。定义定义6.1.,|:|,*0*则则称称迭迭代代法法局局部部收收敛敛且且收收敛敛到到由由迭迭代代法法产产生生的的序序列列对对任任意意的的某某个个邻邻域域如如果果存存在在设设方方程程的的解解为为xDxDxxxDxxn定理定理6.2证明证明., 1| )(|,)(,*则迭代法局部收敛且的某个邻域连续在设方

12、程的解为xxxx|)( | | )(| )()(|)(|,1| )(|.,|:|,*xxxxLDxxxxxxDxLxDxxxDx总有总有又对于任意又对于任意有下式成立有下式成立意意使对于任使对于任的某个邻域的某个邻域存在存在由连续函数的性质由连续函数的性质由微分中值定理.)()(01证证毕毕收收敛敛均均对对于于任任意意初初值值代代过过程程由由上上一一定定理理可可以以断断定定迭迭所所以以DxxxDxnn.敛敛速速度度问问题题下下面面讨讨论论迭迭代代序序列列的的收收3032 . 6*2xx的的根根用用不不同同方方法法求求方方程程例例.),(:由由此此构构造造不不同同的的迭迭代代法法价价形形式式方方

13、程程可可改改写写成成不不同同的的等等解解xx1132)3()(, 12)(, 3)(3, 3) 1 (*2212xxxxxxxxxxxxkkk1)3()(,3)(,1)(3,3) 2(*21xxxxxxxxxkk. 1134. 0231)3()(,211)() 3(41)(),3(41),3(41) 3(*2212xxxxxxxxxxxxkkk)3(21),3(21)4(1kkkxxxxxx0)3()(),31 (21)(),3(21)(*2xxxxxx.)4)(3( ,)2)(1 ( ,收收敛敛条条件件满满足足迭迭代代法法局局部部条条件件不不满满足足迭迭代代法法局局部部收收敛敛可可见见3 .

14、 6,4, 20计计算算结结果果见见表表种种迭迭代代法法对对上上述述取取xkxk迭代法(1) 迭代法(2) 迭代法(3) 迭代法(4)0 x022221x131.51.751.752X2921.73481.73213x3871.51.73241.73213 . 6表表 从计算结果看出，迭代法从计算结果看出，迭代法(1)(1)和迭代法和迭代法(2)(2)不收敛，迭代法不收敛，迭代法(3)(3)和迭代法和迭代法(4)(4)收敛，且迭代法收敛，且迭代法(4)(4)比迭代法比迭代法(3)(3)收敛快。为了衡量迭代法收敛速度的快收敛快。为了衡量迭代法收敛速度的快慢，给出以下定义：慢，给出以下定义：定义定

15、义6.2.2,1,1,)0(lim,)()(1*1时时称称平平方方收收敛敛时时称称超超线线收收敛敛时时称称线线性性收收敛敛阶阶收收敛敛的的则则称称该该迭迭代代过过程程是是常常数数满满足足差差如如果果迭迭代代误误的的根根收收敛敛于于方方程程设设迭迭代代过过程程ppppCCeexxexxxxxpkkkkknn)3 . 6(定理定理6.3.0)(, 0)()()(,)(),(*)(*)1(*)(1阶阶收收敛敛的的邻邻近近是是则则迭迭代代过过程程在在点点并并且且邻邻近近连连续续在在所所求求根根如如果果对对于于迭迭代代过过程程pxxxxxxxxxpppnn )4 . 6(证明证明!)(lim,)(!)(

16、)(,)().,(,)(!)()()(,)(.)(, 0)(*)(1*)(*1*11*)(*1*pxeexxpxxxxxxxxxxpxxxxxxxppkkkpkpkkkkkpkpkknn对迭代误差有因此得注意到则有利用定理条件处做泰勒展开在根再将具有局部收敛性可以断定迭代过程由于.)(1证毕阶收敛的确实为这表明迭代过程pxxnn., 0)(.)(,*性收敛则迭代过程只可能是线如果当取的选赖于迭代函数迭代过程得收敛速度依这一定理表明 xx6.3 Newton6.3 Newton迭代法迭代法.)4(, 2, 3, 032)(,6)(, 0)3()(),4(;)3(, 3, 0134. 0231)3

17、()(),3(,*3*平方收敛即迭代法由定理而对于迭代法线性收敛迭代法定理由对于迭代法上例中例如 pxxxxx把把f(x)f(x)在在x0 x0点附近展开成泰勒级数点附近展开成泰勒级数: :6.3.1 Newton6.3.1 Newton迭代法的迭代公式迭代法的迭代公式 !)()(!2)()()()()()(0)(0020000nxfxxxfxxxfxxxfxfnn)5 . 6(0)()()(,0)(,000 xfxxxfxf则有的近似方程作为非线性方程取其线性部分)()(,0)(00010 xfxfxxxf则其解为设)()(, 0)(.0)(,)(111211xfxfxxxfxfxxf则得若

18、的近似方程性方程也取其线性部分作非线点附近展开成泰勒级数在再把, 2, 1, 0,)()(1nxfxfxxNewtonnnnn迭代法的一个迭代序列这样得到.)5 . 6(迭代法的迭代公式迭代法的迭代公式也称为也称为式式Newtonn1234xn1.41171.36931.36881.36884 . 6表表0201023 . 623xxxNewton迭迭代代法法求求下下面面方方程程的的根根用用例例. 4 . 6, 1104320102,1043)(, 020102)(:02231223则计算结果见表则计算结果见表选取选取式为式为所以迭代公所以迭代公因因解解xxxxxxxxxxxfxxxxfnnn

19、nnnn.,得到了较满意的结果进行了四次迭代就快的牛顿法的收敛速度是很从计算结果看出6.3.2 NewtonNewton迭代法收敛性迭代法收敛性)()()(xfxfxx得两式相减并除以),()()(0)(21)()()(012*kkkkkkkkkkxfxxxfxfxxfxxxfxfxf 对于牛顿法对于牛顿法, ,迭代函数为迭代函数为2)()()()(xfxfxfx 由于又又因因为为的的的的邻邻近近至至少少是是平平方方收收敛敛牛牛顿顿法法在在根根于于是是由由定定理理则则由由上上式式知知即即的的一一个个单单根根是是假假定定., 3 . 6, 0)(, 0)(, 0)(,)(*xxxfxfxfx)(

20、2)(2*1kkkkxfxxfxx )6 . 6()(2)()(2)(lim)(lim,*2*1*xfxfxffxxxxxxkkkkkkk 有时当.的可见牛顿法是平方收敛.)/()(lim, 04 . 6231333kkkxaxaaax并并求求公公式式的的迭迭代代导导出出求求立立方方根根应应用用牛牛顿顿法法于于方方程程例例2231233)311 (3)()(),5 . 6(6)(,3)(,)(:kkkkkkkkkxaxxaxxxfxfxxxxfxxfaxxf 得得由由牛牛顿顿迭迭代代公公式式解解.,0)(, 0)()(,)(, 0)(, 0)()(,)(:.,1 . 6,)(,()(,0)()

21、(,1)(2)()(lim)6 . 6(*00013332331xbaxfxfxfbaxxfxfbfafbaxfxxfxxfyxxxfxfxaafafxaaxkkkkkkkkk的的惟惟一一根根在在于于方方程程收收敛敛则则牛牛顿顿迭迭代代法法所所得得序序列列且且初初值值不不变变号号上上二二阶阶导导数数存存在在在在区区间间设设牛牛顿顿迭迭代代法法收收敛敛定定理理法法因因此此牛牛顿顿法法又又称称为为切切线线所所示示如如图图点点轴轴的的交交处处切切线线与与上上就就是是曲曲线线从从几几何何上上看看的的解解实实际际上上是是线线性性化化方方程程牛牛顿顿迭迭代代公公式式中中的的由由式式 ykxxx*x1kx1

22、 . 6图图6.3.3 Newton6.3.3 Newton迭代法变形迭代法变形)()()()(:.1001kkkkxfxfxfxfxx代替变动的即用不变的平行线法)7 . 6()8 . 6()9 . 6( 牛顿迭代法虽然收敛速度很快，但计算量比较大，因为每次牛顿迭代法虽然收敛速度很快，但计算量比较大，因为每次迭代除计算函数值外还要计算导数值。为使计算简化，提出简化迭代除计算函数值外还要计算导数值。为使计算简化，提出简化牛顿法牛顿法. .0011)()()()(:)()()(,()(:. 2xxxfxfxxxfxfxfxfxxfykkkkkkkkk或的斜率代替弦曲线上两点连线改用处的切线斜率上

23、点若将曲线割线法)()()()()()(:001111xfxfxxxfxxxfxfxxxfxxkkkkkkkkkkkk弦割法则得双点弦割法或单点.)3, 2(0525 . 63内的根内的根在在方程方程用双点和单点弦割法求用双点和单点弦割法求例例 xx6543210094551. 2,094510. 2,096559. 2,058823. 2, 2, 3:xxxxxxx按双点线割法计算得解151432094551. 2,096559. 2,058823. 2:xxxx按单点弦割法计算得.,法快双点弦割法比单点弦割从以上结果看出.,)(,618. 0,很快收敛速度可能变化不大时但当收敛单点弦割法一

24、般是线性且收敛阶数敛性双点弦割法具有局部收可以证明xfp.,),(),(,经常使用这际计算时所以效率较高不需要计算导数值函数值次但迭代一次只需计算一于牛顿法弦割法收敛阶数虽然低kkxfxf)10. 6()()(:. 31kkkkxfxfxx牛牛顿顿下下山山法法)()(,1kkxfxf应满足探索的过程其选取过程是一个逐步称为下山因子.1, 1求得开始用反复折半的方法可从具体计算时通常.,围为目的的是以扩大初值的选取范法的一种修正况下对牛顿未能给出较好初值的情牛顿下山法适合在事先6.4 解非线性方程组的解非线性方程组的Newton迭代法迭代法0),(0),(21211nnnxxxfxxxf考虑方程

25、组0)(,),(,),(.,2121211xFfffFRxxxxxxxffTnnTnnn上面的方程组就可写成若用向量记号的多元函数均为其中. 0)(0)()()(,0)(.,), 2, 1(), 2, 1(, 2xFxfxFxfxfnixnifnii根方法推广到方程组求则可将单变量方程看成向量函数的单变量函数实际上只要把前面介绍求根的直接推广前面介绍的方程是非线性方程组求根问题方程组为非线性方程组非线性函数时的中至少有一个是自变量且当0)()(,0)(,), 2, 1)()(,),(0)()()()()()()(2)(1)(kkkkkTknkkkxxxFxFxFxnixfxFxxxxxF则有的

26、近似方程线性方程组并取其线性部分作为非开用多元函数泰勒展在的分量将向量函数的一个近似根若已给出方程)10. 6(其中nnnnnnxxfxxfxxfxxfxxfxxfxxfxxfxxfxF)()()()()()()()()()(212211212111则则得得记记解解为为并并求求解解线线性性方方程程组组偏偏微微商商矩矩阵阵的的雅雅可可比比称称为为,),10. 6(,)()()1( kxJacobixF, 2, 1, 0)()()(1)()()1(kxFxFxxkkkk)11. 6(迭代法的这就是解非线性方程组NewtonxF0)(.) 1, 1 (0) 13() 1(),(05),(6 . 61

27、212122221211附附近近的的解解用用牛牛顿顿法法求求在在设设例例xxxxxfxxxxf1322)(:122122122111xxxxxfxfxfxfxF先计算出偏微商矩阵解12212122211232162221)(xxxxxxxxxF. 5 . 6,01. 0,.|,25. 225. 1,23)(,111141222281)(, 2, 1, 0)()(,) 1, 1 ()()1()1()0(1)0()(1)()()1()0(计计算算结结果果见见表表取取比比如如为为容容许许误误差差其其中中为为止止直直到到逐逐次次迭迭代代计计算算利利用用迭迭代代公公式式开开始始由由kkkkkkTxxxx

28、FxFkxFxFxxxX(0)X(1)X(2)X(3)X(4)11.2511.00021.000012.252.02782.00012.00005 . 6表表 本章介绍了几种求解非线性方程和方程组的迭代解法：二本章介绍了几种求解非线性方程和方程组的迭代解法：二分法，简单迭代法，牛顿迭代法和弦割法。并讨论了迭代收敛分法，简单迭代法，牛顿迭代法和弦割法。并讨论了迭代收敛的条件及收敛的阶。的条件及收敛的阶。 二分法简单易行，缺点是收敛速度慢，主要用于确定根二分法简单易行，缺点是收敛速度慢，主要用于确定根的大致范围，即根所在的区间。的大致范围，即根所在的区间。 选择使用某种迭代法，应保证迭代收敛，且收

29、敛速度快。选择使用某种迭代法，应保证迭代收敛，且收敛速度快。实际计算时，最好先判断收敛性，也可先算几点，观察是否收实际计算时，最好先判断收敛性，也可先算几点，观察是否收敛及收敛速度。对于非线性方程和方程组，如果导数计算量不敛及收敛速度。对于非线性方程和方程组，如果导数计算量不大，可用牛顿法，如果导数计算量大，则用弦割法或简单迭代大，可用牛顿法，如果导数计算量大，则用弦割法或简单迭代法。法。 求非线性方程数值解的求非线性方程数值解的matlabmatlab函数函数一、多项式求根函数一、多项式求根函数roots(p)roots(p)(1).(1).该函数不能求非线性方程组的解该函数不能求非线性方程组的解, ,使用时将使用时将多项式方程变为多项式方程变为p pn n(x)=0(x)=0的标准形式的标准形式. .(2).(2).参数参数p p是由多项式的系数向量组成是由多项式的系数向量组成, ,缺少的缺少的幂次系数用零填补幂次系数用零填补. .(3).(3).输出多项式的所有实根与复根输出多项式的所有实根与复根. .二、求函数零点函数二、求函