§2.3-牛顿(Newton)法及其变形

2.3牛顿（Newton）法及其变形一、Newton迭代方法牛顿迭代法计算公式的推导过程设*x是()0fx的根，()fx在*x的邻域内具有二阶连续导数，在*x的邻域内取一点0x，使0()0fx，则()fx在*x的邻域内连续，将它在0x点二阶Taylor展开得20000000()()()()()()2!()()()ffxfxfxxxxxfxfxxx又()0fx，则有000()()()0fxfxxx故()0fx的近似解000()()fxxxfx，记0100()()fxxxfx类似，在点1x处Taylor展开，可得：111()()fxxxfx，记1211()()fxxxfx依次往下做，可得一般的迭代格式：1(),(0,1,)()kkkkfxxxkfx上述迭代格式称为求()0fx的解的牛顿迭代法。几何意义在点00(,())xfx处作()fx的切线，交x轴于一点，求该点的横坐标。此切线方程为000()()()yfxfxxx，当0y时，得000()()fxxxfx，正是1x的值。类似地，在点(,())kkxfx作函数()fx的切线，交x轴于一点，切线方程为()()()kkkyfxfxxx，当0y时，得()()kkkfxxxfx，正是1kx的值。所以，牛顿迭代法又称为切线求根法。例6用牛顿迭代法求方程xxe在0.5x附近的根。解.将原方程化为()0xfxxe，则牛顿迭代格式为11kkxkkkxxexxe取00.5x，迭代得1230.5663110.5671431,0.5671433xxx与上一节例2-4相比,牛顿法的收敛速度快。与埃特金法相当.注意：牛顿法的几何意义说明了，迭代初值0x必须足够接近*x，否则可能不收敛或收敛与其它的根。牛顿迭代法的流程图输入迭代初始值0x，精度，最大迭代次数NNk,,2,10'0fTF输出0'0f的信息，结束000'/ffxx1xTF0xxExxxE/0ETF输出kxfx),(,，结束xx0输出迭代N次失败信息，停。二、Newton迭代法的变形牛顿法的优点:收敛速度快。)(''),(0000xffxff牛顿法的缺点:每次迭代要计算一次导数值'()kfx，当()fx表达式复杂或无明显表达式时求解困难。简化的牛顿迭代法1.主要思路:为了避免直接计算导数值，用某个定点上的值（或一常数M）取代()kfx，如，令0()Mfx，则牛顿迭代法的迭代格式变为：10()(),(0,1,)()kkkkkfxfxxxxkfxM称它为简化的牛顿迭代法。只要M选择得当，上式总是收敛的，不过其收敛速度降为线性.2.几何意义其几何意义可描述为用平行线代替牛顿法中的切线。过点(,())kkxfx，斜率为0()fx的直线与x轴有一交点，下面求出该交点的横坐标。该直线的方程为0()()()kkyfxfxxx当0y时，即为直线与x轴交点的横坐标值，也就是简化的牛顿迭代方法中的1kx的表达式：10()()kkkfxxxfx3.优缺点优点：计算简单。缺点：没有充分利用()fx本身的特性，收敛速度慢，收敛阶为1。割线法1.双点割线法(1)基本思想:利用一阶差商11()()kkkkfxfxxx取代牛顿迭代法中的()kfx，则有111()()()kkkkkkkfxxxfxfxxx，即111()()()()kkkkkkkfxxxxxfxfx。上式称为双点割线法。可以验证，在满足一定条件下，其收敛阶1(15)1.6182p(2)几何意义1kx为过点11(,())kkxfx与(,())kkxfx的割线和x轴交点的横坐标。事实上，连接11(,())kkxfx与(,())kkxfx，得到一条直线，该直线的方程为：11()()()()kkkkkkfxfxyfxxxxx当0y时，得到它与x轴的交点的横坐标值，即1kx：111()()()()kkkkkkkfxxxxxfxfx，每一次作迭代序列的第三点时，它都是利用前面两个已知点作曲线()fx的割线，这正是为什么它称为双点割线法的原因。注意：双点割线法必须预先给定两个迭代初始值。2．单点割线法(1)基本思想在用双点割线法计算时，每次都必须计算相邻两个点的函数值，为了简化计算，在计算的过程中固定一点，譬如说是00(,())xfx，让另外一点变化，即用点00(,())xfx代替点11(,())kkxfx，则有100()(),()()kkkkkfxxxxxfxfx上式称为单点割线法，其意义很明了，因为只有一点变化，故称为单点割线法。其具体实现过程如下：预先给定两点00(,())xfx和11(,())xfx，利用单点割线法的计算公式计算出2x的值，然后利用00(,())xfx和22(,())xfx这两点计算3x的值，这么一直做下去，1kx的值是利用00(,())xfx和(,())kkxfx这两点计算而得。(2)几何意义连接点00(,())xfx和点(,())kkxfx，得到一条直线，它和x轴的交点的横坐标的值就是1kx。可以证明，在一定的条件下，单点割线法的收敛阶为1.三、计算重根的牛顿迭代法主要讨论用牛顿迭代法解决重根的问题直接利用牛顿迭代法来求解设*()0xfx为方程的m重根（2m）。这时，*()()()mfxxxgx,*()0gx若直接用牛顿迭代法计算*x的近似值，迭代过程的收敛速度变成线性收敛。这是因为*1*()()()'()()()'()kkkkkkkkkkfxxxgxxxxfxmgxxxgx令*kkexx，则**111()()'()()1()'()110limlimkkkkkkkkkkkkxxkkkkegxexxemgxegxegxemgxegxm（*）所以直接用牛顿迭代法求解，效果并不理想。提高收敛速度有两种方法：(方法一)将求重根的问题转化为求单根。注意到***()()()()'()()()'()()()fxgxuxxxfxmgxxxgxxxQx，由于*1()0Qxm，所以*x是()0ux的单根。因此，求()0fx的m重根*x等价于求()0ux的单根*x，而对()0ux用牛顿迭代法求根是平方收敛的，其迭代格式为：12()()'()'()'()()''()kkkkkkkkkkuxfxfxxxxuxfxfxfx此迭代格式较复杂，应用起来不方便。(方法二)○1修改牛顿迭代法若用下述迭代函数建立迭代格式求解，则它的收敛阶为2。**1*()()()()()()()()()mmmfxmxxgxxxmxfxmxxgxxxgx**()()()()()mxxgxxmgxxxgx1**1***()()'()()()()()()()()()()()()kkkkkmkkkmmkkkkkkkkkkfxxxxmfxmxxgxxmxxgxxxgxmxxgxxmgxxxgx122()()()[()()]()()()()()()kkkkkkkkkkkkkkkkkkkkkkmegxeemgxegxemgxegxegxemgxegxegxmgxegx12()()()kkkkkkegxemgxegx若kx收敛，即0()kek，*kxx*12*()lim0()knkegxemgx所以,此种改进的牛顿迭代方法是平方收敛.○2确定根的重数设2kx，1kx，kx使牛顿迭代格式所得的三个相邻的迭代值，令112kkkkkxxxx,则1**11**21212111()()()()1kkkkkkkkkkkkkkkexxxxeeeeexxxxeeee由（*）式知111limkkmmm故1121kkkkkxxmxxm因此可以用下式估计m：11km例8用牛顿迭代法求方程3()(1)sin(1)310fxxxxx在0.95附近的根。解2'()sin(1)(1)cos(1)363fxxxxxx直接用牛顿迭代格式1()'()kkkkfxxxfx（0,1,2,k）有如下结果成立：kkxk11k01234560.950.97442790.98705830.99348780.99673280.99835760.99919010.50900.50470.50070.51252.03692.01902.00282.0511由121k知所求根为2m重根，我们采用修改的牛顿迭代公式1()'()kkkkfxxxmfx得00.95x10.9988559x231xx其收敛速度大大快于直接用牛顿迭代法。作业P36习题二11