数值分析3-1研

1、1第三章第三章 非线性方程组求根非线性方程组求根引言引言不动点迭代法不动点迭代法牛顿法及其变形牛顿法及其变形求解非线性方程组的牛顿法求解非线性方程组的牛顿法电子工程应用电子工程应用例例3.1： 隧道二极管电路隧道二极管电路 实际电路通常包含线性和非线性元件，二极实际电路通常包含线性和非线性元件，二极管是一种最基本的非线性元件。管是一种最基本的非线性元件。2隧道二极管的电流隧道二极管的电流- -电压关系电压关系电压电压- -x, , 电流电流- -y y =g(x)3.1 引言引言3.1 引言引言3( )0Rg xxE ( )Exg xR ( )yg x ExyR 引言引言二次方程二次方程420

2、axbxc的根可以表示为的根可以表示为242bbacxa 方程求根，也是求方程左边函数的零点方程求根，也是求方程左边函数的零点各类方程均可表示为各类方程均可表示为( )0f x 若若f(x)是多项式是多项式 f(x)=a0+a1x+a2x2+anxn 5若若f(x)含三角函数、指数函数等超越函数含三角函数、指数函数等超越函数则方程则方程 f (x)=0 超越方程超越方程 例如：例如： x2-5x+2=02 2次代数方程次代数方程2x-5x+2=0超越方程超越方程3.1 引言引言则方程则方程 f (x)=0 n次代数方程次代数方程高于高于1次的代数方程和超越方程次的代数方程和超越方程 非线性方程

