数值分析第七章非线性方程与方程组的数值解法0607)

1、第七章 非线性方程的数值解法一些基本概念 非线性方程 如如 方程的根 如果实数如果实数 满足满足 ，则称，则称 为方程的根为方程的根 m重根 若若 能分解为能分解为 ，则称，则称 为方为方程的程的m重根重根77.418 .381 .11)(23xxxxf*x( *) 0f x *x)(xf)(*)()(xgxxxfm*x二分法不动点迭代法牛顿法求根问题的敏感性与多项式的零点非线性方程的数值解法一、二分法1. 二分法的理论基础介值定理介值定理- 设f 是区间a,b上的连续函数，满足f (a)f (b)0，那么f在a与b之间有一个根，即存在一个数r（arb），使f(r)=0.一、二分法一、二分法2

2、. 二分法的求解步骤考察有根区间a,b，检查中点 上的函数值若f (c)=0，c为f (x)=0的根 否则若f (a)f (c)0，有根在a,c区间中 否则若f (c)f (b)0，有根在c,b区间中对规模更小的有根区间，重复以上步骤，直到区间长度小于2)(bac一、二分法3. 二分法的一个例题.25 . 1 , 0 . 1 01 3位小数点后内的一个实根，准确到在求 xx 例2例2k ak bk xkf(xk)符号0123456 1.0 1.25 1.31251.3203 1.5 1.3751.34381.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203

3、 1.3242 + + + 一、二分法4. 二分法的优缺点 二分法的优点是算法简单，且总是收敛的，缺二分法的优点是算法简单，且总是收敛的，缺点是收敛太慢点是收敛太慢一、二分法习题：考虑方程 .1) 求一个长度为1的区间 a,b ，使方程在其中有一个解.2) 以a,b开始，要算出10-10的之内的解需要多少步二分法？用整数回答.43=+10 xx二、不动点迭代法1.不动点不动点不动点- 如果 ，则称x*为 的一个不动点方程的根与不动点方程的根与不动点- 方程 总可以写成等价形式- x*为方程 的根等价于x*为 的不动点 ) *(*xx)(x0)(xf )(xx0)(xf )(xx二、不动点迭代法

4、2. 不动点迭代法 x0=初始估计初始估计 1() 0 1kkxx,k, , 当步数趋于无穷时，数列xk可能收敛，也可能不收敛。如果连续且xk收敛到x*，那么x*就是一个不动点。二、不动点迭代法2. 不动点迭代法kxk012345671.51.357211.330861.325881.324941.324761.324731.32472. ,39.12,375. 2 , 5 . 1 , 1 (2) 21031xxxxxkk.*5 . 101 3xxx附近的根在求 例3例3解解 ：二、不动点迭代法2. 不动点迭代法31)(xx二、不动点迭代法2. 不动点迭代法1)(3 xx不动点迭代法收敛：不动

5、点迭代法收敛：1. 不动点存在不动点存在2. 迭代序列收敛迭代序列收敛二、不动点迭代法3. 存在性与收敛性定理定理1（不动点存在唯一性定理不动点存在唯一性定理） 设(x)Ca, b满足以下两个条件： 1). 对任意xa, b有a(x)b. 2). 存在正数L1，使对任意x,ya, b都有则(x)在a, b上存在唯一的不动点x*. |;| )()(|yxLyx二、不动点迭代法3. 存在性与收敛性全局收敛的充分条件全局收敛的充分条件- 定理2 设(x) 满足定理1中两条件，则对任意x0a, b，迭代法收敛，并有误差估计式原则上确定迭代次数，但它由于含有信息L而不便于实际应用.(2.5) . |1|

6、*| 01xxLLxxkk(2.6) . |11|*|1kkkxxLxx二、不动点迭代法3. 存在性与收敛性全局收敛的充分条件全局收敛的充分条件- 定理2 设(x) 满足定理1中两条件，则对任意x0a, b，迭代法收敛，并有误差估计式(2.5) . |1|*| 01xxLLxxkk(2.6) . |11|*|1kkkxxLxx只要相邻两次计算结果的偏差足够小即可保证近似值xk具有足够精度二、不动点迭代法3. 存在性与收敛性局部收敛性局部收敛性- 定义1 设(x)有不动点x*，若对任意x0 x* 的某个邻域R，迭代公式(2.2)产生的序列xkR，且收敛到x*，则称迭代法(2.2)局部收敛. 二、

7、不动点迭代法3. 存在性与收敛性局部收敛的充分条件局部收敛的充分条件- 定理3 设x*为(x)的不动点，(x)在x*的某个邻域连续，且 ，则迭代法(2.2)局部收敛. 1|*)(| x. 3*03 2xx的根求方程只用四则运算不用开方例4例4 ; 1132*)(12)(3121xxxxxxkkk，）（ ; 1*)(3)(3221xxxxxkk，）（ ;134. 0231*)(21)() 3(41321xxxxxxkkk，）（. 0*)()31 (21)()3(214 21xxxxxxkkk，）（kxk迭代法(1) 迭代法(2) 迭代法(3)迭代法(4)0123 ? x0 x1 x2 x3 ?2

8、3987?21.521.5?21.751.734751.732631?21.751.7321431.732051?不同不动点迭代不同不动点迭代收敛速度不一样收敛速度不一样二、不动点迭代法4. 收敛阶（速度） 定义2 设迭代过程xk+1=(xk)收敛于方程x=(x)的根x*，如果 则称该迭代法是p阶收敛的. 特别地，p=1( |C|1时称超线性收敛， （p=2时称平方收敛）. 1*lim*kpkkxxCxx 二、不动点迭代法4. 收敛阶（速度）- 定理4（p阶收敛的充分条件 ） ：对于迭代过程xk+1=(xk)，如果(p)(x)在所求根x*的邻近连续，并且 则该迭代过程在x*的邻近是p阶收敛的.

9、, 0*)(0*)(*)(*)()()1( xxxxpp，一、不动点迭代法习题： 1）求 的每一个不动点，并确定不动点迭代是否局部收敛于它.22)(2xxx三、迭代收敛的加速方法1.埃特金加速收敛方法加速方法加速方法3210 xxxx321xxx, ,k,xxkk10 )(1kkkkkkkxxxxxxx122112)(三、迭代收敛的加速方法2.斯特芬森迭代法加速方法加速方法- 将埃特金加速技巧与不动点迭代结合00 zy11 zy22 zy)( ),(kkkkyzxy 2)(21kkkkkkkxyzxyxx0 x1x2x四、牛顿法1.牛顿法的基本算法 设设 x*是方程是方程 f (x)=0 的根

10、的根, xk是是x*的近似值的近似值.将将 f (x)在在 xk 附近附近展开展开, 有有 ()()()0kkkf xfxxx .)()( ;1kkkk0 xfxfxxx初始估计 牛顿迭代法牛顿迭代法四、牛顿法1.牛顿法的基本算法牛顿迭代法的几何解释牛顿迭代法的几何解释xyx*x00100()()fxxxfxx 1x 2000:()()()Tangent line yf xfxxx1211()()fxxxfx二、牛顿法应用举例二、牛顿法应用举例.0 的根用牛顿法求方程xex例7例7. 5 . 0 ), 2 , 1 , 0( 1 01xkxexxxkxkkkk取初值解：牛顿迭代公式为kxk012

11、30.50.571020.567160.56714，应用牛顿法解二次方程对于给定正数0 , 2CxC例例8 8;115并求.00迭代公式皆平方收敛证明x(4.5) ). (212 21kkkkkkxCxxCxxx解：. 01 ,1150 xC初值取kxk012341010.75000010.72383710.72380510.723805四、牛顿法2. 收敛性牛顿法就是对 的不动点迭代法单根情形单根情形( ( f (x*)0 ) )- - 因此牛顿迭代法局部平方收敛，)()()( xfxfxx , 0*)(*)(*)(*)( 2 xfxfxfx,*)(*)(*)( xfxfx . *)(2*)

12、( *)(*lim 21xfxfxxxxkkk 四、牛顿法2. 收敛性牛顿法就是对 的不动点迭代法单根情形单根情形( ( f (x*)0 ) )- 例 用牛顿法求f(x)=x2-a (a0)的根的收敛性及收敛速度.- 解 f (a)=2a0，平方收敛，平方收敛 收敛速度收敛速度)()()( xfxfxx . 21222 )a(lim 21aaxaxkkk四、牛顿法2. 收敛性牛顿法就是对 的不动点迭代法重根情形重根情形( ( f (x*)=0 ,.,f (m-1)(x*)=0, f (m)(x*)0) )- - 因此牛顿迭代法局部线性收敛， )()()( xfxfxx , 011*)( mx0

13、*)( x . 1 *lim 1mm-xxxxkkk四、牛顿法2. 收敛性牛顿法就是对 的不动点迭代法重根情形重根情形( ( f (x*)=0 ) )- 例 用牛顿法求f(x)=xm的根.- 解 收敛速度？ )()()( xfxfxx .1)()(1kkkkkkkxmmmxxxfxfxx, 1100 111mmxxxmmxkkkk线性收敛.四、牛顿法2. 收敛性牛顿法就是对 的不动点迭代法重根情形重根情形( ( f (x*)=0 ,.,f (m-1)(x*)=0, f (m)(x*)0) )- )()()( xfxfxx.*)( )()()( )()( )(:11xxfxfxxxxxxfxfm

14、xxkkkkkkkk均局部平方收敛于，或修正牛顿法四、牛顿法习题： 1）求求f(x)=sin x+x2cos x-x2-x的根的根x*=0的重数，并估的重数，并估计牛顿法收敛到计牛顿法收敛到6位正确小数所需步数位正确小数所需步数(设设x0=1).四、牛顿法2.简化牛顿法和牛顿下山法简化牛顿法简化牛顿法- 牛顿法每步需计算f (xk),计算量大，且有时得不到，简化牛顿法可避免计算导数.- .)()( ;01xfxfxxxkkk0初始估计简化牛顿法： 四、牛顿法2.简化牛顿法和牛顿下山法牛顿法下山法牛顿法下山法- 牛顿法只有局部收敛性，若初始点偏离x*较远，牛顿法可能发散，牛顿法下山法可防止牛顿法

15、发散.四、牛顿法2.简化牛顿法和牛顿下山法牛顿法下山法牛顿法下山法- 牛顿法只有局部收敛性，若初始点偏离x*较远，牛顿法可能发散，牛顿法下山法可防止牛顿法发散.- )()(10 .)1 ( ;)()( 1111kkkkkkkkkxfxfxxxxfxfxx，使取牛顿法下山法：五、弦截法与抛物线法 避免牛顿法中对导数的计算，同时具有超线性收敛避免牛顿法中对导数的计算，同时具有超线性收敛速度的两种算法速度的两种算法五、弦截法与抛物线法1.弦截法算法算法1111; (). ()()0kkkkkkkxxxxxxf xf xf x 弦弦截截法法 ，初初始始估估计计 五、弦截法与抛物线法1.弦截法收敛性估计

16、收敛性估计- 可以证明，在弦截法收敛到x*，且f (x*)0的假设下，近似误差关系 成立，也就意味着11*)( 2*)( kkkeexfxfe11( *)151.6182( *)2kkfxeefx ，弦截法超线性收敛.五、弦截法与抛物线法2.抛物线法算法算法- 其中，为以xk.xk-1,xk-2为插值节点的插值多项式P2(x)的零点.- 抛物线法也适用于求解多项式的实根和复根. .,)(4)(2 ;, 212121kkkkkkk0 xxxfxfxfxxxxx初始估计抛物线法五、弦截法与抛物线法2.抛物线法收敛性估计收敛性估计- 迭代估计有下列渐近表达式可见抛物线法也是超线性收敛的。，840.

17、142. 01*)( 2*)( kkexfxfe六、求根问题敏感性与多项式零点1.求根问题敏感性与病态代数方程求根问题敏感性求根问题敏感性- 求根问题：f (x)=y，已知y，求x.- 条件数： 若|f (x*)|非常小，求根问题病态.*)( 1xfyx六、求根问题敏感性与多项式零点1.求根问题敏感性与病态代数方程病态代数方程病态代数方程- 对多项式若系数有微小扰动，对根影响很大，则p(x)为病态代数方程.- 条件数：令, 0)(01110aaxaxaxaxpnnnn，0)()()(xqxpxp)( )()0()0()(kkkkkxpxqddxxx 例例1212 多项式 解解 取 的根由（6.

18、4）可得56732228)7()2)(1()(xxxxxxxp.5040130681313267691960234xxxx)(,002. 0,)(6xpxxq).7,2, 1(kkxk,)(, )()(6kxqjkxpkkjk.)!7()!1()002.0()1()(61kkkkxkk实际上，方程 的根 分别为0)(6 xxp)(kx7.2330128.i,54012578.04586758.5,8195692.3,0331253.3,9989382.1,0000028.1这说明方程是严重病态的.六、求根问题敏感性与多项式零点2.多项式的零点使用牛顿法求解使用牛顿法求解- 对p(x)=0使用牛顿法计算出第一个根，计算过程使用秦九韶算法计算多项式及其导数值；- 对 使用牛顿法计算第二个根；- . - 为二次多项式可直接求解., 0)(111nnnnpxpx