《应用数值分析》课件数值分析6非线性方程(组)求根.ppt

1、第第6章章 非线性方程非线性方程(组组)求根求根6.2 根的搜索6.3 迭代法及其收敛性6.4 方程求根的牛顿法6.5 代数方程求根6.6 非线性方程组的迭代法6.1 问题描述 中至少有一个是中至少有一个是x的非线的非线性函数，若其全为线性的则为线性方程组。性函数，若其全为线性的则为线性方程组。12(,)(1,2,)infxxxin6.1 问题描述问题描述TnxfxfxfxF)(),(),()(21 含有含有n个未知数的个未知数的n个方程的非线性方程组为个方程的非线性方程组为 (1)其中其中 为为n维列向量，维列向量，0)(xFTnxxxx),(21 非线性方程组包非线性方程组包 括：括：高次

2、方程组高次方程组,即即代数方程组代数方程组超越方程组超越方程组产生背景产生背景:许多科学理论与工程技术都可化为非线性方程组许多科学理论与工程技术都可化为非线性方程组求解的特点：求解的特点：无求解公式，无直接解法无求解公式，无直接解法，难求得精确解。难求得精确解。求解的方法：求解的方法：间接法即迭代法。间接法即迭代法。迭代法求解的要求：迭代法求解的要求：l 收敛收敛l 计算效率计算效率(快慢快慢)l 数值稳定性数值稳定性(考虑计算机的舍入误差考虑计算机的舍入误差)初始值好初始值好迭代公式合适迭代公式合适(好的好的)定义定义00()0,()f xxf x若则称为函数的零点.(x),()()0fC

3、a bf af b设，且，定理定理1 1（零点定理）()(,)f xa b则在内至少存在一个零点.abxyxyab00一个零点多个零点6.2 根的搜索根的搜索ab(0)f(0)f(0)f c1a1b1c(0)f2a2b3a3b nanb112baba2222baba2nnnbaba证明（思路）区间套2c(0)f3332baba0n 二分法停止规则停止规则*ln|-|2ln 2nnbabaxxn1.先验估计先验估计2.后验估计后验估计1|-|nnxx ()0 ()fxxxf改 写为 同 解 方 程其 中，连 续1 ()(0,1,2,.)kkxxk 121 ,.,.,kkkx xxxx则产生数列若

4、收敛，设极限为，则1limlim()()kkkkxx 可作为近似值可作为近似值充分大时充分大时之根，故当之根，故当是是即即1,0)(kxkxf1.一般迭代法及其收敛性一般迭代法及其收敛性6.3 迭代法及其收敛性迭代法及其收敛性简单迭代收敛情况的几何解释简单迭代收敛情况的几何解释xyy=xxyy=xx*x*x0p0 x1p1x0p0 x1p1)(xy)(xy例6.3.132*0()11.5.f xxxxx求在附近的根321.xx法一、方程变形为21+1/.xx法二、方程变形为1.1xx法三、方程变形为2.迭代法的收敛性迭代法的收敛性 (),xa b定理6.3设迭代函数在上.连续1且满足;)(,)