3、非线性方程 非线性方程求根非线性方程求根 f(x)=0 6非线性问题的求解，比线性问题复杂非线性问题的求解，比线性问题复杂x*y= f(x)Oxy若有若有x*，使，使 f(x*)=0成立，成立，则则 x*是方程是方程 f(x)=0 的的根根 或函数或函数 f(x) 的的零点零点3.1 引言引言7若若 f(x) 可分解为可分解为 ),(*)()(xgxxxfm 其中其中 为正整数，且为正整数，且 m*()0.g x当当m=1时，称时，称 x* 为单根为单根 ；*(1)*()()()0,mf xfxfx()*()0.mfx当当m1时，称时，称 x* 为为m重根，或重根，或 x* 为为f(x)的的m

4、重零点。重零点。若若x* 为为f(x)的的m重零点，且重零点，且g(x)充分光滑，则充分光滑，则3.1 引言引言1. 对于高次代数方程对于高次代数方程(次数大于等于次数大于等于4)，不能用方，不能用方程系数的解析式表示程系数的解析式表示2. 对于超越方程，没有求根公式对于超越方程，没有求根公式 如何求根？如何求根？8本章内容：本章内容：非线性方程和方程组求非线性方程和方程组求根的近似值的各种根的近似值的各种数值方法数值方法3.1 引言引言9 方程求根，主要解决以下问题：方程求根，主要解决以下问题： 3. 根的精确化根的精确化1. 根的存在性（方程有无根？若有，有根的存在性（方程有无根？若有，有

5、几个根？）几个根？）2. 根的隔离（根的分布）根的隔离（根的分布）3.1 引言引言不动点迭代法不动点迭代法-迭代格式的构造迭代格式的构造迭代的敛散性条件迭代的敛散性条件迭代法的局部收敛性迭代法的局部收敛性迭代法的收敛速度迭代法的收敛速度牛顿法牛顿法牛顿法的局部收敛性牛顿法的局部收敛性3.23.2 迭代法迭代法不动点迭代法不动点迭代法-迭代格式的构造迭代格式的构造迭代的敛散性条件迭代的敛散性条件迭代法的局部收敛性迭代法的局部收敛性迭代法的收敛速度迭代法的收敛速度牛顿法牛顿法牛顿法的局部收敛性牛顿法的局部收敛性3.23.2 迭代法迭代法3.2 迭代法迭代法基本思想：基本思想：逐次逼近逐次逼近用某个

6、固定公式反复校正根的近似值，从而得到一用某个固定公式反复校正根的近似值，从而得到一个近似根的序列个近似根的序列 xk ，使该序列的极限为方程的根。，使该序列的极限为方程的根。12 是一种常用的计算技术是一种常用的计算技术 将一个计算过程反复进行将一个计算过程反复进行 构造有效的迭代格式构造有效的迭代格式 选取合适的迭代初值选取合适的迭代初值 对迭代格式进行收敛性分析对迭代格式进行收敛性分析3.2.1 迭代法迭代法-迭代格式的构造迭代格式的构造已知方程已知方程 f (x) = 0 在区间在区间a,b 内有一根内有一根 f(x)=0 x=(x) （同解方程）（同解方程）若存在若存在 x*，使使 x

7、*=(x*)，则则 x*是方程是方程 f(x)=0 的根（也称为的根（也称为(x) 的的不动点不动点）13任取任取0 , xa b 代入递推公式代入递推公式1(),0,1,2kkxxk 得序列得序列012,xxx 记为记为 xk14当当k 若序列若序列xk有极限有极限x*，且且(x)在在x*附近连续附近连续时时x*=(x*)1(),0,1,2kkxxk 迭代格式迭代格式(x)迭代函数迭代函数迭代序列迭代序列xk迭代收敛迭代收敛k 时，时，xk有极限有极限x*迭代发散迭代发散*0 xx 时，时，xk无极限无极限此种求根方法此种求根方法称为称为不动点迭代法不动点迭代法（简单迭代法简单迭代法）。）。

8、1limlim ()kkkkxx (lim)kkx f(x*)=0可得可得3.2.1迭代法迭代法-迭代格式的构造迭代格式的构造151(),0,1,2kkxxk 不动点迭代法是一种逐次逼近法，其基本思想是将不动点迭代法是一种逐次逼近法，其基本思想是将隐式方程隐式方程( )0f x 归结为一组显式的计算公式归结为一组显式的计算公式即：迭代过程实质上是一即：迭代过程实质上是一个逐步显式化的过程个逐步显式化的过程x0y = x( )yx x1x2x*(x0, y0)(x1, y1)( )xx ( )yxyx 3.2.1迭代法迭代法-迭代格式的构造迭代格式的构造输入：输入：x0, f(x), phi(x

9、); 输出：输出：x.k = 0; er=1; while |f(x0)| epsi1 或或 er epsi2 x = phi(x0); er = |x-x0|; x0 = x; k = k+1;end16算法：不动点迭代法算法：不动点迭代法3.2.1 迭代格式的构造迭代格式的构造例例3.2：求方程：求方程 在区间在区间1, 2内的根。内的根。以不同的方式得到方程的等价形式，并研究相应以不同的方式得到方程的等价形式，并研究相应的不动点迭代法的收敛情况。的不动点迭代法的收敛情况。17324100 xx解：将原方程化为与其等价的方程解：将原方程化为与其等价的方程形式一：形式一：迭代函数为迭代函数为

10、32410 xxxx321( )410 xxxx则迭代格式为则迭代格式为321410kkkkxxxx3.2.1 迭代格式的构造迭代格式的构造以初值以初值 x0=1.5 代入，迭代代入，迭代4次的结果为次的结果为18k012341.5-0.8756.732-469.7kx81.03 10显然，继续迭代下去已经没有必要显然，继续迭代下去已经没有必要因为迭代结果的绝对值显然会越来越大，且正负值因为迭代结果的绝对值显然会越来越大，且正负值交替出现，不可能趋于某个定数交替出现，不可能趋于某个定数这种不收敛的迭代过程称作是这种不收敛的迭代过程称作是发散发散的的3.2.1 迭代格式的构造迭代格式的构造形式二

11、：将原方程形式二：将原方程 改写成改写成考虑所求的根为正根，方程可化为考虑所求的根为正根，方程可化为1923410 xx3 1/21(10)2xx迭代格式为迭代格式为3 1/211(10)2kkxx 13221( )10-2xx 即即324100 xx3.2.1 迭代格式的构造迭代格式的构造取初值取初值 x0=1.5，多次迭代可得，多次迭代可得20k01238201.51.28695381.40254081.34545841.36541011.3652302kx迭代迭代8次，近似解便已稳定在次，近似解便已稳定在1.365上。迭代上。迭代收敛！收敛！原方程可转化成多种等价形式，有多种迭代格式原方

12、程可转化成多种等价形式，有多种迭代格式有的收敛，有的发散有的收敛，有的发散只有只有收敛收敛的迭代格式才有意义的迭代格式才有意义不动点迭代法不动点迭代法-迭代格式的构造迭代格式的构造迭代的敛散性条件迭代的敛散性条件迭代法的局部收敛性迭代法的局部收敛性迭代法的收敛速度迭代法的收敛速度牛顿法牛顿法牛顿法的局部收敛性牛顿法的局部收敛性3.23.2 迭代法迭代法22问题：问题： 如何判断迭代格式是否收敛？如何判断迭代格式是否收敛？ 误差怎样估计？误差怎样估计？ 如何构造如何构造收敛的收敛的迭代格式？迭代格式？3.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性233.2.2 不动点的

13、存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性x0y = x( )yx ( )x 迭代函数迭代函数( )xx ( )yxyx x1x2x*x0y = x( )yx x1x2x*(x0, y0)(x1, y1)(x0, y0)(x1, y1)kkkkyxyx1() 1()kkxx 如果如果 , 且满足两个条件且满足两个条件: ; 24,)(1baCx ( )axb 1| )(| Lx 则：则：(1) 方方 程程 x =(x) 在在a,b上有唯一根；上有唯一根； (2) 对任意对任意 x0 a, b , 迭代格式迭代格式 产生的序列产生的序列 xk 收敛到收敛到 x*1()kkxx *1|1

14、kkkLxxxxL (3)(4)*10|1kkLxxxxL (5)*1*lim()kkkxxxxx 定理定理3.1 不动点迭代全局收敛性定理不动点迭代全局收敛性定理25证：证：(1) 如何证如何证? 作函数作函数 g (x) = x - (x). 由条件由条件 知知( )( )0g aaa ( )( )0g bbb ( )0g x 由条件由条件在在a,b内至少存在一个根内至少存在一个根( )1( )10gxxL g (x) 严格单调增严格单调增( )0g x 在在a,b内至多只有一个根内至多只有一个根 x* 所以，方程所以，方程 x=(x) 在在a,b上有唯一根上有唯一根 x*bxa)(|(

15、)|1xL 区间内存在唯一根26(2)由由x0 a, b，及条件，及条件 知知 xk a, b (k=1,2,) 1*()()kkxxxx *1| |()()|kkxxxx *|,(0,1,2,)kL xxk*0|,(1,2,3,)kkxxLxxk1L *limkkxx *lim0kkxx（ ）bxa)(迭代序列收敛|( )|1xL *|()|kkxx 27(3) 由由*1|,(0,1,2,)kkxxL xxk *11| |kkkkxxxxxx而而*11|kkkxxxx*1|kkkL xxxx *11|1kkkxxxxL 11| |()|kkkkxxxx（ ）又又1|()|kkkxx （）*1

16、|,1,2,1kkkLxxxxkL k次迭代之后误差估计1|,1,2,kkL xxk 28当相邻两次迭代结果满足条件当相邻两次迭代结果满足条件1|kkxx L较小时，可以用相邻两次较小时，可以用相邻两次迭代结果之差来控制迭迭代结果之差来控制迭代过程是否结束代过程是否结束若若L1，则不能用此条件控制迭代过程则不能用此条件控制迭代过程实际误差为实际误差为*1|11kkkLLxxxxLL 利用两次迭代结果之差来估计误差利用两次迭代结果之差来估计误差误差事后估计式误差事后估计式29(4)由由11|,1,2,kkkkxxL xxk112|kkkkxxL xx*1|1kkkLxxxxL *10|,1,2,

17、1kkLxxxxkL 利用首次迭代结果与初值之差来估计误差。利用首次迭代结果与初值之差来估计误差。误差事前估计式误差事前估计式223|kkLxx110|kLxx 首次迭代之后估计误差30若给定精度为若给定精度为，则要求则要求可确定迭代次数可确定迭代次数k*10|1kkLxxxxL 10|(lnln)/ln1xxkLL 可知，可知，L L越小，收敛越快。越小，收敛越快。31由由*1*()()()()kkkkxxxxxx *1*(),0,1,2,kkkxxkxx *1*limlim()()kkkkkxxxxx 当当k 时，前后两次迭代的误差之比。时，前后两次迭代的误差之比。渐进误差估计式渐进误差估

18、计式(5)*1*lim()kkkxxxxx 迭代收敛速度32例例3-3： 用迭代法求方程用迭代法求方程2( )(1)10f xx x在区间在区间0,1 内的一个实根，精确到内的一个实根，精确到4位有效数字。位有效数字。解：解：2( )(1)10f xx x21(1)xx 21( )(1)xx 1( ) (1), (0) ,10,14x0,1，x 当当bxa)(满足满足定理定理3.1的的条件条件3.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性33(0)10f (1)30f1(1)( )(0)24x定理定理3.1的条件的条件未得到满足。未得到满足。缩小有根区间。用二分法。缩

19、小有根区间。用二分法。32( )(1)xx 21( )(1)xx |( )|1xL 2( )(1)10f xx x1) (0.5)0.1250f0,0.5x ，(0)21 ，条件，条件不满足不满足，有根区间为，有根区间为0,0.5.3.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性342) (0.25)0.6093750f 0.25,0.5x ，(0.25)1.024 条件条件不满足不满足3) (0.375)0.2910156250f 0.375,0.5x 当当时时，( )(0.375)0.76931x条件条件满足满足 当当( ) (0.5), (0.375)0.4444

