第五章 1 一元方程的迭代法

1、第第5 5章章 非线性方程求解非线性方程求解第第5章章 非线性方程求解非线性方程求解 非线性方程5.1 解一元方程的迭代法解一元方程的迭代法( )0 (5-1)f x fx其中, 是实变量 的非线性实单值函数是指形如以下形式的方程*(5-1),x满足方程的实数*()0f xx使成立的(5 1)称为方程非线性的解( )f x一元非线性方程是指多项式的非线性方程( )f x只有当为不超过4次的多项式时,可使用公式求得解,即形如-1-110( )01nnnnf xa xaxa xan的方程,其中5.1 解一元方程的迭代法解一元方程的迭代法可以使用迭代法获得(5-1)的近似解需要讨论以下几个问题(1)

2、迭代格式的构造(0)x(2)迭代的初始条件的选取( )kx(3)迭代产生的序列的收敛性(4)迭代的终止条件和误差估计两种方法( )*kkxxa.第 次迭代后,充分接近于( ),()kkf xb.第 次迭代后 有(5)迭代次数的设定第第5章章 非线性方程求解非线性方程求解5.1 解一元方程的迭代法解一元方程的迭代法5.1.1 简单迭代法简单迭代法简单迭代公式(1)( )(),0,1,2,. (5-3)kkxxk,构造 (x)使(0)x当给定初始近似值后,只需逐次计算函数值,( )kx可获得迭代序列由于这一迭代过程十分简单,简因此称为单迭代法( ) x称为迭代函数(5 1)( ),(5-3)xx迭

3、代格式的获得 将改写为可得到形如的等价方程不动点( )( )*( ),(5-3)lim,()kkkxxxxxx 若为连续函数 则当迭代式产生的序列收敛并且满足时 有*( )xx 则 为方程(5-1)的解,也称为的不动点第第5章章 非线性方程求解非线性方程求解5.1 解一元方程的迭代法解一元方程的迭代法5.1.1 简单迭代法简单迭代法-20,0,1xxe例 5.1 设方程在中有一解(0)( )-( ),0 xxf xx得到迭代格式取( )(1)2,0,1,2,.kkxxek不收敛(1)( )ln(2),0,1,2,.kkxxk收敛20, 2, 1,1,2xxe例 5.2 设方程在中各有一根( )