5、1(bxabax时当有且满足存在一正数,10,)2(baxLLLx|)(|1.(),*oxxa bx则方程在内有唯一解012.,()*okkxa bxxx对于任意初值迭代法均收敛于11*.3kkkoxxLLxx011*.4xxLLxxkko（收敛定理）（收敛定理）则设,(x)xg(x)连连续续)(,0)()(,0)()(xbbbgaaag*,()0,xa bg x至少有一故使个根),x(xkk 1对对于于迭迭代代法法由微分中值定理由微分中值定理*1xxk*)()(xxk*)(xxkkkxx1)()(1kkxx)(1kkxx|()|1 ()1()0 xLgxx由(),()0,.g xg xab则

6、递 增 故在根 唯 一上*(),.xxabx即在内 有 唯 一 解kkxx11kkxxL*1xxk*xxLk)(*11kkkxxxxL)(*11kkkxxLxxLkkkxxLLxx111*Lx|)(|由于11*kkkxxLLxx2121kkxxLL011xxLLk*1xxk*)(xxkkkxx1)(1kkxx0 1 *)xx(lim,Lkk由由于于*)(,10 xxxxkk均收敛于迭代法因此对任意初值11*kkkxxLLxx011xxLLk注注：L L越小，收敛越快。越小，收敛越快。指出指出:只要构造的迭代函数满足只要构造的迭代函数满足1|)(|Lx就收敛迭代法)(1kkxx 迭代法的收敛阶迭

7、代法的收敛阶(收敛速度收敛速度)*.limkkxx 若有实数若有实数c0,p11,使使*1*|(0)|lim|kpkkxccxxx 则称则称kx是是 p阶阶收敛收敛,相应的迭代法称为相应的迭代法称为p阶方法阶方法.特别地特别地,定义定义6.3.2:设设p=1时时,称为线性收敛称为线性收敛;1p2时时,称为超线性收敛称为超线性收敛p=2时时,称为平方收敛或二次收敛。称为平方收敛或二次收敛。迭代p阶收敛的充分条件6.4 方程求根的牛顿法方程求根的牛顿法6.4.1.一元方程牛顿法一元方程牛顿法2()()()()()()2!kkkkkfxf xf xfxxxxxTaylorTaylor展开线性化（展开

8、线性化（重要思想重要思想）1()()(k0,1,.)kkkkf xxxfx()0()()()0kkkf xf xfxxx近似于 ()kf xxTaylor将在点作展开：1,kxx解出记为则()()()()kkkf xf xfxxx ()()()()kkkkf xxyf xfxxx用在点处的切线1 kxx与轴的交点，作为下一个迭代点，1()()kkkkf xxxfx即)()(1kkkkxfxfxxNewtonNewton迭代法迭代法需要求每个迭代点处的导数需要求每个迭代点处的导数复杂！复杂！0(),kkxfxx用近似替代中的得)()(01xfxfxxkkk这种格式称为这种格式称为简化简化Newt

9、onNewton迭代法迭代法精度稍低精度稍低()kf x无论哪种迭代法：无论哪种迭代法：NewtonNewton迭代法迭代法简化简化NewtonNewton法法3()3,*1.6717f xxxx精确解用用NewtonNewton迭代法求解迭代法求解:321(3)/(31)kkkkkxxxxxx0=1x1=2.5000 x2=1.9296x3=1.7079x4=1.6726x5=1.6717x6=1.6717是否收敛是否收敛均与初值的位置有关均与初值的位置有关.01x 若取初值x0=0 x1=-3.0000 x2=-1.9615x3=-1.1472x4=-0.0066x5=-3.0004x6=

10、-1.9618收敛收敛发散发散00 x 若取初值*0()(.1)26 40.xf xxxxffxxx 假设是的单根，在根的邻域：内具有二阶连续导数，且对任意有，又因初值，则当邻域充分小时，牛顿法具有 阶收定理敛速度改进的Newton迭代 拟Newton法（Broyden方法）离散Newton法 简化Newton迭代6.6.非线性方程组的迭代法非线性方程组的迭代法12()(),(),()Tnxxxxx 把非线性方程组改写成(1)()(),0,1,kkxxk 并构造不动点迭代法(0)x给定初始点，()kx生成迭代序列()*limkkxx若，(),x且是连续的*()xxx 则满足*()xx即是迭代函

11、数的不动点，*x故是方程组的解。例例 设有非线性方程组设有非线性方程组081008102122122121xxxxxxx把它写成等价形式把它写成等价形式 22111212222121 211(,)(8)101(,)(8)10 xx xxxxx xx xx并由此构造不动点迭代法并由此构造不动点迭代法(1)()()()2()2111212(1)()()()()2()22121211(,)()()8101(,)()810kkkkkkkkkkkxxxxxxxxxxx,1,0k)(1kx)(2kx取初始点取初始点 。计算结果列于表。计算结果列于表1，可见迭代收敛到方，可见迭代收敛到方程的解程的解Tx)0

12、,0()0(Tx)1,1(*表表k012 18 1900.80.9280.9999999720.99999998900.80.9310.9999999720.9999999896.6.2.非线性方程组的非线性方程组的Newton法法对于非线性方程组，也可构造类似于一元方程的对于非线性方程组，也可构造类似于一元方程的Newton迭代法。迭代法。()*(),kixf xTaylor用点处的一阶展开式近似每一个分量函数的值()*()*()1()()()(),1,2,knkkiiijjjjf xf xf xxxinx*()()*()()()()()kkkF xF xF xxx写成向量形式有设设 是方非

13、线性程组的解，是方非线性程组的解，是方程组的一个近似解。是方程组的一个近似解。)(kx*x 11112122221212()()()()()()()()()nTTnTnnnnnfxf xf xxxxf xfxfxfxfxxxxFxfxfxfxfxxxx*()()*()()()()()kkkF xF xF xxx()()()()()kkF xF xF xxJacobi其中为的矩阵在的值，而*()()*()()()()()kkkF xF xF xxx()()kF x若矩阵非奇异，0()()*()()()()0kkkF xF xxx解*()()1()()(),kkkxxF xF x(1)()()1(

14、)()(),kkkkxxF xF x迭代格式Newton迭代法(1)()()kkxx 若写成一般不动点迭代形式1()()()xxF xF xNewton则迭代函数为(1)()()1()()()kkkkxxF xF xNewton 迭代格式k实际计算(第 步)：()()()()()kkkF xxF x 再解线性方程组()kx(1)()()kkkxxx()()()()kkF xF x先计算向量和矩阵(1)()()1()()(),kkkkxxF xF xNewton 迭代格式22112212121080 1080 xxxx xxxNewton用法解方程组例2211221212108()108xxxF

15、 xx xxx解：，(0)(0,0)Tx取初始向量，(0)(0)(0)()()F xxF x 解方程组(0)10081108x 即1222122102()1210 xxF xxx x(0)0.80.88x(1)(0)(0)(0.8,0.88)Txxx(2),x同理计算可见，可见，Newton法的收敛速度比例法的收敛速度比例1中的迭代法（中的迭代法（4）要快的多。）要快的多。表表 kx2kx1k01 2 3 400.800.9917872210.9999752291.0000000000.880.9917117370.9999685241.00000000关于关于Newton法的收敛性，若法的收敛性，若满足满足Lipschitz条件有局部收敛性条件有局部收敛性作业10 本章小结+课后习题第8、16题。