20、,0.5289x条件条件不满足不满足0.375,0.5 (0.5)0f (0.5)0f bxa)(3.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性354) (0.4375)0.09590f ( )(0.4375)0.67331x0.4375,0.5x 当当时时，条件条件满足满足( ) (0.5), (0.4375)0.4444,0.4839x条件条件满足满足根据定理根据定理3.1，对任意，对任意x0 0.4444,0.4839，此此迭代格式收敛。迭代格式收敛。0.4375,0.5 对于定理3.1，迭代初值必须同时满足两个条件，迭代格式才收敛。收敛条件要求较高。(0.5)

21、0f 3.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性36fi=inline(1/(x+1)2 );x0=0.46;er=1;k=0;while er0.00005 x=fi(x0) er=abs(x-x0); x0=x;k=k+1;end若取若取x00.46，k=13, x=0.46558659888486若取若取x00.45，k=15, x=0.465588677959703.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性不动点迭代法不动点迭代法-迭代格式的构造迭代格式的构造迭代的敛散性条件迭代的敛散性条件迭代法的局部收敛性迭代法的局部收敛性迭

22、代法的收敛速度迭代法的收敛速度牛顿法牛顿法牛顿法的局部收敛性牛顿法的局部收敛性3.23.2 迭代法迭代法3.2.3 迭代法的局部收敛性迭代法的局部收敛性定义定义 对于方程对于方程 x=(x) ，若在，若在 x*的某邻域的某邻域38Rx xx* 内内，对任意，对任意 x0 R，迭代格式，迭代格式1(),(0,1,2,)kkxxk 都收敛都收敛，则该迭代格式在，则该迭代格式在 x*的附近的附近 局部收敛局部收敛。39若若x0靠近根靠近根x*，可用，可用0()1x 来判断迭代格式局部收敛或发散。来判断迭代格式局部收敛或发散。0()1x 3.2.3 迭代法的局部收敛性迭代法的局部收敛性定理定理3.2