4、(1)2,0,1,2,.kkxxek取(0)0 x 时收敛(0)1x 时收敛(0)1.5x时不收敛(1)( )ln(2),0,1,2,.kkxxk取(0)1.5x时收敛(0)( 1.841406,)x 当时收敛(0)( 2, 1.841406)x 当时不收敛第第5章章 非线性方程求解非线性方程求解5.1 解一元方程的迭代法解一元方程的迭代法5.1.2 牛顿迭代法牛顿迭代法( )kkx设第 次近似已知( )( )( )()()kkkxf xfx,以处的两个函数信息和Newton构造插值多项式( )( )( )( )()()( -)kkkl xf xfxx x( )f x在局部代替函数,有( )(

5、 )( )()()( -)0kkkf xfxx x得到( )( )( )()()kkkf xxxfx(1)kxNewton这一迭代方法称为迭代法( ) ( )( )f xxxfx其迭代函数为*()0,( )0( )fxf xxx当时的解 必为方程的不动点第第5章章 非线性方程求解非线性方程求解5.1 解一元方程的迭代法解一元方程的迭代法5.1.2 牛顿迭代法牛顿迭代法Newton迭代法的几何意义( )( )(1) (,(),( ),kkkxf xyf xxx它在点邻近的局部范围内以过此点的切线近似代替曲线以切线与 轴的交点 作为下一次的近似 特点(2)由于要计算导数,因此计算量稍大Newton

6、可以使用一点迭代法( )(1)( )( )()()kkkkf xxxfx( )( )(0)(),0,1,2.()kkf xxkfx (1):Newton速度快迭代法比简单迭代法收敛快第第5章章 非线性方程求解非线性方程求解5.1 解一元方程的迭代法解一元方程的迭代法5.1.3 割线法割线法为避免求导数值,(1)(1)( )( )(,()(,()kkkkxf xxf x可以通过和( )f x的线性插值公式近似( )(1)( )( )(),()0kkkkf xf xxxx( )(1)( )( )(1)( )(1)(),0,1,2,.()()kkkkkkkf xxxkf xf xxx得到割线法的迭代

7、式 (1)( )( )(1)(1)( )(1)()(),0,1,2,.()()kkkkkkkxf xxf xxkf xf x或 ( )(1)( )( )( )(1)(),0,1,2,.()()kkkkkkxxxf xkf xf x第第5章章 非线性方程求解非线性方程求解5.1 解一元方程的迭代法解一元方程的迭代法5.1.3 割线法割线法(1)(1)(1)( )( ),()(,()kkkkkxxf xxf xx几何意义 为过(和的割线与 轴的交点割线法的迭代公式可以写为(1)( )( -1)(,)kkkxxx因此,称其为两步法方法其速度比简单方法快,比Newton方法慢( )(1)*( )( -

8、1),(),(),kkkkxxxf xf x当接近于 时也较接近 因此会引起较大误差( )( )(1)( )(1)( )(1)(1)()()()/ 1()()kkkkkkkkf xf xxxxxf xf x 第第5章章 非线性方程求解非线性方程求解第第5章章 非线性方程求解非线性方程求解5.1 解一元方程的迭代法解一元方程的迭代法5.1.4 区间方法区间方法思想:( )kI迭代过程确定了一个区间的序列( )kI,使每个区间*,x都包含方程的一个解( )kI且区间长度趋向于零,则当区间长度足够小时,*x必有区间中的任一点与 的差小于给定误差值 ,则*x可取区间中的任一点作为要解决的问题:(1)初

9、始区间的确定0101() ( )0,f xf xx x满足的区间都可以作为初始区间*x(2)如何缩小区间,使得缩小后的区间中仍保含(3)评定误差第第5章章 非线性方程求解非线性方程求解5.1 解一元方程的迭代法解一元方程的迭代法5.1.4 区间方法区间方法二分法思想是每次减少区间的一半算法0(0)(1),Ixx(1)确定初始区间(0)(1)() ()0,0f xf xk,满足_( )(1)( )(1)1, ()2kkkkkIxxxxx(2)计算区间的中点_( )(1)(1)( )() ( )0, ,kkkkf xf xxxIxx(3)若则令,取=_( )(1)(1),kkkxxIx x否则令,

10、取=( )(1),kkxx(4)计算区间长度,若0的初值Newton,迭代产生的序列( )*( )0kxf xx单调地收敛于方程的唯一解第第5章章 非线性方程求解非线性方程求解5.2 收敛性问题收敛性问题5.2.3 Newton法的收敛性法的收敛性05.8,aa 对任何正数求例x 若令a(1)( )( )1 ,0,1,2,.2kkkNewtonaxxkx构造迭代格式1, ,Ia取区间则定理5.4的条件全部满足( ),kNewtonxa因此迭代序列收敛 且收敛于2( )f xxa则等价于求的正根第第5章章 非线性方程求解非线性方程求解5.2 收敛性问题收敛性问题5.2.3 Newton法的收敛性

11、法的收敛性*( )( )0 , f xf xxa b设在包含方程的定理5.5解 的区间上 二次可微且满足以下条件 , ,( ) ( )0a bf a f b (1)在上( ) , f xa b(2)在上是单调函数 , xa b ,即对( )fx,不变号( )0fx,且( ) , f xa b(3)的凹向在上不变( ) , fxa b即在上不变号00(f xfx则对任意满足)011(f x fx,)010(f xf x)(0)(1)( )*,kxxxx的以及以它们为初值的割线法所产生的迭代序列收敛于第第5章章 非线性方程求解非线性方程求解5.2 收敛性问题收敛性问题5.2.4 收敛速度收敛速度在

12、进行迭代的过程中,需要考虑迭代过程中的 (1)迭代次数 (2)每次迭代的运算量,5.2由推论知(1)*( )* k=0,1,2,. (5-23)kkxxq xx1(0)* kqxxq常数 可以用来确定收敛的速度 q越小,则收敛速度越快q称具有这种性质的收敛性是具有收敛常数 的线性收敛称这类收敛速度为线性收敛速度线性简单收迭代法是敛的方法( )( )xyq xy当迭代公式满足第第5章章 非线性方程求解非线性方程求解5.2 收敛性问题收敛性问题5.2.4 收敛速度收敛速度Newton法*( )()0f xfx当两次可微且,迭代函数满足*()0 x( )*,kNewTonxx因此 当迭代序列收敛于

13、时 ,有()kkq 记lim()kk 由于0于是有此类的收敛要比(5-23)线性收敛要快一点*( )(5-25)kxx称满足条件并收敛于 的序列为超线性收敛的NewTon法为超线性收敛的(1)*( )*( )*(),kkkkkxxxxxx 是与 之间的某个数(1)*( )* (5-25)lim0kkkkkxxq xxq*()x第第5章章 非线性方程求解非线性方程求解5.2 收敛性问题收敛性问题5.2.4 收敛速度收敛速度由于( )( )( )( )()()( -)kkkl xf xfxx x( )( )( )()()( -)0kkkf xfxx x因此*( )( )*( )*( )210()(

14、)()(-)()(-)2kkkkkf xf xfxxxfxx( )( )(1)( )0()()(-)kkkkf xfxxx两式相减( )(1)*( )21()(-)()(-)2kkkkfxxxfxx*( )()0,fxfx由于连续且( )*,kxxk当收敛于 时 对充分大的( )()0kfx总有从而(1)*( )2( )()1-(-)2()kkkkfxxxxfx第第5章章 非线性方程求解非线性方程求解5.2 收敛性问题收敛性问题5.2.4 收敛速度收敛速度( )()1max2()kkfqfx若令2(1)( )( )(*) (5-26)kkkxxq xx则有 (*)( )kxx称满足条件式(5-26)的收敛于的序列称为二阶收敛的Newton