23、设方程设方程 x=(x) 有根有根x*，且在其某邻域，且在其某邻域*Sx xx 内内, (x) 存在一阶连续导数，则存在一阶连续导数，则（1）当）当 *()1x 时，此迭代格式局部收敛；时，此迭代格式局部收敛；（2）当）当 *()1x 时，此迭代格式发散。时，此迭代格式发散。回忆：与定理回忆：与定理3.1的区别的区别403.2.3 迭代法的局部收敛性迭代法的局部收敛性证明：证明：(1) 设设 时，时， *0,Sxx 要证：要证：0( )xS 0,xS *( )()( )xxxx *( )() ,(, )( ,)xxxxx x 或*xx 即：即：0( )xS 定理定理3.1的条件得到满足的条件得

24、到满足迭代格式迭代格式局部收敛局部收敛( )1x 4132( )(1)xx (0.4)0.72891 由定理由定理 3.2知，迭代格式知，迭代格式121(1)kkxx 局部收敛局部收敛迭代格式局部收敛迭代格式局部收敛*()1x 例例: 用迭代法求方程用迭代法求方程2( )(1)10f xx x在在x0=0.4附近附近的一个实根。的一个实根。解：解：21(1)xx 21( )(1)xx 42fi=inline(1/(x+1)2 );x0=0.4;er=1;k=0;while er0.00005 x=fi(x0) er=abs(x-x0); x0=x;k=k+1;end若取若取x00.4，k=19

25、, x=0.4655835827521503.2.3 迭代法的局部收敛性迭代法的局部收敛性不动点迭代法不动点迭代法-迭代格式的构造迭代格式的构造迭代的敛散性条件迭代的敛散性条件迭代法的局部收敛性迭代法的局部收敛性迭代法的收敛速度迭代法的收敛速度牛顿法牛顿法牛顿法的局部收敛性牛顿法的局部收敛性3.23.2 迭代法迭代法3.2.4 迭代法的收敛速度迭代法的收敛速度44定义：定义： 设序列设序列xk 收敛于收敛于x*， ek= xk - x*， (k=0,1,2,) 。若有非零常数若有非零常数 c 和正和正整整数数 p，使使1limkpkkece 则称则称序列序列xk p阶阶收敛。收敛。线性收敛：线

26、性收敛：p=1, 且且01c超线性收敛：超线性收敛：p1。其中，。其中，p=2，平方收敛平方收敛。序列的收敛阶数越高序列的收敛阶数越高,收敛速度越快。收敛速度越快。迭代格式产生的迭代格式产生的序列序列 p 阶收敛阶收敛，则称此，则称此迭代格式迭代格式 p阶收敛阶收敛。45例：例： 2个个迭代格式分别是线性收敛和平方收敛：迭代格式分别是线性收敛和平方收敛：11(1),(0,1,2,);2kkeke 121(2),(0,1,2,);2kkeke 其中，其中，0013ee，若要求精度，若要求精度1010, 估计迭代格式估计迭代格式收敛收敛所需的迭代次数。所需的迭代次数。3.2.4 迭代法的收敛速度迭

27、代法的收敛速度46解：解：（1）由）由101123kkeee 及10111 12322kkkkeee 1010ke 31.63k 应迭代应迭代32次次（2）由）由1021123kkeee 及1222211 1)22 2kkkeee （1010ke 3.73k 应迭代应迭代4次次021221221111( )( )( )2( )2236kkkkke47定理定理3.3：设设(x) 在在x* 附近的某邻域内有附近的某邻域内有p ( p 1 )阶连续导数，且阶连续导数，且*(),xx *()0,x (1)*.,()0,px ()*()0px 则对一个任意靠近则对一个任意靠近x* 的初值，迭代公式的初值

28、，迭代公式1(),(0,1,2,)kkxxk p 阶收敛，且阶收敛，且*()*1*()lim!()pkpkkxxxpxx 如果如果p1，则，则 要求要求*()1x 3.2.4 迭代法的收敛速度迭代法的收敛速度483.2.4 迭代法的收敛速度迭代法的收敛速度证明证明：(1)设设 根据定理根据定理3.2，可以断定迭代，可以断定迭代过程过程 具有局部收敛性。具有局部收敛性。 *()0,x 1()kkxx 将将 在根在根 x*处做泰勒展开，利用条件处做泰勒展开，利用条件则有：则有： ()kx ()*()0px ()*( )()=+()!ppkkxxxxp （ ）*1(), (),kkxxxx ()*1

29、( )()!ppkkxxxxp *()1*( )()!pkpkxxxxp 迭代过程为迭代过程为p阶收敛阶收敛 49(2) 若若*()0,()1,xx 且且线性收敛。线性收敛。定理定理3.1已证明已证明迭代法的收敛速度和迭代函数的选取有关迭代法的收敛速度和迭代函数的选取有关如何构造高阶迭代函数？如何构造高阶迭代函数？3.2.4 迭代法的收敛速度迭代法的收敛速度不动点迭代法不动点迭代法-迭代格式的构造迭代格式的构造迭代的敛散性条件迭代的敛散性条件迭代法的局部收敛性迭代法的局部收敛性迭代法的收敛速度迭代法的收敛速度牛顿法牛顿法牛顿法的局部收敛性牛顿法的局部收敛性3.3 牛顿法牛顿法513.3 牛顿法

30、牛顿法简单迭代法（不动点迭代法）简单迭代法（不动点迭代法）( )xx 不易得到收敛速度快的迭代函数，且可能发散不易得到收敛速度快的迭代函数，且可能发散牛顿法牛顿法：用线性方程近似代替非线性方程：用线性方程近似代替非线性方程f(x)=0可以方便地得到快速收敛的迭代公式可以方便地得到快速收敛的迭代公式52设方程设方程 f (x) = 0取取初值初值为为 x0 , 对函数对函数 f(x) 作泰勒展开作泰勒展开200000()( )()()()()2!fxf xf xfxxxxx000()()()0f xfxxx若若 f (x0)0, 即可求解方程即可求解方程0100()()f xxxfx1x3.3.

31、1 牛顿迭代公式牛顿迭代公式000()()f xxxfx近似方程近似方程 f (x) = 053再把再把 x1 作为新的近似根，同样处理作为新的近似根，同样处理，可得，可得1211()()f xxxfx依此类推，可得到依此类推，可得到1(),(0,1,2,)()kkkkf xxxkfx 牛顿迭代公式牛顿迭代公式利用牛顿迭代公式求根的方法利用牛顿迭代公式求根的方法称称为为牛顿迭代法牛顿迭代法2x3.3.1 牛顿迭代公式牛顿迭代公式54牛顿法的几何意义：牛顿法的几何意义：000()()()yf xfxxx是曲线是曲线 y = f (x) 上过点上过点( x0 , f (x0) ) 处的切线方程处的

32、切线方程x0y = f(x)x1x2x*000()()()0yf xfxxxy 切线与切线与x轴的交点为轴的交点为0100()()f xxxfx1211()()f xxxfx000( )()()()f xf xfxxx55例例 用用牛顿法求方程牛顿法求方程xf xxe( )10在在x0=0.5附近附近的实根，的实根，精度要求精度要求0.5 10-4。解：解：xxfxexe( ) 牛顿迭代格式为牛顿迭代格式为1()()kkkkf xxxfx 取初值取初值 x00.5，计算得到计算得到-,(0,1,2,)1kxkkkxexkx 56k0123xk0.50.571020.567160.56714f=inline(x*exp(x) -1);f2=inline(exp(x)+x*exp (x) );x0=0.4;er=1;k=0;while er0.00005 x=x0-f(x0)/f2(x0) er=abs(x-x0); x0=x;k=k+1;end牛顿迭代法牛顿迭代法不动点迭代法不动点迭代法-迭代格式的构造迭代格式的构造迭代的敛散性条件迭代的敛散性条件迭代法的局部收敛性迭代法的局部收敛性迭代法的收敛速度迭代法的收敛速度牛顿法牛顿法牛顿法的局部收敛性牛顿法的局部收敛性3.3